Блочный шифр

Тип шифра

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

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

Определение

Блочный шифр состоит из двух парных алгоритмов : один для шифрования E , а другой для дешифрования D. ^[1] Оба алгоритма принимают два входных параметра: входной блок размером n бит и ключ размером k бит; и оба дают n -битный выходной блок. Алгоритм дешифрования D определяется как обратная функция шифрования, т.е. D = E ^-1 . Более формально, ^{[2] [3]} блочный шифр задается функцией шифрования.

${\displaystyle E_{K}(P):=E(K,P):\{0,1\}^{k}\times \{0,1\}^{n}\rightarrow \{0,1\}^{n},}$

который принимает на вход ключ K длиной в битах k (называемый размером ключа ) и битовую строку P длиной n (называемую размером блока ) и возвращает строку C из n бит. P называется открытым текстом , а C называется зашифрованным текстом . Для каждого K функция E _K ( P ) должна быть обратимым отображением на {0,1} ⁿ . Обратная для E определяется как функция

${\displaystyle E_{K}^{-1}(C):=D_{K}(C)=D(K,C):\{0,1\}^{k}\times \{0,1\}^{n}\rightarrow \{0,1\}^{n},}$

взяв ключ K и зашифрованный текст C , чтобы вернуть значение открытого текста P , такое, что

${\displaystyle \forall P:D_{K}(E_{K}(P))=P.}$

Например, алгоритм блочного шифрования может принимать на входе 128-битный блок открытого текста и выводить соответствующий 128-битный блок зашифрованного текста. Точное преобразование контролируется с помощью второго входа — секретного ключа. Дешифрование аналогично: в этом примере алгоритм дешифрования берет 128-битный блок зашифрованного текста вместе с секретным ключом и дает исходный 128-битный блок открытого текста. ^[4]

Для каждого ключа K E _K является перестановкой ( биективным отображением) набора входных блоков. Каждая клавиша выбирает одну перестановку из множества возможных перестановок. ^[5] ${\displaystyle (2^{n})!}$

История

Современный дизайн блочных шифров основан на концепции итеративного шифра произведения . В своей основополагающей публикации 1949 года «Коммуникационная теория секретных систем » Клод Шеннон проанализировал продуктовые шифры и предложил их как средство эффективного повышения безопасности путем объединения простых операций, таких как замены и перестановки . ^[6] Итерированные шифры продукта выполняют шифрование в несколько раундов , каждый из которых использует отдельный подключ, полученный из исходного ключа. Одна широко распространенная реализация таких шифров, названная сетью Фейстеля в честь Хорста Фейстеля, особенно реализована в шифре DES . ^[7] Многие другие реализации блочных шифров, такие как AES , классифицируются как сети замены-перестановки . ^[8]

Корень всех форматов криптографических блоков, используемых в стандарте безопасности данных индустрии платежных карт (PCI DSS) и стандартах Американского национального института стандартов (ANSI), лежит в блоке ключей Atalla (AKB), который был ключевым нововведением Atalla Box , первый аппаратный модуль безопасности (HSM). Он был разработан в 1972 году Мохамедом М. Аталлой , основателем корпорации Atalla (ныне Utimaco Atalla ), и выпущен в 1973 году. AKB представлял собой ключевой блок, который необходим для безопасного обмена симметричными ключами или ПИН-кодами с другими участниками банковской отрасли. . Этот безопасный обмен осуществляется с использованием формата AKB. ^[9] Atalla Box защищал более 90% всех действующих сетей банкоматов по состоянию на 1998 год, ^[10] и продукты Atalla по-прежнему обеспечивают безопасность большинства транзакций банкоматов в мире по состоянию на 2014 год. ^[11]

Публикация шифра DES Национальным бюро стандартов США (впоследствии Национальным институтом стандартов и технологий США , NIST) в 1977 году сыграла фундаментальную роль в общественном понимании конструкции современного блочного шифра. Это также повлияло на академическое развитие криптоаналитических атак . И дифференциальный , и линейный криптоанализ возникли в результате исследований по разработке DES. По состоянию на 2016 год ^{[обновлять]}существует целый ряд методов атак, против которых блочный шифр должен быть защищен, а также устойчив к атакам методом перебора .

Дизайн

Итерированные блочные шифры

Большинство алгоритмов блочного шифрования классифицируются как итерационные блочные шифры , что означает, что они преобразуют блоки открытого текста фиксированного размера в блоки зашифрованного текста идентичного размера посредством многократного применения обратимого преобразования, известного как функция раунда , причем каждая итерация называется раундом . . ^[12]

Обычно функция раунда R принимает разные ключи раунда K _i ^{в качестве второго входного} сигнала, который является производным от исходного ключа ^:

${\displaystyle M_{i}=R_{K_{i}}(M_{i-1})}$

где — открытый текст и зашифрованный текст, где r — количество раундов. ${\displaystyle M_{0}}$ ${\displaystyle M_{r}}$

Часто в дополнение к этому используется отбеливание ключей . В начале и в конце данные модифицируются с помощью ключевого материала (часто с помощью XOR , но также используются простые арифметические операции, такие как сложение и ^{вычитание ) :}

${\displaystyle M_{0}=M\oplus K_{0}}$

${\displaystyle M_{i}=R_{K_{i}}(M_{i-1})\;;\;i=1\dots r}$

${\displaystyle C=M_{r}\oplus K_{r+1}}$

Учитывая одну из стандартных схем построения итерированных блочных шифров, довольно легко построить криптографически безопасный блочный шифр, просто используя большое количество раундов. Однако это сделает шифр неэффективным. Таким образом, эффективность является важнейшим дополнительным критерием проектирования профессиональных шифров. Кроме того, хороший блочный шифр предназначен для предотвращения атак по побочным каналам, таких как предсказание ветвей и доступ к памяти в зависимости от ввода, которые могут привести к утечке секретных данных через состояние кэша или время выполнения. Кроме того, шифр должен быть кратким для небольших аппаратных и программных реализаций. Наконец, шифр должен быть легко анализируемым, чтобы можно было показать, до скольких раундов шифр необходимо сократить, чтобы существующие криптографические атаки сработали, и, наоборот, чтобы можно было показать, что количество фактических раундов достаточно велик, чтобы защититься от них. ^{[ нужна цитата ]}

Сети замены-перестановки

Эскиз сети подстановки-перестановки с тремя раундами, шифрующей блок открытого текста длиной 16 бит в блок зашифрованного текста длиной 16 бит. S-блоки — это Si , P-блоки — это тот же _P , а раундовые ключи — это K _i .

Один важный тип итерированного блочного шифра, известный как сеть замены-перестановки (SPN), принимает блок открытого текста и ключ в качестве входных данных и применяет несколько чередующихся раундов, состоящих из этапа замены, за которым следует этап перестановки , - для создания каждого блока зашифрованного текста. выход. ^[13] На этапе нелинейной замены ключевые биты смешиваются с битами открытого текста, что приводит Шеннона в замешательство . Затем на этапе линейной перестановки избыточность рассеивается, создавая диффузию . ^{[14] [15]}

Блок замены (S-box) заменяет небольшой блок входных битов другим блоком выходных битов. Эта замена должна быть взаимно однозначной , чтобы обеспечить обратимость (следовательно, расшифровку). Защищенный S-блок будет обладать свойством, заключающимся в том, что изменение одного входного бита приведет к изменению в среднем около половины выходных битов, демонстрируя так называемый лавинный эффект , то есть он обладает свойством, согласно которому каждый выходной бит будет зависеть от каждого входного бита. ^[16]

Блок перестановок (P-box) — это перестановка всех битов: он принимает выходные данные всех S-блоков одного раунда, переставляет биты и передает их в S-блоки следующего раунда. Хороший P-блок обладает тем свойством, что выходные биты любого S-блока распределяются по как можно большему количеству входов S-блока. ^{[ нужна цитата ]}

В каждом раунде ключ раунда (полученный из ключа с помощью некоторых простых операций, например, с использованием S-блоков и P-блоков) объединяется с помощью некоторой групповой операции, обычно XOR . ^{[ нужна цитата ]}

Дешифрование выполняется путем простого обратного процесса (с использованием инверсий S-блоков и P-блоков и применения раундовых ключей в обратном порядке). ^[17]

Шифры Фейстеля

Многие блочные шифры, такие как DES и Blowfish, используют структуры, известные как шифры Фейстеля.

В шифре Фейстеля блок открытого текста, подлежащего шифрованию, разделяется на две половины одинакового размера. Функция округления применяется к одной половине с использованием подраздела, а затем выполняется операция XOR с другой половиной. Затем две половинки меняются местами. ^[18]

Пусть это функция раунда и пусть это дополнительные клавиши для раундов соответственно. ${\displaystyle {\rm {F}}}$ ${\displaystyle K_{0},K_{1},\ldots ,K_{n}}$ ${\displaystyle 0,1,\ldots ,n}$

Тогда основная операция выглядит следующим образом: ^[18]

Разделите блок открытого текста на две равные части ( , ) ${\displaystyle L_{0}}$ ${\displaystyle R_{0}}$

Для каждого раунда вычислите ${\displaystyle i=0,1,\dots ,n}$

${\displaystyle L_{i+1}=R_{i}\,}$

${\displaystyle R_{i+1}=L_{i}\oplus {\rm {F}}(R_{i},K_{i})}$.

Тогда зашифрованный текст . ${\displaystyle (R_{n+1},L_{n+1})}$

Дешифрование зашифрованного текста осуществляется путем вычисления ${\displaystyle (R_{n+1},L_{n+1})}$ ${\displaystyle i=n,n-1,\ldots ,0}$

${\displaystyle R_{i}=L_{i+1}\,}$

${\displaystyle L_{i}=R_{i+1}\oplus {\rm {F}}(L_{i+1},K_{i})}$.

Затем снова открытый текст. ${\displaystyle (L_{0},R_{0})}$

Одним из преимуществ модели Фейстеля по сравнению с сетью подстановки-перестановки является то, что функция округления не обязательно должна быть обратимой. ^[19] ${\displaystyle {\rm {F}}}$

Шифры Лая – Мэсси

Схема Лая–Мэсси. Архетипическим шифром, использующим его, является IDEA .

Схема Лая-Месси предлагает свойства безопасности, аналогичные свойствам структуры Фейстеля . У него также есть то преимущество, что функция округления не обязательно должна быть обратимой. Еще одно сходство заключается в том, что он также разбивает входной блок на две равные части. Однако к разнице между ними применяется функция округления, а затем результат добавляется к обоим полублокам. ${\displaystyle \mathrm {F} }$

Пусть это функция раунда и функция полураунда, а также дополнительные клавиши для раундов соответственно. ${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {H} }$ ${\displaystyle K_{0},K_{1},\ldots ,K_{n}}$ ${\displaystyle 0,1,\ldots ,n}$

Тогда основная операция выглядит следующим образом:

Разделите блок открытого текста на две равные части ( , ) ${\displaystyle L_{0}}$ ${\displaystyle R_{0}}$

Для каждого раунда вычислите ${\displaystyle i=0,1,\dots ,n}$

${\displaystyle (L_{i+1}',R_{i+1}')=\mathrm {H} (L_{i}'+T_{i},R_{i}'+T_{i}),}$

где и ${\displaystyle T_{i}=\mathrm {F} (L_{i}'-R_{i}',K_{i})}$ ${\displaystyle (L_{0}',R_{0}')=\mathrm {H} (L_{0},R_{0})}$

Тогда зашифрованный текст . ${\displaystyle (L_{n+1},R_{n+1})=(L_{n+1}',R_{n+1}')}$

Дешифрование зашифрованного текста осуществляется путем вычисления ${\displaystyle (L_{n+1},R_{n+1})}$ ${\displaystyle i=n,n-1,\ldots ,0}$

${\displaystyle (L_{i}',R_{i}')=\mathrm {H} ^{-1}(L_{i+1}'-T_{i},R_{i+1}'-T_{i})}$

где и ${\displaystyle T_{i}=\mathrm {F} (L_{i+1}'-R_{i+1}',K_{i})}$ ${\displaystyle (L_{n+1}',R_{n+1}')=\mathrm {H} ^{-1}(L_{n+1},R_{n+1})}$

Затем снова открытый текст. ${\displaystyle (L_{0},R_{0})=(L_{0}',R_{0}')}$

Операции

ARX ​​(добавить-повернуть-XOR)

Многие современные блочные шифры и хэши представляют собой алгоритмы ARX — их функция округления включает только три операции: (A) модульное сложение, (R) вращение с фиксированной величиной вращения и (X) XOR . Примеры включают ChaCha20 , Speck , XXTEA и BLAKE . Многие авторы рисуют сеть ARX, своего рода диаграмму потока данных , чтобы проиллюстрировать такую ​​круглую функцию. ^[20]

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

Прочие операции

Другие операции, часто используемые в блочных шифрах, включают зависящее от данных вращение, как в RC5 и RC6 , поле подстановки, реализованное в виде таблицы поиска , как в Data Encryption Standard и Advanced Encryption Standard , поле перестановки и умножение, как в IDEA .

Режимы работы

Небезопасное шифрование изображения в результате кодирования в режиме электронной кодовой книги (ECB).

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

Чтобы преодолеть это ограничение, было разработано несколько так называемых режимов работы блочного шифрования ^{[22] [23]} и указано в национальных рекомендациях, таких как NIST 800-38A ^[24] и BSI TR-02102 ^[25], а также в международных стандартах, таких как ИСО/МЭК 10116 . ^[26] Общая концепция заключается в использовании рандомизации данных открытого текста на основе дополнительного входного значения, часто называемого вектором инициализации , для создания так называемого вероятностного шифрования . ^[27] В популярном режиме цепочки блоков шифра (CBC) для обеспечения безопасности шифрования вектор инициализации, передаваемый вместе с открытым текстовым сообщением, должен быть случайным или псевдослучайным значением, которое добавляется методом « исключающее или» к первому значению. блок открытого текста до его шифрования. Результирующий блок зашифрованного текста затем используется в качестве нового вектора инициализации для следующего блока открытого текста. В режиме обратной связи шифрования (CFB), который эмулирует самосинхронизирующийся потоковый шифр , вектор инициализации сначала шифруется, а затем добавляется в блок открытого текста. Режим выходной обратной связи (OFB) многократно шифрует вектор инициализации для создания потока ключей для эмуляции синхронного потокового шифра . Новый режим счетчика (CTR) аналогичным образом создает поток ключей, но имеет то преимущество, что в качестве векторов инициализации требуются только уникальные, а не (псевдо)случайные значения; необходимая случайность определяется внутренним образом путем использования вектора инициализации в качестве счетчика блоков и шифрования этого счетчика для каждого блока. ^[24]

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

Заполнение

Некоторые режимы, такие как режим CBC, работают только с полными блоками открытого текста. Простого расширения последнего блока сообщения нулевыми битами недостаточно, поскольку это не позволяет получателю легко различать сообщения, которые отличаются только количеством битов заполнения. Что еще более важно, такое простое решение приводит к очень эффективным атакам оракулов с заполнением . ^[29] Поэтому необходима подходящая схема заполнения , чтобы расширить последний блок открытого текста до размера блока шифра. Хотя многие популярные схемы, описанные в стандартах и ​​литературе, оказались уязвимыми для атак оракула заполнения, ^{[29] [30]} решение, которое добавляет один бит, а затем расширяет последний блок нулевыми битами, стандартизируется как « Метод заполнения 2" в ISO/IEC 9797-1, ^[31] доказал свою безопасность против этих атак. ^[30]

Криптоанализ

Атаки грубой силы

Это свойство приводит к квадратичному ухудшению безопасности шифра, и его необходимо учитывать при выборе размера блока. Однако существует компромисс, поскольку большие размеры блоков могут привести к тому, что алгоритм станет неэффективным в работе. ^[32] Более ранние блочные шифры, такие как DES , обычно выбирали размер блока 64 бита, в то время как новые конструкции, такие как AES , поддерживают размеры блока 128 бит или более, при этом некоторые шифры поддерживают диапазон различных размеров блоков. ^[33]

Дифференциальный криптоанализ

Линейный криптоанализ

Линейный криптоанализ — это форма криптоанализа, основанная на поиске аффинных приближений к действию шифра . Линейный криптоанализ — одна из двух наиболее широко используемых атак на блочные шифры; другой — дифференциальный криптоанализ . ^[34]

Открытие приписывается Мицуру Мацуи , который первым применил эту технику к шифру FEAL (Мацуи и Ямагиши, 1992). ^[35]

Интегральный криптоанализ

Интегральный криптоанализ — это криптоаналитическая атака, которая особенно применима к блочным шифрам, основанным на сетях замены-перестановки. В отличие от дифференциального криптоанализа, который использует пары выбранных открытых текстов с фиксированной разницей XOR, интегральный криптоанализ использует наборы или даже мультинаборы выбранных открытых текстов, часть которых остается постоянной, а другая часть варьируется во всех возможностях. Например, атака может использовать 256 выбранных открытых текстов, у которых все бита, кроме 8, одинаковы, но все они различаются по этим 8 битам. Такой набор обязательно имеет сумму XOR, равную 0, а суммы XOR соответствующих наборов зашифрованных текстов предоставляют информацию о работе шифра. Этот контраст между различиями между парами текстов и суммами более крупных наборов текстов вдохновил на название «интегральный криптоанализ», заимствовав терминологию исчисления. ^{[ нужна цитата ]}

Другие методы

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

В дополнение к линейному и дифференциальному криптоанализу существует растущий каталог атак: усеченный дифференциальный криптоанализ , частичный дифференциальный криптоанализ, интегральный криптоанализ , который включает в себя квадратичные и интегральные атаки, атаки слайдом , атаки бумеранга , атаку XSL , невозможный дифференциальный криптоанализ и алгебраический атаки. Чтобы новая конструкция блочного шифра вызывала доверие, она должна продемонстрировать доказательства защиты от известных атак. ^{[ нужна цитата ]}

Доказуемая безопасность

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

Этот общий подход к криптографии – доказательство безопасности алгоритмов более высокого уровня (таких как CBC) при явно сформулированных предположениях относительно их компонентов (таких как блочный шифр) – известен как доказуемая безопасность .

Стандартная модель

Неформально, блочный шифр в стандартной модели безопасен, если злоумышленник не может отличить блочный шифр (оснащенный случайным ключом) от случайной перестановки.

Точнее, пусть E — n -битный блочный шифр. Представим себе следующую игру:

1. Человек, управляющий игрой, подбрасывает монету.
   • Если монета выпадает орлом, он выбирает случайный ключ K и определяет функцию f = E _K.
   • Если монета выпадает решкой, он выбирает случайную перестановку π в наборе n -битных строк и определяет функцию f = π .
2. Злоумышленник выбирает n -битную строку X , а человек, запускающий игру, сообщает ему значение f ( X ).
3. Шаг 2 повторяется всего q раз. (Каждое из этих q взаимодействий представляет собой запрос .)
4. Злоумышленник догадывается, как упала монета. Он выигрывает, если его предположение верно.

Злоумышленник, которого мы можем смоделировать как алгоритм, называется противником . Функция f (которую злоумышленник смог запросить) называется оракулом .

Обратите внимание, что противник может тривиально обеспечить 50%-ный шанс на победу, просто угадывая наугад (или даже, например, всегда угадывая «орла»). Поэтому пусть P _E ( A ) обозначает вероятность того, что противник A выиграет эту игру против E , и определим преимущество A как 2 ( P E ( _A ) − 1/2). Отсюда следует, что если А угадает случайно, его преимущество будет равно 0; с другой стороны, если A всегда побеждает, то его преимущество равно 1. Блочный шифр E представляет собой псевдослучайную перестановку (PRP), если ни один противник не имеет преимущества, значительно большего, чем 0, с учетом заданных ограничений на q и время работы противника. . Если на шаге 2 выше у противников есть возможность изучить f ⁻¹ ( X ) вместо f ( X ) (но при этом они имеют лишь небольшие преимущества), то E является сильной PRP (SPRP). Противник является неадаптивным, если он выбирает все значения q для X до начала игры (то есть он не использует никакой информации, полученной из предыдущих запросов, для выбора каждого X в ходе игры).

Эти определения оказались полезными для анализа различных режимов работы. Например, можно определить аналогичную игру для измерения безопасности алгоритма шифрования на основе блочного шифра, а затем попытаться показать (посредством аргумента сокращения ), что вероятность победы противника в этой новой игре ненамного больше, чем P _E ( A ) для некоторого A. (Сокращение обычно обеспечивает ограничения на q и время работы A .) Аналогично, если P _E ( A ) мало для всех соответствующих A , то ни один злоумышленник не имеет значительной вероятности выиграть новую игру. Это формализует идею о том, что алгоритм более высокого уровня наследует безопасность блочного шифра.

Идеальная модель шифрования

Практическая оценка

На практике блочные шифры можно оценивать по множеству критериев. Общие факторы включают: ^{[36] [37]}

• Ключевые параметры, такие как размер ключа и размер блока, оба из которых обеспечивают верхнюю границу безопасности шифра.
• Предполагаемый уровень безопасности , который основан на доверии, полученном в конструкции блочного шифра после того, как она в значительной степени выдержала значительные усилия в области криптоанализа с течением времени, математической обоснованности конструкции и существовании практических или сертификационных атак ^[38] .
• Сложность шифра и его пригодность для реализации в аппаратном или программном обеспечении . Аппаратные реализации могут измерять сложность с точки зрения количества вентилей или энергопотребления, которые являются важными параметрами для устройств с ограниченными ресурсами.
• Производительность шифра с точки зрения пропускной способности обработки на различных платформах, включая требования к памяти .
• Стоимость шифрования относится к лицензионным требованиям, которые могут применяться в связи с правами интеллектуальной собственности .
• Гибкость шифрования включает в себя его способность поддерживать несколько размеров ключей и длин блоков .

Известные блочные шифры

Люцифер / ДЕС

Люцифер обычно считается первым гражданским блочным шифром, разработанным в IBM в 1970-х годах на основе работы Хорста Фейстеля . Пересмотренная версия алгоритма была принята в качестве федерального стандарта обработки информации правительства США : FIPS PUB 46 Data Encryption Standard (DES). ^[39] Он был выбран Национальным бюро стандартов США (NBS) после публичного приглашения к участию и некоторых внутренних изменений со стороны NBS (и, возможно, АНБ ). DES был публично выпущен в 1976 году и широко использовался. ^{[ нужна цитата ]}

DES был разработан, среди прочего, для противодействия определенной криптоаналитической атаке, известной АНБ и вновь открытой IBM, хотя и неизвестной публично, пока она не была вновь открыта заново и опубликована Эли Бихамом и Ади Шамиром в конце 1980-х годов. Этот метод называется дифференциальным криптоанализом и остается одной из немногих универсальных атак на блочные шифры; линейный криптоанализ — еще один метод, который, возможно, был неизвестен даже АНБ до его публикации Мицуру Мацуи . DES послужил толчком к большому количеству других работ и публикаций в области криптографии и криптоанализа в открытом сообществе и вдохновил множество новых разработок шифров. ^{[ нужна цитата ]}

DES имеет размер блока 64 бита и размер ключа 56 бит. 64-битные блоки стали обычным явлением в конструкциях блочных шифров после DES. Длина ключа зависела от нескольких факторов, включая государственное регулирование. Многие наблюдатели ^{[ кто? ]} в 1970-х заметил, что 56-битная длина ключа, используемая для DES, слишком коротка. Со временем его неадекватность стала очевидна, особенно после того, как в 1998 году Electronic Frontier Foundation продемонстрировала специальную машину, предназначенную для взлома DES . Расширение DES, Triple DES , осуществляет тройное шифрование каждого блока либо с помощью двух независимых ключей (112-битный ключ и 80-битная безопасность), либо трех независимых ключей (168-битный ключ и 112-битная безопасность). Он получил широкое распространение в качестве замены. По состоянию на 2011 год версия с тремя ключами по-прежнему считается безопасной, хотя стандарты Национального института стандартов и технологий (NIST) больше не разрешают использование версии с двумя ключами в новых приложениях из-за ее 80-битного уровня безопасности. ^[40]

ИДЕЯ

Международный алгоритм шифрования данных ( IDEA ) — это блочный шифр, разработанный Джеймсом Мэсси из ETH Zurich и Сюэцзя Лаем ; Впервые он был описан в 1991 году как предполагаемая замена DES.

IDEA оперирует 64-битными блоками с использованием 128-битного ключа и состоит из серии из восьми одинаковых преобразований (раунд ) и выходного преобразования (полураунд ) . Процессы шифрования и дешифрования аналогичны. IDEA обеспечивает большую часть своей безопасности за счет чередования операций из разных групп — модульного сложения и умножения, а также побитового исключающего или (XOR) , — которые в некотором смысле алгебраически «несовместимы».

Разработчики проанализировали IDEA, чтобы измерить его устойчивость к дифференциальному криптоанализу , и пришли к выводу, что при определенных предположениях он неуязвим. Об успешных линейных или алгебраических слабостях не сообщалось. По состоянию на 2012 год ^[update]лучшая атака, применимая ко всем ключам, может сломать полную 8,5-раундовую IDEA с использованием атаки с узкими бикликами примерно в четыре раза быстрее, чем грубая сила.

RC5

Один раунд (два полураунда) блочного шифра RC5.

RC5 — это блочный шифр, разработанный Рональдом Ривестом в 1994 году, который, в отличие от многих других шифров, имеет переменный размер блока (32, 64 или 128 бит), размер ключа (от 0 до 2040 бит) и количество раундов (от 0 до 2040 бит). 255). Первоначально предложенный выбор параметров предусматривал размер блока 64 бита, 128-битный ключ и 12 раундов.

Ключевой особенностью RC5 является использование ротации в зависимости от данных; одной из целей RC5 было стимулировать изучение и оценку таких операций как криптографических примитивов. RC5 также состоит из ряда модульных дополнений и XOR. Общая структура алгоритма представляет собой сеть типа Фейстеля . Процедуры шифрования и дешифрования можно указать в нескольких строках кода. Расписание ключей, однако, более сложное: расширение ключа осуществляется с использованием, по сути, односторонней функции с двоичными разложениями как e , так и золотого сечения в качестве источников « ничего в запасе ». Дразнящая простота алгоритма вместе с новизной вращения, зависящего от данных, сделали RC5 привлекательным объектом изучения для криптоаналитиков.

12-раундовый RC5 (с 64-битными блоками) подвержен дифференциальной атаке с использованием ²⁴⁴ выбранных открытых текстов. ^[41] В качестве достаточной защиты предлагается 18–20 патронов.

Рейндал / AES

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

Принятый NIST в 2001 году, AES имеет фиксированный размер блока 128 бит и размер ключа 128, 192 или 256 бит, тогда как Rijndael может быть указан с размерами блока и ключа, кратными 32 битам, но не менее 128 бит. биты. Размер блока составляет максимум 256 бит, но размер ключа не имеет теоретического максимума. AES работает с матрицей порядка байтов по столбцам 4 × 4, называемой состоянием (версии Rijndael с большим размером блока имеют дополнительные столбцы в состоянии).

Иглобрюхая рыба

Blowfish — это блочный шифр, разработанный в 1993 году Брюсом Шнайером и включенный в большое количество наборов шифров и продуктов шифрования. Blowfish имеет размер блока 64 бита и переменную длину ключа от 1 до 448 бит. ^[42] Это 16-раундовый шифр Фейстеля , в котором используются большие зависящие от ключа S-блоки . Примечательные особенности конструкции включают зависящие от ключа S-блоки и очень сложную схему клавиш .

Он был разработан как алгоритм общего назначения, задуманный как альтернатива устаревшему DES и свободный от проблем и ограничений, связанных с другими алгоритмами. На момент выпуска Blowfish многие другие разработки были запатентованы, обременены патентами или составляли коммерческую/правительственную тайну. Шнайер заявил, что «Blowfish не имеет патента и останется таковым во всех странах. Алгоритм настоящим размещен в общественном достоянии и может свободно использоваться кем угодно». То же самое относится и к Twofish , алгоритму-преемнику от Schneier.

Обобщения

Настраиваемые блочные шифры

М. Лисков, Р. Ривест и Д. Вагнер описали обобщенную версию блочных шифров, названную «настраиваемыми» блочными шифрами. ^[43] Настраиваемый блочный шифр принимает второй ввод, называемый настройкой, вместе с обычным вводом открытого текста или зашифрованного текста. Твик вместе с ключом выбирает перестановку, вычисленную шифром. Если изменение настроек достаточно легкое (по сравнению с обычно довольно дорогостоящей операцией настройки клавиш), то становятся возможными некоторые интересные новые режимы работы. В статье по теории шифрования диска описаны некоторые из этих режимов.

Шифрование с сохранением формата

Блочные шифры традиционно работают на основе двоичного алфавита . То есть и входные, и выходные данные представляют собой двоичные строки, состоящие из n нулей и единиц. Однако в некоторых ситуациях может потребоваться иметь блочный шифр, работающий с другим алфавитом; например, шифрование 16-значных номеров кредитных карт таким образом, чтобы зашифрованный текст также представлял собой 16-значный номер, может облегчить добавление уровня шифрования в устаревшее программное обеспечение. Это пример шифрования с сохранением формата . В более общем смысле, шифрование с сохранением формата требует перестановки ключей на некотором конечном языке . Это делает схемы шифрования, сохраняющие формат, естественным обобщением (настраиваемых) блочных шифров. Напротив, традиционные схемы шифрования, такие как CBC, не являются перестановками, поскольку один и тот же открытый текст может зашифровать несколько разных зашифрованных текстов, даже при использовании фиксированного ключа.

Связь с другими криптографическими примитивами

Блочные шифры можно использовать для создания других криптографических примитивов, например приведенных ниже. Чтобы эти другие примитивы были криптографически безопасными, необходимо позаботиться о их правильном построении.

• Потоковые шифры могут быть построены с использованием блочных шифров. Режим OFB и режим CTR — это блочные режимы, которые превращают блочный шифр в поточный шифр.
• Криптографические хэш-функции могут быть построены с использованием блочных шифров. ^{[44] [45]} См. функцию одностороннего сжатия для описания нескольких таких методов. Эти методы напоминают режимы работы блочного шифра, обычно используемые для шифрования.
• Криптографически безопасные генераторы псевдослучайных чисел (CSPRNG) могут быть построены с использованием блочных шифров. ^{[46] [47]}
• Безопасные псевдослучайные перестановки конечных множеств произвольного размера могут быть построены с помощью блочных шифров; см. Шифрование с сохранением формата .
• Общеизвестной непредсказуемой перестановки в сочетании с отбеливанием ключа достаточно для создания блочного шифра, такого как одноключевой шифр Эвена-Мансура , возможно, самый простой из возможных доказуемо безопасных блочных шифров. ^[48]
• Коды аутентификации сообщений (MAC) часто создаются на основе блочных шифров. CBC-MAC , OMAC и PMAC являются такими MAC.
• Аутентифицированное шифрование также строится на основе блочных шифров. Это означает одновременное шифрование и MAC. Это необходимо для обеспечения конфиденциальности и аутентификации . CCM , EAX , GCM и OCB являются такими режимами шифрования с аутентификацией.

Точно так же, как блочные шифры могут использоваться для построения хеш-функций, например, SHA-1 и SHA-2 основаны на блочных шифрах, которые также используются независимо как SHACAL , хэш-функции могут использоваться для построения блочных шифров. Примерами таких блочных шифров являются BEAR и LION .

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

• Обзор безопасности шифрования
• Темы криптографии
• XOR-шифр

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

1. Кьюсик, Томас В.; Станица, Пантелимон (2009). Криптографические логические функции и приложения. Академическая пресса. стр. 158–159. ISBN 9780123748904.
2. Менезес, Альфред Дж.; ван Оршот, Пол К.; Ванстон, Скотт А. (1996). «Глава 7: Блочные шифры». Справочник по прикладной криптографии. ЦРК Пресс. ISBN 0-8493-8523-7. Архивировано из оригинала 3 февраля 2021 г. Проверено 15 июля 2012 г.
3. Белларе, Михир; Рогауэй, Филлип (11 мая 2005 г.), Введение в современную криптографию (конспекты лекций) , заархивировано (PDF) из оригинала 09 октября 2022 г., Глава 3.
4. Чакраборти, Д.; Родригес-Энрикес, Ф. (2008). «Режимы работы блочного шифра с точки зрения аппаратной реализации». В Коче, Четин К. (ред.). Криптографическая инженерия . Спрингер. п. 321. ИСБН 9780387718163.
5. Менезес, ван Ооршот и Ванстон 1996, раздел 7.2.
6. Шеннон, Клод (1949). «Теория связи секретных систем» (PDF) . Технический журнал Bell System . 28 (4): 656–715. doi :10.1002/j.1538-7305.1949.tb00928.x. Архивировано из оригинала (PDF) 5 июня 2007 г. Проверено 9 апреля 2012 г.
7. ван Тилборг, Хенк, Калифорния; Яджодиа, Сушил, ред. (2011). Энциклопедия криптографии и безопасности. Спрингер. ISBN 978-1-4419-5905-8., п. 455.
8. ван Тилборг и Джаджодиа 2011, стр. 1268.
9. Рупп, Мартин (16 августа 2019 г.). «Преимущества ключевого блока Atalla». Утимако . Архивировано из оригинала 17 октября 2020 года . Проверено 10 сентября 2019 г.
10. Хамшер, Уолтер (1998). «Электронный бизнес без страха: архитектура безопасности Tristrata» (PDF) . CiteSeerX 10.1.1.123.2371 . Архивировано из оригинала (PDF) 29 мая 2005 года. ^{[ самостоятельно опубликованный источник? ]}
11. Стиеннон, Ричард (17 июня 2014 г.). «Ключевое управление — быстрорастущее пространство». SecurityCurrent . IT-Урожай . Проверено 21 августа 2019 г.
12. Жюно, Паскаль и Канто, Энн (2011). Расширенный линейный криптоанализ блочных и потоковых шифров. ИОС Пресс. п. 2. ISBN 9781607508441.
13. Келихер, Лиам; и другие. (2000). «Моделирование линейных характеристик сетей замены-перестановки». В Хейсе, Ховард; Карлайл, Адам (ред.). Избранные области криптографии: 6-й ежегодный международный семинар, SAC'99, Кингстон, Онтарио, Канада, 9–10 августа 1999 г.: материалы. Спрингер. п. 79. ИСБН 9783540671855.
14. Беньер, Томас; Финиас, Матье (2007). «Наберите «C», чтобы получить шифр». В Бихаме, Эли; Юсефф, Амр (ред.). Отдельные области криптографии: 13-й международный семинар, SAC 2006, Монреаль, Канада, 17–18 августа 2006 г.: пересмотренные избранные статьи . Спрингер. п. 77. ИСБН 9783540744610.
15. Кьюсик, Томас В.; Станица, Пантелимон (2009). Криптографические логические функции и приложения. Академическая пресса. п. 164. ИСБН 9780123748904.
16. Кац, Джонатан; Линделл, Иегуда (2008). Введение в современную криптографию. ЦРК Пресс. п. 166. ИСБН 9781584885511., страницы 166–167.
17. Субхабрата Самадждер (2017). Криптоанализ блочного шифра: обзор . Калькутта: Индийский статистический институт. стр. 5/52.
18. Katz & Lindell 2008, стр. 170–172.
19. Кац и Линделл 2008, с. 171.
20. Омассон, Жан-Филипп; Бернштейн, Дэниел Дж. (2012). «SipHash: быстрый PRF с коротким вводом» (PDF) . В Гэлбрейте, Стивен; Нанди, Мридул (ред.). Прогресс в криптологии — INDOCRYPT 2012: 13-я Международная конференция по криптологии в Индии, Калькутта, Индия, 9–12 декабря 2012 г., материалы . Берлин: Шпрингер. п. 494. дои : 10.1007/978-3-642-34931-7_28. ISBN 978-3-642-34931-7. Архивировано из оригинала (PDF) 12 марта 2020 г.
21. Менезес, ван Ооршот и Ванстон 1996, стр. 228–230, Глава 7.
22. «Режимы блочного шифрования». Ресурсный центр NIST по компьютерной безопасности. 4 января 2017 г.
23. Менезес, ван Ооршот и Ванстон 1996, стр. 228–233.
24. Моррис Дворкин (декабрь 2001 г.), «Рекомендации по режимам работы блочного шифра - методы и методы» (PDF) , специальная публикация 800-38A , Национальный институт стандартов и технологий (NIST), doi : 10.6028/NIST.SP. 800-38А, заархивировано (PDF) из оригинала 9 октября 2022 г.
25. "Kryptographische Verfahren: Empfehlungen und Schlüssellängen", Bsi Tr-02102 (Technische Richtlinie) (Версия 1.0), 20 июня 2008 г.
26. «ISO/IEC 10116:2006 Информационные технологии. Методы обеспечения безопасности. Режимы работы n-битного блочного шифра».
27. Белларе и Рогауэй 2005, с. 101, раздел 5.3.
28. Белларе и Рогауэй, 2005, раздел 5.6.
29. Серж Водене (2002). «Дефекты безопасности, вызванные заполнением CBC — приложения для SSL, IPSEC, WTLS». Достижения в криптологии — EUROCRYPT 2002 . Конспекты лекций по информатике. Том. 2332. Спрингер Верлаг. стр. 534–545. дои : 10.1007/3-540-46035-7_35. ISBN 978-3-540-43553-2.
30. Кеннет Г. Патерсон; Гавен Дж. Уотсон (2008). «Иммунизация режима CBC против атак Oracle с заполнением: формальный подход к обеспечению безопасности». Безопасность и криптография для сетей . Конспекты лекций по информатике. Том. 5229. Спрингер Верлаг. стр. 340–357. дои : 10.1007/978-3-540-85855-3_23. ISBN 978-3-540-85854-6.
31. ISO/IEC 9797-1: Информационные технологии. Методы безопасности. Коды аутентификации сообщений (MAC). Часть 1. Механизмы, использующие блочный шифр, ISO/IEC, 2011.
32. Мартин, Кейт М. (2012). Повседневная криптография: фундаментальные принципы и приложения. Издательство Оксфордского университета. п. 114. ИСБН 9780199695591.
33. Паар, Кристоф; и другие. (2010). Понимание криптографии: Учебник для студентов и практиков. Спрингер. п. 30. ISBN 9783642041006.
34. Мацуи, Мицуру. «Линейный криптоанализ шифра DES». Корпорация Мицубиси Электрик . 1 (3): 43 – через Лабораторию компьютерных и информационных систем.
35. Мацуи, М. и Ямагиши, А. «Новый метод атаки известного открытого текста шифра FEAL». Достижения в криптологии – EUROCRYPT 1992 .
36. Менезес, ван Ооршот и Ванстон 1996, стр. 227.
37. Джеймс Нечватал; Элейн Баркер; Лоуренс Бэшем; Уильям Берр; Моррис Дворкин; Джеймс Фоти; Эдвард Робак (октябрь 2000 г.), Отчет о разработке усовершенствованного стандарта шифрования (AES) (PDF) , Национальный институт стандартов и технологий (NIST), заархивировано (PDF) из оригинала 9 октября 2022 г.
38. Атаки, которые показывают, что шифр не работает так, как заявлено (т. е. уровень сложности его взлома ниже заявленного), которые, тем не менее, имеют достаточно высокую сложность, поэтому практически недостижимы.
39. FIPS PUB 46-3 Стандарт шифрования данных (DES) (это третье издание, 1999 г., но включает историческую информацию в предварительный раздел 12.)
40. Специальная публикация NIST 800-57 «Рекомендации по управлению ключами. Часть 1: Общие сведения (пересмотренные), март 2007 г.». Архивировано 6 июня 2014 г., в Wayback Machine .
41. Бирюков А. и Кушилевиц Э. (1998). Улучшен криптоанализ RC5. ЕВРОКРИПТ 1998.
42. Брюс Шнайер (1994). «Описание нового ключа переменной длины, 64-битного блочного шифра (Blowfish)». Журнал доктора Добба . 19 (4): 38–40.
43. Лисков, М.; Ривест, Р.; Вагнер, Д. «Настраиваемые блочные шифры» (PDF) . Крипто 2002 . Архивировано (PDF) из оригинала 9 октября 2022 г.
44. «ISO/IEC 10118-2:2010 Информационные технологии. Методы обеспечения безопасности. Хэш-функции. Часть 2. Хэш-функции с использованием n-битного блочного шифра».
45. Менезес, ван Ооршот и Ванстон 1996, Глава 9: Хэш-функции и целостность данных.
46. Баркер, Э.Б.; Келси, Дж. М. (2012). «Специальная публикация NIST 800-90A, Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» (PDF) . doi : 10.6028/NIST.SP.800-90A. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
47. Менезес, ван Ооршот и Ванстон 1996, Глава 5: Псевдослучайные биты и последовательности.
48. Орр Данкельман, Натан Келлер и Ади Шамир . «Минимализм в криптографии: новый взгляд на схему Эвена-Мансура».

дальнейшее чтение

• Кнудсен, Ларс Р.; Робшоу, Мэтью (2011). Компаньон по блочным шифрам. Спрингер. ISBN 9783642173417.

Внешние ссылки

• Список многих симметричных алгоритмов, большинство из которых являются блочными шифрами.
• Зал блочного шифрования
• Что такое блочный шифр? из часто задаваемых вопросов по RSA
• Блочный шифр на основе золотых последовательностей и хаотичной логистической палаточной системы