Комментарии 26
Если в шифре нет дупла,
он никогда не станет Государственным Стандартом.
Хм. Одно дело математика, другое - конкретная реализация.
Вот статья про отечественные стандарты.
https://habr.com/ru/articles/530816/
Я думаю найти в них математическую дырку если она есть - вопрос технический. Но её может и не быть, а бэкдор для тех кому нужно делается в каждом конкретном программном продукте.
Дырка в математике на порядки ценнее. Реализаций много, пишутся они в опенсорсе. Иногда как часть других больших библиотек или проектов. Какая реализация станет популярной заранее неизвестно.
Я думаю найти в них математическую дырку если она есть - вопрос технический.
Конечно. В мире много специалистов по криптографии. А если этот американский бекдор существует, и его обнаружат китайцы?
В отечественном алгоритме потенциальную дырку уже нашли, показав, что создатели алгоритма по какой-то причине лгут, утверждая, что в важнейшем элементе алгоритма используются случайно сгенерированные данные.
Про ГОСТовский шифр Кузнечик, его SBox и потерянные сиды
Очередные странности в алгоритмах ГОСТ Кузнечик и Стрибог
Напрашивается прямая аналогия с Dual EC DRBG, где тоже использовалась, вроде бы, случайная константа, а оказалось, что она специально подобрана.
АНБ вроде как оштрафовали за это?
Я что-то не очень понял, это самое Q должно было удовлетворять каким-то внешним условиям?
Если нет, то кто мешает задать новое Q = Q*2+1 и продолжать использовать алгоритм?
кто мешает задать новое Q = Q*2+1 и продолжать использовать алгоритм?
Лень.
Значение Q представляет собой тип данных - массив случайных бит, точнее как доказала статья "случайных" бит. Такие значения в современной криптографии обязаны удовлетворять условиям природности происхождения для того чтобы было понятно что массив не скомпрометирован. Разработчик криптоалгоритма может в процессе обычного рабочего дня отыскать такие значения Q при которых эффективная энтропия (противодействующая брутфорсингам) сильно уменьшается - но только для того нападающего кто заведомо готов именно к этому Q.
Часто в криптографических алгоритмах нужно столько-то бит энтропии. Пример - константа k в алгоритме sha256, там были взяты первые биты от квадратных корней от первых 64-х простых числа. Я не знаю насколько эти значения соответствуют параметру случайности, но я точно уверен что константа k не подобрана с целью уменьшить эффективную энтропию, последовательные простые числа и квадратные корни это в криптографии по-своему модно.
Если нет, то кто мешает задать новое Q = Q*2+1 и продолжать использовать алгоритм?
Это будет или Васян- реализация, или в лучшем случае другой стандарт то есть другой алгоритм с другими характеристиками вывода, ответсвенность за который понесут другие криптографы.
Как знать. Возможно, выбирая это самое k перебрали "красивые" варианты источника битов и взяли наиболее или достаточно уязвимый.
Вы издеваетесь? Пользователю криптоалгоритма нужно доказательство, что магические числа в коде не были полученны путём долгого и тщательного подбора. Красивых вариантов вы и 200 не назовёте, а что такое 200 хэшей/секунду для подбора чего-нибудь что позволит затроянить весь Интернет?
Вдумайтесь какие сущности использованны для получения этих битов: простые числа, натуральные числа начиная аж с первого, корень самой популярной степени, и снова натуральные числа начиная аж с первого.
Мне и 2 варианта предложить сложно: например если заменить корень на квадрат то сильно пострадает случайность, но допустим ещё можно использовать битовые операции, например XOR тоже популярный. Пусть будет: для первых M чисел Фибоначчи (не видел их использования в криптографии но ОК) возводим каждое из них в квадрат и ксорим N первых бит результата с N последних. Ещё варианты красивых последовательностей?
Хорошие криптоалгоритмы публикуют документы о каждом числе. Как и почему оно такое. Любая магическая константа должна приводить к тому что этот криптоаглоритм бракуется и не используется.
Увы, к этому пришли не так давно и легаси еще много. Тут тот случай когда надо пинать свои системы и мигрировать на более правильные и верно доказанные алгоритмы. Это делает мир лучше.
Я лично включил tls1.3 на всем доступном мне продакшене. Карма улучшилась, волосы стали более шелковистоми.
Зачем использовать предложенный алгоритм, если уже в одном его месте нашли нестыковку?
Хотя взвешенный ответ наверняка находится в работах криптографов по этому алгоритму. Тем не менее, это был действительно один из кандидатов на конкурсе.
Например, в случае с российской криптографией, если вы хотите, чтобы у вас всё было сертифицировано и получены нужные бумажки, вы обязаны использовать одобренные значения, а не какие вам захотелось. При этом, эти одобренные значения заявлены, как сгенерированные случайным образом, а на самом деле, таковыми не являются.
Господи, Хабр, ты ли это? Статья о программировании. Интересная. Жесть. Чего только не напишуть.
@PatientZero, спасибо.
Двойные эллиптические кривые
Всё ж, не "двойные эллиптические кривые" - а "удвоенный/двойной генератор (RNG) на эллиптической кривой". Кривая там одна, точек-генераторов - используется две.
Поэтому для нашего proof of concept нужно использовать малое значение Q, которое легко атаковать
Тут, видимо, какая-то опечатка. Что такое "малое значение", применительно к точке кривой? Непонятно, как сравнивать точки (это большая проблема). В упомянутом бэкдоре, если задана точка P, то можно использовать всякую другую точку Q кривой, если вычислить подходящий под P скаляр. Что, собственно, и делается дальше. Другими словами: так как дальше параметры с бэкдором задаются прямо, то никакое требование "малости" тут не нужно.
Вообще, математический смысл данной атаки в том, что владельцу ключа от бэкдора известно соотношение между точками P и Q. То есть, известно такое δ, что δ*P = Q. Это, фактически, шаг протокола Диффи-Хеллмана на эллиптической кривой: P - генератор, δ - секретный ключ, Q - открытый. Зная Q и P вычислительно сложно найти δ (в чистом виде задача "дискретного логарифмирования"). В этом и смысл - для успешной атаки нужно знать секретный ключ, этим ключом "заперт" бэкдор, поэтому не каждая сторона может им воспользоваться. Зная связь между P и Q - можно по выдаче генератора определить его внутреннее состояние (s), перебрав совсем небольшое количество значений.
Жаль, что подобные статьи не пользуются по пулярностью в профильных каналах в сфере блокчейна. Там основные тезисы: если бы были уязвимости, блокчейн бы умер, а взломщики бы обогатились. Тем более есть всякие багбаунти программы с большой выплатой. Из этого (по их мнению) следует, что блокчейны безопасны. Тот простой нюанс, что внедрение таких бекдоров в криптографии нужно не для того, чтоб украсть деньги у пользователей и подорвать доверие в блокчейну, а чтобы контролировать финансовые потоки (США вряд ли отказались от этой идеи со времён утечки секретных международных торговых соглашений TISA) им в голову не приходит. Игнорируют они и чудное везение у биткоина (сильно увеличившее его капитализацию) там, где у других были бы очень большие проблемы - надовящее на мысли о помощи сильных мира сего.
Кстати о биткойне- там есть несколько вариантов раскрытия приватного ключа
Если 2 раза использовать одно и тоже случайное число k
Если найдутся 2 пары транзакций с разными приватными ключами,но повторяющимися числами k
Если известна разница между числами k
Если известно отношение между числами k
Во всех этих случаях раскрытие приватного ключа кошелька довольно простая задача
То есть получается АНБ изначально создала алгоритм, запрятав, бэкдор?
Походу идеально шифровать в 2 раунда Кузнечиком и AES.
Тайное уравнение, позволявшее США следить за всеми