[ale] 4 of 1000 public keys provide no security

[Derek Atkins]

Just to play devil's advocate here:

1) The keys searched span over 20 years of key material, so many of these
bad keys are probably expired.
2) Only one of those "bad" keys was signed by a trusted CA
2a) that one key had already expired
3) There were a bunch of known "keygen" bugs (including a major one in
OpenSSL) a few years ago, and most likely these keys were generated with
those known bugs.

So I would not write this off as the end of the world.  I would, instead,
take it as a lesson that minor things (like a Bad RNG) can truly affect
the outcome of the system as a whole.  However even a bad RNG is only
likely to affect multiple users of that bad RNG.  The research did not
explore the origins of the "bad keys".

-derek, your resident security guru, and instigator of the RSA129 crack team.

On Fri, February 17, 2012 10:47 am, George Allen wrote:
> Judging by this, Could there be a potential to make rainbow tables vs.
> SSL keys?!
>
>>From ARS:
>
> An astonishing four out of every 1,000 public keys protecting webmail,
> online banking, and other sensitive online services provide no
> cryptographic security, a team of mathematicians has found. The
> research is the latest to reveal limitations in the tech used by more
> than a million Internet sites to prevent eavesdropping.
>
> The finding, reported in a paper (PDF) submitted to a cryptography
> conference in August, is based on the analysis of some 7.1 million
> 1024-bit RSA keys published online. By subjecting what's known as the
> "modulus" of each public key to an algorithm first postulated more
> than 2,000 years ago by the Greek mathematician Euclid, the
> researchers looked for underlying factors that were used more than
> once. Almost 27,000 of the keys they examined were cryptographically
> worthless because one of the factors used to generate them was used by
> at least one other key.
>
> "The fact is, if these numbers had the entropy that they were supposed
> to have, the probability of even one of these events happening in 7
> million public keys would be vanishingly small," James P. Hughes, an
> independent cryptographer who participated in the research, told Ars.
> "We thought that was rather startling."
>
> ...
>
> The revelation that such a large proportion of public keys were
> generated with a prime factor shared by one or more other keys means
> that such keys are trivial to break by anyone who can identify them.
> What's more, the percentage of keys known to be generated with
> non-unique factors is likely to grow as more keys are analyzed. The
> 0.38 percentage rate of faulty keys found when the researchers looked
> at 7.1 million total keys compares with a 0.26 percent rate in an
> earlier analysis that considered only 4.7 million RSA moduli. As a
> result, the true number of keys that could be broken using the
> technique may be higher than the current research reveals.
>
> ...
>
> http://arstechnica.com/business/news/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security.ars?src=fbk
> _______________________________________________
> Ale mailing list
> Ale at ale.org
> http://mail.ale.org/mailman/listinfo/ale
> See JOBS, ANNOUNCE and SCHOOLS lists at
> http://mail.ale.org/mailman/listinfo
>


-- 
       Derek Atkins                 617-623-3745
       derek at ihtfp.com             www.ihtfp.com
       Computer and Internet Security Consultant