0
$\begingroup$

Taken from the Cryptography mailing list.

It is claimed that in ECDSA, without knowing the private key and any message signed with it, one can sign:

  1. "random garbage" (there is some complicated structure in it)
  2. $H=0$
  3. $H=r$
  4. $H=s$

The attached Sagemath code works for me. It uses the bitcoin SECP256k1 curve and public key with $x=111$ with allegedly unknown private key.

How is this done?

The attached Sagemath code:

def tesbitcoincurve1():
    """
    sage code:  http://sagemath.org, can be run in a browser in
    the cloud
    to run: %runfile file.sage

    experiments with bitcoin's SEC256k1 curve
    """
    p=  0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
    Gx= 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
    Gy= 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
    E=EllipticCurve(GF(p),[0,7]);G=E(Gx,Gy)
    n=115792089237316195423570985008687907852837564279074904382605163141518161494337
    #print n*G==0
    #public key
    QA=E(111,110020423816543951948138174357929621064214669117893252455581053961287533632517) # x=111, private key not known

    (r,s),H=(111, 111),0
    v1=ECDSA_verify(r,s,n,H,G,QA)
    print v1==r
    (r,s),H=(78357151550401202949332147590566221935398179112989344213812814774602295022407, 97074620393858699186451566299627064894117871696032124298208988958060228258372),0
    v1=ECDSA_verify(r,s,n,H,G,QA)
    print v1==r
    r,s=(105428374047743273196882821059891338511368444654956635403964917579221889109295, 110610231642529734310226903034289623182103004467015769893285040360370025301816)
    H=r
    v1=ECDSA_verify(r,s,n,H,G,QA)
    print v1==r
    r,s=(88726997827321435678026270701493246247383349479297427343226348386495743771888, 6369173660802749257382322127278165968358828480647562576685803871983831660923)
    H=s
    v1=ECDSA_verify(r,s,n,H,G,QA)
    print v1==r
    (r,s),H=(105238699896951558262377011680716928670929106668167672998668678863061090326385, 102286764830003424766749795690788297189374412259121264591707039647964876795035),6206150873392997599270790826086018442478461413119740184175413055321497803859
    v1=ECDSA_verify(r,s,n,H,G,QA)
    print v1==r


def ECDSA_verify(r,s,n,H,G,QA):
    K=Integers(n)
    w=K(s)**(-1)
    u1=H*w
    u2=r*w
    u1,u2=lift(u1),lift(u2)
    x1,y1=(u1*G+u2*QA).xy()
    x1=lift(x1)
    #valid if r==x1
    return x1

tesbitcoincurve1()
$\endgroup$
  • 1
    $\begingroup$ Since the answer is obvious to me (read; “trivial”) I’m not sure I grasp what kind of answer you might be looking for. Could you please clarify what exactly you’re asking? One way to do so is to tell us what research you did, what you found, and why it didn’t meet your needs. That shows users you took time trying to help yourself, it clarifies the question, it saves us from reiterating obvious answers, and (most important) it helps you to get more relevant answers $\endgroup$ – e-sushi Mar 7 '17 at 13:24
  • $\begingroup$ @e-sushi I can't solve without any signature. Are my failures of interest to you? $\endgroup$ – joro Mar 7 '17 at 13:40
3
$\begingroup$

An ECDSA signature works the following way:

  • We work in a sub-group of a curve. The generator is $G$ and it has order $q$ (a prime number). With most curves, $G$ actually generates the whole curve.
  • Private key is $x$, and corresponding public key is $Q = xG$.
  • To sign a message $m$:

    1. Hash message $m$, with result being truncated/reduced modulo $q$: $h = H(m)$.
    2. Generate a random $k$ modulo $q$ (or a non-random one, if using deterministic ECDSA).
    3. Compute the point $kG$ and get its $X$ coordinate. The first half of the signature is $r = X \pmod q$.
    4. Second half of the signature is $s = (h+xr)/k \pmod q$.
  • To verify a signature:

    1. Hash message $m$ again, to get $h$.
    2. Compute $w = 1/s \pmod q$.
    3. Compute point $whG + wrQ$ and check that its $X$ coordinate, when reduced modulo $q$, yields $r$. Indeed, if the signature was properly computed, this expression recomputes the point $kG$ that was produced during signature generation.

There is no known forgery attack on ECDSA when expressed as above. The email you quote implicitly considers the case of ECDSA without the hash function. Or, said otherwise, whether one can make a forged value with $h$ considered as "message input".

For instance, take the point $Q$ (the public key) and extract its $X$ coordinate; call that $r$. Then set $s = r$. The $(r,s)$ pair is a valid signature for a message $m$ such that $h = H(m) = 0 \pmod q$. Indeed, it fulfills the verification equations: $w$ will be equal to $1/r \pmod q$, so $wrQ$ will yield simply $Q$, and since $h = 0$, then the $whG$ component will simply vanish. So the verifier will end up with point $Q$, whose $X$ coordinate indeed yields the $r$ value from the alleged signature.

Now this is not a true forgery in that you get a value which is a valid signature for a message that you do not know: the signature is valid for message $m$ which is such that $H(m) = 0 \pmod q$. But good luck with finding a matching $m$...

None of this is new, but it highlights the important role of the hash function in the process: ultimately, the preimage resistance of the hash function is crucial for resistance against forgeries.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.