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

Тема в разделе "WASM.CRYPTO", создана пользователем blood, 2 янв 2005.

  1. blood

    blood New Member

    Публикаций:
    0
    Регистрация:
    21 ноя 2004
    Сообщения:
    56
    Адрес:
    Russia
    Ну, 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;

    }

    [​IMG] 383043108__sample_crypt.rar
     
  2. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159




    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).
     
  3. blood

    blood New Member

    Публикаций:
    0
    Регистрация:
    21 ноя 2004
    Сообщения:
    56
    Адрес:
    Russia
    to RElf

    Хитро.. Долго врубался.. Остался вариант, когда пара (a,b) одна.
     
  4. Chingachguk

    Chingachguk New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2002
    Сообщения:
    340
    Что-то я не понял, прошу объяснить если не так, но, насколько я понимаю, по условию задачи я свободен в выборе 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 комбинации... Или я чего-то не понял ?
     
  5. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159


    Нет, свободы в выборе c нет. Это фиксированный параметр алгоритма, просто он в отличие от K известен.
     
  6. Chingachguk

    Chingachguk New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2002
    Сообщения:
    340
    Иногда нахожу время для анализа этой функции. Сейчас меня интересует вот какой момент.



    Получил, что преобразование 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 ?...).



    Если кто-то выскажется на эту тему - спасибо ;)
     
  7. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159




    Это свойство называется инъективностью. Но здесь выполняется еще более сильное свойство - обратимость (или биективность), по любому z' мы можем однозначно восстановить z. Другими словами, указанное преобразование является перестановкой на множестве {z}.







    Так и есть. Только эти "кольца" называются циклами. Любая перестановка состоит из некоторого набора циклов.







    Полученную перестановку можно считать случайной. А для случайной перестановки N элементов доказано, что ожидаемое число циклов примерно равно ln(N), т.е. в нашем случае ln(2^96) ~= 67. Средняя длина циклов соответственно будет равна 2^96/67 ~= 2^90.



    Вот некий текст про случайные перестановки и их характеристики.
     
  8. green_g

    green_g New Member

    Публикаций:
    0
    Регистрация:
    9 апр 2005
    Сообщения:
    4
    период и количество циклов существенно зависят от С и, скорее всего, не зависят от К.
     
  9. Chingachguk

    Chingachguk New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2002
    Сообщения:
    340
    Спасибо за ответы !



    Я полагал, что если циклы существуют и их длина невелика, причем длина является какой-то функцией от K, то, измерив их характеристики [длину ?], можно получить некие данные о K. Однако если вы говорите, что их длина ~2^N и они (их характеристики) не зависят от K, то идея была ошибочной. Что ж, попробую посмотреть на небольшом N (16 наверное) на численном эксперименте, как это выглядит "вживую".
     
  10. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159


    С чего бы это вдруг? Единственный случай, когда K не влияет на эти характеристики - это c=1.
     
  11. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.148
    кстати, глупый вопрос: это симметрик??:))
     
  12. Ruptor

    Ruptor Marcos el Ruptor

    Публикаций:
    0
    Регистрация:
    9 янв 2005
    Сообщения:
    167
    Адрес:
    Australia
    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
     
  13. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.148
    Ruptor
    не спорю: хэш, строго говоря, относится к помехоустойчивому кодированию, и смею предположить, что любой алгос стругание хэшей ненадёжен==========> хэш можно подделать (созданный любым алгосом).