Date: Wed, 4 May 2016 20:28:03 +0300 From: Solar Designer <solar@...nwall.com> To: oss-security@...ts.openwall.com Subject: Re: broken RSA keys On Wed, May 04, 2016 at 03:42:48PM +0300, Solar Designer wrote: > 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 = limb + limb > > and also limb is small and thus likely didn't come from a CSPRNG, but > possibly from uninitialized memory. While the 32-bit duplication of e is probably for real (or those keys wouldn't validate... do they?), similar observations for factors are probably a red herring: an artifact of the process used by these factoring projects rather than part of how the keys were generated. Specifically, the above 3-limb example came from this key: http://phuctor.nosuchlabs.com/gpgkey/63016E43A530350EC983F09A74C50EC8E87FEB92F3DEAC355BE2E64CA7985921 Its listed factors for: 30994406304224333705089301021808817053265691600565745779461319192700482173499346901463373323760837101094422297015585914901975150808157025848055524050099664666818474403138047948921297911809676315880151194417982271740532112280276561406067150580272837889469704078603620474607973901168413284328036775114860003006242978036093114581459742298368645557721283839266550975745706234722636520751279031095530989644784794578820133689102573944830983932022310476740027696204630693285065012124122533231053902876463977914183401001126261496277170510153621628673978038897817661593063222593495679683291096299835912556781797309445223969995 are: 15010910703015 5124733305108403985385 149784613473514443594783892995 However, this modulus is also divisible by 3, 5, and thus by 15, etc. So what we're seeing in databases like this are just some larger non-prime factors that combine the smaller factors in specific ways. I understand that's not how they were figured out (rather, they're shared factors with other keys), but that's what they happen to be composed of. Moreover, the larger ones of the factors above are divisible by the smaller ones of them: 5124733305108403985385 / 15010910703015 = 341400559 149784613473514443594783892995 / 5124733305108403985385 = 29227787 So these are pretty much arbitrary, process-dependent combinations of smaller factors, and thus their bit patterns, etc. don't tell us much or anything about the nature of bugs in key generation, if there were any. (I say "if there were any" since the keys could as well have been mangled later.) BTW, had I not realized the above, I would now come up with an even more complex conspiracy theory about 149784613473514443594783892995, which is 0x1E3FAEDA6A4F093A7C0F5A603, so: limb = 0xC0F5A603 limb = 0xA4F093A7 limb = 0xE3FAEDA6 limb = 1 which satisfies: limb = limb + limb + 2 No idea why it's "+ 2" here, unlike in the smaller factor's example, but like I say this is just a conspiracy theory, and I think the simple explanation is it's an artifact of the process rather than any inherent property of the keys. Thus, I think it makes sense to focus on searching for bugs producing the 32-bit duplicated e's, after all. And it also makes sense to validate those keys - not merely rely on data already in these factoring projects' databases. Could it be that all of the broken e keys were generated by OpenSSL from year 2000 or earlier? Embedded copies in proprietary PGP implementations that have since been rebuilt for 64-bit? Doesn't sound very realistic, but who knows. Alexander
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.