Подмена подписанного документа в ECDSA

2002-10-25T00:00:00
ID SECURITYVULNS:DOC:3685
Type securityvulns
Reporter Securityvulns
Modified 2002-10-25T00:00:00

Description

Серьёзная ошибка в ECDSA.

В матаппарате новейшего американского стандарта ЭЦП известного как ECDSA (DSA для эллиптических кривых) [1 cтр. 25-30] существует серьёзная ошибка позволяющая выбрать такое значение секретного ключа, чтобы получить одинаковые подписи для разных документов. Это позволяет мошеннику отказаться от подписанных документов.

Описанная ошибка отличается от уже известных и сходных по смыслу DSKS (Duplicate Signature Key Selection) [1 стр. 30-32] , тем, что не требует участия злоумышленника в выборе параметров подписи (G,q и т.д.). Таким образом она доступна практически любому пользователю ЭЦП.

Подробное описание и обсуждение ошибки, контрольный пример исходники эксплойта лежат по адресам

http://bugtraq.ru/cgi-bin/forum.cgi?type=sb&b=15&m=62248

http://dom.bankir.ru/showthread.php?s=e14b7bfb775587df35c8c789e633f8cc&threadid=24299

С Уважением A.V. Komlin


Серьёзная ошибка в ECDSA.

В матаппарате новейшего американского стандарта ЭЦП известного как ECDSA (DSA для эллиптических кривых) [1 cтр. 25-30] существует серьёзная ошибка позволяющая выбрать такое значение секретного ключа, чтобы получить одинаковые подписи для разных документов. Описанная ошибка отличается от уже известных и сходных по смыслу DSKS (Duplicate Signature Key Selection) [1 стр. 30-32] , тем, что не требует участия злоумышленника в выборе параметров подписи (G,q и т.д.). Таким образом она доступна практически любому пользователю ЭЦП.

В описании сохранены обозначения принятые в стандарте.

Эта ошибка вызвана равенством x-координат противоположных точек эллиптической кривой

_x(G)==_x(-G) . (1)

Легко увидеть, что если nG=0, то (n-1)G=-G. (2)

Отсюда следует, r1= _x(kG)==r2=_x( (n-1)kG)==r (3) где k – случайный ключ подписи для простоты принимаемый за 1.

Кстати k может быть >1, это ничего не меняет, но так проще.

Описание ошибки.

Пусть нам необходимо подобрать одинаковую подпись для сообщений M1 и М2. Мы можем рассчитать личный секретный ключ d такой, что подписи для этих сообщений будут одинаковыми.

Пусть k1=1, k2=n-1, тогда r1=r2=r=x(G). (3a)

Посмотрим внимательнее на формулы подписи:

s1=k1’(e1+dr) mod n и s2=k2’(e2+dr) mod n (4a,б) где k1'k1 mod n =1 ; k1'=1 ; k2’(n-k1) mod n =1; k2'=n-1

e1=SHA(M1) mod n ; e2=SHA(M2) mod n

Отсюда очевидно, что s2=s1=s если (e1+dr) == (n-1)*(e2+dr) (mod n) (5) или e1+dr= (n-1) dr + (n-1)e2 (mod n) (5а)


2dr=(n-1)(e2+e1) (mod n) (5б)

Отсюда легко находится d:

d=z’(n-1)(e2+e1) mod n (6) где z’*(2r) mod n==1

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

Вроде я нигде не ошибся?

Исправить эту ошибку несложно. Нужно всего лишь обеспечить доказательную генерацию d. Например:выбирается случайное значение d0 Личный ключ d:=SHA-1(d0) Сохраняются оба значения. В этой схеме желаемое значение d выбрать не получится. Время генерации ключа конечно увеличиться, но ведь оно не критично в большинстве случаев. - С Уважением A.V. Komlin

Литература

Подробное описание стандарта ECDSA и основных атак на него приведено в книге 1. The Eliptic Curve Digital Signature Algorithm (ECDSA) Don Johnson (Gerticom Research), Alfred Menezes (University of Waterloo) February 24, 2000 Эта книга доступна в PDF-формате по адресу: http://rook.uinc.ru/pdf/ecdsa.zip


/** Экспойтом это назвать трудно. Скорее контрольный пример для одной из стандартных федеральных кривых Curve-192 (FIPS2) рекомендованных для стандарта ECDSA

d= 11782459554268695120436879945370321885315169609588 26812264

SHA1_1 (s,r) "I like ECDSA " 11415401785665165165164984913165161795104565165467 61214564 (3199476249460516057593544464771366849438044062282 169166762, 60204628237568865675821348058752611191669897663688 4684818)

SHA1_2 (s,r) "I do not like ECDSA " 10196894150321651651651989849498414944015631651652 65165121 (3199476249460516057593544464771366849438044062282 169166762, 60204628237568865675821348058752611191669897663688 4684818)

  • ECDSA Bug
  • @author A.V. Komlin (Kobets)
  • @version 1.0 **/

import java.math.BigInteger; import java.security.SecureRandom;

public class ecdsabug {

public static void main(String[] args) { // Curve P-192 BigInteger n=new BigInteger ("6277101735386680763835789423176059013767194773182842284081",10); BigInteger x_G=new BigInteger ("188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",16);

//x(G) BigInteger SHA1=new BigInteger ("1141540178566516516516498491316516179510456516546761214564",10); // SHA1("I like ECDSA"); BigInteger SHA2=new BigInteger ("1019689415032165165165198984949841494401563165165265165121",10); // SHA1("I don't like ECDSA");

BigInteger k=new BigInteger ("1",16);;

BigInteger One=new BigInteger ("1",16); BigInteger Two=new BigInteger ("2",16);

BigInteger n_2=n.subtract(Two); BigInteger n_1=n.subtract(One);

BigInteger e1=SHA1.mod(n); BigInteger e2=SHA2.mod(n);

BigInteger r=x_G; BigInteger z=r.multiply(Two); // z=2r BigInteger _z=z.modPow(n_2,n); // z' BigInteger tmp=e1.add(e2); // (e1+e2) BigInteger d=_z.multiply(n_1).multiply(tmp); //d=z'(n-1)(e1+e2); d=d.mod(n);

System.out.println("d: "+d.toString(10));

BigInteger k1=k; BigInteger k2=n_1.multiply(k1); // k2=(n-1)*k1 BigInteger _k1=k1.modPow(n_2,n); BigInteger _k2=k1.modPow(n_2,n);; BigInteger dr=d.multiply(r); BigInteger s1=(k1.multiply(e1.add(dr))).mod(n); // s1=k1(e1+dr) mod n BigInteger s2=(k2.multiply((e2.add(dr)))).mod(n); // s1=k1(e1+dr) mod n System.out.println("("+s1.toString(10)+",\n"+r.toString(10)+")"); System.out.println("("+s2.toString(10)+",\n"+r.toString(10)+")"); } }