[Haskell-cafe] Digests

[Serguey Zefirov]

2010/12/3 Permjacov Evgeniy <permeakra at gmail.com>:
>>> */me wrote it into to_read list. The problem is, however, that block
>>> ciphers are quite unfriendly to plain word8 streams. It is not a deadly
>>> problem, but i'd like to avoid block collections.
>> All one-way hashes do block collections. This is unavoidable.
> Why ? Is there some math behind this proposition ?

This is hard - to add single byte into the sum with cryptographic (or
near cryptographic) security. To quote Wikipedia again: "The avalanche
effect is evident if, when an input is changed slightly (for example,
flipping a single bit) the output changes significantly (e.g., half
the output bits flip)."

http://en.wikipedia.org/wiki/Avalanche_effect

This is true for hashes too. Hash should change about half of the
random output bits when single bit of input changes. Especially if you
aim to tamper-proof hashes. You have to have that property on every
round of hashing, because you don't know when to stop. For bytes, you
have to guarantee that you get an avalanche effect for every byte - it
means, that you have to transform your entire block plus input byte in
an expensive way. MD5 and all other hashes have internal state of
various size, they all keep input blocks to make hashing transform
less expensive.

Fast methods like sum-modulo-poly (CRC variants) or linear
congruential generators do not have good avalanche property when used
for stream hashing or encryption. Even their combination (one in ZIP
encryption) wasn't strong enough.