Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:03 ADT
Adam Back (aba@dcs.ex.ac.uk)
Wed, 1 Jul 1998 22:29:21 +0100
Alex Alten writes:
> You can't just truncate blindly. You need to understand how the
> hash is internally constructed and operates. On paper you may be
> improving the strength in one area, even in the limited case you
> mention above, however in fact you may have reduced it too much in
> another.
I would think that truncation of a hash (being used as a cryptographic
checksum, for example for input to a digital signature function)
should reduce the strength as expected for any reasonable hash which
did a decent job of:
- providing collision resistance (making it ideally hard to find x and
x', x != x', st h(x) = h(x'))
- providing diffusion (that changing a given bit of the input gives a
50% chance of each output bit changing)
- providing the property that all output bits are equally hard to
find collisions on
So discarding 1 bit of hash output reduces the work to find a chosen
collison by factor of 2, and reduces the work of finding an arbitrary
collision (the birthday attack) by a factor of sqrt(2).
For hash functions such as MD5 and SHA1 which have an iterative
function inside the transform function, each bit of the output is
affected by each iteration, so there isn't much difference between by
omitting say leading bits rather than trailing bits. ie the output
bits are approximately equally valuable.
Possibly for broken proprietary hashes the collision resistance and/or
diffusion is so broken that truncation of removal of certain bits
would be worse than removal of other bits. Probably this is what you
were commenting on originally. ("you can't truncate blindly").
> [...] Have you [Perry] actually gone and torn apart a hash to see
> what makes it tick?
Interesting that you should say that because in an earlier (months ago
off-list) discussion with Adam Shostack, I observed the following
based on the internal structure of SHA1:
It is I think marginally better to remove output bits from the right
rather than from the left with SHA1, if you are removing 32 bits or
more. However the effect is pretty marginal for practical purposes,
there is only about 1% difference in it (for inputs of < 56 bytes, ie
1% on the last block, so 2 blocks that is 0.5%, 3 blocks 0.33% etc).
For 64 bits discarded from the left the effect would be about 2%, for
96 bits from the left about 3%, and for 128 bits from the left about
4% (again all divided by the number of input blocks).
I think discarding from the right is as good as mixing the bits back
in with xor for SHA1. The right is where people would I think
normally remove bits from anyway, because it is easier to code.
Adam
--
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:03 ADT