[OT] Reasons not to use multiple hash functions for "more security"

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Matthieu Moy wrote:
> John Arbash Meinel <john at arbash-meinel.com> writes:
> 
>> 2) Much worse than a single well designed hash of the total length. So
>> even with (1) you end up with an additive function rather than
>> multiplicative. In the case of SHA1 + MD5 the complexity should be:
>>
>>   m*2^(n/2) + 2^(m/2)
>>
>>   (128)*2^(160/2) + 2^(128/2)
>>   = 128 * 2^80 + 2^64
>>   = 2^7 * 2^80 + 2^64
>>   = 2^87 + 2^64
> 
> This is considering the case of brute-force. If coliding SHA1 is
> actually 2^87, you can consider it safe, period.

Actually I think you missed my point. I'm not saying that SHA1 + MD5 is
weaker than either SHA1 or MD5. It is, in fact, stronger.

A hash has a security bound of 2^(m/2) where 'm' is the number of bits.
(It would be 'm' except for the birthday paradox).

The problem is that if you have H(x) = SHA1(x) || MD5(x)

You have a hash of length "m+n" bits. Which *should* have a security
bound of 2^((m+n)/2)

In the case of SHA1 + MD5 that should be 160+128 = 288 / 2 = 144.

So 2^144 *should* be the security bound of SHA1 + MD5.

The paper discusses why this isn't the case, and why it is actually 2^87.

Now, I may be a little wrong but 2^87 <<<<<<< 2^144. Which is why
instead of combining SHA1 and MD5, you *should* use SHA256. Because it
uses fewer bits (256 < 288) and it has a much higher security bound
(2^128 >>>> 2^87).

> 
> Now, if someone clever finds a way to colide SHA1 in n, log(n) or so,
> then, one of the element in your sum becomes negligible, and the
> important is to keep the other. So, having two hash functions might
> not give you a 2^{enough}, but if the hash functions are sufficiently
> different, the probability to have non-brute-force attack on both is
> really smaller than the individual.
> 
> And another technical advantage of having two functions is that the
> transition to a new function is made easier when one is considered
> broken : if version N of your software considers hash1 and hash2
> function, the day hash1 is broken, you can release version N+1
> managing hash2 and hash3, and version N and N+1 have hash2 in common,
> which is still considered secure at this point.
> 

Well, I can agree that if someone changes it from 2^(m/2) to something
like 2^(log(m)) we get pretty hosed by that hash.

However, almost all of the breaks I've heard of are more of the form
2^(m/2 - X).

For example, SHA1 is considered "broken" because there is a theoretical
attack that takes only ~2^63 (versus 2^80). We can look at this as
either a factor (63/80 =~ 80%) or a subtraction (80-63=17). Note that
even "broken" it has almost the same security bound as unbroken MD5
(2^64). I think MD5 has actually been broken down into something like
2^40 or less, and can actually generate collisions on a single users
machine in a weekend.

Either way, if you were looking at SHA1+MD5 it lowers your security
bound to lets say: 87*.8 = 69.

On the other hand, if you had started with SHA256 that would be 128*.8 =
102.

Again, if there is a similar type of attack that breaks SHA256 you are
still better off (larger security margin) than with SHA1 + MD5.


If we go back to the original equation:
  m*2^(n/2) + 2^(m/2)

We can say this is:

  lengthofshorthash * securityoflonghash + securityofshorthash

So if we take SHA1 + MD5 and consider SHA1 "broken" we might end up with

  128 * 2^63 + 2^64
  2^7 * 2^63 + 2^64 =~ 2^70
or
  160 * 2^64 + 2^63
  2^7.3 * 2^64 + 2^63 =~ 2^72.3


I haven't followed the deep math, so I'm sure there are subtle problems
with my approximations. But I'm guessing they will be in the same ballpark.

I understand your point of "rolling" hashes. So you feel like you always
have 1 hash which isn't broken. But remember, there really isn't any
sort of broken that changes something which should be 2^80 into
something which is 2^0. [O(1)]. Maybe quantum computing could, but I
haven't really heard it as claiming to be able to do that.

(In my mind it seems like if you could get N quantum bits entangle to
give you an M bit hash, it could theoretically try all possible inputs
of N bits at the same time, but I guess you still wouldn't have known
what the input was, because you only evaluated the output. So what you
need is to reverse the hash so that for an M bit hash you get all
possible combinations of N bits that could have generated it...)


I kind of like that crypto people consider a hash "broken" when it
starts to not perform like a perfect "ideal" hash. But it might be
better to consider them "weakened". But then you would have to decide
what margin is considered "broken" after you have been weakened.

Pick a security bound, pick anything you want, 2^64? 2^128? If you are
happy with 2^128 I'm pretty damn sure that you could just use SHA512,
and for the rest of your life and probably many many many many
generations to come, you still will maintain your 2^128 security bound.
Theoretically, SHA512 has a bound of 2^256 and it takes a lot of
weakening to get from 2^256 to 2^128.


Also, in my best guess 2^64 is a great security bound, as long as it
isn't weakened. Remember, if you try 1 per second it takes 584 billion
years to break 2^64. Put another way, if you try 1 every nanosecond, it
still takes 584 *years*.
Which is why nobody has proven that SHA1 has a collision in 2^63,
because even though it is a lot less than 2^80, it still takes far to
long to actually perform an attack.

So if you say in the future we will have petaflop computers (10^15
ops/sec) and they take 1 cycle to check a sha hash. It would take
2^63 / 2^50 = 2^13 = 2 hours to check for a collision in SHA1. Without
the break it would be 2^(80-50) = 34 years. So you can see that SHA1
really is "broken" at least if you have a petaflop computer. :)


So really, pick your security bound, go above it by a good margin with a
peer reviewed hash, and then I really don't think you need to worry.

My vote would be for using SHA256 where possible (it is actually a
configuration you can set for gpg, but it doesn't completely help us,
because we are signing a sha1 hash of the content, so bzr would have to
switch to sha256 internally first).

John
=:->

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFFtNuwJdeBCYSNAAMRAjLIAJ4/WfhsLCC1WN3sJJcZDghtTt1N/wCePilS
CNC+EigW5OkS/O/QEuwZKx4=
=JLKe
-----END PGP SIGNATURE-----