ECDSA Challenge

Challenge:

The following go code implements the ECDSA signatures but it has a devastating bug. To give you a small tip an adversary by exploiting the bug can write a code snippet to enforce the API to sign two arbitrary messages with the same private signing key. In reality that can happen by having an adversary obtaining signatures on different messages by the buggy backend signature library intercepting public traffic. Using only publicly available information (signatures and public keys) you can use it to extract the secret signing key and sign messages on your own!!! Can you find it ? The main code shows an example API on how to sign messages with the underlying ECDSA lib. You homework is to print out the secret key (not by copy pasting it) and verifying it is equal to the original one.

Hints

1. Write in pensil and paper the equations in order to extract the nonce from the two signatures and then use that nonce
   $k$ to extract the secret key
   $x$ from the signature by identifying the bug in the code.
2. Apply in code the equations by issuing 2 signatures in arbitraty messages.

//based on https://arm-software.github.io/golang-utils/pkg/crypto/ecdsa.html
package main

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/rand"
	"crypto/sha256"
	"errors"
	"fmt"
	"io"
	"math/big"
)
//https://www.secg.org/sec1-v2.pdf
func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
	orderBits := c.Params().N.BitLen()
	orderBytes := (orderBits + 7) / 8
	if len(hash) > orderBytes {
		hash = hash[:orderBytes]
	}

	ret := new(big.Int).SetBytes(hash)
	excess := len(hash)*8 - orderBits
	if excess > 0 {
		ret.Rsh(ret, uint(excess))
	}
	return ret
}

func fermatInverse(k, N *big.Int) *big.Int {
	two := big.NewInt(2)
	nMinus2 := new(big.Int).Sub(N, two)
	return new(big.Int).Exp(k, nMinus2, N)
}


var errZeroParam = errors.New("zero parameter")

// PublicKey represents an ECDSA public key.
type PublicKey struct {
	elliptic.Curve
	X, Y *big.Int
}

// PrivateKey represents an ECDSA private key.
type PrivateKey struct {
	PublicKey
	D *big.Int
}

var one = new(big.Int).SetInt64(1)

func randElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
	params := c.Params()
	b := make([]byte, params.BitSize/8+8)
	b = []byte("0x6gr56")
	k = new(big.Int).SetBytes(b)
	n := new(big.Int).Sub(params.N, one)
	k.Mod(k, n)
	k.Add(k, one)
	return
}

func signGeneric(priv *ecdsa.PrivateKey, c elliptic.Curve, hash []byte) (r, s *big.Int, err error) {
	N := c.Params().N
	if N.Sign() == 0 {
		return nil, nil, errZeroParam
	}
	var k, kInv *big.Int
	for {
		for {
			k, err = randElement(c, *new(io.Reader))
			if err != nil {
				r = nil
				return
			}

			kInv = fermatInverse(k, N)

			r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
			r.Mod(r, N)
			if r.Sign() != 0 {
				break
			}
		}

		e := hashToInt(hash, c)
		s = new(big.Int).Mul(priv.D, r)
		s.Add(s, e)
		s.Mul(s, kInv)
		s.Mod(s, N) // N != 0
		if s.Sign() != 0 {
			break
		}
	}

	return
}
func main() {
	msg := "Transfer 10k"
	// pubkeyCurve := getCurve(curveType)
	m := []byte(msg)
	digest := sha256.Sum256(m)
	privatekey, _ := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
	pubkey := privatekey.PublicKey
	r, s, _ := signGeneric(privatekey, privatekey.PublicKey.Curve, digest[:])
	fmt.Printf("Message: %s\n", msg)
	fmt.Printf("Private key: %s\n", privatekey.D)
	fmt.Printf("Public key: %s,%s\n", pubkey.X, pubkey.Y)
	fmt.Printf("Signature: (r=%s s=%s\n)", r, s)
	fmt.Printf("Signature verification: %t\n\n", ecdsa.Verify(&pubkey, digest[:], r, s))

}