Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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;
share|improve this question
    
Such a hash never contains duplicate bytes. That's a distinguisher attack, but it prevented the collision attack I was looking for. – CodesInChaos Mar 15 at 10:51
1  
Cool exercise of cryptanalysis :) – cygnusv Mar 15 at 11:10
    
@CodesInChaos IMO, Pearson hash can contain duplicate bytes. Why not? – johnfound Mar 15 at 11:49
    
@johnfound: If your byte array is actually a permutation, the hash can be run backwards, proving that if there are duplicates bytes in the output they would need to come from duplicates initial bytes -- and "simply increment the first byte of the message for every next byte of hash" implies that the initial bytes won't have duplicates. – Henning Makholm Mar 15 at 12:55
    
@HenningMakholm - Every next byte in the hash is actually one byte Pearson hash of different input message. As long as the one byte hashes have very big collision rate, then you can have duplicated bytes in the hash. Imagine hash with length more than 256 bytes. In such hash you will get duplicated bytes in every hash value. – johnfound Mar 15 at 13:05
up vote 21 down vote accepted

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.

share|improve this answer
    
Nice one. It also wouldn't look that difficult to turn this into a preimage attack; first set the first byte to the desired value, and then look for $n$ sequences that preserve that first byte, and find one that sets the second byte to what we want, and continue on until we've set all the bytes... – poncho Mar 15 at 15:24
    
@poncho Generalized the code to include a first pre-image attack like that. – CodesInChaos Mar 15 at 17:37
    
After some changes to the hash (I implemented in C# my code that is in assembly language) I started to get runtime error: Sequence contains no elements at line 39. Is it possible to fix it? The whole code is on: pastebin.com/hbzZWspZ – johnfound Mar 15 at 18:11
    
@johnfound Your running the j loop in the hash backwards breaks the attack code. (That does not mean the change is a security improvement) – CodesInChaos Mar 15 at 18:42
    
@CodesInChaos I understand. It was good exercise for me. – johnfound Mar 15 at 18:56

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.

share|improve this answer
    
I made some tests with randomized array (from random.org) and get always from 114 to 152 changed bits on a single changed bit in the message for a 256bit hash. Which seems to be very good for the avalanche effect. Isn't it? – johnfound Mar 15 at 11:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.