SHARE
TWEET

Untitled

a guest Mar 15th, 2016 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace PearsonBreaker
  7. {
  8.     // (C) 2016 CodesInChaos, released under MIT license
  9.     // A second pre-image attack against the (non cryptographic) Pearson hash https://en.wikipedia.org/wiki/Pearson_hashing
  10.     // see http://crypto.stackexchange.com/a/33724/180 for a description
  11.     public class Program
  12.     {
  13.         public static void Main()
  14.         {
  15.             bool debug = false; // print debug output
  16.             var m0 = new byte [1] {10}; //, 20, 30, 40, 50, 60, 70, 80, 90, 100}; // prefix / message whose hash we want to match
  17.             int maxAlphabet = 280; // limit the alphabet size to this
  18.             var alphabet = alphabetLetters.Take(maxAlphabet).ToArray(); // choose from alphabet1 / alphabet2 / alphabetLetters
  19.  
  20.             var h0 = Pearson16(m0);
  21.             Console.WriteLine("Target Hash: " + BitConverter.ToString(h0));
  22.  
  23.             Func<byte[], int, bool> check = (m, count) => Pearson16(m0.Concat(m).ToArray()).Take(count).SequenceEqual(h0.Take(count));
  24.  
  25.             for (int i = 1; i <= h0.Length; i++)
  26.             {
  27.                 alphabet = Combinations(alphabet).Where(m => check(m, i)).Take(maxAlphabet).ToArray();
  28.  
  29.                 if (debug)
  30.                 {
  31.                     Console.WriteLine(i);
  32.                     Console.WriteLine(alphabet.Length);
  33.                     Console.WriteLine(alphabet.First().Length);
  34.                     Console.WriteLine(BitConverter.ToString(Pearson16(m0.Concat(alphabet.First()).ToArray())));
  35.                     Console.WriteLine();
  36.                 }
  37.             }
  38.  
  39.             var fullSuffix = alphabet.First();
  40.             var combinedMessage = m0.Concat(fullSuffix).ToArray();
  41.             var attackHash = Pearson16(combinedMessage);
  42.  
  43.             Console.WriteLine("Suffix (hex): " + BitConverter.ToString(fullSuffix));
  44.             Console.WriteLine("Suffix (text): " + Encoding.ASCII.GetString(fullSuffix));
  45.             Console.WriteLine("Success: " + h0.SequenceEqual(attackHash));
  46.         }
  47.  
  48.         static byte[][] alphabet1 = Enumerable.Range(0, 1 << 8).Select(i => new byte[] { (byte)i }).ToArray(); // single byte
  49.         static byte[][] alphabet2 = Enumerable.Range(0, 1 << 16).Select(i => BitConverter.GetBytes((byte)i)).ToArray(); // two bytes
  50.         static byte[][] alphabetLetters = Combinations(Enumerable.Range('A', 26).Select(i => new byte[] { (byte)i }).ToArray()).ToArray(); // two letters
  51.  
  52.         static IEnumerable<byte[]> Combinations(ICollection<byte[]> alphabet)
  53.         {
  54.             foreach (var x in alphabet)
  55.             {
  56.                 foreach (var y in alphabet)
  57.                 {
  58.                     yield return x.Concat(y).ToArray();
  59.                 }
  60.             }
  61.         }
  62.  
  63.         // taken from https://en.wikipedia.org/wiki/Pearson_hashing
  64.         static byte[] Pearson16(byte[] x)
  65.         {
  66.             int i, j;
  67.             byte[] hh = new byte[8];
  68.             byte[] T = new byte[256] {
  69.                 141, 227, 251,   2, 201, 179,  30,  63,  93, 145,  92,  46,   6,  95, 105,   1,
  70.                 90, 112,  60,  84, 110, 205,   0, 253, 215, 118, 244, 218, 231,  31, 192,  67,
  71.                 189,  23,  66, 144,  59, 115, 248, 237, 216,  82, 217,  72, 147, 143, 125, 170,
  72.                 152, 154,  57,   4,  44, 131, 157, 111, 209, 185,  35,  81,  41, 182, 202, 176,
  73.                 113, 193, 114, 254,  39, 194,  94, 190,  37,  42,  15, 195, 188, 169,  12,   7,
  74.                 175,  88, 245, 127, 203, 135, 181, 178,  99, 164,  76, 235,  21,  86, 160, 243,
  75.                 223, 126, 136, 129,  77, 239, 132, 174, 122, 233,  87, 108,  47, 146, 158, 128,
  76.                 97, 162, 219,  91, 229, 222, 104,  71, 150,  55, 242,  75, 151, 206, 119,  36,
  77.                 58, 236, 117,  43,  74, 155, 246, 116, 153, 148,  68, 159, 210, 161,  19,  64,
  78.                 247, 186,  83,  29,   5, 249, 177, 196, 250, 197, 167, 230,  26, 134, 124, 240,
  79.                 69, 149,  65,  62, 101,  38, 183,  45,  24, 166,  33, 123, 207, 107, 241, 191,
  80.                 208,  85,  78, 184,  32,  89,  20, 165,  27,  22,  11, 130,  98,  80,  17, 198,
  81.                 200, 211,  16, 100,  51, 232,   3,  96,  73, 187,  14,  53, 121, 199,  18, 103,
  82.                 228, 180, 156, 252, 168,  49,   8, 171,  79, 204,  10, 139,  40,  61, 220, 212,
  83.                 13, 221, 109,  25, 255, 120,  70,  28,  48, 213, 234,  50, 138,   9,  52, 142,
  84.                 225, 172, 106,  54, 214, 163, 140,  34, 238, 224,  56, 226, 102, 137, 133, 173
  85.  
  86.                 // 256 values 0-255 in any (random) order suffices
  87. //              98,  6, 85,150, 36, 23,112,164,135,207,169,  5, 26, 64,165,219, //  1
  88. //              61, 20, 68, 89,130, 63, 52,102, 24,229,132,245, 80,216,195,115, //  2
  89. //              90,168,156,203,177,120,  2,190,188,  7,100,185,174,243,162, 10, //  3
  90. //              237, 18,253,225,  8,208,172,244,255,126,101, 79,145,235,228,121, //  4
  91. //              123,251, 67,250,161,  0,107, 97,241,111,181, 82,249, 33, 69, 55, //  5
  92. //              59,153, 29,  9,213,167, 84, 93, 30, 46, 94, 75,151,114, 73,222, //  6
  93. //              197, 96,210, 45, 16,227,248,202, 51,152,252,125, 81,206,215,186, //  7
  94. //              39,158,178,187,131,136,  1, 49, 50, 17,141, 91, 47,129, 60, 99, //  8
  95. //              154, 35, 86,171,105, 34, 38,200,147, 58, 77,118,173,246, 76,254, //  9
  96. //              133,232,196,144,198,124, 53,  4,108, 74,223,234,134,230,157,139, // 10
  97. //              189,205,199,128,176, 19,211,236,127,192,231, 70,233, 88,146, 44, // 11
  98. //              183,201, 22, 83, 13,214,116,109,159, 32, 95,226,140,220, 57, 12, // 12
  99. //              221, 31,209,182,143, 92,149,184,148, 62,113, 65, 37, 27,106,166, // 13
  100. //              3, 14,204, 72, 21, 41, 56, 66, 28,193, 40,217, 25, 54,179,117, // 14
  101. //              238, 87,240,155,180,170,242,212,191,163, 78,218,137,194,175,110, // 15
  102. //              43,119,224, 71,122,142, 42,160,104, 48,247,103, 15, 11,138,239  // 16
  103.             };
  104.  
  105.             byte h = 0;
  106.             for (j = 7; j >=0; j--)
  107.             {
  108.                 //h = T[(x[0] + j) % 256];
  109.                 h = T[((h + j)%256 ^ x[0])];
  110.                 for (i = x.Length-1; i > 0; i--)
  111.                 {
  112.                     h = T[h ^ x[i]];
  113.                 }
  114.                 hh[j] = h;
  115.             }
  116.             return hh;
  117.         }
  118.     }
  119. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top