Тоже пролистал статью, пока вроде ничего криминального в плане стойкости; только обобщение устройства узла замены с вытекающей алгеброй. Но генератор этих узлов сотрудникам ТК-26, наверное, придется придумывать новый.
Не утрудитесь ссылочкой на оптимизацию, о которой вы говорите? Ведь в посте полный цикл как раз сводится к небольшому количеству (15) операций исключающее ИЛИ (XOR) с константами из небольшого массива (64 КБ для шифрования и 64 КБ для расшифрования).
Я вам ответил именно на ваш вопрос ;) ГОСТ во многом похож на AES; можно устроить очень похожие атаки на время загрузки векторов из таблиц, оно прямо зависит от значений байт промежуточного текста. Таблицы появляются только в оптимизированной версии шифра. В теории, при известном открытом тексте и точном способе измерять это время, можно попробовать определить байты первых двух цикловых ключей (половин секретного ключа). Но это тема отдельной статьи.
Полагаю, что можно устроить атаки, аналогичные описанным здесь; время загрузки очередного слагаемого Xi на очередном цикле шифрования прямо зависит от значения соответствующего байта промежуточного текста.
@AleksGRV Не осилили пост? В ней про структуру узлов замены написан целый раздел, даже ссылка на более полную работу представлена.
Но даже известное устройство узлов замены не могу назвать закладкой шифра, ведь полученные таким способом узлы обладают действительно хорошими криптографическими свойствами, и очевидным образом использовать эту структуру для дешифрования шифртекста или определения цикловых ключей я не вижу.
Автор этой статьи, Андрей Луценко, обладает рядом патентов на скоростную реализацию ГОСТ 28147 '89, ему экономически выгодно пиарить прежний стандарт шифрования.
Если же объективно говорить о производительности скоростных версий шифров на одной и той же платформе, то результаты оказались примерно следующие: ~170 МБ/с на поток для Магмы и ~150 МБ/с на поток для Кузнечика.
Сложно что-то сказать о криптостойкости алгоритма по сравнению с зарубежными аналогами, шифр сравнительно новый и пока мало исследован. На мой взгляд, он во многом похож на AES, выглядит очень крепко, очевидных слабых мест в нем нет.
В России более важными вопросами являются вопросы сертификации средств защиты информации; и с средствами, использующими зарубежную криптографию, вы попросту не пройдете сертификацию в органах. Поэтому здесь выбора особо и нет.
Да, кстати, насчет малой длины блока. Ну конечно, длина блока — критически важный параметр для криптосистемы. Поскольку любой блочный шифр может быть рассмотрен как некоторая подстановка на очень большом множестве (алфавите блоков), то любой шифр может быть взломан с использованием полной кодовой книги (при фиксированном ключе). Так, чем меньше выбранная длина блока, тем меньше памяти требуется злоумышленнику для размещения кодовой книги. Так, при длине блока в 32 бита, кодовая книга занимает, как вы правильно заметили, всего 32 * (2^32) бит, что примерно равно 18 ГБ, и, на мой взгляд, вполне осуществимо.
Нет, про 32 бита — это я в ответ на Ваш пост писал:
В принципе, даже это большой прогресс по отношению к одноразовому блокноту, где длина случайного блока данных должна быть равна длине шифруемого текста, и повторное использование ключа невозможно.
Для случайных подстановок длиной 32 бита уже можно реализовать шифрование на современной элементной базе. Интересно, не дает ли малая длина блока в 32 бит каких-то специфических слабостей шифра сама по себе?
А в схеме Even-Mansour длина блока совпадает с фактической длиной ключа.
А что если применить не конкретно схему Even-Mansour, а более общую схему — ключезависимую подстановку на блоке? Например, чтобы подстановка была истинно случайной и сама являлась ключом? Сводится ли такая схема к Even-Mansour? Если нет — то ломается ли она теми же методами, что Even-Mansour?
Вот как раз такой шифр — в котором каждому ключу соответствует своя истинно случайная подстановка на алфавите блоков — и называется идеальным шифром (не смогу сейчас по памяти сказать, кто ввел такое определение). Суть заключается в том, что именно таким должен быть идеальный шифр, да и был бы, если бы не проблема нехватки памяти. Можно ли атаковать такую криптосистему? Несомненно, с помощью общих методов криптоанализа. Но ни один из них существенно полный перебор не сократит.
32 бита — это просто смешно, а не криптостойкость (с, А. Е. Жуков). Любой сможет взломать такой шифр на домашнем компьютере. Приемлимой длиной ключа сейчас считается 128 бит (поправьте меня, если ошибаюсь). Проблема практического применения этой схемы в том и заключается, что подстановки на таких больших множествах хрен задашь занимают много места в памяти.
icoz, это блочный шифр. Вам достаточно бит секретного ключа, чтобы шифровать сколь угодно большое число блоков открытого текста (каждый блок имеет размер бит).
MichaelBorisov Я бы не стал сравнивать криптостойкость одноразового блокнота со стойкостью предложенной схемы, а дело вот в чем:
Одноразовый блокнот является абсолютно криптостойким (по Шеннону), это означает, что, даже имея неограниченные ресурсы (память, и время), Вам не удасться дешифровать шифртекст. Такая криптостойкость безотносительна, она не зависит ни от ресурсов злоумышленника, ни от величины параметра .
Схема Even–Mansour гарантирует лишь стойкость от любых полиномиальных атак. При отсутствии ограничений по времени выполнения атаки, либо по памяти, доступной атакующему, шифр легко ломается. Конкретнее об этом расскажу тогда в следующей публикации.
Обобщая вышесказанное: при одних и тех же условиях (неограниченные ресурсы) одноразовый блокнот стоек, а схема Even–Mansour легко вскрывается.
Такая модель вычисления предложена авторами, и только в рамках этой модели стойкость шифра доказана.
Я считаю, что злоумышленнику доступен не только оракул для функции подстановки, но и полное математическое описание этой функции, т.е. таблица либо формула.
Если подстановка случайная, то никакого математического (алгоритмического) описания у нее нет, а что касается таблицы замены — таблица вычислительно эквивалентна оракулу относительно временной сложности атаки, только занимает в памяти бит, что совершенно неудобно.
Если же подстановка псевдослучайна (например, задана суперпозицией преобразований, как в современных шифрах), то, даже если злоумышленнику известно ее устройство, это все равно ему не поможет, потому что иначе эта подстановка не была бы псевдослучайной согласно определению авторов. Другими словами, если существует полиномиальная атака на этот шифр, использующая особенности устройства выбранной подстановки, то такая подстановка не является псевдослучайной.
Приведу пример: если злоумышленнику заранее известно, что подстановка является инволюцией (обратна сама себе), то шифр уже не является стойким.
Не очень понимаю, что имеете в виду под кражей оракула)
Дело в том, что подстановка доступна всем, она не является частью секретного ключа. Даже если в качестве случайно выбрать тождественную подстановку, шифр все равно будет полиномиально стоек (ведь убедиться, что подстановка действительно тождественна, имея только оракула, можно только за экспоненциально большое число запросов к этому оракулу).
Никакой неясности в схеме нет, все прозрачно для злоумышленника. Есть четыре оракула, к которым он может обращаться, все оракулы для него — черные ящики. Схема шифра ему тоже известна, неизвестен только ключ шифрования.
Тоже пролистал статью, пока вроде ничего криминального в плане стойкости; только обобщение устройства узла замены с вытекающей алгеброй. Но генератор этих узлов сотрудникам ТК-26, наверное, придется придумывать новый.
Полагаю, что все сдвиги можно осуществлять за постоянное время: либо простоем конвейера, либо сдвигами фиктивного регистра.
Не утрудитесь ссылочкой на оптимизацию, о которой вы говорите? Ведь в посте полный цикл как раз сводится к небольшому количеству (15) операций исключающее ИЛИ (XOR) с константами из небольшого массива (64 КБ для шифрования и 64 КБ для расшифрования).
Я вам ответил именно на ваш вопрос ;) ГОСТ во многом похож на AES; можно устроить очень похожие атаки на время загрузки векторов из таблиц, оно прямо зависит от значений байт промежуточного текста. Таблицы появляются только в оптимизированной версии шифра. В теории, при известном открытом тексте и точном способе измерять это время, можно попробовать определить байты первых двух цикловых ключей (половин секретного ключа). Но это тема отдельной статьи.
Полагаю, что можно устроить атаки, аналогичные описанным здесь; время загрузки очередного слагаемого
Xiна очередном цикле шифрования прямо зависит от значения соответствующего байта промежуточного текста.@AleksGRV Не осилили пост? В ней про структуру узлов замены написан целый раздел, даже ссылка на более полную работу представлена.
Но даже известное устройство узлов замены не могу назвать закладкой шифра, ведь полученные таким способом узлы обладают действительно хорошими криптографическими свойствами, и очевидным образом использовать эту структуру для дешифрования шифртекста или определения цикловых ключей я не вижу.
@shifttstas Если они есть, мы об этом не узнаем ;)
Спасибо, надо будет пореверсить после релиза новой версии криптопровайдера.
@ru_crypt, уточните, 330 МБ/с в одном потоке? Какой процессор? Какой режим? Какой набор инструкций?
Не могу представить себе способа еще почти втрое алгоритмически ускорить базовое преобразование. Думаю, что такие скорости достижимы при
За наводку на
_mm_stream_load_si128спасибо, попробую.Автор этой статьи, Андрей Луценко, обладает рядом патентов на скоростную реализацию ГОСТ 28147 '89, ему экономически выгодно пиарить прежний стандарт шифрования.
Если же объективно говорить о производительности скоростных версий шифров на одной и той же платформе, то результаты оказались примерно следующие: ~170 МБ/с на поток для Магмы и ~150 МБ/с на поток для Кузнечика.
@Decker, mayorovp Спасибо, ошибку с
<algorithm>исправил.Сложно что-то сказать о криптостойкости алгоритма по сравнению с зарубежными аналогами, шифр сравнительно новый и пока мало исследован. На мой взгляд, он во многом похож на AES, выглядит очень крепко, очевидных слабых мест в нем нет.
В России более важными вопросами являются вопросы сертификации средств защиты информации; и с средствами, использующими зарубежную криптографию, вы попросту не пройдете сертификацию в органах. Поэтому здесь выбора особо и нет.
А в схеме Even-Mansour длина блока совпадает с фактической длиной ключа.
Вот как раз такой шифр — в котором каждому ключу соответствует своя истинно случайная подстановка на алфавите блоков — и называется идеальным шифром (не смогу сейчас по памяти сказать, кто ввел такое определение). Суть заключается в том, что именно таким должен быть идеальный шифр, да и был бы, если бы не проблема нехватки памяти. Можно ли атаковать такую криптосистему? Несомненно, с помощью общих методов криптоанализа. Но ни один из них существенно полный перебор не сократит.
хрен задашьзанимают много места в памяти.Обобщая вышесказанное: при одних и тех же условиях (неограниченные ресурсы) одноразовый блокнот стоек, а схема Even–Mansour легко вскрывается.
Такая модель вычисления предложена авторами, и только в рамках этой модели стойкость шифра доказана.
Если подстановка случайная, то никакого математического (алгоритмического) описания у нее нет, а что касается таблицы замены — таблица вычислительно эквивалентна оракулу относительно временной сложности атаки, только занимает в памяти
Если же подстановка псевдослучайна (например, задана суперпозицией преобразований, как в современных шифрах), то, даже если злоумышленнику известно ее устройство, это все равно ему не поможет, потому что иначе эта подстановка не была бы псевдослучайной согласно определению авторов. Другими словами, если существует полиномиальная атака на этот шифр, использующая особенности устройства выбранной подстановки, то такая подстановка не является псевдослучайной.
Приведу пример: если злоумышленнику заранее известно, что подстановка является инволюцией (обратна сама себе), то шифр уже не является стойким.
Дело в том, что подстановка доступна всем, она не является частью секретного ключа. Даже если в качестве
Никакой неясности в схеме нет, все прозрачно для злоумышленника. Есть четыре оракула, к которым он может обращаться, все оракулы для него — черные ящики. Схема шифра ему тоже известна, неизвестен только ключ шифрования.