Subject: Re: [openpgp] Followup on fingerprints

From: Derek Atkins <[email-masked]>
Date: Mon, 03 Aug 2015 11:08:04 -0400

Phillip Hallam-Baker <[email-masked]> writes:

> On Fri, Jul 31, 2015 at 9:28 AM, Derek Atkins <[email-masked]> wrote:
>
>     Daniel Kahn Gillmor <[email-masked]> writes:
>    
>     >> At this point, any attempt to hold Mallet accountable is going to have
>     to
>     >> rely on a human examining the logs and working out that Mallet must have
>     >> generated the malicious pair of keys. There is going to be no way to
>     unwind
>     >> the thing automatically.
>    
>     Why?  M1 and M2 are completely different fingerprints, unless you're
>     assuming that the x's are the same.  If the x's are the same that means
>     that Mallet has performed a 2^50 level attack to get 100 bits to match!
>     How long and how much energy does Mallet have to do this?  It's
>     certainly not something s/he is going to do over a long weekend!
>
> Not with RSA keys. With ECC keys, different matter entirely.

Even if you could do 30,000,000 ECC key generations per second (I think
my laptop can do about 3,000-10,000 -- I'm not sure how to measure that
beyond running an openssl speed test), and also assuming the SHA hash to
compute the fingerprint is "free", to do 2^50 keygen + sha computations
would still take 37,529,996 seconds or 434 days, which is over a year!
Remember, the fingerprint is over the public key, so you still have to
actually perform the ECC g^x operation for each trial.

So no, this is not something Mallet is going to be able to do over a
weekend without expending a LOT of effort and cost.  I guess if they had
access to a few hundred really beefy machines (and the electricity to
power them) they might be able to accomplish this feat.  So sure, maybe
a large corporation or gov't agency could perform this kind of Mallet
attack, but generally not some teenager sitting in their basement.

Maybe in a decade or two this will be feasible to a singleton.

This of course is still based on your (rather forced) 100-bit truncated
hash concept.  If applications use the full 160-bit fingerprint (or more
if we migrate up to a larger hash) then a 2^80 attack would still be out
of reach.

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Gregory Maxwell <[email-masked]>
Date: Mon, 3 Aug 2015 16:59:11 +0000

> actually perform the ECC g^x operation for each trial.

Take care to not confuse what you would do with what an attacker _must_ do.

For each new key to generate the attacker can perform only a single
addition of G or a doubling (whichever is faster for the curve in
question), then a conversion to affine (which is nearly free--
marginally, ~one field multiply-- if done in a batch).

E.g. You compute,
P_0 = xG
P_1 = P_0 + G  (x_1 = x_0 + 1)
P_2 = P_1 + G  (x_2 = x_1 + 1)
...

There are even faster techniques available for some curves.

If software for this doesn't run in the rough ballpark of a million
per second on a current gen laptop/desktop or 10 million/sec on a GPU
even on a fairly generic curve, it's probably completely naieve.

---

From: "Derek Atkins" <[email-masked]>
Date: Mon, 3 Aug 2015 13:20:08 -0400

> even on a fairly generic curve, it's probably completely naieve.

Luckily my computations (which you unfortunately cut out) were based on 30
million attempts per second, so my results (the attack taking over a year)
is still correct!  Indeed, your numbers are still 3x slower than my
computation estimates.

-derek

---

From: Peter Pentchev <[email-masked]>
Date: Mon, 3 Aug 2015 20:32:31 +0300

> is still correct!  Indeed, your numbers are still 3x slower than my

Um, I believe that the point is that Mallory doesn't *need* to brute-force
anything to create two keys with almost-identical hashes.  ICBW, but I think
that the idea is that Mallory, in the process of creating the first key,
is in possession of some intermediate information that enables him to create
a related key much cheaper, with a single run.

G'luck,
Peter

-- 
Peter Pentchev  [email-masked] [email-masked] [email-masked]
PGP key:        http://people.FreeBSD.org/~roam/roam.key.asc
Key fingerprint 2EE7 A7A5 17FC 124C F115  C354 651E EFB0 2527 DF13

---

From: "Derek Atkins" <[email-masked]>
Date: Mon, 3 Aug 2015 13:47:37 -0400

> a related key much cheaper, with a single run.

They do still need to brute-force -- they still need to find a hash
collision.  Whether they do this randomly or forcing it still requires on
the order of 2^50 operations (assuming they want to match 100 bits of a
hash).

My previous statements assumed the hashing was free, but we all know
that's not true.  On my laptop I can perform on the order of 3 to 5
million SHA operations per second (3.4 SHA256, and 4.6 SHA1) on 16 bytes
of data.  So we're still well within the 30 million trials per second. 
But how about this, I'll be nice and give you yet another order of
magnitude to 300 million attempts per second.  That STILL limits you to
~46 days to find a 100-bit collision.  But the data being hashed is more
than 16 bytes so I still think it's going to be closer to 30 vs 300
million attempts per second.

Thanks,

-derek

> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 3 Aug 2015 16:22:15 -0400

> is still correct!  Indeed, your numbers are still 3x slower than my

Your original assertion was broken. I don't think it very likely that
someone is going to spend more than a machine year to generate a vanity key
unless they can get someone else to pay for the time.

A hundred machine years for creating a key collision attack is completely
viable.

Also when we are talking about PGP Key fingerprint, the fingerprint is over
the key binding and not just the key and so it is malleable.

I can well imagine someone making use of all that Bitcoin hardware for some
mischief. Hence a reason to go for SHA-2-512.

Again, this is only a security consideration that has to be noted.

---

From: Vincent Breitmoser <[email-masked]>
Date: Tue, 04 Aug 2015 02:38:50 +0200

Maybe I missed an answer to this, but could someone please explain what
the point of finding a collision on a pgp fingerprint is, and why we
need to consider it as an attack scenario in the first plce?

Let's say you spent the (cpu) time, and you now have two different pgp
keys with the same fingerprint.  What do you do with those?

 - V

---

From: Vincent Breitmoser <[email-masked]>
Date: Tue, 04 Aug 2015 04:42:41 +0200

> Maybe I missed an answer to this, but could someone please explain
> what the point of finding a collision on a pgp fingerprint is, and
> why we need to consider it as an attack scenario in the first plce?

I could have been more clear here: I saw the previous answer, but the
discussion went into the direction of collision feasibility without
really answering dkg's doubts about whether this was even a reasonable
scenario, and I'm not convinced it is.

> Mallet joins an open source project which only takes the first 100
> bits for the fingerprint. He uploads the key for M1 to a keyserver.
>
> He then commits a large number of malicious patches using M2 for
> authentication. These are all authenticated against his public key M2
> when he does the commit but the repository uses the key sent in band
> and does not keep the key for later verification.

So the premise here is:
- a user uploads his key, but it is not actually used other than for its
  fingerprint
- at authentication time, a public key sent by the user is used to check
  signatures, which is only checked to have the same fingerprint as the
  uploaded one
- the implementation uses truncated fingerprints for this

> to rely on a human examining the logs and working out that Mallet must
> have generated the malicious pair of keys. There is going to be no way
> to unwind the thing automatically.

And the actual attack is "slightly weaker non-repudiation"?

 - V

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 3 Aug 2015 23:32:15 -0400

> And the actual attack is "slightly weaker non-repudiation"?

The attack is to confuse someone's perl hack into letting someone get away
with something they should not.

---

From: Werner Koch <[email-masked]>
Date: Tue, 04 Aug 2015 08:44:27 +0200

> And the actual attack is "slightly weaker non-repudiation"?

... when using a truncated fingerprint.

Why should anyone truncate a fingerprint from 20 bytes to 13 bytes?
This is an arbitrary value in between the known weak 8 byte keyids and
the full 20 byte fingerprints for which we expect that in our lifetime
collisions can be created.

Shalom-Salam,

   Werner

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

---

From: Nicholas Cole <[email-masked]>
Date: Tue, 4 Aug 2015 09:05:03 +0100

On Tuesday, 4 August 2015, Werner Koch <[email-masked]> wrote:

> collisions can be

I'm really struggling to follow what is going on with this whole
discussion!  Fingerprints need to be robust enough that creating aritrary
collisions is not feasible. That has always been central to OpenPGP.  If
that creates headaches for user interfaces then we will have to find ways
to deal with that, but that is a separate discussion.

I thought that there were some well established, secure as far as anyone
knows, hash algorithms. We've many years experience of the problems of
including or not including various extra bits of information along with the
key material itself, so doesn't the WG just need to pick one of the
candidate algorithms and have done with it?

---

From: Derek Atkins <[email-masked]>
Date: Tue, 04 Aug 2015 09:08:08 -0400

Phillip Hallam-Baker <[email-masked]> writes:

> Your original assertion was broken. I don't think it very likely that someone
> is going to spend more than a machine year to generate a vanity key unless they
> can get someone else to pay for the time.

Phill, it was *your* proposal that I was talking to, Mallet creating
keys M1 and M2 to attack some open source project using PGP Signatures.
So thank you for acknowledging that your original assertion was broken!
My point was that particular notion isn't viable; nobody is going to
expend that much effort just to be able to spoof a broken source control
system.  And moreover, a non-broken system (that uses the full
fingerprint) is still out of reach even for stronger adversaries.

> A hundred machine years for creating a key collision attack is completely

It's only a hundred machine years for a 100-bit collision.  A 160-bit
collision is much much further out!

> Also when we are talking about PGP Key fingerprint, the fingerprint is over the
> key binding and not just the key and so it is malleable. 

I don't see how that helps (today) with SHA1 or SHA2.

-derek

---

From: Derek Atkins <[email-masked]>
Date: Tue, 04 Aug 2015 09:16:52 -0400

Nicholas Cole <[email-masked]> writes:

> I'm really struggling to follow what is going on with this whole discussion! 
> Fingerprints need to be robust enough that creating aritrary collisions is not
> feasible. That has always been central to OpenPGP.  If that creates headaches
> for user interfaces then we will have to find ways to deal with that, but that
> is a separate discussion. 
>
> including or not including various extra bits of information along with the key
> material itself, so doesn't the WG just need to pick one of the candidate
> algorithms and have done with it?  

Every hash algorithm is going to have collisions.  In an ideal hash you
can find a collision in 2^(N/2) trials where N is the number of bits in
the hash.  If you truncate the hash then that reduces N.  In non-ideal
hashes it's less effort.

-derek
-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/    PP-ASEL-IA     N1NWH
       [email-masked]                        PGP key available

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 4 Aug 2015 10:49:13 -0400

On Tue, Aug 4, 2015 at 9:08 AM, Derek Atkins <[email-masked]> wrote:

> someone

That is not a vanity fingerprint, it is an attack. A vanity fingerprint
would be doing a brute force search for a key whose fingerprint begins
MINIO-Nxxxx-xxxxx-xxxxx-xxxxx

Spending a hundred computer years to insert malware into an open source
project is a much more probable attack.

> fingerprint) is still out of reach even for stronger adversaries.

The moral here is to use a sufficiently long fingerprint. But the point is
that the fingerprint is indeed subject to birthday attack under rare
circumstances.

> collision is much much further out!

Yes, but if you didn't have to worry about a birthday attack at all, 80
bits would be acceptable by that metric.

The point is that 80 bits is sufficient for a KeyID type use but a
fingerprint should be at least 160 bits. 100/125 and 256 offer some safety
margin.

> I don't see how that helps (today) with SHA1 or SHA2.

If you are doing RSA, it greatly reduces the cost of a collision attack as
you can avoid the need to generate new keypairs on each trial. But I don't
think that is important as we are going to ECC in the near future anyway.

---

From: Derek Atkins <[email-masked]>
Date: Tue, 04 Aug 2015 11:48:08 -0400

Phillip Hallam-Baker <[email-masked]> writes:

> That is not a vanity fingerprint, it is an attack. A vanity fingerprint would
> be doing a brute force search for a key whose fingerprint begins

The "MINIO-Nxxxx-..." vanity fingerprint issue is yet another issue you
brought up, which is still different than this one.  Yes, a vanity key
fingerprint is definitely less work because there are many fewer bits
that you care about.  There's really no way to disallow it that I can
see, but we should definitely remind people to always check the full
fingerprint.

> Spending a hundred computer years to insert malware into an open source project
> is a much more probable attack.

I think you're mis-remembering your attack setup.  The hundred
computer-years effort is for someone to generate two keys that have the
same matching truncated-to-100-bits fingerprint to use in a broken
source code control system that only checks the truncated hash.  But
it's more than that; Mallet has to be trusted to actually push data into
the source repository in the first place.

For your attack scenario to succeed Mallet needs to generate both keys
prior to being added to the project and only then will he be able to
surrepticiously add code.  Of course Mallet needs to have been trusted
enough to get M1 added to the authorized commiters list first!  My point
is that finding an adversary that is trusted enough to get M1 added, and
also a bad player such that they generated an M1 and M2, is probably
going to be hard, because they have to control BOTH keys and generate
them together.  It also depends on this broken truncated-hash system.

That's why I find that attack scenario unlikely.

More likely Mallet would want to find a key that matches an already
trusted key.  This is NOT a collision attack but is a preimage attack;
you know the hash result and need to find a second item that matches.
Luckily that's still a 2^N and not a 2^(N/2) attack, so unachievable
even with your 100-bit truncated hash system.

> The moral here is to use a sufficiently long fingerprint. But the point is that
> the fingerprint is indeed subject to birthday attack under rare circumstances.

I do agree with this.

> Yes, but if you didn't have to worry about a birthday attack at all, 80 bits
> would be acceptable by that metric.
>
> The point is that 80 bits is sufficient for a KeyID type use but a fingerprint
> should be at least 160 bits. 100/125 and 256 offer some safety margin.

Agreed, which is why we should tell people not to truncate!  :)

> If you are doing RSA, it greatly reduces the cost of a collision attack as you
> can avoid the need to generate new keypairs on each trial. But I don't think
> that is important as we are going to ECC in the near future anyway.

-derek

---

From: Vincent Breitmoser <[email-masked]>
Date: Tue, 04 Aug 2015 18:37:45 +0200

On 4 Aug 2015, Phillip Hallam-Baker wrote:

> Spending a hundred computer years to insert malware into an open
> source project is a much more probable attack.

Your attack scenario has no implications on authentication properties,
only non-repudiation.

 - V

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 04 Aug 2015 17:12:32 -0400

> with something they should not.

This seems like an insufficiently specified attack to me.  The same
"someone" controls both (fingerprint-collided) keys anyway, so even if
there's a "perl hack" involved, that someone is already authorized,
right?

can you please describe a more detailed attack scenario?

    --dkg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 04 Aug 2015 17:30:49 -0400

On Tue 2015-08-04 04:05:03 -0400, Nicholas Cole wrote:
> collisions is not feasible. That has always been central to OpenPGP.

Why must fingerprints be collision-resistant?  We've always said that
fingerprints need to be preimage-resistant -- that is, if i know your
fingerprint, i should not be able to forge a new key that has the same
fingerprint.

But collision-resistance is a different property: if the fingerprint
mechanism is not collision-resistant, then an attacker can create two
keys with the same fingerprint.  Why is this a threat?

> If that creates headaches for user interfaces then we will have to
> find ways to deal with that, but that is a separate discussion.

I agree with this.

> candidate algorithms and have done with it?

The current OpenPGP fingerprint mechanism (in RFC 4880) uses SHA-1,
which is a 160-bit digest.  SHA-1's collision resistance is believed to
be weaker than the 2^80 work factor that an ideal 160-bit digest should
have.  But that doesn't mean that it is necessarily "broken" for
OpenPGP, if there is no way to exploit a collision atack on fingerprints
in general.

That said, the general cryptographic advice on SHA-1 is "don't use it",
so while sticking with SHA-1 may not be a problem for this specific
case, it is a distraction from the cryptanalysis to have to have this
kind of discussion ("actually, maybe it's ok in this particular use")
whenever it comes up.

Our constraints in the WG here are also bound by UI concerns -- the
fingerprint mechanism is one used by humans, and humans have a limited
capacity to process and handle long high-entropy bitstrings (regardless
of their representation).  So we're really trying to navigate a
multidimensional design space here when we talk about what to do for
fingerprints.

I'll try to start a new thread that identifies those choices more
clearly, and ask people to weigh in on simpler questions about
fingerprints rather than having everything tangled up.

             --dkg

---

From: Derek Atkins <[email-masked]>
Date: Wed, 05 Aug 2015 13:15:57 -0400

> OpenPGP, if there is no way to exploit a collision atack on fingerprints

Indeed, while the SHA-1 collision resistance appears to be less than
2^80, there does not seem to be any known attacks that would make a
preimage attack any easier, which means the way OpenPGP uses SHA-1 for
fingerprints is still, technically, secure.

The real issue is one of education.  It's probably easier to move to
SHA2 than explain why the OpenPGP use of SHA-1 for fingerprints isn't
broken.

-derek

---

From: ianG <[email-masked]>
Date: Thu, 06 Aug 2015 16:55:25 +0100

> keys with the same fingerprint.  Why is this a threat?

I'll bite:  A person with two keys can sign a document that holds him, 
then announce that it wasn't signed by him.  As proof, he can 
anonymously publish his other key...

(What does this prove?  Well, not a lot but it does spoil the normal 
narrative.  Part of the success of a system is that it eliminates 
spoilers...)

iang

---

From: Vincent Breitmoser <[email-masked]>
Date: Thu, 06 Aug 2015 18:07:57 +0200

On 6 Aug 2015, ianG wrote:

> I'll bite: A person with two keys can sign a document that holds
> him, then announce that it wasn't signed by him.

Even though two keys exists with the same fingerprint, a signature made
by one will only check out with that one, so creating ambiguous
signatures is not that simple unless the attacker can also freely choose
which one of the two keys will be used for verification.  Also keep in
mind that certificates are made over public key material, not only
fingerprints.

> As proof, he can anonymously publish his other key...

Yes, well.  He could also publish this key if it wasn't a collided one,
or simply state that it was compromised.  Which leads us to the same old
discussion about the usefulness of non-repudiation in practice.

 - V

---

From: Nicholas Cole <[email-masked]>
Date: Thu, 6 Aug 2015 17:12:48 +0100

> discussion about the usefulness of non-repudiation in practice.
There's actually just a more basic, practical problem. Most gpg tools
assume unique fingerprints. Is it even possible to specify one key rather
than another if both have the same fingerprint?

---

From: Werner Koch <[email-masked]>
Date: Thu, 06 Aug 2015 18:19:36 +0200

> anonymously publish his other key...

or publish his private key and claim that it has been stolen.

Shalom-Salam,

   Werner

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 6 Aug 2015 12:38:22 -0400

> discussion about the usefulness of non-repudiation in practice.

Yes, I think we all understand the attack scope etc. pretty well at this
point. The question is what to do about it and I think we actually have a
practical consensus there as well.

Remember that I am a systems guy looking to build stuff on top of stuff
that is built on top of stuff. So for me the problem with a fingerprint
that might or might not be vulnerable to attack is that I have to evaluate
the security properties every time it is used and give reasons.

The use of MD5 in HTTP-DIGEST authentication is perfectly secure even with
the known flaws in MD5 etc. because the design intentionally uses a nested
construction to guard against extension attacks and the low entropy of
passwords means MD5 is never going to be the weakest link. But even so I
gave up explaining to people why that was so about ten years ago because it
just wasn't worth having the same argument again and again and again. Even
pointing out that the scheme was designed that way only to get round the
public key patents and there are much much better ways to do things does
not end the argument.

There are really two questions that the group needs to consider:

1) How many significant bits are necessary when printing a fingerprint on a
business card?

2) How many internal bits should be preserved?

The answer to 1 seems to be that 100 bits is the very lowest security level
that is acceptable and 150 bits should be more than sufficient for OpenPGP
uses.  The work factor for impersonation of a key holder being 2^100 and
2^150 respectively.

The answer to 2 is 'as many as you have available'. So even if there are
only 150 bits printed on the business card, programs should store either
the complete key parameters or the full digest output internally.

The security considerations should mention the birthday attack so that
reviewers know it has been considered and that the scope is limited to
allowing an attacker to create a pair of colliding keys for their own use.
The circumstances in which this could be exploited are very narrow and
would depend on the attacker being able to cause two different systems to
react differently to the same fingerprint.

For example, imagine a debit system in which the account is identified by a
fingerprint. Mallet creates a malicious keypair and ensures that the bank
of Ethel has one and the bank of Gax has the other. Mallet then creates a
money transfer order from his account at Ethel to his account at Gax which
he signs with the Gax key. As soon as Gax has cleared the funds, Mallet
transfers them out again (a few milliseconds later). When Gax tries to
perform settlement against Ethel at the end of the day, Ethel rejects the
transfer order because the signature doesn't verify.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 06 Aug 2015 15:19:24 -0400

> than another if both have the same fingerprint?

but what are the consequences of this?  If there's a specifically
troubling scenario that puts other people at risk, we should be able to
describe it.

If there isn't, then this suggests that actually using two keys with the
same fingerprint is a problem only for the person who holds the two
keys, right?

But that person has an easy (much cheaper in fact) way to proceed
without the problem: don't make a fingerprint collision in the first
place!

        --dkgp

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 6 Aug 2015 21:20:12 -0400

> without the problem: don't make a fingerprint collision in the first

Dan,

The problem is that the person who is potentially at risk is not the key
holder but the relying party who verifies the key.

As with 'Domain Separation' it is a case where most of us prefer to be
conservative unless there is a good reason to try the bleeding edge.
Doubling the length of a printed fingerprint is clearly a problem. Having a
big internal fingerprint isn't.

Here, 100, 125 or 150 bits seem fine for a printed fingerprint and 256 bits
is comfortable for an internal one. Do we really need to go further? My
original goal was to avoid having to go into this explanation at last call.

---

From: ianG <[email-masked]>
Date: Fri, 07 Aug 2015 03:06:43 +0100

On 7/08/2015 02:20 am, Phillip Hallam-Baker wrote:
>
>
> On Thu, Aug 6, 2015 at 3:19 PM, Daniel Kahn Gillmor
> <[email-masked] <mailto:[email-masked]>> wrote:
>
> Doubling the length of a printed fingerprint is clearly a problem.
> Having a big internal fingerprint isn't.
>
> Here, 100, 125 or 150 bits seem fine for a printed fingerprint and 256
> bits is comfortable for an internal one. Do we really need to go
> further? My original goal was to avoid having to go into this
> explanation at last call.

Are we arguing about a shortened internal identifier for the key? 
That's easy.  The full hash, please.

iang

---

From: Vincent Breitmoser <[email-masked]>
Date: Fri, 07 Aug 2015 12:06:49 +0200

On 7 Aug 2015, Phillip Hallam-Baker wrote:

> Here, 100, 125 or 150 bits seem fine for a printed fingerprint and
> 256 bits is comfortable for an internal one. Do we really need to go
> further?

I'm not even sure what an "internal" fingerprint is supposed to be, or
where it is supposed to be used.  A fingerprint is the one true unique
identifier for a key, diverging from this "internally" misses the point
of that.

I also agree with Werner on the aspect that the openpgp rfc should
specify what a fingerprint is purely from a data perspective.  How it is
printed or otherwise represented is not something we should go into
there.

 - V

---

From: Bill Frantz <[email-masked]>
Date: Sun, 9 Aug 2015 08:49:40 -0700

I am more and more convinced of the wisdom of Alan Karp when he 
insists that any system which uses a hash must specify what 
happens when there is a hash collision. He points out that 
anytime data longer than the hash output is hashed, there is the 
possibility of a collision, which is true when calculating key fingerprints.

Now the consequences may be severe or trivial. If a PGP message 
routing application uses the fingerprint to select the 
destination, the consequence of a collision may be as trivial as 
routing messages to recipients who can't decrypt them, or the 
more serious consequence of not sending messages to the 
recipient who can decrypt them. The exercise of figuring out 
what will happen results in better design.

There has also been an undertone of, "If we can't come up with 
an attack, there aren't any." in this thread. I find this 
attitude very dangerous as new classes of attacks (e.g. power 
analysis) are constantly being discovered.

I would suggest wording in the security considerations section 
something like:

"During the design process, any application using key 
fingerprints SHOULD characterize the consequences of a 
fingerprint collision on the application's security and 
implementation integrity, particularly when using fewer bits 
than the output of the fingerprint hash."

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz        | Ham radio contesting is a    | Periwinkle
(408)356-8506      | contact sport.               | 16345 
Englewood Ave
www.pwpconsult.com |  - Ken Widelitz K6LA / VY2TT | Los Gatos, 
CA 95032

---

From: ianG <[email-masked]>
Date: Sun, 09 Aug 2015 17:23:55 +0100

Hi Bill,

On 9/08/2015 16:49 pm, Bill Frantz wrote:
> I am more and more convinced of the wisdom of Alan Karp when he insists
> that any system which uses a hash must specify what happens when there
> is a hash collision. He points out that anytime data longer than the
> hash output is hashed, there is the possibility of a collision, which is
> true when calculating key fingerprints.
>
> Now the consequences may be severe or trivial. If a PGP message routing
> application uses the fingerprint to select the destination, the
> consequence of a collision may be as trivial as routing messages to
> recipients who can't decrypt them, or the more serious consequence of
> not sending messages to the recipient who can decrypt them. The exercise
> of figuring out what will happen results in better design.
>
>
> There has also been an undertone of, "If we can't come up with an
> attack, there aren't any." in this thread.

I disagree with that characterisation.  I would rather see it like this:

       If we can't come up with an attack,
       then we should not defend against it.
       We should *accept the risk*.

1. it is likely the attacker won't either.

2. if the attack-space is theoretical or exotic (eg quantum), the 
likelihood of it developing to a practical attack is low and/or slow. 
Then, waiting for more info is the smarter thing to do unless there is a 
cheap easy fix.

3. when an algorithm is designed to be very strong, this gives us an 
ability to lean on it and rely on it entirely.  This delivers benefits 
in code simplicity, and releases resources to concentrate on what we do 
know is likely to break, and is hurting our users.

The one thing we can say about hashes is they are darn strong.  They've 
never really failed us.  The only blackmark was MD5, when some projects 
where negligent and didn't move [0].  Lean on hashes.

4. how can you defend against an attack you can't come up with?

5. and finally, concentrating on attacks that we imagine might happen in 
the lab and can't build even a PoC for leads to isolation and myopia. 
We are in the business of serving our users, and they have plenty of 
things harming them right now.  Let's concentrate on delivering what 
addresses their pain, not what confuses us.

(Although I agree that the risk-analysis methodology -- which explicitly 
includes the willingness to accept a risk -- has not found widespread 
favour in our community :)

> I find this attitude very
> dangerous as new classes of attacks (e.g. power analysis) are constantly
> being discovered.

1. when that information develops, we can "come up with the attack." 
This stops us drifting into lab myopia.

2. How is power analysis going to effect a hash?  Surely, if I can do 
power analysis, I'm not that concerned about the hash, I'd rather suck 
the key bits?  OK, I know it was an example... but this is an example of 
"not an attack."

> I would suggest wording in the security considerations section something
> like:
>
> "During the design process, any application using key fingerprints
> SHOULD characterize the consequences of a fingerprint collision on the
> application's security and implementation integrity, particularly when
> using fewer bits than the output of the fingerprint hash."

If we're talking about a mid-range published key fingerprint of say 100 
bits, then there is a capability for collisions and perhaps preimages in 
the future, sure.

But we have a built in mechanism for that already;  increase to 150 then 
200.  So how about:

"During the design process of any application using shortened key 
fingerprints, attention should be paid to a recovery strategy in the 
event that the shortened fingerprint becomes subject to collisions or 
preimage attacks."

And at full hash-length in the fingerprint I'd be silent in the 
document.  Accept the risk.  Lean on the full SHAx.  It's been the most 
solid rock in cryptography so far.

iang

[0] MD5 should have been deprecated in 1993-1995 timescale, SHA1 should 
have been deprecated in the 2000-2004 timescale, if you are at risk of 
collision attacks.

---

From: Bill Frantz <[email-masked]>
Date: Sun, 9 Aug 2015 14:52:15 -0700

>We should *accept the risk*.

The specific issue I was addressing was PHB's source code 
checkin attack. Most of us, me included, thought that specific 
attack was not very convincing. However, to my mind, there may 
be other, more serious attacks using the same basic mechanism. 
Just because we can't think of them doesn't mean we shouldn't 
defend against them.

Using all the bits of the key fingerprint hash is probably good 
a good enough defense against these unanticipated attacks, and 
we should state that in the security considerations section. A 
better defense would be to use the key itself, but that is 
probably overkill in most situations.

>1. when that information develops, we can "come up with the 
>attack." This stops us drifting into lab myopia.
>
>2. How is power analysis going to effect a hash?  Surely, if I 
>can do power analysis, I'm not that concerned about the hash, 
>I'd rather suck the key bits?  OK, I know it was an example... 
>but this is an example of "not an attack."

Power analysis was an example of a class of attack that came up 
late in the security analysis field and exposed a significant 
number of vulnerabilities. It is not a attack against hashes. 
Those are more likely to be new mathematical techniques.

>If we're talking about a mid-range published key fingerprint of 
>say 100 bits, then there is a capability for collisions and 
>perhaps preimages in the future, sure.
>
>But we have a built in mechanism for that already;  increase to 150 then 200.  So how about:
>
>
>"During the design process of any application using shortened 
>key fingerprints, attention should be paid to a recovery 
>strategy in the event that the shortened fingerprint becomes 
>subject to collisions or preimage attacks."

My problem with that statement is that there is no incentive to 
analyse the failure mode of the application should a collision 
occur. I agree that a collision is far more likely to be due to 
a hardware or software error than a hash failure, but performing 
the analysis can make the application more robust.

Let me return to my straw man example of a application that 
routes messages based on key fingerprint. If it assumes that 
there is only one routing address/fingerprint, and there is a 
collision, then it will route all the colliding messages to one 
address. If it assumes that there may be more than one address, 
then it will route all colliding messages to all the address. In 
the later case, the receivers will not be able to decrypt all 
the messages, but the messages encrypted to them will get 
through, a more robust situation.

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz        | Security is like Government  | Periwinkle
(408)356-8506      | services. The market doesn't | 16345 
Englewood Ave
www.pwpconsult.com | want to pay for them.        | Los Gatos, 
CA 95032