Subject: Non-SHA-1 fingerprints

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

Now that I think about the variable-hash fingerprint question a bit,  
I'm concerned about things like RFC-4398, which uses OpenPGP  
fingerprints in DNS.  There is a fingerprint field there, and it is  
variable length, but it has no concept of hash algorithm.  We'd have  
to define some standard way to write out a fingerprint in binary with  
the hash field incorporated.

So given that, I am wondering why we need a delimiter between the hash  
specifier and the fingerprint data for the human-readable version at  
all?  A written fingerprint is expected to be readable, but not  
interpretable by a human being anyway, and software doesn't care about  
the delimiter one way or another.

So rather than 01.23456789ABCDEF.... or MD5-23456789ABCDEF... why not  
just 0123456789ABCDEF... ?

We already have a concept of variable length fingerprints (V3 = 16  
bytes, and V4 = 20 bytes), and this fits reasonably well alongside  
those two.  The rule would be 16 bytes means it's V3, 20 bytes means  
it's V4, and an odd number of bytes means it's this new format.  If  
you see an odd number of bytes, you pull off the leftmost byte, and  
that's the algorithm number.  The rest of the bytes are the hash  
value.  We can trivially transform a V4 fingerprint into this new  
format by sticking the value 2 in front of it.

This does, of course, presume that all of our hashes for OpenPGP in  
the future will generate an even number of bytes.

David

---

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

David Shaw wrote:
> 
> Now that I think about the variable-hash fingerprint question a bit, I'm
> concerned about things like RFC-4398, which uses OpenPGP fingerprints in
> DNS. 

For fingerprints, MDC and self-signatures, collision-resistance does not matter,
only the one-way property. So I think it is totally safe to postpone discussion
until SHA3 is selected.

Reviewing the fingerprint is a MAJOR issue, as (parts of) fingerprints are used
as lookup keys in the PKS database.

Here are some points:

I believe that a fingerprint that is longer than 160 bits is pointless; even 160
bits is an overkill causing inconvenience with no tangible benefit in terms of
security over a 128 bit fingerprint.

What does cause some problems, is the fact that the creation date (32 bits) is
included in the fingerprint. It makes sevaral attacks substantially easier than
if the fingerprint was calculated only over the key material and key attributes
(such as key type). Basically, it should be impossible for the same key to have
different fingerprints.

Also, since mobile phones typically have a numeric keypad, it would be nice if
fingerprints and key IDs were numeric-only. It is an increasingly important
platform for OpenPGP, I believe.

-- 
Daniel

---

From: Ian G <[email-masked]>
Date: Tue, 05 May 2009 00:19:05 +0200

On 4/5/09 23:35, David Shaw wrote:

> This does, of course, presume that all of our hashes for OpenPGP in the
> future will generate an even number of bytes.

I like the idea.

But, I'm the one who favours aphorisms such as "there is only one mode, 
and it is secure."  Or, perhaps, "There is one cipher suite, and it is 
numbered Number 1."

So I would be looking for SHA3 as the one and only thing that ever 
hashes the publics, and bugger the rest.  Algorithm agility is for the 
birds.  We would just need to agree how many even bytes to allocate to 
the SHA3 for the next 4 decades.

iang

---

From: Jon Callas <[email-masked]>
Date: Mon, 4 May 2009 16:32:52 -0700

At the last IETF meeting, Derek discussed new drafts (particularly  
this one) with Tim Polk, and either Derek can shepherd it, or we can  
find someone else. I sent Derek a sketch of what I propose.

Note that it's pretty much what's been discussed here, but I used a  
colon (which is what I remember in the original proposal) rather than  
a dot.

> From: "Jon Callas" <[email-masked]>
> Date: April 1, 2009 3:43:08 AM PDT
> To: "Derek Atkins" <[email-masked]>
> Cc: "Jon Callas" <[email-masked]>
> Subject: Re: OpenPGP Extensions Doc(s)
>
> * PGP Signed: 04/01/2009 at 07:37:45 AM, Decrypted
>

...

>
> Here's what I propose:
>
> We define a new fingerprint.
>
> Basics
> ------
>
> The fingerprint is a struct, consisting of:
>
> Hash Alogrithm Type (1 Octet)
> Hash Value (N Octets)
>
> The hash is computed over the same fields of the key packet, just as  
> in RFC4880, just with a different hash function than SHA1.
>
> Truncations
> -----------
>
> The Hash Value may be of any size equal to or less than the natural  
> size of the hash function. If it is a truncation, then it is the  
> high-order bits. Thus, the SHA1 hash "ED15 5BDF CD41 ADFC 00F3  28B6  
> 52BF 5A46 BC98 E63D" truncated to 64 bits is "ED15 5BDF CD41 ADFC".
>
> There are a number of reasons truncating a fingerprint. One is for  
> ease in transport, display, etc. In the past, we moved from 16-byte  
> fingerprints to 20-byte fingerprints. While a larger fingerprint may  
> have increased cryptographic use, human beings still sometimes use  
> them
>
> Display
> -------
>
> The normal display of a fingerprint is:
>
> <algid>:<hex digits>
>
> White space may be added for readability.
>
> Example:
>
> 2:ED15 5BDF CD41 ADFC 00F3  28B6 52BF 5A46 BC98 E63D
>
> Other formats are possible, but they should remember to show the  
> algorithm either numberically or symbolically. Note that RFC 4880  
> defines ASCII display strings for all algorithms.
>
> Fingerprint Preference
> ----------- ----------
> This is a new preference subpacket that is a single byte of the hash  
> algorithm preferred fingerprint type. Not only can this be used by  
> an implementation for display, but an implementation SHOULD use this  
> algorithm for determining a key id when encrypting to that key.
>
> If this preference is not present, the implementation SHOULD use old- 
> style SHA1 fingerprints.
>
> Key IDs
> --- ---
>
> OpenPGP already has one natural truncation of the fingerprint, the  
> Key ID. Under this proposal, a Key ID is a 64-bit truncation of the  
> Hash Value of a fingerprint. An example is given above.
>
> Note that for SHA1, this means that there are two possible Key IDs,  
> the old one and a new one. RFC 4880 (and 2440 before it) already  
> said that an implementation must recognize that there could be  
> collisions in Key IDs. An implementation SHOULD use the old-style  
> one unless there is a preference specifying SHA1.
>
> Other places to look at
> ----- ------ -- ---- --
>
> We need to look at updating (or handwaving) 5.2.3.15.  Revocation Key.
>
> What do you think?
>
> 	Jon
>
>
> -- 
> Jon Callas
> CTO, CSO
> PGP Corporation         Tel: +1 (650) 319-9016
> 200 Jefferson Drive     Fax: +1 (650) 319-9001
> Menlo Park, CA 94025    PGP: ed15 5bdf cd41 adfc 00f3
> USA                          28b6 52bf 5a46 bc98 e63d
>
>
>
>
> * Jon Callas <[email-masked]>
> * 0xBC98E63D(L)
>

---

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

> only the one-way property. So I think it is totally safe to postpone  

It's a larger problem than just fingerprints.  We also use a  
fingerprint as a specifier inside the revocation key subpacket, to  
designate which key can be used to issue revocations on our behalf.   
The thing is, though, a fingerprint isn't really a very good  
revocation key specifier:

Fingerprints:
* Must be human-readable
* Needs to be small to be useful
* Can collide to some small amount (4880 even documents that they  
collide in section 12.2)

Revocation key specifier:
* Does not need to be human-readable
* Has much looser size requirements (shouldn't be enormous, but  
certainly can be bigger than 160 bits without hurting anything)
* Should never collide (we don't want the wrong key being able to  
revoke our key)

Perhaps we'd do better by leaving fingerprints alone and instead  
fixing how we specify revocation keys?

We could try to come up with a new non-colliding way to disambiguate  
keys, but fundamentally, anything that is smaller than the key packet  
itself can still collide.  So instead, why not define a new revocation  
subpacket that contains the class octet from the old revocation key,  
and the rest of the subpacket is simply a copy of the public key  
packet in question?  I don't mean the whole transferable public key,  
of course, just the contents of packet #6.  This public key packet  
doesn't need any self-signatures or anything else like that, as it is  
implicitly authenticated by the signature that carries the revocation  
key subpacket.

David

---

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

> platform for OpenPGP, I believe.

I think that is a good point and a great idea, but the only reason  
that fingerprints and key IDs are printed in hex now is tradition.   
There is nothing in the standard one way or another about how humans  
should consume fingerprints.  You could even do it with the current V4  
fingerprints: just as my key fingerprint is
7D92FD313AB6F3734CC59CA1DB698D7199242560 in hex, it is equally correct  
as 716901811312187285520504099705403090347495794016 in decimal.  The  
big problem I see here is that's it's an awfully long number to type  
into a mobile keypad.  (Well, that, and persuading the various  
implementations to support the decimal format in addition to the  
traditional hex).

David

---

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

On 05/04/2009 08:17 PM, David Shaw wrote:
> I think that is a good point and a great idea, but the only reason that
> fingerprints and key IDs are printed in hex now is tradition.  There is
> nothing in the standard one way or another about how humans should
> consume fingerprints.  You could even do it with the current V4
> as 716901811312187285520504099705403090347495794016 in decimal.  The big
> problem I see here is that's it's an awfully long number to type into a
> mobile keypad.

How often does anyone type in a fingerprint at all?  My impression of
the typical workflow is:

 * read fingerprint from physical media (business card, scrap of paper, etc)

 * search for a key from the public keyservers (usually by User ID).

 * scan list of results for a key with a matching keyid (truncated
fingerprint)

 * fetch selected key from keyserver

 * view/double-check fingerprint of fetched key againt physical media

In this workflow, the only typing done is to enter the user id to search
for (and even that is not always needed on a mobile device, because the
person searched for is may already be in the address book for other
contacts).  if the fingerprint is entered, it's often only the truncated
keyid, which is guaranteed to be much smaller than the fpr in any case.

Making this change to the fingerprint presentation seems huge: are
people expected to change all their business cards, .sigs, web sites,
etc. to show both styles of fingerprint?  or to completely transition to
the new style?  in terms of truncated fingerprints (keyids), how are we
to distinguish between the ones which currently have only digits 0-9 in
hex and decimal-style fingerprints?  This seems like a very costly
tradeoff for the sake of thumbing in 8 decimal characters instead of 8
hex digits.

	--dkg

---

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

> only the one-way property. So I think it is totally safe to postpone discussion

The more that i consider this, the more important it seems.  Thank you
for emphasizing it, Daniel.

If i understand you correctly, your point is that fingerprints and
self-signatures use hashes over data that is provided entirely by the
signer, covering nothing that is supplied by an outside party.

Since "birthday" attacks rely on the attacker generating an arbitrary
collision, providing one side of it for signing by the victim, and then
transferring the signature onto the other side of the discovered
collision, they do not work against material under full control of the
signer (like fingerprints and self-sigs).

Even if the recent claims of O(2^52) (instead of the
theoretically-optimal 2^80) operations to generate a colliding pair were
to scale proportionally to attacks against the one-wayness of SHA-1,
that would mean O(2^104) (instead of 2^160) operations to find a message
that hashes to a given value.  i have no idea if these sort of results
can actually scale this way, but i  imagine we'd hear a much larger
hullabaloo if someone had announced an  attack against the one-wayness
of SHA-1 with less than O(2^104) operations.

Anyway, since 2^104 is still outside the capabilities of well-funded
organizations, we have breathing room on these parts of the
specification that only rely on collision-resistance.

Did i get anything wrong above?  I apologize if this is elementary for
everyone else, i'm just trying to make sure i understand the ideas involved.

	--dkg

---

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

On 05/04/2009 08:17 PM, David Shaw wrote:
> Perhaps we'd do better by leaving fingerprints alone and instead fixing
> how we specify revocation keys? 
 [...]
> why not define a new revocation
> subpacket that contains the class octet from the old revocation key, and
> the rest of the subpacket is simply a copy of the public key packet in
> question?  I don't mean the whole transferable public key, of course,
> just the contents of packet #6.

This seems like a good strategy to me, and a *much* simpler one than
trying to overhaul fingerprints!  In fact, this seems like a good idea
whether or not fingerprints are overhauled.  Are there any objections in
the WG to this re-definition of revocation key subpackets?  the largest
realistic keys out there right now are still only around 1KB of a
subpacket, and revocation key subpackets themselves are pretty rare.  So
the added size doesn't seem problematic to me.

	--dkg

---

From: "Daniel A. Nagy" <[email-masked]>
Date: Tue, 05 May 2009 08:13:58 +0200

Hi,

David Shaw wrote:
> It's a larger problem than just fingerprints.  We also use a fingerprint
> as a specifier inside the revocation key subpacket, to designate which
> key can be used to issue revocations on our behalf.  The thing is,
> though, a fingerprint isn't really a very good revocation key specifier:
> 
> Fingerprints:
> * Must be human-readable

That's not the fingerprint. That's the key ID.

> * Should never collide (we don't want the wrong key being able to revoke
> our key)

In case of collision, both colliding pre-images are done by the same entity.

> how we specify revocation keys?

There is nothing wrong with them at present.

Well, actually, I would argue that revocation is currently over-designed. Since
revocation is an irreversible act, there is no need for the heavy artillery of
digital signatures for that purpose. All the s2k specifiers used for symmetric
encryption would do (in a hashed sub-packet together with the resulting
symmetric key) and inserting a non-hashed sub-packet with a matching revocation
passphrase into the revoked signature would be just as secure a method for
revocation than adding a revocation signature packet.

There is no need for asymmetric crypto for revocation. Instead of revocation
signatures, it would be perfectly safe to use revocation passphrases.

> itself can still collide.

Again, collisions are not important in this case. Collisions only matter when
the signed information is compiled by a different entity than the signer.

With a hash that is one-way but not collision resistant, you can do two keys
that have the same fingerprint. So whay? Both are under your control, a
signature with either is your signature.

> So instead, why not define a new revocation
> question?

It costs more and does not provide any extra security. I mean there is no attack
that can be prevented in this way. Therefore, it is less secure.

>  I don't mean the whole transferable public key, of course,
> just the contents of packet #6.  This public key packet doesn't need any
> self-signatures or anything else like that, as it is implicitly
> authenticated by the signature that carries the revocation key subpacket.

It still makes the key fatter without making any attack more difficult. It won't
make illegitimate revocation more difficult.

-- 
Daniel

---

From: "Daniel A. Nagy" <[email-masked]>
Date: Tue, 05 May 2009 08:17:48 +0200

Your reasoning below is correct, as far as I can tell.

---

From: "Daniel A. Nagy" <[email-masked]>
Date: Tue, 05 May 2009 08:15:29 +0200

Actually, it is not the fingerprint, but the key ID that is typed in, but it is
a NICE feature of OpenPGP at present that the key ID is simply a substring of
the fingerprint. I would hate to lose that.

---

From: Werner Koch <[email-masked]>
Date: Tue, 05 May 2009 08:59:33 +0200

> the added size doesn't seem problematic to me.

I concur.

In fact the forthcoming default of RSA signatures will increase the size
of a keyblock far more than a single longer revocation key subpacket.

Shalom-Salam,

   Werner

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

---

From: Ingo Klöcker <[email-masked]>
Date: Wed, 06 May 2009 00:00:42 +0200

On Tuesday 05 May 2009, David Shaw wrote:
> should consume fingerprints.  You could even do it with the current
> V4 fingerprints: just as my key fingerprint is
> 7D92FD313AB6F3734CC59CA1DB698D7199242560 in hex, it is equally
> correct as 716901811312187285520504099705403090347495794016 in
> decimal.  The big problem I see here is that's it's an awfully long
> number to type into a mobile keypad.

Right. I do already have a hard time typing an unknown phone number with 
8 digits.

Since most mobile phones come with a camera nowadays the way to go is to 
take a picture of the fingerprint and then run some OCR on the picture. 
In fact, it would be much better to encode the fingerprint in some kind 
of easily scanable bar code (additionally to the common hex 
fingerprint) than as long string of numbers (similar to Semapedia).

Regards,
Ingo

P.S.: The mailing list software does not add a List-Post header (which 
is used for "Reply to List" by my MUA). Is it possible to fix this?

---

From: David Shaw <[email-masked]>
Date: Thu, 7 May 2009 11:45:08 -0400

On May 5, 2009, at 2:13 AM, Daniel A. Nagy wrote:

>> fingerprint

A nit, but that really is the fingerprint.

12.2:

    Note that there is a much smaller, but still non-zero, probability  
that two different keys have the same fingerprint.

It's not exactly *likely*, but it's not quite zero.  I heard a urban- 
legendish story once about someone who (completely accidentally)  
generated a key that just happened to have a fingerprint collision  
with someone else's key.  Unfortunately, thinking it was a bug, they  
deleted the key... make of that what you will :)

David

---

From: "Daniel A. Nagy" <[email-masked]>
Date: Thu, 07 May 2009 19:06:20 +0200

Hello,

> that two different keys have the same fingerprint.

While the probability is non-zero, but it is roughly equal to accidentally
guessing the discrete logarithm of a DSA key or a prime factor of the RSA key.

> It's not exactly *likely*, but it's not quite zero.  I heard a
> urban-legendish story once about someone who (completely accidentally)
> generated a key that just happened to have a fingerprint collision with
> someone else's key.  Unfortunately, thinking it was a bug, they deleted
> the key... make of that what you will :)

There WAS a bug and he did the right thing.

-- 
Daniel

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 07 May 2009 13:46:48 -0400

> A nit, but that really is the fingerprint.

The important items here are 1 and 2, which both apply to a fingerprint.
 Humans need to be able to cognitively compare fingerprints, so they
must be both human-readable and small enough to wade through.

As for collisions, 32-bit key ids don't collide "to some small amount".
They have *massive* collisions because of the small output space.  It
takes a few hours of compute time on a single modern desktop machine to
generate 32-bit keyID collisions against every single key in the public
WoT.  64-bit keyids are better, but still nowhere near the collision
resistance we should be expecting from tools we expect humans to use to
validate content.

keyIDs are useful as pointers, but are not at all useful for
verification purposes.

	--dkg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Mon, 11 May 2009 16:58:22 -0400

(dredging this up from a week ago because i was re-thinking it today)

> only the one-way property. So I think it is totally safe to postpone discussion

I think this point holds for fingerprints and MDCs.  I'm not convinced
that it holds for self-signatures, though.

Let's assume Alice has an SHA-1 collision-generator that she can coax
into generating two messages, A and B with the same digest, and that she
is meeting Bob for a keysigning at the pub on Friday.

She crafts message A, which looks like a regular public key/uid
signature, including friday evening's timestamp and her User ID (this is
exactly the information to be hashed in a non-self-signature -- maybe it
hides the collision-generating bits in one of the public key MPIs?).
Message B is the data within a self-signature over Bob's key, asserting
something Bob didn't want to assert (e.g. binding a user ID of a known
villain, or binding a false encryption subkey which Alice controls).
The collision-generating bits in B might be hidden here in a notation
subpacket or something similarly opaque.

At the pub, Alice gets Bob to sign her key (message A) at just the right
time, retrieves his signature, and transfers it to the new bogus
self-sig (message B).

I think this means we need to consider self-signatures made over a given
algorithm as potentially spoofable if the digest's collision-resistance
is weakened.  It is *not* just the one-wayness that matters for self-sigs.

Is this analysis reasonable?  What have i missed?

	--dkg

PS i know that no one has demonstrated anything remotely close to the
hypothesized oracle i've given Alice above.  The point is just that
collision-resistance affects self-sigs in ways that it does not affect
the MDC or the fingerprint.

---

From: "Daniel A. Nagy" <[email-masked]>
Date: Tue, 12 May 2009 07:41:09 +0200

I think, you are right. My bad.