Автор: Андрей Винокуров

7. Недостатки режима простой замены.

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

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

Можно предложить модификацию схемы шифрования по алгоритму простой замены, устраняющую данный недостаток – для этого перед зашифрованием сообщения надо выполнить его рандомизацию. Это действие заключается в том, что блоки исходного текста модифицируются индивидуальным образом, например, комбинируют¬ся с данными, вырабатываемыми датчиком псевдослучайных чисел (ПСЧ) с помощью некоторой бинарной операции °, имеющей обратную операцию •. Зашифрование и расшифрование будет выполняться согласно следующим уравнениям:

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

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

• можно дополнить “хвост” фиксированными данными – например, нулями. Это, однако, существенно снизит криптостойкость последнего блока, так как криптоаналитику, обладающему информацией о способе дополнения “хвоста”, потребуется выполнить перебор по множеству возможных значений этого блока, гораздо меньшему, чем полное пространство значений блока.
• можно дополнять “хвосты” данными из полных блоков. В целом это неплохое решение, но оно не работает, если неполный блок – единственный, то есть если длина сообщения меньше размера блока шифра. Кроме того, используя данный подход, мы рано или поздно столкнемся с ситуацией, когда для дополнения “хвоста” будут использованы фиксированные части сообщения, обладающие недостаточной неопределенностью для криптоаналитика. Так, например, многие сообщения начинаются с грифа, который может принимать всего два – три возможных значения, а различных форм его записи в текстовом виде может быть максимум несколько десятков вариантов. Если для дополнения “хвоста” используется часть такого блока, то складывается ситуация, подобная рассмотренной в предыдущем пункте – “хвост” может стать легкой добычей криптоаналитика.
• применение для дополнения “хвоста” отдельного постоянного секретного элемента не подходит по той же самой причине, что и первый способ – использование данного элемента по частям делает его уязвимым к криптоанализу. Такая схема оказывается беззащитной перед анализом на основе выбранного открытого текста. Кроме того, данный способ увеличивает общий объем секретной (ключевой) информации, что весьма нежелательно.
• пожалуй, наилучший возможный способ заключается в том, чтобы использовать для дополнения “хвоста” данные с аппаратного датчика случайных чисел. Здесь нужен датчик, вырабатывающий действительно случайные числа, имеющие высокое статистическое качество. По этой причине различные программные датчики ПСЧ здесь не подходят. В силу этого часто такой способ оказывается неприемлемым по экономическим соображениям, так как требует наличия на каждом компьютере-шифрователе весьма дорогостоящей аппаратной компоненты.

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

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

В силу изложенных выше соображений использование блочного шифра в режиме простой замены может быть рекомендовано только для шифрования небольших по объему массивов данных, размер которых кратен размеру блока используемого блочного криптоалгоритма и которые не содержат повторяющихся блоков. Этому набору требований вполне удовлетворяют лишь массивы ключевой информации. Именно поэтому DES не рекомендует, а Российский стандарт ГОСТ 28147-89 прямо запрещает использовать шифрование в режиме простой замены для данных, не являющихся ключевыми.

8. Гаммирование.

Предложенная в предыдущем разделе процедура шифрования по методу простой замены с использования датчика псевдослучайных чисел может быть слегка изменена, что освободит ее от ряда недостатков. Зашифрованию по алгоритму простой замены следует подвергать сами блоки, вырабатываемые датчиком ПСЧ, и уже их использовать в качестве гаммы, комбинируемой с блоками данных с помощью бинарных операций ° и •:

Смысл первого требования становится очевидным исходя из того, что метод гаммирования по своей сути требует одноразовой гаммы, иначе он легко вскрывается по алгоритмической линии. Если же период повторения вырабатываемой гаммы недостаточно велик, различные части одного и того же длинного сообщения могут оказаться зашифрованными с помощью одинаковых участков гаммы. Это на много порядков снижает стойкость шифра, делая его легкой добычей криптоаналитика. Второе требование является менее очевидным, и, вообще говоря, имеет место только для шифров вполне определенных архитектур, в которых шаг шифрования является комбинацией нескольких сравнительно простых преобразований, в ходе каждого из которых различия в шифруемых блоках данных увеличиваются весьма незначительно. Поэтому, если мы подвергнем шифрованию два блока, отличающиеся только в единственном двоичном разряде, серьезные различия между ними появятся только через несколько таких простых шагов, что несколько снижает стойкость шифра и облегчает задачу криптоаналитика. Конечно, в случае ГОСТа это снижение не так велико, но разработчики алгоритма решили подстраховаться. Датчик ПСЧ, входящий в Российский стандарт на шифрование, предполагает независимую обработку старшей и младшей половин вырабатываемого блока

Команды даны в мнемонике фирмы Intel для производимого ею процессора iAPX386, G0,G1 – 32-х битовые элементы данных – регистры или двойные слова в памяти, соответственно младшая и старшая половины 64-битового блока данных, из которого после зашифрования по алгоритму простой замены получается блок гаммы.

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

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

Во-первых, одинаковые блоки исходного текста после зашифрования дадут различные блоки шифротекста, что не облегчает задачу криптоанализа на основе только шифротекста.

Во-вторых, как и во всех поточных шифрах, отсутствует проблема неполного блока данных. Действительно, при зашифровании последнего в сообщении блока данных Tn неполного размера | Tn | < N из выработанного для этого блока гаммы мы можем взять фрагмент такого же размера. Этот подход очевиден, если операция наложения гаммы является побитовой, но может быть применен и в иных случаях. Важно, что при этом мы получим блок шифротекста того же размера, что и блок исходных данных. Таким образом, зашифрование по методу гаммирования не изменяет размер шифруемых данных, что в ряде случаев бывает важным.

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

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

Указанное свойство гаммирования довольно неприятно, так как по своей сути означает, что злоумышленник, воздействуя только на шифротекст, может по своему усмотрению менять любые разряды в соответствующем открытом тексте. Насколько это может быть опасно, поясним на следующем примере: пусть почтальон – злоумышленник передает шифрованное сообщение, которое он не может расшифровать, однако может внести в него произвольные изменения. Таким почтальоном может быть, например, работник филиала фирмы, обслуживающий коммуникационную ЭМВ, предназначенную для передачи сообщений в головное отделение фирмы. Пусть он передает некий документ, составленный в виде текстового файла, зашифрованного в режиме гаммирования, в котором, как он знает, с 13 позиции начинается запись некоторого числа, например, суммы его премиального вознаграждения. Вполне может оказаться, что ему известна вся сумма или, хотя бы ее некоторая часть – предположим, что запись числа начинается с символа ‘1’, и злоумышленник это знает. Тогда для него не с

оставит труда переправить эту цифру на другую, например – на ‘9’. Все что для этого требуется – это заменить 13-й байт сообщения B13 на новое значение, вычисляемое следующим образом: B'13 = B13 [] '1' [] '9'. Через '1' и '9' мы обозначили коды цифр 1 и 9 соответственно в той системе кодировки, в которой подготовлен текст сообщения. Если это ASCII, то достаточно инвертировать всего один бит сообщения: B'13 = B13 [] 8. После расшифрования получатель получит сообщение, в котором вместо верной цифры 1 стоит цифра 9, и больше никаких изменений нет! Очевидно, что данная подмена не может быть обнаружена, если в передаваемом массиве данных нет никакой дополнительной информации, кроме зашифрованного исходного сообщения. Приведенный пример еще раз иллюстрирует тот факт, что обеспечение секретности сообщения (его шифрование) само по себе не обеспечивает его аутентичности, то есть подлинности. В чем же причина такой особенности гаммирования? Дело в том, что этот режим не обеспечивает весьма желательного для всех шиф ров перемешивания битов сообщения, то есть влияния одного бита исходного текста на несколько битов шифротекста.

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

9. Гаммирование с обратной связью.

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

Из этих уравнений становится ясно, что каждый блок шифротекста при расшифровании оказывает влияние лишь на два блока открытого текста: на соответствующий ему блок, и на следующий за ним блок. Причем в первом случае это влияние носит такой же характер, как и при использовании обычного гаммирования, а во втором – как при простой замене. Таким образом, если злоумышленник внесет изменения в блок шифротекста, они отразятся на текущем и следующем блоках сообщения.

Проявление этого влияния удобно пояснить на примере из предыдущего раздела: если сообщение было зашифровано по методу гаммирования с обратной связью и в него были внесены указанные в примере изменения, то после расшифрования получатель увидит следующую картину:

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

Таким образом, режим гаммирования с обратной связью имеет те же преимущества, что и обычное гаммирование, и вместе с тем свободен от его недостатков. Гаммирование с ОС устойчиво к перестановкам блоков и к направленным модификациям шифротекста, если только модифицируется не последний блок. Иными словами, злоумышленник, вносящий изменения в шифротекст, не может точно рассчитать их влияние на открытый текст, если, конечно, не обладает секретным ключом. С другой стороны, для этого режима как для частного случая гаммирования, отсутствует проблема “хвоста” – последнего неполного блока данных и в отличие от гаммирования без ОС не так остра проблема уникальности синхропосылки. Поясним последнее замечание: действительно, при обычном гаммировании вырабатываемая гамма однозначно определяется синхропосылкой и ключом:

10. Имитозащита.

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

Имитозащита есть защита системы шифрованной связи или иной криптосистемы от навязывания ложных данных.

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

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

Для вычисления такой контрольной комбинации может быть использована так называемая вычислительно необратимая функция. Функция Y = f(T ) называется вычислительно необратимой, если определение таких значений T, для которых справедливо уравнение f(T ) = Y, то есть вычисление обратной функции T = f–1(Y ) вычислительно невозможно. На практике это означает, что такое значение T не может быть определено более эффективным способом, чем перебором по множеству всех его возможных значений. Размер имитовставки Y |Y | = N должен исключать сколько-нибудь значимую вероятность успешной подделки сообщения, которая в наихудшем для аналитика случае равна p = 2–N.

Ясно, что понятие вычислительной необратимости чрезвычайно трудно формализуемо и поэтому его выполнение практически невозможно проверить для конкретных алгоритмов. Схема имитозащиты, основанная на необратимой функции, устойчива по отношению к первой угрозе. Действительно, чтобы ее реализовать, злоумышленник должен подобрать сообщение T под заданную контрольную комбинацию Y, для чего ему необходимо решить уравнение f(T ) = Y относительно T, что по нашему предположению невозможно за приемлемое время. Однако данная схема имитозащиты не защищает от второй угрозы. Чтобы сделать ее устойчивой к ней, можно передавать имитовставку вместе с сообщением зашифрованной на том же самом или другом ключе. Контрольная комбинация, вычисленная таким образом, в зарубежной литературе называется кодом обнаружения манипуляций с данными (Manipulation Detection Code), и сокращенно обозначается MDC. Для реализации данного метода необходима вычислительно необратимая функция сжатия данных. Слово “сжатие” присутствует в названи

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

Чтобы злоумышленник не смог реализовать ни одну из перечисленных выше доступных ему угроз по нарушению целостности данных, достаточно обеспечить невозможность вычисления им контрольной комбинации f(T ) для любого текста T. Для этого просто надо сделать алгоритм ее вычисления f(T ) секретным элементом криптосистемы. Последовательное проведение в жизнь принципа Кирхгофа приводит к схеме, в которой функция f сама по себе не секретна, но зависит от вектора секретных параметров – ключа K:

I = f(K ,T ) = f(K,T1,...,Tn), где

T = (T1,...,Tn) – исходный текст, разбитый на блоки фиксированного размера. Выработанная таким способом контрольная комбинация получила название кода аутентификации сообщений (Message Autentification Code) и сокращенно обозначается MAC. В отечественной литературе она иногда (не вполне корректно) именуется криптографической контрольной суммой. Как нам реализовать эту функцию f(K ,T )? В нашем распоряжении имеется алгоритм криптографического преобразования I = EK(T ) (простой замены) ,который обладает необходимыми для построения подобных функций свойствами, однако позволяет работать только с блоками текста фиксированного размера | T | = N.

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

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

f(T) = (E_K(T₁) + E_K(T₂) +...+ E_K(T_n)) mod 2^N.

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

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

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

• использовать для вычисления имитовставки различные криптоалгоритмы, или различные режимы одного и того же алгоритма;
• использовать для шифрования и вычисления имитовставки различные ключи;

Заключение.

На этом автор вынужден поставить точку, хотя без рассмотрения осталось большое число важных вопросов, в частности, совсем не были затронуты вопросы реализации Российского стандарта в виде аппарата или программы для ЭВМ, представляющие в последнее время наибольший интерес для широкого круга специалистов. Тем не менее автор надеется, что данная статья будет полезна всем интересующимся криптографическими методами защиты информации. В качестве дополнения к статье прилагается набор уравнений для всех режимов криптопреобразований по ГОСТ 28147-89, являющийся по сути формальным и достаточно полным описанием стандарта.

Литература.

• Дж. Л. Месси. Введение в современную криптологию. ТИИЭР, т.76, №5, Май 88, М, Мир, 1988, с.24–42.
• М. Э. Смид, Д. К. Бранстед. Стандарт шифрования данных: прошлое и будущее. ТИИЭР, т.76, №5, Май 88, М, Мир, 1988, с.43–54.
• У. Диффи. Первые десять лет криптографии с открытым ключом. ТИИЭР, т.76, №5, Май 88, М, Мир, 1988, с.54–74.
• А. Н. Лебедев. Криптография с открытым ключом и возможности ее практического применения. Тем. Сб. «Защита информации», вып. 2, М.1992, с.129–147.
• А. В. Спесивцев и др. Защита информации в персональных компьютерах. М., Радио и связь, 1992, с.140–149.
• ГОСТ 28147–89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.
• С. Мафтик. Механизмы защиты в сетях ЭВМ. М., Мир, 1992.
• В. Жельников. Криптография от папируса до компьютера. М., ABF, 1996.