kantrium.com | E-Norway.ru | HELFI.ru | MySuomi.com

3. С точки зрения защиты

С точки зрения защиты

 

3.1. Введение

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

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

 

3.2. Криптографические типы

Отношения между различными криптографическими категориями показаны на рис. 3.1.

pic37

Шифрование — перестановка, или маскировка информации — используется для защиты данных от чтения неуполномоченными сторонами. Существует два типа шифрования: рассеивание (diffusion), когда информация скрывается, и перемешивание (confusion), когда информация переставляется так, чтобы, хотя сообщение и можно обнаружить, но его содержание (значение) установить невозможно.

 

3.2.1. Рассеивание

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

Рассеивание все еще используется и сегодня. Например, в электронной почте можно использовать специальные литеры или комбинации литер, которые имеют значение только для того получателя, кому они предназначены. Другие читатели в этом случае видели бы просто безобидное сообщение. Следующее английское предложение: "This sentence also appears innocent, being text advocating a key idea" — также кажется безобидным текстом, пропагандирующим некую ключевую идею. Однако вторая литера каждого слова этого предложения посылает иное сообщение — "help needed". Широкополосная радиосвязь, которая используется военными, тоже является формой рассеивания. Частота, на которой передается радиосигнал, быстро изменяется непредсказуемым способом, который известен только тому получателю, кому этот сигнал предназначен. Эта методика называется "скачкообразной перестройкой частоты", и если приемник получателя будет переходить (перескакивать) к правильным частотам, то он примет полное сообщение. Подслушивающий на одной частоте субъект примет только крошечную часть сообщения, и поэтому может даже не знать, что оно передавалось.

Стеганографию используют также для того, чтобы посылать информацию в составе видео- или звуковых файлов. Можно изменять случайные биты изображения (или звука в случае аудиофайла), добавляя в них информацию, которую нужно передать. При просмотре или прослушивании изображения или звука, которые содержат скрытую информацию, они будут выглядеть (звучать) так же, как до передачи. На рис. 3.2, а показан штриховой рисунок (схема), который скрыт в фотографии (рис. 3.2, б). Фотография состоит из 16-битных полутоновых значений, младший бит которых используется для скрытия схемы.

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

pic38

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

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

 

3.2.2. Перемешивание

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

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

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

 

3.3. Криптографические сценарии

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

Существует две возможности для нападающего (по-разному, в зависимости от автора, называемого Чарльзом или Евой). Первое нападение (атака) носит Название канал прослушивания (wiretap channel), когда Ева может прослушивать сообщения, передаваемые между Алисой и Бобом, но не может изменять их (рис. 3.3, а), и второе — нападение с подстановкой (substitution attack), когда Ева может также изменять сообщения или заменять их (рис. 3.3, б). Первая форма нападения относительно проста для большинства передающих сред, особенно для радио, где физическое соединение не требуется, тогда как возрастающее использование сетей пакетной коммутации, где данные обрабатываются в каждом маршрутизаторе, означает, что нападение с подстановкой также вполне возможно. Хорошим действующим примером второго типа канала нападения (с перехватом сообщений) является брандмауэр (firewall1) Internet.

pic39

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

  • Только зашифрованный текст. Это простое прослушивание, при кото¬ром Ева может только читать зашифрованные сообщения, когда они проходят по каналу.
  • Известный открытый текст. В этом варианте нападения Ева получает и незашифрованный, и зашифрованный текст некоторых сообщений. При этом нередко часть открытого текста можно разгадать. Обычно она является адресом или именем отправителя или временем передачи. Этот подход использовался во время Второй мировой войны — когда бомбы сбрасывались на какой-нибудь порт, то зашифрованные сообщения об этом записывались в надежде, что в них будут включены имя порта и другие детали нападения.
  • Выбранный открытый текст. При этом варианте атаки Ева может включать в зашифрованный текст свои сообщения, которые должны быть каким-то образом зашифрованы и затем прочитаны Бобом. Делает она это либо обманным путем заставляя Алису посылать свои сообщения, либо похищая оборудование кодирования и используя его самостоятельно.
  • Выбранный зашифрованный текст. Заключительная возможность для Евы состоит в том, чтобы заставлять Боба дешифровать зашифрованные сообщения, которые она генерирует, а она могла бы читать их расшифровку. Это опять-таки можно сделать, лишь захватывая или подменяя оборудование шифрования.

При всех видах нападений следует предполагать, что сам алгоритм шифрования известен. Объясняется это совсем просто — слишком много людей знают любой из этих алгоритмов, чтобы хранить их в тайне. Это предположение известно как предположение Керхкоффа (Kerchoff). Защита зависит только от ключа. Некоторые разработчики коммерческих программ шифрования в целях повышенной защиты пытаются сохранять свои алгоритмы в секрете. Однако реверсировать машинный код обратно в ассемблерный — относительно простая задача, и неблагоразумно предполагать, что такие коды не попадут в плохие руки.

 


 

1 Firewall — программно-аппаратное средство межсетевой зашиты. — Пер.

 

3.4. Системы с частными ключами

3.4.1. Введение

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

 

3.4.2. Перестановочные шифры

В перестановочных шифрах позиции символов сообщения изменяются, но значение сообщения остается неизменным. Простой шифр — это специальная таблица (сетка), куда сообщение вписывается одним способом, а затем счи-тывается — другим. Эта операция показана на рис. 3.4. Сообщение вписывается в строки сетки, а считывается по столбцам. Древний вариант этого способа состоял в записи сообщения на полосу, обернутую вокруг цилиндра, которая затем раскручивалась и отправлялась с посыльным. Как будет показано в разд. 5.4.5, обе эти формы являются простым чередованием (расслоетем), только используемым для различных целей. Все, что подслушивающему нужно сделать, — это определить глубину сетки (или диаметр цилиндра). Увеличение глубины сетки приводит к тем же проблемам с задержкой, что и при чередовании с контролем ошибок.

pic40

Усовершенствование этой методики состоит в том, чтобы читать столбцы сетки в более сложном порядке, чем просто слева направо. Для указания по¬рядка считывания столбцов можно использовать ключевое слово, алфавитное упорядочивание букв которого и определяет порядок чтения столбцов. На¬пример, если бы ключевым было слово cipher, то мы вписывали бы шифруе¬мое сообщение в 6 столбцов, и затем считывали бы столбцы в следующем порядке 1 (с), 5 (е), 4 (h), 2 (i), 3 (р) и 6 (г). Однако такая система остается все еще очень восприимчивой к нападениям по методу проб и ошибок.

 

3.4.3. Трансформационные шифры

Моноалфавитный шифр

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

О раннем использовании такой системы сообщил древнеримский коммента¬тор сплетен Светоний, хотя это ни в коем случае не первое зарегистрирован¬ное использование криптографии, которое относится к древнему Египту, и использовалось в узнаваемых сегодня формах еще греками. Светоний напи¬сал, что еще Юлий Цезарь использовал систему преобразований при обще¬нии со своими друзьями. Он заменял каждую букву сообщения на третью бу¬кву из того же алфавита (рис. 3.5), доказывая не только потребность в секретной политической связи, но и трудность сохранения такой связи в тай¬не от прессы Термин "подстановка Цезаря" теперь применяется к любому шифру с подобным сдвигом между символами сообщения и алфавитом шиф¬ра, даже если этот сдвиг не равен трем.

pic41

Более безопасной (но лишь незначительно) является произвольная подстановка, когда изменяется порядок подстановочных символов. Однако, хотя Такая система имеет больше возможных ключей (26! вместо 26 возможных в системе Цезаря, один из которых тривиален), проблема со всеми моноалфавитными трансформационными шифрами состоит в том, что их очень просто атаковать с использованием частотного анализа. Избыточность, свойственная английскому языку, такова, что только около 25 символов зашифрованного текста требуются для того, чтобы дешифровать сообщение. Если в зашифрованном тексте остаются пробелы, расшифровка его даже упрощается, т. к. однобуквенным словом может быть лишь "а" или "I". Через эти прорехи может просачиваться и другая информация сообщения. Испытательная версия подобной "защитной" программы используется в системе программирования Java для шифрования адреса Web-сайта в том случае, если не был введен правильный ключ. Однако такой зашифрованный текст легко перехватывать, поскольку все URL-адреса Web-сети начинаются с последовательности "http", а большинство из них содержат строку "www" и заканчиваются на "html" или "htm". Таким образом, кодирование символов h, t, р, w и m обычно считается заданным. Разработчики программы облегчили жизнь хакера, оставляя пунктуацию без кодировки, так что "xyz" в конце имени хост-машины — это вероятнее всего ".com". Такой код оставляет для расшифровки так мало букв, что остающиеся возможности можно проверить методом проб и ошибок.

Другая проблема с произвольной подстановкой — длина ключа, т. к. должно быть определено преобразование каждого символа. Это непросто запомнить. В простой системе подобного рода, иногда называемой подстановкой Виже-нера (Vigenere) (хотя на самом деле она не имеет никакой связи с этим французским дипломатом 16-ого столетия), используется специальное кодовое словом чтобы определить несколько первых подстановок, и затем вставляются остальные буквы. Ключ в форме кодового слова легко запомнить, но шифр очень беден, т. к. последние символы алфавита (такие как w или у) вряд ли будут вообще зашифрованы (рис. 3.6).

pic42

Полиалфавитный шифр

Одним из способов преодоления атаки частотного анализа является использование разных алфавитов преобразования, зависящих от позиции символа в сообщении. Система, изобретенная Джироламо Кардано (Girolamo Cardano), упоминается после системы Виженера, хотя на самом деле именно он (Виже-нер) разработал автоключевую систему, описанную в разд. 3.4.7. Имя Блэза де Виженера, к сожалению, неправильно связывают с созданием двух шифров, которые он на самом деле не разрабатывал, и наоборот, не связывают с намного более качественным шифром, который действительно он изобрел. Для определения числа подстановок Цезаря, которые впоследствии будут использоваться для кодирования, применяется специальное кодовое слово. Например, пусть этим кодовым словом будет "code". Оно определяет четыре алфавита (рис. 3.7, а), первый— со сдвигом 2, второй — со сдвигом 14, третий — со сдвигом 3 и четвертый — со сдвигом 4. Пример кодирования показан на рис. 3.7, б.

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

pic43

 

3.4.4. Одноразовое заполнение

Можно расширить понятие полиалфавитного шифрования до системы, назы ваемой "одноразовым заполнением" (One Time Pad), которая является единст венной полностью безопасной криптосистемой. В полиалфавитном шифровании существует проблема повторения ключа. В системе одноразового заполнения каждое сообщение шифруется с ключом, который затем сбрасывается и никогда не используется снова. Поэтому ключ используется только один раз, давая шифру его название. Криптограмма зависит от сообщения и ключа, но так как ключ уникален для данной передачи и никогда повторно не используется, то подслушивающий не имеет никакой возможности узнать его и взломать шифр. Процесс кодирования может быть очень простым — нужно просто добавлять ключ к сообщению (рис. 3.8).

pic44

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

 

3.4.5. Кодировщики со сдвиговым регистром

В разд. 6.4.3 будет рассмотрено использование перестановок в приложениях линейного кодирования, с помощью которых мы попытаемся разрушать длинные ряды нулей и единиц. Подобную методику можно применять и для шифрования, используя линейный сдвиговый регистр с обратной связью (Linear Feedback Shift Register, LFSR), инициализируя его некоторым значе¬нием и затем добавляя его вывод к сообщению. Аналогичный LFSR-регистр в приемнике будет возвращать биты к их первоначальной последовательности (рис. 3.9). m-каскадный регистр сдвига в общем случае способен к созданию неповторяющихся последовательностей длины до 2m-l, которые предполагают хорошую защиту даже для относительно небольших значений т, но, к сожалению, система очень восприимчива к известному нападению с открытым текстом. Так как существует только т каскадов, то требуются лишь 2m разрядов в последовательности сдвигового регистра для того, чтобы вычислить ответвления обратной связи и взломать код.

pic45

В практических приложениях используются также нелинейные сдвиговые реги¬стры с обратной связью, которые обладают устойчивостью против подобных нападений. Нелинейным элементом может быть JK-триггер или мультиплексор. Можно также использовать и умножение, но проблема состоит в том, что оно является асимметричной операцией и дает 0 в трех случаях, а 1 — только в од¬ном (для 1x1). Это означает, что в выходной последовательности может быть слишком много нулей и характеристики сообщения могут "утекать" через нее.

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

 

3.4.6. Продукционные шифры

Как перестановочные, так и трансформационные шифры имеют свои преиму¬щества. Поэтому безопасную криптосистему можно построить путем их объе¬динения. Продукционный шифр — это такой шифр, в котором объединены две или несколько криптографических функции, выполняемых одна за другой. Примером такой системы является шифровальная машина военного времени "Enigma" (Загадка), в которой ряд кодовых колес переставлял и преобразовы¬вал символы сообщения в кодовые символы. Многие коммерческие шифры основаны на принципе выполнения достаточного количества относительно простых перестановок и преобразований, формирующих безопасную систему.

Хорошим примером системы этого типа является стандарт шифрования данных (Data Encryption Standard, DES), который использует последовательность из 16 преобразований и перестановок. Он имеет 56-разрядный ключ, который, хотя и восприимчив к нападениям "в лоб", но все еще очень популярен. Другие примеры продукционных шифров коммерческого использования — Blowfish Брюса Шнейера, ТС4 Рональда Райвеста (соавтора криптосистемы RSA) и IDEA (International Data Encryption Algorithm) — международный алгоритм шифрования данных, который использует 128-разрядный ключ и ряд, состоящий из 8 преобразований и перестановок.

Продукционные шифры обеспечивают очень хороший компромисс между защитой, сложностью и генерацией/распределением ключей. Они продолжают быть популярными и приняты Национальным институтом стандартов и технологий США (NIST, National Institute of Standards and Technology) для замены стандарта DES под названием Advanced Encryption Standard, AES (Расширенный стандарт шифрования).

DES

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

Кроме шифрования передаваемых данных стандарт DES также используется для шифрования паролей в операционной системе UNIX и для проверки PIN-кодов2 на кэш-картах ATM.

DES-алгоритм состоит из 16 стандартных конструктивных блоков, которые переставляют и преобразуют 64-разрядные входные блоки в 64-разрядные выходные (рис. 3.10, а). Каждый стандартный конструктивный блок работает с отдельным 48-разрядным ключом, который получается из первоначального ключа. Ключ состоит из 64 разрядов, но 8 из них — разряды проверки на четность, так что фактически ключ имеет длину 56 разрядов. До подачи в первый стандартный конструктивный блок, 64-разрядный ввод подвергается перестановке, а после прохождения через блоки — обратной перестановке.

 


 

PIN — сокращение от Personal Identification Number, личный идентификационный номер (код) в различных электронных, в частности, банковских системах. — Пер.

 

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

pic46

Нелинейная функция детализирована на рис. 3.10, в. 32-разрядный правый блок входа расширяется до 48 битов путем двойного повторения половины его разрядов и их перестановки. Затем к этому блоку добавляется специфический 48-разрядный ключ. Результат делится на восемь 6-разрядных блоков. Каждый из этих блоков используется как адрес для массива, состоящего из 8 S-элементов. Каждый S-элемент в этом массиве представляет число от 0 до 1S, так что выходом каждого S-элемента является 4-разрядное число, поэтому функции 5-элементов уменьшают выход до 32 разрядного числа. Функция 5-элемента нелинейна, т. е. F(A) + f(B) <> f(A + В), а сами 5-элементы различны. Перед добавлением к левому 32-разрядному блоку 32-разрядный выход S-элементов снова подвергается перестановке и затем используется для формирования нового 32-разрядного правого блока выхода.

16 секций подключей формируются из 56 значащих разрядов ключа (без учета разрядов проверки на четность) путем их расщепления на две секции по 28 разрядов. Затем эти 28-разрядные секции циклически сдвигаются на один или два разряда и между каждым этапом каждые 48 разрядов соответствующего этапа извлекаются и переставляются, формируя подключи К1—К16- Если подключи используются в прямом порядке (K1 К2, К3,..., К16), то выполняется прямое шифрование. Если же они используются в обратном порядке (K16, К15,..., К1), то в результате происходит инверсия функции шифрования, т. е. зашифрованный блок преобразуется обратно в соответствующий блок сообщения. Это означает, что для шифрования и дешифровки может использоваться одно и то же оборудование.

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

Для работы с DES требуются весьма мощные компьютеры. В течение ряда лет полный перебор в течение нескольких часов был возможен только для очень богатых организаций, но прогресс в изготовлении микропроцессоров теперь вкладывает эти возможности в руки любой организации, позволяя экономить десятки миллионов долларов на использовании чужих секретов. Двойная шифровка сообщений приводит к небольшому увеличению защиты из-за возможности применения так называемого "встречающегося посередине" (meet in the middle) нападения. Однако шифрование с одним ключом, дешифрование — со вторым и повторное шифрование — с третьим, которое называется тройным DES-шифрованием, увеличивает число ключей, требующих проверки, приблизительно до 280, что снова можно считать безопасным.

Расширенный стандарт шифрования (AES)

Как отмечалось ранее, DES-стандарту присуща повышенная сложность обрабатывающего оборудования, что привело к практическим предложениям по его пересмотру. После открытого приглашения к разработке алгоритмов, на которое было получено 21 предложение от 11 стран, и двухлетней процедуры их оценки Национальный институт стандартов и технологий США (NIST) выбрал замену для DES в форме Расширенного стандарта шифрования (AES). Для него был принят шифр, строящийся по алгоритму Райндала (Rijndael). Это сложный блочный продукционный шифр, который может быть эффективно реализован. Шифр Райндала был разработан фламандскими исследователями Джоан Даймен (Joan Daemen) и Винсентом Райменом (Vincent Rijmen). В стандарте определяется три размера ключей: 128,192 и 256 разрядов.

Также как DES, алгоритм состоит из нескольких раундов, точное число которых зависит от размера ключа, состоящих из перестановок и добавления под-ключа. Хотя алгоритм Райндала может работать и на других размерах блоков, стандарт AES определяет размер блока, равным 128 разрядов. Этот блок разбивается на 168-разрядных байтов, размещаемых в массивах размером 4 строки х 4 столбца. Каждый раунд обработки состоит из четырех этапов: нелинейного преобразования ^-элемента, которое реализуется как отображение одного байта в другой, перестановки строк, перемешивания столбцов и, наконец, добавления подключа текущего раунда.

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

 

3.4.7. Поточные шифры

В поточных шифрах имеется обратная связь от открытого текста или, аналогично, от зашифрованного текста к ключу. Использование сообщения для формирования ключа таким способом называется автоключом (autokey) и было впервые предложено Виженером в 1568 году. Этот способ шифрования имеет преимущество в части сокращения длины ключа, который нужно сохранять или транспортировать, но есть в нем и очень существенный недостаток, состоящий в том что, если в посылаемом сообщении содержится какая-нибудь ошибка, то эта ошибка будет размножаться. В блочном шифре каждый блок рассматривается отдельно, так что ошибки будут затрагивать только один блок.Система Виженера подобна полиалфавитной системе, которая теперь носит его имя, но вместо повторения ключевого слова для определения алфавита (см. рис. 3.7), после начального ключевого слова (в качестве которого Виже-нер использовал одиночный символ) используется сам текст сообщения (рис. 3.11). Это позволяет избегать повторений, которые ослабляют полиалфавитные системы, но если хотя бы один символ искажен, то, начиная от этой точки, расшифровка будет ошибочной.

pic47

Для того чтобы дешифровать сообщение, приемник знает ключевое слово или символ (в примере, показанном на рис. 3.11, это один символ — "С"), что позволяет расшифровать первый символ сообщения. Это дает ключ для следующего символа, и т. д. Шифрованию и расшифровке помогает таблица Виженера (рис 3.12). Шифром буквы в первой строке по алфавиту, заданному в первом столбце, является буква на пересечении этой строки и столбца.

pic48

Такая автоключевая система не ограничивается системой Виженера, ее мож¬но использовать и с другими шифрами. Достаточно серьезной проблемой яв¬ляется распространение ошибок, но, чтобы оказывать влияние на текущее кодирование, можно использовать предыдущие сообщения, открытые или закодированные. Это обеспечивает существенное преимущество, состоящее в том, что нарушаются взаимно-однозначные отношения между входными и выходными блоками, от которых страдают даже сложные блочные шифры. Например, если для защиты банковской системы используется DES-шифрование, то могут существовать короткие сообщения (например, подтверждающие транзакции), которые являются одинаковыми во всех случаях. Подслушивающий может сформировать справочную таблицу шифрограмм без необходимости фактической расшифровки сообщений. Чтобы предотвратить это, DES-шифрование можно использовать в поточном режиме — этот очень популярный режим, называемый "сцеплением блоков шифра" (СВС-операция3) показан на рис. 3.13. Прежде чем шифровать сообщение, к нему добавляется предыдущий блок шифрограммы, а для первого блока используется некоторое начальное значение (НЗ) этой шифрограммы. Существует, правда, еще и проблема с очень короткими сообщениями, которые все еще можно распознавать, так что НЗ часто делается зависящим от номера коммуникационной последовательности или от некоторой другой переменной, известной обеим связывающимся сторонам.

pic49

 


 

3 СВС — Cipher Block Chaining, сцепление блоков шифра. — Пер.

 

3.5. Криптосистемы с общим ключом

3.5.1. Проблема распределения ключей

Серьезной проблемой является распределение и управление ключами. В криптосистеме с частными ключами каждое коммуникационное звено требует отдельного ключа. Для двух пользователей требуется только один ключ, но когда к системе с и - 1 уже существующими пользователями каждый раз добавляется по одному пользователю, то требуется п - 1 дополнительных ключей. Это означает, что система с п пользователями требует pic50 различных ключей. Система, показанная на рис. 3.14, имеет 8 пользователей, так что для нее требуются 28 ключей.Криптосистема с общим ключом, как подсказывает название, имеет ключ, который является общим и поэтому доступным для всех сторон, которые желают поддерживать связь. Это решает проблему распределения ключей — они могут быть опубликованы в чем-то похожем на телефонную книгу, например. Устраняется также потребность для поддерживающих связь сторон в заблаговременном согласовании ключей. Алиса может посылать зашифрованное сообщение Бобу, даже если она никогда не имела никакого предыдущего контакта с ним, что важно для таких приложений, как электронная торговля, где требуется безопасная связь с незнакомцами.

pic51

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

На первый взгляд, это выглядит так, как если бы система с общим ключом требовала большего количества ключей, т. к. каждая дуплексная связь требует двух ключей, по одному для каждого направления. Однако в системе с общим ключом, хотя имеется 56 коммуникационных связей, каждая связь с одним и тем же адресатом использует один и тот же ключ (общий ключ этого адресата), так что фактически требуется только 8 ключей. Кроме того, каждая связывающаяся сторона должна хранить только один ключ — свой частный секретный ключ, вместо n-1 ключей в случае системы с частными ключами.Системы с общим

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

 

3.5.2. Односторонние функции

Односторонняя (one-way) функция — это функция, которую просто вычислять, но трудно обращать. Пример — умножение больших чисел. Мы можем вычислить без слишком больших трудностей произведение 89 681 х 96 079 = 8 616 460 799, но обратный процесс — факторизация (разложение на множители) числа 8 616 460 799 существенно труднее. В. С. Джевонс (W. S. Jevons), рассматривавший эту проблему в 1873 г., резюмировал, что "мы можем легко... сделать некоторую вещь, но можем иметь много неприятностей, если попытаемся разделить ее". Это наблюдение, которое имеет отношение не только к арифметике!

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

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

Система работает следующим образом.

  1. Каждый пользователь имеет пару ключей Ki и Li
  2. Сообщение т шифруется с помощью функции Е(m, Кi) = с.
  3. Выполняется дешифрация с помощью функции D(E(m, К,), £,) = m
  4. Е и D проектируются так, чтобы:
  • для заданных m и Kt можно было легко находить с = Е (т, Ki);
  • для заданного с было бы нереально найти т (то есть функция Е должна быть односторонней);
  • для заданных с и Z,, можно было легко найти т (то есть функция Е должна иметь "лазейку", задаваемую параметром L,).

Для использования в криптосистемах были предложены различные функции.

  • Ключевой обмен Диффи-Хеллмана (Diffie-Hellman). Основан на трудности вычисления дискретных логарифмов полей, которая возрастает по сравнению с вычислениями на основе степенных функций. Это не совсем шифр, но это первая опубликованная система с общим ключом.
  • RSA (криптосистема Райвеста, Шамира, Альдемана). Основана на трудности факторизации (разбиения на множители) произведения по сравнению с операцией умножения. Это наиболее популярная система с общим ключом, используемая, например, для почтовой программы, реализующей протокол POP (Post Office Protocol). Но в вычислительном отношении она довольно дорогая, и коммерческое ее использование в США подлежит патентованию.
  • Knapsack. Методика с таким странным4 названием основана на трудности разделения суммы на индивидуальные элементы по сравнению с добавлением этих элементов в начало суммы. Было много успешных атак на эту систему и в результате она используется довольно редко. Однако, она менее сложна, чем RSA, и до появления более современных систем с эллиптическими кривыми ее считали системой, вполне оправдывающей свои обещания, т. е. обладающей низкой сложностью и относительной безопасностью.
  • Эллиптические кривые. Эллиптические кривые — это специальные линии, определенные над первичным полем. Задав некоторую точку на этой линии, легче вычислять и все другие ее точки. Без генерации всех возможных точек (что не практично, если поле достаточно велико) обращение операции довольно затруднительно. Эти схемы являются довольно многообещающими, потому что кодирование и декодирование в них не очень-то сложное. Если не касаться защиты, то эта схема обладает всеми преимуществами предыдущей.
  • Коды с исправлением ошибок. Хотя код с исправлением ошибок (см. разд. 5.4) способен исправлять до (d - 1)/2 ошибок, но без набора декодирующих правил единственный способ реализовать эту возможность состоит в том, чтобы сравнивать полученный вектор с каждым кодовым словом и выбирать тот, который находится на расстоянии (d- 1)/2 от него. Для длинных кодов это практически невозможно. Поэтому можно сформировать криптосистему, использующую код с исправлением ошибок, выполняя перестановки генерирующей матрицы. Исходный генератор формирует частный ключ, позволяющий декодировать сообщения, а генератор с перестановками используется в качестве общего ключа. Посылаемые сообщения маскируются добавлением ошибок, которые подслушивающий не может удалить, т. к. генератор с перестановками не позволяет выполнить простое декодирование.

 


 

"Knapsack" (англ.) — означает ранец, заплечный мешок. — Пер.

 

3.5.3. Ключевой обмен Диффи-Хеллмана

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

Протокол выполняет обмен секретом между двумя сторонами по опасному каналу, не требуя ни знания, ни даже существования этого секрета. Работает это следующим образом.

  1. Алиса и Боб соглашаются использовать генератор g и простой модуль р.
  2. Алиса генерирует случайное число х. Это ее частный ключ. Она вычисляет свой общий ключ X, который равен X = g* mod p.
  3. Подобным же образом Боб генерирует случайный частный ключ у и общий ключ Y = g* mod p.
  4. Алиса и Боб обмениваются их общими ключами X и Y.
  5. Алиса принимает ключ Y и использует свой частный ключ х для следующего вычисления: Xy mod р = gxy mod р = к.
  6. И Алиса и Боб теперь знают к, но подслушивающий не может вычислять к по наблюдениям g,p, X, и Y.

В качестве примера такого обмена рассмотрим следующую процедуру.

  1. Р=11 И Алиса получает случайный х = 4, Боб выбирает у = 6.g=2.
  2. Алиса получает случайный х = 4, Боб выбирает у = 6.
  3. Алиса вычисляет Х= 24 mod 11=5.
  4. Боб вычисляет Y = 26 mod 11=9.
  5. Алиса посылает Бобу число 5, а Боб посылает Алисе число 9.
  6. Алиса вычисляет YX mod 11 = 94 = 6561 = 5 mod 11.
  7. Боб вычисляете mod 11 = 56 = 15 625 = 5 mod 11.
  8. Поэтому к = 5.

Обратите внимание, что общий секрет случаен, т. к. к = gxy mod р, так что его нельзя использовать, чтобы напрямую посылать информацию. Если Алиса и Боб не выбирают свои частные ключи чисто случайно, то это знание можно использовать для нападения на систему.

Когда Р и g опубликованы, то нападение на эту систему становится эффективным с помощью задачи дискретного логарифмирования. X — gx mod Р  означает, что х = loggX mod Р. Поэтому Ева может находить к, вычисляяYloggX  mod Р. В вышеупомянутом примере нахождение log25 mod 11 тривиально, но очень трудно, если Р велико.

 

3.5.4. Криптосистема RSA (Rivest, Shamir, Adleman)

Схема RSA Райвеста, Шамира, Адлемана (Rivest, Shamir, Adleman) связана с от носительной трудностью факторизации чисел по сравнению с их умножением. Это одна из наиболее популярных систем, используемых, например, в PGP-программе5 шифрования почты. Она запатентована в Соединенных Штатах.

 


 

5 PGP — Pretty Good Privacy, алгоритм "надежной конфиденциальности". — Пер.

 

Для генерации ключа выбираются два больших простых случайных числа: р и q. Насколько больших — зависит от приложения и соглашения, но часто используются числа порядка сотни цифр. Эти простые числа хранятся в секрете, но их произведение n=pq и случайное число е, простое по отношению к (р - 1)(q - 1), публикуются и формируют общий ключ. Частный ключ d выбирается таким, чтобы соблюдалось следующее равенство: de = 1 mod(р - 1)(q - 1). Обратите внимание, что т.к. р и q хранятся в секрете, то любой подслушивающий не может вычислить d без факторизации m.

Сообщение m шифруется с помощью следующего выражения

с = me mod п,

где с — зашифрованное сообщение.

Расшифровка же выполняется с помощью выражения

m = cd mod n,

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

Факт, что расшифровка работает (то есть что (me)d mod n = m mod n) не очевиден, но зависит от теоремы Эйлера, в которой утверждается, что аф(n)= (mod n) для относительно простых чисел а и и, таких что 0 < а < n.Здесь ф — функция Эйлера (тотиент), определяемая как количество положительных целых чисел, меньших n, которые являются относительно простыми для n. Если n — простое число, то ф(n) = n — 1. Если же n — это произведение двух простых чисел р и q, как в нашем случае (то есть n =pq), то

ф(n)=pq-1-(p-1)-(q-1)=pq-p-q+1=(p-1)(q-1),

т. к. нет числа, меньшего, чем п, которое является множителем как числа р, так и числа q.

Это говорит о том, что de = 1 mod ф(n) по определению и, в свою очередь, означает, что de = 1ф(n) + 1 для некоторых /. Дешифрация приводит к следующей цепочке вычислений:

cdmod n = medmodn = miф(n+1) mod n = (mф(n))km mod n = (1)km mod n = m mod n

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

Очевидное нападение на эту систему — это факторизация n на два множителя p и q. Оно требует pic52 операций, основанных на более доступных алгоритмах факторизации. В году содержится приблизительно 2 секунд, так что при использовании одного процессора, работающего со скоростью в один миллиард операций в секунду, потребуется приблизительно 241 лет, чтобы факторизовать 1024-разрядный ключ (который используется в PGP-алгоритме защиты почты). Это больше чем время существования Вселенной со времени большого взрыва, и сравнимо примерно с годом, который потребовался бы, чтобы взломать защиту системы DES, использующей аналогичные предположения. Для организаций, подобных правительственным, способных вложить большие деньги в решение этой проблемы, время взлома DES-защиты можно сократить всего лишь до нескольких часов, используя параллельно несколько компьютеров, но масштаб проблемы в случае RSA-защиты делает эту задачу вообще невыполнимой, если не использовать иной подход. Другое нападение могло бы заключаться в том, чтобы найти такое число х, которое удовлетворяло бы уравнению хе mod n = с. Но это привело бы только к взлому (расшифровке) индивидуального сообщения и не взламывало бы всю систему в целом, и, в любом случае проблема отгадки сообщений была бы столь же трудной, как и проблема факторизации.

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

 

3.6. Идентификация

3.6.1. Введение

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

 

3.6.2. Целостность

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

Простой способ обеспечить правильный прием — попросить, чтобы отправленное сообщение было послано обратно (рис 3.15, а). Однако работа с такими протоколами требует осторожности. Если речь идет о системе с частным ключом, то ключи, используемые Алисой и Бобом, будут одинаковыми, так что все, что Боб должен будет сделать, получив зашифрованное сообщение, — это послать его назад Алисе, и оно будет таким же, как криптограмма, посланная от Алисы к Бобу. Если Еве вместо простого отвода от линии связи удастся включиться в разрыв этой линии, то она сможет, получив криптограмму от Алисы, отправить ее назад (Алисе) без ее декодирования. Тогда Алиса будет думать, что именно Боб принял и понял ее сообщение, тогда как фактически оно так никогда до него и не доходило (рис 3.15, б). Такой перехват сообщения более труден, чем простой отвод в обычной цепи связни, но для пакетных систем, подобных Internet, где сообщения посылаются от машины к машине, сброс или подстановка сообщения выполняются тривиально при обращении к промежуточному компьютеру. Ева не может декодировать сообщение, но она может вводить в заблуждение Алису, заставляя ее думать, что сообщение получил Боб, когда на самом деле этого не произошло. Если сообщение — это что-то вроде "заплатите 1 000 000$ по счету X", то удаление таких сообщений может очень дорого стоить.

pic53

Единственный способ предотвратить это нападение состоит в том, чтобы за¬шифровать адрес и, таким образом, изменять возвращаемое сообщение. Од¬нако здесь требуется осторожность. Если в качестве дополнения к сообще¬нию посылается зашифрованный адрес, то мы имеем с = е(T, к) + е(а, к). Теперь все, что должна делать Ева, это — прослушать несколько правильных сообщений между Алисой и Бобом, чтобы выяснить е(а, к), где аА — адрес Алисы, а ав — адрес Боба. Когда она хочет перехватить сообщение, она от¬бирает из сообщения зашифрованный адрес е(аА, к) и заменяет его на е(ав, к).

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

Этих нападений можно избежать, если вместо добавления адреса в конец сообщения сделать сообщение функцией от посылаемой информации и адреса. Тогда мы имеем с = e(f(m,a)k). Теперь, хотя Ева знает аA, и ав, она не может вычислить правильный ответ е(f(m,аB)к), чтобы обмануть Алису.

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

Если Боб, со своей стороны, не знает адрес, откуда передает Алиса, все что Ева должна делать при передаче сообщения, — заменить свой адрес на адрес Алисы (рис. 3.16). Боб отвечает кодированием сообщения с общим ключом "Алиса", который фактически является ключом Евы, т. к. она поменяла адреса. Поскольку ответ кодируется с общим ключом Евы, она может декодировать его и восстановить сообщение. Затем она заново кодирует сообщение с общим ключом Алисы и посылает его так, чтобы Алиса и не подозревала о перехвате. Как в случае симметричного шифра, это нападение можно предотвратить, сделав сообщение функцией посылаемой информации и адреса, причем так, чтобы адрес нельзя было извлечь отдельно.

pic54

Вместо посылки сообщения обратно к источнику, некоторые из этих проблем можно обойти, посылая обратно случайные (хеш-) сообщения, h(m). Хеш-функция отображает входной набор символов на выходной набор фиксированной длины. Хеш-функция должна быть достаточно простой для вычислений, но очень трудной или даже невозможной для инвертирования, и такой, чтобы с высокой вероятностью выполнялось соотношение h(m1)=h(m2)=> m1 = m2 Чем больше фиксированная длина выхода, тем выше эта вероятность, но тем больше информации должно быть послано. Этим требованиям удовлетворяют односторонние функции, так что можно использовать общий ключ системы с общим ключом, но его не очень просто вычислять. Однако никакого частного ключа не требуется. Так как Алиса знает сообщение тп, она может кодировать его, чтобы найти е(m, Рh) и сравнить его с полученной хеш-функцией. Когда первоначальная криптограмма посылается Алисой, то для Евы атака тоже затруднена. Весьма популярны в качестве хеш-функций стандарты DES и MD5 , т. к. они вводят менее сложные вычисления, чем односторонние функции, используемые для общих ключей.

 

3.6.3. Идентификация

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

Категоризированные идентификационные (опознавательные) системы американского ФБР основаны на том, что человек знает (например, пароль), что он имеет (например, ключ), и что он собой представляет (например, отпечатки пальцев или образец сетчатки глаза). Любая опознавательная схема должна быть основана по крайней мере на двух категориях — на соответствующей физической безопасности и все еще остающейся проблеме удаленной связи. Система не может зависеть от того, что Алиса просто скажет: "Я Алиса", потому что Ева способна сделать запись предыдущего опознавательного сеанса и воспроизвести это сообщение. Чтобы избежать подобной атаки, хороший опознавательный протокол должен включать вызов, за которым последует ответ, базирующийся на этом вызове, который доказывает, что партнер по связи именно тот, кем он себя объявляет.

 


 

6 MD5 — Message Digest 5, профиль сообщения 5. — Пер.

 

Основу для идентификации может обеспечить система с общим ключом. Только подлинные партнеры по связи будут знать их собственные частные ключи, и можно будет использовать этот факт, чтобы их опознавать (идентифицировать). В системе с общим ключом, обозначив функцию шифрования как Е, а дешифрования — как Д получим D(E(m)) = m, т. е. дешифровка шифрованного сообщения m приводит к исходному сообщению. Однако, если начать преобразования с криптограммы, то можно получить выражение E(D(c)) = с, т. е. шифрование дешифровки криптограммы с дает исходную криптограмму.

Вокруг этих фактов можно построить протокол. Если Боб желает опознать Алису, то можно поступить следующим образом.

  1. Генерировать случайную криптограмму (с), т. е. сообщение с тем же алфавитом, как в зашифрованном сообщении.
  2. Послать криптограмму Алисе для дешифровки.
  3. Алиса дешифрует сообщение, используя свой частный ключ. Так как первоначальная криптограмма была случайна, то дешифрованное сообщение будет бессмысленно, но только тот, кто обладает частным ключом, может сгенерировать его.
  4. Алиса посылает дешифрованное сообщение (m) обратно Бобу, который  затем зашифровывает это с общим ключом Алисы.
  5. Если заново зашифрованное сообщение соответствует случайной криптограмме, которую Боб первоначально сгенерировал, т. е. если Е(т) = с, то Алиса должна иметь частный ключ и, если имеет, то поэтому действительно является Алисой.

Если бы Ева претендовала быть Алисой, то ей пришлось бы быть способной к генерации такого сообщения т, чтобы выполнялось соотношение Е(т) = с, где с — шифрованное сообщение, посланное Бобом. Это эквивалентно тому, что Ева может декодировать криптограммы и тем самым взламывать шифр. Однако требуется некоторая осторожность, чтобы генерируемое Бобом сообщение с было действительно случайным. Если бы это было не так, то Ева была бы способна подобрать подходящее значение т для специфического значения с, используемого Бобом, вероятно просто наблюдая предыдущие попытки опознавания. Этим способом была взломана система смарт-карт оплаты телевидения, поскольку "случайный" вызов был фактически 8-разрядным двоичным числом. Хакеры взломали эту систему, делая запись всех возможных опознавательных вызовов и ответов, даваемых подлинными картами, и затем программируя точные копии карт со справочной таблицей правильных ответов без необходимости что-нибудь знать относительно действий алгоритма. Это нападение было возможно, потому что подлинные карты имели чрезвычайно ограниченную память и мощность обработки.

3.6.4. Цифровые подписи

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

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

Системы с общим ключом обеспечивают возможность обойти эту проблему, используя процесс, подобный процессу идентификации. В данном случае в качестве "случайной" криптограммы мы используем сообщение или случайно перемешанное сообщение. Алиса подписывает документ, используя свой частный ключ, чтобы "дешифровать" перемешанное сообщение. Это дешифрованное сообщение и есть подпись. Затем Алиса посылает сообщение и подпись Бобу, шифруя все, что посылается, общим ключом Боба. Боб дешифрует сообщение своим частным ключом и проверяет подпись, зашифрованную общим ключом Алисы, на равенство случайно перемешанному сообщению.

3.7. Другие криптографические протоколы

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

3.7.1. Удаленное бросание монеты

Пример удаленного бросания монеты демонстрирует такой тип конструкции, который требуется для создания хороших протоколов. Рассмотрим следующий сценарий: Алиса и Боб решают отпраздновать некоторую дату. Алиса хочет встретиться в ресторане, но Боб предпочел бы паб. При обсуждении вечерней программы по телефону Боб предлагает бросить монету и приглашает Алису назвать исход. Она говорит "орел", после чего Боб сообщает, что, к сожалению, у монеты выпала "решка", так что они идут в паб. Может ли Алиса доверять Бобу? Фактически, даже если бы Боб сказал, что у монеты выпал "орел", как Алиса может узнать, был ли это правильный ответ или Боб просто проявил учтивость? Хороший протокол должен защитить как от ложных проигрышей, так и от ложных побед.

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

Уравнение х2 = а имеет два решения (корня) для любого положительного числа а, который является квадратом некоторого числа. Например, если а равно 4, то х может быть равным 2 или -2. То же правило можно применить и для числовых полей, сравниваемых по простому модулю р. Например, х2 = 4 mod 5 также имеет два решения x1 = 2 и х2 = 3 (= -2 mod 5). (Обратите внимание, что а должно быть квадратом некоторого числа в этом поле. Приведенный случай не имеет решения для а = 2 или 3).

Если вместо простого модуля мы используем композицию, составленную из двух простых чисел, то получим 4 корня. Например, если р = 3 и q = 5, то u2 mod 15 = 1 имеет решения 1, 4, 11 (=-4 mod 15) и 14 (=-1 mod 15). Для многих простых р существуют методы вычисления корней по mod р, но для больших составных чисел их очень трудно выполнять. Однако если для составного числа n=pq мы знаем р и q, то мы можем вычислить корни п по корням р и q, вычисленным по mod р и mod q, соответственно. Протокол работает следующим образом.

  1. Алиса выбирает два больших простых числа р и q и посылает их произведение n = pq Бобу.
  2. Боб случайным образом выбирает целое число и между 1 и n/2 включительно, и посылает его квадрат Алисе. Этот квадрат имеет четыре корня, два из которых будут между 1 и n/2 (т. к. если х находится между 1 и n/2, его отрицательное значение -х не будет находиться в этом интервале, и наоборот).
  3. Используя свои знания о р и q, Алиса вычисляет четыре квадратных корня выражения z mod п. Обозначим корни этого выражения как ±х и ±у. Она выбирает два корня между 1 и n/2. Пусть это будут х' и у'. Пусть, кроме того, она знает, что и — это один из этих корней, но не знает — какой.
  4. Алиса выбирает один из этих корней и посылает его Бобу. Это делается путем определения такого наименьшего i, для которого i-й разряд в числах х' и у' различается, и в предположении, что i-й разряд и есть 0 или 1. Заметим, что Алиса не посылает все число Бобу, т. к. если бы она выбрала его неправильно, то Боб тогда знал бы как и, который выбрал он, так и другой корень, посланный Алисой, и мог бы тогда заявить, что Алиса выиграла, когда она на самом деле проиграла.
  5. Боб сообщает Алисе, является ли ее выбор правильным или нет, и посылает ее и, чтобы доказать это.
  6. Алиса посылает р и q Бобу так, чтобы он мог найти другие корни и проверить, что Алиса придерживалась соответствующей процедуры.

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

 

3.7.2. Неосознанная передача

Пример 50%-го шанса на успех, очевидного при удаленном бросании монеты, можно использовать в протоколах для "неосознанной передачи". Неосознанной называют такую передачу, при которой секрет совместно используется (скажем, Алисой с Бобом), но так, что она не знает (или не обращает внимания на то), получил ли Боб секрет или нет. Хотя это может казаться довольно бессмысленным в коммуникационной системе, существуют случаи, когда вы не хотели бы, чтобы '"владелец" секрета знал, получил ли кто-нибудь доступ к этому секрету или нет. Примером может быть система голосования, где важно, чтобы избирательные бюллетени были проверены, но человек, опускающий их, остается анонимным. Система действует следующим образом.

  1. Алиса выбирает n=pq, где р и q— это большие простые числа, и посылает п Бобу.
  2. Боб выбирает х и посылает его квадрат по mod п обратно Алисе. Заметим, что в отличие от бросания монеты, в данном случае это значение может не находиться в интервале между 1 и n/2. В этой точке протокола Боб знает два из четырех корней (x и -x).
  3. Алиса вычисляет корни полученного значения (±х и ±у) и посылает один из них Бобу.

Так как Алиса не знает число, выбранное Бобом, то имеется 50%-й шанс, что Алиса пошлет Бобу один из корней, который он уже имеет. Если Боб получает такой корень, то он не получает никакой информации и не владеет секретом. Однако, если он получает другой корень, то он может использовать эту информацию для факторизации и на множители р и q. Поэтому с вероятностью 1/2. Боб получает секрет, но Алиса сама не знает, получил ли Боб его или нет.

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

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

Этот тип протоколов имеет также применение к системам электронных расчетов. Обычные наличные деньги имеют следующие свойства.

  • Защита от подделки. Выпускать банкноты не просто, поэтому и подделывать их довольно трудно.
  • Универсальная аккредитация. Наличным деньгам доверяют все, потому что они имеют поддержку банка, кроме того известно, что их все принимают.
  • Анонимность. Владение наличными деньгами не связывает вас с конкретной транзакцией, и те, кто вовлечены в транзакцию, не должны знать Друг друга или доверять друг другу для проведения транзакции. Верят в деньги, а не в человека.

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

3.8. Практическая защита

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

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

3.8.1. Какова необходимая степендаащиты?

Важный вопрос — какую степень защиты нужно обеспечивать? В настоящее время можно использовать очень защищенные схемы, но когда системы становятся более защищенными, растет и их сложность, увеличиваются объемы передаваемых данных и затраты на их обработку. Стоимость нападения на систему также изменяется, поскольку чем более мощная обработка используется для атаки на код, тем быстрее может быть взломан алгоритм защиты. Между этими тремя факторами существует определенная связь: дополнительная передача и стоимость обработки имеют отношение к схеме защиты, к стоимости нападения на схему и стоимости самой информации (в терминах ее ценности для нападающего или потерь для владельца). Например, для атаки на транзакцию кредитной карточки с лимитом в 100£ (фунтов стерлингов) не стоило бы подключать большие обрабатывающие мощности, но для нападения на систему передачи международного банка, обрабатывающую сотни миллионов фунтов, стоило бы инвестировать в соответствующие вычислительные мощности несколько миллионов фунтов. По этой причине одиночная DES-защита безопасна для первого случая, но недостаточна для последнего, хотя тройной DES-защиты было бы достаточно. Однако для небольших устройств слишком сложна даже одиночная DES-защита.

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

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

3.8.2. Проверка полномочий

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

3.8.3. Аварийные ситуации

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

3.8.4. Человеческий фактор

Коммуникационная среда может быть опасна, но это "надежная" опасность. Часто самым слабым звеном в цепи является человек. Люди могут обходить системы очень творчески или злонамеренно или просто от недостатка знания соответствующей системы. Еще один из самых общих и очевидных недостатков — это бедный выбор паролей или других ключей системы. Может показаться, что стремление сделать систему более сложной, сделает ее и более безопасной, но это часто заставляет пользователей попытаться обмануть ее (чтобы сэкономить время или усилия), например, записывая ключи, которые должны запоминаться. И наконец, как бы ни была защищена система, в некоторой ее точке человек должен управлять ею или интерпретировать ее данные. Этот человек может быть подкуплен или принужден обойти защиту.

ПечатьE-mail

Яндекс.Метрика