How do we know our PRNGs work properly?

Presented at 33C3 (2016), Dec. 29, 2016, 11:30 a.m. (60 minutes)

Pseudo-random number generators (PRNGs) are critical pieces of security infrastructure. Yet, PRNGs are surprisingly difficult to design, implement, and debug. The PRNG vulnerability that we recently found in GnuPG/Libgcrypt (CVE-2016-6313) survived 18 years of service and several expert audits. In this presentation, we not only describe the details of the flaw but, based on our research, explain why the current state of PRNG implementation and quality assurance downright provokes incidents. We also present a PRNG analysis method that we developed and give specific recommendations to implementors of software producing or consuming pseudo-random numbers to ensure correctness. <P>Bugs in PRNGs often go unnoticed for years, as witnessed previously by the Debian OpenSSL disaster (2006-2008; see presentation at 25C3) or the Android PRNG vulnerability (2005-2013), which was responsible for a series of bitcoin thefts. This longevity has good reasons, as currently almost no effective technical safeguards against the PRNG flaws are in place. In public forums, questions about quality assurance for PRNGs are typically met with fatalistic shrugging, links to web comics, or links to statistical test suites. None of these approaches is effective in solving the problem. <P>In the past two years, we carried out research into correctness of cryptographic PRNGs, studying the effectiveness of various measures, and developing new ones. We analyzed numerous PRNGs that are currently in deployment. With this presentation we aim to convey insights into: <UL> <LI> the current state of PRNG implementations <LI> why quality assurance of PRNGs is difficult and <LI> why hardly any technical safeguards against flaws in PRNGs are currently in place <LI> the details of the GnuPG flaw that we uncovered <LI> the hidden technical similarities behind many PRNG flaws (such as the three mentioned above) <LI> which safeguards are effective and which are not <LI> how to improve the situation </UL>


  • Felix Dörre
    Bachelor student of computer science at KIT, Karlsruhe. Wrote his bachelor's thesis about the verification of Pseudo-Random-Number-Generators.
  • Vladimir Klebanov
    Up to 2016, Vladimir Klebanov was a postdoctoral researcher at Karlsruhe Institute of Technology, developing formal methods for program correctness and information security. Since 2016, he is part of the security testing & tools group at SAP SE.


Similar Presentations: