yaonet
10 minutes to read
We are given two files id_ecdsa, id_ecdsa.pub and a remote instance to connect using SSH:
ssh -o StrictHostKeyChecking=no -o UserKnownHostsFile=/dev/null yaonet@mc.ax -p 31000 -i id_ecdsa
The private key id_ecdsa is corrupt:
-----BEGIN OPENSSH PRIVATE KEY-----
??????????1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAA????????????????????????
??????????c3RwMjU2AAAACG5pc3RwMjU2AAAAQQR72Bqp????????????????????????
??????????1hSxoXrVpRtsx1F2GIgXAqI/6MxuS7Bq86XF????????????????????????
??????????ZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAy????????????????????????
??????????lSEQfdEcgOhx7zvWFLGhetWlG2zHUXYYiBcC????????????????????????
??????????37PMrof3dNCpeuwsSUupbaUh3/+7+eDnRH+3????????????????????????
-----END OPENSSH PRIVATE KEY-----
And the public key id_ecdsa.pub is correct:
ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBHvYGqk903tU4dOcBPTbZ9xl5rlSEQfdEcgOhx7zvWFLGhetWlG2zHUXYYiBcCoj/ozG5LsGrzpcXE3HuEzPEQg= yaonet
We will need to fix the private key in order to connect to the remote instance and get the flag.
OpenSSH format for ECDSA
We must start figuring out what information we can rescue from the corrupt private key. For this, let’s create a new key:
$ ssh-keygen -t ecdsa
Generating public/private ecdsa key pair.
Enter file in which to save the key (~/.ssh/id_ecdsa): ./id_ecdsa_test
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in ./id_ecdsa_test
Your public key has been saved in ./id_ecdsa_test.pub
The key fingerprint is:
SHA256:JocGd4h16h6YwlGK1VdYgx2tBnhEdSYe5kKG+k924YQ rocky@MBP-Rocky.local
The key's randomart image is:
+---[ECDSA 256]---+
| ...=*B@oo |
| o o+=*B.*. |
|. o.oo=o+. |
| ... *E+= |
| o.o *+S. |
| ..oo=o |
| +.. |
| . |
| |
+----[SHA256]-----+
$ cat id_ecdsa_test
-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAAAAAAABAAAAaAAAABNlY2RzYS
1zaGEyLW5pc3RwMjU2AAAACG5pc3RwMjU2AAAAQQRFzFiscnRWlvedDbDCgZulaX4kbFCQ
hu2MoblHDeppAZPsgCq28Ha5lMDE6Iqt8kossHrFowT4Os1gfzMaF6xsAAAAsJGHg1SRh4
NUAAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBEXMWKxydFaW950N
sMKBm6VpfiRsUJCG7YyhuUcN6mkBk+yAKrbwdrmUwMToiq3ySiywesWjBPg6zWB/MxoXrG
wAAAAhAP4mWGJoSAnkDQDtwLahS17+hw7j5D6fJZj6ZgXFH92TAAAAFXJvY2t5QE1CUC1S
b2NreS5sb2NhbAEC
-----END OPENSSH PRIVATE KEY-----
$ cat id_ecdsa_test.pub
ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBEXMWKxydFaW950NsMKBm6VpfiRsUJCG7YyhuUcN6mkBk+yAKrbwdrmUwMToiq3ySiywesWjBPg6zWB/MxoXrGw= rocky@MBP-Rocky.local
Now, we can import it to Python and find the key parameters:
$ python3 -q
>>> from Crypto.PublicKey import ECC
>>>
>>> private_key = ECC.import_key(open('id_ecdsa_test').read())
>>> public_key = ECC.import_key(open('id_ecdsa_test.pub').read())
>>>
>>> private_key
EccKey(curve='NIST P-256', point_x=31570635356302975547204064636676814907262944410487335975000995944154943613185, point_y=66907849224143765145869109791263747842720656896951286262556819933609256791148, d=114955213735346645511226667280015474436164920344675662509995323724030871068051)
>>> public_key
EccKey(curve='NIST P-256', point_x=31570635356302975547204064636676814907262944410487335975000995944154943613185, point_y=66907849224143765145869109791263747842720656896951286262556819933609256791148)
Basically, it is an ECC key, where the private key is $d$ and the public key is $Q$, where $Q = d \cdot G$ and $G$ is a generator point of the NIST P-256 curve. We can print the relevant values in hexadecimal format:
>>> private_key.curve
'NIST P-256'
>>> hex(private_key.d)
'0xfe265862684809e40d00edc0b6a14b5efe870ee3e43e9f2598fa6605c51fdd93'
>>> hex(private_key.pointQ.x)
'0x45cc58ac72745696f79d0db0c2819ba5697e246c509086ed8ca1b9470dea6901'
>>> hex(private_key.pointQ.y)
'0x93ec802ab6f076b994c0c4e88aadf24a2cb07ac5a304f83acd607f331a17ac6c'
With this, we can Base64-decode the private key and print it out in hexadecimal format to find the position of the above values:
$ cat id_ecdsa_test | grep -v 'PRIVATE KEY' | base64 -d | xxd
00000000: 6f70 656e 7373 682d 6b65 792d 7631 0000 openssh-key-v1..
00000010: 0000 046e 6f6e 6500 0000 046e 6f6e 6500 ...none....none.
00000020: 0000 0000 0000 0100 0000 6800 0000 1365 ..........h....e
00000030: 6364 7361 2d73 6861 322d 6e69 7374 7032 cdsa-sha2-nistp2
00000040: 3536 0000 0008 6e69 7374 7032 3536 0000 56....nistp256..
00000050: 0041 0445 cc58 ac72 7456 96f7 9d0d b0c2 .A.E.X.rtV......
00000060: 819b a569 7e24 6c50 9086 ed8c a1b9 470d ...i~$lP......G.
00000070: ea69 0193 ec80 2ab6 f076 b994 c0c4 e88a .i....*..v......
00000080: adf2 4a2c b07a c5a3 04f8 3acd 607f 331a ..J,.z....:.`.3.
00000090: 17ac 6c00 0000 b091 8783 5491 8783 5400 ..l.......T...T.
000000a0: 0000 1365 6364 7361 2d73 6861 322d 6e69 ...ecdsa-sha2-ni
000000b0: 7374 7032 3536 0000 0008 6e69 7374 7032 stp256....nistp2
000000c0: 3536 0000 0041 0445 cc58 ac72 7456 96f7 56...A.E.X.rtV..
000000d0: 9d0d b0c2 819b a569 7e24 6c50 9086 ed8c .......i~$lP....
000000e0: a1b9 470d ea69 0193 ec80 2ab6 f076 b994 ..G..i....*..v..
000000f0: c0c4 e88a adf2 4a2c b07a c5a3 04f8 3acd ......J,.z....:.
00000100: 607f 331a 17ac 6c00 0000 2100 fe26 5862 `.3...l...!..&Xb
00000110: 6848 09e4 0d00 edc0 b6a1 4b5e fe87 0ee3 hH........K^....
00000120: e43e 9f25 98fa 6605 c51f dd93 0000 0015 .>.%..f.........
00000130: 726f 636b 7940 4d42 502d 526f 636b 792e rocky@MBP-Rocky.
00000140: 6c6f 6361 6c01 02 local..
$ cat id_ecdsa_test | grep -v 'PRIVATE KEY' | base64 -d | xxd | grep -E '^|fe ?26|45 ?cc|93 ?ec'
00000000: 6f70 656e 7373 682d 6b65 792d 7631 0000 openssh-key-v1..
00000010: 0000 046e 6f6e 6500 0000 046e 6f6e 6500 ...none....none.
00000020: 0000 0000 0000 0100 0000 6800 0000 1365 ..........h....e
00000030: 6364 7361 2d73 6861 322d 6e69 7374 7032 cdsa-sha2-nistp2
00000040: 3536 0000 0008 6e69 7374 7032 3536 0000 56....nistp256..
00000050: 0041 0445 cc58 ac72 7456 96f7 9d0d b0c2 .A.E.X.rtV......
00000060: 819b a569 7e24 6c50 9086 ed8c a1b9 470d ...i~$lP......G.
00000070: ea69 0193 ec80 2ab6 f076 b994 c0c4 e88a .i....*..v......
00000080: adf2 4a2c b07a c5a3 04f8 3acd 607f 331a ..J,.z....:.`.3.
00000090: 17ac 6c00 0000 b091 8783 5491 8783 5400 ..l.......T...T.
000000a0: 0000 1365 6364 7361 2d73 6861 322d 6e69 ...ecdsa-sha2-ni
000000b0: 7374 7032 3536 0000 0008 6e69 7374 7032 stp256....nistp2
000000c0: 3536 0000 0041 0445 cc58 ac72 7456 96f7 56...A.E.X.rtV..
000000d0: 9d0d b0c2 819b a569 7e24 6c50 9086 ed8c .......i~$lP....
000000e0: a1b9 470d ea69 0193 ec80 2ab6 f076 b994 ..G..i....*..v..
000000f0: c0c4 e88a adf2 4a2c b07a c5a3 04f8 3acd ......J,.z....:.
00000100: 607f 331a 17ac 6c00 0000 2100 fe26 5862 `.3...l...!..&Xb
00000110: 6848 09e4 0d00 edc0 b6a1 4b5e fe87 0ee3 hH........K^....
00000120: e43e 9f25 98fa 6605 c51f dd93 0000 0015 .>.%..f.........
00000130: 726f 636b 7940 4d42 502d 526f 636b 792e rocky@MBP-Rocky.
00000140: 6c6f 6361 6c01 02 local..
Alright, so the coordinates of $Q$ appear twice and the $d$ secret value appears at the end. The id_ecdsa_test.pub shows the coordinates of $Q$:
$ awk '{ print $2 }' id_ecdsa_test.pub | base64 -d | xxd | grep -E '^|fe ?26|45 ?cc|93 ?ec'
00000000: 0000 0013 6563 6473 612d 7368 6132 2d6e ....ecdsa-sha2-n
00000010: 6973 7470 3235 3600 0000 086e 6973 7470 istp256....nistp
00000020: 3235 3600 0000 4104 45cc 58ac 7274 5696 256...A.E.X.rtV.
00000030: f79d 0db0 c281 9ba5 697e 246c 5090 86ed ........i~$lP...
00000040: 8ca1 b947 0dea 6901 93ec 802a b6f0 76b9 ...G..i....*..v.
00000050: 94c0 c4e8 8aad f24a 2cb0 7ac5 a304 f83a .......J,.z....:
00000060: cd60 7f33 1a17 ac6c .`.3...l
Corrupt key information
With this knowledge, we can take some information from the challenge files:
$ cat id_ecdsa | tr '?' A | grep -v 'PRIVATE KEY' | base64 -d | xxd -R never
00000000: 0000 0000 0000 000d 6b65 792d 7631 0000 ........key-v1..
00000010: 0000 046e 6f6e 6500 0000 046e 6f6e 6500 ...none....none.
00000020: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000030: 0000 0000 0000 0000 0000 0000 7374 7032 ............stp2
00000040: 3536 0000 0008 6e69 7374 7032 3536 0000 56....nistp256..
00000050: 0041 047b d81a a900 0000 0000 0000 0000 .A.{............
00000060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000070: 0d61 4b1a 17ad 5a51 b6cc 7517 6188 8170 .aK...ZQ..u.a..p
00000080: 2a23 fe8c c6e4 bb06 af3a 5c50 0000 0000 *#.......:\P....
00000090: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000a0: 0000 0000 0064 7361 2d73 6861 322d 6e69 .....dsa-sha2-ni
000000b0: 7374 7032 3536 0000 0008 6e69 7374 7032 stp256....nistp2
000000c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000d0: 0000 0000 0000 0000 0009 5211 07dd 11c8 ..........R.....
000000e0: 0e87 1ef3 bd61 4b1a 17ad 5a51 b6cc 7517 .....aK...ZQ..u.
000000f0: 6188 8170 2000 0000 0000 0000 0000 0000 a..p ...........
00000100: 0000 0000 0000 0000 0000 0000 0000 dfb3 ................
00000110: ccae 87f7 74d0 a97a ec2c 494b a96d a521 ....t..z.,IK.m.!
00000120: dfff bbf9 e0e7 447f b700 0000 0000 0000 ......D.........
00000130: 0000 0000 0000 0000 0000 00 ...........
$ cat id_ecdsa.pub | awk '{ print $2 }' | base64 -d | xxd -R never
00000000: 0000 0013 6563 6473 612d 7368 6132 2d6e ....ecdsa-sha2-n
00000010: 6973 7470 3235 3600 0000 086e 6973 7470 istp256....nistp
00000020: 3235 3600 0000 4104 7bd8 1aa9 3dd3 7b54 256...A.{...=.{T
00000030: e1d3 9c04 f4db 67dc 65e6 b952 1107 dd11 ......g.e..R....
00000040: c80e 871e f3bd 614b 1a17 ad5a 51b6 cc75 ......aK...ZQ..u
00000050: 1761 8881 702a 23fe 8cc6 e4bb 06af 3a5c .a..p*#.......:\
00000060: 5c4d c7b8 4ccf 1108 \M..L...
Looking at those, we can find the exact coordinates of $Q$ from the public key and some bytes of the secret value $d$ from the private key. Particularly, we know
$$ d = \mathtt{0x??????dfb3ccae87f774d0a97aec2c494ba96da521dfffbbf9e0e7447fb7????} $$
We are missing 5 bytes (3 at the left and 2 at the right). We can define $d_k$ as the known part of $d$:
$$ d_k = \mathtt{0xdfb3ccae87f774d0a97aec2c494ba96da521dfffbbf9e0e7447fb7} $$
And define $d_l$ and $d_r$ to be the unknown left and right parts of $d$, such that
$$ d = 256^{29} \cdot d_l + 256^2 \cdot d_k + d_r $$
Key recovery
We need to find the value of $d_l$ and $d_r$ to find the secret value $d$ and create the private key id_ecdsa. However, 5 bytes (40 bits) is a lot to use a naïve brute force approach, we need to come up with a better algorithm.
Baby-step Giant-step
The Baby-step Giant-step (BSGS) is an algorithm to compute discrete logarithms on finite groups whose complexity is $O(\sqrt{n})$, where $n$ is the order of the element. This would be perfect, because we improve the naïve brute force approach to a complexity of 20 bits, which is affordable.
This algorithm wants to find $d$ satisfying $Q = d \cdot G$ where both $G$ and $Q$ are known. The algorithm takes the $\mathrm{ord}(G) = n$ and computes $m = \lceil\sqrt{n}\rceil$. Then, it starts computing the following recurrence:
$$ \begin{cases} H_1 = m \cdot G \\ H_i = H_{i - 1} + m \cdot G = (i \cdot m) \cdot G, \quad 1 < i < m \end{cases} $$
All the $H_i$ coordinates are saved in a map $H_i \mapsto i$.
After that, we do a similar computation:
$$ \begin{cases} K_1 = Q \\ K_j = K_{j - 1} - G = Q - j \cdot G, \quad j > 1 \end{cases} $$
While computing $K_j$ we need to look if the point is in the map $H_i \mapsto i$. In such case, then $d = i \cdot m + j$ and we are done.
Meet-in-the-middle attack
The previous algorithm is kind of a Meet-in-the-middle attack, because it starts from both $G$ and $Q$ sides until finding a common place “in the middle”.
With the challenge setup, we can’t simply use BSGS because the unknown bytes are not contiguous, but we can apply the same concepts. Notice that:
$$ \begin{align} Q & = d \cdot G \\ & = (256^{29} \cdot d_l + 256^2 \cdot d_k + d_r) \cdot G \\ & = (256^{29} \cdot d_l) \cdot G + (256^2 \cdot d_k) \cdot G + d_r \cdot G \end{align} $$
For instance, we can start computing the following recurrence:
$$ \begin{cases} H_1 = (256^2 \cdot d_k) \cdot G + G \\ H_i = H_{i - 1} + G = (256^2 \cdot d_k + i) \cdot G, \quad 1 < i < 256^2 \end{cases} $$
We will save the values in a map $H_i \mapsto i$, and compute the next recurrence starting from $Q$ (let’s define $P := 256^{29} \cdot G$):
$$ \begin{cases} K_1 = Q \\ K_j = K_{j - 1} - P = Q - j \cdot P, \quad 1 < j < 256^3 \end{cases} $$
While computing $K_j$ we will look if the point is in the map $H_i \mapsto i$, and then $d = 256^{29} \cdot j + 256^2 \cdot d_k + i$ and we are done.
Implementation
The above algorithm can be implemented as follows:
#!/usr/bin/env python3
from sage.all import EllipticCurve, GF
from Crypto.PublicKey import ECC
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
E = EllipticCurve(GF(p), [a, b])
G = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
dk = 0xdfb3ccae87f774d0a97aec2c494ba96da521dfffbbf9e0e7447fb7
Q = E(0x7bd81aa93dd37b54e1d39c04f4db67dc65e6b9521107dd11c80e871ef3bd614b, 0x1a17ad5a51b6cc7517618881702a23fe8cc6e4bb06af3a5c5c4dc7b84ccf1108)
table_points = {}
H = (256 ** 2 * dk) * G
for i in range(2 ** 16):
table_points[H.xy()] = i
H += G
P = (256 ** 29) * G
K = Q
for j in range(2 ** 24):
if (i := table_points.get(K.xy())):
d = (256 ** 29) * j + (256 ** 2) * dk + i
assert Q == d * G
with open('id_ecdsa', 'w') as f:
f.write(ECC.EccKey(curve='NIST P-256', d=d).export_key(format='PEM'))
break
K -= P
Once we find $d$, we just create the ECC key and export it to PEM format.
Flag
With the recovered private key, we just need to connect to the remote instance and capture the flag:
$ chmod 600 id_ecdsa
$ ssh -o StrictHostKeyChecking=no -o UserKnownHostsFile=/dev/null yaonet@mc.ax -p 31000 -i id_ecdsa
Warning: Permanently added '[mc.ax]:31000' (RSA) to the list of known hosts.
dice{now_can_you_sing_it?}
Connection to mc.ax closed by remote host.
Connection to mc.ax closed.
The full script can be found in here: solve.py.