This is the solution of the challenge “Spooky Safebox” from Hack.lu 2023 CTF. It was a ECDSA signature with a known prefix but with a limited number of signatures. Applying the Bounded Distance Decoding with Predicate algorithm allows to recover the private key.
Description
Satoshi lost his private key, can you help him recover his secret?
nc flu.xxx 10030
Download challenge files
Details
Category: Crypto
Author: newton
Solution
The goal of the challenge is to recover the private key to decrypt the flag. We are allowed to sign 9 messages of our choice with ECDSA over NIST P-256 curve before the key is changed. The nonce for the signature is generated with a fixed part depending of the message and the private key and a random part generated over 224 bits which are added together. The fixed part is also at most 225 bits long thus the final nonce is at most 226 bits. It means that the first 30 bits of the nonce will be always zero. It is a common vulnerability of ECDSA implementations. The secret key should be found by solving an instance of the Hidden Number Problem.
The first problem was that the message is not hashed before being signed but processed with a HMAC function and the key of the HAMC depends on the public key:
1
|
msg = hmac.new(cryptod.int_to_bytes(kpub.point.x() * i), msg_.encode(), "sha224").hexdigest()
|
Then I noticed that the public key was not given. However, for the first signature we have i=0 and thus the key is fixed to zero so we can compute the first HMAC for the message "1" with this:
1
|
z = int(hmac.new(b"\0", b"1", "sha224").hexdigest(), 16)
|
Then with ECDSA formulas we can recover the public key $Q$ from an ECDSA signature $(r,s)$. We need the generator of the curve $G$ and $R$ a point with x-coordinate equals $r$ then we have:
$$Q = r^{-1} (s\cdot R - z \cdot G)$$
Since there is two points with x-coordinate equals $r$ we have to verify with the second signature which is the correct public key by verifying the signature. With the public key we are finally able to compute all the HMAC given as input of ECDSA.
Then I had all I wanted to run a standard attack based on solving the shortest vector problem. However I was concerned with the low number of signatures which would give a very low probability of success and we were not allowed to test a lot of trials since there was a small proof of work to solve before getting the 9 signatures. Nevertheless I used the implementation of Joachim Vandersmissen and run the attack. It did not find any solution after about 500 trials even though with a local sets of 20 signatures it recovers the private key immediately.
Then I remembered I read during a recent work that a new algorithm based on On Bounded Distance Decoding with Predicate was used to increased drastically the success probability of such attacks. Hopefully for me the authors provided a Github repository implementing this attack. I rearrange the signatures, the messages and the public key to allow the algorithm to work:
1
2
3
4
5
6
7
8
9
|
226 000000002e99a92c8c0319f42f968de7e94b939cafbac5815eb1810883db0b62 98d8dc3de6c00049628c58f852412d8a3a0f8ff45c3999cbb59ff3485f7b18683b06db284342da30e72ae0b12de100aaa22ccbdbd3e079357946b53e949f0d88 6fdfe1b6369f5bfe306053bff3ce3d0399ca8e471163ce5331a696cc74253f66d62441c9dafa4f66c27affddea0679354dbf265c24c88511f54d5a88112b1d52
226 000000002d111a7958a7d2f282e4d17e120cd2a0de9dd5813acc693c5c49b2ea 1646008ca9294027f26d7a66a6b2a008c88b8981c3293f1fa8e99d2e896f86b04d32c697cb41f91a00f0a6f21c794d3aab7ea2288dc63f9daad48f30f6f458c7 6fdfe1b6369f5bfe306053bff3ce3d0399ca8e471163ce5331a696cc74253f66d62441c9dafa4f66c27affddea0679354dbf265c24c88511f54d5a88112b1d52
226 0000000018b92392d2c24707d78004f1b37a8854413203e99aba372700998fe9 cef1185b71cf91a95f41a37bf1e6e2cc8f91c16b39fb22ba614b22c18781c9de1c2baa10a0d59048b3946b2538289f5c0511f76bc4424ab18a2f7fd9beae04ba 6fdfe1b6369f5bfe306053bff3ce3d0399ca8e471163ce5331a696cc74253f66d62441c9dafa4f66c27affddea0679354dbf265c24c88511f54d5a88112b1d52
226 00000000f7473e3e956cbe122c6f0fedf79c010b8791344d648fe62a9fd6a1ec 7931cc7a92fbc4292735b7b30c9e276efb34f0cfd70dc075f3581240765aa815b1cf7bad2ad86e0b4e18b0e5915ffcf985090b0148328e77cd1bf116e4ac903a 6fdfe1b6369f5bfe306053bff3ce3d0399ca8e471163ce5331a696cc74253f66d62441c9dafa4f66c27affddea0679354dbf265c24c88511f54d5a88112b1d52
226 00000000f6eba8443398206a42131ab7f3cb2e3733373eb0b77a5f6f50377139 502fa439c433af50691e37121b14ea22527e275b122e464c28790f01ed99d2fc2d2199ce6e61e552817fbc2ff1774c3f29f04ec2e69fecb4eed2c41cfdb25011 6fdfe1b6369f5bfe306053bff3ce3d0399ca8e471163ce5331a696cc74253f66d62441c9dafa4f66c27affddea0679354dbf265c24c88511f54d5a88112b1d52
226 000000006bd64c2092ea43a371d1b25439481a43d33c2c2b0542c71cb6fa1c34 096c756c843aa9c9799877b691cb1133244a219684f6e32f871b4d3fbf1b263e006b14e30b0499cc4792fb193cfcad294beacbc3655d8eaacd5c688caceab37a 6fdfe1b6369f5bfe306053bff3ce3d0399ca8e471163ce5331a696cc74253f66d62441c9dafa4f66c27affddea0679354dbf265c24c88511f54d5a88112b1d52
226 00000000267afcdec4b263699233db0ce40699c678853c2c1f846b2269c56853 0f9a78255d6f43b319f9d33207fba035908cab65bb72be17010d4c50acbaef4b9d67c4499800d217d37cd215ad0a28f965b7f4627e2846cc48811e4b9eee78b9 6fdfe1b6369f5bfe306053bff3ce3d0399ca8e471163ce5331a696cc74253f66d62441c9dafa4f66c27affddea0679354dbf265c24c88511f54d5a88112b1d52
226 00000000f462e0ea4aa1e37206efd736d44025b7b37d675ade1eb6ce62823717 46bebc3ef8411cea98edb4ebcf436ae9192ecf378b1e2588972049a241ba15e790ae903e6b7bc8d549497e1961d47d9cf195124be361614ed22b65d3fb78479a 6fdfe1b6369f5bfe306053bff3ce3d0399ca8e471163ce5331a696cc74253f66d62441c9dafa4f66c27affddea0679354dbf265c24c88511f54d5a88112b1d52
226 0000000088d4350e6745fcdd868aa1a202ebcfaf29ca1a0a3bd0a00da634d1ad 61084c06faf916231cff8c79ab6b9fdcef61864dc60d58bfdfee6b52982ddbac2cf12e5a7722e3be4462b370fc52762d448d4f15bce732e0cb723975d4e26979 6fdfe1b6369f5bfe306053bff3ce3d0399ca8e471163ce5331a696cc74253f66d62441c9dafa4f66c27affddea0679354dbf265c24c88511f54d5a88112b1d52
|
The first column is the size in bits of the nonces, the second column is the messages, the third is the signature $r$ and $s$ and the last is the public key. Then I used their docker to recover the private key:
1
2
3
4
5
6
7
8
9
|
$ docker run -ti --rm -v `pwd`:/bdd-predicate -w /bdd-predicate martinralbrecht/bdd-predicate
sage: f = open("input1.txt","r")
sage: lines = f.read().split("\n")
sage: f.close()
sage: ecdsa = ECDSA(nbits=256, curve="nist256p")
sage: solver = ECDSASolver(ecdsa,lines,m=m)
sage: key, res = solver("bkz-enum")
sage: key
69890597975357728277539391118157508862544796823382301452272038386666314999803
|
It found the private key on the first trial! Then the only remaining task was to implement the ciphertext decryption which decrypts the flag properly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
from cryptod import derive_symkey, int_to_bytes
from Crypto.Cipher import ChaCha20_Poly1305
from binascii import unhexlify
# P-256 curve
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
K = GF(p)
a = K(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc)
b = K(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b)
E = EllipticCurve(K, (a, b))
G = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
E.set_order(0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 * 0x1)
def decrypt_sym(input_bytes, nonce, key):
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
plaintext = cipher.decrypt(input_bytes)
return plaintext
d = 69890597975357728277539391118157508862544796823382301452272038386666314999803
encrypted_flag = "c430554086489131b4c7043786cf4847b8a6206b031b9d633d7903c166dba2efb5e185a3528a3497f85770c1aee0965f9523abda9b82ccc42b813d9d50954eb1e1be74b60ccfdeadbeefb7acc6cb9fe616c623b4c2e104d2eb68b25c0e6f9570b4fc1bdfcb8bd8ea9bea3b4f03af6477e9ae1457dc64881d6cfab994a88f4c093d4ce69d281610332182"
x = encrypted_flag.split("deadbeef")[1][:64]
y = encrypted_flag.split("deadbeef")[1][64:]
R = E(int(x,16), int(y,16))
ciphertext= unhexlify(encrypted_flag.split("deadbeef")[0])
S = d*R
key = derive_symkey(int_to_bytes(int(S.xy()[0])))
print(decrypt_sym(ciphertext[:-12-16], ciphertext[-12:], key))
|
And I obtained the flag:
1
2
|
$ sage decrypt_flag.sage
b'flag{s4tosh1s_Funds_4re_safu_safeB0x_isnt}'
|