SHA1 collision found

[Daniel Kahn Gillmor]

On Sat 2017-02-25 09:09:20 -0500, MFPA wrote:
> On Friday 24 February 2017 at 3:15:23 PM, in <mid:20170224151523.B27CFE05F7 at smtp.hushmail.com>, vedaal at nym.hush.com wrote:-
>
>> Even for v3 keys, which were not SHA1 hashed, the only way to
>> generate a new key with the same fingerprint, would be to allow the
>> key size to vary (usually to a bizarre key size that would be quite
>> suspect, and not believed).
>
> Is that why the majority of keys are exactly 1024, 2048, etc. bits, or 
> is there a technical reason?

I think the reason that a majority of keys have "round" key sizes is
habit, and that the tools make it easy to generate them that way.

The size variation that vedaal describes is due to the definition of the
v3 fingerprint:

 https://tools.ietf.org/html/rfc2440#section-11.2

   The fingerprint of a V3 key is formed by hashing the body (but not
   the two-octet length) of the MPIs that form the key material (public
   modulus n, followed by exponent e) with MD5.

As a toy example, consider the case where p = 0x1411304f and q =
0x141120c5, so n = 0x0192af7bf8830ccb and e = 0x010001

These MPIs are stored in full octets, so the material hashed for the v3
fingerprint is (in hex)

    01 92 af 7b f8 83 0c cb 01 00 01
   |--------- n -----------|-- e ---|

if i want to find a key with the same v3 fingerprint, i just need to
vary the boundary between the two, for example like this:

    01 92 af 7b f8 83 0c cb 01 00 01
   |--------- n --------|---- e ----|

the bytestring hashed (and therefore the fingerprint) is exactly the
same as before, but n is 8 bits shorter, and e is 8 bits longer.

now, it's probably obvious to anyone who bothers to inspect the public
key that this is not a good key -- at the very least, n is clearly not
the product of two primes ;) But RSA will still work with it.  If the
goal is to produce a key with the same fingerprint, it's trivial to do.

This is one of the reasons why the modern GnuPG suite no longer supports
these archaic keys.  it's simply not a reasonable or safe-to-use format.

The OpenPGPv4 fingerprint includes explicit sizes of the components in
the material hashed, so it doesn't have this problem.

      --dkg
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 832 bytes
Desc: not available
URL: </pipermail/attachments/20170225/f4c6216c/attachment.sig>