ImperialViolet

Just posted on BUGTRAQ (not by me):

Contemporary world is practically impossible without systems of electronic digital signature (EDS). Every Internet user imperceptibly for himself uses them. It is these methods which ensure functionality and efficiency of contemporary banking sector. Despite this fact the EDS standards themselves are very young and are at the stage of perfection. One of the most perspective standards is ANSI X.9-62 ECDSA of 1999 - DSA for elliptic curves. In the process of adaptation all peculiarities of the operations with the elliptic curves were not taken into account to full extent and it gave an opportunity to imitate substitution of the signed document. One of the main requirements to the methods of digital signature is the impossibility to find within reasonable period of time two or more documents corresponding one signature (or vice versa). In addition to the EDS mechanism the procedure of hashing is used (in DSA it is SHA-1) which results in assigning to each document very large and unpredictable number (hereinafter referred to as hash) which is signed.

The majority of the attacks is aimed at this procedure in order to find method of receiving documents with identical hashes (or hashes which differ at given value). This work uses slightly different approach: there is made an attempt by modification of the keys chosen by the user to find such meanings of the signature so that they match two previously determined hash values. It was determined that it can be done by ordinary user of EDS scheme, if he specially chooses value for his keys: private key and per- message secret. In this case the user does not need to modify domain parameters of EDS. For the purpose of clearness below is given an illustration of the substitution of signature for approved NIST sets of parameter of federal use.

I suppose that there is no need to comment legal consequences of the existence of common signature for two documents.

Mathematical apparatus of the latest American standard of electronic digital signature know as ECDSA (DSA for elliptic curves) [1 page 25-30] contains grave mistake which makes it possible to choose value of secrete code in order to get identical signatures for various documents. The described mistake differs from the already known, having similar consequences DSKS (Duplicate Signature Key Selection) [1, page 30-32] as it does not require participation of the criminal in selection of signature parameters (G,n etc). Thus it is available for almost any EDS user and not only to EDS software engineers.

The description retains symbols adopted in the standard.

The mistake is caused by the equality of x-coordinates of the opposite points of the elliptic curve _x(G)= =_x(-G). (1)

It is easy to see that from nG=0 follows that (n-1)G=-G (2)

Thus rl = _x(kG)= = r2=-x( (n-l)kG)= = r (3)

where k - per-message secret of the signature for the purpose of simplicity taken for 1.

The development of formula for k>1 is analogous.

Let we need to select identical signature for messages M1 and M2 ( or rather for their hashes e1 and e2). We can calculate such private key d that signatures for these messages will be identical. Let k1 = 1, k2 = n-1, then r1 = r2=r_x(G) (3a)

Lets take a closer look at the formula of the signature:

• S: = k'(e+dr)(mod n)
• s1=k1'(e1+dr) mod n (4a,b)
• s2=k2'(e2+dr) mod n (4 a,b)

where

• k1'*k1 mod n = 1; k1' = 1
• k2'*(n-k1) mod n = 1; k2'= n-1
• e1 = SHA(M1); e2=SHA(M2)

This implies that s2=s1=s if (e1+dr) = = (n-1)*(e2+dr) (mod n) (5) 2dr = (n-1)(e2+e1) (mod n) (5b)

From here it is easy to find d: d = z'(n-1)(e2+e1) mod n (6)

where z'*(2r) mod n = = 1 mod n

Thus we get absolutely identical signatures (s, r) for various messages.

It is not difficult to correct this mistake. It is only necessary to provide for demonstrative generation of d.

For example, random variable Seed0 is chosen. Private key d : = SHA-1(Seed0) Both values are retained. It is impossible to select desirable value d in this scheme. Of course, the time of key generation will increase, but it is not critical in the majority of cases.

There is one more option: to send as signature not (s,r) but rather (s, R) where R=kG.

Sincerely yours,

A.V. Komlin, Russia

Detailed description of ECDSA standard and known attacks at it is given in the book The Elliptic Curve Digital Signature Algorithm (ECDSA) Don Johnson (Gerticom Research), Alfred Menezes (University of Waterloo) February 24, 2000. The book is available in PDF format at http://rook.unic.ru/pdf/ecdsa.zip.

The mentioned below page contains Java-applet allowing to calculate within several seconds in the interactive mode identical signatures and required keys for any two different messages in five standard NIST curves or in any its own

http://www.venue.ru/sign1en.htm

The applet code us not closed and one can look it through with JAD.