KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Dörre, Felix; Klebanov, Vladimir


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.

Volltext §
DOI: 10.5445/IR/1000058113
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 2016
Sprache Englisch
Identifikator ISSN: 2190-4782
KITopen-ID: 1000058113
Verlag Karlsruher Institut für Technologie (KIT)
Umfang 14 S.
Serie Karlsruhe Reports in Informatics ; 2016,12
Schlagwörter 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