Finds second pre-images on the pearson hash

pearson-breaker.cs

// (C) 2016 CodesInChaos, released under MIT license
// A pre-image attack against the (non cryptographic) Pearson hash https://en.wikipedia.org/wiki/Pearson_hashing
// see http://crypto.stackexchange.com/a/33724/180 for a description

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PearsonBreaker
{
    public class Program
    {
        public static void Main()
        {
            bool debug = true; // print debug output
            var m0 = new byte[] { 0 };
            var targetHash = Pearson16(new byte[] { 1 });// use Pearson16(m0) for a second pre-image attack
            int maxAlphabet = 280; // limit the alphabet size to this
            var alphabet = alphabetLetters2.Take(maxAlphabet).ToArray(); // choose from alphabet1 / alphabet2 / alphabetLetters2

            var h0 = Pearson16(m0);
            Console.WriteLine("Target Hash: " + BitConverter.ToString(targetHash));

            Func<byte[], int, byte[], bool> check = (m, count, target) => Pearson16(m0.Concat(m).ToArray()).Take(count).SequenceEqual(target.Take(count));

            var projections = alphabet;
            var fixedPoints = alphabet;
            for (int i = 1; i <= h0.Length; i++)
            {
                var fixedPoints2 = Combinations(fixedPoints, fixedPoints).Where(m => check(m, i, h0)).Take(maxAlphabet).ToArray();
                var projections2 = Combinations(fixedPoints, projections).Where(m => check(m, i, targetHash)).Take(maxAlphabet).ToArray();

                fixedPoints = fixedPoints2;
                projections = projections2;

                if (debug)
                {
                    Console.WriteLine(i);
                    Console.WriteLine(fixedPoints.Length + " " + projections.Length);
                    Console.WriteLine(alphabet.First().Length);
                    Console.WriteLine(BitConverter.ToString(Pearson16(m0.Concat(projections.First()).ToArray())));
                    Console.WriteLine();
                }
            }

            var fullSuffix = projections.First();
            var combinedMessage = m0.Concat(fullSuffix).ToArray();
            var attackHash = Pearson16(combinedMessage);

            Console.WriteLine("Suffix (hex): " + BitConverter.ToString(fullSuffix));
            Console.WriteLine("Suffix (text): " + Encoding.ASCII.GetString(fullSuffix));
            Console.WriteLine("Success: " + targetHash.SequenceEqual(attackHash));
        }

        static byte[][] alphabet1 = Enumerable.Range(0, 1 << 8).Select(i => new byte[] { (byte)i }).ToArray(); // single byte
        static byte[][] alphabet2 = Enumerable.Range(0, 1 << 16).Select(i => BitConverter.GetBytes((byte)i)).ToArray(); // two bytes
        static byte[][] alphabetLetters1 = Enumerable.Range('A', 26).Select(i => new byte[] { (byte)i }).ToArray(); // one letter (too small to use directly)
        static byte[][] alphabetLetters2 = Combinations(alphabetLetters1, alphabetLetters1).ToArray(); // two letters

        static IEnumerable<byte[]> Combinations(ICollection<byte[]> xs, ICollection<byte[]> ys)
        {
            foreach (var x in xs)
            {
                foreach (var y in ys)
                {
                    yield return x.Concat(y).ToArray();
                }
            }
        }

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

            byte h = 0;
            for (j = 0; j < 8; j++)
            {
                h = T[(x[0] + j) % 256];
                //h = T[(h + x[0] + j) % 256]; // johnfound's "improved" version
                for (i = 1; i < x.Length; i++)
                {
                    h = T[h ^ x[i]];
                }
                hh[j] = h;
            }
            return hh;
        }
    }
}