Here is my code I'm using to test which Poly cause collisions on a set of test input messages.
The idea would be to come up with a CRC configuration that produces collisions when and only when the mystery algorithm does, then try to build a 65536 entry lookup table between the CRC output and the values the mystery would produce.
It occurs to me I may not even need to be testing Init values in this case
On the first test I ran, I came up with possible Poly of:
0xFD00
0x8000
0x5600
My operating theory is that they chose a terribly "weak" poly that is vulnerable to 16 bit words that are decimal 1, 2, or a multiple of 8, or that its something different than a CRC
Code:
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Runtime.InteropServices.JavaScript.JSType;
namespace CRC_CollisionResearcher
{
internal class Program
{
static byte[] StringToByteArray(string hex)
{
return Enumerable.Range(0, hex.Length)
.Where(x => x % 2 == 0)
.Select(x => Convert.ToByte(hex.Substring(x, 2), 16))
.ToArray();
}
static void Main()
{
string LogPath = "CollisionResearch_FullResults.txt";
string LogPath2 = "CollisionResearch_PolysOnly.txt";
if (File.Exists(LogPath))
{
File.Delete(LogPath);
}
else
{
var LogFileStream = File.Create(LogPath);
LogFileStream.Close();
}
if (!File.Exists(LogPath2))
{
var LogFileStream2 = File.Create(LogPath2);
LogFileStream2.Close();
}
Console.WriteLine("Welcome to CRC Collision Researcher!\n");
Console.WriteLine("You will need 3-7 sample messages with the 16bit checksums removed, that are known to / should result in collisions.\n");
Console.WriteLine("NOTICE: The input messages must be an even number of bytes\n");
Console.WriteLine("How many sample messages would you like to provide?");
int desiredInputs = int.Parse(Console.ReadLine());
List<byte[]> inputs = new List<byte[]>();
for (int k = 0; k < desiredInputs; k++)
{
Console.WriteLine("Enter message " + (k+1) + ":");
string tempstring = Console.ReadLine().Replace(" ", "").ToUpper();
if (tempstring.Length % 4 != 0)
{
Console.WriteLine("ERROR: The string you entered does not represent an EVEN number of bytes (ENTER to exit)\n");
while (Console.ReadKey(true).Key != ConsoleKey.Enter) ;
Environment.Exit(0);
}
inputs.Add(StringToByteArray(tempstring));
}
ushort poly = 0xFFFF;
int initialValue = 0x0000;
DateTime previousTime = DateTime.Now;
Console.WriteLine("\nProcessing... Poly: " + poly.ToString("X4") + " (0% complete)");
while (poly > 0x0)
{
int NoteWorthyPoly = 0;
if (poly != 65500 && poly % 655 == 0)
{
TimeSpan ts = DateTime.Now - previousTime;
TimeSpan TimeRemaining = ts.Multiply(100 - ((0xFFFF - poly) / 655));
StreamWriter Logger3 = new StreamWriter(LogPath, true);
Console.WriteLine("Processing... Poly: " + poly.ToString("X4") + " (" + ((0xFFFF - poly) / 655) + "% complete, Time Remaining: " + TimeRemaining.ToString(@"dd\.hh\:mm\:ss") + ")");
Logger3.WriteLine("Processing... Poly: " + poly.ToString("X4") + " (" + ((0xFFFF - poly) / 655) + "% complete, Time Remaining: " + TimeRemaining.ToString(@"dd\.hh\:mm\:ss") + ")");
Logger3.Close();
previousTime = DateTime.Now;
}
while (initialValue <= 0xFFFF)
{
List<ushort> CrcResultsCache = new List<ushort>();
for (int i = 0; i < inputs.Count; i++)
{
CrcResultsCache.Add(Crc16(inputs[i], poly, (ushort)initialValue));
}
if (CrcResultsCache.Count != CrcResultsCache.Distinct().Count())
{
StreamWriter Logger = new StreamWriter(LogPath, true);
NoteWorthyPoly = 1;
Console.WriteLine("\nCOLLISIONS FOUND!!!\n");
Logger.WriteLine("\nCOLLISIONS FOUND!!!\n");
Console.WriteLine("Current CRC Parameters:");
Logger.WriteLine("Current CRC Parameters:");
Console.WriteLine("Poly: " + poly.ToString("X4") + " Init: " + initialValue.ToString("X4"));
Logger.WriteLine("Poly: " + poly.ToString("X4") + " Init: " + initialValue.ToString("X4"));
Console.WriteLine("List of Collisions:");
Logger.WriteLine("List of Collisions:");
var q = from x in CrcResultsCache
group x by x into g
let count = g.Count()
orderby count descending
select new { Value = g.Key, Count = count };
List<int> Counts = new List<int>();
foreach (var x in q)
{
Console.WriteLine("Value: " + x.Value.ToString("X4") + " Count: " + x.Count);
Logger.WriteLine("Value: " + x.Value.ToString("X4") + " Count: " + x.Count);
Counts.Add(x.Count);
}
Console.WriteLine("Highest Collision Count: " + Counts.Max());
Logger.WriteLine("Highest Collision Count: " + Counts.Max());
Logger.Close();
}
initialValue++;
}
if (NoteWorthyPoly == 1)
{
StreamWriter Logger11 = new StreamWriter(LogPath2, true);
Logger11.WriteLine("Poly: " + poly.ToString("X4"));
Logger11.Close();
}
initialValue = 0x0000;
//StreamWriter Logger2 = new StreamWriter(LogPath, true);
poly--;
//Logger2.WriteLine("Progress Status: Poly: " + poly.ToString("X4"));
//Logger2.Close();
}
}
static ushort Crc16(byte[] bytes, ushort poly, ushort initialValue)
{
ushort[] table = new ushort[256];
ushort temp, a;
ushort crc = initialValue;
for (int i = 0; i < table.Length; ++i)
{
temp = 0;
a = (ushort)(i << 8);
for (int j = 0; j < 8; ++j)
{
if (((temp ^ a) & 0x8000) != 0)
temp = (ushort)((temp << 1) ^ poly);
else
temp <<= 1;
a <<= 1;
}
table[i] = temp;
}
for (int i = 0; i < bytes.Length; ++i)
{
crc = (ushort)((crc << 8) ^ table[((crc >> 8) ^ (0xff & bytes[i]))]);
}
return crc;
}
}
}
