CTF: Cracking a Faulty Signature

Do you have a cybersecurity mind? Well, one of the key skills is the ability to solve complex problems. One way to do this, is to undertake…

CTF: Cracking a Faulty Signature

Do you have a cybersecurity mind? Well, one of the key skills is the ability to solve complex problems. One way to do this, is to undertake a CTF (Capture The Flag) exercise.

Here’s a challenge for you …

Bob creates a signature for a message to Alice, but there is a fault in the creation of the signature. The message is “hello” and the signature is 33561470437852350800490296761035292196715158781566678427933645057899269717707506647931331164413297433452052757522476505043933758201648524587067912327069386833529595693294784445885069514609509940138677177002837616414260865324998574585955604784961293369461236228238076243170840123022488381745254995816247017490. Bob’s public key modulus is 94136336122929214497645947944239488252265637517769497863995725490749118151338146906097108857799005345920509263235470705894384169684628344131600231570414799978836997446701647934689166024214620156488862336056183901241288511987984235432767088697131078894390476645020437264124880061155505393367858836280160054199. Can you discover Bob’s private key?

[Ans: p = 898…, q = 104..]

Now, let’s crack it.

RSA signature fault

In a brilliant paper published at USENIX 2022, Sullivan et al [1] show that real-life RSA signatures can be cracked for their private key — if the signature contains a fault. This fault method has been known for a while, and it was Lenstra [2] and Bohen et al [3] who outlined the methods used to recover the prime numbers (p and q) used in RSA. Once these are revealed, it is then trivial to generate the private key:

It basically focuses on a fault occurring in the generation of the RSA-CRT (Chinese Remainder Theory).

With RSA, we create two random prime numbers (p and q), and determine the modulus:

We create a signature of a message with:

and where (e,N) is the encryption key, and (d,N) is the decryption key. In order to create the signature we can apply CRT (Chinese Remainder Theory) to solve:

For this we use CRT to solve for M in:

and also use Fermat’s Little Theorem:

For this we need:

and which is the inverse of e(modp−1). Also:

and:

The signature is then created using less complex operations of:

This operation can be up to four times faster than performing S=Md(modN).

Fault

The implementation of the code above is:

e=65537
dP = 1 * pow(e,-1,p-1)
dQ= 1 * pow(e,-1,q-1)
qInv= 1 * pow(q,-1,p)
s1 = pow(m,dP,p)
s2 = pow(m,dQ,q)
h = (qInv*(s1 - s2)) % p
s= s2 + h*q

But now let’s introduce an fault in s1 or s2, and which will then produce an incorrect signature (s). If we do it on s2 then:

e=65537
dP = 1 * pow(e,-1,p-1)
dQ= 1 * pow(e,-1,q-1)
qInv= 1 * pow(q,-1,p)
s1 = pow(m,dP,p)
s2 = pow(m,dQ,q)+1 
h = (qInv*(s1 - s2)) % p
s= s2 + h*q

Notice that s2 has one added to it. We can first recover p with:

and where GCD is the greatest common denominator. This will work, as p is correct, and will still share a factor in the faulty signature. To determine q, we can simply divide N by the recovered p value. We can then recover p and q using:

p_rec=libnum.gcd(pow(s,e,N)-m,N)
q_rec = N//p_rec

The coding is [here]:


from Crypto.Util.number import *
from Crypto import Random
import Crypto
import sys
import libnum

msg="Hello"
bits=256

if (len(sys.argv)>1):
    msg=str(sys.argv[1])
if (len(sys.argv)>2):
    bits=int(sys.argv[2])

m=  bytes_to_long(msg.encode())

p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)

N=p*q
e=65537

dP =pow(e,-1,p-1)
dQ= pow(e,-1,q-1)
qInv= pow(q,-1,p)

s1 = pow(m,dP,p)
s2 = pow(m,dQ,q)+1 # Add an error
h = (qInv*(s1 - s2)) % p
s= s2 + h*q

print(f"Bob creates a signature for a message to Alice, but there is a fault in the creation of the signature. The message is {m} and the signature is {s}. Bob's public key modulus is {N}. Can you discover Bob's private key?")


print("\n\n=== Answers ===")

p_rec=libnum.gcd(pow(s,e,N)-m,N)
q_rec = N//p_rec



print("p recovered: ",p_rec)
print("q recovered: ",q_rec)

if (p==p_rec): print("!!! Successfully recovered p !!!")
if (q==q_rec): print("!!! Successfully recovered q !!!")

print(f"\n\nMsg={m}\nbits={bits}")
print(f"p={p}\nq={q}")
print(f"N={N}\n")
print(f"M={m}\n")
print(f"dP={dP}\n")
print(f"dQ={dQ}\n")
print(f"qInv={qInv}\n")

and a sample run for 256-bit prime numbers is [here]:

s1 (no error):  56021528294969193000731306253734117928622714863840906998488964544710659710980
s2 (error):  42724684149461483152909999694448356241172489949685162384842906716939741826064
s (error):  6469101265404271060291683786345788979042545758481144741828344290809928816661412935473574653422845058112228879641634752200930385344983247751270281428653036
p recovered:  97517551883295679149151625389578232227330410834441262164393827490010395338679
q recovered:  89616351945908038439087976457740417907961251495093633980856593171428370490021
!!! Successfully recovered p !!!
!!! Successfully recovered q !!!
Msg=448378203247
bits=256
p=97517551883295679149151625389578232227330410834441262164393827490010395338679
q=89616351945908038439087976457740417907961251495093633980856593171428370490021
N=8739167250476772834723958776533490857578332452121827595533332412376015002357767538111398114928439814548573718893487586591637049018866157094722857484822259
M=448378203247
dP=58431370750951951180371930015462221360987501763243266001397397068910969598159
dQ=31373996048749775454269108012975817453961318862679529701645996516856928643713
qInv=71254943511234361046555380686031562560199917601477871414869197304782914474460

Here’s more CTFs:

https://asecuritysite.com/ctf/

So can you crack:

[Ans: p = 898…, q = 104..]

References

[1] Sullivan, G. A., Sippe, J., & 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] Lenstra, A. K. (1996). Memo on RSA signature generation in the presence of faults (No. REP_WORK).

[3] Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. On the importance of eliminating errors in cryptographic computations. Journal of Cryptology, 14(2):101–119, March 2001.