Category: литература

Category was added automatically. Read all entries about "литература".

Криптография и Свобода - 2

Итак, у нас есть некоторое фиксированное конечное заполнение регистра после t тактов работы: (yt,yt+1,…,yt+N-1), которое было получено после подачи на вход регистра длины N некоторого сообщения M1 = m1(0),m1(1),…,m1(j) при том, что прокрутка осуществлялась с «дырками»: после подачи на вход одного байта сообщения – два «холостых» такта, т.е. таких, когда на вход подается 0. Мы хотим его «захватить» (capture), т.е. подобрать другое сообщение M2 = m2(0),m2(1),…,m2(j), такое, что его конечное заполнение (zt,zt+1,…,zt+N-1) будет совпадать с (yt,yt+1,…,yt+N-1). Сообщение начинаем подбирать не с начала, а с конца. Например, первая строка таблицы – это заполнения регистров за один шаг до совпадения - (yt-1,yt,…,yt+62) и (zt-1,zt,…,zt+62). Отличие в них может быть только по одной координате: yt-1 ≠ zt-1. Поскольку на последнем шаге значение m2(j) добавляется линейно, то обеспечить совпадение последней координаты не составит никаких проблем: m2(j) = π(yt-1–yt–yt+59+yt+62)+m1(j) - π(zt-1–zt–zt+59+zt+62). Здесь вероятность правильного подбора равна 1. А вот за два шага до совпадения ситуация иная. На вход подается дырка, и совпадение получается только в том случае, если было обеспечено выполнение условия yt-2–yt-1=zt-2–zt-1. Дырка свое дело сделала, подобрать какие-то соотношения для символов M2, при которых это равенство выполнялось бы безусловно, не удается, остается только предполагать, что такое может случиться с вероятностью 2-8. Именно это и требуется для хеширования. Поехали дальше. За три шага до совпадения. Условие совпадения: yt-3–yt-2=zt-3–zt-2. А вот тут-то, отъехав назад аж до 67 шага, видим, что подбором значения m2(j-22) можно добиться этого совпадения с вероятностью, близкой к 1. Действительно, это же элемент знакомой нам по первой книге матрицы частот P(π), у которой на пересечении i-ой строки и j-го столбца стоит число решений системы

x – y = i;

        π(x) – π(y) = j;

А в логарифмической подстановке это число почти всегда равно 1 для ненулевых i и j.

Так может не надо использовать логарифмические подстановки в MCSSHA? Нет, мне кажется, что именно логарифмические подстановки наиболее пригодны для MCSSHA, ибо с их помощью можно получить гарантированные оценки трудоемкости подобного метода захвата. Решение системы с большой вероятностью однозначное, следовательно, требуемое значение m2(j-22) - тоже только одно. Но тогда на других местах с «чистыми дырками» (например на упоминавшемся выше шаге 2 до захвата) требуемые соотношения получаются с вероятностью 2-8, ибо возможностей для подбора предыдущих значений M2 не остается никаких других, кроме случайных. А если взять, к примеру, антипод логарифмической подстановки – линейную подстановку π(x) = ax + b, то, как нетрудно видеть, ей никакие дырки не помогут, система разваливается и элементарно решается.

Исходя из этих соображений, я получил оценки вероятности «захвата» для алгоритма MCSSHA при различных значениях длины регистра:

SR length (bytes)

Steps with probability 1

Steps with probability ≈1

Steps with probability 2-8

Total Probability

64

22

20

22

<2-176≈10-52

128

44

40

44

<2-352≈10-105

Экстрим закончен, дальше можно двигаться спокойнее. Наводим блеск и лакировку на оригинальную криптографическую идею дырок на входе в регистр.

Выдавать заполнение регистра в явном виде в качестве результата хеширования нельзя. Ну, например, потому, что от последнего знака текста зависит только последний знак регистра, а это противоречит требованиям NIST: любое изменение в тексте должно приводить к появлению абсолютно новой, случайной и равновероятной хеш-функции. Ну, тут уже проблем меньше: подача текста на вход закончилась, можно подать полученное заполнение в качестве входа на такой же или подобный регистр, но уже без всяких дырок, и прокрутить несколько раз. Именно это я и сделал, в результате получился алгоритм хеширования MCSSHA-3, который я и послал в NIST в установленные регламентом сроки, т.е. до наступления deadline.

«Головокружение от успехов». Именно такими словами товарища Сталина я бы сейчас охарактеризовал свои действия в последние недели перед deadline. За короткие сроки придуман оригинальный алгоритм, решена давно не дававшая мне покоя задача пристроить куда-нибудь логарифмические подстановки, оценки стойкости – ломовые, скорость – весьма приличная. А блеск и лакировка – дело десятое, главное – оригинальная идея!

«NIST will NOT accept modifications to the submitted algorithms during Round 1». Этой фразе в требованиях NIST я поначалу не придавал значения: исследовательская задача, как же с первого раза – и безо всяких изменений и доработок? А потом интуитивно ясно, что главная задача моего участия в этом конкурсе – публично заявить об оригинальных российских криптографических идеях и разработках, которые по разным причинам оказались похоронены в России. Надеяться на то, что эти идеи окажутся приняты в качестве нового мирового стандарта хеширования, можно было только втайне от самого себя. Мне больше была интересна реакция на них «мировой криптографической общественности», внешние криптографические аргументы и контраргументы за и против них.

Итак, наступил долгожданный deadline и появились описания всех алгоритмов-кандидатов, допущенных NIST для участия в первом раунде конкурса. Одновременно появился полуофициальный сайт с очень симпатичным названием: The SHA-3 Zoo. Там тоже есть все кандидаты, а также мнения о каждом из них независимых криптографических экспертов. Оппонентами алгоритмов хеширования типа MCSSHA стали Jean-Philippe Aumasson (Nagravision SA, Switzerland) and Mar´ıa Naya-Plasencia (INRIA projet-team SECRET, France). С MCSSHA-3 они обошлись по-простому, не вдаваясь ни в какие дебри. В нем длина регистра при подаче на него хешируемого сообщения была в точности равна длине требуемой хеш-функции. В регистре есть «критические точки», т.е. такие, на которые при построении последнего заполнения поступали знаки сообщения. Остальные, на которые поступали «дырки», назовем некритическими. В MCSSHA-3 на один знак сообщения приходилось три «дырки», поэтому ¼ часть точек – критическая, а ¾ - нет. Генерим случайные сообщения, совпадения критических точек обеспечиваем решением уравнений, а некритические точки – методом, использующим парадокс дней рождения. Сокрашение трудоемкости с требуемых 2N/2 до 23N/8. Тут же на «клетку» с MCSSHA-3 в SHA-3 Zoo повесили табличку «2nd preimage», что означает: получено снижение оценок стойкости по сравнению с brute force при анализе по поиску коллизий второго типа.

Лазил, лазил по горам, а до такой очевидной вещи так и не долез! И ведь защититься от нее – элементарно. Ну кто, спрашивается, просил меня на первом этапе, пока сообщение подается на вход регистра, делать длину регистра равной длине хеш-функции? Явное головокружение от успехов, сделал бы на первом этапе длину регистра раза в два больше, благо на скорости это почти никак не сказывается: в программной реализации сдвигаются не сами байты в регистре, а точки съема, значение которых затем приводится по модулю длины регистра. Даже в некоторых случаях будет быстрее. Например, при N = 224 и 384 я зачем-то приводил значения точек съема по этим модулям, в то время как если бы взять, например, длину регистра 256 или 512, то и приведение по этим модулям реализуется быстрее. Ну и самое главное: в MCSSHA-3 я использовал три «дырки» после каждого знака, а увеличив длину регистра можно вполне обойтись и двумя и опять-таки увеличить скорость. Приведение же к нужной длине запросто можно осуществить на втором этапе, когда включившее в себя все знаки сообщения заполнение регистра подается на вход другого регистра, длина которого уже совпадает с длиной хеш-функции.

«Поезд ушел» - примерно так ответили мне в NIST, когда я попросил внести изменения в свою заявку. Но описание алгоритма MCSSHA-4, в котором проблемы MCSSHA-3 были устранены, я всеми правдами и неправдами протащил в материалы The First SHA-3 candidate conference, которая проходила в бельгийском городе Leuven с 25 по 28 февраля 2009 года.

С «дырками» ситуация прояснилась, те подходы, которые имели место для MCSSHA-3 оказались непригодны, когда длина регистра при подаче на его вход сообщения была увеличена в два раза. Вроде остается пустячок: заполнение фиксированной длины пропустить пару раз через регистр нужной длины. И тут мои зоркие оппоненты подметили то, что от меня ускользнуло.

Возьмем, к примеру, длину хеш-функции равной 32 байтам. Одним из требований к идеальной хеш-функции является то, чтобы трудоемкость построения сообщения с фиксированным значение хеш-функции составляла в данном случае примерно 232*8 операций. На этом требовании и подловили меня мои оппоненты в MCSSHA-4.

На первом этапе (pre-image computation) используется регистр длиной 64 байта, а на втором (final hash computation) – 32 байта. Займемся повнимательнее вторым этапом. В нем на регистр длины 32 два раза подается одно и то же входное слово длины 64, при этом начальное заполнение регистра R0 = (0, 1, 2,…,31). Попробуем построить сообщение, которое на первом этапе дает конечное заполнение y0,y1,…,y63 такое, при котором на втором этапе R0 переходит само в себя. Методика простая: для произвольных случайных y0,y1,…,y31 вычисляем состояние R1 регистра и для него однозначно находим y32’,y33’,…,y63’, переводящие его в R0. Дергаем случайные сообщения, получаем какие-то y0, y1,…,y31, вычисляем для них y32’,y33’,…,y63’ и пытаемся дописать сообщение так, чтобы последующие 32 байта совпали с y32’,y33’,…,y63’. Из этих 32 байт 22 – случайные, приходящиеся на «дырки», а 10 – на символы текста, которые однозначно подбираем. Если удалось подобрать, то значение хеш-функции такого сообщения будет совпадать с R0. Трудоемкость – 222*8, не выполнено условие «preimage resistance of approximately n bits».

Да, JP & Marıa (именно так они всегда подписывали свои письма, посылаемые мне по e-mail) нельзя было отказать в оригинальности их криптографического мышления. На Namhansanseong не полезли, обошлись без экстрима.

Я тогда сильно переживал за свои «головокружения от успехов». Неужели хорошая и перспективная идея с «дырками» в неавтономном регулярном регистре сдвига оказалась перечеркнутой от того, что мне не пришло в голову сразу же навести на нее необходимый криптографический блеск? Лихорадочно сделанные и помещенные на мой корейский сайт (сейчас он, к сожалению, закрыт, и ссылки на него из NIST не работают) очередные две модернизации: MCSSHA-5 и MCSSHA-6, к сожалению, не прикрыли полностью проблемы второго этапа алгоритмов типа MCSSHA. Во второй раунд SHA-3 моя заявка не прошла, и я потерял к этому конкурсу первоначальный интерес.

Сейчас, спустя почти три года после этих событий, мне по-прежнему кажется, что идею «регистра с дырками» можно довести до совершенства и создать на ее основе идеальную хеш-функцию, не допускающую никаких снижений трудоемкости по сравнению с brute force. И защититься от атаки JP & Marıa тоже можно сравнительно несложно: например, второй раз подавать на вход регистра перевернутый вектор y0,y1,…,y63. Для оценки и сравнения скорости работы алгоритмов типа MCSSHA я послал их в Иллинойс профессору Бернштейну. Там сейчас проводится тестирование скорости всех присланных алгоритмов хеширования на различных компьютерах. Результаты показывают, что по скорости MCSSHA является далеко не худшим из известных алгоритмов хеширования. Вот, например, один из последних результатов.


Назад                                Продолжение
В начало книги Криптография и Свобода - 2