A Tool for finding implementation bugs in PRNGs

Entroposcope

Entroposcope is the first static analysis for finding implementation bugs in pseudo-random number generators (PRNGs). More precisely, Entroposcope finds instances of entropy loss, i.e. two seeds leading to the same output.

Entroposcope is developed by Vladimir Klebanov and Felix Dörre. The method behind Entroposcope is described in:

Felix Dörre and Vladimir Klebanov:
Practical Detection of Entropy Loss in Pseudo-Random Number Generators
ACM Conference on Computer and Communications Security (CCS)
PDF (preprint) - BibTeX - ACM DL

Included further below are a few screenshots illustrating what the user sees.

Entroposcope detected the Libgcrypt / GnuPG bug

Entroposcope has been instrumental in finding the recent bug in the Libgcrypt PRNG, which is also used in GnuPG (CVE-2016-6313). The bug survived 18 years of service and several external audits. A description of the bug is available here:

Felix Dörre and Vladimir Klebanov:
Entropy Loss and Output Predictability in the Libgcrypt PRNG (CVE-2016-6313)
PDF

Explanation of the screenshots

The links below show dumps from the Entroposcope's counterexample visualizer. You are looking at two runs of the PRNG in a side-by-side diff. At the top is the seed for each run. At the very bottom is the PRNG output. Inbetween is a trace of the PRNG invoking cryptographic primitives (typically SHA-1) with their inputs and outputs. The primitives have been replaced by idealizations. The colors help trace the dataflow.

Screenshot: The Debian OpenSSL disaster

Here's how the Debian OpenSSL disaster looks like in Entroposcope. The seed is completely uncolored, i.e., it has no influence on the output. The problem occurs before the first call to SHA-1.

Screenshot: A bug in OpenSSL's entropy pool implementation

Another OpenSSL anomaly. This one is still present in latest code. Look at the last byte of the seed. This is the byte that has no influence on the output. The problem is small and not exploitable in practice, but this is only by chance. Pointer manipulation in complex circular data-structures is error-prone.

Screenshot: After fixing the above one

This is OpenSSL after fixing the problem. This is actually no longer a counter-example, as there are no two distinct seeds leading to the same output.

Contact

If you are interested in the tool or have other questions, send an email.