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


Relevant Pages

  • A poormans block encryption algorithm
    ... scenario where two partners agree on a secret key for block encryption ... under the circumstance that one of them has to implement the algorithm ... coefficients can be generated from the given secret key by ...
    (sci.crypt)
  • Re: Pin generation algorithm question
    ... the pin-generation system. ... PINs required becomes important. ... By "the algorithm," do you mean the PIN-generating algorithm, ... And you use the same algorithm and secret key in the field to verify ...
    (sci.crypt)
  • Re: Learning cryptanalysis
    ... he picks an algo in function of the date/time and the secret key, ... Even you idea of a one time algorithm is flawed and I will give you the complete reason: There has been available for more than a century a perfect algorithm which is totally unbreakable - it is the One Time Pad. ... The OTP is rarely or never used because the problem of distributing the keys is insolvable - the cost is so prohibitive that only governments use it and even then they use it only for their most important messages, certainly much less than one message in a million. ...
    (sci.crypt)
  • Re: A question about passwords and login/authentication
    ... The DES algorithm is a secret key algorithm (so the same key is used ... comunication between Windows and SAMBA and "how does one determine ... For SAMBA on a linux: the authentification is determinate by the ...
    (Focus-Linux)