Quelques explications sur le problème RSA du SIGINT CTF 2013:
Les deux fichiers suivants sont donnés:
genrsa.py
#!/usr/bin/env python
from time import time
from os import system
from Crypto.PublicKey import RSA
SEED = int(time())
def randfunc(n):
def rand():
global SEED
ret = SEED*0x1333370023004200babe004141414100e9a1192355de965ab8cc1239cf015a4e35 + 1
SEED = ret
return (ret >> 0x10) & 0x7fff
ret = ""
while len(ret) < n:
ret += chr(rand() & 0xff)
return ret
if __name__ == "__main__":
keypair = RSA.generate(1024, randfunc)
with open("pub", "w") as pubfile, open("id_rsa", "w") as privfile:
privfile.write(keypair.exportKey())
pubfile.write(keypair.publickey().exportKey())
system("ssh-keygen -m PKCS8 -i -f pub > id_rsa.pub && rm pub")
Et le fichier authorized_keys
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAAAgQC+K6w1yodieqyryJnUYHw/ZuycabT0Ehwg4XFqZYfh/euE4QIXPJ23widXJUKIq8Gqwi5M/Pa+7/gAPeVcrcF65pUkeIYeZBXoAeDj0EqpFxiHdSB/K1Ovt/lIFmBG3hy+MVJLYfz6lBRxQwj+CJRkFX2Xf/5JyZWSK5UwXOlh0w==
On a donc la partie publique d'une clef RSA générée avec un RNG faible.
La première observation est que ce RNG fait grandir SEED de manière arbitrairement grande; ce RNG est donc très, très lent. Cependant, on observe qu'en sortie, seuls les bits 16-24 de SEED sont utilisés (on à SEED >> 0x10 & 0xff). Autrement dit, ce générateur non borné est congru a un autre modulo 2^24. Ou, pour voir plus simplement les choses: après multiplication par la grande constante, un bit changé dans la seed en entrée ne peut affecter que des bits de poids plus fort. on peut donc joyeusement ignorer les bits au dela du 24e.
.On peut donc remplacer la grande constante 0x1333...5a4e35, par sa réduction modulo 2^25, soit 0x15a4e35. On peut également réduire SEED à chaque iteration, avec SEED &= 0x1ffffff. Ceci a pour effet d'accélérer considérablement le RNG.
Pour le bruteforce, l'espace des seeds est quand même assez grand, nous allons donc essayer de la deviner. Le header de la réponse HTTP du fichier authorized_keys nous indique:
Last-Modified: Fri, 05 Jul 2013 17:50:05 GMT
La génération de la clef est donc antérieure à cette date. On va commencer à bruteforcer en partant de cette valeur, et en descendant.
Pour ne pas perdre de temps, on lit le code de PyCrypto concernant la génération de clefs RSA, et on s'aperçoit que ce code appelle pubkey.getStrongPrime une première fois, avec la moitié de la taille souhaitée, puis autant de fois que nécessaire pour obtenir le deuxième nombre. Pour gagner un peu de temps, plutôt que de chercher a générer la clef exacte, nous allons seulement générer le premier nombre premier p, et tester si ce nombre divise le n connu; si c'est le cas, le résultat de la division nous donnera le deuxième nombre q.
On commence par extraire le e et le n de la clef ssh, avec
ssh-keygen -e -f authorized_keys -m PKCS8 |openssl rsa -pubin -text
Ceci nous révèle l'exposant 65537 (comme prévu suivant le code de génération) et le module 0xBE2BAC35CA87627AACABC899D4607C3F66EC9C69B4F4121C20E1716A6587E1FDEB84E102173C9DB7C22757254288ABC1AAC22E4CFCF6BEEFF8003DE55CADC17AE6952478861E6415E801E0E3D04AA917188775207F2B53AFB7F948166046DE1CBE31524B61FCFA9414714308FE089464157D977FFE49C995922B95305CE961D3
.On lance le bruteforce avec le script d'attaque suivant:
#!/usr/bin/env python
from time import time
from os import system
from Crypto.PublicKey import pubkey
target = 0xBE2BAC35CA87627AACABC899D4607C3F66EC9C69B4F4121C20E1716A6587E1FDEB84E102173C9DB7C22757254288ABC1AAC22E4CFCF6BEEFF8003DE55CADC17AE6952478861E6415E801E0E3D04AA917188775207F2B53AFB7F948166046DE1CBE31524B61FCFA9414714308FE089464157D977FFE49C995922B95305CE961D3
SEED2 = 0
def randfunc2(n):
def rand():
global SEED2
ret = SEED2 * 0x15a4e35 + 1
SEED2 = ret & 0xffffffff
return (ret >> 0x10) & 0x7fff
ret = ""
while len(ret) < n:
ret += chr(rand() & 0xff)
return ret.encode('latin1')
if __name__ == "__main__":
x = 1373046605
while True:
SEED2 = x
x -= 1
prime = pubkey.getStrongPrime(512, 65537, 1e-12, randfunc2)
if target % prime == 0:
print("BROKEN!!! p={0}".format(prime));
exit(0);
if x % 10 == 0:
En quelque minutes, on obtient les valeurs p = 13097286606179453667665592444299109782484218865253457545521978739889248320232481682880143106432871469494586765663594908396375009598486558938138835723794021 et q = 10196183246368760603869192593971202143897281417220455881063414616103901438182656326076501376638806928762094749150020638960102206987607293047096627515275223
On utilise Crypto.PublicKey.RSA.construct() pour construire la clef, on l'exporte dans un fichier, elle est utilisable directement par openssh.
