[Haskell-cafe] Digests

[Permjacov Evgeniy]

On 12/03/2010 11:40 AM, Serguey Zefirov wrote:
> 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)."
This simply means, that active set of bits must be at least of the size
of final value and value to be added must be added somehow to every byte
in active set. The simplest way to do it is multiplication of vector
[active-state-bits++current-byte] and some matrix of size [resulting
bytes count|resulting bytes count + 1] (of cource, not in floating-point
math, but, for example, using modulo-256 arithmetic or even hand-coded
tables for "mul" and "sum"). This, of course, means, that byte-streaming
hashes needs some initial seed (that must be paired with resulting value
to check) and that every byte will cause much operations to perform,
resulting in poor performance. So, the conclusion is: byte-streaming
hashes are possible, but because of requirements definitly will have
poor performance, much worse then block ones. Am I correct?
> 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.