[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 5 May 2016 11:23:50 +0200
From: Hanno Böck <hanno@...eck.de>
To: oss-security@...ts.openwall.com
Subject: Re: broken RSA keys
Hi,
I've now done a bit more thorough analysis, but I really don't think
there's anything overly interesting to find here.
A comment before: The guy who publicized this stuff via his blog writes
some very confused blog entrys and has lately written one where he
threw a lot of insults at me and declared that I'm responsible for
everything that's wrong with computers and with the world. So please
understand that I find it a bit hard to deal with these people, and I
won't attempt to communicate with them in any way. But I'll try to do my
best to clarify what I know. (I don't know if/how the author of phuctor
who wrote in this thread is related to these blogposts.)
As a background: What we're talking about is a so-called batch-gcd
attack, developed by DJB. Arjen Lenstra and Nadia Heninger were as far
as I know the first ones to use this on publicly available keysets in
order to find vulnerable keys. The implementation from Nadia Heninger is
freely available [1] and some code to turn a pgp keyserver dump into a
mysql database is available from me [2]. So everyone should be able to
replicate what I'm saying (the workflow is: use my script to turn
keyserver dump into a database, select the rsa_n value from the
keys_rsa table, run sort -u on it, feed the result into nadia's fastgcd
tool). It takes a couple of hours on a fast machine to replicate the
attack.
What one will find are 273 vulnerable moduli. Of those most have
invalid self signatures. If you look at them the most plausible
explanation is that they're the result of data errors. You'll
find corresponding valid keys for most/all of them (I have only checked
some manually). If you look into them you'll find stuff like this:
f92f34e31bfcd57369ae04bf87888cfbca5525e3b24dd55aa4f7775ffb631c24f511c8de4c6707d3f685ea75c8b5f6e432e86fea10edaa6ed4812cdd51a90203010001300b06092a864886f70d010104030100fdfdfdfd00000000000000000000000000b0120a01e8220a01684640005000000010000000010000002a000000
f92f34e31bfcd57369ae04bf87888cfbca5525e3b24dd55aa4f7775ffb631c24f511c8de4c6707d3f685ea75c8b5f6e432e86fea10edaa6ed4812cdd51a90203010001300b06092a864886f70d010104030100fdfdfdfd00000000000000000000000000b0120a01e8220a01684640005000000010000000010000002a000000
Or in short: lots of repetitions, zero and ff values. I think it'll be
very hard to pinpoint what the source of these issues is, but it looks
a lot like simple data errors. I assume network transmission problems,
disk failures or software bugs. It's also possible that
people just messed with a hexeditor in keys and uploaded them. I think
all primefactor patterns are just factors that happen to be likely once
you do such random data errors.
Now to the 10 keys that have valid selfsigs. Two are for
alice@...mple.com (and honestly it may be that these one comes from me,
but I don't remember exactly. I created broken test keys, but I don't
know if I uploaded any. At least the date roughly matches when I worked
on this).
2 keys are for Texas Instruments and 512 bit. That's probably some joke
referring to the breakage of TI signing keys [3]. One key is for "FAKE:
key generation test", one has an empty userid field. They're probably
examples as well.
That leaves 4 keys that look somewhat reasonable. They're all really
old (>10 years). Of those two have very small gcd factors and are
pre-2000. The other two are from 2001 and have large factors.
The last two are supposedly (from what Nadia Heninger told me) from a
software called CryptoEx from a german company Glück&Kanja.
Unfortunately one doesn't find this software anywhere online, just some
old press releases. The product later got bought by PGP (aka
what today belongs to symantec).
Honestly I don't think there's too much to see here. There likely was a
very old commercial PGP implementation that created broken keys. Maybe
there were two (because of the two keys with small primefactors). And
the keyservers take broken copies of valid keys without complains, as
they don't check any signatures. Plus there are some keys that look
like people manually creating broken test keys. I don't see any sign of
a deliberate attack in this data. But you don't have to take my word
for it. The software and data I used to analyze this is all public.
I'll upload a keyids file to the pgpmoduli repo:
https://github.com/hannob/pgpmoduli
The way to interpret that data is that line numbers match. I.e. the gcd
in line 10 of gcds matches the modulus in line 10 of vulnerable_moduli
and the keyid in line 10 of keyids etc.
Slightly related: There are other ways to search for bad pgp (or
generally crypto) keys. I once searched for broken DSA keys (due to
duplicate r values) [4] and found one broken key and for RSA-CRT issues
and found one other broken key (E46DEB00098894FD). The first came from
a beta of an app, the second is of unknown source (the crt issue is
something I haven't published anywhere before).
[1] https://factorable.net/resources.html
[2] https://github.com/hannob/pgpecosystem
[3]
https://en.wikipedia.org/wiki/Texas_Instruments_signing_key_controversy
[4] https://eprint.iacr.org/2015/262
--
Hanno Böck
https://hboeck.de/
mail/jabber: hanno@...eck.de
GPG: BBB51E42
Content of type "application/pgp-signature" skipped
Powered by blists - more mailing lists
Please check out the
Open Source Software Security Wiki, which is counterpart to this
mailing list.
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
