Re: A review of hash function brittleness in OpenPGP


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


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

* PGP Signed by an unknown key

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.


Great comments.



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.


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

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.


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

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.


Solved by upgrading fingerprints and three more paragraphs of text.



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.


Are you volunteering to write a document?



Regards,

      --dkg

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


* Unknown Key
* 0xD21739E9