2010/12/3 Permjacov Evgeniy
*/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.