Subject: A review of hash function brittleness in OpenPGP

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 08 Jan 2009 13:59:45 -0500

Hey folks--

I've been trying to evaluate RFC 4880's resistance to a hash function
compromise in light of the recent activity exploiting weaknesses MD-5 in
That Other PKI [0].

I'm quite pleased with the bulk of what i've found.  OpenPGP's use of
message digests is almost entirely parameterized, leaving the door open
to forward-looking adoption of new hash algorithms and the smooth
deprecation as older ones are demonstrated to be weak.

So I've been looking for places in the spec where the choice of digest
function is not parameterized.  In particular, explicit and hardcoded
reliance on SHA-1 could become problematic as it is already being
deprecated.  For example, reliance on SHA-1 must be eliminated in all US
Gov't federal agencies by the end of 2010 [1].

Here are the concerns i've found so far:

MDC
---

The modification detection packets (sections 5.13 and 5.14) explicitly
specify SHA-1, and basically acknowledge that this choice may need to be
made more flexible in the future.

Fingerprints
------------

Fingerprints (section 12.2) are specified as an SHA-1 computation.
While this isn't an explicit reliance on SHA-1 for cryptographic
security (and the RFC makes it clear that there is a non-zero chance of
fingerprint collisions), the real-world use of fingerprints as unique
identifiers for keys poses a serious risk to OpenPGP infrastructure
should SHA-1 become further compromised.

Revocation keys
---------------

Section 5.2.3.15 defines a way that key A can allow key B to
authoritatively issue revocation signatures on A's behalf, including key
 revocation (sigtype 0x20), subkey revocation (sigtype 0x28), and
certification revocation (sigtype 0x30).  However, this mechanism relies
on the fingerprint of B being unique.  Since the fingerprint itself is
bound to SHA-1, this presents a risk to users of this feature of the
specification should SHA-1 become further compromised.

As the IETF working group for OpenPGP, we probably should start actively
working to resolve these issues so we can have infrastructure in place
well before SHA-1 is similarly compromised.  Any suggestions?  I'm new
to the WG, so i don't have any experience addressing concerns like this.

I'm particularly concerned about fingerprints, since they is used widely
in the real world (e.g. i have my fingerprint on my business card).  I
can imagine relatively straightforward technical measures to resolve the
other concerns.

Also, it's quite likely that i've missed things in my reading of the
spec.  If anyone sees any other problematic areas, it would be great to
air them as soon as possible.

Regards,

	--dkg

[0] http://www.phreedom.org/research/rogue-ca/
[1] http://csrc.nist.gov/groups/ST/hash/statement.html

---

From: tz <[email-masked]>
Date: Thu, 8 Jan 2009 16:34:25 -0600

The other exploit was also complex and required finding collisions
which was not trivial but possible with MD5.  The key seemed to be
that the separate bits of the certificate were in places which made
the exploit easy, e.g. the top half was either static or predictable,
but there was a comment field (which could be stuffed with the bits to
generate the collision), then the big prime product.

To analyze the RFC, the internal structure of the key certificates
which are signed need to be analyzed (first there has to be a current
source for new things with MD5 anyway, I'd have to come up with two
things to be signed, a real one which will be signed and the rogue one
that has the same MD5 hash).  I think the simplicity of the
certificates might make it more difficult, but that is where I would
look.

I don't think there are many such things in place, but I would look if
there are any legacy signers (including prominent people with older
keys or implementations).  I think after PGP5 it would be very
unlikely, but I would look for something that allowed, requested, or
forced "backward compatibility", i.e. if there are bits or something
else I can cause the hash algorithm to be MD5.

---

From: "Daniel A. Nagy" <[email-masked]>
Date: Fri, 09 Jan 2009 00:04:35 +0100

Hi,

First off, thank you for such a swift reaction to one of the most serious
cryptographic vulnerabilities discovered in recent times. Let me just comment on
 your comments.

> made more flexible in the future.

We should be very careful here. By being more flexible on MDCs, one makes the
system less secure. After all, it is sufficient to forge ONE of the valid MDC
functions for the MDC-protected packet to check. There is a reason (with a good
discussion in the archives of this list, if I am not mistaken) why there is no
algorithm agility in OpenPGP MDC.

Also, MDC needs to be secure against second pre-images, not against collisions.
Collision-resistance is not a requirement for MDCs.

> Fingerprints

There are many more problems with current OpenPGP key IDs and fingerprints. I
think that these are in need of a major overhaul. Here are two other problems
with fingerprints and keyIDs:

Creation date is hashed in the fingerprint, thereby allowing the same key with
different fingerprints of which 31 bits are of the attacker's choosing,
effectively shaving off 31 bits off the attacker's task (in other words, making
it 2 billion times easier on average).

Also, fingerprints and key IDs are hexadecimal, which makes them
super-inconvenient with mobile phones with numeric keypads.

> Revocation keys

Again, collisions don't seem to be a problem here.

> can imagine relatively straightforward technical measures to resolve the

I think, fingerprints should be dealt with as part of the shift to v5 keys.
However, formulating reasonable requirements for fingerprints sounds like a good
way to kick off the design process of v5 key format specification. I will write
up a few ideas soon.

Regards,

-- 
Daniel

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 08 Jan 2009 18:20:33 -0500

On 01/08/2009 05:34 PM, tz wrote:
> that has the same MD5 hash).  

I suppose i should have been more explicit: i'm not concerned about this
specific attack working against OpenPGP.  It just got me to thinking
about various ways that an abused hash function could cause a PKI
failure, and how the community around that PKI could respond to such an
attack.

The X.509 community was able to respond by further deprecating MD5
because there was a parameterized method in place to switch to another
hash function.  OpenPGP currently has this in place almost everywhere a
hash function is used.  That's good!

However, there are a few places where we don't have that agility, which
is what i was trying to highlight.  Actually doing the switch from one
hash algorithm to another within a well-defined parameterized structure
is a chore, but it's doable.  My concern is that there are places in
OpenPGP (fingerprints being the most worrisome place) where we would be
unable to actually make such a transition should there be a
cryptographic result rendering that hash function unusable.

> else I can cause the hash algorithm to be MD5.

Doing a test of common implementations of OpenPGP to see if they give
adequate warnings based on use of deprecated algorithms would be good,
though this was not intended to be the point of my initial message.  For
example, the following series of commands generates warnings on
signature creation, but not on signature verification, afaict:

  echo test > test
  gpg --digest-algo MD5 --clearsign test
  gpg --verify test.asc

Is this the desired behavior?  Or should there be a warning during
verification that the signature was based on a deprecated hash?  What
about during certification verification or web of trust calculations?
How do other implementations approach this scenario?

	--dkg

---

From: "Daniel A. Nagy" <[email-masked]>
Date: Fri, 09 Jan 2009 01:03:48 +0100

> hash function is used.  That's good!

As far as I can judge, X.509 PKI is still in the state of catastrophic failure
with no obvious way out.

Right now, if my browser (or yours, or anybody else's) tells me that the site I
am browsing presented a certificate issued to it by a legitimate CA, I cannot be
sure that this assertion is true. Rejecting all certificates with MD5 in their
signatures is not a solution (there are too many out there and replacing them
requires non-trivial cooperation between different parties; no-one can do it
acting alone). Not issuing any more MD5-based certificates is not a solution
(who knows how many rogue CAs are already out there?). In fact, I do not see an
easy and cheap solution out of this mess.

It is a good thought-experiment to assess the consequences of an existential
collision attack on SHA1 such as the one we have for MD5 on OpenPGP security,
considering all the places where SHA1 is wired in. I haven't checked every
corner of RFC4880, but I can see no catastrophic failure akin to what happened
to X.509 PKI.

-- 
Daniel

---

From: Jon Callas <[email-masked]>
Date: Fri, 9 Jan 2009 15:28:03 -0800

On Jan 8, 2009, at 10:59 AM, Daniel Kahn Gillmor wrote:

> * PGP Signed by an unknown key
>
> Hey folks--
>

Great comments.

> made more flexible in the future.

Yes.

Let me add an historic note. The MDC occupies an odd position.

There is an obvious, easy, supported way to create an integrity- 
protected message: you sign it.

The problem is that an unsigned message is pretty vulnerable to many  
problems from cut-and-paste attacks on. A number of people wanted to  
do something about that problem -- you want an unsigned message that  
has a reasonable guarantee that it arrived whole.

Most people didn't see the threat. Outside this working group, almost  
no one did. Even inside the working group we were ambivalent about it.

The solution as you see it was a compromise among us, and as a  
compromise it means we're all a bit ambivalent about it. In  
retrospect, an MAC would have been a better solution, but brought up a  
new set of issues like what key to use.

HMACs were developed *during* the MDC discussions, and the proof of  
security for HMAC was done *after* we all agreed. The implementors  
didn't want to do an HMAC for performance reasons, especially for  
streaming, and again -- there was no proof of security. HMAC was this  
new thing that Hugo and Shai did. Since then, there are also obvious  
answers for KDFs as well.

Despite this, it's a fine construction. It does what it was intended  
to do, and the known weaknesses of SHA-1 do not affect it at all. We  
are not relying on collision-resistance, we are relying on one- 
wayness. Remember, this is an *unauthenticated*, but whole message. If  
you want to authenticate the message, we have some nice digital  
signatures to offer you.

Since then, there have been several attacks against the OpenPGP  
formats that are thwarted by the MDC. If we want to upgrade the MDC,  
we know how to do it, that's outlined in 4880.

(Let me put on my hash-designer's hat for a moment. In Skein, we  
created a one-pass MAC construction that can replace HMAC. It also has  
a proof of security. I think it would be best to wait a while longer  
to see what comes out of the SHA3 competition, because it's likely  
that it will yield KDFs and hash-based MACs that answer all of the  
concerns that lead us to the present MDC compromise. They'll be fast,  
easy, and one-pass.)

> Fingerprints

There's a proposal for a new way to do fingerprints. I will do it the  
injustice of summarizing it:

You express a fingerprint as the algorithm number, a colon, and then  
the hexadecimal. Truncations are handled in some obvious manner.  
Presently, for better or worse, a key id is the low-order 64 bits of a  
fingerprint, so we probably have to stick with that, despite the  
gnashing of teeth many of us will have.

Under that proposal, one of my fingerprints (DFA7 517E 2BF4 6834 6C15   
C029 B137 9D59 9383 DE06) could also be expressed as (2:DFA7 517E 2BF4  
6834 6C15  C029 B137 9D59 9383 DE06) because SHA-1 has the algorithm  
number of 2.

All we need is someone to write this up as an I-D -- or code it up  
preemptively.

> Revocation keys

Solved by upgrading fingerprints and three more paragraphs of text.

> air them as soon as possible.

Are you volunteering to write a document?

> * Unknown Key
> * 0xD21739E9

---

From: Ben Laurie <[email-masked]>
Date: Sat, 10 Jan 2009 00:16:23 +0000

Jon Callas wrote:
> a proof of security.

I wish people would stop saying that things have "a proof of security".
Rot13 has a proof of security, but I don't want to use it. You need to
state what security properties you have proved.

-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: Jon Callas <[email-masked]>
Date: Sat, 10 Jan 2009 13:56:24 -0800

> state what security properties you have proved.

If we're going to get picky, Rot-13 is not a cipher, it's a code. It  
has similar security properies to ASCII, which is a related code. But  
you're right -- on another list I'm on, there was someone who made the  
comment that there's no theoretically perfect cryptography. I almost  
replied that the Caesar cipher (which is ROT-N) has perfect security,  
just an inadequate key space.

Nonetheless, you're right. Many people including me sneer at security  
proofs. The list of things that have had proofs of security and then  
fallen over is large. There are plenty of proofs of security that have  
some people raise an eyebrow. For example, we say that HMAC is secure  
on today's slightly dodgy hash functions because of a proof of  
security, but that proof relies on properties of the hash function  
we're not sure they have. (Niels Ferguson was the first person I know  
to bring this up, and for the most part, we all whistle as we walk by  
his observations.)

I think that security proofs are fundamentally lacking in basic  
foundations. There's a sense in which you can start with the Peano  
postulates for arithmetic and end up with double entry bookkeeping. We  
can't do anything like that in security, and it's a huge lack.

Nonetheless, it's better to have a proof than not to have one. And I  
didn't want to turn this into a Skein discussion, I was making the  
aside that there are people looking at verification constructions that  
have properties programmers like, and I know this because I've worked  
on one.

Go read the Skein paper. It's at <http://www.skein-hash.info>. I think  
we've addressed your comments, because we feel the same way.

	Jon

---

From: Florian Weimer <[email-masked]>
Date: Sun, 11 Jan 2009 18:04:02 +0100

> air them as soon as possible.

There's the issue of V3 keys.

If packet formats are changed once again, it could make sense to
incorporate random blobs near the start of the packets, so that an
attacker cannot predict the internal state of the hash function when a
signature is created.  OpenPGP does not need the convergent property
of hash functions.

---

From: Ben Laurie <[email-masked]>
Date: Tue, 13 Jan 2009 11:30:37 +0000

Jon Callas wrote:
> If we're going to get picky, Rot-13 is not a cipher, it's a code.

So what?

> It  
> proofs.

Then why mention them?

> The list of things that have had proofs of security and then  
> Nonetheless, it's better to have a proof than not to have one.

If the proof proves something useful, then indeed it is better. But once
more, saying "it has a security proof" provides no useful information.

> And I

I have read the Skein paper.