Криптография и Свобода - 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
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