An Open Specification for Pretty Good Privacy (openpgp)

David Shaw | 4 May 2009 23:35

Non-SHA-1 fingerprints


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

(Continue reading)

Jon Callas | 5 May 2009 01:32

Re: Non-SHA-1 fingerprints


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

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" <jcallas <at> pgp.com>
> Date: April 1, 2009 3:43:08 AM PDT
> To: "Derek Atkins" <warlord <at> pgp.com>
> Cc: "Jon Callas" <jon <at> pgp.com>
> 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
> ------

(Continue reading)

Ian G | 5 May 2009 00:19

Re: Non-SHA-1 fingerprints

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

Daniel A. Nagy | 5 May 2009 00:04

Re: Non-SHA-1 fingerprints

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.

--

--

(Continue reading)

Daniel Kahn Gillmor | 11 May 2009 22:58

collision-resistance and self-signatures [was: Re: Non-SHA-1 fingerprints]

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

On 05/04/2009 06:04 PM, Daniel A. Nagy wrote:
> 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.

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

(Continue reading)

Daniel A. Nagy | 12 May 2009 07:41

Re: collision-resistance and self-signatures [was: Re: Non-SHA-1 fingerprints]

I think, you are right. My bad.

Daniel Kahn Gillmor wrote:
> (dredging this up from a week ago because i was re-thinking it today)
> 
> On 05/04/2009 06:04 PM, Daniel A. Nagy wrote:
>> 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.
> 
> 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).

(Continue reading)

Daniel Kahn Gillmor | 5 May 2009 04:47

Re: Non-SHA-1 fingerprints

On 05/04/2009 06:04 PM, Daniel A. Nagy wrote:
> 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.

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.

(Continue reading)

Daniel A. Nagy | 5 May 2009 08:17

Re: Non-SHA-1 fingerprints

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

Daniel Kahn Gillmor wrote:
> On 05/04/2009 06:04 PM, Daniel A. Nagy wrote:
>> 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.
> 
> 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.
>

(Continue reading)

David Shaw | 5 May 2009 02:17

Re: Non-SHA-1 fingerprints

On May 4, 2009, at 6:04 PM, Daniel A. Nagy wrote:

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

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

Ingo Klöcker | 6 May 2009 00:00

Picon

Re: Non-SHA-1 fingerprints

On Tuesday 05 May 2009, David Shaw wrote:
> On May 4, 2009, at 6:04 PM, Daniel A. Nagy wrote:
> > 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.
>
> 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.

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

(Continue reading)

Hal Finney | 5 May 2009 17:03

Re: Non-SHA-1 fingerprints

On 05/04/2009 06:04 PM, Daniel A. Nagy wrote:
> 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.

To quibble a bit, the real issue is not the specific usage, but whether
the creator of the signature controls the content that is hashed, and
whether he adds enough information and "entropy" of his own that no
outsider could substantially control and/or guess the content.

I can imagine situations from the list above where outsiders might be
able to mount an attack. Even self-signatures may have substantial
data contributed by outsiders, at least with use of some allowed
extensions. We have notation subpackets and possibly other subpackets
which could include data that is supplied by outsiders.

PGP has for many years supported an extension to the User ID called a
Photo ID, which includes a picture of the key holder. Imagine if you added
to your key a photo of yourself, but one that was taken by someone else,
and signed it with a self signature using a weak hash. Some time later
you might discover a different-looking photo circulating, signed with
that same signature (because the photo was gimmicked to allow a change
in some data to display a different image).  One could imagine security
implications of this kind of substitution.

MDC packets should be immune because we hash the prefix which should
normally include 128+ bits of randomness. Likewise with fingerprints,
presumably the key itself includes sufficient randomness to make it
unguessable, otherwise many other attacks are possible.

(Continue reading)

Daniel Kahn Gillmor | 5 May 2009 03:22

decimal fingerprints [was: Re: Non-SHA-1 fingerprints]

On 05/04/2009 08:17 PM, David Shaw wrote:
> 
> On May 4, 2009, at 6:04 PM, Daniel A. Nagy wrote:
> 
>> 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.
> 
> 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.

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)

(Continue reading)

Daniel A. Nagy | 5 May 2009 08:15

Re: decimal fingerprints [was: Re: Non-SHA-1 fingerprints]

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.

Daniel Kahn Gillmor wrote:
> On 05/04/2009 08:17 PM, David Shaw wrote:
>> On May 4, 2009, at 6:04 PM, Daniel A. Nagy wrote:
>>
>>> 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.
>> 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.
> 
> 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).

(Continue reading)

David Shaw | 5 May 2009 02:17

Fix revocation keys instead of fingerprints? (was Re: Non-SHA-1 fingerprints)

On May 4, 2009, at 6:04 PM, Daniel A. Nagy wrote:

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

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:

(Continue reading)

Daniel A. Nagy | 5 May 2009 08:13

Re: Fix revocation keys instead of fingerprints? (was Re: Non-SHA-1 fingerprints)

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
> * Needs to be small to be useful
> * Can collide to some small amount (4880 even documents that they
> collide in section 12.2)

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

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

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

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

There is nothing wrong with them at present.

(Continue reading)

David Shaw | 7 May 2009 17:45

Re: Fix revocation keys instead of fingerprints? (was Re: Non-SHA-1 fingerprints)


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

> 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
>> * Needs to be small to be useful
>> * Can collide to some small amount (4880 even documents that they
>> collide in section 12.2)
>
> That's not the fingerprint. That's the key ID.

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-

(Continue reading)

Daniel Kahn Gillmor | 7 May 2009 19:46

keyids vs. fingerprints [was: Re: Fix revocation keys instead of fingerprints?]

On 05/07/2009 11:45 AM, David Shaw wrote:
> On May 5, 2009, at 2:13 AM, Daniel A. Nagy wrote:
>> David Shaw wrote:
>>> 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)
>>
>> That's not the fingerprint. That's the key ID.
> 
> 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

(Continue reading)

Daniel A. Nagy | 7 May 2009 19:06

Re: Fix revocation keys instead of fingerprints? (was Re: Non-SHA-1 fingerprints)

Hello,

David Shaw wrote:
> On May 5, 2009, at 2:13 AM, Daniel A. Nagy wrote:
> 
>> 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
>>> * Needs to be small to be useful
>>> * Can collide to some small amount (4880 even documents that they
>>> collide in section 12.2)
>>
>> That's not the fingerprint. That's the key ID.
> 
> 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.

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.

(Continue reading)

Daniel Kahn Gillmor | 5 May 2009 04:49

Re: Fix revocation keys instead of fingerprints? (was Re: Non-SHA-1 fingerprints)

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

Werner Koch | 5 May 2009 08:59

Picon

Re: Fix revocation keys instead of fingerprints?


On Tue,  5 May 2009 04:49, dkg <at> fifthhorseman.net said:

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

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.

Return

Return to gmane.ietf.openpgp.

Search Archive

Language

Change language

Options

Current view: Threads only / Showing only 20 lines / Not hiding cited text.
Change to All messages, whole messages, or hide cited text.

Post a message
NNTP Newsgroup
Classic Gmane web interface
XML

XML

RSS Feed
List Information

About Gmane