yaonet
10 minutos de lectura
Se nos proporcionan dos archivos id_ecdsa, id_ecdsa.pub y una instancia remota para conectarnos usando SSH:
ssh -o StrictHostKeyChecking=no -o UserKnownHostsFile=/dev/null yaonet@mc.ax -p 31000 -i id_ecdsa
La clave privada id_ecdsa está corrupta:
-----BEGIN OPENSSH PRIVATE KEY-----
??????????1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAA????????????????????????
??????????c3RwMjU2AAAACG5pc3RwMjU2AAAAQQR72Bqp????????????????????????
??????????1hSxoXrVpRtsx1F2GIgXAqI/6MxuS7Bq86XF????????????????????????
??????????ZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAy????????????????????????
??????????lSEQfdEcgOhx7zvWFLGhetWlG2zHUXYYiBcC????????????????????????
??????????37PMrof3dNCpeuwsSUupbaUh3/+7+eDnRH+3????????????????????????
-----END OPENSSH PRIVATE KEY-----
Y la clave pública id_ecdsa.pub es correcta:
ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBHvYGqk903tU4dOcBPTbZ9xl5rlSEQfdEcgOhx7zvWFLGhetWlG2zHUXYYiBcCoj/ozG5LsGrzpcXE3HuEzPEQg= yaonet
Tendremos que arreglar la clave privada para conectarnos a la instancia remota y obtener la flag.
Formato de ECDSA en OpenSSH
Debemos comenzar por descubrir qué información podemos rescatar de la clave privada corrupta. Para esto, creemos una nueva clave:
$ 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
Ahora, podemos importarla en Python y encontrar los parámetros clave:
$ 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)
Básicamente, es una clave de ECC, donde la clave privada es $d$ y la clave pública es $Q$, donde $Q = d \cdot G$ y $G$ es el punto generador de la curva NIST P-256. Podemos imprimir los valores relevantes en formato hexadecimal:
>>> private_key.curve
'NIST P-256'
>>> hex(private_key.d)
'0xfe265862684809e40d00edc0b6a14b5efe870ee3e43e9f2598fa6605c51fdd93'
>>> hex(private_key.pointQ.x)
'0x45cc58ac72745696f79d0db0c2819ba5697e246c509086ed8ca1b9470dea6901'
>>> hex(private_key.pointQ.y)
'0x93ec802ab6f076b994c0c4e88aadf24a2cb07ac5a304f83acd607f331a17ac6c'
Con esto, podemos decodificar la clave privada en Base64 e imprimirla en formato hexadecimal para identificar la posición de los valores anteriores:
$ 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..
Muy bien, vemos que las coordenadas de $Q$ aparecen dos veces y el valor secreto de $d$ aparece al final. El archivo id_ecdsa_test.pub muestra las coordenadas de $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
Información en la clave corrupta
Con este conocimiento, podemos tomar algo de información de los archivos del reto:
$ 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...
Mirándolos, podemos encontrar las coordenadas exactas de $Q$ en la clave pública y algunos bytes del valor secreto $d$ en la clave privada. Particularmente, sabemos que
$$ d = \mathtt{0x??????dfb3ccae87f774d0a97aec2c494ba96da521dfffbbf9e0e7447fb7????} $$
Nos faltan 5 bytes (3 a la izquierda y 2 a la derecha). Podemos definir $d_k$ como la parte conocida de $d$:
$$ d_k = \mathtt{0xdfb3ccae87f774d0a97aec2c494ba96da521dfffbbf9e0e7447fb7} $$
Y definir $d_l$ y $d_r$ como las partes desconocidas izquierda y derecha de $d$, de modo que
$$ d = 256^{29} \cdot d_l + 256^2 \cdot d_k + d_r $$
Recuperación de la clave
Necesitamos encontrar el valor de $d_l$ y de $d_r$ para encontrar el valor secreto $d$ y crear el la clave privada id_ecdsa. Sin embargo, 5 bytes (40 bits) es mucho para usar un enfoque de fuerza bruta, necesitamos encontrar un mejor algoritmo.
Baby-step Giant-step
El algoritmo Baby-step Giant-step (BSGS) se utiliza para calcular logaritmos discretos en grupos finitos, con una complejidad es $O(\sqrt{n})$, donde $n$ es el orden del elemento. Esto sería perfecto, porque mejoramos el enfoque de fuerza bruta a una complejidad de 20 bits, lo cual es asequible.
Este algoritmo trata de encontrar $d$ tal que $Q = d \cdot G$ donde ambos $G$ y $Q$ son conocidos. El algoritmo toma $\mathrm{ord}(G) = n$ y calcula $m = \lceil\sqrt{n}\rceil$. Luego, comienza a calcular la siguiente recurrencia:
$$ \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} $$
Todas las coordenadas $H_i$ se guardan en un mapa $H_i \mapsto i$.
Después de eso, hacemos un cálculo similar:
$$ \begin{cases} K_1 = Q \\ K_j = K_{j - 1} - G = Q - j \cdot G, \quad j > 1 \end{cases} $$
Mientras se calcula $K_j$, debemos buscar si el punto está en el mapa $H_i \mapsto i$. En tal caso, $d = i \cdot m + j$ y hemos terminado.
Ataque Meet-in-the-middle
El algoritmo anterior es una especie de ataque Meet-in-the-middle, porque comienza desde ambos lados de $G$ y $Q$ hasta encontrar un lugar común “en el medio”.
Con la configuración del reto, no podemos simplemente usar BSGS porque los bytes desconocidos no son contiguos, pero podemos aplicar los mismos conceptos. Nótese que:
$$ \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} $$
Por ejemplo, podemos comenzar a calcular la siguiente recurrencia:
$$ \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} $$
Guardaremos los valores en un mapa $H_i \mapsto i$, y calcularemos la siguiente recurrencia a partir de $Q$ (definimos $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} $$
Mientras calculamos $K_j$, miramos si el punto está en el mapa $H_i \mapsto i$, y entonces $d = 256^{29} \cdot j + 256^2 \cdot d_k + i$ y habremos terminado.
Implementación
El algoritmo anterior se puede implementar de la siguiente manera:
#!/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
Una vez que encontramos $d$, simplemente creamos la clave de ECC y la exportamos en formato PEM.
Flag
Con la clave privada recuperada, solo necesitamos conectarnos a la instancia remota y capturar la 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.
El script completo se puede encontrar aquí: solve.py.