Subject: Re: New results against SHA-1

From: Daniel Kahn Gillmor <[email-masked]>
Date: Mon, 04 May 2009 11:32:04 -0400

On 04/30/2009 06:39 PM, David Shaw wrote:
> 
> http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf
> 
> There is not much hard information yet, but the two big quotes are
> "SHA-1 collisions now 2^52" and "Practical collisions are within
> resources of a well funded organisation."

Ugh.  i didn't think this would happen this soon.

I'd like to formally suggest that we need to re-open this working group
and begin discussion on a new revision of the OpenPGP draft.

Whether or not the above report turns out to have legitimate theoretical
grounding (i've only read the abstract, and don't know if my math would
be sufficient to evaluate a full report anyway), we know that there are
explicit dependencies on SHA-1 in OpenPGP that need to be made more
flexible.

Here are some key points that need to be adjusted w.r.t. digest algorithms:

 a) Fingerprints: these are currently SHA-1 hashes of the public key
mateerial.  One proposal is to continue hashing the exact same data but
to prefix the fingerprint with the canonical name of the digest
algorithm used, separated by an unambiguous delimiter (i'm using -
because : seems pretty overloaded in a lot of places, but i'm sure we
can collaboratively choose a good delimiter).  So in that case, my
current fingerprint would be re-written as:

 SHA1-0EE5BE979282D80B9F7540F1CCD2ED94D21739E9

 b) fix the Revocation Key (subpacket 12) to indicate digest algorithm
and variable length data.  A poorly-worded attempt at a revision:

5.2.3.15.  Revocation Key

   (1 octet of class, 1 octet of public-key algorithm ID, 1 octet of
   digest algorithm, N octets of digest)

   Authorizes the specified key to issue revocation signatures for this
   key.  Class octet must have bit 0x80 set.  If the bit 0x40 is set,
   then this means that the revocation information is sensitive.  If bit
   0x20 is unset, the digest algorithm is assumed to be SHA-1, and no
   octet identifying the digest algorithm is included.  Implementations
   SHOULD set bit 0x20 and explicitly include the hash identifier.
   Other bits are for future expansion to other kinds of authorizations.
   This is found on a self-signature.

   If the "sensitive" flag is set, the keyholder feels this subpacket
   contains private trust information that describes a real-world
   sensitive relationship.  If this flag is set, implementations SHOULD
   NOT export this signature to other users except in cases where the
   data needs to be available: when the signature is being sent to the
   designated revoker, or when it is accompanied by a revocation
   signature from that revoker.  Note that it may be appropriate to
   isolate this subpacket within a separate signature so that it is not
   combined with other subpackets that need to be exported.

 c) settling on a new "lowest-common-denominator" hash aside from SHA-1
(or discarding the idea of a lowest-common-denominator hash?)

Some other possible changes:

 d) suggesting new defaults for key choices (does this mean avoiding
DSA1, for example, or other algorithms that rely on 160-bit hashes?)

 e) allow injection of arbitrary key material at the head of signatures
to allow signers to to avoid a chosen-prefix attack?  This would make it
significantly more difficult to predict the hash that someone will sign,
which makes birthday attack collisions more difficult to pull off since
the signer cannot be compelled to sign a particular hash.

 f) explicit introduction of new hashes/ciphers/asymmetric algorithms?

I've probably missed something.  What else should be addressed?  What
steps are necessary to get the WG back in order again?  Or is that not
needed?

	--dkg

---

From: Werner Koch <[email-masked]>
Date: Mon, 04 May 2009 19:38:28 +0200

>  SHA1-0EE5BE979282D80B9F7540F1CCD2ED94D21739E9

Using a number (2) and, say, a dot as a prefix would be a better choice.
We use algorithnm numbers anyway and OpenPGP users are used tp spell a
large row of hex digits; we would only confuse them with an S and an H..

> significantly more difficult to predict the hash that someone will sign,

and gives more bandwidth for a subliminal channel...

>  f) explicit introduction of new hashes/ciphers/asymmetric algorithms?

We should defer such a discussion until there are semi final results
from the SHA-3 contest.

> steps are necessary to get the WG back in order again?  Or is that not

Right, we should re-establish the WG to no rely on I-Ds by individuals.

Salam-Shalom,

   Werner

-- 
Die Gedanken sind frei.  Auschnahme regelt ein Bundeschgesetz.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Mon, 04 May 2009 14:22:18 -0400

> large row of hex digits; we would only confuse them with an S and an H..

ok, that works for me.  would the prefix be in hex or decimal?  for
example, would an SHA512 fingerprint look like
 a.3dd7a2cb8f9e51f2fc096e7022a8192099aa89e10c699e46223851cc36f406b1beb734d5a7da0d8ebc08cc37e30088300c7a9ae81ba7ab758047a89cfa191aff

or

10.3dd7a2cb8f9e51f2fc096e7022a8192099aa89e10c699e46223851cc36f406b1beb734d5a7da0d8ebc08cc37e30088300c7a9ae81ba7ab758047a89cfa191aff

Ugh.  that's horrifically long either way.  Is a base64 encoding worth
considering?  it would shave off a third of the length, but it seems
like it would introduce significant ambiguity (0 vs O, A vs a, etc)

> and gives more bandwidth for a subliminal channel...

True, but some room for the subliminal channel already exists (e.g.
notations can be injected in the signed material).  This would simply
allow signers to better control what they actually sign, rather than
being compelled into signing a given text.  Daniel Franke's recent
message on gnupg-devel about this is interesting:

 http://lists.gnupg.org/pipermail/gnupg-devel/2009-May/024967.html

Another approach would be to formally prefer digest algorithms that do
not exhibit the same single-pass behavior of SHA-1 -- is that feasible?

> We should defer such a discussion until there are semi final results

SHA-3 finalizes in the end of 2012, though first-round candidates have
already been selected.  Third quarter of 2010 should have finalists
selected:

  http://csrc.nist.gov/groups/ST/hash/timeline.html

Which phase of the timeline would be sufficient for you?

> Right, we should re-establish the WG to no rely on I-Ds by individuals.

So what's the process to do this?

	--dkg

---

From: David Shaw <[email-masked]>
Date: Mon, 4 May 2009 14:57:21 -0400

> large row of hex digits; we would only confuse them with an S and an  

I like the dot, but I'd like to see the hash number in two-digit hex.   
The reason is that I strongly suspect that when read out over the  
phone, or written down, or transmitted in pretty much any means other  
than strict cut-and-paste, the dot (or any other delimiter) will be  
lost in translation.  Thus, "40.ABCDEF0123456....." will become  
"40ABCDEF0123456....." and we would have to play length checking games  
to guess if they meant hash 4 or 40.

With 2-digit hex, "4" would be written as "04", removing any doubt.

David

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Mon, 04 May 2009 15:24:13 -0400

On 05/04/2009 02:57 PM, David Shaw wrote:
> we would have to play length checking games

We're still going to have to do a little bit of length-checking games,
to distinguish between traditional SHA1 fingerprints and an
accidentally-truncated version of the newer (and presumably longer)
fingerprints.

One of the reasons that i initially proposed prefixes like SHA256- is
because they are so unambiguously *unlike* the traditional fingerprints
that it is clear what to expect next.

	--dkg

---

From: David Shaw <[email-masked]>
Date: Mon, 4 May 2009 15:45:50 -0400

> accidentally-truncated version of the newer (and presumably longer)

We can use the presence of the delimiter dot to tell the difference.

If they've lost the dot, then, well, absent some special knowledge, we  
can't really tell the difference between a old-style fingerprint and a  
new-style fingerprint that is both accidentally truncated and missing  
its delimiter dot.  I wouldn't even try.

Note that the current OpenPGP does not attempt to tell the difference  
between a V3 fingerprint (32 printed digits) and a V4 fingerprint that  
just happened to lose 8 characters in a cut and paste error  
somewhere.  That's the job of the client (if it chooses to take it on  
at all) more so than the job of the protocol.

David

---

From: David Shaw <[email-masked]>
Date: Mon, 4 May 2009 17:51:55 -0400

On May 4, 2009, at 2:22 PM, Daniel Kahn Gillmor wrote:

> a. 
> 3dd7a2cb8f9e51f2fc096e7022a8192099aa89e10c699e46223851cc36f406b1beb734d5a7da0d8ebc08cc37e30088300c7a9ae81ba7ab758047a89cfa191aff
>
> or
>

I'm sure there is a study somewhere that says just how long of a  
string a human being can handle without getting lost, but even without  
such a study I can say that 512 bits is just too long for usability.   
If you think about it, the whole point of fingerprints is that they're  
a short way to refer to a key.  If we make them too long, we're  
hurting the very thing that fingerprints were created for.

"3dd7a2cb8f9e51f2fc096e7022a8192099aa89e10c699e46223851cc36f406b1beb734d5a7da0d8ebc08cc37e30088300c7a9ae81ba7ab758047a89cfa191aff 
" is not exactly the kind of thing someone could print on a business  
card or read to a corespondent over the phone.

David

---

From: "Daniel A. Nagy" <[email-masked]>
Date: Tue, 05 May 2009 00:09:34 +0200

> like it would introduce significant ambiguity (0 vs O, A vs a, etc)

I would go the other way. Since collision-resistance is not an issue with
fingerprints, 128 bits are perfectly adequate for 2048-bit keys (i.e. breaking
the key and making a new key matching the fingerprint require about the same
amount of work). Also, keeping mobile phones in mind, I would suggest using 40
decimal digits. This way, the total length of fingerprints remain the same (40
characters), but typing them in on a decimal keypad would be much faster than
currently.

-- 
Daniel

---

From: Werner Koch <[email-masked]>
Date: Tue, 05 May 2009 09:09:01 +0200

> not exhibit the same single-pass behavior of SHA-1 -- is that feasible?

No.  Single pass processing an important feature.  Anything else can
only be done if the required amount of RAM is small enough and with an
upper limit to be implemented on small devices.  Think of a network
proxy with no need to store the data passing through but to verify
signatures of large chunks of this data.

Salam-Shalom,

   Werner