Re: A review of hash function brittleness in OpenPGP

[Jon Callas <[e-mail]>]

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


-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.6.3
Charset: US-ASCII

wj8DBQFJZ8+zsTedWZOD3gYRAkutAJ0Wo0iRVUNDaF1KAw//GocHyI+PbwCgzdZ8
pWhsc6izhtYXW5MYUnkiwVA=
=6Xt5
-----END PGP SIGNATURE-----