lundi 8 juillet 2013

SIGINT CTF 2013: RSA

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.