← Retour à CryptoHack

CryptoHack | Cofactor Cofantasy

•6 min•Difficile

Cofactor Cofantasy

Énoncé du challenge Cofactor Cofantasy sur CryptoHack

Le challenge propose un service qui renvoie une valeur différente selon le bit du flag demandé. Si le bit vaut 1 on reçoit une puissance de g modulo N. Si le bit vaut 0 on reçoit un entier aléatoire.

Le but est de distinguer ces deux cas pour reconstruire le flag bit par bit.

Comprendre le service

On connaît trois paramètres : N, phi et g. Le modulo N est le produit de 16 nombres premiers sûrs. La valeur phi correspond à l'indicatrice d'Euler de N.

Pour demander un bit on envoie un objet JSON avec son indice :

query = {"option": "get_bit", "i": i}

Si le bit vaut 1 le serveur choisit un exposant aléatoire r et renvoie :

h=gr mod Nh = g^r \bmod N

Sinon il renvoie un entier aléatoire entre 1 et N - 1.

La réponse contient une clé bit mais sa valeur est un entier hexadécimal. Ce n'est pas directement le bit recherché :

h = int(response["bit"], 16)

Il faut donc trouver une propriété des puissances de g que les valeurs aléatoires possèdent rarement.

Utiliser la forme des nombres premiers

Un nombre premier sûr s'écrit :

pi=2qi+1p_i = 2q_i + 1

avec q_i également premier. Comme N est le produit de 16 premiers distincts on a :

φ(N)=∏i=116(pi−1)=216∏i=116qi\varphi(N) = \prod_{i=1}^{16}(p_i - 1) = 2^{16}\prod_{i=1}^{16}q_i

On peut retirer cette puissance de deux pour définir :

s=φ(N)216s = \frac{\varphi(N)}{2^{16}}

Pour info : en Python ^ correspond au XOR. Pour calculer une puissance il faut utiliser **.
2 ^ 16 ne donne donc pas 65536.

Pour les paramètres du challenge les tests donnent :

assert pow(g, s, N) != 1
assert pow(g, 2 * s, N) == 1

L'ordre de g divise donc 2s mais ne divise pas s. Ces tests ne suffisent pas à affirmer que son ordre vaut exactement 2s.

Distinguer les deux types de réponses

On élève chaque réponse à la puissance s modulo N :

value = pow(h, s, N)

Si le bit vaut 1 alors h est une puissance de g :

hs≡grs(modN)h^s \equiv g^{rs} \pmod N

Quand r est pair on peut écrire r = 2k. On obtient alors :

hs≡(g2s)k≡1(modN)h^s \equiv (g^{2s})^k \equiv 1 \pmod N

Quand r est impair le résultat vaut g^s qui est différent de 1.

Avec un exposant aléatoire de parité équilibrée une réponse correspondant à un bit 1 passe donc le test environ une fois sur deux.

Pour un bit 0 la valeur est aléatoire. Elle a beaucoup moins de chances de donner 1 après cette exponentiation.

Comprendre la probabilité d'erreur

Modulo chaque premier p_i le groupe multiplicatif possède 2q_i éléments. Pour les facteurs du challenge les q_i sont distincts et s est un multiple impair de chacun d'eux.

L'équation suivante possède alors q_i solutions non nulles modulo p_i :

xs≡1(modpi)x^s \equiv 1 \pmod{p_i}

Cela représente la moitié des éléments non nuls. Pour satisfaire la relation modulo les 16 facteurs à la fois la proportion devient :

1216=165536\frac{1}{2^{16}} = \frac{1}{65536}

Cette proportion concerne les éléments inversibles modulo N. Le serveur tire dans un intervalle qui contient aussi des éléments non inversibles. Ceux-ci ne peuvent pas satisfaire le test. Avec les grands facteurs du challenge la probabilité reste très proche de 1 / 65536.

Une seule réponse ne suffit donc pas pour décider sans erreur. Un bit 1 peut échouer au test et un bit 0 peut le réussir par hasard.

On peut répéter les requêtes sur le même indice et compter les réussites :

def count_hits(get_value, i, s, N, samples=64):
    hits = 0

    for _ in range(samples):
        h = get_value(i)
        if pow(h, s, N) == 1:
            hits += 1

    return hits

get_value(i) représente ici la fonction qui envoie la requête au service et renvoie l'entier reçu.

Avec 64 réponses un bit 1 donne en moyenne 32 réussites. Un bit 0 en donne normalement zéro. Un seuil de quelques réussites permet de limiter les erreurs dans les deux sens.

hits = count_hits(get_value, i, s, N)
bit = int(hits >= 4)

Ce bloc illustre une méthode de décision statistique. Le nombre de requêtes et le seuil peuvent être ajustés selon le temps disponible.

Reconstruire les octets

Les bits sont demandés dans l'ordre du bit de poids faible au bit de poids fort de chaque octet. Il faut donc replacer chaque bit à sa position :

flag = bytearray()

for start in range(0, 344, 8):
    value = 0

    for offset in range(8):
        bit = recover_bit(start + offset)
        value |= bit << offset

    flag.append(value)
    print(f"progress: {start + 8} / 344")

print("flag:", flag.decode())

recover_bit représente la fonction qui décide de la valeur du bit à partir des réponses du serveur.

Le décalage bit << offset place le bit au bon endroit. L'opérateur |= l'ajoute à l'octet en cours.

Les 344 bits correspondent à 43 octets. La progression avance donc de huit bits après chaque octet reconstruit.

Résultat

solve.py termine la récupération des 344 bits :

Exécution du script de Cofactor Cofantasy avec le flag masqué

Conclusion

Les puissances de g et les valeurs aléatoires ne suivent pas la même distribution. La forme des facteurs de N et la connaissance de phi permettent de construire un test modulaire pour les distinguer.

En répétant ce test sur chaque indice on peut retrouver les bits puis reconstruire les octets du flag.

Références

Voir aussi d'autres catégories...

Ces thèmes pourraient aussi t'intéresser.