Re: HELP: Need a simple hash function

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 01/13/04


Date: 12 Jan 2004 16:28:29 -0800

In article <goFMb.120033$AAe1.10015@news01.bloor.is.net.cable.rogers.com>,
Tom St Denis <tomstdenis@iahu.ca> wrote:
>
>"Phil Frisbie, Jr." <phil@hawksoft.com> wrote in message
>news:1gFMb.8213$XF6.178002@typhoon.sonic.net...
>> Tom St Denis wrote:
>>
>> > "Phil Frisbie, Jr." <phil@hawksoft.com> wrote in message
>> > news:yABMb.8177$XF6.176952@typhoon.sonic.net...
>> >
>> >>Or 'fold' the 128 bits down to 32 with XORs.
>> >
>> > Technically there is zero benefit in doing that provided you assume
>SHA-1 is
>> > a secure one-way function [which you have to assume in your model
>anyways].
>>
>> That is what I thought until I came across a paper a few months ago
>recommending
>> folding rather than truncating. I think they were using MD5 if that makes
>any
>> difference...
>
>Then they have a proof the hash isn't secure.

Not necessarily. In practical security, it is
quite often useful to adopt a
"belt-and-suspenders" approach, also often called
"defence in depth". As a case in point, there's
only one algorithm in use in 2G cellphones that
isn't broken in practice; it's the hashing
algorithm used in ANSI-41 systems for
authentication and key derivation. (It's called
CAVE for "Cellular Authentication and Voice
Encryption" although it does key derivation
rather than encryption.)

The idea is to shove all sorts of stuff, including
the secret key, into CAVE, which hashes it and
produces authentication signatures, keys, and so
on.

Now CAVE, the algorithm, is (at least) slightly
broken. If you know its entire output and all the
inputs except for the 64-bit secret key, you can
derive the secret key with 2^56 work. (It may be
more broken than that, who knows?) But anyway, it
turns out that if you are missing just some of
the output bits, you can basically guess them and
push an attack through. But the output bits are
actually XOR-folded, and that happens to prevent
the known attack.

So, I agree that "if there's a difference between
folding and truncating, the algorithm is
broken.". But that doesn't mean that it might
not be advantageous, in practice, to fold anyway.
Taken to an extreme, Patel and Ramzan (from
memory, might be wrong) propose a linear
transform that makes all the bits equally safe...
folding with XOR or whatever is a simple case of
this. It gives some level of protection if the
algorithm *does* turn out subsequently to be
broken.

Greg.

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au