On 28 Dec 2005, at 3:23 PM, Daniel A. Nagy wrote:
Hi,
I think, I should explain the Klima-Rosa attack, because the
original paper
is a bit difficult to understand.
It is slightly different for RSA and DSA keys, but the main idea is
the
same. In both cases, the private material is an exponent and the
public
material has the modulus of an exponentiation, the result of which
is part
of the signature. The base of the exponentiation is different for
RSA and
DSA (and ElGamal), but it is known in all cases.
Let's stick to the ElGamal example, for the sake of clarity (and
because it
isn't covered elsewhere). The signature contains g^k mod p (k is a
random
number), so if the attacker corrupts p and g such that discrete
logarithms
mod p are easy to solve, he can work back k and from there, the
secret x.
The point is that the secret material is revealed by using it in a
modified
context.
Now, this attack can be thwarted by a lot of sanity checks on the
private
key (e.g. checking that the private part indeed corresponds to the
public
part), before outputting the signature, as is done by GPG, but it
might be
expensive for less powerful computers/smartcards. If the public-
private
binding were provided by the hash-based MDC, it would be a lot
cheaper.
Stuff to read:
http://eprint.iacr.org/2002/076 (original paper)
http://www.orlingrabbe.com/DSAflaw_OpenPGP.htm (explaination and
exploit code)
Okay, so there isn't anything new here. We fixed this years ago.
Jon