RE: [Cfrg] Crypto results on digest algs

["Whyte, William" <WWhyte at ntru.com>]

Hi Jon,

> For any given key K, you have to find a collision where the 
> colliding bit string forms two legal MPIs that form a valid RSA key. 
> You get to divide the bit string where convenient, but it can't be just 
> any bit string. I believe that this is significantly harder than simply 
> finding a collision on the preimage K.

A few comments on this.

First, I'm not sure I fully understand Russ's attack. It seems
to be:
a) Alice distributes key a;
b) Something bad happens;
c) Alice says "key a was never my key -- it was key b"
... in other words, it's a repudiation attack. But the two keys
only collide in their fingerprints; they still, for example, 
generate different signatures, so they can be distinguished 
that way. Also, if Alice has already used key a multiple times,
it seems that she's established ownership of it in a way that's
hard to repudiate based on a fingerprint collision.

Second, consider this attack:
a) Mallory finds a collision with Alice's key;
b) Mallory gets his key installed over Alice's key on Bob's
   machine;
c) Mallory man-in-the-middles and reads Alice's mail.

Now, Mallory needs not just to find a collision on the 
public key, but also to know the private key corresponding 
to the colliding bit string. If the public key has to
be valid, as in it has to be the product of two primes,
then Mallory has to be able to factor. This would considerably
impede the attack. However, AFAIK PGP doesn't check that v3 
keys have any particular mathematical properties, so Mallory 
could in theory try to find a colliding string corresponding 
to a public key with exponent 1, in which case this attack 
becomes more realistic.

Third, and directly addressing Jon's point above: Suppose 
that v3 keys must be valid (as in, the product of two primes), 
and that the attacker doesn't need to know the private key 
corresponding to the colliding public key. Then the attacker's 
chances of finding a valid colliding string aren't too bad. 
The chance that any m-bit integer is a prime is about 1/m, 
so the chance that any 2m-bit integer is a product of two 
m-bit primes is about 1/m^2. So if m is 512, it should take 
about 250,000 attempts (2^18) before you get a valid RSA 
modulus.

Fourth: I suspect none of this is really relevant anyway.
The discussion seems to be based on the assumption that
the algorithm works like this:

  Input:  I, a string
  Output: C, a colliding string.

In fact, my understanding is that it works more like this:

  Input:  I, a string
  Output: C1, C2, two colliding strings which are similar 
          to each other and to I.

So with current attacks, attackers can produce collisions,
but they can't produce second preimages. In other words, an
attack on PGP based on this collision-finding approach starts
from two public keys; it doesn't start from a target public
key that I want to ofind a collision with. That changes the
potential attacks considerably, and so I don't see that this MD5
collision enables any attacks that require at least one valid 
public and private keypair.

Any comments?

Cheers,

William

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg