Why is Pearson hash not used as a cryptographic hash?

Question

The original algorithm produces 1 byte long hash and is (of course) not suitable for cryptography use.

But according to wikipedia, it is possible and easy to produce Pearson hash of any length, simply by increment the first byte of the message for every next byte of the hash.

Also, if the encoding array is filled with real random numbers it will guarantee very high quality of the produced hash.

So, why this hash function is not widely used in the cryptography algorithms?

Edit1:

I have made some tests of the avalanche effect of the Pearson hash with the following byte array, generated by the https://www.random.org/lists:

141, 227, 251,   2, 201, 179,  30,  63,  93, 145,  92,  46,   6,  95, 105,   1
 90, 112,  60,  84, 110, 205,   0, 253, 215, 118, 244, 218, 231,  31, 192,  67
189,  23,  66, 144,  59, 115, 248, 237, 216,  82, 217,  72, 147, 143, 125, 170
152, 154,  57,   4,  44, 131, 157, 111, 209, 185,  35,  81,  41, 182, 202, 176
113, 193, 114, 254,  39, 194,  94, 190,  37,  42,  15, 195, 188, 169,  12,   7
175,  88, 245, 127, 203, 135, 181, 178,  99, 164,  76, 235,  21,  86, 160, 243
223, 126, 136, 129,  77, 239, 132, 174, 122, 233,  87, 108,  47, 146, 158, 128
 97, 162, 219,  91, 229, 222, 104,  71, 150,  55, 242,  75, 151, 206, 119,  36
 58, 236, 117,  43,  74, 155, 246, 116, 153, 148,  68, 159, 210, 161,  19,  64
247, 186,  83,  29,   5, 249, 177, 196, 250, 197, 167, 230,  26, 134, 124, 240
 69, 149,  65,  62, 101,  38, 183,  45,  24, 166,  33, 123, 207, 107, 241, 191
208,  85,  78, 184,  32,  89,  20, 165,  27,  22,  11, 130,  98,  80,  17, 198
200, 211,  16, 100,  51, 232,   3,  96,  73, 187,  14,  53, 121, 199,  18, 103
228, 180, 156, 252, 168,  49,   8, 171,  79, 204,  10, 139,  40,  61, 220, 212
 13, 221, 109,  25, 255, 120,  70,  28,  48, 213, 234,  50, 138,   9,  52, 142
225, 172, 106,  54, 214, 163, 140,  34, 238, 224,  56, 226, 102, 137, 133, 173

After changing single bit of the message the hash function changes in the different cases from 110 to 150 bits of the 256bit hash generated.

Edit2:

Thanks to the analysis of CodesInChaos it is obvious, that the multibyte hash, as described in the wikipedia has serious flaws with the non repeating bytes in the result and in revers full repeating of the hash after the 256th byte.

But it seems that this is not a flaw of the Pearson hash by itself, but a problem of the algorithm for multibyte hash combining. All this is because the value of h in the below code is cleared to fixed value for every byte of the result by the line: h = T[x[0] + j) % 256];

  for (j = 0; j < 8; j++) {
     unsigned char h = T[(x[0] + j) % 256];
     for (i = 1; i < len; i++) {
        h = T[h ^ x[i]];
     }
     hh[j] = h;
  }

But this problem has simple solution - don't reset the value of h after the inner loop. I tried with the following formula: h = T[((h+j)%256 ^ x[0])]. In my test it show repeating bytes in the result, non repeating of the hash after the 256th byte and still very good avalanche effect. The code of the modified function is (C#):

        byte h = 0;
        for (j = 7; j >=0; j--)
        {
            //h = T[(x[0] + j) % 256];
            h = T[((h + j)%256 ^ x[0])]; 
            for (i = x.Length-1; i > 0; i--)
            {
                h = T[h ^ x[i]];
            }
            hh[j] = h;
        }
        return hh;

Answer 1

Observation:

An individual 1-byte pearson hash behaves like an 8 bit block cipher, encrypting the initial state using the message as key. This means that given a fixed message, each possible initial state produces a different output. This implies that a combined hash will never contain duplicate bytes.

Without this property a hash would forget about the initial state after about 1.5 kB and the combined hash would consist of identical bytes, degrading its quality to that of a single byte hash.

Never producing identical bytes is a trivial distinguishing attack, but in exchange you get a hash that doesn't produce a lot of collisions by accident.

Meet-in-the-middle attack to find pre-images:

Since the mapping between previous and next state is bijective and efficiently computable, a meet-in-the-middle attack, can find pre-images of an n bit hash in $2^{n/2}$ time, similar to how 2DES can be broken by a meet-in-the-middle attack. This is feasible for 64 bit hashes. The sponge construction used in SHA-3 suffers from a similar attack, which is why the capacity needs to be at least twice the desired pre-image size.

Pre-image attack by finding a fixed point:

The message we're targetting is called $m_0$. We're searching for a suffix $m$ such that $h(m_0)=h(m_0||m)$. This is a second pre-image on $m_0$ using that $m$ preserves the state.

We start with $n$ short messages, which we'll call the alphabet. There are $n^2$ different 2-symbol combinations, of which a fraction of $1/256$ will preserve the initial byte. We try to find about $n$ fixed points, so we need $n\approx 256$ (slightly larger $n$ might be required in practice, to compensate for random deviations).

Once we have enough fixed-points for the first output byte, we extend to two output bytes. For this, we look at sequences which consist of two one-byte fixed-points. All of these combinations are one-byte fixed-points as well, and $1/256$ of them are two-byte fixed points.

Repeating this procedure 8 times, produces an $m$ that preserves the full state. Since each iteration doubles the message length, we'll end up with a message that's 256 times the length of or short single-symbol messages (which consists of one or two bytes each).

For a 128 bit Pearson hash this produces a relatively long message ($2^{16}$ symbols or 100-200kB). You can start with $n\approx 256^2$, fixing two bytes of the hash at the same time, which increases the cost to $\approx 2^{32}$ hashes, which is still feasible. In exchange for the higher runtime, it reduces the message length back to 256 symbols or 500-1000 bytes.

As poncho pointed out, this attack can easily be adapted to first pre-images.

A quick and dirty implementation of this attack is available at: https://gist.github.com/CodesInChaos/4a399a26b98221155a92

My code naively enumerates all $n^2$ combinations and filters out the approximately $n$ that produce the desired result. Running the hash function in reverse to execute a meet-in-the-middle attack, it's possible to reduce these $n^2$ hash computations down to about $n$ hash computations. This optimization doubles the length of the hash you can break with a given cost and message size. So breaking 128 bit hash should have a cost of about $2^{16}$ hashes and breaking a 256 bit hash about $2^{32}$ hashes, where each message is about 1 kB.

Concerning your "improved" version:

The second pre-image attack above works without any changes to the attack code. Just replace the hash function with the "improved" version.

Answer 2

Because it is not secure enough.

Hash functions rely a lot on diffusion (a single bit change must change half of the other bits) and confusion (the value of a bit should depend on the value of other bits). This is also known as the avalanche effect.

Because it lacks a permutation, my first intuition: it lacks diffusion and has weakness to differential cryptanalysis. I also guess there will be a correlation between each pack of 8 bits: see line 25 in the source provided by wikipedia:

24       for (j = 0; j < 8; j++) {
25          unsigned char h = T[(x[0] + j) % 256];
26          for (i = 1; i < len; i++) {
27             h = T[h ^ x[i]];
28          }
29          hh[j] = h;
30       }

if the encoding array is filled with real random numbers it will guarantee very high quality of the produced hash.

That is not enough: the S-box has to be securely design (just random number if you refer to the wikipedia). Example DES: how the values where chosen with their cryptanalysis resistance. Moreover the substitution table has to be the same for everyone. The differential analysis of the table provided by wikipedia led to the following probabilities :

 00000101 => 00100010 : 10 / 256
 00100100 => 01100010 : 10 / 256
 00100100 => 11100110 : 10 / 256
 00011100 => 11100001 : 10 / 256
 00111111 => 10011011 : 10 / 256
 00100001 => 01011100 : 10 / 256
 01010010 => 10110111 : 10 / 256
 01011011 => 11010010 : 10 / 256
 01100011 => 11101110 : 10 / 256
 11001111 => 11110101 : 10 / 256
 11011000 => 10000100 : 10 / 256
 01110100 => 00101011 : 10 / 256
 01111011 => 00110111 : 10 / 256
 01111110 => 10000010 : 10 / 256
 01111111 => 11000011 : 10 / 256
 10110110 => 01000000 : 10 / 256
 11111001 => 00001101 : 10 / 256
 11101010 => 00001000 : 12 / 256

As a scale, AES S-box (optimized) probabilities are never higher than 4/256.

For the second preimage attack see CodeInChaos' answer.