[I sent this an hour ago but it has not appeared so I'm trying again...]
Links to English language versions of their paper and PowerPoint slides
are at http://www.i.cz/en/.
There are really two different attacks, one for RSA and one for DSA.
Both require modifying your secret key file. Of course, for most users
this is not an issue. Any attacker who could get to their secret key
file and modify it would also be able to modify their PGP executable or
public key file and weaken the program in any number of ways. So the
practical impact of this attack is very low.
However it is very interesting theoretically. Even though the attack
is relatively easy to see once the idea is raised (several people had
reconstructed the attack just from the press release in the last few
days), it is a new idea and may be applicable to other systems than
OpenPGP.
The RSA attack is the one Lutz called a "Bellcore" attack, based on the
Eurocrypt 97 paper by Boneh et al at
http://theory.stanford.edu/~dabo/papers/faults.ps.gz.
One of the attacks in this paper is against RSA done using the Chinese
Remainder Theorem. (The authors of the Czech paper attributed the idea
to Arjen Lenstra.) This optimization of RSA signature involves doing
the calculation twice, mod p and mod q, and then combining the result.
Boneh/Lenstra showed that if you could disrupt one side of this
calculation, the resulting signature would leak the key.
His group was looking at hardware faults, but the Czech group accomplishes
the same thing by perturbing some of the RSA secret parameters so that
one side of the signature is done wrong. Specifically they change the
last value in the secret key, "u", which is the inverse of p mod q.
This disrupts the part of the CRT calculation which is mod q while
leaving the mod p alone, satisfying the requirement for the Boneh attack.
A simple subtraction and GCD will recover p from the result.
The DSA attack is quite different. In this case they change the
public parameters of the DSA key to weaken it but leave the private
part alone. They change p and g to be a group where discrete logs are
easy, one where (p-1) has only small factors. Then when the signature
is calculated, they can find the secret k value by taking the discrete
log of r, and from this they can calculate the user's secret key.
The commercial version of PGP, and possibly others, does extra checks on
RSA private keys which prevent the RSA attack from working. Specifically,
whenever it decrypts RSA private key data, it does the following checks:
n = p*q
d*e mod p = 1
d*e mod q = 1
p*u mod q = 1
This validates all of the private key data and makes sure it is consistent
with the public key values. In particular the last check prevents the
Czech attack from working as a change to u will make this one fail.
Note that these checks are quite fast, just a few multiplies and
divides, so they do not slow down the signature calculation by much,
since it involves exponentiations. Unfortunately such fast checks are
not possible for DSA keys. To validate the parameters two exponentiations
are necessary, while only one exponentiation is used in a DSA signature.
Doing validations will therefore slow down DSA signing by a factor
of three.
The authors of the paper make several recommendations for changes to OpenPGP
to address these kinds of attacks. They are:
- Use CBC mode rather than CFB to encrypt private key components
- Use an HMAC to protect public and private key data
- Use PSS padding from PKCS-1 v 2.1 rather than the v 1.5 padding
The idea behind using CBC mode is that you can perturb the last block
of data encrypted in CFB in a predictable way; you can XOR any desired
bit pattern into it. They use this to attack RSA V4 keys. However,
CBC mode allows similar perturbations, but to the first block rather
than the last block. So this fix does not go to the heart of the problem
and could still leave vulnerabilities.
The last idea, to use PSS padding, also does not seem to fundamentally
help. It would still be possible to disrupt the CRC calculation.
The best idea seems to be to replace the current checksum with an HMAC.
This would cover both the private and public components; it would be keyed
based on the passphrase. Then it would be impossible for an attacker
to alter private key data undetectably unless they knew the passphrase.
Broadly speaking, because the attack requires write access to users'
private keys, I don't think making changes is an urgent matter.
Users need to be careful to protect their private key files in any case.
For most users, if attackers can get at these files they could cause
many other sorts of problems.
However we may want to begin discussing a change to using HMAC in place of
checksum. We need to agree on exactly what data is covered by the HMAC,
and how the key for the HMAC is calculated from the passphrase (generally
it is a good idea for MAC keys to be different from decryption keys).
Do we need to define a new packet format, V5 for keys? Or could we keep
the old format number and use the length difference of a 20-byte HMAC
vs a 2-byte checksum to recognize which one is being used?
If we do add an HMAC, software could then work in a mode where old-format
keys get the extra checks applied to carefully validate them, then
get rewritten using the HMAC. From then on the extra checks are not
necessary and the HMAC alone will detect changes. So we will retain
fast performance, plus have security against tampered private key files.
Hal Finney