IEEE Network Magazine, 1987, v.1, N2, p.17-23 R.R.Jueneman. Electronic Document Authentication. Аутентификация электронных документов С ростом применения электронной передачи и хранения документов возросли требования к защите и аутентификации документов. В частности, необходимо рассмотреть методы, обеспечивающие аутентичность документов не хуже, чем обычные бумажные документы с обычной подписью, и внедрить эти методы в мир коммерции. Код аутентификации сообщений (КАС) предлагался как одно из средств подтверждения аутентичности документа между двумя доверяющими друг друг корреспондентами, и в ANSI Х9.9-1986 [1] представлен один из таких методов. КАС использует традиционные криптоалгоритмы типа DES и полагается на секретный ключ аутентификации, когда только полномочный персонал может выработать сообщение с соответствующим КАС. Метод цифровой подписи типа RSA [2] может служить и для проверки аутентичности документа, и для проверки идентичности отправителя, но из-за вычислительной сложности алгоритма RSA для цифровой подписи используют метод контрольной суммы представления документа, а затем подписывают контрольную сумму. Часто используется метод формирования КАС по DES-алгоритму. Однако при использовании КАС по стандарту X9.9 и с применением некоторых методов контрольных сумм на основе DES столкнулись с рядом трудностей. В частности, контрольные суммы должны быть длиной не менее 128 бит, за что и критиковался Х9.9. Кроме того, приведгм архитектурные соображения, говорящие в пользу алгоритма расчгта контрольной суммы, не использующего криптографию и, следовательно, секретные ключи. Коды обнаружения манипуляций (MDC-коды) - это класс алгоритмов расчгта контрольной суммы, обнаруживающих случайные и злонамеренные модификации электронного сообщения или документа без криптографического ключа. Хотя MDC-результат должен шифроваться, чтобы нарушитель не мог подставить свой MDC-результат вместе с изменгнным текстом, достаточно добавить MDC-результат к тексту и шифровать весь поток. Этот метод удобен для реализации шифрования и аутентификации сообщений на разных протокольных уровнях систем связи без трудностей с управлением ключами, а также при реализации цифровой подписи. Представлен эффективный алгоритм 128-битного MDC, использующий сопроцессор Intel 8087/80287 для IBM PC/XT/AT. Архитектурные соображения Общей темой статей [3-6] было желание разделить функции шифрования и аутентификации сообщений для их реализации на разных архитектурных уровнях систем связи. Например, для эталонной модели ВОС было предложено использовать канальное шифрование для всех связей от главной станции, применяя отдельный канальный шифратор на канальном уровне ВОС (уровень 2). В этом случае место аутентификации, вероятно, на уровне представления данных или на прикладном уровне (уровни 6 и 7) в виде прикладной программы главной станции. (Предполагается, что сеть уже предприняла попытки исправить явные ошибки данных. Если текст сообщения был изменгн так, что он прошгл механизмы исправления ошибок, но был выявлен при аутентификации, можно предполагать, что была предпринята попытка намеренного обмана. В этом случае информируется соответствующий пользователь. Если разместить функцию аутентификации ниже уровня представления данных, то будет уведомляться управляющий сетью, но не обязательно пользователь. Мы считаем, что поскольку метод шифрования может изменяться в зависимости от используемой физической среды, желательно, чтобы метод аутентификации не зависил от метода шифрования. Недавнее решение АНБ не сертифицировать новое DES-оборудование в соответствии с Федеральным стандартом 1027: 1988 и перейти к новому семейству алгоритмов шифрования информации подтверждает наше мнение о разделении функций и говорит в пользу бесключевых MDC-алгоритмов. В предыдущих статьях основной задачей являлось отыскание алгоритма аутентификации, более эффективного, чем программная реализация КАС, и не требующего шифрования. Лишь затем мы сосредоточились на основном различии между КАС и MDC - MDC использует только известные величины, поэтому более удобен с точки зрения управления ключами. Следует отметить, что между алгоритмами шифрования и аутентификации существует большое различие в отношении смены алгоритма. При шифровании тяжело обнаружить тайное нарушение трафика. А при аутентификации рано или поздно обман обнаруживается (после сведения баланса по книгам или при обнаружении ошибки при дальнейшем обмене). Цель аутентификации - снизить время обнаружения обмана. Следовательно, нет необходимости менять алгоритмы аутентификации так часто, как алгоритмы шифрования, и при их создании, возможно, не требуется такая секретность. Требования к криптографической контрольной сумме Исходя из таких архитектурных соображений, предположим, что мы хотим применить криптографическую печать в виде MDC-контрольной суммы для электронного сообщения или документа. Кроме того, мы используем метод цифровой подписи, либо канальное или сквозное шифрование для защиты MDC-результата от неслучайных нападений. Желательно, чтобы алгоритм не использовал секретной информации; при этом мы избегаем громоздкой системы управления и распределения ключей. Мы надеемся, что алгоритм будет эффективным и не использует специального криптооборудования. Но наиболее важный критерий заключается в том, чтобы множество всех контрольных сумм однозначно соответствовало множеству всех текстов сообщений; должна обеспечиваться лггкая подпись и/ проверка контрольных сумм при обработке текста по алгоритму цифровой подписи. Другими словами, контрольные суммы двух сообщений A и B идентичны, если идентичны A и B. Таким образом, алгоритмы должен обладать следующими свойствами: 1) алгоритм расчгта контрольной суммы не должен требовать никакой секретной информации при работе; хотя текст и/или контрольная сумма должны сохраняться в тайне от злоумышленника; 2) алгоритм должен эффективно выполняться и на универсальных ЭВМ и на микроЭВМ, не завися от криптооборудования; 3) контрольная сумма должна быть чувствительна ко всем перестановкам и переупорядочениям, а также редактированию, уничтожению или вставке текста, то есть сообщение ABC даст иной результат, чем ACB и т.д.; 4) вероятность того, что контрольные суммы двух различных текстов (произвольной длины) равны, должна быть равномерно распределеннной случайной переменной, независимой от текста, со средним знчением по всем возможным текстам 2**-k, где kчисло бит в контрольной сумме; 5) как будет показано ниже, итоговая контрольная сумма должна иметь длину порядка 128 бит, чтобы противостоять так называемой "атаке дня рождения"; 6) функция контрольной суммы не должна быть обратимой, а также не должна подвергаться разложению на отдельные и независимые элементы. Мы должны указать, что если КАС на основе DES можно использовать для аутентификации зашифрованных или незашифрованных текстов с последующим шифрованием, поскольку используется секретный ключ, этого нельзя сказать о MDC (использование незашифрованного КАС не рекомендуется, так как он дагт некоторую информацию о сообщении и может послужить основой для атаки "словаря"). Хотя сам текст можно не шифровать, это требуется для MDC, чтобы противник не имел возможности со значительной вероятностью успеха подставить свой MDC. В большинстве случаев можно просто добавить MDC к сообщению, и если всг сообщение шифруется вместе с MDC, то обеспечивается надгжная защита. Атаки против методов контрольных сумм В ряде статей рассматриваются различные атаки против методов контрольных сумм (см. подробности в статье Джуенмана, Матиаса и Мейера 1983 г.). Однако существует очень важная атака против самого текста сообщения или документа, не получившая должного внимания и носящая название "Атака дня рождения". Сущность "атаки дня рождения" Предположим, что пользователь "Алиса" пытается обмануть пользователя "Боба", предлагая ему ложный или неблагоприятный вариант контракта или соглашения, имеющий такую же, что и законный вариант, контрольную сумму. При этом Алиса имеет законный вариант, "подписанный" Бобом. Алиса создагт фальшивый вариант контракта и заявляет, что Боб не выполнил своих обязательств, удостоверенных его цифровой подписью. 1) для доказательства предположим, что используется некоторая 32-битная контрольная сумма, и противник обладает бесконечными аутентификационными ресурсами для выработки контрольной суммы; 2) Алиса должна предварительно и в тайне подготовить набор вариантов законного текста и рассчитать контрольную сумму для каждого из них. Предположим, например, что ряд строчек сообщения или документа электронной почты содержит последовательности ASCII-символов "пробел-пробел-возврат на 1 позицию" между выбранными словами. (Возможны и другие комбинации, такие как символ пробела или возврат каретки-перевод строки. Можно использовать и более простые варианты, например, замена "the" на "an", вставка или уничтожение запятых или пробелов в числовых полях.) Атакующий может подготовить варианты сообщения, в которых эта последовательность заменена на "пробел-возврат на 1 позицию-пробел". При этом длина текста не изменяется, и модификации не обнаруживаются при выводе на печать или на видеодисплей, за исключением дампа в 16-ричном виде. Кроме того, можно провести и более сложные изменения текста. Систематическое изменение или неизменение текста всего лишь в 16 различных строках позволяет получить 2**16=65536 вариантов. Файл записей, состоящих из контрольной суммы плюс 16-битный индекс перестановки, можно использовать для обобщения того, какие строки изменялись в данном варианте и какая при этом была контрольная сумма; 3) затем Алиса подготавливает такое же число вариантов фальшивого текста и рассчитывает для них контрольные суммы, получая другой файл контрольных сумм и индексов перестановки; 4) затем Алиса сравнивает два файла в поисках идентичных КАС или MDC, отмечая при этом соответствующие индексы перестановки (если совпадений не обнаружено, она попросту может выработать дополнительные варианты фальшивого и законного текста для получения совпадения). Затем она воссоздагт полные тексты приемлемого и неприемлемого документов с модификациями, обеспечивающими согласование контрольных сумм, на основе индексов перестановок; 5) наконец, Алиса предлагает соответствующий вариант законного текста Бобу, и оба подписывают его. Так как контрольные суммы обоих документов идентичны, будут идентичными и цифровые подписи. Следовательно, Алиса может подменить неблагоприятный контракт и попытаться на основе цифровой подписи убедить судью, что это именно тот контракт, который подписали стороны. Это классическая разновидность "атаки дня рождения", предложенная Ювалем [7], под названием "Как обмануть Рабина". В соответствии со знаменитым парадоксом статистики (а именно, сколько людей должно быть в комнате, чтобы возникла высокая вероятность того, что хотя бы у двух из них совпадала дата дня рождения) этот тип атаки обеспечивает вероятность успеха 50%, если число сгенерированных и сравнгнных вариантов каждого документа приближается к корню квадратному от общего числа возможных контрольных сумм. То есть при использовании 32-битной контрольной суммы вероятность успешной атаки составит 50% после расчгта двух файлов по 2**16 или 65536, а после этой точки быстро возрастгт. При использовании 64-битного КАС или MDC потребует 8.6 миллиардов итераций, вырабатываемых систематическим изменением 32 строк текста в каждом из двух документов (сортировка и сравнение такого количества данных не являются тривиальными, но вполне выполнимы. См. статью для КРИПТО'86).