Hal,
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.
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.
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.
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.
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.
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.
The thing is that partially broken security products are a tough sell even if
the remaining part is still secure enough. It is pretty clear from your
post that you _are_ concerned about this. Let me digress a bit:
In the USSR, it was okay to slash development costs by building in safety
factors, so that even if the hash function or the block cipher turned out to
be weaker than the designers originally thought, they would be still secure
enough. Hence the 256-bit key length of the standard soviet block cipher
(GOST 28147-89) which also doubles as the compression function of their
standard hash function (standardized later as GOST 34.11-94). For government
use (**) and for use in a planned economy this was the most rational way of
designing the system: quick, cheap and a little dirty. In market economies,
this approach won't fly, because as soon as your product is discredited by
being partially broken, you will have to switch anyway, so cheap development
with safety factors won't save you money in the long run. Hence, it's not a
rational approach to cryptographic algorithm design and indeed, we don't see
it in successful products in the free market. It is important to emphasize
that it is not because your customers are somehow dumber in a market economy
but because in addition to your development costs, they also have to bear
the cost of choosing the right product for themselves (this cost does not
occur in planned economies -- in certain cases, it can be a significant
saving), and they are rational about minimizing it by not touching anything
that has been discredited in any way -- they simply cannot afford to behave
otherwise (in most cases).
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.
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.
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.
(*) It is impossible to trick someone into binding a sane-looking unseen UID
to a given public key by presenting him with another sane-looking UID that
would collide with the unseen one for signature.
(**) There is evidence suggesting that the mentioned algorithms were in
government use long before having been released to the public as industry
standards. Probably since the early eighties or even earlier.
Bests,
--
Daniel