Re: broken RSA keys

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

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


On Thu, May 5, 2016 at 4:17 AM, Solar Designer <solar () openwall com> wrote:
> When a modulus is (mangled?) such that each of its 64-bit limbs consists
> of two matching 32-bit limbs, it is necessarily a multiple of 2^32+1.
> That's because it can be represented as:
>
> N = {an an ... a1 a1 a0 a0} = (2^32+1) * {0 an ... 0 a1 0 a0}
>
> where the {...} notation means concatenated 32-bit limbs (or base 2^32
> digits, if you will).  From this, it follows that pairwise GCDs of such
> moduli will also have 2^32+1 as a factor, and this is what ultimately
> causes the 32-bit limb patterns in the GCDs.  As Alexander Cherepanov
> correctly pointed out, even the seemingly slightly more complex 32-bit
> limb patterns in the GCDs are merely indication of them being multiples
> of 2^32+1.  There's probably nothing else to see here.

Mircea Popescu (trilema.com) and I figured this out last May.
But the conclusion 'nothing to see here, move along' does not follow.

> > 1) We presently know of 165 keys containing 'mirrored' moduli.
>
> This is similar but not the same as the number Alexander Cherepanov
> posted after analyzing your data:

The 165, as described in the linked piece on Mircea's site, were obtained
by filtering an SKS dump specifically for the mirrored-32 pattern. Last May.
Said dump is about 95% of the way through Phuctor at the moment, so it
stands to reason that all of them will appear in it soon.

> Is your definition of "mirrored" different from "divisible by 2**32+1",
> or does something else (what?) cause the 165 vs. 152 discrepancy?

See above.

> Are all of the "politically interesting" targets' keys (at least those
> you explicitly listed in 2 above) "mirrored" (and don't have valid
> self-signatures, as you say)?

DISA's key appears to be well-formed.

> Makes sense, but why would they similarly mangle the exponent as well?
> As Alexander Cherepanov wrote, if I understand him correctly, there's
> 100% overlap between keys with such moduli and with such exponents.

Presently I do not know why the perpetrator found it necessary to mangle
the exponent.

> As I understand it, the description at evil32.com in particular is about
> generating valid (and not necessarily weak) keypairs that would happen
> to have the intended 32-bit key id.  This is more computationally
> intensive than the "mirroring", but it is fast enough, is an
> older-known(?) and more obvious attack, and it doesn't expose the
> encrypted data to other/unintended attackers (OK, the "evil guys" might
> not care either way).  So it is a little bit surprising (but just a
> little) that someone would go for the "mirroring" instead.
>
> Alexander

I haven't any notion of why this particular mutilation was chosen.
But the particular list of victims is sufficient to rule out 'software bug'
in my mind as an intellectually-honest explanation.


Yours,
- -S

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

iQEcBAEBCgAGBQJXKz47AAoJELmCKKABq//HLToH/Re+2x5wXZp/RpJBP4Ca5juU
OeXzto0GIVYgC4bO+IWchpyBM9I2O5SAZvv1+oDyCs/H3dZV/SG5uCTEow/Xtseu
rMbfBrObxZSQiysfR9c3/xlLdpaY/Djj43TpSmzIJZhUDVf1CPO8PSOLiQEAVctQ
omysFkfHHpT/FWBtGOq7Ew3xA9Jj4qcQVgST+4cKXuNfpMQCd6+6wJoQGvn8WInJ
b0Ut5V0v88DzsvSlRe4BxHvZxi/0zHr4L/7sLeSdJ6z2WOG3tEKS7Fpe5qh5PVXc
Jkd/+K//ShVOMd8yw3Ha45/3F5LFVO6sN0WM50qQAUoTguQA6GCiiFtP9pORKgU=
=tFtl
-----END PGP SIGNATURE-----