Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 5 May 2016 08:36:29 -0400
From: Stanislav Datskovskiy <>
Subject: Re: broken RSA keys

Hash: SHA512

On Thu, May 5, 2016 at 4:17 AM, Solar Designer <> 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 ( 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 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.

- -S

Version: GnuPG v1.4.10 (GNU/Linux)


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.