[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <572B3DA1.6030608@openwall.com>
Date: Thu, 5 May 2016 15:33:37 +0300
From: Alexander Cherepanov <ch3root@...nwall.com>
To: oss-security@...ts.openwall.com
Subject: Re: broken RSA keys
On 2016-05-05 11:17, 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.
>
> I made the mistake yesterday of looking at hex representations of the
> posted shared factors without first looking at hex representations of
> the moduli. Now that I just did, I see that the example modulus I
> posted does follow the pattern mentioned above, and which Stanislav
> mentioned below.
All modulus from Phuctor that are divisible by 2**32+1 indeed have the
form {an an ... a1 a1 a0 a0}. The following script would print moduli
that don't have this form but it prints nothing. The script:
perl -Mbigint -ln0e '
while (m{RSA Modulus .N.:.*?<td>(\d+)<.*?<td>(\d+)<}sg) { # extract
numbers
if ($1 % (2**32 + 1) == 0) { # is modulus a multiple of
2**32 + 1
$m = ($1+0)->as_hex; # modulus as hex
$m =~ s/^0x//; # remove hex prefix
$m = '0' x (-length($m) % 8) . $m; # pad up to multiple of 8 digits
if ($m !~ /^(([0-9a-f]{8})\2)+$/) { # check
print $m
}
}
}
' phuctored
While at it, let's see which exponents we get after dividing by 2**32+1
(from those that are divisible):
$ perl -Mbigint -ln0e 'while (m{RSA Modulus
.N.:.*?<td>(\d+)<.*?<td>(\d+)<}sg) { print $2 / (2**32 + 1) if $2 %
(2**32 + 1) == 0 }' phuctored | sort | uniq -c
2 17
7 41
143 65537
>> 4) One parsimonious explanation for (1) given (2) and (3) is that the
>> 'mirrored' keys were generated by a malicious actor,
>
> 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.
That's right. My original one-liner ended with "grep -c '^0 0$'" which
counts cases where both remainders are 0. If you change it to "grep -c
'^0 '" it will count cases where modulus is divisible by 2**32+1.
Similarly, "grep -c ' 0$'" will count exponents. Results from all three
commands are the same (152).
--
Alexander Cherepanov
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.
