ietf-openpgp
[Top] [All Lists]

Re: Any SHA-1 dependencies?

2005-09-15 20:12:47

Daniel Nagy writes:
Basically, what you are proposing is a sort of universal hash function,
where the hash algorithm identifier is followed by the hash computed using
that particular algorithm.

This is potentially very dangerous, as it does not follow several
assumptions about a good hash function. Namely the hash value is not
unique and parts of the hash function are not uniformly strong.

I agree that is one way to look at it.  In a hypothetical future key
fingerprint system, there would be multiple kinds: a SHA-1 fingerprint,
a SHA256 fingerprint, a RIPEMD160 fingerprint, and so on.  So it is
non-unique.  The idea is that if SHA-1 or some other hash became broken,
the other kinds of fingerprints could be used, without revising the spec.
Of course an attacker could replace a fingerprint with one based on an
old, weak hash, but it would ultimately be up to the verifier to decide
which hashes he would trust.

In the event of a break, switching over to a new hash would be a
potentially costly operation but it would not require issuing a new spec.
I'm not sure what dangers you see over a system which would require
changing both implementations and specifications.

On the other hand, there is a fair chance that SHA1 (and even MD5, though
its 128 bit length is a problem by itself) might be fixed. The known
collision attacks are based on collisions in the compression function
and it seems that in both cases the set of "problematic" blocks is actually
very sparse and easily detectable. This allows for several security
improvements: first, (and it has already been done, AFAIK) one can
immediately detect a data stream as one that is likely to be an
attempted attack on the hash function, second, one might create a "fixed"
compression function that does something different for problematic blocks,
thus yielding a hash function that gives the same output as SHA1 for the
vast majority of inputs, while being resistant against SHA1 collisions.

The detection result is very likely to be presented at Eurocrypt2006, and
there's a chance that the fix will be presented too.

I will look forward to seeing that.  I wonder if it might be discussed
at the NIST Halloween "hash bash", it sounds like it would be of great
interest there.

Without knowing the details it is hard to comment, but in general I
would worry that any detection system might be "brittle" and possibly
small changes to the attack method might bypass the detector while still
producing collisions (perhaps somewhat more expensively).  For example
the Wang attacks always use the same initial differential, but there
is no reason they could not work with slightly different differentials,
I think.  She chose the best one but I gather that there are others that
weren't too bad.  A detection system tuned too closely to known attacks
might miss these alternatives.

The sparsity of problematic blocks also implies (although this is not
strictly within the scope of the discussion) that key-id binding signatures
might collide only on the key part (*), which is not dangerous. If the above
mentioned sanity check is performed, it removes even the non-dangerous key
collision as a possibility.

I also remember Eli Biham last year at Crypto demonstrating very textual
looking collisions on truncated SHA-1.  His collisions were composed
of ascii characters and even English words.  Granted, truncation makes
a world of difference in the ease of the attack but I wonder if we can
be sure that the full SHA-1 attacks can never be improved in this way.

Also remember, that collisions are of concern only if the data is to be 
signed by
someone different from its author. There are protocol-level safeguards
against this possibility, though employing these would require a major
overhaul of OpenPGP, which in the light of the above is not warranted (yet).
Someday, however, we might very well be forced to introduce version 5
signatures for certification and other notarial purposes. It is better to
postpone that as long as possible, because important discoveries with
immediate consequencnes on design and standardization decisions might lay 
ahead.

Yes, there have been strong debates in online forums for example about
changing signature procedures so that the signer prepends a block of
data of his choice to the message to be signed, in case the message is
prepared by someone else.  There seems to be no consensus on whether
this is on balance a good idea or not.

So, I would recommend sticking to SHA1 for the time being, as there is no
hash function with a better design at this point. Alternatives that belong
to the same MD4 family of hash functions (e.g. the now-fashionable
RIPEMD-160) have not been attacked only because SHA1 was a more rewarding
target.

I didn't recommend stopping using SHA-1.  In fact my only actual
recommendation was to include SHA256 as another MUST hash, in case SHA-1
gets broken more badly (and in the hope that SHA256 will be OK).

Now, moving to 256-bit hash functions in order to have a built-in "safety
factor" keeping the hash-function safe even if it's partially broken, seems
to be inconsistent with market-economies. In our case it is particularly
relevant, because the standard we are designing is not enforced, leaving the
choice to the user.

In general, though, it is risky to use non-MUST hashes in your
signatures, for interoperability reasons.  Of course we have only limited
leverage over this via the spec, and as you note the market may force
implementations to move to SHA256 regardless of whether it is MUST or not.

[Skipping on a bit]

Back on topic, this is why I would advise against moving to 256-bit hashes
based on the MD4 design. Yes, it would add some security against hypotetical
ultra-motivated adversaries flush with resources, but you are interested in
these not because they are actually threats but because you are catering to
paranoid customers. Those would sneer at a partially broken SHA256 just as
they sneer at a partially broken SHA1. So, you will have to switch again
very soon, without gaining anything from the previous switch. It's not
rational behavior, especially in standardization.

So, are you predicting that SHA256 will have at least theoretical breaks
of its own?  The people I have talked to seem quite non-committal about
this prospect.  No one can rule it out but most people say it should be
stronger than SHA-1 and more resistant to this kind of attack.

Thus, my recommendation would be to postpone the discussion until more is
known, to avoid swift moves and stick to SHA1 for the time being. Maybe a
footnote would be warranted to explain why it's still safe to do things the
way we do them.

Again, the only thing I recommended was to add SHA256 as a MUST.  The only
MUST-implement hash we have now is SHA-1.  What do you think of that change?


Now, I have a separate set of grievances about the v4 private key packet 
format
and the way v4 key fingerprints are being calculated, but that has very
little to do with the recent developments around our once-favorite hash
function. In a separate post, I will explain why I would like to introduce a
new version of key packets (both public and private), and once we embark on
designing new packet formats, we can address the use of hash functions in
that context as well, but again, it's a separate topic.

I have another change to suggest as well, which will also go into a future
message.

Thanks for your comments, they are very interesting and helpful.

Hal Finney

<Prev in Thread] Current Thread [Next in Thread>