Subject: Bellcore Attack

From: [email-masked] (Lutz Donnerhacke)
Date: 21 Mar 2001 10:59:16 GMT

According to the current Comp.Risks Digest, a Bellcore attack seems possible
due to the OpenPGP secret key format.

---

From: Jon Callas <[email-masked]>
Date: Wed, 21 Mar 2001 16:51:25 -0800

You can see the press release at <http://www.i.cz/en/onas/tisk4.html>.
There are also things in Czech on their web site. Supposedly, the details
will be published tomorrow.

The gist, as much as we know of it now is that they claim that they can
write into a V3 secret key (the PGP 2.6 format) in such a way as to force
you to make signatures that the attacker can then forge. We don't know the
details yet. They only want to talk to reporters, not to technical people.
All the details I have are ones I wheedled out of reporters. I sent mail to
the contact on the press release yesterday who said that we have to wait
like everyone else. Some mail today going directly to the cryptographers
involved got a reply that said they'll publish tomorrow. So we'll see.

	Jon

---

From: Rodney Thayer <[email-masked]>
Date: Wed, 21 Mar 2001 17:55:33 -0600

what is the reference to calling this a "Bellcore attack"?

---

From: Jim Gillogly <[email-masked]>
Date: Wed, 21 Mar 2001 18:23:55 -0800

> what is the reference to calling this a "Bellcore attack"?

"On the importance of Checking Cryptographic Protocols for Faults"
  Dan Boneh, Richard A. DeMillo, Richard J. Lipton, Bellcore 1997.

See http://citeseer.nj.nec.com/correct/21216, for example.
They break RSA using one bogus signature and the Chinese
Remainder Theorem.  This was the inspiration for the whole
field of differential fault analysis.

-- 
	Jim Gillogly
	Highday, 30 Rethe S.R. 2001, 02:18
	12.19.8.1.5, 12 Chicchan 8 Cumku, Seventh Lord of Night

---

From: John W Noerenberg II <[email-masked]>
Date: Wed, 21 Mar 2001 21:58:32 -0600

>due to the OpenPGP secret key format.

Yes, Lutz.  There has been a fair amount of discussion here in 
Minneapolis regarding the discovery by the Czech researchers.  I'll 
leave the detailed analysis to others to publish, but at this point 
it appears this attack does not appear to pose a significant threat 
to the integrity of information encrypted with PGP.

-- 

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: [email-masked] (Lutz Donnerhacke)
Date: 22 Mar 2001 07:58:11 GMT

>what is the reference to calling this a "Bellcore attack"?

I did. There was no reference, but only the Bellcore attack or a substantial
new type of attack seems a valid assumption to me.

---

From: [email-masked] (Lutz Donnerhacke)
Date: 22 Mar 2001 08:03:18 GMT

>you to make signatures that the attacker can then forge. We don't know the

That seems resonable: Modifying the least significant in the last crypted
secret key component can be used (in conjunction with the chipher feedback
mode) to determine the necessary checksum fooling PGP integrity checks. It
might be possible to extend this to v4 keys too.

---

From: Lutz Donnerhacke <[email-masked]>
Date: Thu, 22 Mar 2001 16:55:00 +0100

> >  PGP2.6.3(i)n is fixed against all those types of attacks (and I had
> >a look on buffer overflows).

> you should mention that on the ietf open pgp list.

I posted the announcement some minutes ago to the usenet.
OK. CC: ML

ftp://ftp.iks-jena.de/mitarb/lutz/crypt/software/pgp/pgp263in/

---

From: Florian Weimer <[email-masked]>
Date: 22 Mar 2001 18:58:18 +0100

> ftp://ftp.iks-jena.de/mitarb/lutz/crypt/software/pgp/pgp263in/

I've just decided that I won't implement a similar check for the DSA
case (actually, I've implemented it already, but I won't recommend its
use).  The situation is much too murky.  Maybe a relative proof of
security can be obtained, but I very much doubt it.  (Peter Gutmann
told me about a different attack against unprotected DSA parameters,
the whole situation doesn't look very promising at all.) IMHO, the
problem can only be addressed in a safe way if the format is changed.
Implementations can already do this on their own, of course, but
there's still the problem that the standard is really misleading in
this area.

Unfortunately, this is not the first problem due to the attempt to
minimize the amount of data which is cryptographically protected, a
rather questionable design goal.  It's not hard to spot the pattern in
the list of past problems with OpenPGP and OpenPGP-derived
protocols. :-(

BTW: With RSA keys, GnuPG is not as reliable as it could be (it
doesn't check the computed signatures and performs only a simple
consistency check), but it's not vulnerable to the described attack.
The situation is much better with RSA keys anyway because the secret
key packet contains all necessary information in the encrypted area.
I whish it were true for DSA as well. :-/

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