The State of TLS … ECDSA Nonce Reuse

The State of TLS … ECDSA Nonce Reuse

Satoshi Nakamoto selected ECDSA for Bitcoin transactions, and the rest is history. Ethereum has since adopted it too. But, it has weaknesses, and one of the core weaknesses is that we should NOT reuse the same nonce value.

The signature is:

and where the random nonce value is k. If the same value is used, it is possible to derive the private key (priv). A new paper [1] now shines a light on the current state of the usage of TLS, and where the research team analysed 5.8 billion TLS handshakes from two different university networks:

Unfortunately they found many connections that used nonce reuse:

Nonce reuse

In ECDSA, Bob creates a random private key (priv), and then a public key from:

Next, in order to create a signature for a message of M, he creates a random number (k) and generates the signature of:

The signature is then (r,s) and where r is the x-co-ordinate of the point kG. H(M) is the SHA-256 hash of the message (M), and converted into an integer value. Now let’s say we have two messages (m_1 and m_2) and have hashes of:

Now let’s say that Alice signs the messages with the same private key (priv) and the same nonce (k, we can then recover the private key with:

We can also recover the nonce with:

Here is some code which does a discovery of the private key, and the nonce (k) if we use the same nonce value [here]:

import ecdsa
import random
import libnum
import hashlib
import sys

G = ecdsa.SECP256k1.generator
order = G.order()

priv1 = random.randrange(1,order)
 
Public_key = ecdsa.ecdsa.Public_key(G, G * priv1)
x1 = ecdsa.ecdsa.Private_key(Public_key, priv1)

k = random.randrange(1, 2**127)

msg1="Hello"
msg2="Hello1"

if (len(sys.argv)>1):
	msg1=(sys.argv[1])
if (len(sys.argv)>2):
	msg2=(sys.argv[2])

h1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16)
h2 = int(hashlib.sha256(msg2.encode()).hexdigest(),base=16)
 
sig1 = x1.sign(h1, k)
sig2 = x1.sign(h2, k)

r1,s1 = sig1.r,sig1.s
r2,s2 = sig2.r,sig2.s

valinv = libnum.invmod( r1*(s1-s2),order)

x1rec = (   (s2*h1-s1*h2) * (valinv)) % order

print ("Message 1: ",msg1)
print (f"Signature r={r1}, s={s1}")
print ("\nMessage 2: ",msg2)
print (f"Signature r={r2}, s={s2}")

print ("\nPrivate key",priv1)
print ("\nPrivate recovered ",x1rec)

valinv = libnum.invmod( (s1-s2),order)

k1rec = (   (h1-h2) * valinv) % order

print ("\nK: ",k)
print ("\nK recovered ",k1rec)

A sample run is [here]:

Message 1:  hello
Signature r=16163824871702315365636544754327339671279830383115616072776286071644348532176, s=78942102071383249892109282228339664393041099900407940222266026023142592864884

Message 2:  hello1
Signature r=16163824871702315365636544754327339671279830383115616072776286071644348532176, s=83502523167965149244641473202679268630845178075816922294718909855670078364206

Private key 6542179820561127199468453109220159836323733777364616770035873205004743487369

Private recovered  6542179820561127199468453109220159836323733777364616770035873205004743487369

K:  109308891778201478280270581205739604663

K recovered  109308891778201478280270581205739604663

Conclusions

TLS is a mess. There are so many problems, of which a few will be solved by moving to TLS 1.3.

References

[1] Sullivan, G. A., Sippe, J., Heninger, N., & Wustrow, E. (2022). Open to a fault: On the passive compromise of {TLS} keys via transient errors. In 31st USENIX Security Symposium (USENIX Security 22) (pp. 233–250).

[2] Brengel, M., & Rossow, C. (2018, September). Identifying key leakage of bitcoin users. In International Symposium on Research in Attacks, Intrusions, and Defenses (pp. 623–643). Springer, Cham [here].