Category: it

Category was added automatically. Read all entries about "it".

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

Оригинал взят у kolkankulma в Криптография и Свобода - 2. MCSSHA
Оригинал взят у mikhailmasl в Криптография и Свобода - 2

MCSSHA

SHA-1 – нестойкий! Такая новость облетела криптографический мир в 2005 году. Но ведь SHA-1 – алгоритм хеширования, а в алгоритме хеширования нет никаких секретных ключей, здесь ничего не шифруется, что понимается под его стойкостью? Тут надо заметить, что одной из основных сфер использования алгоритма хеширования является ЭЦП, когда для применения математического аппарата электронной подписи сообщение произвольной длины нужно «сжать» в его хеш-функцию фиксированной длины, из которой затем с помощью секретного асимметричного ключа вычисляется подпись, а с помощью открытого - проверяется. Здесь слово «сжать» умышленно поставлено в кавычки, поскольку классическое сжатие предполагает возможность последующего восстановления исходного сообщения из сжатого текста, а для алгоритма хеширования, наоборот, возможность восстановления исходного сообщения из его хеш-функции должна быть практически исключена. Насколько сложно по хеш-функции восстановить хешируемое сообщение или получить какую-нибудь информацию о нем – это первый критерий оценки стойкости хеш-функции.

Сообщений произвольной длины бесконечно много, а значений хеш-функции фиксированной длины – конечное число, поэтому заведомо существуют различные сообщения, обладающие одинаковыми хеш-функциями. Насколько сложно их найти – второй критерий стойкости алгоритма хеширования. Пару сообщений с одинаковыми хеш-функциями в криптографии принято называть коллизией хеш-функции, причем коллизии бывают двух сортов: первого, когда требуется подобрать сообщение с той же хеш-функцией к некоторому фиксированному сообщению, и второго, когда просто требуется найти произвольную пару сообщений с одинаковыми хеш-функциями.

Давайте попробуем представит себе идеальную хеш-функцию, т.е. такую, для которой по каждому из приведенных выше критериев самые лучшие из оценок – это brute force, метод грубой силы. Каковы будут оценки brute force для хеш-функции?

    Начнем с первого критерия. Тут, вроде, все понятно: дергаем случайные сообщения, вычисляем для каждого из них хеш-функцию и проверяем ее на совпадение с имеющимся у нас значением хеш-функции. Если предположить, что длина хеш-функции равна 2n бит, то самым эффективным должен быть метод выбора случайных сообщений и каждое из них должно давать в качестве хеш-функции случайный и равновероятный вектор длины n, или, выражаясь официальным языком, preimage resistance of approximately n bits. Та же самая оценка будет справедлива и для нахождения коллизии первого сорта. А вот для нахождения коллизии второго сорта потребуется в среднем 2n/2 опробований – тут вступает в силу парадокс дней рождения. На упоминавшемся выше официальном языке это называется collision resistance of approximately n/2 bits. Такая получается картина идеальной хеш-функции.

Что же произошло с SHA1? В статье Брюса Шнайера Cryptanalysis of SHA-1, опубликованной 18 февраля 2005 года, утверждается, что три китайских криптографа смогли найти метод построения коллизии второго сорта для SHA1 за 269 операций. Если учесть, что длина хеш-функции SHA1 составляет 20 байт или 160 бит, то идеальная хеш-функция такой длины должна требовать в среднем 280 опробований для решения подобной задачи. Следовательно, SHA1, как следует из этой статьи, не является идеальной хеш-функцией. А 269 – это примерно 1021. Не такая уж астрономическая величина, а с криптографической точки зрения просто критическая. У Брюса Шнайера даются оценки времени и трудоемкости ее практического решения - 1757 дней (4,81 лет) усилиями 331252 пользователей.

SHA1 является в настоящее время, пожалуй, самым распространенным в мире алгоритмом хеширования. Даже такие чисто абстрактные подозрения в его ненадежности вынудили американский NIST (National Institute of Standard and Technology) принять срочные меры. 2 ноября 2007 года был объявлен открытый конкурс на разработку хеш-функций третьего поколения – SHA-3. Тут надо заметить, что хеш-функции второго поколения – SHA-2 – уже есть, они были разработаны американским АНБ, но по каким-то причинам NIST решил подстраховаться и провести открытый конкурс на SHA-3.

Требования к кандидатам SHA-3 были опубликованы на сайте NIST, если взять их криптографическую часть, то требование было одно: NISTу требовались идеальные хеш-функции, не допускающие среди известных в настоящее время методов анализа иных, кроме brute force.

Я впервые услышал о конкурсе SHA-3 в конце июня 2008 года. Один из выпускников 4 факультета ВКШ КГБ Игорь С. одним из первых «прорубил окно в Европу» и уехал жить в Норвегию. Там он больше был связан с теоретической криптографией, чем я в Корее, и, прочитав в Internet мою первую книжку «Криптография и Свобода», прислал мне письмо, из которого я и узнал об SHA-3. Я с радостью ухватился за эту мысль: после всех программистских баталий вспомнить про теорию и предложить NIST свой оригинальный вариант SHA-3, благо идей на этот счет было предостаточно: читатель первой книги наверняка помнит шифры на новой элементной базе и логарифмические подстановки. Эти оригинальные криптографические решения, которым было отдано много лет жизни, так и остались во многом невостребованными, и это меня все время угнетало. Так родились алгоритмы хеширования типа MCSSHA.

Сроки поджимали. Deadline для приема заявок на участие в конкурсе SHA-3 – 31 октября 2008 года. Следовательно, на все про все (разработка, анализ и оформление) у меня оставалось около 4-х месяцев. Особенно удручала невозможность какого бы то ни было квалифицированного обсуждения моих идей по MCSSHA, ибо те корейцы, с которыми я в то время работал, о теоретической криптографии имели весьма туманное представление. Так что весь криптоанализ MCSSHA проходил по примерно такой схеме: в выходные на целый день я уходил в горы и там, лазая по горным тропам, все время прикидывал те или иные возможности использования идей шифров на новой элементной базе для хеширования. И вот до чего в конце концов долазился.

Попробуем использовать для хеширования упоминавшийся в первой книге «Криптография и Свобода» неавтономный регулярный регистр сдвига над кольцом вычетов по модулю 256 (над байтами). Вот его рисуночек.

Идея использования подобного регистра для хеширования напрашивается сама собой: фиксируем какое-то начальное заполнение регистра и подаем сообщение на вход - x1,x2,…xL. Или что-то в этом роде… Дело в том, что в явном виде подавать сообщение на вход нельзя, сразу же возникнут коллизии – получающаяся система из N нелинейных уравнений элементарно решается и строятся пары с одинаковыми хеш-функциями. Как с этим бороться и в этой борьбе не слишком сильно усложнить такую красивую и элементарную реализацию? С этим вопросом, мучавшим меня около двух месяцев, я лазил по Bukhansan и Dobongsan и все никак не мог придумать удовлетворительного решения. А вот на горе с простым и понятным названием Namhansanseong осенило: нужны дырки!

    Дальше вынужден начать писать формулы… Ничего не могу с собой поделать, дорогой мой читатель, сейчас начнутся математические дебри. Так что самых мужественных и терпеливых приглашаю лезть в эти дебри и дальше, а большинству нормальных читателей – сесть на пенек, съесть пирожок и малость подождать, пока любители криптографического экстрима не налазаются по Namhansanseong.

    Если символами (yi,yi+1,…,yi+N-1) обозначить заполнение регистра сдвига в i-ый такт работы, то в (i+1)-ый такт оно будет (yi+1,yi+2,…,yi+N), где yi+N= π(yi–yi+1–yi+N-4+ yi+N-1) + xi. Заполнение регистра полностью обновляется за N тактов работы:

yi+N= π(yi–yi+1–yi+N-4+ yi+N-1) + xi

yi+N+ 1= π(yi+1–yi+2–yi+N-3+ yi+N) + xi+1

……………………………………………………………….

yi+2N- 1= π(yi+N-1–yi+N–yi+2N-5+ yi+2N-2) + xi+N-1

    При простой подаче сообщения на вход регистра из этой системы коллизия видна невооруженным взглядом: берем произвольное сообщение, вычисляем соответствующее ему значение регистра сдвига и элементарными арифметическими операциями решаем систему из N уравнений с N неизвестными – находим все xi, необходимые для того, чтобы получить нужное конечное заполнение регистра. Ну а если сообщение на вход подавать не сплошняком, а с дырками, например на один знак сообщения две дырки, что это даст? Да почти все, что доктор прописал!

yi+N= π(yi–yi+1–yi+N-4+ yi+N-1) + xj

yi+N+1= π(yi+1–yi+2–yi+N-3+ yi+N)

yi+N+2= π(yi+2–yi+3–yi+N-2+ yi+N+1)

yi+N+3= π(yi+3–yi+4–yi+N-1+ yi+N+2) + xj+1

…………………………………………

    И логарифмические подстановки, если кто помнит первую часть «Криптографии и Свободы», здесь очень даже к месту оказываются. Давайте попробуем порешать такую систему на дальних подступах к итоговому заполнению регистра.


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



promo sparnins may 18, 2015 15:32 Leave a comment
Buy for 10 tokens
Оригинал взят у matholimp в Мы – венеды Vene. Так называют нас не только соседи с запада и севера (эстонцы, финны, карелы), но также малочисленные ныне народы, пришедшие на землю нынешних 47 и 78 регионов РФ задолго до славян. Часто наш город называют Северной Венецией. Удивительным…

о ненависти к монадам

Оригинал взят у juan_gandhi в о ненависти к монадам
Среди программистов особенно популярна идея ненавидеть монады. Почему-то именно монады. Стрелки никто не ненавидит, потому что никто не в состоянии даже вообразить их (как квадратный трехчлен). А вот монады - пожалуйста.

К апликативным функторам тоже маловато претензий, хотя казалось бы. Ведь монада (по верованию хаскельщиков) - это апликативный функтор.

Возможно, дело в слове "функтор". Никто еще не выступал с критикой функторов. Мол, вы, функциональщики, может, и молодцы, но категория функторов не является локально малой. Или, скажем, раз в хаскеле ковариантности нету (да и в джаве ее маловато), то функторы в энтерпрайзе не нужны. Нет, ничо, терпят.

Хотя даже поклонники монад начинают частенько плеваться и ругаться, если им скажешь про сопряженные функторы. И еще что интересно, вот монада; к ней прилагается категория Клейсли; ее любят. А категорию Эйленберга-Мура не любят, и даже над теми, кто ее регулярно но бессознательно использует (username = if (database.get("username") == null) "" else database.get("username")), смеются как над лохами. Хотя эти две категории - просто два крайних объекта в одной душевной категории, образованной этой монадой.

Ну ладно, "простые программисты" (это для нас они простые) у себя в вузе на последнем курсе в Стэнфорде узнают, что функтор - это просто функция, которая беред функцию и возвращает функцию (интересно, что получится, если ее такую применить к самой себе, будет ли она по-прежнему брать функцию и возвращать функцию, или уже сломается?); в результате чего у них половина дизайн патернов превращается в какой-нибудь функтор, чем они и пугают робких выпускников Аризонского Госуниверситета (в Аризоне функторы не водятся).

Но где-то должна быть такая граница, что до нее они не боятся, а после уже боятся.

Или, может, свободная монада как раз будет этакой тайной тропой через границу, отличающую познаваемое от непознаваемого? Хз.

Комонаду же точно почти все боятся. Хотя (открою секрет) у каждой монады есть своя комонада (и у каждой комонады - своя монада).

Тот же Reader паттерн monad - в большинстве текстов про него я вижу не монаду, а комонаду. Традиция, претендующая на звание культурной, что ж.