Слабый ключ - Weak key

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

Историческое происхождение

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

Первые машины с потоковым шифрованием, которые также были роторными машинами, имели некоторые из тех же проблем слабых ключей, что и более традиционные роторные машины. T52 был один шифр машина такого потока , который имел слабые проблемы ключа.

Британцы впервые обнаружили трафик T52 летом и осенью 1942 года. Одно соединение было между Сицилией и Ливией под кодовым названием « Осетр », а другое - между Эгейским морем и Сицилией под кодовым названием « Скумбрия ». Операторы обоих каналов имели обыкновение шифровать несколько сообщений с одинаковыми настройками машины, получая большое количество глубин .

Было несколько (в основном несовместимых) версий T52: T52a и T52b (которые отличались только подавлением электрических шумов), T52c, T52d и T52e. Хотя T52a / b и T52c были криптологически слабыми, последние два были более продвинутыми устройствами; движение колес было прерывистым, решение о том, продвигать ли их вперед или нет, контролировалось логическими схемами, которые принимали в качестве входных данных от самих колес.

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

Слабые клавиши в DES

Блочный шифр DES имеет несколько специфических клавиш называются «слабые ключи» и «пол-слабых ключи». Это ключи, которые заставляют режим шифрования DES действовать идентично режиму дешифрования DES (хотя потенциально с другим ключом).

В процессе работы секретный 56-битный ключ разбивается на 16 подключей согласно расписанию ключей DES ; один подключ используется в каждом из шестнадцати раундов DES. Слабые ключи DES порождают шестнадцать идентичных подключей. Это происходит, когда ключ (выраженный в шестнадцатеричном формате ):

  • Чередующиеся единицы + нули (0x0101010101010101)
  • Чередование 'F' + 'E' (0xFEFEFEFEFEFEFEFE)
  • '0xE0E0E0E0F1F1F1F1'
  • '0x1F1F1F1F0E0E0E0E'

Если реализация не учитывает биты четности, соответствующие ключи с инвертированными битами четности также могут работать как слабые ключи:

  • все нули (0x0000000000000000)
  • все (0xFFFFFFFFFFFFFFFF)
  • '0xE1E1E1E1F0F0F0F0'
  • '0x1E1E1E1E0F0F0F0F'

При использовании слабых ключей результат перестановочного выбора 1 (PC-1) в расписании ключей DES приводит к тому, что ключи раунда либо все нули, либо все единицы, либо чередуются шаблоны ноль-один.

Поскольку все подключи идентичны, а DES является сетью Фейстеля , функция шифрования является самоинвертирующейся; то есть, несмотря на то, что однократное шифрование дает безопасный на вид зашифрованный текст, двойное шифрование дает исходный открытый текст.

DES также имеет полуслабые ключи , которые создают только два разных подключа, каждый из которых используется в алгоритме восемь раз: это означает, что они входят в пары K 1 и K 2 , и у них есть свойство, которое:

где Е К (М) является алгоритм шифрования шифрования сообщения M с ключом K . Всего существует шесть полуслабых пар ключей:

  • 0x011F011F010E010E и 0x1F011F010E010E01
  • 0x01E001E001F101F1 и 0xE001E001F101F101
  • 0x01FE01FE01FE01FE и 0xFE01FE01FE01FE01
  • 0x1FE01FE00EF10EF1 и 0xE01FE01FF10EF10E
  • 0x1FFE1FFE0EFE0EFE и 0xFE1FFE1FFE0EFE0E
  • 0xE0FEE0FEF1FEF1FE и 0xFEE0FEE0FEF1FEF1

Также существует 48, возможно, слабых ключей, которые производят только четыре отдельных подключа (вместо 16). Их можно найти в публикации NIST.

Эти слабые и полуслабые ключи не считаются «фатальными недостатками» DES. Для DES существует 2 56 (7,21 × 10 16 , около 72 квадриллионов) возможных ключей, из которых четыре являются слабыми, а двенадцать - полуслабыми. Это настолько малая часть возможного пространства ключей, что пользователям не о чем беспокоиться. При желании они могут проверить наличие слабых или полуслабых ключей при генерации ключей. Их очень мало, и их легко узнать. Обратите внимание, однако, что в настоящее время DES больше не рекомендуется для общего использования, так как все ключи DES могут быть подобраны с тех пор, как машина Deep Crack взламывала их в течение нескольких дней, прошли десятилетия , и, как это обычно делают компьютеры, появились более свежие решения. намного дешевле в этом масштабе времени. Примеры прогресса можно найти в статье Deep Crack.

Список алгоритмов со слабыми ключами

Этот список неполный ; вы можете помочь, добавив недостающие элементы из надежных источников .
  • DES, как описано выше.
  • RC4 . Слабые векторы инициализации RC4 позволяют злоумышленнику организовать атаку с использованием известного открытого текста и широко используются для компрометации безопасности WEP .
  • ИДЕЯ . Слабые ключи IDEA можно идентифицировать при атаке с выбранным открытым текстом . Они делают предсказуемой взаимосвязь между суммой XOR битов открытого текста и битами зашифрованного текста. Список этих ключей отсутствует, но их можно определить по их «структуре».
  • Blowfish . Слабые клавиши Blowfish создают плохие S-блоки , поскольку S-блоки Blowfish зависят от клавиш. Существует атака по выбранному открытому тексту против варианта Blowfish с уменьшенным числом раундов, которая упрощается за счет использования слабых ключей. Это не касается полностью Blowfish с 16 раундами.
  • GMAC . Часто используется при построении AES-GCM. Слабые ключи можно идентифицировать по групповому порядку ключа аутентификации H (для AES-GCM, H получается из ключа шифрования путем шифрования нулевого блока).
  • RSA и DSA . Август 2012 Надя Хенингер, Закир Дурумерик, Эрик Вустроу, Дж. Алекс Халдерман обнаружили, что TLS-сертификаты, которые они оценили, имеют общие ключи из-за недостаточной энтропии во время генерации ключей, и смогли получить DSA- и RSA-закрытые ключи TLS- и SSH-хостов, зная только общедоступные ключ.

Отсутствие слабых ключей как цель дизайна

Цель иметь «плоское» пространство ключей (т. Е. Все ключи одинаково сильны) всегда является целью разработки шифров. Как и в случае с DES, иногда допустимо небольшое количество слабых ключей при условии, что все они идентифицированы или поддаются идентификации. Алгоритм с неизвестными слабыми ключами не вызывает особого доверия.

Две основные меры против случайного использования слабого ключа:

  • Проверка сгенерированных ключей по списку известных слабых ключей или включение отказа от слабых ключей в планирование ключей.
  • Когда известно, что количество слабых ключей очень мало (по сравнению с размером пространства ключей), генерация ключа равномерно случайным образом гарантирует, что вероятность того, что он будет слабым, является (известным) очень малым числом.

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

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

Смотрите также

Рекомендации