IETF63: Observations from the Hash BOF

Here go my observations and notes from the Hash BOF at last week's
IETF...



Executive summary: The IETF doesn't know, yet, what to do, because
NIST (and the crypto community at large) don't know, either, so
everybody is holding their breath until CRYPTO 2005, and the NIST
hash workshop on halloween. [3]


More extensive report: XML Signature has DSAwithSHA1 as its
mandatory signature algorithm. Recently, attacks against the
collision resistance of SHA1 have been published, i.e., it is now
less computationally expensive than expected to calculate two
messages m and m' such that SHA1(m) = SHA1(m').

Similar attacks against MD5 have been known for some time, but have
recently been improved to the level on which collisions can be
created on an off-the-shelf notebook computer [0]. The techniques
used against the different hash algorithms are apparently related.
Attacks against SHA1 are not yet there, but then again, attacks
never get worse.

SHA1 generally being the bread-and-butter hash of the IETF (after
MD5 was for new protocols), there was a BOF at IETF63 in Paris last
week to discuss how to move forward.


draft-hoffman-hash-attacks-04 [1] (by Paul Hoffman and Bruce
Schneier) contains an analysis of the current situation, and some
arguments on the effect of the weaknesses on internet protocols.
Non-repudiation digital signatures and digital signatures in
certificates are given as examples for protocols where collision
resistance is relevant; there are a number of other uses of hash
algorithms in protocols where this property is not essential. The
basic claim is that, when the hashed material is intended for human
consumption, actual attacks are unlikely, or are at least unlikely
to cause real damage. (Imagine a court case where two different
messages with the same signature are presented, one of these
possibly including some form of gibberish.) This argument, however,
does not apply to material intended for machine consumption, in
particular when the signature confers authorization to do certain
things.

However, it's interesting to note that the weaknesses in MD5 have
actually been used to produce X.509 certificates with the same
signature, but different public keys. [2] (These certificates do not
give raise to a practical attack, but they are still troubling.) 

A similar attack was demonstrated against PostScript files, where
PostScript prologues with a hash collision were used. [6]

So attacks based on lack of collision resistance clearly get closer
to being practical; it is interesting to note that the PostScript
example is essentially an attack on counter signatures.


It's important to note that we are not at a stage where preimaging
attacks are practical, i.e., attacks where either a colliding
message for a given (!) message can be found, or attacks where a
preimage for a given hash value is found.


In draft-hoffman-hash-attacks [1], the authors interestingly
disagree on the path forward.  Schneier suggests immediately
migrating towards SHA-256 (a "longer" cousin of SHA-1); Hoffman
suggests sticking with SHA-1 for the moment (given the cost of
switching hash algorithms), and switching when the current class of
attacks is better understood, and more robust algorithms are
available.


The BOF in Paris started with a summary of
draft-hoffman-hash-attacks [1], and a pointer at the NIST halloween
workshop; an agenda for that workshop is expected to be published
right after CRYPTO 2005 (held from August 14 to August 18 in Santa
Barbara).  That workshop is expected to help NIST decide its next
steps, such as whether to hold a competition for hash functions, and
what policies to apply to the use of SHA-256.


Russ Housley then presented a paper by some people at RSA (who were
not present).  This paper describes some extremely simple
preprocessing steps that can be applied to data before it is fed to
SHA1 or MD5 (!), and that allegedly thwart all known collision
attacks. These preprocessing steps consist in inserting four 0 bytes
every 12 bytes of input, or duplicating every byte in the input
stream, in the sense of turning a byte string abc into aabbcc.  [4] 


Ran Canetti presented randomized hashing approaches: The idea is to
parametrize the hash function with a random value that is then
included with the signature data.

I.e., when the signature with the traditional mechanism would be
s(k, h(m)), then the signature now becomes 

		   ( r, s(k, encode (r, H_r (m))) ),

encode being a suitable encoding function.  Canetti claimed that
this approach reduces the security requirements on the hash function
from collision resistance to target collision resistance.  It's
worth noting that this approach assumes the availability of a good
source of random numbers with the signing party.  In some contexts,
that's a strong assumption to make.

Also, Uri Blumenthal raised concerns that, while this approach might
sound like a viable defense against some attack mechanisms (i.e.,
raising the bar for brute force attacks), it might not be applicable
to differential attacks.


Steve Bellovin presented joint work with Eric Rescorla [5]; they
analyzed S/MIME, TLS and IPSec and asked whether it is easily and
securely possible to change hash algorithms in these protocols.  The
conclusion was that "they all got it wrong", in the sense of
requiring protocol changes beyond simply adding some identifiers to
prepare for a transition to a new hash algorithm.

With respect to XML Sig, this is more an issue for protocols that
are built on top of that spec than for XML Sig itself.




Tim Polk from NIST talked about hash truncation, i.e., using a
longer hash such as SHA-256 and deriving a shorter function from it.
NIST advises *against* using simple truncation (i.e., just take the
first n bytes of the hashes output) because of concerns about
downgrade attacks: Imagine that you can attack a shortened version
of a hash, but not its entire length.  In that case, simple
truncation would mean that one could trick the relying party into
trusting that shorter hash, as opposed to the real thing.

The conclusion is that they want a totally different hash value for
every given output size.  Their current approach is to generate the
hash function's initial value from a combination of the base
algorithm and the truncation length.  They are planning to submit
this technique as an Internet-Draft prior to IETF 64.

Polk also mentioned that the security proof for truncation turns out
to be surprisingly hard.


Finally, charter bashing.  A draft charter for an IETF hash working
group had been distributed in preparation for the BOF, and was
discussed.

There was consensus that the IETF is not in the business of
designing new hash functions or modes of operations.  Appropriate
tasks for the IETF in this space are (1) stating its requirements,
and (2) going through its protocols and looking what needs to be
done.  (I.e., a more extensive exercise à la the work of Rescorla
and Bellovin that I talked about above, probably best conducted in
the individual working groups.)

There was also some discussion about a Best Current Practice
document on how to use hash functions in protocols.

Another topic for a BCP would be to standardize hash functions and
modes of operations, that have been developed elsewhere.  It looks
like the time is not yet there for such a document, given the
general lack of knowledge about where hash function research is
going.

There was a suggestion that negotiation mechanisms and the BCPs
mentioned above would be an appropriate topic for IETF work (with
different timing), while at least part of the questions related to
the intricacies of hash functions, modes, etc. would be in scope for
the Internet *Research* Task Force.

The conclusion of the meeting was that the discussion needs to
continue, for the moment on the mailing list.

Probably, we'll know much more than now in a couple of weeks or
months.


0. http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf
1. http://www.ietf.org/internet-drafts/draft-hoffman-hash-attacks-04.txt
2. http://www.win.tue.nl/~bdeweger/CollidingCertificates/ddl-final.pdf
3. http://www.csrc.nist.gov/pki/HashWorkshop/index.html
4. http://eprint.iacr.org/2005/248
5. http://www.cs.columbia.edu/~smb/papers/new-hash.ps
6. http://th.informatik.uni-mannheim.de/people/lucks/HashCollisions
-- 
Thomas Roessler, W3C   <tlr@w3.org>

Received on Tuesday, 9 August 2005 21:45:17 UTC