Ну, cgi/php - это выше моих сил, а вот прожку написал. Там шифратор и дешифратор. Представь, что у тебя нет дебугера и ломай наздоровье. Алгоритм: #define c=0x0557DBCDFD39B793F73D93B7F _int96 crypt(_int96 x,_int96 K) { _int96 z; int i; z=x; for(i=0;i<97;i++){ z=z^K;//xor z=rol(z,1);//циклический сдвиг на 1 бит влево z=z*c;//умножение } return z; } 383043108__sample_crypt.rar
Meet-In-The-Middle атака, требующая около 2^48 пар (a,b): Для каждой пары вычисляем два 96-битных числа x(a,b)=a XOR b и y(a,b)=(rol(a,1)*c) XOR (rol(b,1)*c) и ищем две такие пары, для которых x(a1,b1)=y(a2,b2). По парадоксу близнецов потребуется около 2^48 пар, чтобы найти две подходящие. Если x(a1,b1)=y(a2,b2), то ключ можно вычислить как K=a1 XOR (rol(a2,1)*c).
Что-то я не понял, прошу объяснить если не так, но, насколько я понимаю, по условию задачи я свободен в выборе c и x, но не знаю K. Пусть я выбрал c=1, x=0. Это вроде не противоречит условию. Пусть K0..Kn - биты ключа K, n-разрядность хэша (в данном случае n=95). Следим за эволюциями z: Шаг 1: z=Kn ... K0 Шаг 2: z=Kn-1^Kn ... Kn^K0 ... Шаг n: z=K0^K1^K2...^Kn ... K1^K2^...^K0 Во всех битах сейчас одинаковое число - K0^K1^K2...^Kn - перексоривание битов K, обозначим его {Kn}. Шаг n+1: z={Kn}^Kn ... {Kn}^K0. Это выход хэша. Т.е. он равен самому K с точностью до {Kn}. Это всего 2 комбинации... Или я чего-то не понял ?
Нет, свободы в выборе c нет. Это фиксированный параметр алгоритма, просто он в отличие от K известен.
Иногда нахожу время для анализа этой функции. Сейчас меня интересует вот какой момент. Получил, что преобразование z'=(rol(z,1)*c)^k; "однозначно" (не знаю как точно назвать), т.е. для заданной пары (z',z) не найдется другого z1, чтобы (rol(z1,1)*c) = (rol(z,1)*c) = z'. Отсюда вроде бы следует однозначность всей функции, т.е. нет такого z1 для z, чтобы hash(z)=hash(z1). Тогда если мы будем использовать последовательно преобразование z1=(rol(z0,1)*c), z2=(rol(z1,1)*c)..., то получим некую цепочку: z0->z1->z2->... Если продолжать цепочку далее, то (из свойства однозначности) мы должны получить кольцо: z0->z1->z2->...->z0. Тут может быть два варианта. Либо для всего множества {zn} (те для всех чисел от 0 до 2^96-1 как в примере) существует одно кольцо, охватывающее все значения {zn}, либо набор независимых колец (незавтсимых из свойства однозначности, иначе если кольца пересекаются, то оно нарушается). Вот мне пока интересно, будет ли одно кольцо или семейство (тогда какой период и зависит ли он от K ?...). Если кто-то выскажется на эту тему - спасибо
Это свойство называется инъективностью. Но здесь выполняется еще более сильное свойство - обратимость (или биективность), по любому z' мы можем однозначно восстановить z. Другими словами, указанное преобразование является перестановкой на множестве {z}. Так и есть. Только эти "кольца" называются циклами. Любая перестановка состоит из некоторого набора циклов. Полученную перестановку можно считать случайной. А для случайной перестановки N элементов доказано, что ожидаемое число циклов примерно равно ln(N), т.е. в нашем случае ln(2^96) ~= 67. Средняя длина циклов соответственно будет равна 2^96/67 ~= 2^90. Вот некий текст про случайные перестановки и их характеристики.
Спасибо за ответы ! Я полагал, что если циклы существуют и их длина невелика, причем длина является какой-то функцией от K, то, измерив их характеристики [длину ?], можно получить некие данные о K. Однако если вы говорите, что их длина ~2^N и они (их характеристики) не зависят от K, то идея была ошибочной. Что ж, попробую посмотреть на небольшом N (16 наверное) на численном эксперименте, как это выглядит "вживую".
Posmotri na nazvaniye toi C function... "hash" - eto ni symmetric, ni asymmetric potomu chto eto ne cipher. eto neinvertiruyemoye. Po krainei mere tak pohozhe zadumivalos. Ruptor
Ruptor не спорю: хэш, строго говоря, относится к помехоустойчивому кодированию, и смею предположить, что любой алгос стругание хэшей ненадёжен==========> хэш можно подделать (созданный любым алгосом).
