Создание функций шифрования / дешифрования с использованием алгоритма Питера Вайнбергера
Можно ли расшифровать хэш-алгоритм Питера Вайнбергера?
Я пытаюсь написать свои собственные функции Encrypt Decrypt. Я понимаю концепцию, что значение Hash означает, что вы не можете или не должны расшифровывать значение хеш-функции, но я думаю, что, поскольку алгоритм относительно прост, возможно, в этом случае возможно расшифровать этот тип хеш-функции. Я сделал простое шифрование, которое использует простое вращение, и теперь я хочу попробовать что-то более сложное.
Так можно ли расшифровать хеш-значение, полученное из хеш-алгоритма Питера Вайнбергера?
Следующая функция шифрования — точный алгоритм Хэша Питера Вайнбергера, расшифровка — моя собственная попытка, которая не работает:
int encrypt(char *s)
{
/* Peter Weinberger's */
char *p;
unsigned int h, g;
h = 0;
for(p=s; *p!='\0'; p++){
h = (h<<4) + *p; printf("Step : ");
if (g = h&0xF0000000) {
h ^= g>>24;
h ^= g;
}
}
return h % 211;
}
std::string decrypt(int v)
{
/* Peter Weinberger's */
unsigned int h, g;
h = 0;
v /= 211;
int s = sqrt(v);
/* Not sure what to do here
for(p=s; *p!='\0'; p++){
}
*/
return string(h);
}
Решение
Учитывая чрезвычайно малый выходной размер, атака методом перебора является тривиальной.
- Генерация строки (например, случайно)
- Хэш это
- Если оно соответствует известному значению, вы нашли первое предварительное изображение, иначе перейдите к шагу 1
В среднем потребуется 211 попыток, чтобы получить строку, соответствующую данному хешу. Вероятно, это не будет исходная строка, но этого следует ожидать, учитывая хэширование с потерями.
Для двухсимвольных вводов этот хеш становится (16*s[0]+s[1])%211 который вы можете переписать как (16*(s[0]-'A')+(s[1]-'A') + 50)%211
Решая для строки, вы получаете:
s[0]=(hash+161)/16+'A';
s[1]=(hash+161)%16+'A';
Например для s == "AB" ты получаешь hash==51, Затем с помощью приведенных выше формул, чтобы изменить это:
s[0] = 13 +'A' = 'N'
s[1] = 4 +'A' = 'E'
=> s="NE" который соответствует хешу 51, но не является исходной строкой.
Другие решения
Если я правильно понимаю алгоритм, для каждого символа он делает:
- Умножьте хеш на 16 (переместите его на 4 бита влево)
- Добавить символ строки
- Если результат имеет более 28 бит, удалите 4 старших бита и сделайте XOR их где-нибудь в хэше.
Ограничив строку размером 6 (или 7, если первый байт меньше 16), шаг 3 никогда не будет выполнен. Так что все, что осталось, это просто сдвиг и добавление.
Когда строка содержит 6 символов, конечный результат представляет собой следующую сумму (h = старшие 4 бита символа, l = младшие 4 бита):
pos: bits
0: .hl00000
1: ..hl0000
2: ...hl000
3: ....hl00
4: .....hl0
5: ......hl
----------- +
0******* Result is 32 bits with upper 4 bits zero
Мы видим, что биты 24-27 определяются старшими 4 битами символа в позиции 0 плюс возможный перенос из сложения младших битов. Биты 20-23 представляют собой сумму младших битов char 0 и старших битов char 1 (плюс возможный перенос).
Если входные символы могут иметь все 255 возможных значений (за исключением нуля), создать строку, генерирующую хэш, не так сложно.
- Посмотрите на старшие 4 бита в хэше. Это будет верхняя часть персонажа в позиции 0.
- Посмотрите на следующие 4 бита в хэше. Это сложение верхней части символа 1 и нижней части символа 0.
- Выберите значение для самой высокой части. Например. «самая высокая часть всегда равна нулю» или «самая высокая часть всегда равна 0100 (заглавные буквы)».
- Если биты в значении меньше значения, которое вы выбрали на шаге 3, позаимствуйте некоторые из предыдущих битов (если эти биты были нулевыми, перетяните их в следующую группу битов).
- Теперь у вас есть нижняя часть символа 0 и верхняя часть символа 1.
- Вернитесь к шагу 2 для следующих 4 битов, пока не достигнете конца хеша
- Убедитесь, что в вашей строке нет символов со значением 0.
Код будет немного более сложным, так как есть все виды крайних случаев (например, хэш 01000000), и будет оставлен читателю в качестве упражнения;).
Редактировать: я полностью пропустил h % 211 операция. Что делает это еще проще, как показывает CodesInChaos.
detector