Subject: [Cfrg] Who needs collision-resistance, anyway?

From: Shai Halevi <[email-masked]>
Date: Thu, 17 Mar 2005 14:05:50 -0500

Since at present we are not really sure what construction can we trust 
to be collision-resistant, it seems to make sense asking whether we can 
live without fully collision-resistance hash functions.

Signatures is one applications where full collision-resistant is *not* 
needed (in principle). It is well known that one can construct digital 
signatures from "target collision-resistant" functions, just as easily 
as from fully collision-resistant functions: Roughly, to sign a message 
m, the signer chooses a new random key k, computes h=HMAC_k(m), and then 
uses (say) some variant of RSA-PSS to sign the pair (k,h), and outputs 
also k as part of the signature.

My questions are the following:

* Are there signature standards that actually work this way?

* Wouldn't it make sense to modify some of the standards along this 
line? (Yes, I know that modifying standards is always hard, but we
would eventually have to replace the hash function anyway, so we might 
as well take this opportunity to modify also the way it is used.)

* Can anyone describe a real-life application where full 
collision-resistance is really needed?

-- Shai

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Daniel Brown <[email-masked]>
Date: Thu, 17 Mar 2005 14:04:21 -0500

> * Are there signature standards that actually work this way?

Yes: PV-signatures in IEEE 1363a, for example.

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 17 Mar 2005 22:42:49 +0200 (IST)

A concrete proposal for randomized hashing in the context of signatures is
as follows:

Alice sends m to Bob for signing.
Bob chooses a random SHA-1 IV r and generates a digest d(m)=SHA1_r(m)
(SHA1_r denotes SHA1 with IV=r).
Bob computes his signature s on the concatenation of d(m)|r
B returns to A the pair (s,r) as his signature  on m

Here the hash function does not need to be fully collision resistant (but
rather what is caled in the literature "target collision resistant" or
"one-way hash").
Note that B may find two msgs for which the same pair (s,r) is a valid
signature but that's not a problem as long as A cannot find such pair.
If at any point two msgs m,m' with the same valid signature arise then the
blame is on B (in which case B should be considered the legal signer of
both msgs).

Hugo

---

From: Russ Housley <[email-masked]>
Date: Thu, 17 Mar 2005 17:39:13 -0500

Hugo:

Is this the same as the following?

         h = SHA1 ( salt || msg )
         s = Sign ( h )

         salt is a random value, and it is a full block
            (512 bits in the case of SHA1)

         msg is the message to be signed

The signer needs to pass salt, msg, and s to the recipient for them to 
validate the signature.  In this way, there is not change to SHA1 itself, 
but the random salt leads to the randomization of the IV prior to the 
processing of the msg.

Russ

---

From: csjutla <[email-masked]>
Date: Thu, 17 Mar 2005 17:51:55 -0500 (EST)

You forgot to sign the salt.

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 18 Mar 2005 01:09:02 +0200 (IST)

Yes. the SHA1(salt||msg) is equivalent to SHAI_r as I described and
(as in hmac) it avoids the need to "program" the IV in SHA1.
 Note that the length of salt may be significant since it needs to be
transmitted with (and/or inside) the signature; so since we are talking
about "practcal heuristics" anyway we could make salt to be 160 random
bits padded with 0s. Or, at the expense of an extra SHA1 calculation, one
can implement the hash as HMAC with the 160-bit "salt" as the key (as said
this is somewhat more expensive but can use the same interface as hmac).

Hugo

On Thu, 17 Mar 2005, Russ Housley wrote:

> validate the signature.In this way, there is not change to SHA1 itself,
> >B returns to A the pair (s,r) as his signatureon m
> >
> >rather what is caled in theliterature "target collision resistant" or
> >"one-way hash").
> > > *Wouldn't it make sense to modify some of the standards along this

---

From: "D. J. Bernstein" <[email-masked]>
Date: 17 Mar 2005 23:25:33 -0000

Shai Halevi writes:
> line?

Why _would_ it make sense? Why should anyone believe that this use of
CPU time and bandwidth is more secure than using a larger hash function?
Would you really be surprised if the attack techniques are extended to
allow some randomness in the input?

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 18 Mar 2005 01:49:50 +0200 (IST)

On 17 Mar 2005, D. J. Bernstein wrote:

> Wouldyou really be surprised if the attack techniques are extended to

This is not just "some randomness in the input".
The point is about WHO chooses the randomness and in what ORDER.
In order to break a signature ALice needs to be able to:
(1) choose m
(2) receive r from Bob
(3) find m' such that H_r(m)=H_r(m')
(Note that Alice must choose m before seeing r and Bob chooses r
independently from m!)

This notion of hashing is DIFFERENT and MUCH WEAKER than collision
resistance. This notion is what many books referred to as
"second-mage resistance" and it's what Naor-Yung called OWH (One-way
hashing) and Bellare-Rogaway call TCR (target collision resistant).
Breaking SHA1 in this sense is far harder than finding collisions.
Also, designing new functions with TCR as the goal should be
significantly easier than designing fully collision resistant functions.

Using this approach can also get as closer to proven encoding schemes for
signatures such as PSS for RSA or DSS with H(m,r) (instead of H(m)).

Hugo

---

From: "D. J. Bernstein" <[email-masked]>
Date: 18 Mar 2005 00:30:39 -0000

> Breaking SHA1 in this sense is far harder than finding collisions.

You'll actually be surprised when the MD5 attack techniques are extended
to break randomized MD5-based signatures? You'll be embarrassed for
having told people to use randomized MD5 rather than spending the same
CPU cycles (not to mention bandwidth) on a larger hash function?

Decades of cryptanalysis keep telling us that extra state bytes and
extra rounds make the attacker's job much more difficult. Do you really
have the same level of confidence in randomization?

I find it difficult to believe that you thought this through before
saying it, so here's a perfect chance for you to clarify your position.

P.S. Yes, we're both talking about the same randomization: the signer
prepends a random number to the message before hashing it. By the way,
when you repeat Rabin's ideas, you should also give Rabin proper credit.
See http://cr.yp.to/bib/entries.html#1979/rabin, page 10.

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 18 Mar 2005 03:41:09 +0200 (IST)

> CPU cycles (not to mention bandwidth) on a larger hash function?

I will not be embarrased at all. If these randomized techniques become
part of the crypto practice I will be very satisfied. The reason is
simple: not only we are raising the bar for the type of break that we need
against SHA-1 (i.e. 2nd primage vs collisions) but we also raise it for
ALL FUTURE DESIGNS. Indeed, if you are going to provide us with a
beautiful new hash function I can already tell you that it is harder to
break it when using randomness than without it (again, this is not
randomness for obscuring things but for lowering the design requirements!)

> have the same level of confidence in randomization?

Actually more. Should I say again that this use of randomness is not to
make the finding of collisions harder but to completely change (and
harden) the attacker's task?

> saying it, so here's a perfect chance for you to clarify your position.

I really appreciate giving me this (probably last) chance.
You'll pardon me (well probably you won't) if I let this opportunity go
by. But, how about trying to convince me that this is a bad idea using
some rational arguments (hopefully free of  derogatory terms and other
"threats")? If you speak with reason you may even convince others.

> See http://cr.yp.to/bib/entries.html#1979/rabin, page 10.

This is one mistake I am willing to immediately correct.
(Do you know that that same year Michael Rabin was my first year's Algebra
professor in the Hebrew University? As you see, I did not learn much ;)

Hugo

---

From: "D. J. Bernstein" <[email-masked]>
Date: 18 Mar 2005 03:24:46 -0000

Hugo Krawczyk writes:
> I can already tell you that it is harder to break it when using
> randomness than without it

How much harder? You're not doing science if your claims aren't clear
enough to be falsifiable. How thoroughly will a cryptanalyst have to
shred randomized MD5 signatures before you admit that you were wrong?

You're asking for something that has a very real cost in CPU time and
bandwidth. Consider, for example, public-key signatures where the signer
prepends 128 bits of randomness to the message before hashing it with
MD5. The randomness needs to be

   * generated by the signer,
   * hashed by the signer,
   * transmitted through the network, and
   * hashed by the receiver,

all of which pumps up the cost of this system to somewhere around the
cost of SHA-256 or more, depending on exactly what cost metric you use.
Do you seriously believe that randomized MD5 is as strong as SHA-256?

You keep claiming that randomized hash-function families (UOWHFs, some
people would say) are easier to design than deterministic hash-function
families (CRHFs). Have you ever actually tried to design one of these
objects? Exactly what aspect of the design, pray tell, is made easier by
this change in standards?

I've spent time on these problems. I'm now offering a $1000 reward for
256-bit collisions in my Salsa10 function. I've often considered the
question of whether lowering my standards from deterministic to
randomized would allow faster functions. I've never seen a way in which
it would, and I've never seen anyone else point out a way. Randomization
doesn't make me comfortable with a smaller state, or with a smaller
number of rounds. _I_ won't be surprised when randomized MD5 signatures
are broken.

There are deeper problems with the whole oracle-separation philosophy
lurking behind your claims. Yes, we have an oracle separation putting
CRHFs above UOWHFs, but we also have an oracle separation putting
public-key encryption systems above public-key signature systems---and
that's completely out of whack with real-world cryptography. Building a
_good_ public-key signature system---not something as bloated as hash
trees---is even more difficult than building a good public-key
encryption system.

The recurring problem here is cost. ``Switch from MD5(m) to MD5(r,m)!''
and ``Switch from AES_k(n) to Twofish_i(RC6_j(AES_k(n)))!'' and ``Switch
from Rabin-Williams signatures to hash trees!'' and ``Switch from direct
use of UOWHFs to trees based on OWFs!'' all sound like perfectly good
ideas if you don't pay attention to cost. But many real-world systems---
enough systems to drive cryptographic standards---simply can't afford
those costs.

I'm not saying that there's any loss of security from randomization. I'm
saying that there's a cost, and that devoting the same resources to
larger hash functions provides much more confidence than devoting them
to randomization.

---

From: [email-masked] (David Wagner)
Date: Fri, 18 Mar 2005 03:42:59 +0000 (UTC)

Seems like the use of randomization (i.e., use of universal one-way hash
functions) is orthogonal to the choice of hash function.  No matter
what hash function you choose, randomization seems like a good idea
if you are going to use that hash function for public-key signatures.
Moreover, these two changes occur at a different level of abstraction;
we might change the specification of the signature scheme to use
randomization no matter what hash function is specified, and then this
change will benefit all uses of that signature scheme.  If you like,
you can think of randomization as a "hedge" against cryptanalysis of
the collision-resistance of the underlying hash.

I heard a concern that randomization has a cost.  I would like
to understand better what that cost is.  If you are talking about
performance, I would expect the performance overhead of randomization
to be negligible compared to the time it takes to compute a signature.
Since we are talking about using randomization in the context of
public-key signatures, performance does not seem like a big deal.
Am I missing something?  Is there some other cost I am overlooking?

---

From: "D. J. Bernstein" <[email-masked]>
Date: 18 Mar 2005 04:56:32 -0000

Exercise for the reader: SHA-512 has been a standard for years, and is
obviously vastly more difficult to break than MD5 and SHA-1. Can you
explain why so few people are using it? Followup: Why would anyone
choose SHA-256 rather than SHA-512?

David Wagner writes:
> Seems like the use of randomization (i.e., use of universal one-way
> hash functions) is orthogonal to the choice of hash function.

If you don't care about cost, you're free to choose any hash function
you want, and then to add randomization. However, in the real world,
cost limits constrain the collection of choices in a complicated way.

> No matter what hash function you choose, randomization seems like a
> good idea if you are going to use that hash function for public-key
> signatures.

If you don't care about cost, then randomization is clearly harmless,
and some people speculate that it's beneficial.

Whenever you see people using SHA-1(m), do you tell them to switch not
just to SHA-1(r,m) but to (SHA-1(r,m),SHA-512(r,m))? After all, if you
don't care about cost, then concatenating SHA-512 is clearly harmless,
and one can speculate that it's beneficial---in fact, (SHA-1,SHA-512) is
generally believed to be _much_ stronger than SHA-1, despite anything
bad that you might have heard about concatenation.

> If you like, you can think of randomization as a "hedge" against
> cryptanalysis of the collision-resistance of the underlying hash.

One could say the same about appending SHA-512 (although it's more like
a brick wall than a hedge, if your other function is SHA-1). Or about
assuming merely that SHA-512 is a OWF, and building a UOWHF by a
gigantic tree of SHA-512 computations. All of this is perfectly
reasonable if you don't care about cost.

> If you are talking about performance, I would expect the performance
> overhead of randomization to be negligible compared to the time it
> takes to compute a signature.

Generating random numbers isn't free. Furthermore, transmitting random
numbers costs bandwidth. Furthermore, in many applications, signature
_verification_ happens much more frequently than signature computation.

One example you should keep in mind is DNS---a critical database of
public information that, after twelve years of discussion, _still_ isn't
protected against forgery. Securing DNS means having busy caches verify
tens of thousands of signatures per second, and fitting those signatures
into UDP packets. Do you think that it's a ``good idea'' to casually
stuff more data into the hashes, and into the packets?

---

From: Michael Silk <[email-masked]>
Date: Thu, 17 Mar 2005 23:39:55 -0800

I don't see the difference between this hashing proposal and HMAC?
Except in this case you skip the XOR'ing part and you don't keep the
key.. and why have you decided not to use HMAC in this case? (or have
I, again, missed something obvious?)

And an implementation note i'm sure we are all aware of: random
numbers are really hard for most companies to get right; and probably
they would (if they were allowed to) use their email, or company name,
or something as the 'random' part.

-- Michael

---

From: Daniel Brown <[email-masked]>
Date: Fri, 18 Mar 2005 09:09:49 -0500

> performance, I would expect the performance overhead of randomization

A slight advantage of computing H(m) instead of H(r|m) is that H(m) can be 
pre-computed.  This can be merely a matter of implementation convenience, 
or a more significant savings if m is to be signed by many parties.

Schemes like DL/ECPVSSR in IEEE 1363a, define r = g^k, where k is random. 
Computing k is quick (obtaining entropy for k is arguably expensive, but 
it may be fine to use a PRNG with enough start-up entropy).  It's 
computing r that is the most expensive step of ElGamal-based signatures. 
Therefore a requirement like H(r|m) introduces a delay before hashing can 
be begin, which could be avoided if hashing was done in parallel to 
computing r = g^k.

One could also just prepend m with some random value "salt", then include 
salt with the signature.  This, however, adds to bandwidth, which may be 
fine in some circumstances and a nuisance in others.  ElGamal-based 
signature schemes are already randomized, so it seems sensible to re-use 
randomization in the hash to save bandwidth and to benefit from the 
security advantages of H(r|m), however debatable those might be. 

By the way, the security of advantage of H(r|m) is not just that it 
reduces dependence on collision-resistance, it is also makes certain kinds 
of security proofs work, especially in the random oracle model, such as 
Pointcheval and Stern's "forking lemma" proof for modified DSA (see also 
http://www.cacr.math.uwaterloo.ca/techreports/2000/corr2000-39.pdf).  On 
the other hand, addition of r into the hash also interferes certain other 
kinds of security proofs (see 
http://www.cacr.math.uwaterloo.ca/conferences/2001/ecc/brown.ps).

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 18 Mar 2005 18:18:22 +0200 (IST)

> I, again, missed something obvious?)

Adding to Shai's response let me first say that I have found
myself innumerable times convincing people not to use hmac,
what's wrong with me? :)

More seriously, let me clarify some points.

(1) The proven security of HMAC (as a MAC or even PRF) is irrelevant to
this application (though, one may be able to derive some relevant
properties from our paper with Dodis et al from last crypto)

(2) The main objection to HMAC here is its added computation. The
argument against this objection is that since we are talking about
computing signatures then the additional two-block hashing required by
HMAC (relative to just H(r,m)) is negligible. This is even true for RSA
verification with short exponent.

(3) A purely heuristic advantage of HMAC is that the job of the
cryptanalyst is made much harder. It now needs to find m, then receive r
and now find m' such that H(r|H(r|m))= H(r|H(r,m')) so the attacker needs
to be able to simultaneously control both h=H(r|m') and the resultant H(r|h).
This would probably require an algortihm that fully inverts H on more or
less every output (not to speak of the need to invert H in a way that the
found preimage, m', be of any use to the attacker).

(4) Probably the main advantage of HMAC is its availability in most
systems today. You can re-use its implementation and interface.

So, after all, using HMAC may be a good idea...

> or something as the 'random' part.

I do not dismiss the problems with pseudo-random generation. But as Shai
said once you get a single good key (or seed)  you can generate many
pseudo-random bits via a pseudo-random generator or PRF. Hopefully, heavy
signers such as CAs will be able to have some good randomness generators.
And even lighter cryptographic systems will need to have random generators
for many other cryptographic uses (such as generating keys, nonces and
the like). And, as usual, there is many ways a bad implementation will
break even the best crypto.

Hugo

---

From: "D. J. Bernstein" <[email-masked]>
Date: 18 Mar 2005 17:43:17 -0000

Daniel Brown writes:
> of security proofs work, especially in the random oracle model

The randomization certainly allows ``weaker'' assumptions about, e.g.,
RSA. However, as Koblitz and Menezes have explained in detail, there's
no reason to believe that the ``weaker'' RSA assumptions are any harder
to break---i.e., that this extra cost produces any extra security. See
http://eprint.iacr.org/2004/152, especially the section ``Pass on PSS.''

Katz and Wang showed a couple of years ago that, if r is generated
deterministically (as proposed by Barwood and Wigley), then any length
of r down to one bit allows a tight security proof under the ``weaker''
RSA assumptions. This eliminates most of the costs of relying on the
``weaker'' RSA assumptions. See http://cr.yp.to/papers.html#rwtight for
a variant that covers Rabin-Williams, and a detailed discussion of
several cost issues.

A short r does _not_ let us rely on ``weaker'' H assumptions, namely
UOWHF instead of CRHF. Systems using the ``weaker'' H assumptions have
the same basic problem as non-Katz-Wang systems using the ``weaker'' RSA
assumptions, such as PSS: they incur very real costs for users in
exchange for a purely speculative improvement in security.

---

From: david jacobson <[email-masked]>
Date: Fri, 18 Mar 2005 11:17:24 -0800

> or something as the 'random' part.

As to the last paragraph, I think the upcoming ANSI X9.82 standard on
random number generation will help.  (This discussion is getting way too
heated and needs to be spun off on a tangent :-) ).

Companies respond to market pressure---customers have to be asking for
something, or it has to be seen as a way to differentiate the company's
product from its competitors' products.  Most customers don't know they
need a source of quality random nubmers, those who do don't have a short
name for it, and it isn't showing up as a column heading in
comparisions.  So it doesn't get done.

When the standard comes out, the phrase will be "ANSI X9.82 compliant".
 Customers can ask for it.  Companies can claim it.  Companies will have
guidance in how to do it.

  -- David Jacobson

---

From: [email-masked] (David Wagner)
Date: Fri, 18 Mar 2005 19:35:37 +0000 (UTC)

D. J. Bernstein wrote:
>explain why so few people are using it?

I don't know how others choose between hash functions, but I can tell you
some of my reasoning, if that is relevant.  I know SHA1 well; I have spent
time trying to cryptanalyze SHA1; I have spoken to others who have done
the same.  I can't say the same for SHA-256 or SHA-512.  While SHA-256
or SHA-512 may well be better, that has made me reluctant to switch to
a hash function that I understand less well.  However, I may well be
forced to overcome my reluctance, given the recent results on SHA1.

---

From: [email-masked] (David Wagner)
Date: Sat, 19 Mar 2005 08:22:46 +0000 (UTC)

D. J. Bernstein wrote:
>don't care about cost, then concatenating SHA-512 is clearly harmless, [...]

A minor nitpick: Concatenating hashes is not necessarily harmless.
It is harmless to collision-resistance, because the concatenation
is as strong as the stronger of the two components when it comes to
collision-resistance.  However, it might (at least in principle) be
harmful to one-wayness, because the concatenation is only as strong
as the weaker of the two components when it comes to one-wayness.
This is tangential to your main point, but I thought I'd bring it up,
as it illustrates that combining two hash functions is not an entirely
trivial task.

---

From: [email-masked] (David Wagner)
Date: Sat, 19 Mar 2005 08:51:16 +0000 (UTC)

>_verification_ happens much more frequently than signature computation.

Thanks for articulating the costs that you were concerned about.
But I still don't see what the problem is.  For many applications,
this just doesn't sound like a big deal.  Let's try to analyze the
costs quantitatively.

How long a salt do we need?  80 bits seems likely to be more than
adequate.  It will be possible to break the UOWHF/TCF properties
in an online attack requiring on the order of 2^80 chosen messages,
but such attacks seem totally infeasible.  80 bits may be overkill,
and many applications may be able to get by with shorter applications
(say, 64-bit salts), but let's go with the 80-bit figure for now.

Is the bandwidth overhead significant?  No, probably not.  If we use
2048-bit RSA, then a 80-bit salt adds 4% overhead to signature sizes.
If we use 1024-bit RSA, then a 64-bit salt adds 6% overhead to signature
sizes.  If we use 512-bit RSA, we're screwed anyway.  Overheads of this
magnitude seem unlikely to be a big deal for most applications.

Of course, there are certainly some signature schemes where the overhead
is much larger.  For instance, if we are using 160-bit ECC with point
compression in an effort to minimize signature sizes, then an 80-bit salt
adds 50% overhead to signature sizes -- which is likely to be unacceptable
to systems that are sensitive to signature sizes.  So for some systems,
randomization will be inappropriate because of its bandwidth overhead.

Is the latency overhead significant?  I doubt it, for most applications.
The cost of hashing 80 extra bits is a few hundred cycles, which is
negligible compared to the cost of signature generation.  As for signature
verification, `openssl speed rsa1024` says my CPU takes about a hundred
thousand cycles per 1024-bit RSA signature verification operation.
This means that the latency cost of randomization would be essentially
negligible for these signature schemes.

Of course, there may be the occasional signature scheme where the CPU cost
of randomization is not entirely negligible.  Perhaps the signature scheme
with the fastest secure verification is 1024-bit Rabin (or variants).
How fast is signature verification with such schemes?  Thousands of
cycles?  If so, randomization would contribute a 10% overhead to the
time to perform a signature verification -- non-negligible, to be sure,
but whether that is a showstopper will depend on the application.

Is the cost of generating random bits significant?  I don't see how
it could be.  Just use a PRG.  Any crypto implementation already
needs crypto-strength (pseudo)random bits for other purposes anyway.
I honestly don't see what the issue here might be.

My tentative conclusion: The costs seem likely to be small for most
applications.

For a few applications which try to squeeze out every last cycle
of CPU and every last bit of signature length -- applications where
performance is of absolute paramount importance -- randomization will be
inappropriate.  Those applications will need to find some other defense
against collision attacks on the hash function, or will need to accept
the higher level of risk.

However, for most applications -- applications where security is a higher
priority -- randomization seems like a reasonable countermeasure to have
in your toolbox.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 19 Mar 2005 10:22:46 -0000

David Wagner writes:
> 80 bits seems likely to be more than adequate.

Will you be surprised when 64-bit-randomized MD5 and 80-bit-randomized
SHA-1 are broken? I certainly won't.

> It will be possible to break the UOWHF/TCF properties
> but such attacks seem totally infeasible.

I wonder how many times I'm going to have to say ``TCR is the wrong
problem'' before it sinks in.

> If we use 1024-bit RSA, then a 64-bit salt adds 6% overhead to
> signature sizes.

You're drawing a completely inaccurate picture of the state of the art.
1024-bit Rabin-Williams signatures with Bleichenbacher compression take
only 520 bits. Furthermore, other types of signatures are even smaller.
Furthermore, as noted above, everyone else is talking about 160 bits of
randomization.

Similar comments apply to your discussion of verification speed.

> it could be.  Just use a PRG.

Funny, I don't see a ``PRG'' feature in my RSA chip.

Yes, we can compute MD5(r,m) where r is MD5(s,m) and s is a secret, but
that's more than twice as expensive as computing MD5(m).

> My tentative conclusion: The costs seem likely to be small for most

It's pointless to discuss this unless you define ``small.'' Is the cost
of switching to SHA-256 ``small''? How about SHA-512?

If randomized MD5 is more expensive than deterministic SHA-256, and if
nobody is willing to claim that it's as secure as deterministic SHA-256,
then switching to randomized MD5 is obviously silly.

Your response might be that we should use _randomized_ SHA-256. But if
randomized SHA-256 is more expensive than deterministic SHA-512, and if
nobody is willing to claim that randomized SHA-256 is as secure as
deterministic SHA-512, then switching to randomized SHA-256 is obviously
silly.

What some people keep doing wrong in this discussion is comparing the
(speculative) security of randomized MD5 to the (pathetic) security of
deterministic MD5---as if those were the only two options! There are, in
fact, many options at each cost level. Saying ``We think you can achieve
higher security at higher cost'' is content-free; it is of no help for
users choosing a system.