Re: broken RSA keys

[Stanislav Datskovskiy <stas () loper-os org>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Author of Phuctor speaking.  I would like to point out that there is a
'contact' button on the site, anyone who wishes can click and ask
questions in real time.  Readers are encouraged to do this!

A few observations of possible interest to the folks on this list:

1) We presently know of 165 keys containing 'mirrored' moduli.
They, and the process whereby they were found in an SKS dump, even
prior to being properly 'phuctored', can be seen at
http://trilema.com/2015/more-factored-rsa-keys-and-assorted-other-considerations
.

2) The list of affected persons and organizations includes a number of
possibly 'politically interesting' targets, e.g., mathematicians, open
source projects (Debian, a few others), plus a few other delicacies,
such as 'Apple Product Security', 'PGP Corporation Update Signing
Key', etc.

3) The 'mirrored' keys found thus far in no case have valid
self-signatures. (A number of the remaining phuctored keys - do.) Thus
it does not follow from the facts at hand that these particular keys
were generated /by the people and organizations whose names appear in
the user string/ !

4) One parsimonious explanation for (1) given (2) and (3) is that the
'mirrored' keys were generated by a malicious actor, who counted on
the principle described at, e.g.,  https://evil32.com ,
https://bugs.gnupg.org/gnupg/issue1579 - whereby older versions of GPG
will regard the bottom 32 bits of a modulus as the 'fingerprint',
rather than performing a hash.  The SKS network happily accepts such
keys, and will list them as search results if the username associated
with a genuine key is searched for.  PGP/GPG clients which do not
check a key's self-signatures will happily encipher to a 'mirrored'
key, and the adversary presumably counted on having access to the
resulting ciphertext. A program which generates a 'mirrored'
fraudulent key for any particular public key on SKS can be written
trivially. (In the interest of not encouraging low-effort hooliganism,
I have not posted this simple program publicly. It is left as an
exercise for the reader.)

- -S
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)

iQEcBAEBCgAGBQJXKp8UAAoJELmCKKABq//HnLoH/jo5vxYhasg+7FgZtqQ44dh3
cxUNit7w41DtIOT93LkEn3ZPw1z1Q8u0qD6RUJKHTUwxYDwkjE2jV9HVV0/n4Pdj
+ma9q7K+1lHV5QOpMvuNl05oakHLTpc5P0iC0T+tULz7gC8Y1UwkUbGcYIunXQT6
7fTi1z19emSxu9pJtLtfZoRX+7KEGdpdWmX4gIOCS8Gc7YJd2Oco/nzdXwEmpCfn
Qr+kjGu4SkX4Iy34JDQ54Psy+sNiKP13rifvCKNoMKU4I2sEC/ilxGcj0wSSqvYX
0J0ZWp9hlHOnonQUre2AyTPDO8hSlmoc2rcqOi7Y10HCpZZeihlT2cODbcbBrXc=
=w4Ox
-----END PGP SIGNATURE-----


On Wed, May 4, 2016 at 1:28 PM, Solar Designer <solar () openwall com> wrote:
> 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