[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20160504172803.GA19393@openwall.com>
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[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.
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[0] = 0xC0F5A603
limb[1] = 0xA4F093A7
limb[2] = 0xE3FAEDA6
limb[3] = 1
which satisfies:
limb[1] = limb[0] + limb[2] + 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.
