[cryptography] Duplicate primes in lots of RSA moduli

Thierry Moreau thierry.moreau at connotech.com
Mon Feb 20 12:22:19 EST 2012

Ben Laurie wrote:

>> On Sun, Feb 19, 2012 at 05:57:37PM +0000, Ben Laurie wrote:
>>> In any case, I think the design of urandom in Linux is flawed and
>>> should be fixed.
> In FreeBSD random (and hence urandom) blocks at startup, but never again.

Thanks for bringing this freebsd random source design as this neat summary.

I take this opportunity to review the Linux design decisions.

First, let me put aside the initial entropy assessment issue -- it's not 
solvable without delving into the details, and let me assume the freebsd 
entropy collection is good, at the possible cost of slowing down the 
boot process.

Then, basically the freebsd design is initial seeding of a deterministic 
PRNG. If a) the PRNG design is cryptographically strong (a qualification 
  which can be fairly reliable if done with academic scrutiny), and b) 
the PRNG state remains secret, THEN the secret random source is good 
through the system operating life cycle. (I make a restriction of the 
design as a simple PRNG because periodic true random data merging into 
the PRNG state is something not studied in the algorithmic theory 

The secrecy of the PRNG state is a requirement NO GREATER THAN the 
secrecy of any long-term secret (e.g. a MAC symmetric key or a digital 
signature private key) needed during the system operating life cycle. 
Even if there were a few cases where a security system requires a random 
source, but not a single long-term secret, an anecdotal case may not be 
the best model for a general-purpose OS design. By logical inference 
then, requiring continuous (or periodic) true random data collection is 
an over-design (i.e. engineering resources better put into greater 
assurance about secrecy protections), or a plain design flaw (remaining 
vulnerabilities in the secrecy attack vectors overlooked due to 
attention paid to true random data collection).

So, the freebsd design appears reasonable to me. Can it be brought into 
Linux? Is it a Linux design flaw to omit boot-time entropy assessment?

My answers are "only as an option" and "no".

The design glitch is the blocking at boot time for entropy assessment 
(wait until the entropy pool is filled at an adequate level).

By essence, true random data collection is antagonistic to a complex 
computer system. Generally, you want a computer system to behave 
predictably. Specifically, it would be sad if your next aircraft 
boarding ends in a crash because a bad pointer in the fly-by-wire 
software referred to a memory location holding a precise interrupt 
timing measurement instead of a fixed data value (RTCA D0178B in a 
nutshell). In practice, almost every strategy for collecting true random 
data based on unpredictable facets of computer technology turns void 
with the technological advances. Dedicated devices or audio ports cost 
money and/or provisioning hindrance.

Thus, the blocking at boot time for entropy assessment may be not be 
acceptable as a default for Linux: it is hard to provide an upper limit 
of the blocking time, and it is certainly not perceived as useful by a 
large portion of system users/operators. The freebsd design for 
/dev/{,u}random appears fit for a more understanding users/operators base.

The mental model for authentication key generation operation should 
reflect the fact that "it requires the computer to roll dice very 
secretly for your protection, but the computer is very poor at this type 
of dice rolling -- it may thus take time and/or require you to input 
anything on the keyboard/mouse/touchscreen until adequate dice shaking 
simulation has been achieved".

If security experts are not prepared to face this fact -- true random 
data collection and associated entropy assessment can not be made 
intrinsic to a computer system -- we are unjustified to expect OS 
suppliers to provide a magic fix, or software developers to take the 
liberty to solve an issue which is seldom stated.

In this perspective, the root cause for the RSA modulus GCD findings is 
the security experts inability to recognize and follow-up the 
ever-present challenges of secret random data generation. As such, the 
Linux design is seldom at stake.

Just my view, enjoy!

- Thierry Moreau

CONNOTECH Experts-conseils inc.
9130 Place de Montgolfier
Montreal, QC, Canada H2M 2A1

Tel. +1-514-385-5691

More information about the cryptography mailing list