In <slrn64oq3v(_dot_)m0(_dot_)lutz(_at_)taranis(_dot_)iks-jena(_dot_)de>, on
10/21/97
at 08, lutz(_at_)taranis(_dot_)iks-jena(_dot_)de (Lutz Donnerhacke) said:
I do not know how to deal with key ID attacks, birthday phenomena,
and user provided parts of the key/user ID without defining the
key ID as not unique.
I strongly agree - especially if we provide support for short keyIDs
as well as the long ones.
At 04:38 AM 10/21/1997 -0500, William H. Geiger III wrote:
Well the way I see it we have 2 possIbilities for duplicate keyID's:
1) Collision. Does anyone know what the probability of 2 users generating
2 unique keys with the same keyID? If this number is high then perhaps we
should look at either using the fingerprint in the PGP packets or
providing additional info in the packets to provide uniqueness.
The number of keys required to probably have a birthday collision is about
sqrt(2**keysize) - thus 32-bit keyids will generate a collision
by about 2**16 keys (and in fact there was at least one real collision.)
64-bit KeyIDs will generate a collision by around 4 billion keys,
which is small enough that any application generating lots of public keys
for some reason will risk the problem, especially if the keys
end up in public or on some persistent server rather than being
used once and discarded. 128-bit keyids would be fine.
2) DEliberate Attack. We know of the common attacks aginst the keyID &
Fingerprint with the PGP 2.6.x keys. Are the DSS/DH keys also open to such
attacks? Is it realy wise to allow these keys to be added to the keyring
in the first place or should the user when confronted with duplicate
keyID's be required to take futher action?
There are at least two deliberate attacks.
The less useful one requires the Bad Guy to generate two keys with
identical KeyIDs and find some workable scam that uses them.
It's a birthday attack again, so you need >>64-bit KeyIDs to prevent it.
In particular, if the recipient is a program rather than a human,
will it do something useful while waiting for some human
to come over and click an "Accept/Reject" box on some GUI?
Or will it fail in some ugly fashion?
The other attack is the 0xdeadbeef attack, which is probably easier
with DSA than with RSA, since you don't need to find lots of primes.
A DSA signature uses a long prime p, a 160-bit prime q, and a
generator g, all public and optionally shared, and a private key x<q
and public key g**x mod p. So you can take your target's p,q,g,
and start generating x, g**x mod p, at a cost of one modmult each.
(An easy approach is to let x = 1, 2, 3, ...., which just requires
multiplying by g each time. If you find a value of g**x mod p
that's small relative to p, you can probably go much faster by
multiplying by this instead of g, since you can shortcut around the
mod p fairly often, though I don't know if this really saves you much
in practice when you're trying a few billion keys.
It's probably more important just to find a short multiplier to
reduce the multiplication work.)
I may be wide off on this one but it just seems to be a bad design
approach to allow non-unique identifIers in the PGP packets and then try
every key that matches it.
It's an inherent problem with using KeyIDs.
The only way to prevent the problem is to use identifiers long enough
that you can't deliberately or accidentally generate a collision,
which is almost the same as just using the fingerprint or key as KeyID;
the alternative is to do the right thing with collisions if they occur.
Defining "the right thing" is hard, so it's important to avoid building
formats and GUIs that only show the user the KeyID.
Thanks! Bill
Bill Stewart, stewarts(_at_)ix(_dot_)netcom(_dot_)com
Regular Key PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
[I'm currently having hardware problems with my main email;
send Cc: billstewart(_at_)att(_dot_)com if you need to reach me in a hurry.]