Блочный шифр

Тип шифра

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

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

Определение

Блок-схема шифрблока, показывающая его входы, выходы и компоненты.

Блочный шифр состоит из двух парных алгоритмов , один для шифрования, E , и другой для расшифровки, D . ^[1] Оба алгоритма принимают два входа: входной блок размером n бит и ключ размером k бит; и оба выдают n -битный выходной блок. Алгоритм расшифровки D определяется как обратная функция шифрования, т. е. D = E ⁻¹ . Более формально, ^{[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 Key Block (AKB), который был ключевым нововведением Atalla Box , первого аппаратного модуля безопасности (HSM). Он был разработан в 1972 году Мохамедом М. Аталлой , основателем Atalla Corporation (теперь Utimaco Atalla ), и выпущен в 1973 году. AKB был ключевым блоком, который требовался для безопасного обмена симметричными ключами или PIN-кодами с другими участниками банковской отрасли . Этот безопасный обмен выполняется с использованием формата AKB. ^[9] Atalla Box защищал более 90% всех сетей банкоматов , находящихся в эксплуатации по состоянию на 1998 год, ^[10] и продукты Atalla по-прежнему защищают большинство транзакций банкоматов в мире по состоянию на 2014 год. ^[11]

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

Дизайн

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

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

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

${\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}}$

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

Сети подстановки-перестановки

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

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

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

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

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

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

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

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

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

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

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

Разделить блок открытого текста на две равные части, ( , ) ${\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})}$

Одним из преимуществ модели Фейстеля по сравнению с сетью подстановки-перестановки является то, что раундовая функция не обязательно должна быть обратимой. ^[20] ${\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, своего рода диаграмму потока данных , чтобы проиллюстрировать такую ​​раундовую функцию. ^[21]

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

Другие операции

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

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

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

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

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

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

Прокладка

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

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

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

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

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

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

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

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

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

Интегральный криптоанализ — это криптоаналитическая атака, которая особенно применима к блочным шифрам, основанным на сетях подстановки-перестановки. В отличие от дифференциального криптоанализа, который использует пары выбранных открытых текстов с фиксированной разницей 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). Из этого следует, что если A угадывает случайно, его преимущество будет равно 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 , то ни один злоумышленник не имеет значительной вероятности выиграть новую игру. Это формализует идею о том, что алгоритм более высокого уровня наследует безопасность блочного шифра.

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

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

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

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

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

Люцифер / ДЕС

Lucifer обычно считается первым гражданским блочным шифром, разработанным в IBM в 1970-х годах на основе работы, проделанной Хорстом Фейстелем . Пересмотренная версия алгоритма была принята в качестве федерального стандарта обработки информации правительства США : FIPS PUB 46 Data Encryption Standard (DES). ^[40] Он был выбран Национальным бюро стандартов США (NBS) после публичного приглашения к представлению и некоторых внутренних изменений со стороны NBS (и, возможно, NSA ). 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-битного уровня безопасности. ^[41]

ИДЕЯ

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

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

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

RC5

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

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

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

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

Рейндал / AES

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

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

Рыба-иглу

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

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

Обобщения

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

M. Liskov, R. Rivest и D. Wagner описали обобщенную версию блочных шифров, называемых «настраиваемыми» блочными шифрами. ^[44] Настраиваемый блочный шифр принимает второй вход, называемый твиком, вместе с его обычным открытым текстом или зашифрованным текстом. Твик вместе с ключом выбирает перестановку, вычисленную шифром. Если изменение твиков достаточно легкое (по сравнению с обычно довольно дорогой операцией по установке ключа), то становятся возможными некоторые интересные новые режимы работы. Статья о теории шифрования дисков описывает некоторые из этих режимов.

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

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

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

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

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

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

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

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

Ссылки

1. Cusick, Thomas W.; Stanica, Pantelimon (2009). Криптографические булевы функции и их применение. Academic Press. С. 158–159. ISBN 9780123748904.
2. Менезес, Альфред Дж.; ван Ооршот, Пол К.; Ванстоун, Скотт А. (1996). "Глава 7: Блочные шифры". Справочник по прикладной криптографии. CRC Press. ISBN 0-8493-8523-7. Архивировано из оригинала 2021-02-03 . Получено 2012-07-15 .
3. Белларе, Михир; Рогауэй, Филлип (11 мая 2005 г.), Введение в современную криптографию (конспекты лекций) , заархивировано (PDF) из оригинала 2022-10-09, глава 3.
4. Чакраборти, Д.; Родригес-Энрикес, Ф. (2008). «Режимы работы блочного шифра с точки зрения аппаратной реализации». В Koç, Çetin K. (ред.). Криптографическая инженерия . Springer. стр. 321. ISBN 9780387718163.
5. Менезес, ван Ооршот и Ванстон 1996, раздел 7.2.
6. Шеннон, Клод (1949). "Теория связи в секретных системах" (PDF) . Bell System Technical Journal . 28 (4): 656–715. doi :10.1002/j.1538-7305.1949.tb00928.x. Архивировано из оригинала (PDF) 2007-06-05 . Получено 2012-04-09 .
7. ван Тилборг, Хенк, Калифорния; Яджодиа, Сушил, ред. (2011). Энциклопедия криптографии и безопасности. Спрингер. ISBN 978-1-4419-5905-8., стр. 455.
8. ван Тилборг и Джаджодиа 2011, стр. 1268.
9. Рапп, Мартин (16 августа 2019 г.). «Преимущества блока Atalla Key». Utimaco . Архивировано из оригинала 17 октября 2020 г. Получено 10 сентября 2019 г.
10. Хамшер, Уолтер (1998). "Электронный бизнес без страха: архитектура безопасности Tristrata" (PDF) . CiteSeerX 10.1.1.123.2371 . Архивировано из оригинала (PDF) 29 мая 2005 г. ^{[ самостоятельно опубликованный источник? ]}
11. Стиннон, Ричард (17 июня 2014 г.). «Управление ключами — быстрорастущая сфера». SecurityCurrent . IT-Harvest . Получено 21 августа 2019 г. .
12. Junod, Pascal & Canteaut, Anne (2011). Advanced Linear Cryptanalysis of Block and Stream Ciphers. IOS Press. стр. 2. ISBN 9781607508441.
13. Омассон, Жан-Филипп (6 ноября 2017 г.). Серьёзная криптография: практическое введение в современное шифрование. No Starch Press. стр. 56. ISBN 978-1-59327-826-7. OCLC  1012843116.
14. Келихер, Лиам; и др. (2000). «Моделирование линейных характеристик сетей подстановки–перестановки». В Hays, Howard; Carlisle, Adam (ред.). Избранные области криптографии: 6-й ежегодный международный семинар, SAC'99, Кингстон, Онтарио, Канада, 9–10 августа 1999 г. : труды. Springer. стр. 79. ISBN 9783540671855.
15. Baigneres, Thomas; Finiasz, Matthieu (2007). «Наберите 'C' для шифра». В Biham, Eli; Yousseff, Amr (ред.). Избранные области криптографии: 13-й международный семинар, SAC 2006, Монреаль, Канада, 17–18 августа 2006 г.: пересмотренные избранные статьи . Springer. стр. 77. ISBN 9783540744610.
16. Cusick, Thomas W.; Stanica, Pantelimon (2009). Криптографические булевы функции и их применение. Academic Press. стр. 164. ISBN 9780123748904.
17. Кац, Джонатан; Линделл, Йехуда (2008). Введение в современную криптографию. CRC Press. стр. 166. ISBN 9781584885511., страницы 166–167.
18. Субхабрата Самадждер (2017). Криптоанализ блочного шифра: обзор . Калькутта: Индийский статистический институт. С. 5/52.
19. Katz & Lindell 2008, стр. 170–172.
20. Кац и Линделл 2008, стр. 171.
21. Aumasson, Jean-Philippe; Bernstein, Daniel J. (2012). "SipHash: быстрый PRF с коротким входом" (PDF) . В Galbraith, Steven; Nandi, Mridul (ред.). Progress in cryptology-- INDOCRYPT 2012: 13-я Международная конференция по криптологии в Индии, Калькутта, Индия, 9-12 декабря 2012 г., труды . Berlin: Springer. стр. 494. doi :10.1007/978-3-642-34931-7_28. ISBN 978-3-642-34931-7. Архивировано из оригинала (PDF) 2020-03-12.
22. Менезес, ван Ооршот и Ванстон 1996, стр. 228–230, Глава 7.
23. "Режимы блочного шифрования". Центр ресурсов компьютерной безопасности NIST . 4 января 2017 г.
24. Менезес, ван Ооршот и Ванстон 1996, стр. 228–233.
25. Morris Dworkin (декабрь 2001 г.), «Рекомендации по режимам работы блочных шифров – методы и приемы» (PDF) , специальная публикация 800-38A , Национальный институт стандартов и технологий (NIST), doi :10.6028/NIST.SP.800-38A, архивировано (PDF) из оригинала 2022-10-09
26. "Kryptographische Verfahren: Empfehlungen und Schlüssellängen", Bsi Tr-02102 (Technische Richtlinie) (Версия 1.0), 20 июня 2008 г.
27. "ISO/IEC 10116:2006 Информационные технологии. Методы безопасности. Режимы работы n-битного блочного шифра".
28. Белларе и Рогауэй 2005, с. 101, раздел 5.3.
29. Беллар и Рогауэй 2005, раздел 5.6.
30. Serge Vaudenay (2002). "Security Flaws Induced by CBC Padding — Applications to SSL, IPSEC, WTLS". Advances in Cryptology — EUROCRYPT 2002. Lecture Notes in Computer Science. Vol. 2332. Springer Verlag. pp. 534–545. doi :10.1007/3-540-46035-7_35. ISBN 978-3-540-43553-2.
31. Kenneth G. Paterson; Gaven J. Watson (2008). "Immunizing CBC Mode Against Padding Oracle Attacks: A Formal Security Treatment". Безопасность и криптография для сетей . Конспект лекций по информатике. Том 5229. Springer Verlag. С. 340–357. doi :10.1007/978-3-540-85855-3_23. ISBN 978-3-540-85854-6.
32. ISO/IEC 9797-1: Информационные технологии — Методы безопасности — Коды аутентификации сообщений (MAC) — Часть 1: Механизмы, использующие блочный шифр, ISO/IEC, 2011
33. Мартин, Кит М. (2012). Повседневная криптография: основные принципы и приложения. Oxford University Press. стр. 114. ISBN 9780199695591.
34. Paar, Christof; et al. (2010). Понимание криптографии: учебник для студентов и практиков. Springer. стр. 30. ISBN 9783642041006.
35. Мацуи, Мицуру. «Линейный криптоанализ шифра DES». Mitsubishi Electric Corporation . 1 (3): 43 – через Computer & Information Systems Laboratory.
36. Мацуи, М. и Ямагиши, А. «Новый метод атаки на известный открытый текст шифра FEAL». Достижения в криптологии – EUROCRYPT 1992 .
37. Менезес, ван Ооршот и Ванстон 1996, стр. 227.
38. Джеймс Нечватал; Элейн Баркер; Лоуренс Басшем; Уильям Берр; Моррис Дворкин; Джеймс Фоти; Эдвард Робак (октябрь 2000 г.), Отчет о разработке усовершенствованного стандарта шифрования (AES) (PDF) , Национальный институт стандартов и технологий (NIST), архив (PDF) из оригинала 2022-10-09
39. Атаки, которые показывают, что шифр не работает так, как заявлено (т. е. уровень сложности его взлома ниже заявленного), но которые, тем не менее, достаточно сложны, поэтому они практически неосуществимы.
40. FIPS PUB 46-3 Стандарт шифрования данных (DES) (Это третье издание, 1999 г., но включает историческую информацию в предварительном разделе 12.)
41. Специальная публикация NIST 800-57 Рекомендации по управлению ключами — Часть 1: Общие положения (пересмотренная), март 2007 г. Архивировано 6 июня 2014 г. на Wayback Machine .
42. Бирюков А. и Кушилевиц Э. (1998). Улучшенный криптоанализ RC5. EUROCRYPT 1998.
43. Брюс Шнайер (1994). «Описание нового ключа переменной длины, 64-битного блочного шифра (Blowfish)». Журнал доктора Добба . 19 (4): 38–40.
44. Лисков, М.; Ривест, Р.; Вагнер, Д. «Настраиваемые блочные шифры» (PDF) . Crypto 2002. Архивировано (PDF) из оригинала 2022-10-09.
45. "ISO/IEC 10118-2:2010 Информационные технологии — Методы безопасности — Хэш-функции — Часть 2: Хэш-функции, использующие n-битный блочный шифр".
46. Менезес, ван Ооршот и Ванстон, 1996, Глава 9: Хэш-функции и целостность данных.
47. Баркер, Э. Б.; Келси, Дж. М. (2012). «Специальная публикация NIST 800-90A Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» (PDF) . doi :10.6028/NIST.SP.800-90A. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
48. Менезес, ван Ооршот и Ванстон 1996, Глава 5: Псевдослучайные биты и последовательности.
49. Орр Данкельман , Натан Келлер и Ади Шамир . «Минимализм в криптографии: пересмотр схемы Эвена–Мансура».

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

• Кнудсен, Ларс Р.; Робшоу, Мэтью (2011). The Block Cipher Companion. Springer. ISBN 9783642173417.

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

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