openPGP в России / Новости / 2014 / Следите за константами: как в хэш-функции Стрибог можно спрятать бэкдор

30.10 // Следите за константами: как в хэш-функции Стрибог можно спрятать бэкдор

Разработка криптографических примитивов всегда привлекала внимание спецслужб. В криптографическом сообществе давно существовали подозрения, что правительственные агентства могут внедрять для своих шпионских целей бэкдоры в продвигаемые ими алгоритмы. Речь идёт об искусственных трудновыявляемых потайных ходах, позволяющих создателям алгоритма легко его взламывать.

Опасения такого рода только усилились после раскрытия Эдвардом Сноуденом программы Bullrun, которая указывала на то, что агентство национальной безопасности США умышленно внесло бэкдор в стандарт генератора псевдослучайных чисел на эллиптических кривых Dual_EC_DRBG, позволяющий по фрагментам гаммы раскрывать внутреннее состояние генератора. Предполагается, что за внедрение этого алгоритма в библиотеку RSA BSAFE фирма RSA Security получила от АНБ сумму в 10 миллионов долларов в ходе секретной сделки, немотря на то, что в ходе появления рекомендации от Национального института стандартов и технологий (NIST) возникли опасения, что стандарт подвергался злонамеренным манипуляциям со стороны АНБ в области подбора констант эллиптических кривых.

Ранее были немногочисленные исследования о создании алгоритмов с бэкдорами: были описаны теоретические возможности построения злонамеренных шифров CAST и LOKI, а впоследствии и хэш-функции SHA-1.

В 2010 году была предложена хэш-функция Стрибог, которая стала российским стандартом хэширования, что было отражено в стандарте IETF. В отличие от открыто разрабатываемых хэш-функций, в стандарте ГОСТ на хэширование не были обоснованы ни выбор функций, ни выбор множества случайно выглядящих констант, ни количество раундов. Это позволило исследователям Riham AlTawy и Amr M. Youssef из института разработки систем безопасности Университета Конкордиа (Монреаль, Квебек, Канада) разработать прототип методики секретного внедрения бэкдора в Стрибог.

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

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

Источник: Cryptology ePrint Archive.

См. также: Ошибка в структуре российской хэш-функции Stribog привела к её полнораундовому взлому, Интегральный криптоанализ хэш-функции ГОСТ Р 34.11-2012 Стрибог, STRIBOB: шифрование с аутентификацией на основе стандарта российской хэш-функции.

Комментарии [скрыть комментарии/форму]

—	*Гость* (30/10/2014 23:47) <#>

Причиной недоверия к алгоритму является уже факт разработки его в секретной службе. Чтобы они выдали в паблик продукт свободный от бэкдоров – такого просто быть не может. Для своих – секретные алгоритмы, а у стада не должно быть секретов от государства. В этом все спецслужбы однинаковы. Отличие лишь в том, что если в США им нужно подкупать разработчиков (10 млн для RSA), то в России они ввели законодательный запрет на разработку чистого крипто под угрозой лишения лицензии.

—	unknown (31/10/2014 10:02) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Криптографы оперируют более изящными понятиями, чем стадо и пастухи. Хотя, в целом к этому всё и сводится, но поведение злонамеренного создателя алгоритмов моделируется и в теории игр, и в разных методиках анализа протоколов. Так, можно выделить такие модели противника, разрабатывающего стандарты, как «злонамеренный разработчик — наивный и честный пользователь», «полузлонамеренный принципиальный стандартизатор», «стандартизатор с прогрессивными знаниями», «защитник своей команды» и пр. Достаточно интересно эта тема обыграна в слайдах file

Deniable and not self-harming trapdoors.

—	*Гость* (31/10/2014 12:08) <#>

Как быть с "пастухами"с разных частей света? Инструменты, которые используются каждыми (пастухами) для своих "стадов", могут быть использованы представителями "иного стада" (с другой части света). Или "пастухам" из разных ~~банд~~ частей света нечего скрывать друг от друга?

—	unknown (31/10/2014 13:01, исправлен 31/10/2014 13:04) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Если отбросить теории заговоров, то считается, что пока глобального ~~пастуха~~ наблюдателя нет, что и обеспечивает некую надежду на защиту разным пользователям.

На самом деле, не так легко встроить незаметный и неизвлекаемый бэкдор в алгоритм. Так что его с другой части света также могут определить. Другое дело, что как описано в слайдах и отчасти в работе Бернштейна, теоретически можно создать отрицаемый бэкдор вида: можно доказать, что он может быть, сгенерив самому похожие константы, функции, структуры, но подобрать к нему точный ключ тому, кто не сам его генерировал можно только за 2¹²⁸ шагов. Так что, стандартизатор-злоумышленник вида АНБ и прочее ГБ, ничего не потеряет (кроме некоей эфемерной репутации) в случае раскрытия способа создания такого бэкдора на примере конкретного алгортима: конкретный ключ к нему будет неизвестен раскрывшей стороне и закрытые коммуникации будут от неё о прежнему закрыты. Есть и аргумент недостижимости такого подхода в ряде случаев: если бы так умели делать для симметричных шифров, то с помощью симметричного алгоритма можно было бы компактно заменить асимметричную криптографию, но никто пока не показал, что так возможно в принципе.

Ваша оценка документа [показать результаты]