Cybercamp 2019 – Sow Cipher (Criptografia)

CyberCamp 2019

Con esta entrada continuamos con los writeups resolviendo los retos de la fase clasificatoria online de la CyberCamp 2019.
En este caso es un reto de nivel medio de Criptografia.

Enunciado

En este reto nos dan cuatro ficheros:

• cipher.py – una parte del script que se utiliza para encriptar la flag
• given_ciphertext.txt – una muestra cifrada con el mismo script que la flag
• given_plaintext.txt – el texto claro de la muestra anterior
• secret.txt – la flag cifrada

Con estos cuatro ficheros debemos ser capaces de entender cómo funciona el script de encritpado y crear un método para desencriptar la flag.
El código de cipher.py:

#!/usr/bin/python3
import sys, re
from itertools import cycle

class Cipher:

    def __init__(self, text_in, passphrase, n_ops, n_salt, salt):
        self.text_in = text_in
        self.passphrase = passphrase
        self.n_ops = n_ops
        self.n_salt = n_salt
        self.salt = salt

    def bytes_xor(self, text, passwd):
        xor = bytes(x ^ y for x, y in zip(text, cycle(passwd)))
        return xor

    def execute(self):

        if len(self.salt) not in [3] or not re.match("^[A-Z]+$", self.salt.decode()):
            print("Incorrect salt format")
            exit()
        if not re.match("^[a-z]+$", self.passphrase.decode()):
            print("Incorrect passphrase format")
            exit()
        if self.n_ops < 3 and n_salt < 3:
            print("Incorrect cipher params")
            exit()

        salted = self.text_in
        for _ in range(0, self.n_ops):
            for _ in range(0, self.n_salt):
                salted = self.salt + salted
            xor = self.bytes_xor(salted, self.passphrase)
            salted = xor

        result_text = hex(int.from_bytes(xor, 'big'))[2:]
        if len(result_text) % 2 != 0:

given_ciphertext.txt:

2e3d282321322a2b322e3b352f212829263529352929362e41534d50555e535f5a47485c5c4f475d555a4e5a464d5e412f363e24392727373334212f3220332e3a3d21352225312f4a454a4840534f5e405d52415d5440415d524e514a4a5f4a39312631343b262d292e3c2e29272f26323d2a3925243a392f0f05031040161f1b1b054f11060c0f094c180a16481e0e0503461e0f111c0d0d1c0a011c12401a0802130b1b1c0a0e1046180c161b481e1a0a0100150d574c0f0212011d1613571608120a1c480c040e1b0d09145b1c190a0f010c43091a1618121b060d1a481c001a100515080210110d5f0501140f11090c06464e3d1d1b0840100903020d420b0a0e401a09110c161c480d070103080c0c121f4b0610070c4f4011071e0913061b074802141c1209084c020d420c0a0a4c570818035f000c07074f161c12011e4c1b060c090b0a0202155340330a074e0d1d141d4013140f020c11190a430d160a18130a0e0c0f4809100509135b050517070f1a1140061314130e1a0d4e180e071d15121209051742181a0d01030f1f150c4f18011a1b1449060509010e0d161d124f40110710050c4f1b0b054f060c0d101e1e4b1707050f1613570b120c13061b4e1c0a190515135b0d1e04170d5f0d09040f5d0c161b071c0941

given_plaintext.txt:

Lorem ipsum dolor sit amet consectetur adipiscing elit pretium, dapibus purus blandit primis imperdiet suspendisse facilisi. Urna proin cum mollis convallis eros, facilisi mauris in dui, nec odio curae penatibus. Leo erat sociosqu malesuada felis integer quisque parturient penatibus porta fermentum, fames sem semper tempus mollis tellus augue nisi litora.

secret.txt:

2e3d282321322a2b322e3b352f212829263529352929362e41534d50555e535f5a47485c5c4f475d555a4e5a464d5e412f363e24392727373334212f3220332e3a3d21352225312f4a454a4840534f5e405d52415d5440415d524e514a4a5f4a39312631343b262d292e3c2e29272f26323d2a3925243a39050c1601063408580f1a5b27210f3a2837382a2e25583e30170d572e2c085c15

Entendiendo el cifrado

El primer paso es entender cómo funciona el cifrado. Como veis en el código del script, se reciben cuatro argumentos:

def __init__(self, text_in, passphrase, n_ops, n_salt, salt)

En la función execute() vemos que el salt debe ser siempre 3 y letras mayúsculas.

if len(self.salt) not in [3] or not re.match("^[A-Z]+$", self.salt.decode()):
    print("Incorrect salt format")
    exit()

Vemos también que passphrase debe ser minúscula y que n_ops y n_salt deben ser, al menos una, mayor o igual que 3:

if not re.match("^[a-z]+$", self.passphrase.decode()):
    print("Incorrect passphrase format")
    exit()
if self.n_ops < 3 and n_salt < 3:
    print("Incorrect cipher params")
    exit()

Tras superar estas condiciones comienza el cifrado.
Básicamente se trata de un cifrado que añade el salt al texto plano (por la izquierda) tantas veces como n_salt, ejecuta un xor de lo anterior con la passphrase y repite esto tantas veces como n_ops.

salted = self.text_in
for _ in range(0, self.n_ops):
    for _ in range(0, self.n_salt):
        salted = self.salt + salted
    xor = self.bytes_xor(salted, self.passphrase)
    salted = xor

result_text = hex(int.from_bytes(xor, 'big'))[2:]

Rompiendo el cifrado

Para poder descifrar secret.txt debemos conocer el valor de las variables que se usaron para encriptarlo (salt, n_salt, n_ops, passphrase).
Sabemos que el salt es una palabra de tres caracteres asi que podemos calcular n_ops * n_salt restando el tamaño de los ficheros cifrado y en plano:

Vemos que n_ops * n_salt * 3 = 120, es decir, que n_ops * n_salt = 40.

El siguiente paso es ser capaces de calcular n_ops o n_salt. Esto se puede hacer aprovechando que la passphrase debe ser minúsculas mientras que el salt es mayúscula.
En diversas fuentes vemos que las mayúsculas tiene el bit 0x20 activo (= 1) mientras que las minúsculas no (= 0). Si ejecutamos “letra mayúscula” & 0x20 = 0x20 pero si “letra minuscula” & 0x20 = 0:

Entonces en la primera iteración se ejecuta XOR entre los salt (mayúscula) y la passphrase (minúscula), el resultado será un caracter que no tenga el bit 0x20 activo.
En la siguiente iteración se ejecutará XOR entre dichos caracteres con el bit 0x20 desactivado (=0) y la passphrase (minúsuclas) y el resultado será un caracter con el bit 0x20 activo.
Quizás esto parece un poco lioso, con un ejemplo se ve más facilmente:

Con esta premisa podemos calcular el tamaño de n_salt:

Obtenemos secuencias de 24 “0x20” (32 en decimal) y 24 “0”. Esto nos indica que en cada iteración se han añadido 24 / 3 = 8 salts –> n_salt = 8. 8 * n_ops = 40
Entonces ya tendremos n_salt = 8, n_ops = 5 y nos falta passphrase.

Cada 24 caracteres se ha ejecutado el XOR asi que podemos calcular facilmente la passphrase. Basta con ejecutar XOR cada 24 caracteres del texto cifrado:

Así hemos sido capaces de obtener el passphrase: “honestlythisisnotsogood”.
Ahora con el mismo código de cifrado podemos obtener la flag (con cualquier salt ya que solo nos intersa el texto plano):

#!/usr/bin/env python3
import sys, re
from itertools import cycle

class Cipher:

    def __init__(self, text_in, passphrase, n_ops, n_salt, salt):
        self.text_in = text_in
        self.passphrase = passphrase
        self.n_ops = n_ops
        self.n_salt = n_salt
        self.salt = salt

    def bytes_xor(self, text, passwd):
        xor = bytes(x ^ y for x, y in zip(text, cycle(passwd)))
        return xor

    def execute(self):

        if len(self.salt) not in [3] or not re.match("^[A-Z]+$", self.salt.decode()):
            print("Incorrect salt format")
            exit()
        if not re.match("^[a-z]+$", self.passphrase.decode()):
            print("Incorrect passphrase format")
            exit()
        if self.n_ops < 3 and n_salt < 3:
            print("Incorrect cipher params")
            exit()

        salted = self.text_in
        for _ in range(0, self.n_ops):
            for _ in range(0, self.n_salt):
                salted = self.salt + salted
            xor = self.bytes_xor(salted, self.passphrase)
            salted = xor

        result_text = hex(int.from_bytes(xor, 'big'))[2:]
        return result_text

with open("secret.txt", "r") as f:
    ct = bytes.fromhex(f.read())
    c = Cipher(text_in=ct[120:], passphrase=b"honestlythisisnotsogood", n_ops=5, n_salt=8, salt=b"AAA").execute()
    print(bytes.fromhex(c))