Subject: [openpgp] Fingerprints and their collisions resistance

From: Andrey Jivsov <[email-masked]>
Date: Wed, 02 Jan 2013 23:18:46 -0800

We exchanged a few emails on gnupg list about this this issue, which I 
think belongs here, the OpenPGP thread.

The issue is that fingerprint calculation method in OpenPGP is hardwired 
to use SHA-1. Some scenarios in which fingerprints are used  depend on 
hash function collision resistance.

It's easy to see the collision resistance requirement of fingerprints by 
making the comparison with document signatures.

Classical collision resistance requirement arises in a situation when 
the owner is free to create two documents that hash to the same hash 
value. The attacker then makes one document available for signing. As a 
result he has acquired an option to use the second document later and 
claim that it was the document that was originally signed.

When viewed as document, the keys fit this pattern. One possible 
exploitation of the hash collision is when the attacker can repudiate 
signatures or repudiate his ability to decrypt messages (because he can 
offer a wrong key with the same fingerprint as a proof supporting his 
inability to perform the private key operation).

Public keys offer a reasonable opportunity to place arbitrary bytes into 
fields that are hashed. For example, DSA P,Q,G, are primes. Every byte 
but the last one of a 2048 bit prime can be fixed, on average, due to 
the high density of primes. It suggests that the task of finding a 
collision with public keys is at least no more difficult than for ASCII 
documents.

Not all scenarios involving fingerprint depend on collision resistance. 
For example, the ability to substitute a designated revoker, which 
fingerprint is stored in a subpacket of a public key, is not assisted by 
compromised collision resistance of SHA-1.

As a remedy to the problem note that the collision resistance only 
arises when the original "document" is not available. Fortunately, keys 
are small, and therefore, the suggested enhancement to the RFC4880 to 
remedy the collision dependence of fingerprints on SHA-1 is to store the 
original key. Continuing the above example with non-repudiation, the 
non-repudiation claims will be made against the application logs (i.e. 
audit trails), thus it will be necessary to include complete keys in 
addition to fingerprints in logs that record protocol exchanges that are 
dependent on public key identification.

This concern will need to be communicated somehow to developers that are 
relying on RFC4880.

An alternative method is outlined next. We introduce a new hardwired 
fingerprint, for example, based on SHA-3. The above-mentioned 
application logs can simply state that "SHA-3 fingerprint is XXX" and 
not bother with storing the whole key (which is unfortunately allowed to 
change, for example, by acquiring new userIDs, making it hard to compare 
the revisions). Any subpacket that currently takes the fingerprint will 
be able to take the new SHA-3 fingerprint as well. Applications will be 
expected to calculate two fingeprints in parallel and perform a match 
with either of them. In addition, we might consider a features packet 
forcing or preferring SHA-3 fingeprint (similar to the MDC feature). 
KeyIDs in messages can also use 8 bytes of the new fingerprint.

Regarding compatibility, note that the fingerprint in the subpackets are 
not affected by collision weakness, so that there is no downgrade 
attack. Fingerprints that are sensitive to collision resistance are 
external features. In addition to mentioned application logs, consider 
the UI implication. When a key is looked up by its fingerprint on a key 
server, the UI can offer to search by SHA-1 or the new style fingerprint 
and this will work with any current key.

I will appreciate your comments on this feature. I don't expect this to 
be a task that needs an urgent resolution. In my mind this is something 
that we agree on, have a simple spec, and then take a few years to 
implement and deploy it in a least disruptive way.

If there is a more elegant/simpler solution? I would like to hear about it.

Thank you.

---

From: ianG <[email-masked]>
Date: Thu, 03 Jan 2013 12:03:10 +0300

> This concern will need to be communicated somehow to developers that are

I agree with this approach.  It means no change to the tech in the short 
term, just a note that is distributed (perhaps added in any next 
revision or additional ID):  to insure against future key collision 
possibilities in high-security application, store the full key with any 
fingerprint.

> KeyIDs in messages can also use 8 bytes of the new fingerprint.

Now that SHA-3 is settled, it seems reasonable to clean out all of the 
SHA-1s.

It would be nice if this were to take place within an overall 
refurbishment of the entire suite, e.g., OpenPGP 5 or whatever one calls 
it.  Any change is going to be disruptive, and confusion out in userland 
with different feature/time/brand sets leads to loss of users, which 
isn't really any good compensation for the illusory security advantage 
of replacing SHA1.

...
> implement and deploy it in a least disruptive way.

+1  It would be ideal if we could select a single small fixed suite of 
everything that would last for the next 2 decades.

> If there is a more elegant/simpler solution? I would like to hear about it.

On another related point - have the MD numbers been allocated for SHA3 
in its various guises?

iang

---

From: Nicholas Cole <[email-masked]>
Date: Thu, 3 Jan 2013 09:33:27 +0000

> think belongs here, the OpenPGP thread.

[snip]

> fields that are hashed. For example, DSA P,Q,G, are primes. Every byte but
> the last one of a 2048 bit prime can be fixed, on average, due to the high
> density of primes. It suggests that the task of finding a collision with
> public keys is at least no more difficult than for ASCII documents.
>

If anyone has already done this, they are keeping very quiet about it.

I don't think I favour interim solutions - it would be better if the issue
were tackled directly.  From a user point of view, it would be good if new
formats were decided that hard-wire a new formats.  I think that these
decisions should be made sooner rather than later, because it will take
some years for end-user software to fully catch up.  Is it impossible to
think that new standards would be decided this year?

One issue with SHA-3 is that the fingerprints are going to be very long.
 How should these be displayed to the user?  Hex strings seem unsuitable
for this task, and I think any new standard should recommend that
fingerprints be displayed in some other way - probably using a different
base.

Best wishes,

N.

---

From: Jon Callas <[email-masked]>
Date: Thu, 3 Jan 2013 08:17:52 -0800

The proposal that we had a long time ago which was essentially prefix a hash with an algorithm number was a good one. I remember everyone thinking it was a good idea and no one belling the cat. I vaguely remember someone writing up an I-D on it, too.

That's the way I'd go, as it's future-proofed.

	Jon

---

From: "Arturo 'Buanzo' Busleiman" <[email-masked]>
Date: Thu, 3 Jan 2013 13:22:04 -0300

+1 Jon!
On Jan 3, 2013 1:18 PM, "Jon Callas" <[email-masked]> wrote:

> The proposal that we had a long time ago which was essentially prefix a
> hash with an algorithm number was a good one. I remember everyone thinking
> it was a good idea and no one belling the cat. I vaguely remember someone
> writing up an I-D on it, too.
>
> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp
>

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 03 Jan 2013 11:06:18 -0800

> That's the way I'd go, as it's future-proofed.

I am a big fan of algorithm agility myself, but I have a difficult time 
justifying the additional complexity that the new *suite* of the 
fingerprints would bring v.s. just one new fingerprint algorithm.

Compare the situation with the AES. There are 3 AES sizes and other 
ciphers in use. Other ciphers exist as legacy ciphers that preceded AES 
or for regulatory reasons. 3 AES sizes exist for performance reasons.

None of these concerns apply for the new algorithm we are introducing ( 
we have clarity of future strength, small input for hashing, no 
export/import control of encryption). Fingerptins are special data 
structures because they are sometimes input by humans.

We now have SHA-3, which is good for a few decades ( and also SHA-2s are 
not so bad ).

Here is a more technical description, to be specific:

Let's say we choose SHA-3-384, which is no more difficult to implement 
than SHA-2. We then simply use the current fingerprint algorithm but 
instead of SHA-1 use SHA-3-384. Then allow truncation of the output 
(it's already implied by the 8 byte keyIDs). 20 byte fingerprint on a 
business card may be reasonable, but we also would like to have full 
strength for regulatory compliance. Consider not hashing the key 
creation date. Fixing all the variables in this paragraph, we have the 
new single fingerprint algorithm.

To put it differently, users may care about the hash associated with a 
signed message, but I don't think they materially care about the flavour 
of the fingerprint (as long as it's a "strong" one).

---

From: Tony Hansen <[email-masked]>
Date: Thu, 03 Jan 2013 14:26:17 -0500

On 1/3/2013 4:33 AM, Nicholas Cole wrote:
> One issue with SHA-3 is that the fingerprints are going to be very 
> long.  How should these be displayed to the user?  Hex strings seem 
> unsuitable for this task, and I think any new standard should 
> recommend that fingerprints be displayed in some other way - probably 
> using a different base.

SHA3 is defined for a variety of hash sizes. Using SHA3 does not imply a 
long fingerprint.

     Tony Hansen
     [email-masked]

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 03 Jan 2013 14:33:44 -0800

On 01/03/2013 01:03 AM, ianG wrote:
...
...
> On another related point - have the MD numbers been allocated for SHA3

In the process of writing such a draft I noticed that the only place in 
OpenPGP where SHA1 is used in collision resistance sensitive way without 
the possibility to change it is fingerprints. For this reason OpenPGP 
fingerprints stand out because these are the data structures that 
technically make (or soon will make) RFC 4880 non-compliant with 
recognized standards. I would separate the issue of fingerprints 
depending on known SHA1 weaknesses from any other task that can be 
categorized as "OpenPGP V5".

Speaking of the Keccak in OpenPGP draft, I thought that it would be 
important to gather the feeling about the path of fixing the 
fingerprints. These issues are more dependent as seems. For example, if 
you have to use SHA-3-384 for fingerprints, it affects the decisions 
about SHOULDs for hashes elsewhere.

I have this Keccak in OpenPGP darft written, waiting to for the NIST to 
publish SHA-3 and the OIDs assigned.

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 03 Jan 2013 14:38:36 -0800

> SHA3 is defined for a variety of hash sizes. Using SHA3 does not imply a

I would argue for SHA-3-384 and then possible truncation.

Keccak of different sizes is pretty much implemented as internal 
truncation anyway (of a large sponge structure), plus there is no 
different initialization vectors as for SHA-2 for different hash sizes.

The KeyIDs are the truncation of the fingerprint already.

---

From: Werner Koch <[email-masked]>
Date: Thu, 03 Jan 2013 23:54:33 +0100

On Thu,  3 Jan 2013 20:06, [email-masked] said:

> AES or for regulatory reasons. 3 AES sizes exist for performance
> reasons.

I'd say for marketing reasons. 

> structures because they are sometimes input by humans.

Well, humans compare fingerprints but don't enter them.  I doubt that I
ever did this in the last 20 years.

> than SHA-2. We then simply use the current fingerprint algorithm but

Except that SHA-2 is already in use and has hardware support.

> business card may be reasonable, but we also would like to have full

So why should we truncate the fingerprint?  Is there a reason to believe
that truncation to 160 bit of SHA-2 or SHA-3 is seriously more secure
than SHA-1?  I don't know.

> creation date. Fixing all the variables in this paragraph, we have the

What would be the advantage of this except for yet another code path.

> signed message, but I don't think they materially care about the
> flavour of the fingerprint (as long as it's a "strong" one).

They will care if a key suddenly comes with two different fingerprints.
We never had this situation in OpenPGP.  Recall how long it took to get
rid of v3 keys.  Thus if we want a new fingerprint algorithm we need to
change more than just this.

BTW, what about re-establishing the OpenPGP WG? 

Salam-Shalom,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 03 Jan 2013 18:08:42 -0500

On 01/03/2013 05:33 PM, Andrey Jivsov wrote:
> the possibility to change it is fingerprints.

As i mentioned on the discussion on the GnuPG discussion list, i remain
unconvinced that OpenPGP fingerprints need to be collision-resistant.
They certainly need to be able to resist preimage attacks, but i haven't
seen any convincing attacks that make me think collision resistance is
an issue.

Here's the recent GnuPG discussion:

 http://thread.gmane.org/gmane.comp.encryption.gpg.devel/17366/focus=17389

And here's earlier discussion from Daniel Nagy and myself on this list
suggesting that collision-resistance is an issue for fingerprints:

 http://thread.gmane.org/gmane.ietf.openpgp/6012/focus=6013
 http://thread.gmane.org/gmane.ietf.openpgp/7115/focus=7126

If anyone disagrees with this analysis, i would be interested in hearing
how failed collision-resistance of the fingerprint mechanism could lead
to practical attacks in OpenPGP.

> publish SHA-3 and the OIDs assigned.

thanks for doing this, i think this will be a useful contribution.

Regards,

	--dkg

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 03 Jan 2013 15:30:14 -0800

> Except that SHA-2 is already in use and has hardware support.
... but there is no reason why SHA-3 will not optimized in the future. 
BTW, which SHA-2 friendly CPU feature we are talking about? ( other than 
Intel's plans to add cycle shift )

In any case, please note that we are talking about hashing the key 
material and thus the performance of the hash algorithm doesn't matter.

My preference for SHA-3 is to satisfy the concerns of algorithm agility. 
I argue for a hardcoded algorithm, and thus the natural choice is the 
strongest of SHA that will be future-proof for regulatory compliance.

I would also be OK to do SHA-2 + SHA-3, TLS style, to be future proof, 
but this seems too paranoid.

> than SHA-1?  I don't know.

The current attacks tell us so. Instead of 80 bit is security (birthday 
bounds) SHA-1 is listed as 51 bits on 
http://en.wikipedia.org/wiki/Message_digest. The number can continue to 
go lower.

But I also think that it makes sense to standardise on larger than 160 
bits of the fingerprint as a UI feature (somewhere between 160 and 384 
bits).

> change more than just this.

While every key inherently will have two fingerprints -- old and new 
(and I was saying don't make it worse with hash variations) -- the 
software should probably select to display only one of them with an 
option to change it.

We might let users enter the fingerprint as before but then use it for 
dual purpose as SHA-1 or new one (as opposed to using an explicit type). 
At some point in the future one might start flagging links achieved with 
the old fingerprint. Features flags will be helpful for this (i.e. I 
generate a key that I want to be known only by its new fingerprint; I 
put this fact into Features; don't match this key by the old fingerprint)

> BTW, what about re-establishing the OpenPGP WG?

I suppose it's a matter of how much work there is in the OpenPGP.

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 03 Jan 2013 16:01:59 -0800

On 01/03/2013 03:08 PM, Daniel Kahn Gillmor wrote:
...
...
...

Key fingerprints can be designed to be cryptographically strong, so that 
it is infeasible to forge them / find collisions for anybody. The 
overall system is stronger if we can rely on this stronger assertion.

OpenPGP is a format on the wire. I need to show only one vulnerable 
hypothetical OpenPGP system to prove that Daniel is wrong.

Let's say I have a server that manages a domain of user, each have their 
own key, one at a time. Users can update their keys. They cannot remove 
keys (other than updating them). The server logs protocol actions and it 
uses key fingerprints to log changed to keys. The server decide to log 
the whole key on the key material change event, which it identifies by 
the change in the key fingerprint. Seems like a reasonable and secure 
system at first sight.

I am a malicious member of that domain. I create two keys with the same 
fingerprint. Now I can repudiate my document signatures. Document 
signatures will refer to either of my keys with the same 8 byte KeyID. 
Server logs will have the same 160 bit fingerprints. I can replace my 
first key on the server with another and no logs will tell that I have 
updated the key. This will invalidate documents signed with my first key.

There is an easy remedy to this problem, but it will essentially mean 
that we don't trust the key fingerprint and diligently log whole keys. 
This means that we moved away from relying on collision resistance of 
the fingerprint.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 03 Jan 2013 23:27:20 -0500

This sounds like a system that explicitly ignores the warning in RFC 4880:

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

https://tools.ietf.org/html/rfc4880#page-72

The purpose of a fingerprint is for one human to be able to securely
verify the key of another peer.  This means that they must be short
enough for humans to understand them, and they must resist preimage
attacks (no one should be able to come up with a new key that matches an
arbitrary fingerprint).

If your argument is "existing tools misuse fingerprints (and even
keyids) and treat them as unique identifiers when they should not" then
i'd have to agree with you.  We need to fix those tools.  If the
argument is "fingerprints need to be resistant to collision attacks, not
just preimage attacks because we want to be able to use them as unique
identifiers in cases like this that would allow for repudiation of
previously-signed messages where the earlier key was not properly
stored", then you're effectively doubling the length of the required
fingerprint for the sake of some problem better solved another way.  i
think that would defeat (or at least severely damage) the ability for
human beings to actually cognitively process the fingerprint.

It's arguably too difficult already for humans to accurately compare or
transcribe 160 bits of high-entropy data.  Asking them to compare or
transcribe larger fingerprints seems likely to result in operator error.

	--dkg

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 03 Jan 2013 21:35:48 -0800

> https://tools.ietf.org/html/rfc4880#page-72

Sure, shorter fingerprints are good for humans...

On the other hand, my reading of the above quote is that this is a 
general warning about the 1/2^80 probability of a collision.

SHA-1 collision at 1/2^51 probability is a different story.

I wouldn't assume that real-world OpenPGP systems today are written to 
handle collisions in 20 byte OpenPGP fingerprints. That would "never" 
happen in practice.

Furthermore, I think there are probably no systems that deal with
KeyID collisions either. KeyID collisions have a chance to happen at a 
rate of 1/2^32 -- readily observable. I am guessing that the problem is 
currently avoided by application design, which eliminates scenarios of 
large number of messages signed/encrypted by different users, all in one 
pile. Usually a metadata like UserIDs, SMTP headers, etc, is used first 
to filter messages/locate keys.

It seems to me that instead of fixing the software to handle fingerprint 
collisions, I would consider diverting this effort to introduce the new 
fingerprint instead.

> attacks (no one should be able to come up with a new key that matches an

RFC4880 also specifies how fingerprints are stored to identify revokers, 
and they are a truncated to produce keyIDs. The point is that it's nice 
to have a single general-purpose method without flaws.

> human beings to actually cognitively process the fingerprint.

I am saying that let's pack as much security bits into fingerprints as 
the current state of the art allows. 256 bit fingerprint should mean at 
least 128 bit security under any scenario, regardless of higher-level 
protocols. This adds clarity to security properties of the system and 
gets rid of (almost) non-compliant use of SHA-1.

> transcribe larger fingerprints seems likely to result in operator error.

I will guess that humans are unlikely to compares full fingerprints 
anyway. They start from (hopefully :-)) the same end of hex digits and 
stop somewhere along the way. If fingerprints to become 256 bit long, 
this may turn out to be unnoticeable.

---

From: ianG <[email-masked]>
Date: Fri, 04 Jan 2013 08:56:50 +0300

Some comments...

> but this seems too paranoid.

It also seems non-sensical, the notion that anyone is likely to trash 
SHA-2 or SHA-3 over the next decade has been well and truly trounced.  I 
don't think we really have to worry about the hardness of this 
particular application overly muchly.

Meanwhile, spending time on that means they weren't spending time on 
other more important things.  Maybe a warning to us!

> bits of the fingerprint as a UI feature (somewhere between 160 and 384

If the purpose of the fingerprint is *only* for human comparisons, then 
it would seem that this is a marginal improvement.  But if it falls out 
of other decisions, oh well, maybe.

> software should probably select to display only one of them with an

It doesn't need to be so.  If the switch to some other algorithm is 
organised in alignment with a new key type, then it can roll over with 
the new key type.

(Whether this is overall better or worse depends...)

> put this fact into Features; don't match this key by the old fingerprint)

those Features seem like User and Code Confusion :)

iang

---

From: ianG <[email-masked]>
Date: Fri, 04 Jan 2013 09:25:48 +0300

> That's the way I'd go, as it's future-proofed.

If we have to have hash agility, I agree that's a good way to do it.

Alternatively we can do OIDs in which case we will generate arguments, 
external dependencies and work for ourselves for generations -- over on 
another list some were arguing recently about whether Taiwan was allowed 
to use this OID or that OID for their root key, Taiwan being one of 
those not-a-countries, and everyone arguing being not-those-authorities.

Hence my earlier question - has anyone allocated the OpenPGP numbers for 
Keccak as yet?  The reason I asked is because I stumbled on the code 
last week and thought what a fine idea it would be to at least prepare 
the way....  Strawman?

   SHA3-224         4        12
   SHA3-256         5        13
   SHA3-384         6        14
   SHA3-512         7        15

Strawman?  I'm not sure why there is a gap 4-7 in rfc4880.  Are there 
any spots already allocated?

Another question, back on the fingerprints.  If we end up doing a 
hash-agile fingerprint, how does the algorithm number get laid out by 
the users on their business cards?

E.g., can we agree on a one byte number, values 0 to 7F, with leading 
bit reserved for future escape valve?

Then, if it is to be written out, this would mean a "new-style 
fingerprint" is always an odd number of bytes.  Could we agree on a 
stylistic convention?  Something like:

   7F-- AB01 CD23 EF45 ...

Just thinking aloud.  Are there any other practical ramifications of 
going to an agile fingerprint?

iang

---

From: ianG <[email-masked]>
Date: Fri, 04 Jan 2013 09:40:27 +0300

> publish SHA-3 and the OIDs assigned.

Post?  I'm extra happy if the OIDs are missing ;)

iang

---

From: Christian Aistleitner <[email-masked]>
Date: Fri, 4 Jan 2013 11:53:29 +0100

Hi Andrey,

On Thu, Jan 03, 2013 at 03:30:14PM -0800, Andrey Jivsov wrote:
> Instead of 80 bit is security (birthday 
> http://en.wikipedia.org/wiki/Message_digest.

Since you mention the 51 bits part again and again ...

Do you have any data / research underpinning this 51 (Besides
Wikipedia)?

After all, the cited Wikipedia page links to the retracted variant of
an article :-(

Otherwise, the best /theoretical/ result that I know of is just
above 60.

Best regards,
Christian

-- 
---- quelltextlich e.U. ---- \\ ---- Christian Aistleitner ----
                           Companies' registry: 360296y in Linz
Christian Aistleitner
Gruendbergstrasze 65a        Email:  [email-masked]
4040 Linz, Austria           Phone:          +43 732 / 26 95 63
                             Fax:            +43 732 / 26 95 63
                             Homepage: http://quelltextlich.at/
---------------------------------------------------------------

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 04 Jan 2013 11:56:36 -0800

> Otherwise, the best /theoretical/ result that I know of is just

It looks like this is from the paper "Classification and Generation of 
Disturbance Vectors for Collision Attacks against SHA-1"
published in 2011 in Designs, Codes and Cryptography
http://link.springer.com/article/10.1007%2Fs10623-010-9458-9?LI=true
with 27 citations in Google scholar. There you can find a dozen of 
different copies (or minor revisions?) of the paper and Wikipedia links 
one of them.

Should we rather say that the _practical_ value is about 60 (it's not to 
say that 2^60 is that practical, but that there is an expensive but an 
actionable attack plan). The following post leads the reader to the 
algorithm : 
http://www.schneier.com/blog/archives/2012/10/when_will_we_se.html

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 04 Jan 2013 12:55:10 -0800

On 01/03/2013 10:25 PM, ianG wrote:
...
> any spots already allocated?

One point I wanted bring up here based on the draft that I wrote last 
year is that let's think for a moment about the usefulness of the SHA3-224.

I would like to see an argument for it. Algorithms like DSA/ECDSA are 
capable to deal with hash truncation or padding. RSA mod has sufficient 
space to always use SHA3-512.

The question is especially relevant if you familiarize yourself with the 
Keccak. Keccak is basically a single hash algorithm which output is 
truncated to 256, 384, 512, etc bits. The only difference between 
SHA3-256 and SHA3-512, for example, is one integer used in the internal 
loop.

You can always go with stronger security. Who are those people who would 
not be OK with SHA3-256 but are happy with SHA3-224 ? Why can't they use 
shorter public keys (to solve space concerns?) ?

---

From: jbar <[email-masked]>
Date: Fri, 4 Jan 2013 22:00:26 +0100

On Fri, 04 Jan 2013 11:56:36 -0800

> http://www.schneier.com/blog/archives/2012/10/when_will_we_se.html

In either case, humans are less than 2^33 todays and this number should not increase so much in the next decades. Even if each living human use OpenPGP and more than a dozen of keys, we are far from 2^60 or 2^51...

(even if we consider also the life expectancy)

regards,
-- 
jbar <[email-masked]>

---

From: Christian Aistleitner <[email-masked]>
Date: Fri, 4 Jan 2013 23:21:25 +0100

Hi Andrey,

On Fri, Jan 04, 2013 at 11:56:36AM -0800, Andrey Jivsov wrote:
> [...]

I guess you are aware of the fact that in recent variants of the
article, the 51 is gone and that there is a reason why I wrote
“retracted variant” in my original mail :-)

> Should we rather say that the _practical_ value is about 60 [...]

Practical has more than just one meaning, just as theoretical :-)
As the post you reference only says

  If Stevens' attack of $2^{60}$ SHA-1 operations serves as the
  baseline [...]

and does not say that “Stevens' attack” is practical (or “practical”
in what sense), I am convinced you have read in Stevens' research to
underpin your claim. For example you might have come across Stevens'
2012 PhD thesis and have read passages as

  [...] and this chosen-prefix collision attack against SHA-1 remains a
  theoretical attack.

in section 7.7.3 (but that's somewhat out of context), or more
general statements as

  [...] even though no practical collision attacks against SHA-1 or
  actual colliding messages are known yet.

from section 8.4.

But be things as they may, if you know better than Stevens himself and
can make his results even more practical, please step up and share
your work.

All the best,
Christian

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 04 Jan 2013 17:25:16 -0500

On 01/04/2013 04:00 PM, jbar wrote:
> On Fri, 04 Jan 2013 11:56:36 -0800  Andrey Jivsov <[email-masked]> wrote:

I think you're trying to analyze this in a scenario where you want to
establish equitable sharing of limited resources among cooperating peers.

This is not the scenario the OpenPGP specification needs to concern
itself with.  Rather, the OpenPGP specification needs to be concerned
with providing cryptographically strong guarantees in the face of
malicious and well-funded adversaries.

That is, it's not enough to say that we have enough to go around.  We
need to show that the search space is large enough (and the digest
strong enough) that someone can't come up with a new key that matches
the fingerprint of your key, even if they have millions of dollars and
powerful computers at their disposal.

Regards,

	--dkg

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 04 Jan 2013 16:06:03 -0800

We are talking about the realm of (single) DES security here (i.e. ~ 
DES-X variant) and one will need all the additional bits. The question 
of how much can we actually get beyond DES may not be so important in 
the context of this thread.

Recall that my initial post doesn't claim any immediate attack on SHA-1 
or a specific weakness of OpenPGP. I am looking for a solution that we 
can implement in a few years to move to the full 128 bit security (or 
closer to it). This means that we need to have a method now so that we 
can begin to slowly integrate it.

IMO the upgrade can be done "cheaply", without disruption, so my thought 
is why not do it anyway?

---

From: ianG <[email-masked]>
Date: Sat, 05 Jan 2013 22:38:41 +0300

> overall system is stronger if we can rely on this stronger assertion.

My understanding is that Key Fingerprints are purposed for humans. 
RFC4880 says:

    Note that it is possible for there to be collisions of Key IDs -- two
    different keys with the same Key ID.  Note that there is a much
    smaller, but still non-zero, probability that two different keys have
    the same fingerprint.

Although see 5.2.3.15 & 5.5.2 for interesting comments.  Let's ask for 
consensus on this point:

   Are fingerprints cryptographically secure?

   Or are they convenient human introduction handles?

> hypothetical OpenPGP system to prove that Daniel is wrong.

Fingerprints aren't really for the wire, and if you use them for the 
wire, you're exercising your right to develop your own security model 
and threat model.  For my money - don't do that.

> own key, one at a time.

Note, a key can have multiple fingerprints.

> Users can update their keys. They cannot remove

Right.  That's what you should do anyway.  If you are to rely on the 
digsig for any length of time, you should escrow the full public key.

> This means that we moved away from relying on collision resistance of

OpenPGP is primarily a wire format, a communication tool, and has 
steered clear of how you might store the data, leaving this up to the 
designer.  The fingerprint is clearly a useful index, but is not really 
purposed to be a cryptographically secure index - that's more left for 
the designer.  E.g., you can have the same key with 2 fingerprints:

    Also note that if V3 and V4 format keys share the same RSA key
    material, they will have different Key IDs as well as different
    fingerprints.

In more particularity, a document signing system should store the keys 
in or near the document [0].  Otherwise you have the problem of lost 
keys, being a serious risk for any long-lived system.  And, if you've 
got the keys, you don't care what indexing technique you use.

iang

[0] ok, so I may be biased.  This is what I recommend and do:
http://iang.org/papers/ricardian_contract.html

---

From: Jon Callas <[email-masked]>
Date: Sat, 5 Jan 2013 12:00:16 -0800

I think that along with just parameterizing a fingerprint, it's best not to assume that they are unique. Obviously, there are a few places where we assume they are, and those are the flies in that particular ointment (for example, designated revokers). But that's not hard to deal with. It's not (in general) exposed to humans, so you can make it be a hash as long as you want.

For human use, any reasonable hash function will do, and that even includes SHA-1. (While it has been estimated that one can construct a collision with 2^51 work, that's not the same as constructing a second-preimage collision.) For any crypto operation, a fingerprint collision isn't going to lead to crypto interoperability -- and this is why the 64-bit key id isn't a problem.

	Jon

---

From: Werner Koch <[email-masked]>
Date: Sun, 06 Jan 2013 00:04:29 +0100

> and threat model.  For my money - don't do that.

The fingerprint is used for an revocation key (5.2.3.15).  However, your
policy may simply disallow the use of a revocation key if this is a
threat to you.

Shalom-Salam,

   Werner

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sat, 05 Jan 2013 18:22:04 -0500

> policy may simply disallow the use of a revocation key if this is a

iirc, there was a rough consensus within this working group that this
was probably a mistake in RFC 4880, and any future revision of the draft
should place the full key material into the revocation key subpacket
instead of the key's fingerprint.

	--dkg

---

From: Jon Callas <[email-masked]>
Date: Sat, 5 Jan 2013 19:19:43 -0800

> instead of the key's fingerprint.

I was about to comment that if we move on shifting to ECC keys as per Andrey's work on them, we could just about eliminate fingerprints and just use the keys.

Also, the point compression patent expired last year.

	Jon

---

From: Andrey Jivsov <[email-masked]>
Date: Sat, 05 Jan 2013 22:19:28 -0800

On 01/05/2013 11:38 AM, ianG wrote:
...
>    Or are they convenient human introduction handles?

I can live with the interpretation of RFC 4880 that implies that 
fingerprints are not cryptographically secure.

IMO, however, it would be beneficial if they were secure at the birthday 
boundary size.

I know that there were suggestions by multiple people to store complete 
keys. The problems are:
* keys are volatile; as a developer I want, at least internally in my 
software, a method to ID the key material; key material is often reused 
and traverses X.509 and OpenPGP world
* it's a convenience when the ID is of fixed size (think about database 
tables, software memory allocations, etc)

There is an objective need to ID the key material with a hash. I think 
at the very least we should spec the algorithm in an e-mail on this 
list. It would even be better if this algorithm was supported across 
applications, so that the IDs are portable.

---

From: Andrey Jivsov <[email-masked]>
Date: Sat, 05 Jan 2013 22:28:43 -0800

> Also, the point compression patent expired last year.

BTW, here is my current contribution to the process of making OpenPGP 
data structures most compact: 
http://tools.ietf.org/html/draft-jivsov-ecc-compact-00 . It's a generic 
format that can be used anywhere: X.509, DNS, etc. Realistically, I hope 
that designers of new protocols at IETF will consider this (more 
superior to SEC1 :-)) proposal...

Back to OpenPGP, there is certainly a need to have most compact keys and 
messages, and this is one of the advantages of the ECC keys. It's 
remarkable that one can have a 32 byte public key of AES-128 strength 
and my proposal lays the groundwork to make this happen in OpenPGP (v.s. 
the current 65 bytes).

Given that OpenPGP messages are very compact by design, everything fits 
nicely together.

---

From: Andrey Jivsov <[email-masked]>
Date: Sat, 05 Jan 2013 22:50:42 -0800

> shorter public keys (to solve space concerns?) ?

I think I found some support to my suggestion in the latest SHA2 spec: 
FIPS 180-4 "Secure Hash Standard (SHS)":

> 7.  TRUNCATION OF A MESSAGE DIGEST
> Some application may require a hash function with a message digest length different than those
> provided by the hash functions in this Standard. In such cases, a truncated message digest may be
> used, whereby a hash function with a larger message digest length is applied to the data to be
> hashed, and the resulting message digest is truncated by selecting an appropriate number of the
> leftmost bits. For guidelines on choosing the length of the truncated message digest and
> information about its security implications for the cryptographic application that uses it, see SP
> 800-107 [SP 800-107].

In SHA2 SHA-224 is the SHA-256 with different IV. NIST was worrying 
about some theoretical concerns with examples that show non-uniform 
distribution of the SHA2 hash output (see 
http://csrc.nist.gov/groups/ST/hash/documents/Kelsey_Truncation.pdf)

Given that there are no IVs in Keccak, the section 7 of FIPS 180-4 
allows the truncation, and the truncation should be happening anyway in 
practice when you use mismatched weaker DSA keys with stronger hashes, 
benefits of SHA3-224 are even harder to see.

---

From: Werner Koch <[email-masked]>
Date: Sun, 06 Jan 2013 13:23:10 +0100

> Also, the point compression patent expired last year.

Oh really.  That would be great news.  No other patents to the same
effect?

Salam-Shalom,

   Werner

---

From: Werner Koch <[email-masked]>
Date: Sun, 06 Jan 2013 13:25:04 +0100

On Sun,  6 Jan 2013 07:28, [email-masked] said:

> Given that OpenPGP messages are very compact by design, everything
> fits nicely together.

Finally Phils preference for saving every little bit turns out be an
advantage :-).

Shalom-Salam,

   Werner

---

From: Bill Frantz <[email-masked]>
Date: Sun, 6 Jan 2013 09:29:10 -0800

On 1/5/13 at 10:19 PM, [email-masked] (Andrey Jivsov) wrote:

>There is an objective need to ID the key material with a hash. 
>I think at the very least we should spec the algorithm in an 
>e-mail on this list. It would even be better if this algorithm 
>was supported across applications, so that the IDs are portable.

I hope that anything which affects program interoperability or 
escapes to the user would be specified in a more permanent way 
than an email to a list. An informational RFC might be the easy choice.

Cheers - Bill

---------------------------------------------------------------------------
Bill Frantz        |"We used to quip that "password" is the most common
408-356-8506       | password. Now it's 'password1.' Who said 
users haven't
www.pwpconsult.com | learned anything about security?" -- Bruce Schneier

---

From: Jon Callas <[email-masked]>
Date: Sun, 6 Jan 2013 11:10:23 -0800

> Oh really.  That would be great news.  No other patents to the same

The ECC patents are starting to expire en masse. It started last year, and over the next year or two most of the really annoying ones are going. Others, like MQV will take longer. But the IP reasons to avoid ECC are going quickly, especially if you stick to the Suite B curves, as Andrey did with his draft. 

Jon

---

From: Nicholas Cole <[email-masked]>
Date: Mon, 7 Jan 2013 07:20:22 +0000

> ever did this in the last 20 years.

Yes.  And it is also important that there is a way to 'uniquely' (granted
the *very* small chance of a collision - I think there has been only one
possible collision with SHA-1 fingerprints reported on the gnupg list)
identify keys to other programs.  I suspect that a lot of programs using
gnupg and other implementations expect the fingerprint to be unique.  There
does have to be a reliable way to refer to a particular key.

So fingerprints are compared by humans, but they are also important for
computers too - and probably used more by computers than by humans.  I
don't see the sense in adopting a truncated standard.  Any new fingerprint
is going to be more tedious than comparing SHA-1, but that's the price to
be paid for security.

I suppose that humans will start relying more on the key-id.  I assume that
any new standard would adopt a more collision-resistant key-id.

N.

---

From: ianG <[email-masked]>
Date: Mon, 07 Jan 2013 11:30:23 +0300

Part of the problem here is that claiming uniqueness to a cryptographic 
level is harder to do than say.  Typically if we are dealing with larger 
keys and much more aggressive attackers, we'd want to up the size of the 
hash to larger SHA2/3s.  Which means that ordinary users with their 
human comparison function are going to be left behind.  Time factors 
also make us too conservative.

For about 10-15 years we had relative peace with this question because 
we had a strong single SHA1 that survived well.  That is unusual in the 
history of cryptographic computing, and we can see the reflection of 
this low expectation in later algorithms - AES, SHA2 and SHA3 all offer 
a range of strengths.  So perhaps we have been lulled into a sense that 
we can do two or more not-so-complementary things with one algorithm.

I cannot see how we can totally mix the unique programmatic identifier 
with the fingerprint function with a single fixed hash.  Basically, 
humans can be relied upon to never go beyond the 160 bit length of SHA1, 
and even the dedicated struggle to get that on their business card.  80 
bits is far more sensible.

So in this sense, we seem to be facing two possible directions:  Stick 
with SHA1, and have the fingerprint for people only.  If programs want 
more, it is up to them to extract out the key and generate their own 
unique identifier.  I do this all the time in my code, and it isn't a 
bother.  There are benefits in doing the right thing up front.

Alternatively, if we combine these roles, what we might need then is a 
more agile *length* but one fixed algorithm.  Right now we have KeyID, 
Fingerprint and something else I forget - 2 or 3 lengths extracted from 
the same algorithm.  To pursue that, we could simply stick in the 
longest biggest baddest Keccak and write up a process for truncation, 
for different lengths.  Then match that up to the key sizes.

(Or, option 3 - as Jon points out, ECC is looking good, and just use the 
key as is.  That has many advantages.)

iang

On 7/01/13 10:20 AM, Nicholas Cole wrote:
>
>
>
> On Thu, Jan 3, 2013 at 10:54 PM, Werner Koch <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>     On Thu,  3 Jan 2013 20:06, [email-masked]
>     <mailto:[email-masked]> said:
>
>
> Yes.  And it is also important that there is a way to 'uniquely'
> (granted the *very* small chance of a collision - I think there has been
> only one possible collision with SHA-1 fingerprints reported on the
> gnupg list) identify keys to other programs.  I suspect that a lot of
> programs using gnupg and other implementations expect the fingerprint to
> be unique.  There does have to be a reliable way to refer to a
> particular key.
>
> don't see the sense in adopting a truncated standard.  Any new
> fingerprint is going to be more tedious than comparing SHA-1, but that's
> the price to be paid for security.
>
> I suppose that humans will start relying more on the key-id.  I assume
> that any new standard would adopt a more collision-resistant key-id.
>
> N.
>
>
>
>