KIT | KIT-Bibliothek | Impressum

Practical Detection of Entropy Loss in Pseudo-Random Number Generators : Extended Version

Dörre, Felix; Klebanov, Vladimir

Abstract:
Pseudo-random number generators (PRNGs) are a critical infrastructure for cryptography and security of many computer applications. At the same time, PRNGs are surprisingly difficult to design, implement, and debug. This paper presents the first static analysis technique specifically for quality assurance of cryptographic PRNG implementations.
The analysis targets a particular kind of implementation defect, the entropy loss. Entropy loss occurs when the entropy contained in the PRNG seed is not utilized to the full extent for generating the pseudo-random output stream. The Debian OpenSSL disaster, probably the most prominent PRNG-related security incident, was one but not the only manifestation of such a defect.
Together with the static analysis technique, we present its implementation, a tool named Entroposcope. The tool offers a high degree of automation and practicality. We have applied the tool to five real-world PRNGs of different designs and show that it effectively detects both known and previously unknown instances of entropy loss.


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2016
Sprache Englisch
Identifikator DOI(KIT): 10.5445/IR/1000058113
ISSN: 2190-4782
URN: urn:nbn:de:swb:90-581132
KITopen ID: 1000058113
Verlag Karlsruhe
Umfang 14 S.
Serie Karlsruhe Reports in Informatics ; 2016,12
Schlagworte Pseudo-Random Number Generator; PRNG; entropy loss; information flow; OpenSSL; static analysis; bounded model checking
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page