Re: broken RSA keys

[Alexander Cherepanov <ch3root () openwall com>]

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