Номер «ничего в рукаве»
Цифры, используемые криптографами для подтверждения того, что они работают добросовестно

В криптографии числа «ничего в рукаве» — это любые числа, которые по своей конструкции находятся вне подозрений о скрытых свойствах. Они используются при создании криптографических функций, таких как хэши и шифры . Эти алгоритмы часто нуждаются в рандомизированных константах для целей смешивания или инициализации. Криптограф может захотеть выбрать эти значения таким образом, чтобы продемонстрировать, что константы не были выбраны для гнусной цели, например, для создания бэкдора в алгоритме. [1] Эти опасения можно развеять, используя числа, созданные таким образом, чтобы оставалось мало места для корректировки. Примером может служить использование начальных цифр числа π в качестве констант. [2] Использование цифр π миллионов знаков после десятичной точки не будет считаться заслуживающим доверия, поскольку разработчик алгоритма мог выбрать эту начальную точку, поскольку она создавала секретную слабость, которую разработчик мог позже использовать, — хотя даже при кажущихся естественными выборах в возможных вариантах существует достаточно энтропии , из-за чего полезность этих чисел ставится под сомнение.

Цифры в позиционных представлениях действительных чисел, таких как π , e и иррациональные корни, как полагают, появляются с одинаковой частотой (см. нормальное число ). Такие числа можно рассматривать как противоположную крайность случайных чисел Чайтина-Колмогорова, поскольку они кажутся случайными, но имеют очень низкую информационную энтропию . Их использование мотивировано ранними спорами по поводу Стандарта шифрования данных правительства США 1975 года , который подвергся критике, поскольку не было предоставлено объяснения констант, используемых в его S-box (хотя позже было обнаружено, что они были тщательно отобраны для защиты от тогдашней засекреченной техники дифференциального криптоанализа ). [3] Таким образом, возникла необходимость в более прозрачном способе генерации констант, используемых в криптографии.

Карта, спрятанная в рукаве

«В рукаве ничего нет» — фраза, связанная с фокусниками , которые иногда перед началом фокуса держат рукава открытыми, чтобы показать, что у них нет спрятанных внутри предметов.

Примеры

  • Рон Ривест использовал функцию тригонометрического синуса для генерации констант для широко используемого хэша MD5 . [4]
  • Агентство национальной безопасности США использовало квадратные корни первых восьми простых целых чисел для создания хеш-констант в своих функциях «Алгоритма безопасного хеширования» SHA-1 и SHA-2 . [5] SHA-1 также использует 0123456789ABCDEFFEDCBA9876543210F0E1D2C3 в качестве своего начального хеш-значения.
  • Алгоритм шифрования Blowfish использует двоичное представление числа π − 3 для инициализации своего ключевого расписания . [2]
  • RFC 3526 описывает простые числа для обмена ключами в Интернете , которые также генерируются из числа π .
  • S -блок шифра NewDES взят из Декларации независимости США . [6]
  • Кандидат AES DFC выводит все свои произвольные константы, включая все записи S-box, из двоичного расширения e . [7]
  • В схеме ключей ARIA используется двоичное расширение 1/ π . [8]
  • В ключевом расписании шифра RC5 используются двоичные цифры как из числа e, так и из золотого сечения . [9]
  • Несколько шифров, включая TEA и Red Pike, используют 2654435769 или 0x9e3779b9, что равно ⌊ 2 32 / ϕ ⌋ , где ϕ — золотое сечение.
  • Хэш-функция BLAKE , финалист конкурса SHA-3 , использует таблицу из 16 константных слов, которые представляют собой первые 512 или 1024 бита дробной части числа π .
  • В схеме ключей шифра KASUMI для получения измененного ключа используется 0x123456789ABCDEFFEDCBA9876543210.
  • Семейство шифров Salsa20 использует строку ASCII «expand 32-byte k» или «expand 16-byte k» в качестве констант в процессе инициализации блока.
  • Bcrypt использует строку «OrpheanBeholderScryDoubt» в качестве строки инициализации [10] [11]

Контрпримеры

  • Утверждалось, что хеш -функция S-box Стрибог генерируется случайным образом, но была проведена ее обратная разработка и доказано, что она генерируется алгоритмически с некоторыми «загадочными» слабостями. [12]
  • Стандарт шифрования данных (DES) имеет константы, которые были выданы АНБ. Они оказались далеки от случайности, но вместо этого сделали алгоритм устойчивым к дифференциальному криптоанализу , методу, который в то время не был публично известен. [3]
  • Dual_EC_DRBG , криптографический псевдослучайный генератор битов , рекомендованный NIST , подвергся критике в 2007 году, поскольку константы, рекомендованные для использования в алгоритме, могли быть выбраны таким образом, чтобы позволить их автору предсказывать будущие результаты с учетом выборки сгенерированных в прошлом значений. [1] В сентябре 2013 года The New York Times написала, что «внутренние меморандумы, просочившиеся бывшим подрядчиком АНБ Эдвардом Сноуденом , предполагают, что АНБ создало один из генераторов случайных чисел, используемых в стандарте NIST 2006 года, называемом стандартом Dual EC DRBG, который содержит лазейку для АНБ». [13]
  • Кривые P стандартизированы NIST для эллиптической кривой криптографии . Коэффициенты в этих кривых генерируются путем хеширования необъясненных случайных начальных чисел , таких как:
    • С-224: bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5.
    • С-256: c49d3608 86e70493 6a6678e1 139d26b7 819f7e90.
    • С-384: a335926a a319a27a 1d00896a 6773a482 7acdac73.

Хотя это и не связано напрямую, после того, как был обнаружен бэкдор в Dual_EC_DRBG, подозрительные аспекты констант кривой P NIST [14] привели к опасениям [15] , что АНБ выбрало значения, которые дали им преимущество в поиске [16] закрытых ключей. [17] С тех пор многие протоколы и программы начали использовать Curve25519 в качестве альтернативы кривой NIST P-256.

Ограничения

Бернстайн и соавторы демонстрируют, что использование чисел «ничего в рукаве» в качестве отправной точки в сложной процедуре генерации криптографических объектов, таких как эллиптические кривые, может быть недостаточным для предотвращения вставки бэкдоров. Например, существует множество кандидатов на, казалось бы, безвредные и «неинтересные» простые математические константы, такие как π , e , гамма Эйлера , √2 , √3 , √5 , √7, log(2), (1 + √5)/2 , ζ(3) , ζ(5), sin(1), sin(2), cos(1), cos(2), tan(1) или tan(2). Для этих констант также существует несколько различных двоичных представлений на выбор. Если в качестве случайного начального числа используется константа, то для выбора также существует большое количество кандидатов на хеш-функции, таких как SHA-1, SHA-256, SHA-384, SHA-512, SHA-512/256, SHA3-256 или SHA3-384.

Если в процедуре выбора объекта имеется достаточно регулируемых параметров, комбинаторный взрыв гарантирует, что вселенная возможных вариантов дизайна и, по-видимому, простых констант может быть достаточно большой, чтобы автоматический поиск возможностей позволил построить объект с желаемыми скрытыми свойствами. [18]

Сноски

  1. ^ Брюс Шнайер (15.11.2007). «АНБ встроило секретный бэкдор в новый стандарт шифрования?». Wired News .
  2. ^ ab "Blowfish Paper". Архивировано из оригинала 2011-09-06 . Получено 2010-06-09 .
  3. ^ ab Брюс Шнайер . Прикладная криптография , второе издание, John Wiley and Sons, 1996, стр. 247.
  4. ^ RFC 1321 Раздел 3.4
  5. ^ FIPS 180-2: Secure Hash Standard (SHS) Архивировано 12 марта 2012 г. на Wayback Machine ( PDF , 236 кБ) – Текущая версия Secure Hash Standard (SHA-1, SHA-224, SHA-256, SHA-384 и SHA-512), 1 августа 2002 г., изменено 25 февраля 2004 г.
  6. ^ "Пересмотр NEWDES, Роберт Скотт, 1996". Архивировано из оригинала 2012-11-08 . Получено 2010-06-09 .
  7. ^ Анри Жильбер; М. Жиро; П. Хугворст; Ф. Нойан; Т. Порнин; Г. Пупар; Дж. Стерн; С. Воденай (19 мая 1998 г.). "Decorrelated Fast Cipher: an AES candidate" (PDF/ PostScript ) . Архивировано из оригинала 9 апреля 2008 г. . Получено 9 июня 2010 г. .
  8. ^ A. Biryukov ; C. De Cannière; J. Lano; B. Preneel ; SB Örs (7 января 2004 г.). Анализ безопасности и производительности ARIA ( PostScript ) (Отчет). Версия 1.2 — Финальный отчет. Katholieke Universiteit Leuven . Архивировано из оригинала 16 июля 2011 г. . Получено 9 июня 2010 г. .
  9. ^ Ривест, Р. Л. (1994). «Алгоритм шифрования RC5» (PDF) . Труды Второго международного семинара по быстрому программному шифрованию (FSE) 1994e . С. 86–96.
  10. ^ "src/lib/libc/crypt/bcrypt.c - diff - 1.3". cvsweb.openbsd.org . Архивировано из оригинала 2022-07-05 . Получено 2022-07-05 .
  11. ^ "хэш - Почему текст BCrypt "OrpheanBeholderScryDoubt"". Information Security Stack Exchange . Архивировано из оригинала 2023-07-10 . Получено 2022-07-05 .
  12. ^ Бирюков, Алекс; Перрен, Лео; Удовенко, Алексей (2016). «Реверс-инжиниринг S-box Стрибога, Кузнечика и СТРИБОБр1 (Полная версия)». Iacr-Еврокрипт-2016 . дои : 10.1007/978-3-662-49890-3_15. Архивировано из оригинала 02 августа 2023 г. Проверено 26 марта 2019 г.
  13. ^ Перлрот, Николь (10 сентября 2013 г.). «Правительство объявляет о шагах по восстановлению доверия к стандартам шифрования». The New York Times . Архивировано из оригинала 23 апреля 2015 г. Получено 11 сентября 2013 г.
  14. ^ "SafeCurves: Introduction". Архивировано из оригинала 2017-09-05 . Получено 2017-05-02 .
  15. ↑ Максвелл, Грегори (8 сентября 2013 г.). "[tor-talk] NIST одобрил криптографию в Tor?". Архивировано из оригинала 2014-10-02 . Получено 2015-05-20 .
  16. ^ "SafeCurves: Rigidity". safecurves.cr.yp.to . Архивировано из оригинала 2015-05-22 . Получено 2015-05-20 .
  17. ^ «АНБ взламывает большинство систем шифрования в Интернете — Шнайер о безопасности». www.schneier.com . Архивировано из оригинала 2017-12-15 . Получено 2015-05-20 .
  18. ^ Как манипулировать стандартами кривых: белая книга для черной шляпы Архивировано 08.03.2016 в Wayback Machine Дэниел Дж. Бернстайн, Тунг Чоу, Читчанок Чуенгсатиансуп, Андреас Хулсинг, Эран Ламбуидж, Таня Ланге , Рубен Нидерхаген и Кристин ван Вредендал, 27 сентября 2015 г., доступ получен 4 июня 2016 г.

Ссылки

  • Брюс Шнайер . Прикладная криптография , второе издание. John Wiley and Sons, 1996.
  • Эли Бихам , Ади Шамир , (1990). Дифференциальный криптоанализ криптосистем типа DES. Достижения в криптологии – CRYPTO '90. Springer-Verlag. 2–21.
Взято с "https://en.wikipedia.org/w/index.php?title=Nothing-up-my-sleeve_number&oldid=1251323019"