/den/face0xff/writeups
  • Introduction
  • 2023
    • FCSC 2023
      • Hola Amigo (reverse)
      • Picasso (reverse)
  • 2022
    • Root-Me 10K CTF
      • chef's kiss
    • FCSC 2022
      • httpd (pwn)
      • Hyper Packer (reverse)
      • Khal Hash (crypto)
    • Hackday Qualifications 2022
      • Cubik'cipher
    • DiceCTF 2022
      • cable management
  • 2021
    • Aero CTF 2021
      • Not received prize
    • FCSC 2021
      • Shared Notes (web, 500)
      • BattleChip (misc, 495)
    • UIUCTF 2021
      • phpfuck_fixed
  • 2020
    • FCSC Prequals 2020
      • Keykoolol (reverse, 500)
      • Macaron (crypto, 200)
      • Merry (crypto, 500)
      • SSEcret (reverse, 500)
      • Why not a sandbox? (pwn, 500)
    • European Cyber Week CTF Qualifiers 2020
      • Antirdroid
      • Windtalkers
    • DefCamp CTF 2020
      • dumb-discord, spy agency, cross me, syntax check
    • ångstromCTF 2020
      • RSA-OTP
  • 2019
    • ECW Quals 2019
      • S3cr37 4g3nt
    • X-MAS CTF 2019
      • FUNction Plotter
      • Emu 2.0
    • Square CTF 2019
      • Go Cipher
    • Byte Bandits CTF 2019
      • babycrypto
    • Securinets Prequals 2019
      • Beginner's Luck
    • STEM CTF 2019
      • QvR Code
      • REbase
    • Pragyan CTF 2019
      • Decode This
      • Save Earth
      • Super Secure Vault
    • CTFZone 2019
      • Agents
Powered by GitBook
On this page
  • Description du challenge
  • Solution

Was this helpful?

  1. 2020
  2. FCSC Prequals 2020

Merry (crypto, 500)

Description du challenge

Un serveur a été conçu pour utiliser un algorithme d'échange de clés avec ses clients. Cet algorithme génère et garde le même bi-clé pour plusieurs requêtes. Il notifie aussi ses clients quand l'échange a échoué et que la clé partagée n'est pas la même. Votre but est de retrouver la clé secrète du bi-clé généré par le serveur.

Service : nc challenges1.france-cybersecurity-challenge.fr 2001

Note : La version de Python utilisée par le serveur est 3.5.3 (default, Sep 27 2018, 17:25:39) [GCC 6.3.0 20170516]

Solution

Le challenge a pour tag post-quantum mais il ne faut pas se laisser impressionner, aucune connaissance en crytographie quantique n'est nécessaire pour résoudre ce challenge. Il faut juste savoir faire du calcul matriciel de base 😃

Voici le code du serveur :

import sys
import numpy as np
from flag import flag
from zlib import compress, decompress
from base64 import b64encode as b64e, b64decode as b64d

class Server:
    def __init__(self, q, n, n_bar, m_bar):
        self.q     = q
        self.n     = n
        self.n_bar = n_bar
        self.m_bar = m_bar
        self.__S_a = np.matrix(np.random.randint(-1, 2, size = (self.n, self.n_bar)))
        self.__E_a = np.matrix(np.random.randint(-1, 2, size = (self.n, self.n_bar)))
        self.A     = np.matrix(np.random.randint( 0, q, size = (self.n, self.n)))
        self.B     = np.mod(self.A * self.__S_a + self.__E_a, self.q)

    ### Private methods
    def __decode(self, mat):
        def recenter(x):
            if x > self.q // 2:
                return x - self.q
            else:
                return x

        def mult_and_round(x):
            return round((x / (self.q / 4)))

        out = np.vectorize(recenter)(mat)
        out = np.vectorize(mult_and_round)(out)
        return out

    def __decaps(self, U, C):
        key_a = self.__decode(np.mod(C - np.dot(U, self.__S_a), self.q))
        return key_a

    ### Public methods
    def pk(self):
        return self.A, self.B

    def check_exchange(self, U, C, key_b):
        key_a = self.__decaps(U, C)
        return (key_a == key_b).all()

    def check_sk(self, S_a, E_a):
        return (S_a == self.__S_a).all() and (E_a == self.__E_a).all()

def menu():
    print("Possible actions:")
    print("  [1] Key exchange")
    print("  [2] Get flag")
    print("  [3] Exit")
    return int(input(">>> "))

if __name__ == "__main__":

    q     = 2 ** 11
    n     = 280
    n_bar = 4
    m_bar = 4

    server = Server(q, n, n_bar, m_bar)

    A, B = server.pk()
    print("Here are the server public parameters:")
    print("A = {}".format(b64e(compress(A.tobytes())).decode()))
    print("B = {}".format(b64e(compress(B.tobytes())).decode()))

    nbQueries = 0
    while True:
        try:
            choice = menu()
            if choice == 1:
                nbQueries += 1
                print("Key exchange #{}".format(nbQueries), file = sys.stderr)
                U     = np.reshape(np.frombuffer(decompress(b64d(input("U = "))), dtype = np.int64), (m_bar, n))
                C     = np.reshape(np.frombuffer(decompress(b64d(input("C = "))), dtype = np.int64), (m_bar, n_bar))
                key_b = np.reshape(np.frombuffer(decompress(b64d(input("key_b = "))), dtype = np.int64), (m_bar, n_bar))

                if server.check_exchange(U, C, key_b):
                    print("Success, the server and the client share the same key!")
                else:
                    print("Failure.")

            elif choice == 2:
                S_a = np.reshape(np.frombuffer(decompress(b64d(input("S_a = "))), dtype = np.int64), (n, n_bar))
                E_a = np.reshape(np.frombuffer(decompress(b64d(input("E_a = "))), dtype = np.int64), (n, n_bar))

                if server.check_sk(S_a, E_a):
                    print("Correct key, congratulations! Here is the flag: {}".format(flag))
                else:
                    print("Sorry, this is not the correct key.")
                    print("Bye bye.")
                    exit(1)

            elif choice == 3:
                print("Bye bye.")
                break

        except:
            pass

L'idée est que l'on peut demander autant de fois que l'on veut au serveur un "key exchange", qui est un oracle à réponse binaire. Le but du challenge est de déterminer deux paramètres privés SaS_aSa​ et EaE_aEa​.

A l'initialisation, le serveur pose q=211q = 2^{11}q=211, n=280n = 280n=280, nbar=mbar=4n_{bar} = m_{bar} = 4nbar​=mbar​=4 et génère deux clés privées SaS_aSa​ et EaE_aEa​ à valeurs dans {−1,0,1}\{-1,0,1\}{−1,0,1} (oui, 2 est exclu, le randint de numpy n'agit pas comme le randint vanilla... !!). SaS_aSa​ et EaE_aEa​ sont de dimensions (n,nbar)(n, n_{bar})(n,nbar​).

Enfin, AAA et BBB sont deux matrices publiques. AAA est générée aléatoirement à valeurs dans {0, ..., q}\{0, \:..., \: q\}{0,...,q} et est de taille (n,n)(n, n)(n,n) ; BBB satisfait la relation suivante :

B:=(ASa+Ea) mod  qB := (A S_a + E_a) \: \mod{q}B:=(ASa​+Ea​)modq

Étudions maintenant check_exchange. Le serveur nous demande UUU, une matrice (mbar,n)(m_{bar}, n)(mbar​,n), CCC, une matrice (mbar,nbar)(m_{bar}, n_{bar})(mbar​,nbar​), et keyb\text{key}_bkeyb​, une matrice aussi (mbar,nbar)(m_{bar}, n_{bar})(mbar​,nbar​).

Il vérifie alors si :

decode((C−USa)mod  q)=keyb\text{decode}((C - U S_a) \mod{q}) = \text{key}_bdecode((C−USa​)modq)=keyb​

decode est une fonction qui recentre les valeurs de la matrice autour de 0 (pour qu'elles passent entre −q/2-q/2−q/2 et q/2q/2q/2 environ) puis les divise par q/4q/4q/4 et les arrondit, ce qui donne une matrice à valeurs dans {−2,−1,0,1,2}\{-2, -1, 0, 1, 2\}{−2,−1,0,1,2}.

Si l'on arrive à retrouver SaS_aSa​, il sera aisé de calculer EaE_aEa​. Alors comment choisir les paramètres pour faire fuiter de l'information sur SaS_aSa​ ?

Ma solution (il y a certainement plusieurs techniques) est de poser C=0C = 0C=0 et de choisir U=λE1,jU = \lambda E_{1, j}U=λE1,j​, où λ\lambdaλ est un coefficient entier à paramétrer et Ei,jE_{i,j}Ei,j​ sont les matrices de la base canonique (des zéros partout, sauf un 1 en (i,j)(i, j)(i,j)).

Ainsi, on aura :

C−USa=−USa=−λE1,jSa=[−λSa,j000]∈M4,4({0, ..., q−1}) mod  qC - U S_a = -U S_a = -\lambda E_{1, j} S_a = \begin{bmatrix} & -\lambda S_{a, j} & \\ & 0 & \\ & 0 & \\ & 0 & \end{bmatrix} \in \mathcal{M}_{4, 4}(\{ 0, \:..., \: q - 1\}) \: \mod{q}C−USa​=−USa​=−λE1,j​Sa​=​​−λSa,j​000​​​∈M4,4​({0,...,q−1})modq

où Sa,jS_{a, j}Sa,j​ est la j-ème ligne de SaS_aSa​ (qui contient 4 valeurs entre -1 et 1).

Les valeurs subissant dans decode la division par q/4q/4q/4, on voit l'importance du facteur λ\lambdaλ. En effet, sans, les coefficients 000 et 111 de la matrice obtenue se feraient arrondir à 0 et on ne pourrait plus les distinguer.

Je pose maintenant λ=q/4=512\lambda = q/4 = 512λ=q/4=512 qui donne des résultats intéressants. En effet, en raisonnant coefficient par coefficient dans la matrice, on a, en partant d'un coefficient de Sa,jS_{a,j}Sa,j​ :

  • 000 reste 000, est recentré en 000 et est arrondi à 000

  • 111 devient −512≡1536 mod  q-512 \equiv 1536\:\mod{q}−512≡1536modq, est recentré en −512-512−512 et est arrondi à −1-1−1

  • −1-1−1 devient 512512512, est recentré en 512512512 et est arrondi à 111

Il suffit donc de prendre l'opposé du résultat pour obtenir la valeur d'origine. Il ne reste plus qu'à challenger l'oracle en brute-forçant toutes les matrices 4×44 \times 44×4 dont la première ligne est à valeurs dans {−1,0,1}\{-1, 0, 1\}{−1,0,1} (donc 34=813^4 = 8134=81 requêtes dans le pire cas) jusqu'à ce qu'on nous réponde succès, ce qui nous permet d'identifier une ligne de SaS_aSa​.

On répète cela n=280n = 280n=280 fois (soit 226802268022680 requêtes dans le pire cas) et on a réussi à déterminer SaS_aSa​. Il ne reste plus qu'à utiliser :

Ea≡B−ASa mod  qE_a \equiv B - A S_a \: \mod{q}Ea​≡B−ASa​modq

et à soumettre la réponse (Sa, Ea)(S_a, \:E_a)(Sa​,Ea​) au serveur.

Voici l'exploit :

from pwn import *
import numpy as np
from zlib import compress, decompress
from base64 import b64encode as b64e, b64decode as b64d
from itertools import product

q = 2 ** 11
n = 280
n_bar = 4

LAMBDA = 512

s = remote('challenges1.france-cybersecurity-challenge.fr', 2001)

msg = s.recvuntil(b'Possible actions')
s.recv(1024)

A = msg.split(b'A = ')[1].split(b'\n')[0]
B = msg.split(b'B = ')[1].split(b'\n')[0]

A = np.reshape(np.frombuffer(decompress(b64d(A)), dtype = np.int64), (n, n))
B = np.reshape(np.frombuffer(decompress(b64d(B)), dtype = np.int64), (n, n_bar))

__S_a = np.zeros((n, n_bar), dtype = np.int64)

s.send(b'1\n')

for k in range(n):
  U = np.zeros((n_bar, n), dtype = np.int64)
  C = np.zeros((n_bar, n_bar), dtype = np.int64)

  U[0][k] = LAMBDA

  U = b64e(compress(U.tobytes()))
  C = b64e(compress(C.tobytes()))

  for c in product([-1, 0, 1], repeat=n_bar):
    CMP = np.zeros((n_bar, n_bar), dtype = np.int64)
    for i in range(n_bar):
      CMP[0][i] = c[i]
    CMP = b64e(compress(CMP.tobytes()))

    s.recv(1024)
    s.send(U + b'\n')

    s.recv(1024)
    s.send(C + b'\n')

    s.recv(1024)
    s.send(CMP + b'\n')

    msg = s.recv(1024)
    s.send(b'1\n')

    if b'Success' in msg:
      break

  for i in range(n_bar):
    __S_a[k][i] = -c[i]

  print("[+] Ligne %s: %s" % (k, repr(__S_a[k])))  

__E_a = np.mod(B - np.dot(A, __S_a), q)

def t(x):
  if x == q - 1:
    return -1
  return x

__S_a = b64e(compress(np.vectorize(t)(__S_a).tobytes()))
__E_a = b64e(compress(np.vectorize(t)(__E_a).tobytes()))

print(__S_a)
print(__E_a)

s.interactive()
s.close()

L'exploit est un peu long, il y a peut-être moyen de faire plus court en répartissant un peu plus l'information à travers les requêtes mais cette méthode est suffisante donc je n'ai pas cherché.

La séquelle de cette épreuve, Pippin, se résolvait de façon exactement similaire, mais il fallait remarquer que SaS_aSa​ avait sur chaque ligne exactement 2 "0", 1 "1" et 1 "-1", ce qui réduit les possibilités et permet de passer en dessous de 3000 requêtes.

Enjoy !

PreviousMacaron (crypto, 200)NextSSEcret (reverse, 500)

Last updated 5 years ago

Was this helpful?