kiev-security.org.ua-Криптография.Проблемы безопасности в системах обработки информации. Протоколы криптосистем

A.F.Ronzhin. Problems of Security in Information Processing Systems//В сб.: Организация безопасной связи должна удовлетворять определенным строгим правилам, которые регулируются протоколами. Для различных типов безопасной связи требуются разные протоколы. Мы не имеем возможности перечислить все типы безопасной связи и привести хотя бы краткое описание соответствующих протоколов. Ограничимся некоторыми примерами протоколов аутентификации и цифровой подписи. 4.1. Задачи аутентификации Аутентификация - это процесс, используемый для подтверждения подлинности (аутентичности) кого-либо или чего-либо. Криптографические методы обеспечивают высший уровень аутентификации сообщений, данных, ключей и устройств. Все методы аутентификации имеют общую часть, в которой проверяется аутентичность одного или нескольких параметров. Федеральный стандарт США (Federal Standard 1026, 1978) определяет аутентификацию как процесс, гарантирующий инвариантность данных частей или позиций, либо подтверждающий аутентичность данного информационного блока. Необходимо отличать параметры аутентификации и процесс аутентификации от цифровых подписей. В процессе аутентификации не требуется доказывать третьей стороне, что информация была послана этим отправителем и не была создана получателем. Однако требуется, чтобы получатель был уверен в том, что информация была послана именно данным отправителем. Криптографические алгоритмы, используемые для аутентификации, должны удовлетворять следубщим условиям. 1. Они должны быть надежными в том смысле, что ключ шифрования не может быть найден на основе соответствующих открытого и зашифрованного текстов. 2. Ключи криптосистемы должны быть защищены. Очевидно, что эти условия выполняются при использовании классических алгоритмов, алгоритмов с открытыми ключами и процедур, основанных на односторонних функций (Evans et al., 1974; Purdy, 1974; Westin, 1968). Рассмотрим три случая, когда аутентификация играет важную роль. В первом случае это подтверждение установления связи между двумя санкционированными пользователями системы. Процедура называется рукопожатием. Второй случай - это аутентификация сообщения, которая должна подтвердить получателю аутентичность отправителя сообщения, содержимого сообщения, порядка сообщений (т.е. получатель должен быть уверен, что он принял сообщения в том порядке, в котором они отправлялись), адреса сообщения (т.е. пользователь должен быть уверен, что сообщение передано в том направлении, в котором оно посылалось). В третьем случае проверяется аутентичность тех системных данных, которые должны быть постоянными в течение некоторого периода времени (например, ключи, идентификаторы пользователя и т.п.). В качестве примера опишем протокол рукопожатия. 4.2. Протокол рукопожатия Рассмотрим процедуру, позволяющую пользователю А проверить аутентичность пользователя В. Очевидно, что обратная процедура позволяет пользователю В проверить аутентичность пользователя А. Пользователь А вырабатывает псевдослучайное число N, которое шифруется с помощью сеансового ключа k и посылается пользователю В. Пользователь В дешифрует его и вычисляет некоторую открытую (несекретную) функцию y(N). Затем значение y(N) шифруется и посылается пользователю А. Пользователь А дешифрует принятое значение и сравнивает его с y(N). Равенство подтверждает аутентичность пользователя В. Этот метод делает невозможной "ночную атаку" злоумышленника, поскольку при следующем сеансе терминал вырабатывает другое псевдослучайное число N, и злоумышленник не может дать правильный ответ на запрос системы, так как он знает только значение E(k , N). Иногда в качестве функции Y используется инверсия некоторых битов в двоичной записи числа N. Важно, чтобы N генерировалось терминалом A в защищенной памяти, и, более того, оператор не должен иметь возможности ввода N. В противном случае злоумышленник может действовать следующим образом. Он устанавливает на терминале y(N') вместо N', получает E(k , y(N')), шифрует его и посылает пользователю B вместо E(k ,N'). Таким образом, в памяти пользователя теперь находится E(k ,y(N')) вместо истинной записи E(k ,y(N)). Затем злоумышленник посылает N' пользователю В и успешно проходит проверку на аутентичность. Для предотвращения таких типов нападений можно использовать некоторое число R , хранимое в защищенной памяти, вместо случайно генерируемого N. Для проверки аутентичности связи А шифрует число R на ключе k , т.е. берет E(k ,R ). Злоумышленник может ввести N' и получить E(k ,N'). Поскольку y - это открытая функция, можно получить y(E(k ,N')). Также можно получить y(E(k ,y(k ,N'))). Он может заменить E(k ,y(E(k ,E(k R )))) на E(k ,y(E(k ,N'))), но он не может заменить N на N'. 4.3. Цифровые (электронные) подписи В соответствии с единым торговым кодексом (Uniform Commercial Code, 1972) и законами США такими, как Закон о подписи и Закон об учреждениях (Corley and Robert, 1971), подпись на документе должна гарантировать то, что документ, обговаривающий обязательства сторон, действительно подписан данным лицом в данное время. С этой целью в процесс вовлекается третья сторона (арбитр, нотариус и т.п.). У (Lipton and Matyas, 1978) юридические положения адаптированы для электронной почты. Цифровая подпись должна быть такой, чтобы получатель мог доказать аутентичность сообщения третьей стороне и отправителю. Цифровая подпись является функцией подписываемого сообщения, протокола или документа и конфиденциальной информации, известной только отправителю, а также, возможно, открытой информации. Передача подписанного сообщения от А к В может осуществляться, если они имеют соответствующие возможности. А должен иметь информацию для создания подписи для каждого сообщения, а В должен иметь информацию для проверки аутентичности сообщения и авторства А. Отправитель А может потребовать подтверждение факта приема сообщения. Существует несколько криптосистем, позволяющих реализовать цифровые подписи на базе симметричных алгоритмов и алгоритмов с открытым ключом. Цифровые подписи, используемые в системах, где каждое лицо, допущенное к системной услуге, может проверить аутентичность отправителя и сообщения, называют универсальными. Их легко построить, используя алгоритмы с открытым ключом. Универсальные подписи можно создать и на сонове симметричных алгоритмов. В этом случае требуется передача дополнительной конфиденциальной или открытой информации для каждого сообщения. Также представляют интерес методы построения цифровых подписей на базе симметричных алгоритмов, обеспечивающие свойства алгоритмов с открытым ключом. Другим подходом к созданию цифровых подписей является вовлечение в процесс связи третьей стороны, играющей роль инспектора. 4.4. Протоколы универсальных подписей Применение универсальных подписей позволяет получателю проверить аутентичность подписи и сообщения независимо от других лиц. Третья сторона может вовлекаться в процесс только для разрешения спорных моментов. Рассмотрим более подробно некоторые протоколы. 4.5. Применение алгоритма с открытым ключом Данный класс алгоритмов описан в (Cryptographic Algorithms, 1973; Hellman et al., 1976; Shamir, 1978). Пусть К будет ключом для шифрования сообщений i-ым пользователем, и пусть К будет ключом для дешифрования сообщений, принимаемых j-ым пользователем. Затем в зависимости от секретности ключей возможны следующие типы систем связи: а) К - открытый, К - секретный. В этом случае система связи обеспечивает секретность передаваемой информации. Любой пользователь, применяющий открытый ключ, может передать сообщение, а соответствующий получатель может только дешифровать его; б) К - секретный, К - открытый. В этом случае аналогичная система связи не обеспечивает секретность передаваемой информации. Любой пользователь может дешифровать сообщение, и, следовательно, проверить, что информация была послана i-ым пользователем, так как i-ый пользователь может шифровать только на К ; в) К и К секретные, а К и К открытые. Алгоритм удовлетворяет условию D(K ,E(K ,X)) = E(K ,D(K ,X)) = X (3) для всех Х или подмножества всех сообщений (Hellman et al., 1976). Система обеспечивает секретность передаваемых сообщений и доказательство аутентичности подписи. Общая схема передачи подписанного сообщения строится на основе файла, доступного каждому лицу и содержащего идентификаторы пользователей (числа 1, 2,...) и их ключи шифрования К , К ,... Каждый пользователь имеет секретный ключ дешифрования К , К ,.. Кроме этого, условие (3) выполняется для каждой пары ключей К , К и не действует почти для всех Х, если К =К , К =К . Несмотря на тот факт, что открытый файл не содержит никакой секретной информации, его необходимо защищать от разрушения другими системами. Пусть все сообщения имеют вид М=<идентификатор отправителя><идентификатор получателя> <последовательность чисел><данные>. Для передачи сообщения Mn(i,j,n,X) от i к j необходимо выполнить следующие процедуры: 1. Пользователь i дешифрует сообщение Mn на секретном ключе K . 2. Пользователь i шифрует его на открытом ключе К и после этого передает j сообщение вида E(K ,D(K ,X)). 3. Пользователь j дешифрует сообщение на секретном ключе K и шифрует его на открытом ключе К , получая сообщение Mn. Величину D(K ,X) после проверки сообщения Mn можно использовать как доказательство того, что сообщение Mn было послано пользователем i. Поскольку величина К известна только пользователю i, никто не мог создать сообщение. Пусть часть сообщения Mn, включающая Qn=<идентификатор отправителя><идентификатор получателя> <последовательность чисел>, содержит r бит. Тогда вероятность правильного дешифрования D(K , Mn) на произвольном ключе, отличном от К , равна 2^(-r). Это позволяет выполнить аутентификацию Mn путем проверки значения Qn. В данном случае D(K ,Mn) зависит и от сообщения и от секретного ключа отправителя и может быть рассчитано только отправителем. Кроме того, D(K ,Mn) можно рассматривать как подпись, поскольку аутентичность сообщения определяется по параметрам Qn, которые доступны всем. Несмотря на тот факт, что симметричные блочные алгоритмы существенно отличаются от алгоритмов с открытым ключом с точки зрения шифрующих и дешифрующих преобразований, основанные на них криптосистемы, включая управление ключами, можно построить таким образом, что описанный выше протокол не претерпит изменений. Подробное описание метода взаимодействия двух пользователей, либо пользователя и системы можно найти в (Zennon et al., 1980, 1982). Коротко опишем идею. Пусть К - секретный ключ, и пусть определены следующие ключи: К = E(K ,K), K = E(K ,K). В данном случае K , i=1,2, - это варианты главного ключа. Кроме того, имеются два типа криптографических операций - только шифрование данных (ENCO) и только дешифрование данных (DECO): ENCO{K ,X} -- E(D ,K ,X) и DECO{K ,Y} -- D(D ,K ,Y) соответственно. В этом случае для всех Х имеем DECO{K ,ENCO{K ,X}} = X, и K = K для всех K. Следует отметить, что знание K не дает возможности восстановить K благодаря стойкости самого блочного алгоритма. Если положить, что К открытый, а К секретный, то получим все свойства алгоритмов с открытым ключом. При обеспечении защиты главного ключа системы и ключа К обеспечивается стойкость системы. Для выработки ключей К и К используется операция GENKEY, которая не имеет входных значений (она берет псевдослучайные числа RN от своего внутреннего генератора) и имеет два выхода: GENKEY -- (E(K ,RN),E(K ,RN)). 4.6. Метод Диффи-Лампорта Метод основан на симметричном блочном алгоритме (Chaum, 1979). Пусть требуется подтверждение подписей n-битного сообщения. Отправитель заранее вырабатывает n пар ключей криптоалгоритма: (К , К ), i = 1,...,n, которые хранятся в тайне, и предоставляет получателю две последовательности для проверки аутентичности: (U , U ), (V , V ), i = 1,...,n, где V = E(K , U ), l = 1,2, i = 1,...,n. Отправитель записывает последовательности, а получатель хранит их в несекретном файле, имеющем дополнительную защиту от разрушения. По окончании описанного процесса выполняется следующая процедура передачи подписанного сообщения. Отправитель передает сообщение M = m(1)...m(n) вместе с ключами К ; сравнение результата с V , i = 1,...,n, позволяет сделать вывод об аутентичности сообщения и отправителя, так как никто не знает ключей К и К , i = 1,...,n. Поскольку ключи неизвестны и получателю, тот не может сформировать фальшивое сообщение. Процедура имеет существенный недостаток. Требуется передавать и хранить большой объем информации, пропорциональный длине передаваемого сообщения. Один из методов смягчения этого недостатка - использование методов сжатия. Код сжатия (С ) - это функция, которая отображает двоичные последовательности переменной длины в битовые последовательности фиксированной длины m. Код сжатия и величина m выбираются таким образом, чтобы вычисление М и М', для которых справедливо С (М) = С(М'), было чрезвычайно сложным. Один из способов построения функции С с помощью симметричного алгоритма заключается в следующем. Выбираются два несекретных ключа К и К . Для сообщения Х, состоящего из блоков Х ,...,Х , вычисляются два значения U и U по следующим правилам: Y = E(K , X + Y ), Y = 0, i = 1,...,n, U = E(K , X +...+ X + Y ), r = 1,2, после чего полагаем, что C (M) = (U , U ). 4.7. Метод Рабина Метод описан в (Rabin, 1978). Отправитель вырабатывает 2r криптографических ключей К ,..., K , которые хранятся в секрете. Ключи используются для выработки параметров U ,..., U и E(K ,U ),..., E(K , U ), позволяющих установить аутентичность. Эти параметры посылаются получателю и хранятся получателем и отправителем в файлах, имеющих дополнительную защиту от разрушения. Цифровая подпись сообщения М формируется следующим образом. Находится сжатие сообщения вида C (M), которое шифруется на всех ключах сообщения. Итоговая подпись E(K , C (M)),..., E(K , C (M)) (4) передается получателю. Процедура проверки аутентичности заключается в следующем. Отправитель раскрывает получателю половину ключей, а другую половину хранит в тайне, чтобы предотвратить фальсификацию сообщения получателем. r требуемых ключей выбираются с участием получателя. Он либо производит случайную выборку объема r без заемены из множества 2r элементов, либо вырабатывает случайный двоичный вектор длины 2r, содержащий ровно r единиц. Единица в i-ой позиции означает выбор ключа К . Выбранные ключи передаются получателю, который проверяет, совпадают ли значения параметров U и C (M), зашифрованные на ключах, со значениями E(K ,U ) и E(K ,C (M)) соответственно. Если получатель пытается приписать отправителю фальшивое сообщение, то отправитель показывает все ключи К ,..., К третьей стороне, которая проверяет соответствие всех параметров. Если совпадает более r элементов подписи (4), сообщение приписывается отправителю. В противном случае оно считается поддельным. Для формирования фальшивого сообщения отправитель должен определить ровно r параметров. Поскольку ключи запрашиваются получателем, отправитель может правильно угадать положения параметров с вероятностью (r!)^2/(2r)!. 4.8. Метод Матиаса и Мейера Данный метод (Matyas and Meyer, 1981a, 1981b) требует построения исходных таблиц параметров. Первая таблица размера 31х31 состоит из секретных ключей K(i,j), а вторая таблица размера 30х31 состоит из кодовых слов U(i,j), являющихся несекретными параметрами для проверки аутентичности. Эти таблицы можно, например, построить следующим образом. Предположим имеется секретный ключ К и открытый параметр U. Тогда для n-ного сообщения построим первую таблицу с элементами U(i,j) = E(31^2(n-1) + 31(j-1) + j), K(1,j) = E(K, 31(n-1) + j), K(i + 1,j) = E(K(i,j), U9i,j)), i = 1,...,30, j = 1,...,31. Ключи из 31 строки ключевой таблицы называют конечными; они передаются получателю заранее. Получатель може потребовать доказательства их аутентичности путем помещения в общедоступный список. Кроме того, необходимо иметь 31 несекретный ключ К ,...,К , которые помещаются в общедоступный список. Затем для каждого сообщения М вычисляется код сжатия C (M) и тридцать одно кодовое слово С = E(K ,C (M)),...,C = E(K ,C (M)). Кодовые слова С ,...,C упорядочиваются в возрастающем порядке в строку С ,...,C , а номера ключей цифровой подписи образуются строками как ключис номерами (i(1),1),...,(i(31),31) соответственно. Ключи, находящиеся в этих позициях, передаются получателю, который выполняет за исключением одного шага те же шаги, что и отправитель. Получатель вычисляет код сжатия сообщения М. Затем он вычисляет и сортирует кодовые слова, проверяет номера полученных ключей; затем с помощью этих ключей и таблицы кодовых слов восстанавливает 31 строку ключевой матрицы. На последнем шаге он проверяет соответствие восстановленных ключей и матрицы кодовых слов. Как видно, протоколы, основанные на симметричных алгоритмах, являются одноразовыми и требуют смены хотя бы одного параметра для каждого нового сообщения. В то же время алгоритмы с открытым ключом позволяют использовать один параметр - открытый ключ отправителя - для всех подписываемых сообщений. В заключение следует отметить, что обзор в основном посвящен криптографии. Рамки статьи не позволяют рассмотреть результаты другой части криптологии - криптоанализа. Надеюсь, что представленная в обзоре информация дает начальное понятие об этой замечательной области прикладной математики, выдвигающей целый ряд чисто математических проблем.