как найти столкновение для простого алгоритма хеширования
У меня есть следующий алгоритм хеширования:
unsigned long specialNum=0x4E67C6A7;
unsigned int ch;
char inputVal[]=" AAPB2GXG";for(int i=0;i<strlen(inputVal);i++)
{
ch=inputVal[i];
ch=ch+(specialNum*32);
ch=ch+(specialNum/4);
specialNum=bitXor(specialNum,ch);
}
unsigned int outputVal=specialNum;
BitXor просто выполняет операцию Xor:
int bitXor(int a,int b)
{
return (a & ~b) | (~a & b);
}
Теперь я хочу найти алгоритм, который может генерировать «inputVal» когда задан outputVal. (Сгенерированный inputVal не обязательно должен совпадать с исходным inputVal. Вот почему я хочу найти столкновение).
Это означает, что мне нужно найти алгоритм, который генерирует решение, которое при подаче в вышеупомянутый алгоритм приводит к тем же результатам, что и указанный «outputVal».
Длина создаваемого решения должна быть меньше или равно 32.
Решение
Метод 1: грубая сила. Ничего страшного, потому что ваш «specialNum» всегда находится в диапазоне целых чисел, поэтому, попробовав в среднем несколько миллиардов входных значений, вы найдете правильное. Должно быть сделано за несколько секунд.
Способ 2: грубая сила, но умная.
Рассмотрим значение specialNum перед обработкой последнего канала. Сначала вы рассчитываете (specialNum * 32) + (specialNum / 4) + ch. С -128 <= ch < 128 или 0 <= ch < 256 в зависимости от подписи char, вы знаете 23 старших бита результата, независимо от ch. После xor’ing ch с specialNum вы также знаете старшие 23 бита (если ch подписан, есть два возможных значения для старших 23 битов). Вы проверяете, соответствуют ли эти 23 бита желаемому результату, и если они не соответствуют, вы исключили все 256 значений ch за один раз. Таким образом, метод грубой силы закончится в среднем через 16 миллионов шагов.
Теперь рассмотрим значение specialNum перед обработкой двух последних ch. Опять же, вы можете определить максимально возможные 14 битов результата (если ch подписан четырьмя альтернативами), вообще не проверяя последние два символа. Если старшие 14 бит не совпадают, все готово.
Метод 3: Вот как вы это делаете. Рассмотрим по очереди все строки s длиной 0, 1, 2 и т. Д. (Однако ваш алгоритм, скорее всего, найдет решение гораздо быстрее). Вычислить specialNum после обработки строки s. Следуя вашему алгоритму и учитывая, что char должен быть подписан, найдите до 4 различных значений, которые могут иметь старшие 14 бит specialNum после обработки еще двух символов. Если какой-либо из них соответствует желаемому выводу, то проверьте значение specialNum после обработки каждого из 256 возможных значений следующего символа и найдите до 2 различных значений, которые могут иметь старшие 23 бита specialNum после изучения другого символа. Если один из них соответствует старшим 23 битам желаемого вывода, то проверьте, каким будет specialNum после обработки каждого из 256 возможных следующих символов, и найдите совпадение.
Это должно работать ниже миллисекунды. Если char без знака, это быстрее.
Другие решения