CookieMonster
J’ai bien galéré lol
On nous présente un serveur qui crée un JWT avec une clé RSA bien grande (8k bits).
Cependant, les facteurs p et q de cette clé sont générés à partir de 512 bits chacuns. Chaque bit de la clé prend un byte. La clé ressemble à quelque chose comme
Exemple à 16 bits:
p: 0x01000101000101010100010000010101
q: 0x01010000000101000100000100000001
n: 0x0001010102010203030502030502050505040204030304020201020100010101
e: 65537
mais avec 512 bits.
Théorie
J’ai réfléchis à pourquoi les extrémités de n étaient aussi petits, et pourquoi le millieu était plus grand. Je me suis ensuite rappellé de la multiplication en colonne.
En effet, on peut déduire les bits de p et de q, en faisant l’inverse d’une multiplication en colonne. Ça nous arrange tout particulièrement, car il n’y aura jamais de retenu (p ou q ne sont pas assez grand.)
Par exemple, on peut avoir quelque chose du style:
010101
* 010001
----------
+ 010101
+ 000000
+ 010101
----------
0101020101
Le résultat devient alors 0101020101, mais peut-t-on faire l’opération inverse facilement ?
En réfléchissant avec des inconnus temporaires, on peut:
0x0x0x
* 0x0x0x
----------
+ 0x0x0x
+ 0x0x0x
+ 0x0x0x
----------
0101020101
En effet, sur la colonne tout à droite, le premier bit devient obligatoirement 01, et donc p et q finissent tous les deux par 01
0x0x01
* 0x0x01
----------
+ 0x0x01
+ 0x0x0x
+ 0x0x0x
----------
0101020101
Ensuite, pour la deuxième colonne, on ne peut pas être sûr. Cependant, puisque les deux facteurs de la multiplication sont indentiques et que la multiplication est commutative, on peut choisir où mettre le bit.
0x0001
* 0x0101
----------
+ 0x0001
+ 0x0x01
+ 0x0x0x
----------
0101020101
Puisque on a un nouveau bit, on peut maintenant remplir ce que j’appèle la “somme du millieu”. En effet, on peut connaître le prochain bit pour la deuxième ligne d’addition
0x0001
* 0x0101
----------
+ 0x0001
+ 0x0001
+ 0x0x0x
----------
0101020101
Maintenant, pour que l’addition fasse un 2, on est sûr que les deux x correspondent à des 1.
010001
* 010101
----------
+ 010001
+ 0x0001
+ 0x0x01
----------
0101020101
Puis on rempli le reste des additions pour être sûr que la réponse est juste
010001
* 010101
----------
+ 010001
+ 010001
+ 010001
----------
0101020101
Comme on peut le voir, ça fonctionne. Maintenant, il faut faire ça à une plus grande échelle.
Dans certain cas, on ne peut pas être sûr de où mettre le bit, par exemple si il y a deux choix, et que p n’est déjà plus égal à q. Il suffit juste d’essayer dans ce cas là, et de comparer les réponses à la fin.
Pratique
J’ai écrit un script en Rust qui factorise N à partir de cette méthode, en moins d’une seconde.
fn main() {
let n = hex_literal::hex!("0001010102010203030502030502050505040204030304020201020100010101");
println!("{:?}", n);
let mut p = vec![0x01];
let mut q = vec![0x01];
factorize_n(&n.to_vec(), &mut p, &mut q);
}
fn factorize_n(n: &Vec<u8>, p: &mut Vec<u8>, q: &mut Vec<u8>) -> bool {
println!("[*] Starting factorization...");
assert_eq!(p.len(), q.len(), "P and Q lengths are not the same.");
let end_index = n.len() / 2 + 1;
for i in q.len()..end_index {
println!("[*] Index: {}", i);
println!("[*] p: {:?}", p);
println!("[*] q: {:?}", q);
let mut sum = n[n.len() - i - 1];
println!("[*] Unmodified sum: {}", sum);
for j in 1..i {
let a_index = i - j - 1;
let b_index = j - 1;
let a = p[a_index];
let b = q[b_index];
println!("[*] Processing inter sum: {} ({})x({}) = {}x{} = {}", j, a_index, b_index, a, b, a * b);
if sum < a * b {
println!("[*] Branch fail: modifying sum not enough");
return false
}
sum -= a * b;
}
println!("[*] Modified sum: {}", sum);
if sum == 2 {
p.insert(0, 1);
q.insert(0, 1);
} else if sum == 0 {
p.insert(0, 0);
q.insert(0, 0);
} else if sum == 1 {
// unknown, we have to branch out.
println!("[*] Branching...");
let mut pcopy = p.clone();
let mut qcopy = q.clone();
pcopy.insert(0, 1);
qcopy.insert(0, 0);
if factorize_n(n, &mut pcopy, &mut qcopy) {
// yay, we found
for i in (0..(pcopy.len() - p.len() + 1)).rev() {
p.insert(0, pcopy[i])
}
for i in (0..(qcopy.len() - q.len() + 1)).rev() {
q.insert(0, qcopy[i])
}
println!("[*] Branch WIN!!!");
return true
} else {
pcopy = p.clone();
qcopy = q.clone();
pcopy.insert(0, 0);
qcopy.insert(0, 1);
if factorize_n(n, &mut pcopy, &mut qcopy) {
// yay, we found
for i in (0..(pcopy.len() - p.len() + 1)).rev() {
p.insert(0, pcopy[i])
}
for i in (0..(qcopy.len() - q.len() + 1)).rev() {
q.insert(0, qcopy[i])
}
println!("[*] Branch WIN!!!");
return true
}
}
// fail!
println!("[*] Branch fail: subbranches did not work");
return false
} else {
println!("[*] Branch fail: sum too big");
// fail!
return false
}
}
println!("p: {:?}", p);
println!("q: {:?}", q);
// implement one last check to make sure it works lol
if p[0] != 1 {
println!("Branch fail: p not starting with 1 lol");
return false
}
if q[0] != 1 {
println!("Branch fail: q not starting with 1 lol");
return false
}
let p_x = num_bigint::BigUint::from_bytes_be(p);
let q_x = num_bigint::BigUint::from_bytes_be(q);
let n_x = num_bigint::BigUint::from_bytes_be(n);
println!("[*] p*q: {}", p_x.clone() * q_x.clone());
println!("[*] n: {}", n_x);
println!("[***] p: {}", hex::encode(p));
println!("[***] q: {}", hex::encode(q));
if p_x * q_x != n_x {
println!("Branch fail: p * q != n");
return false;
}
true
}
Il y a encore quelque bug, mais c’était suffisant pour gagner le challenge.
Sans compter l’écriture des logs, le script prend 0.20s à factoriser N (8k bits).
J’ai aussi dû faire un petit script en python pour lire la clé publique du serveur:
from Crypto.PublicKey import RSA
from Crypto.Util import asn1
from base64 import b64decode
from typing import Tuple
def decode_public_key(key: str) -> Tuple[int, int]:
key = key.strip()
if key.startswith(b"-----BEGIN PUBLIC KEY-----"):
key = key[key.index(b"\n")+1:]
if key.endswith(b"-----END PUBLIC KEY-----"):
key = key[:key.rindex(b"\n")]
key = b64decode(key)
key = RSA.import_key(key)
return key.n, key.e
(N, e) = decode_public_key(b"""
-----BEGIN PUBLIC KEY-----
MIIEIDANBgkqhkiG9w0BAQEFAAOCBA0AMIIECAKCA/8BAQABAgMDAgMDAgMDAgID
AgQFBAQEBQQDBQQDBQUFBAUHBQcIBwgJCQgLCgYIBwkJCAoHCQsLCwcNDQkNDAsM
CwsJDg4JEQ4NEA8SDBETExIOEw8RExASFA4UFRQYFxcUGBQWHA8YGRcYGxcYGRkb
HxYhIhwdIBcdHR0dIR0cIB4aIhwlIx4iIR0eIRweJx8hJCEmKCElIiQsJyclJiQl
KygpLicnKiosMiwqKiUkLSgsLC0rLysnKikoLDEwMjApJykuLzEvLjEuLzEzLi8y
MzIyLy0sKzE0NDUyMjIyNDU1LzM1OC43MTExMjk1OTo1Pjc5Mjk2Ojo5OUA+PDw8
REE7QDk7PkI7Ozs4RDc4Q0BGRj1APkJDSEFCPkY6PkFGQkBMQEhPRVM/R01JSURJ
SUtJQk1GUEhNUE1OU0pKSEtOTkhKUlVQTE5UT1RSUE1ZVVhPTFZUU1JZWVhVWlZY
UVdTV1xSW1tVVGJVVmJdU1hUWV5WUlpXWGJZWF1aWGBfWl9iX2FlYmNaVVNZamJp
WmVlW1tiYl5daWBkaGRdW2NiWWtsYmhmW2tfYW1qZ2lgamVlZXJsbXRlbWZjbW5q
cGtjbG1sZ3Bpam5sb21rcnFrbW1scGt3dX93d3RsbXlxd3V3eHV4cnF2e3l0fIR3
fYR4e354e4Fwg3d3fHuAf4SAhIlyd3Z3foB3eXiAgXV+d3p6doh8doR0c4RyeHpy
dnp/gH14dHpyb39vcH11dnZyeXB3c3RydXB+cn99cXJucXVtcnF2d2l2bnB4aXxv
bmZsbGlvcnRrcF1qaXNkZmhsZG1gXmZjZVxlYWteZmFYXGhVYV1ca11lXmVbYVtf
YF9VYF5YWVphVVVXW1ldYFhfW11VVWJdVU5PW1JXVFRXVFVWW1FVWVVWUVdVVFJX
UFNQWElVVVVbU0tVTUxNTldRUlFQTkdXTEtZU09QTExNS1BKTlFPTEdSUU1RTFFL
SU5JR0tPTkxMSkxMSUNLRUtLST5LREdAQz1EQ0JIRztERUJDPkM/QUBCPEZEPz0/
QDNAPjg9PTg+NDg/Nj01PDozOjI6ODc0Lio1LjUyMjI3My4vNTYzNSwxMDA3Ly80
MTEvKTAtNS8vKyosLCguKygsLCosKygpKSkpJSsiKyArKCUmJygpJCInICkjKyMn
IyErHiEiJyApISQjHiMhIyYfGycgJB8mHR0lHCMiHR8fICIdHx8eGxkeGx4XHxkb
GRobGBsZFxQaFxoZGxQcGBUUFRkUFRMYEhIUFhEUExIOEg8PExERCw4RDw4ODQwL
DgsJDAsNCgsJCgoLCQoIBwgICggHCAoHBgcHBggGAwUEAwMEBQMBAgMBAQIBAAEC
AwEAAQ==
-----END PUBLIC KEY-----
""")
print("N = "+N.to_bytes(1024, "big").hex())
print("e =", e)
Ensuite, il fallait juste générer un jwt valide:
from Crypto.PublicKey import RSA
import jwt
p = 0x0101010000010000010100000000000101010000010100000000000101010000010000000000010101010101000000000001000101000001000000010001010101010000000001000000010001010100000101000000010101010101010000000000000000000001010101000000000100000101010101000101000000010001000100010101000100010001000100010001010001010000000001000100010001010000010001010000000101010101010100000100010000010101000100000101010001010001010101010100000001010101010001010001010101000100000001000001000000010101000100010101000001000100000100010101010101000000000001010100000000010000010001010001010101000100010001000100000000000101010101010001000001010000010101010000000100010101010001010100000001000001000000000101010000000101000000010001010101010100000001000001000100000001000101000001000100000101010101000101000001000000010000010100010101010101010100000100010001010101010101000101010000010001000101000000000100000000000101000000010001010000010100010101010100010000010000000100010001010001010001000001010100000101000001010001000001010001010001010001010000010101
q = 0x0100000000000100000001010100010001010101000001000100000100000000000001010101010101010100010101010101010001010000010000000001000100010100010100000101010001010000010100000000010101010001010000010001000100010101010001010000000001000001000100010001000000010000000000000101010001010100010001000100010101010000010100010100010100000101010101000001000101000000000101010101000001010100010001000101010100000000000000000001010001010001000001000100000000010001010100010000010000000001000100010101000101000000000101010101010101000000010100010100010000010100000100010100010001000001000001010001000001000001000101000001000100010001010000010101000101000100000000010100010001000000010100010100000000010000010000000100010101000000010000000000000101000001010001010000010100010100000001010001010000000101000100000000010100000100010001000000000100000101000100010001000101010100000100010001000001010100010000000001000100000000010101000101000000000001000001000101010000010000000000010000010101010000010100010100000000000100000100000000010100000001
e = 65537
n = p * q
d = pow(e, -1, (p - 1) * (q - 1))
sk = RSA.construct((n, e, d), consistency_check=True)
pk = sk.public_key().export_key()
cookie = jwt.encode({"user": "admin"}, sk.export_key(), algorithm="RS256")
print(cookie)
Et j’ai aussi dû faire un petit script pour communiquer avec le serveur lol (le jwt était trop grand pour netcat ?)
import pwn
r = pwn.remote("challenges.shutlock.fr", 50005)
r.interactive()
Solution
SHLK{0b94541e218f89e51ffec67e0cc2de91}