[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 5 May 2016 08:36:29 -0400
From: Stanislav Datskovskiy <stas@...er-os.org>
To: oss-security@...ts.openwall.com
Subject: Re: broken RSA keys
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512
On Thu, May 5, 2016 at 4:17 AM, Solar Designer <solar@...nwall.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-----
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.
