
MessageID: <572B3DA1.6030608@openwall.com> Date: Thu, 5 May 2016 15:33:37 +0300 From: Alexander Cherepanov <ch3root@...nwall.com> To: osssecurity@...ts.openwall.com Subject: Re: broken RSA keys On 20160505 11:17, Solar Designer wrote: > When a modulus is (mangled?) such that each of its 64bit limbs consists > of two matching 32bit 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 32bit 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 32bit limb patterns in the GCDs. As Alexander Cherepanov > correctly pointed out, even the seemingly slightly more complex 32bit > 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 !~ /^(([09af]{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 oneliner 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.