NK
Раз уж я в понедельник утром вспомнил про RC4, то есть еще одна занятная штука. Двадцать лет назад равноапостольный гуру криптографии Брюс Шнайер придумал современный шифр Solitaire, который не требует ничего кроме ручки, бумаги и колоды карт. Собственно, похожими средствами людям приходилось обходиться тысячи лет, и многие, из-за недостатка воображения, поплатились за свои криптологические опыты головой. Как известно, каждый может придумать шифр, который сам не сможет взломать. Взрослые дяди и тёти редко уделяют внимание таким штукам, но так как автор Шнайер и шифр описан в Криптономиконе, то его испытывали на прочность, и да, в нем нашлись уязвимости. Пару дней назад у меня спросили, что я думаю о LC4, еще одна попытка в области "низко-технологичных" шифров, и что будет, если увеличить размер внутреннего состояния?
Алан Каминский, автор шифра, попытался упростить RC4 до "бумажного" вида и исправить несколько известных уязвимостей. Сильный перекос в начальных байтах ключевого потока и отсутствие аутентификации. "Бумажным" шифр можно назвать довольно условно, потому что фаза генерации ключа отсутствует, и вам придётся изрядно потрудиться, чтобы выбрать начальную перестановку случайно и равномерно, и при этом не накосячить. RC4 до сих пор иногда используется, как тяжкое наследие, и чтобы избавиться от уязвимых начальных последовательностей его "проматывают" вперёд на пару сотен байт, а Алан использует шестибуквенные nonces (передаются вместе с шифротекстом в открытом виде). Так же nonces защищают от повторного использования ключа. И, чтобы жизнь медом не казалась, в состояние непрерывно "домешивается" открытый текст. Называется автоключ, и если мне не изменяет память, впервые такой фокус использовал Виженер (то что сейчас называется "Виженером" - упрощенная версия). Не смотря на то, что это значительно усложняет расшифровку, люди очень долго не хотели пользоваться шифрами с обратной связью из-за того, что ошибка в одном символе превращает весь последующий текст в мусор.
На первый взгляд шифр выглядит неплохо. В случае идеальной PRP-функции можно расчитывать на 36! вариантов (~ 2^138, даже все вычисления, проведенные всеми майнерами биткоина и близко не могут подойти к подобному числу). Однако, именно потому что сообщение смешивается с внутренним состоянием, возможна plaintext-атака. Если у нас есть открытое и зашифрованное сообщение, то можно попытаться восстановить внутреннее состояние. Автор шифра оценил сложность атаки в 2^58, что всего в четыре раза больше, чем урезанный DES. "Взрослый" шифр уже отправился бы на помойку. Но, где взять открытый текст, если шифрование проводится вручную? (если вы не Никсон и у вас нет бригады "водопроводчиков") Тут как раз и пригодятся nonces. Закрыли две известные атаки, но открыли возможность для третьей. Но для "бумажного" шифра с короткими сообщениями всё, ну, какбы, приемлемо, хотя уже хуже, чем в "Пасьянсе". Как оценить стойкость, не сильно выжигая себе мозг? На статистических тестах шифр ведёт себя прилично. А давайте, просто превратим его в псевдослучайный генератор и посмотрим, что он нам выдаст? 138 бит состояния - не хухры-мухры. И вот тут сразу становятся видны короткие циклы (вплоть до нескольких десятков символов), в которые шифр сваливается с пугающей скоростью. Именно благодаря петле обратной связи. Хорошая попытка, автору респект и уважуха, но нет.
Я это к чему. Если у вас где-то завалялся RC4 - выкиньте его нахуй, и не пытайтесь изобретать велосипеды с квадратными колесами. Таких попыток было много и ошибаются чуть менее, чем все.
Алан Каминский, автор шифра, попытался упростить RC4 до "бумажного" вида и исправить несколько известных уязвимостей. Сильный перекос в начальных байтах ключевого потока и отсутствие аутентификации. "Бумажным" шифр можно назвать довольно условно, потому что фаза генерации ключа отсутствует, и вам придётся изрядно потрудиться, чтобы выбрать начальную перестановку случайно и равномерно, и при этом не накосячить. RC4 до сих пор иногда используется, как тяжкое наследие, и чтобы избавиться от уязвимых начальных последовательностей его "проматывают" вперёд на пару сотен байт, а Алан использует шестибуквенные nonces (передаются вместе с шифротекстом в открытом виде). Так же nonces защищают от повторного использования ключа. И, чтобы жизнь медом не казалась, в состояние непрерывно "домешивается" открытый текст. Называется автоключ, и если мне не изменяет память, впервые такой фокус использовал Виженер (то что сейчас называется "Виженером" - упрощенная версия). Не смотря на то, что это значительно усложняет расшифровку, люди очень долго не хотели пользоваться шифрами с обратной связью из-за того, что ошибка в одном символе превращает весь последующий текст в мусор.
На первый взгляд шифр выглядит неплохо. В случае идеальной PRP-функции можно расчитывать на 36! вариантов (~ 2^138, даже все вычисления, проведенные всеми майнерами биткоина и близко не могут подойти к подобному числу). Однако, именно потому что сообщение смешивается с внутренним состоянием, возможна plaintext-атака. Если у нас есть открытое и зашифрованное сообщение, то можно попытаться восстановить внутреннее состояние. Автор шифра оценил сложность атаки в 2^58, что всего в четыре раза больше, чем урезанный DES. "Взрослый" шифр уже отправился бы на помойку. Но, где взять открытый текст, если шифрование проводится вручную? (если вы не Никсон и у вас нет бригады "водопроводчиков") Тут как раз и пригодятся nonces. Закрыли две известные атаки, но открыли возможность для третьей. Но для "бумажного" шифра с короткими сообщениями всё, ну, какбы, приемлемо, хотя уже хуже, чем в "Пасьянсе". Как оценить стойкость, не сильно выжигая себе мозг? На статистических тестах шифр ведёт себя прилично. А давайте, просто превратим его в псевдослучайный генератор и посмотрим, что он нам выдаст? 138 бит состояния - не хухры-мухры. И вот тут сразу становятся видны короткие циклы (вплоть до нескольких десятков символов), в которые шифр сваливается с пугающей скоростью. Именно благодаря петле обратной связи. Хорошая попытка, автору респект и уважуха, но нет.
Я это к чему. Если у вас где-то завалялся RC4 - выкиньте его нахуй, и не пытайтесь изобретать велосипеды с квадратными колесами. Таких попыток было много и ошибаются чуть менее, чем все.
