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.

jeudi 2 mai 2013

Un élusif problème de DNS

J'ai compris la cause récente du problème récurrent et aléatoire de DNSSEC sur ma zone principale. Comme la plupart du temps, c'est une erreur très bête.

Le programme dnssec-signzone prend en entrée une zone DNS non-signée et produit un fichier de zone augmenté d'enregistrements contenant les signatures. C'est le fichier signé qui est ensuite chargé dans le serveur de noms.

dnssec-signzone dispose d'une option, -N, pour contrôler le numéro de séquence du SOA de la zone. Les valeurs possibles sont "keep" pour conserver le SOA sans modification, "unixtime" pour remplacer le n° de séquence par le temps unix, et "increment" pour incrémenter le numéro de série de la zone.

En effet, lorsqu'on active la signature d'une zone, il est nécessaire de pousser la nouvelle version de la zone, contenant les signatures, et donc d'incrémenter le n° de série.

Ayant auparavant utilisé le format classique de n° de série (année-mois-jour + deux chiffres de série), le timestamp unix ne me convenait pas, j'ai donc utilisé le mode "increment".

Les signatures étant limitées dans le temps, j'ai mis un cron pour resigner périodiquement ma zone.

Lo and Behold, dnssec-signzone en mode incrément, ne contrôle pas le numéro de séquence de l'ancienne zone signée, seulement celle de la zone source. Et comme j'ai deux fichiers séparés, seule la première signature après une mise a jour de la zone disposait d'une signature fraîche. Une fois le premier round de signatures expirées, les suivantes n'étaient jamais envoyées vers les serveurs esclaves, causant des problèmes aléatoires de signatures invalides. DUH.

Moralité: utiliser le mode Unix Timestamp, ou incrémenter le n° de séquence a la main.