О двуличии в алгоритмах цифровой подписи

О “двуличии” в алгоритмах цифровой подписи

БЕЗОПАСНОСТЬ

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

Хрестоматийный пример - использование одного и того же ключа одновременно в схеме шифрования RSA и в схеме подписи RSA. В этом случае просьба “друга” расшифровать якобы предназначенное для вас зашифрованное сообщение может оказаться попыткой подписать некоторый хэш-код некоторых данных. Возвращая бессмысленный набор кодов расшифрованного сообщения, вы отдаете подпись, изготовленную с помощью вашего личного (секретного) ключа. Опасность другого рода возможна в случае одновременной работы субъекта с несколькими активными ключами подписи, или своего рода “двуличия”.

Ситуация в общих чертах такова. Предварительно некто регистрирует два активных открытых ключа проверки подписи y и y, соответствующие личным (секретным) ключам подписи x и x. С помощью первого ключа x он подписывает документ m, а с помощью x - m. Причем ключи x и x выбраны таким образом, что подписи c и c на документах m и m совпадают. После этого подписанный документ вместе с подписью (m, c) отсылается адресату, который с успехом проверяет подпись c ключом проверки y и верит ему. А автор при попытке предъявить ему претензию показывает в качестве “истинного” подписанного им документа (m, c) и отказывается от m. При этом все претензии адресуются авторам реализации схемы подписи, поскольку именно они “виноваты” в том, что есть возможность использовать перехваченную подпись в качестве корректной подписи другого документа.

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

H - криптографическая хэш-функция;

Z - множество чисел {0,1, +, n - 1}, n - натуральное число; a (mod p) - остаток от деления целого числа a на натуральное число p; a  b(mod n) означает, что целые числа a и b сравнимы по модулю n, т. е. имеют одинаковые остатки при делении на натуральное число n.

1. Схема подписи Эль-Гамаля

Сначала опишем алгоритм формирования подписи эль-Гамаля *1:

- фиксируется простое число p достаточной разрядности и g-примитивный элемент mod p;

- личным ключом подписи является любое число x  Z;

Затем опишем алгоритм вычисления подписи сообщения m:

- вычисляется хэш-код h = H(m);

- выбирается случайное число k, взаимно простое с p - 1: 1 < k < p - 1;

- вычисляется r = g(mod p);

- вычисляется s = k(h - xr)(mod p - 1);

- подписью является пара c = (r, s).

_____

*1. ElGamal T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. - IEEE Trans. on Inf. Theory, 1985, v. IT-31, № 4, p. 469-472.

Теперь рассмотрим, что нужно делать злоумышленнику для реализации атаки, описанной выше. Исходя из приведенных описаний, он должен сгенерировать хэш-коды h = H(m), h = H(m) и совпадающие подписи с одинаковым случайным числом k:

s = k(h - xr)(mod p - 1)

и s = k(h - xr)(mod p - 1)

А это значит, что

h - xr  h - xr(mod p - 1)

             (1)

Как видно, при таком выборе ключей x и x подписи совпадают.

2. DSA и ECDSA

Теперь понятно, что аналогичным образом можно построить желаемую коллизию и для алгоритмов, близких к схеме эль-Гамаля:

- алгоритма подписи американского стандарта DSA и его развития ECDSA;

- алгоритма подписи российского стандарта ГОСТ Р 34.10-94 и его развития ГОСТ Р 34.10-01.

Без лишних деталей напомним подготовительные шаги и алгоритм формирования подписи DSA:

- выбираются простые числа p и q так, что p - 1 делится на q;

- выбирается число g - элемент порядка q в мультипликативной группе Z;

- в качестве личного ключа подписи используется число x: 1 < x < q;

Алгоритм вычисления подписи сообщения m таков:

- вычисляется хэш-код h = H(m);

- выбирается случайное число k: 1 < k < q;

- вычисляется r = g(mod p)(mod q);

- вычисляется s = k(h + xr)(mod q);

- подписью является пара c = (r, s).

Опять, как и выше, для совпадения подписей двух хэш-кодов h и h на ключах x и x необходимо, чтобы выполнялись равенства

s = k(h + xr)(mod q)

и s = k(h + xr)(mod q)

Откуда получаем требуемое условие на x и x

          (2)

Что же касается алгоритма подписи ECDSA, то он принципиально не отличается от DSA в плане рассматриваемой уязвимости. Здесь вместо арифметики в мультипликативной группе поля Z используется арифметика в группе точек некоторой эллиптической кривой E над полем Z, и в качестве r при вычислении подписи используется x-координата точки kP, где P - точка порядка q на кривой E. При этом приведенная выше формула (2) зависимости ключей x и x остается в силе.

3. ГОСТ Р 34.10-94 и ГОСТ Р 34.10-01

Параметры и асимметричный криптографический алгоритм формирования подписи ГОСТ Р 34.10-94 в общих чертах выглядят следующим образом:

- выбираются простые числа p и q: p - 1 делится на q;

- выбирается число g - элемент порядка q в Z;

- в качестве личного ключа подписи используется число x: 0 < x < q;

Алгоритм вычисления подписи сообщения m следующий:

- вычисляется хэш-код h = H(m);

- выбирается случайное число k: 0 < k < q;

- вычисляется r = g(mod p)(mod q);

- вычисляется s = (kh + xr)(mod q);

- подписью является пара c = (r, s).

Опять же отличие ГОСТ Р 34.10-01 от ГОСТ Р 34.10-94 только в том, что вместо арифметики поля Z используется арифметика группы точек эллиптической кривой над полем Z. Для наших целей это непринципиально. Все ниже приведенные выкладки проходят и там, причем без малейших изменений.

Итак, для того чтобы подписи сообщений m и m совпадали, необходимо потребовать выполнения равенств

s = (kh + xr)(mod q)

и s = (kh + xr)(mod q)

Откуда

sh - sh  xrh - xrh(mod q)

xrh  xrh + s(h - h)(mod q)

              (3)

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

RSA

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

- выбирается модуль n, представляющий собой произведение двух различных простых чисел p и q примерно равной разрядности, сохраняемых в секрете;

- в качестве ключа подписи выбирается натуральное число x  Z, взаимно простое с (p - 1)(q - 1);

- подпись c сообщения m вычисляется следующим образом:

- вычисляется хэш-код h = H(m);

- c = hx(mod n).

_____

*1. Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signature and public-key cryptosystems. Commun. ACM, 1978, v. 21, № 2.

Для того чтобы подписи сообщений m и m на ключах x и x соответственно совпадали, необходимо выполнение сравнения:

Откуда, возведя в степень x, получим

Теперь, для того чтобы найти требуемое значение x, необходимо решить задачу дискретного логарифмирования по основанию h в кольце Z, а точнее, вычислить такое число u  Z, чтобы

                (4)

Тогда

xx  u(mod(p - 1)(q - 1))

x  ux(mod(p - 1)(q - 1))

Дискретное логарифмирование в кольце Z выполняется следующим классическим образом. Поскольку n = pq, то, перейдя в (4) к модулю p и модулю q, получим систему сравнений:

                          (5)

Решив каждое из них, получим два числа: u - решение первого сравнения, u - второго. Теперь, воспользовавшись китайской теоремой об остатках, можно построить u: u  u[mod(p - 1)] и u  u[mod(q - 1)]. Это число u и есть решение сравнения (4).

Что касается решения сравнений (5), то это проще задачи разложения на простые множители числа n. Приходится решать задачу дискретного логарифмирования в полях Z и Z. Но поскольку числа p и q имеют разрядность примерно в два раза меньше разрядности числа n, то сложность решения этих задач есть примерно квадратный корень из сложности факторизации числа n.

Что делать?

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

- запретить использование более одного активного ключа цифровой подписи одновременно;

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

Простого именования подписавшего субъекта в формате подписанного сообщения недостаточно, если ему (субъекту) не запрещено использовать более одного активного ключа подписи. Впрочем, зачастую и этого не делается.

Надо отметить, что большинство современных коммерческих систем криптографической защиты информации следуют этим правилам. Они автоматизированно или организационно обеспечивают активность не более одного ключа либо используют формат подписанных данных PKCS#7 вместе с системой сертификации открытых ключей стандарта X.509, что при грамотной реализации достаточно для успешного противостояния рассмотренной нами атаке “двуличия” в алгоритмах цифровой подписи.

С автором можно связаться по адресу: gr@crystall.tl.ru.