[cryptography] Duplicate primes in lots of RSA moduli

Thierry Moreau thierry.moreau at connotech.com
Sun Feb 19 12:39:45 EST 2012

Ben Laurie wrote:
> On Fri, Feb 17, 2012 at 8:39 PM, Thierry Moreau
> <thierry.moreau at connotech.com> wrote:
>> Ben Laurie wrote:
>>> On Fri, Feb 17, 2012 at 7:32 PM, Thierry Moreau
>>> <thierry.moreau at connotech.com> wrote:
>>>> Isn't /dev/urandom BY DEFINITION of limited true entropy?
>>> $ ls -l /dev/urandom
>>> lrwxr-xr-x  1 root  wheel  6 Nov 20 18:49 /dev/urandom -> random
>> The above is the specific instance on your environment. Mine is different:
>> different kernel major/minor device numbers for /dev/urandom and
>> /dev/random.
> So? Your claim was "Isn't /dev/urandom BY DEFINITION of limited true
> entropy?" My response is: "no".
>> I got the definition from
>> man 4 random
>> If your /dev/urandom never blocks the requesting task irrespective of the
>> random bytes usage, then maybe your /dev/random is not as secure as it might
>> be (unless you have an high speed entropy source, but what is "high speed"
>> in this context?)
> Oh, please. Once you have 256 bits of good entropy, that's all you need.

First, about the definition, from "man 4 random":

A  read  from  the  /dev/urandom device will not block waiting for more 
entropy.  As a result, if  there  is  not  sufficient  entropy  in  the 
entropy  pool,  the  returned  values are theoretically vulnerable to a 
cryptographic attack on the algorithms used by the  driver.   Knowledge 
of how to do this is not available in the current non-classified 
literature, but it is theoretically possible that such an attack may 
exist.  If this is a concern in your application, use /dev/random instead.

If the RSA modulus GCD findings is not a cryptographic attack, I don't 
know what is. (OK, it's not published as an attack on the *algorithm*, 
but please note the fact that /dev/urandom cryptographic weakness may be 
at stake according to other comments in the current discussion.)

Second, about sufficiency of "256 bits of good entropy", the problem 
lies with "good entropy": it is not testable by software because entropy 
quality depends on the process by which truly random data is collected 
and the software can not assess its own environment (at least for the 
Linux kernel which is meant to be adapted/customized/built for highly 
diversified environment).

Third, since "good entropy" turns out to become someone's confidence in 
the true random data collection process, you may well have your own 

In conclusion, I am personally concerned that some operational mishaps 
made some RSA keys generated with /dev/urandom in environments where I 
depend on RSA security.

And yes, my concern is rooted in the /dev/urandom definition as quoted 

If I am wrong in this logical inference (i.e. the RSA modulus GCD 
findings could be traced to other "root cause" than limited entropy of 
/dev/urandom), then I admittedly have to revise my understanding.


- 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