oss-sec mailing list archives
broken RSA keys
From: Solar Designer <solar () openwall com>
Date: Wed, 4 May 2016 15:42:48 +0300
Hi, As many of you know, the projects factorable.net and Phuctor have identified some weak RSA keys in the wild - on (key)servers or submitted to those projects. This does not necessarily mean that the weak keys were generated as such in all cases - it can as well be that keys got mangled later. (In fact, this has spurred heated debate and insults. Luckily, that's not the primary topic of my message, so I don't have to refer to it more directly risking to bring that controversy in here. Let's just not go into that direction at all.) Now to the point: some of the keys do look to me like they're a result of software bugs in key generation. Specifically, as it was noticed and noted by many before, Phuctor's list of broken keys includes many with non-prime e of the form intended_e*(2^32+1) - that is, with the 32-bit value duplicated across 64 bits. (I wrote it that way to show that all such e's are non-prime.) When looking into this a few days ago, I found that OpenSSL 0.9.5a (and earlier?), which was current in year 2000, had a bug that would result in behavior just like this on some 64-bit platforms: http://marc.info/?l=openssl-users&m=95961024500509 I've also checked libgcrypt's code since its commit history start in 1997 and to latest. Its RSA e setup looks OK to me: it uses libgcrypt's own *mpi*_set_ui(), which just set first limb without going to bit level. Additionally, both Phuctor's list and Hanno Bock's list of GCDs include many small factors that also exhibit 32-bit value duplication. To me, this speaks in favor of there being a bignum library bug like this. A bug that not only duplicates the least significant 32 bits onto the next 32 bits, but also keeps the rest of the limbs at all-zeroes. There are even weirder examples, though - e.g., one of Phuctor's factors is 0x115CFF61CFECFF61BE9, where we see three 32-bit limbs satisfying: limb[1] = limb[0] + limb[2] and also limb[2] is small and thus likely didn't come from a CSPRNG, but possibly from uninitialized memory. We may want to review other RSA and general bignum libraries for bugs that would match these patterns, although that's probably not any easier than just reviewing them for any bugs in related code paths. It is likely that something more recent than OpenSSL 0.9.5a still has a bug of this sort (besides, that OpenSSL bug can't explain the 3-limb relationship in a factor, above). Indeed, that "something" might turn out not to be open source, but we would care about and would be reviewing the open source libraries and programs - hence posting in here for now. Any volunteers? Please post to these thread about whatever you've reviewed, even if you came to the conclusion it probably isn't buggy (like I did for libgcrypt's e setup). Alexander P.S. I've attached the OpenSSL bug posting from 2000, for archival.
Attachment:
openssl-rsa-e-bug.txt
Description:
Current thread:
- broken RSA keys Solar Designer (May 04)
- Re: broken RSA keys Solar Designer (May 04)
- Re: broken RSA keys Solar Designer (May 04)
- Re: broken RSA keys Alexander Cherepanov (May 04)
- Re: broken RSA keys Stanislav Datskovskiy (May 04)
- Re: broken RSA keys Solar Designer (May 05)
- Re: broken RSA keys Alexander Cherepanov (May 05)
- Re: broken RSA keys Stanislav Datskovskiy (May 05)
- Re: broken RSA keys Solar Designer (May 12)
- Re: broken RSA keys Solar Designer (May 04)
- Re: broken RSA keys Solar Designer (May 05)
- Re: broken RSA keys Hanno Böck (May 05)
- Re: broken RSA keys Solar Designer (May 04)