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

namespace PearsonBreaker
{
    // (C) 2016 CodesInChaos, released under MIT license
    // A second 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
    public class Program
    {
        public static void Main()
        {
            bool debug = false; // print debug output
            var m0 = new byte [1] {10}; //, 20, 30, 40, 50, 60, 70, 80, 90, 100}; // prefix / message whose hash we want to match
            int maxAlphabet = 280; // limit the alphabet size to this
            var alphabet = alphabetLetters.Take(maxAlphabet).ToArray(); // choose from alphabet1 / alphabet2 / alphabetLetters

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

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

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

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

            var fullSuffix = alphabet.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: " + h0.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[][] alphabetLetters = Combinations(Enumerable.Range('A', 26).Select(i => new byte[] { (byte)i }).ToArray()).ToArray(); // two letters

        static IEnumerable<byte[]> Combinations(ICollection<byte[]> alphabet)
        {
            foreach (var x in alphabet)
            {
                foreach (var y in alphabet)
                {
                    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] {
                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

                // 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 = 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;
        }
    }
}