mailing list archives
Substitution of document signed under new American format ECDSA.
From: Alexander Komlin <avkvladru () mail ru>
Date: 28 Oct 2002 14:36:44 -0000
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)
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)
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)
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.
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
The applet code us not closed ant one can look it through with JAD.
- Substitution of document signed under new American format ECDSA. Alexander Komlin (Oct 28)