Как найти ключ

Есть такой алгоритм значит:

Код (Text):

1. #define c=какая_нибудь_нечетная_константа
2. _int96 hash(_int96 x,_int96 K)
3. {
4. _int96 z;
5. int i;
6. z=x;
7. for(i=0;i<97;i++){
8.  z=rol(z,1);//циклический сдвиг на 1 бит влево
9.  z=z*c;//умножение :)
10.  z=z^K;//xor
11. }
12. return z;
13. }

Все операции 96 битовые.

Даны a,b. hash(a,K)=b. Найти нужно K. Незнаю зачем спрашиваю, трудно все это. И всетаки есть какие мысли?



P.S.

Вот еще в аттаче крякми - демо-версия алгоритма(без rol). Для тех кому интересно, попробуйте. С теорией, господа кейгеншики, тоже боротся надо



1035251676__blood_crackme.rar

 

Найти нужно K



:-/ Я чего-то не догнал? Бряк на строку



_int96 hash(_int96 x,_int96 K)



или на



z=z^K;//xor



и смотри в отладчике свое К. Без всякой математики :-/

 

Ну уж нет a,b - константы программы. K - вводит пользователь. "и смотри в отладчике свое К"- то свое K что ввел и увидишь. А покажи мне тот, который hash(a,K)=b?

(в крякми K вводится, и должна типа табличка вылести что все ок)

З.Ы. в крякми кстати ключь можно найти хотя отличий то совсем ничего.

 

Ага. Теперь понятно. Дык так надо было и раньше-то говорить! А как используется z (что в твоей hash) в ходе выполнения программы далее?

 

z? z-локальная переменная в hash, в ней результат накапливается, затем возвращается как значение функции.

 

Тьфу. Я спрашиваю, как ты дальше используешь z в программе? Возвратила твоя hash свой z. И что потом?

 

Потом z(тобишь результат) - сравнивается с b, принимается решение о валидности ключа K. Если реально, введеный K можно еще для расшифровки кода проги использовать. Кстати hash(a,K) обратима, тоесть можно найти a такое, что hash(a,K)=b зная K и b. Так что hash на самом деле-это crypt при некоторых условиях.

(Кажется понял что тебя смутило. 2 аргумента? Извиняюсь. Просто алгоритм изначально придумывался как шифр, шифруется a получается b. Стандартная задача криптоанализа: зная текст и шифровку найти ключ. Еще раз sorry)

 

blood, операции все линейные, ключ найти можно. хотя очень смутно вижу связь между куском кода в первом посте и исходником в аттаче

 

Ага, угу. Теперь понял.

Т.е. задача формулируется так: проверить, является ли hash стойкой к коллизиям?

Велл, априори могу сказать - явно не стойкая. Это тебе не MDx/SHA-x/RIPEMD и прочие ужасы. Сам алгоритм простенький. Меж прочим, в строке



z=z*c;//умножение



чертовски вероятно переполнение. Как результат - потеря старших значащих бит, что не есть хорошо.

Что до анализа таких вещей, практически я этим не занимался пока, увы. Советую почитать что-то типа "Differential cryptanalysis of hash functions based on block ciphers", да и Менезес в своей книге очень много полезных практических штуковин описывает...

 

Broken Sword Да несовсем. Линейность у них в разных группах.

Связь есть с таким куском:

_int96 crypt(_int96 x,_int96 K)

{

_int96 z;

int i;

z=x;

for(i=0;i<97;i++){

z=z^K;

z=z*c;

}

return z;

}

 

blood, ааа.. а то я rol пытался найти ) p.s. что есть "разные группы"?

 

volodya

чертовски вероятно переполнение

угу, очень вероятно, так и было задумано, что умножение по модулю 2^96. Но если c нечетно, то существует c^(-1) значит не происходит потери информации.

 

что умножение по модулю 2^96



Пардон, где ты здесь увидел модуль?

И еще, что ты сначала делаешь - ксоришь или умножаешь? А-то два кода - две версии

 

А обратный элемент существует только тогда, когда с не нечетно, а ПРОСТОЕ.

 

простое? а не взаимно простое с 2^96?

 

Broken Sword

С группами эт я пожалуй погоречился. Тут скорее кольца(даже поля). Имелось ввиду что z*c линейно относительно сложения ((a+b)*c=a*c+b*c), а xor линеен для логических операций or,and. Линейность обычно хороша тем, что суперпозиция линейных преобразований есть линейное преобразование, да только не здесь, т.к здесь как бы разные линейности.

(Правка: с полями я тоже пожалуй погоречился...)

 

blood так бы сразу и сказал

 

volodya

flankerx прав, достаточно взаимной простоты. Например в RSA для експоненты - публичного ключа e, ищется приватный ключ d как обратный по модулю (p-1)*(q-1) (e=d^(-1) mod (p-1)*(q-1))

на счет умножение по модулю 2^96, как бы обьяснить... Например регистр 3 бита, когда мы умножаем 5*4 получаем 20=10100b , отбрасываем лишние биты получаем 100b=4, тоже самое 20 mod 8=4, как бы беря остаток от деления на 2^3 мы избавляемся от старших бит.

Две версии потому, что одну я взломал, другую нет. Ту что взломал запихал в аттач для развлечения вас

 

да ладно... компьютер работает с арифметиков по модулю 2^32... ну и что ? можно было твои операции и с обычным int вести... вот и все дела... :p

 

нет, нельзя.

2^32 очень легко отбрютфорсить - фактически, пришлось бы перебирать 2^16 вариантов при использовании birthday-attack на хеш-функцию. так что выбор int96 я вполне одобряю и даже могу заметить, что и это - не слишком много...