Subject: [saag] Revision of "Attacks on Cryptographic Hashes in Internet Protocols"

From: Paul Hoffman <[email-masked]>
Date: Thu, 8 Nov 2012 07:29:21 -0500

Greetings again. Bruce Schneier and I have started an update to RFC 4270, "Attacks on Cryptographic Hashes in Internet Protocols". This revision is meant to deal with new and more devastating attacks on MD5, the fact that SHA-1 collisions will be financially feasible in the foreseeable future, and NIST's upcoming SHA-3 announcements. We expect to keep this revision process open for at least five months because NIST probably won't finalize the parameters and naming and so on for KECCAK until then; that is, we won't send this to RFC Editor until SHA-3 is finalized. Please take a look at 

http://tools.ietf.org/html/draft-hoffman-schneier-4270bis

Sean and Stephen have agreed that we should use the SAAG mailing list for discussing this draft. 

--Paul Hoffman

---

From: Barry Leiba <[email-masked]>
Date: Thu, 8 Nov 2012 09:21:41 -0500

> Greetings again. Bruce Schneier and I have started an update to RFC 4270,
> "Attacks on Cryptographic Hashes in Internet Protocols". This revision is
> meant to deal with new and more devastating attacks on MD5, the fact that
> SHA-1 collisions will be financially feasible in the foreseeable future, and
> NIST's upcoming SHA-3 announcements. We expect to keep this revision
> process open for at least five months because NIST probably won't finalize
> the parameters and naming and so on for KECCAK until then; that is, we
> won't send this to RFC Editor until SHA-3 is finalized. Please take a look at
>

Is there time in the SAAG session today to run through the major changes?

Barry

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 08 Nov 2012 14:25:58 +0000

> Is there time in the SAAG session today to run through the major changes?

Plan is for Paul to do that at open-mic without slides, but it'll be
March-ish before NIST have the parameters AIUI so there's time. We also
plan to AD sponsor this so it'll get an IETF LC, and might be better to
see presented at IETF-86 around when that LC will be happening.

S.

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

---

From: Joe Touch <[email-masked]>
Date: Tue, 13 Nov 2012 14:16:03 -0800

Hi, Paul (et al.),

This doc refers to IETF protocols that use hashes, but doesn't discuss 
any in specific. It also doesn't address how hashes are used, e.g., solo 
(as a fingerprint), keyed (for authentication and source confirmation), 
as part of an HMAC, or as part of key derivation.

That sort of information might be additionally useful, IMO.

Joe

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 13 Nov 2012 20:24:19 -0800

On Nov 13, 2012, at 2:16 PM, Joe Touch <[email-masked]> wrote:

> This doc refers to IETF protocols that use hashes, but doesn't discuss any in specific. It also doesn't address how hashes are used, e.g., solo (as a fingerprint), keyed (for authentication and source confirmation), as part of an HMAC, or as part of key derivation.
> 

The opposite was decided when we did RFC 4270, of which this is a direct revision. Many protocols use hashes in multiple ways, and trying to list them was considered a distraction. I believe that is still the case.

--Paul Hoffman

---

From: Joe Touch <[email-masked]>
Date: Tue, 13 Nov 2012 23:35:04 -0800

> The opposite was decided when we did RFC 4270, of which this is a direct revision. Many protocols use hashes in multiple ways, and trying to list them was considered a distraction. I believe that i…

The doc says directly that the way in which specific hashes are used in 
"many" Internet protocols is safe. Indicating the details of that claim 
is critical to it having *any* weight.

Further, there's a big difference in the way in which hashes are used 
which can be just as important as the use of "better hash algorithms"

Leaving the interpretation of this doc as an exercise to the reader 
renders it inconsequential.

Joe

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Wed, 14 Nov 2012 13:14:34 +0000

Hi Joe and Paul,

>That sort of information might be additionally useful, IMO.

I think you (Joe) have a valid point about how the draft could be
improved, though the draft does address the use question somewhat (it even
has a section on "How Internet Protocols Use Hash Algorithms").

I have a suggestion: the draft could

1) more precisely define the different ways that hash functions are used
in more detail (in signatures, in HMAC, KDFs, other message authentication
codes, integrity checking, ...)   The definitions should be clear enough
that a relative crypto novice, looking at a specification that describes a
use of a hash function, could correctly categorize that use.

2) relate the security of each use case to the collision/first
preimage/second preimage attacks

3) have a section that describes uses of hash functions in Internet
protocols that rely on collision resistance.   (My thinking here is that
there are many uses of hash functions, and so we should focus on the most
security critical cases)

If we had an RFC with these clear categories in them, then we could
categorize new uses of hash functions that appear in new drafts, perhaps
focusing on the cases where collision resistance is required.   This could
be part of the SECDIR review process, or perhaps some other independent
process (for instance, send an automatic message to the authors pointing
out the hash function in their draft and the categories in the RFC).
Yes, I realize that there are a lot of of RFC and drafts using hash
functions, and that this is a non-trivial amount of work. But consider how
much better off we would be now if we had started categorizing uses of
hash functions in RFCs back in y2k ...

What do you think?

David

>> Greetings again. Bruce Schneier and I have started an update to RFC
>>4270, "Attacks on Cryptographic Hashes in Internet Protocols". This
>>revision is meant to deal with new and more devastating attacks on MD5,
>>the fact that SHA-1 collisions will be financially feasible in the
>>foreseeable future, and NIST's upcoming SHA-3 announcements. We expect
>>to keep this revision process open for at least five months because NIST
>>probably won't finalize the parameters and naming and so on for KECCAK
>>until then; that is, we won't send this to RFC Editor until SHA-3 is
>>finalized. Please take a look at
>>

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 14 Nov 2012 13:40:24 -0800

> Sean and Stephen have agreed that we should use the SAAG mailing list for discussing this draft.

One issue stands out for me in this excellent overview: the document 
suggests the preference of SHA-2 over the SHA-3 (Keccak), as in the 
following paragraph:

>    The authors acknowledge that deprecating a hash algorithm is
>    difficult from an operational standpoint, but it needs to be done
>    eventually, and this is a good time to again make a significant push
>    to SHA-2.  When NIST finalizes the parameters and test vectors for
>    SHA-3, implementors might want to start adding SHA-3 to their
>    products.  However, the authors do not believe that any push to start
>    using SHA-3 is warranted at any time soon.

SHA-2 is well-supported today, but there are no solid reasons why SHA-3 
will not be supported equally well in the future.

AES was not the fastest algorithm in software, but look what Intel did 
to it with the AESNI. Keccak is outstanding in hardware and perhaps on 
less mainstream CPU architectures (can't beat table lookup + XOR as min. 
instruction set).

Keccak is arguably the simplest standard hash algorithm, quite 
comparable to the simplicity of MD5.

As the computing environment gets more diverse, this will increase the 
value of Keccak. I support the algorithm agility, but it's not as easy 
to accomplish for the hash algorithms than, for example, for the 
encryption preferences.

Let's say there is a protocols that is hardwired to SHA1 or MD5. Are we 
telling people thinking about its improvement to go with the SHA-2? What 
about newly designed protocols? If you are a maintainer, what would you 
prefer: worry about explaining to others that "my SHA-2 use doesn't 
depend on collision resistance and is not vulnerable to extension 
attacks", v.s. I "use SHA-3".

I suggest that the document at least softens the statements on SHA-2 
v.s. SHA-3. Ideally, I would like to see a path on which we move to the 
universally supported SHA-3 and, hopefully, the hardware manufacturers 
are comfortable to jump in.

Thank you.

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 14 Nov 2012 14:33:43 -0800

On Nov 14, 2012, at 1:40 PM, Andrey Jivsov <[email-masked]> wrote:

> SHA-2 is well-supported today, but there are no solid reasons why SHA-3 will not be supported equally well in the future.

In that future, we can re-look at support for it in IETF protocols. For now, algorithm agility might be sufficient.

> Let's say there is a protocols that is hardwired to SHA1 or MD5. Are we telling people thinking about its improvement to go with the SHA-2?

Yes.

> What about newly designed protocols?

The same.

> If you are a maintainer, what would you prefer: worry about explaining to others that "my SHA-2 use doesn't depend on collision resistance and is not vulnerable to extension attacks", v.s. I "use SHA-3".

Nowhere did we say that you should not use SHA-3. In fact, we said the opposite. We said there was no need to push that.

> I suggest that the document at least softens the statements on SHA-2 v.s. SHA-3. Ideally, I would like to see a path on which we move to the universally supported SHA-3 and, hopefully, the hardware manufacturers are comfortable to jump in.

That's one view; we took a different one. So far, we have had good support in the IETF community for our view, but at some point that might change.

--Paul Hoffman

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 14 Nov 2012 14:37:45 -0800

> has a section on "How Internet Protocols Use Hash Algorithms").

Yes, it does.

> use of a hash function, could correctly categorize that use.

Proposed wording would be greatly appreciated here. I cannot see how to add that text and have it be anything other than singing to the choir.

> preimage/second preimage attacks

Ditto here. When we tried this seven years ago, we were attacked for being to restrictive in our descriptions. Seriously: if you have a contribution to make that you think is readable to a relative crypto novice and still accurate, we're all ears.

> there are many uses of hash functions, and so we should focus on the most

We thought we had that in the existing RFC and the current draft. Which other protocols are you thinking of?

--Paul Hoffman

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 14 Nov 2012 15:35:43 -0800

> In that future, we can re-look at support for it in IETF protocols. For now, algorithm agility might be sufficient.

I would agree, but the document such as RFC 4270 influence the future. 
If the message it sends is that the SHA-3 is an odd bifurcation in the 
SHA line, SHA-3 won't gain critical mass.

> That's one view; we took a different one. So far, we have had good support in the IETF community for our view, but at some point that might change.

It would be useful for me and others to see more details behind the 
arguments that the SHA-2 is preferred to SHA-3 at IETF. I suspect there 
are a lot of assumptions here that may not apply to every particular case.

One of the parameters is the timeline. The transition to a new hash 
algorithm may take years in protocols and formats without algorithm 
agility, while the plans for which route to take are being made today.

For example, in OpenPGP there is a hardwired SHA1 fingerprint. It still 
seems wrong to me to move to SHA-2 and not SHA-3. I am leaning toward 
non-agile solution here because of space constrains and the fact that 
the agility will only be a benefit if Keccak is broken (so instead of 
adding SHA-2 + agility, add hardwired SHA-3 which is good for a few 
decades, at least).

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 14 Nov 2012 15:42:52 -0800

On Nov 14, 2012, at 3:35 PM, Andrey Jivsov <[email-masked]> wrote:

> I would agree, but the document such as RFC 4270 influence the future. If the message it sends is that the SHA-3 is an odd bifurcation in the SHA line, SHA-3 won't gain critical mass.

If we have suggested that in the draft, we should change the text. Can you say where you got that feeling?

> It would be useful for me and others to see more details behind the arguments that the SHA-2 is preferred to SHA-3 at IETF. I suspect there are a lot of assumptions here that may not apply to every particular case.

Instead of speaking for others, I'll let them chime in here.

> One of the parameters is the timeline. The transition to a new hash algorithm may take years in protocols and formats without algorithm agility, while the plans for which route to take are being made today.

Noted.

> For example, in OpenPGP there is a hardwired SHA1 fingerprint. It still seems wrong to me to move to SHA-2 and not SHA-3. I am leaning toward non-agile solution here because of space constrains and the fact that the agility will only be a benefit if Keccak is broken (so instead of adding SHA-2 + agility, add hardwired SHA-3 which is good for a few decades, at least).

The OpenPGP people can speak for themselves; I certainly don't represent them.

--Paul Hoffman

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 14 Nov 2012 16:33:52 -0800

> If we have suggested that in the draft, we should change the text. Can you say where you got that feeling?

"However, the authors do not believe that any push to start using SHA-3 
is warranted at any time soon."

Suppose I am an Internet browser company. I read this as "OK, I will 
revisit the SHA-3 support in 5 year".

In 5 years the Keccak "read" support is added, hopefully without bugs.

X.509 CAs cannot enable the Keccak because they will want wide browser 
support. This means they are waiting for all the browser vendors to make 
the support available.

OK, the other browser vendors added the support in the following few 
years.

Then the CA will need to wait for the wide deployment of said browsers. 
Count the browsers in the TVs too. This will be another half of a decade.

So, we are looking at more than a decade, perhaps two, when the SHA-3 
can actually happen without significant disruptions.

For this to happen a decade from now some of the players should start 
making plans today. I think the statement I quoted above is only true 
for an environment where we can upgrade every participant fairy easily.

Hopefully NIST will force some timeline that will put the process in 
motion, because if I am in minority regarding how painful the new hash 
adoption is, I don't see it happening smoothly without a bit more 
proactive plan.

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 14 Nov 2012 16:39:32 -0800

On Nov 14, 2012, at 4:33 PM, Andrey Jivsov <[email-masked]> wrote:

> "However, the authors do not believe that any push to start using SHA-3 is warranted at any time soon."

We disagree that that sentence indicates "that the SHA-3 is an odd bifurcation in the SHA line".

--Paul Hoffman

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 14 Nov 2012 16:59:44 -0800

> We disagree that that sentence indicates "that the SHA-3 is an odd bifurcation in the SHA line".

OK Paul, I noted this :-). I would not read it that way, but some people 
might. The Internet will keep your reply as a proof to those.

Nonetheless... I would prefer to see some language suggesting that the 
hash transition issue may be more urgent because of the time lag in some 
cases (described in my previous email).

Re-phrasing my earlier deployment concerns, let me observe that the hash 
algorithm agility/preferences is an elusive thing in general. In 
general, we sign persistent data structures that will be processed by 
entities we may not know anything about. Thus, we cannot gather 
capability preferences from entities who will be performing the 
verification. The only reliable solution is to (universally) deploy 
"read" support and then enable the "generation" of the new data structures.

Thank you.

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Wed, 28 Nov 2012 15:23:06 +0000

Hi Paul,

A quick comment.   The draft says that uses for hash algorithms include

   o  Integrity protection.  It is common to compare a hash value that
      is received out-of-band for a file with the hash value of the file
      after it is received over an unsecured protocol such as FTP.

... and it then says that collision resistance is not needed for the
integrity protection use case.   However, it seems to me that there are
possible threats against hash-based integrity protection that would be
possible if the person/system generating the hash can generate collisions,
and is untrustworthy.  Consider the case of an md5sum hash on a debian ISO
image.  If the person responsible for generating the hash can create a
malware-laden ISO imagine that has a hash collision with the actual ISO
image, then they could substitute the bad one for the good one regardless
of the hash checking step.  An attacker might leave the good ISO image in
place to avoid detection, while foisting the bad one on some victims.  I
am assuming that there are different ways of distributing ISO images, or
that the substitution of bad for good can take place after the good one
has been investigated and found to be good.

It is debatable how important this scenario is in practice, but it seems
that collision resistance is at least desirable for integrity protection.

David

P.S. - apologies for picking on debian, which is a most excellent distro
:-)

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 28 Nov 2012 07:40:46 -0800

> that collision resistance is at least desirable for integrity protection.

Collision resistance is not needed if you trust the party who created the hash; it is needed if you do not trust that party.

Proposed addition to the paragraph following the list:

Integrity protection is affected by collision attacks if the party checking the hash does not completely trust the party who published the hash.

--Paul Hoffman

---

From: Mouse <[email-masked]>
Date: Wed, 28 Nov 2012 16:32:22 -0500 (EST)

> Consider the case of an md5sum hash on a debian ISO image.  If the
> person responsible for generating the hash can create a malware-laden
> ISO imagine that has a hash collision with the actual ISO image,

...then you're dealing with second-preimage reisistance, not just
collision resistance.

At least, unless the "actual ISO image" creator is in on the deal, and
in that case even the best hash imaginable won't help.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		[email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Wed, 28 Nov 2012 22:29:59 +0000

>in that case even the best hash imaginable won't help.

The point that I wanted to make is: if the actual ISO image creator is
untrustworthy and the hash function is not collision resistant, then it is
possible for that person to make two images, one good and one bad.   This
enables attacks on the system that are not otherwise possible, i.e.
publishing the good image in the distribution channels that will actually
be checked by security auditors, then publishing the bad one in some other
distribution channels.

David

---

From: Steven Bellovin <[email-masked]>
Date: Wed, 28 Nov 2012 17:38:39 -0500

> be checked by security auditors, then publishing the bad one in some other

What about the party who prepares part of the contents, i.e., one file?
The hash function reaches that file with fixed but unknown internal state.
It's easy to prepare two different files that would cause a collision from
the standard starting state, but I'm not sure about this scenario.

		--Steve Bellovin, https://www.cs.columbia.edu/~smb

---

From: Mouse <[email-masked]>
Date: Thu, 29 Nov 2012 01:20:12 -0500 (EST)

> The point that I wanted to make is: if the actual ISO image creator
> is untrustworthy and the hash function is not collision resistant,
> then it is possible for that person to make two images, one good and
> one bad.   This enables attacks on the system that are not otherwise
> possible, [...]

Ah!  I misunderstood.

Yes.  (I could quibble about how the colliding data blobs have to be
valid ISO images, but I suspect that part would border on trivial in
any realistic collision-resistance break, just as the MD5 collision
example I have managed to make both blobs valid PostScript programs.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign