Основы Защиты информации

Введение

Одним из эффективных методов криптографической защиты информации на сегодняшний день является использование симметричных блоковых шифров. Симметричные шифры – это класс криптографических алгоритмов, использующих наборы идентичных примитивных операций и один и тот же ключ, как для зашифровывания, так и для расшифровывания. Существует два вида симметричных шифров: потоковые и блоковые. Процесс шифрования одного элемента открытого текста (символа или одного бита), который фактически сводится к процессу гаммирования, выполняют поточные симметричные шифры, причем в основном каждый элемент открытого текста зашифровывается независимо друг от друга. В симметричных блоковых шифрах, в отличие от поточных, обработке подлежат группы элементов открытого текста (блоки данных). Во время такого шифрования каждый блок данных, который обрабатывается, во-первых, подвергается преобразованию несколько раундов, что, в свою очередь, вызывает лавинный эффект. Во-вторых, каждый элемент блока данных зависит от всех элементов этого же блока. Симметричные шифры применяют для хранения конфиденциальных данных на физических носителях и шифрования информации при ее передаче через компьютерные сети. Однако, если непосредственно использовать любой симметричный блоковый шифр без применения дополнительных криптографических преобразований, то такой процесс шифрования будет иметь ряд недостатков. В частности, в таких случаях невозможно скрыть структуру информации, которая защищается за счет того, что во время шифрования используются блоки фиксированного размера и один и тот же секретный ключ. Поэтому, с целью устранения отрицательных свойств процесса шифрования и в зависимости от отрасли применяют ряд базовых режимов блокового шифрования, которые стандартизированы Национальным институтом стандартизации и технологий (National Institute of Standards and Technology):
− Electronic Codebook (ECB) – режим электронной кодовой книги;
− Cipher Block Chaining (CBC) – режим сцепления блоков зашифрованного текста;
− Cipher Feedback (CFB) – режим обратной связи по зашифрованному тексту;
− Output Feedback (OFB) – режим обратной связи по выходу;
− Counter Mode (CTR) – режим счетчика.
Кроме вышеупомянутых режимов разработан ряд новых режимов шифрования, которые могут быть использованы при защите информации, в частности режим CTR приняли как дополнение к стандарту «NIST Special Publication 800-38A 2001 Edition – Recommendation for Block Cipher Modes of Operation. Methods and Techniques» .


Принципы построения блоковых шифров

Современный блочный шифр – это шифр с симметричным ключом, разбивающий перед шифрованием открытый текст на n -битовые блоки и далее шифрующий сообщение блоками [11], т.е.

y=Ekx и x=Dk(y)

где x , y – блоки открытого и шифрованного текстов; k – секретный ключ шифра; E , D – функции шифрования и дешифрования (другими словами, блоковый алгоритм – это алгоритм простой замены блоков текста фиксированной длины).
Алгоритмы дешифрования и шифрования – инверсные, оба работают на одном и том же секретном ключе.

Рис. 1 Общая идея шифрования и дешифрования с помощью блокового шифра

Если сообщение содержит менее n битов, то его дополняют дополнительными данными (чаще нулями) до n - битового размера; если текст имеет больше, чем n бит, то его делят на n -битовые блоки. Чаще всего блочные шифры обрабатывают блоки длиной n 64, 128, 256, 512 бит. Пример. Сколько дополнительных бит надо добавить к сообщению длиной 100 символов, если кодирование одного символа требует 8 бит и блочный шифр работает с блоками длиной 64 бита?
Р е ш е н и е. Закодированное сообщение из 100 символов содержит 800 бит. Исходный текст должен делиться без остатка на 64. Обозначим L и l – длина сообщения и длина дополнения L l 0(mod 64) l 800(mod64) 32(mod64).
Следовательно, в конце открытого текста надо добавить 32 дополнительных бита. Общая длина 832 бита или 13 блоков по 64 бита. Алгоритм шифрования будет работать 13 раз, чтобы создать 13 блоков шифрованного текста. Блочный шифр можно спроектировать так, чтобы он действовал и как шифр подстановки, и как шифр перестановки: 1) если шифр спроектирован как шифр подстановки, каждый бит открытого текста может быть заменен на 0 или 1 исходный текст и шифротекст могут иметь различное число единиц. 2) если шифр спроектирован как шифр перестановки, то биты открытого текста только меняются местами. В любом случае, число возможных n -битовых открытых текстов равно числу шифротекстов и равно 2 n (так как каждый из n битов блока может быть равен 0 или 1).
Современные блоковые шифры спроектированы как шифры подстановки, потому что использование только перестановки (сохранение числа единиц или нулей) делает шифр уязвимым к методу полного перебора (из-за сохранения числа единиц или нулей).
По виду повторяющегося преобразования, используемого в раундах, блоковые алгоритмы шифрования делят на несколько категорий:
1. Сеть Фейстеля [4,5], использующая многократно повторяющуюся структуру, называемую ячейкой Фейстеля. Допускается использование необратимых операторов. При переходе от одной ячейки к другой меняется раундовый ключ. Операции зашифрования/расшифрования при определённой доработке совпадают, требуя только использования ключей в обратном порядке. Шифрование при помощи данной конструкции легко реализуется как на программном уровне, так и на аппаратном, что обеспечивает широкие возможности применения (например, DES, ГОСТ 28147-89, RC5, BLOWFISH, TEA, CAST-128 и т.д.).
2. Подстановочно-перестановочная сеть [8] (SP-сеть - Substitution-permutation network). В отличие от сети Фейстеля, SP-сети обрабатывают за один раунд целиком шифруемый блок. Обработка данных сводится, в основном, к заменам и перестановкам, зависящим от ключа. Упрощенная схема показана на рисунке. Впрочем, такие операции характерны и для других видов алгоритмов шифрования, поэтому, на мой взгляд, название "подстановочно-перестановочная сеть" является достаточно условным. SP-сети распространены существенно реже, чем сети Фейстеля; в качестве примера SP-сетей можно привести алгоритмы SERPENT или SAFER+ .


Рис. 2 Подстановочно-перестановочная сеть

Шифры со структурой квадрат основанные только на обратимых операторах. Пример – шифр AES. Для структуры "квадрат" характерно представление шифруемого блока данных в виде двумерного байтового массива. Криптографические преобразования могут выполняться над отдельными байтами массива, а также над его строками или столбцами. Структура алгоритма получила свое название от алгоритма Square, который был разработан в 1996 году Винсентом Риджменом (Vincent Rijmen) и Джоан Деймен (Joan Daemen) – будущими авторами алгоритма Rijndael, также имеющего Square-подобную структуру и ставшего новым стандартом шифрования США AES после победы на открытом конкурсе. Другой пример – алгоритм SHARK (более ранняя разработка Риджмена и Деймен) и CRYPTON, разработанный южнокорейским криптологом Че Хун Лим из Южной Кореи в 1998 г.
Строгие границы между описанными выше структурами не определены, поэтому достаточно часто встречаются алгоритмы, причисляемые различными экспертами к разным типам структур. Например, алгоритм CAST-256 относится его автором к SP-сети, а многими экспертами называется расширенной сетью Фейстеля.
Шифр (сеть) Фейстеля базируется на необратимых операторах и использует один и тот же модуль при расшифровании и зашифровании. Возникает вопрос: если алгоритмы шифрования и расшифрования содержат необратимые операторы, то как зашифрованный текст инвертировать в открытый? Фейстель показал, что действие необратимого оператора в алгоритме шифрования можно нейтрализовать в алгоритме расшифрования с помощью операции XOR.

Рис. 3 Шифрование и дешифрование

Покажем это. Пусть при зашифровании ключ поступает на вход необратимой функции f(k), значения которой далее складываются по модулю 2 (операция XOR) с исходным текстом. В результате этих действий появлется шифротекст. Пусть открытому тексту x1 отвечает шифрованный текст y1 , и при любом изменении в ходе зашифрования возникает шифрованный текст y2 , который при расшифровании дает открытый текст x2. Надо показать, что из равенства y2=y1, следует равенство x1=x2. Зашифрование: y1=x1 f(k) .
Расшифрование:

Следовательно, хотя в шифре использована необратимая функция, алгоритмы зашифрования и расшифрования могут быть инверсными.
Свойства сети Фейстеля:
Сеть Фейстеля можно сконструировать так, что для зашифрования и расшифрования будет использоваться один и тот же алгоритм – отличие между этими операциями будет состоять лишь в порядке применения раундовых ключей; такое свойство алгоритма наиболее полезно при его аппаратной реализации или на платформах с ограниченными ресурсами.
В одном раунде меняется только половина битов блока для стойкости шифра надо увеличивать число раундов

.
Замечание: Подстановочно-перестановочные сети используют лишь обратимые операторы: S-боксы должны иметь равное число входов и выходов, чтобы быть совместимыми. Не позволяется сжатие или расширение P-боксов, нет необходимости делить исходный текст на две половины. Для получения криптопреобразования, обладающего хорошими криптографическими свойствами, функция усложнения f , используемая в раунде, реализуется в виде композиции элементарных преобразований, называемых слоями функции усложнения (функцию f называют еще раундовой, цикловой). Конструктивные слои функции усложнения имеют следующие назначения: подмешивание раундовых ключей; перемешивание входных блоков; реализацию сложной нелинейной зависимости между знаками ключа, входного и выходного блоков. Раундовая функция должна удовлетворять ряду условий: - цикловая функция должна быть обратимой (однако помнить, что в схеме Фейстеля функция усложнения в принципе может не удовлетворять этому требованию, так как обратимость преобразования обеспечивается за счет использования операции XOR); - раундовая функция должна быть нелинейной; - перемешивающие слои раундовой функции должны реализовывать связи между входными и выходными битами S-боксов таким образом, чтобы каждый S-бокс удовлетворял критериям лавинного эффекта, а совокупность входных битов каждого S-бокса зависела от выходов нескольких S-боксов предыдущего раунда; - раундовая функция должна обладать свойствами, затрудняющими применение методов дифференциального и линейного криптоанализа, т.е. раундовая функция должна иметь минимальную корреляцию между разностью открытых текстов и соответствующих криптограмм.


Основные виды блоковых шифров

Первым и самым простым режимом блокового шифрования является режим электронной кодовой книги [1]. При использовании данного режима открытый текст разбивают на n-битные блоки, и каждый блок зашифровывают независимо от других. Процесс зашифровывания и расшифровывания описывают следующими формулами:

где E, D – соответственно функции зашифровывания и расшифровывания; Pi, Сi – i-ый n-битный блок открытого и зашифрованного текста соответственно, i=1, 2, 3, ...; K – n-битный секретный ключ шифрования.
Основными преимуществами режима ECB является возможность одновременно шифровать несколько блоков данных и поддержка самосинхронизации, т. е. повреждения i-го блока зашифрованного текста влияет только на тот же самый расшифрованный блок.
Однако такой процесс шифрования имеет ряд недостатков:
− одинаковые блоки открытого текста обуславливают появление одинаковых блоков зашифрованного текста;
− перестановка блоков зашифрованного текста вызывает перестановку
соответствующих блоков открытых текстов, что приводит к нарушению целостности информации;
− невозможно скрыть структуры информации, подлежащей защите.
Часть базовых режимов блокового шифрования, в частности режим ECB, уязвимы к атаке на основе пар известных текстов и зашифрованных текстов, и к атаке «дня рождения». Кроме того, известным фактом является то, что когда большой объем информации зашифровывают с использованием одного и того же секретного ключа, то в блоках зашифрованного текста присутствует информация об открытом тексте. В работе [3] приводится такой факт.
Если блоки открытого текста принимают случайную форму, которая удовлетворяет закон равномерного распределения, и зашифрованные на одном и том же секретном ключе, то в зашифрованном тексте присутствует утечка информации об открытом тексте с вероятностью

где s = 2(n+2)2, ps ≈ 0,63.
Согласно парадоксу «дня рождения», для режима ECB, для s n-битных блоков зашифрованных текстов C1, …, Cs существует такая пара, Ci = Cj с вероятностью ps. Таким образом, первый из недостатков режима ECB становится весомой помехой для использования данного режима, поскольку злоумышленник сразу может узнать, что Pi = Pj.
В режиме сцепления блоков зашифрованного текста [1], i-ый блок открытого текста и (i-1)-ый блок зашифрованного текста сцепляют с помощью операции сложения по модулю два перед выполнением процесса зашифровывания, который выполняется следующим образом:


где ⊕ – операция сложения по модулю два; IV – вектор инициализации.
Преимуществами режима CBC является отсутствие недостатков, присущих ECB, а именно, поддержки процесса сокрытия структуры открытого текста и отсутствие возможности перестановки блоков зашифрованного текста, которые достигаются за счет того, что каждый следующий блок зашифрованного текста зависит от всех предыдущих блоков. Однако, это в свою очередь не позволяет одновременно зашифровывать несколько блоков открытого текста.
Кроме вышеуказанных преимуществ, следует отметить, что данный режим позволяет распараллелить процесс расшифровки блоков зашифрованного текста и поддерживает самосинхронизацию. Если во время передачи или записи данных был поврежден i-ый блок зашифрованного текста, то только i-ый и (i+1)-ый блоки открытого текста будут повреждены при расшифровывании.
Одинаковые блоки открытого текста обуславливают появление разных блоков зашифрованного текста, это в свою очередь делает невозможным использование процесса перестановки блоков зашифрованного текста для модификации содержания открытого текста в отличие от режима ECB. За счет этого режим шифрования CBC также используют в качестве средства для обеспечения целостности и защиты информации от фальсификации.
Однако для режима CBC как и для режима ECB, также существует s n-битных блоков зашифрованных текстов C1, ..., Ct таких, что Ci = Cj с вероятностью ps [3]. То есть Pi ⨁ Ci-1 = Pj ⨁ Cj-1 → Pi ⨁ Pj = Ci-1 ⊕ Cj-1. В случае, если у атакующего есть доступ к нескольким наборам зашифрованных текстов C1, …, Ct, где каждый набор Cl состоит из sl блоков зашифрованного текста, то общий объем выборки, с которой работает злоумышленник, равен:

Таким образом, используя парадокс «дня рождения» злоумышленник может заменить пару блоков зашифрованных текстов (Ci-1, Ci) на (Cj-1, Cj) даже несмотря на то, что блоки открытых текстов Pi-1 и Pj-1 не будут достоверными, чтобы получить во время расшифровки все остальные блоки открытых текстов, которые будут эквивалентны оригинальным блокам.
Более того, злоумышленник, обладая несколькими наборами зашифрованных текстов, может подменить целые группы блоков зашифрованных текстов (Ci-1, …, Ci-w) на (Cj-1, …, Cj-w), если Ci = Cj и Ci-w = Cj-w.
Также, как указано в работах [7, 9], атаковать базовую функцию шифрования в режиме CBC можно с использованием атаки на основе пар известного открытого текста. То есть входное значение, которое подают на функцию шифрования, рассчитывают с помощью добавления по модулю два текущего блока открытого текста и предыдущего блока зашифрованного текста, а выход функции шифрования – это текущий блок зашифрованного текста.
В режиме обратной связи по зашифрованному тексту блоки открытого текста добавляют по модулю два с блоками гаммы. Первый блок гаммы формируют с использованием n-битного начального вектора (1 ≤ n ≤ b), который записывают в младшие n-бит b-битного входного блока I1, который вместе с секретным ключом K подают на функцию шифрования.
В качестве гаммы выступают n-старших битов исходного блока данных из функции шифрования, которую добавляют по модулю два с блоком открытого текста, в результате чего получают блок зашифрованного текста. Входной j-ый блок Ij является результатом конкатенации (b-n)-младших бит предыдущего входного блока Ij-1, который записывается в старшие (b-n)-биты b-битного входного блока Ij и n-бит блока зашифрованного текста Cj-1,
которые записывают в младшие n-бит b-битного входного блока Ij и т. д.
Процесс зашифровывания блоков открытого текста и расшифровывания блоков зашифрованного текста выполняют таким образом:

где Ij – b-битный входной блок; Oj – b-битный выходной блок; >>, << – операции правостороннего и левостороннего сдвига соответственно.
К положительным свойствам режима CFB относят возможность скрывать структуру открытого текста и поддержку самосинхронизации, т. е. если будет потерян 1 бит любого блока зашифрованного текста, то при расшифровке будет повреждено еще дополнительно b/n блоков открытого текста. Как и в режиме CBC процесс расшифровки может быть распараллелен, а процесс зашифровывания – нет, поскольку каждый следующий блок зашифрованного текста зависит от всех предыдущих блоков.
Режим обратной связи по выходу является конфиденциальным режимом, в котором из начального вектора IV генерируют последовательность n-битных выходных блоков Oj, которые суммируют по модулю два с блоками открытых текстов Pj, чтобы получить блоки зашифрованных текстов и наоборот.
Процесс зашифровывания и расшифровывания, согласно [1], выполняют следующим образом:

где Ij – n-битный входной блок; PN*,CN*– последние u-битные блоки открытого и зашифрованного текстов соответственно.
Если последний блок открытого текста PN* состоит из u-бит, то данный блок открытого текста добавляют по модулю два с u наиболее значимыми битами последнего выходного блока