Subject: Re: Czech attack to PGP

From: [email-masked]
Date: Thu, 22 Mar 2001 10:51:30 -0800

[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

---

From: Florian Weimer <[email-masked]>
Date: 22 Mar 2001 20:38:41 +0100

[email-masked] writes:

> Do we need to define a new packet format, V5 for keys?

A V5 key format could address the protocol error with key expiration,
too.

> 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?

Hmm.  What about introducing a new secret key packet with a hash
instead of a checksum? This approach seems to be much cleaner, and it
doesn't cause surprising problems for the end user.

-- 
Florian Weimer 	                  [email-masked]
University of Stuttgart           http://cert.uni-stuttgart.de/
RUS-CERT                          +49-711-685-5973/fax +49-711-685-5898

---

From: [email-masked] (Lutz Donnerhacke)
Date: 22 Mar 2001 19:49:47 GMT

>http://theory.stanford.edu/~dabo/papers/faults.ps.gz.

Yep. Thanks for the link. 'Bellcore attack' is the name in the German
smartcard hacking scene.

>last value in the secret key, "u", which is the inverse of p mod q.

Posted this yesterday: Yep possible, even to change the checksum.

>log of r, and from this they can calculate the user's secret key.

Great idea.

>with the public key values.  In particular the last check prevents the

It makes sure, that is consistent in itself, but it does not say anything
about a prevented attack: Assume an attack able to modifiy the parameter q
to be equal 1. If have to sleep about this.

>since it involves exponentiations.

They do not address probability attacks to errors in the MPI calculus. (Wait
for a bellcore scenario ... most customer PCs run far from there
specifications, so we have a real smartcard analogon). Thats why PGP263(i)n
does check against any miscalculations.

>  - Use PSS padding from PKCS-1 v 2.1 rather than the v 1.5 padding

I'd like to add: Throw away the bit gambling. Redesign from scratch.

>and could still leave vulnerabilities.

Yep. This would be a HMAC.

>help.  It would still be possible to disrupt the CRC calculation.

We could prevent algebraic attacks by applying the P.1363 recommendation.

>private keys, I don't think making changes is an urgent matter.

Ack. We should stress that private key files should not reside on shared
media and that OpenPGP ist a transport message format, not a local storage
recommendation. Implementations are free to choose anything else.

>vs a 2-byte checksum to recognize which one is being used?

No more bit gamblings! Use v5 for secret keys. A public part to index and a
whole encrypted and hashed private part including the whole pulic key data
again.

>fast performance, plus have security against tampered private key files.

I'm feeling bad.

---

From: John W Noerenberg II <[email-masked]>
Date: Thu, 22 Mar 2001 14:16:04 -0600

>recommendation. Implementations are free to choose anything else.

Yes, definitely, Lutz.  This has been mentioned in a number of 
different messages, but this is probably the single most important 
point, and worth singling it out.  Transferring secret key files 
makes them vulnerable to attack.  Vlastimil and Rosa have shown a 
particular way to attack them.

best,

-- 

john noerenberg
[email-masked]
   --------------------------------------------------------------------------
   Peace of mind isn't at all superficial, really.  It's the whole thing.
   That which produces it is good maintenance; that which disturbs it
   is poor maintenance.
   -- Zen and the Art of Motorcycle Maintenance, Robert M. Pirsig, 1974
   --------------------------------------------------------------------------

---

From: Werner Koch <[email-masked]>
Date: Sat, 24 Mar 2001 14:51:18 +0100

> Do we need to define a new packet format, V5 for keys?  Or could we keep

No need for a new format - doing such changes for OpenPGP right now
will delay getting to draft even more.

There is a far easier way to do this and we can do this first in our
implementations and use the old format for transferring secret keys
(which is a Bad Thing doing it at all or over an insecure channel):

We introcude a new S2K mode and encrypt this:

 1. fingerprint of the public key
 2. the secret MPIs
 3. A SHA-1 hash over 1 and 2.
 
This closly resembles the MDC encryption we are now using. The
fingerprint also comes handy to store these secret parts on hardware
tokens and migh be a good idea anyway for an internal secret key
storage format.  If there are concerns about known plaintext we
could leave the fingerprint out of the encryption so that we hash
1+2 and encrypt 2+3.

GnuPG can already use an extension to the secret key protection,
which is used to allow for a primary key without secret key but
workable secret subkeys (nice on a automated system):

| S2K mode 101 is used to identify these extensions.
| After the hash algorithm the 3 bytes "GNU" are used to make
| clear that these are extensions for GNU, the next bytes gives the
| GNU protection mode - 1000.  Defined modes are:
|   1001 - do not store the secret part at all
 
So either each implementation uses it's own scheme or we agree
informally on one in the (not officially reserved) private range of
S2K mode.

I agree with Hal that there is no urgent need to do something.  This
might backfire on repudation of the OpenPGP specs.

Ciao,

  Werner

-- 
Werner Koch        Omnis enim res, quae dando non deficit, dum habetur
g10 Code           et non datur, nondum habetur, quomodo habenda est.
Privacy Solutions                                        -- Augustinus