Substitution of document signed under new American format ECDSA.

[Alexander Komlin <avkvladru () mail ru>]

Introduction.

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. 

Description of the mistake

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 ant one can look it through with JAD.