En esta entrada, se presenta una solución al reto HeHeDa, perteneciente a la categoría crypto del SSCTF 2016 Quals. Deseamos que disfruten de su lectura, tanto como nosotros redactándola.

Descripción

La descripción que nos dan es la siguiente:

Primera aproximación

Tras descargarnos un fichero ‘Algorithm1-577265e1.py’. Lo primero que llama la atención es el valor de la variable:

key = bytearray(/*Missed*/)

Lo cual denota, que lo más inmediato es descubrir la key, que con toda seguridad será la usada para cifrar el contenido de:

plain = bytearray("asdfghjk123456")

Además, deja claro que la longitud de la contraseña es de 8 bytes:

assert len(key) == 8

También llama poderosamente la atención, los comentarios que hay al final del fichero:

# out>>

# OO|OO||OO|||||OO|OO||O||O|O||O|||O|OOOOOOO|O|O|O|||||OO|||O|||OO||O|OOOOOO|O|OO|OO||||OO|||OOOO|||||O||||O|OO|O|O|O||OO|O||O|OO|O||O|||O||O|OO|OOOOOO||OOO|O|O|O|||O|OO|O|O||O||O||OOOOO|||OO|O|

# flag >>

# OO||O||O|O|||OOOO||||||O|O|||OOO||O|OOOO||O|O|OO|||||OOOO||||O||OO|OO||O||O|O|O|||||OOOOOO|O|O||OOOOOOO||O|||OOOO||OO|OO|||O|OO|O|||O|O|OO|OOOO|OOO|OOO|OOOO||O|OO||||OO||||OOO|O|O||OO||||O||OOO|||O|OO|OO||OO||OOOO|O|

Un galimatías que recuerda mucho al código binario. De hecho, si nos centramos en la siguiente función:

def encode(p):
    ret = ""
    for i in range(8):
        ret = ('|' if (p >> i) & 1 else 'O') + ret
    return ret

Se ve claramente que es justo eso, un valor codificado a binario en el que el 1 se sustituye por | y el 0 por O.

Troceando el código

Generación de arrays

El próximo paso, es ir viendo sentencia a sentencia que es lo que hace el código para cifrar un texto plano ‘plain’ con una clave ‘key’.

Al realizar esta tarea, en seguida nos damos cuenta de que el algoritmo genera dos arrays de bytes:

t1 = bytearray()
for i in plain:
    t1.append(A[i])

t2 = bytearray()
for i in range(len(t1)):
    t2.append(LShift(t1[i], B[i % 8]))

Arrays cuyo tamaño es determinado por la longitud del texto a cifrar y que son rellenados, a través de las listas A y C, cuyo contenido son 256 bytes (supongo que generados aleatoriamente).

Por tanto, lo importante aquí es que la generación de esos arrays no nos vale para demasiado, pues siempre se generará igual independientemente del texto a cifrar que se le pase (salvo la longitud).

Cifrado

Continuando con el análisis del algoritmo, observamos que de las dos tablas generadas anteriormente, es en t2 en donde se centrará el resto del algoritmo y es en última instancia quien contendrá la cifra.

for times in range(16):
    for i in range(len(t2)):
        t2[i] = C[t2[i]]
    for i in range(len(t2)):
        t2[i] = LShift(t2[i], i ^ D[i % 8])
    for i in range(len(t2)):
        t2[i] ^= key[i % 8]

A priori parece que por cada byte de t2 se realiza una asignación, una operación de desplazamiento y un xor, repetido todo ello 16 veces. Por lo que parece casi imposible poder revertir el algoritmo. Es más, apostaría incluso, que se trata de un ‘algoritmo de una sola vía’. Es decir, que únicamente nos valdría para cifrar, pero no para descifrar.

Sin embargo, en el trozo de código anterior hay un fallo muy grave y no es otro que el de aplicar el proceso de cifrado byte a byte y no por bloques de bytes. Esto, como ya veremos más adelante, nos permitirá someterlo a un ataque por fuerza bruta que nos ayude a descubrir la clave con la cual fue cifrado un texto.

Como prueba de esto, vamos a ejecutar el algoritmo repetidas veces, con las siguientes keys y nos fijaremos en el valor de t2 antes de su codificación:

'aaaaaaaa' => CB 93 7D 3B AF 82 C1 C5 5D 07 9A 54 08 3C
'abaaaaaa' => CB 3F 7D 3B AF 82 C1 C5 5D 2A 9A 54 08 3C
'aabaaaaa' => CB 93 D0 3B AF 82 C1 C5 5D 07 81 54 08 3C

Fases

En este punto, ya podemos intuir que el éxito se obtendrá del desarrollo de dos fases:

Hacer Brute Force para obtener la key
Obtenido el paso 1, hacer Brute Force para obtener la flag.

Fase 1: Obtención de la key

Para poder obtener la key, es necesario tener una cifra y eso es justo lo que nos dan con:

# out>>

# OO|OO||OO|||||OO|OO||O||O|O||O|||O|OOOOOOO|O|O|O|||||OO|||O|||OO||O|OOOOOO|O|OO|OO||||OO|||OOOO|||||O||||O|OO|O|O|O||OO|O||O|OO|O||O|||O||O|OO|OOOOOO||OOO|O|O|O|||O|OO|O|O||O||O||OOOOO|||OO|O|

Como ya comentamos anteriormente, esto no es más que una codificación binaria, de la cual podemos recuperar sus bytes:

26 7C 9B 5B A0 2A F9 DC D0 29 3C E1 F7 A5 59 69 6E D2 06 2A E9 5B 60 E5

Por tanto, lo que hay que hacer es, limitar el algoritmo a una función y devolver t2 en cada llamada:

def algorithm(key):
    A = [85, 128, 177, 163, 7, 242, 231, 69, 185, 1, 91, 89, 80,
. . .
    #key = bytearray(/*Missed*/)

. . .
    for times in range(16):
        for i in range(len(t2)):
            t2[i] = C[t2[i]]
        for i in range(len(t2)):
            t2[i] = LShift(t2[i], i ^ D[i % 8])
        for i in range(len(t2)):
            t2[i] ^= key[i % 8]
    return t2

A esta función, se le pasará una key que irá cambiando byte a byte hasta que tenga una coincidencia con los bytes de la cifra. Como sabemos que ésta es de 8 bytes, tan solo necesitamos los primeros 8 bytes de la cifra (26 7C 9B 5B A0 2A F9 DC).

Para ello, añadimos al script la siguiente porción de código:

# Added ________________________________________________________

outFromAlgorthm = [0x26,0x7C,0x9B,0x5B,0xA0,0x2A,0xF9,0xDC]
index = 0
found = []
for times in xrange(len(outFromAlgorthm)):
    for c in xrange(32, 128):
        key = bytearray('aaaaaaaa')
        key[index] = c
        out = algorithm(key)
        if out[index] == outFromAlgorthm[index]:
            # Use 'times' for handling collisions

            found += [(times, chr(c))]
    index = (index + 1) % len(outFromAlgorthm)
print(found)

y cuya salida al ejecutarlos es:

[(0, '@'), (0, '^'), (1, '&'), (1, 'N'), (2, '#'), (3, 'q'), (4, 'D'), (5, '9'), (5, 'T'), (6, '3'), (7, '_')]

Aunque casi hemos obtenido la key, podemos comprobar como en algunas parte de ella existen colisiones, esto es, que distintos valores obtienen el mismo resultado. En el siguiente diagrama apreciamos mejor la lectura anterior:

¡Es decir, tenemos 8 keys candidatas!:

@&#qD93_
@N#qD93_
@&#qDT3_
@N#qDT3_
^&#qD93_
^&#qDT3_
^N#qD93_
^N#qDT3_

¿Qué podemos hacer? La respuesta es que tan solo tendremos que probar todas en la fase 2 y ver los resultados obtenidos.

Fase 2: Obtención de la Flag

Esta fase, es exactamente igual a la primera, salvo que ahora hay que buscar coincidencias con la Flag en vez de con la key.

Por tanto, modificamos:

la signatura de la función ‘algorithm’ de esta manera:

def algorithm(key, plain):

comentamos la la sentencia de asignación de la variable ‘plain’:

# plain = bytearray("asdfghjk123456")

la flag codificada (27 bytes) que nos dan es esta:

36 B8 7E B8 D0 D4 F8 7B 26 D5 F0 2B 01 B8 64 E9 75 21 11 0D 3C F1 59 EC 74 99 85

modificamos la porción de código que añadimos en la fase 1 de esta manera:

# Added _________________________________________________________

flag = [0x36, 0xB8, 0x7E, 0xB8, 0xD0, 0xD4, 0xF8, 0x7B, 0x26,
        0xD5, 0xF0, 0x2B, 0x01, 0xB8, 0x64, 0xE9, 0x75, 0x21,
        0x11, 0x0D, 0x3C, 0xF1, 0x59, 0xEC, 0x74, 0x99, 0x85]
keys = ['@&#qD93_', '@&#qDT3_', '@N#qD93_', '@N#qDT3_',
        '^&#qD93_', '^&#qDT3_', '^N#qD93_', '^N#qDT3_']
index = 0
for key in keys:
    found = ''
    for times in xrange(len(flag)):
        for c in xrange(32, 128):
            plain = bytearray('aaaaaaaaaaaaaaaaaaaaaaaaaaa')
            plain[index] = c
            out = algorithm(bytearray(key), plain)
            if out[index] == flag[index]:
                found += chr(c)
        index = (index + 1) % len(flag)
    print 'Found {0} chars in {1}'.format(str(len(found)), found)

El resultado obtenido de la ejecución de este script es:

Found 25 chars in SCTF{1qaz9ol.nhy64rfv7um}
Found 23 chars in SCTFg1qaz9olnhy64rf7um}
Found 23 chars in CTF{1qa9ol.nhyW4rfv7u)}
Found 21 chars in CTFg1qa9olnhyW4rf7u)}
Found 27 chars in SSCTF{1qaz9ol.nhy64rfv7ujm}
Found 25 chars in SSCTFg1qaz9olnhy64rf7ujm}
Found 25 chars in SCTF{1qa9ol.nhyW4rfv7uj)}
Found 23 chars in SCTFg1qa9olnhyW4rf7uj)}

Como se aprecia, la única coincidencia que contempla 27 caracteres es:

SSCTF{1qaz9ol.nhy64rfv7ujm}

Descarga en PDF

Si has llegado hata aquí y te ha gustado la entrada, tal vez quieras descargartelo en PDF. En tal caso, puedes hacerlo desde aqui:


	HeHeDa.pdf

EOF

Generalizando, este CTF es sin duda de los más completos y duros. Sin embargo, es ideal para curtirse en este mundillo que a tantos nos apasiona.

Nuestra más sincera enhorabuena a los ganadores y a todos aquellos te@ms españoles que hayan participado en él.

Hay una fuerza motriz más poderosa que el vapor, la electricidad y la energía atómica: la voluntad.

Albert Einstein

Anexo

Algorithm1-577265e1.py

def LShift(t, k):
    k %= 8
    return ((t << k) | (t >> (8 - k))) & 0xff


def encode(p):
    ret = ""
    for i in range(8):
        ret = ('|' if (p >> i) & 1 else 'O') + ret
    return ret


A = [85, 128, 177, 163, 7, 242, 231, 69, 185, 1, 91, 89, 80, 156, 81, 9, 102, 221, 195, 33, 31, 131, 179, 246, 15, 139, 205, 49, 107, 193, 5, 63, 117, 74, 140, 29, 135, 43, 197, 212, 0, 189, 218, 190, 112, 83, 238, 47, 194, 68, 233, 67, 122, 138, 53, 14, 35, 76, 79, 162, 145, 51, 90, 234, 50, 6, 225, 250, 215, 133, 180, 97, 141, 96, 20, 226, 3, 191, 187, 57, 168, 171, 105, 113, 196, 71, 239, 200, 254, 175, 164, 203, 61, 16, 241, 40, 176, 59, 70, 169, 146, 247, 232, 152, 165, 62, 253, 166, 167, 182, 160, 125, 78, 28, 130, 159, 255, 124, 153, 56, 58, 143, 150, 111, 207, 206, 32, 144,
     75, 39, 10, 201, 204, 77, 104, 65, 219, 98, 210, 173, 249, 13, 12, 103, 101, 21, 115, 48, 157, 147, 11, 99, 227, 45, 202, 158, 213, 100, 244, 54, 17, 161, 123, 92, 181, 243, 184, 188, 84, 95, 27, 72, 106, 192, 52, 44, 55, 129, 208, 109, 26, 24, 223, 64, 114, 19, 198, 23, 82, 120, 142, 178, 214, 186, 116, 94, 222, 86, 251, 36, 4, 248, 132, 25, 211, 199, 30, 87, 60, 127, 155, 41, 224, 151, 237, 136, 245, 37, 170, 252, 8, 42, 209, 46, 108, 88, 183, 149, 110, 66, 235, 229, 134, 73, 38, 118, 236, 119, 154, 216, 217, 240, 22, 121, 174, 93, 126, 230, 228, 18, 148, 220, 172, 2, 137, 34]

B = [0, 2, 3, 7, 1, 5, 6, 4]

C = [179, 132, 74, 60, 94, 252, 166, 242, 208, 217, 117, 255, 20, 99, 225, 58, 54, 184, 243, 37, 96, 106, 64, 151, 148, 248, 44, 175, 152, 40, 171, 251, 210, 118, 56, 6, 138, 77, 45, 169, 209, 232, 68, 182, 91, 203, 9, 16, 172, 95, 154, 90, 164, 161, 231, 11, 21, 3, 97, 70, 34, 86, 124, 114, 119, 223, 123, 167, 47, 219, 197, 221, 193, 192, 126, 78, 39, 233, 4, 120, 33, 131, 145, 183, 143, 31, 76, 121, 92, 153, 85, 100, 52, 109, 159, 112, 71, 62, 8, 244, 116, 245, 240, 215, 111, 134, 199, 214, 196, 213, 180, 189, 224, 101, 202, 201, 168, 32, 250, 59, 43, 27, 198, 239, 137, 238, 50,
     149, 107, 247, 7, 220, 246, 204, 127, 83, 146, 147, 48, 17, 67, 23, 93, 115, 41, 191, 2, 227, 87, 173, 108, 82, 205, 49, 1, 66, 105, 176, 22, 236, 29, 170, 110, 18, 28, 185, 235, 61, 88, 13, 165, 188, 177, 230, 130, 253, 150, 211, 42, 129, 125, 141, 19, 190, 133, 53, 84, 140, 135, 10, 241, 222, 73, 12, 155, 57, 237, 181, 36, 72, 174, 207, 98, 5, 229, 254, 156, 178, 128, 55, 14, 69, 30, 194, 122, 46, 136, 160, 206, 26, 102, 218, 103, 139, 195, 0, 144, 186, 249, 79, 81, 75, 212, 234, 158, 163, 80, 226, 65, 200, 38, 187, 113, 63, 24, 25, 142, 51, 228, 35, 157, 216, 104, 162, 15, 89]

D = [2, 4, 0, 5, 6, 7, 1, 3]


plain = bytearray("asdfghjk123456")
key = bytearray(/*Missed*/)
assert len(key) == 8
t1 = bytearray()
for i in plain:
    t1.append(A[i])
t2 = bytearray()
for i in range(len(t1)):
    t2.append(LShift(t1[i], B[i % 8]))
for times in range(16):
    for i in range(len(t2)):
        t2[i] = C[t2[i]]
    for i in range(len(t2)):
        t2[i] = LShift(t2[i], i ^ D[i % 8])
    for i in range(len(t2)):
        t2[i] ^= key[i % 8]
out = ""
for i in t2:
    out += encode(i)
print out


# out>>

# OO|OO||OO|||||OO|OO||O||O|O||O|||O|OOOOOOO|O|O|O|||||OO|||O|||OO||O|OOOOOO|O|OO|OO||||OO|||OOOO|||||O||||O|OO|O|O|O||OO|O||O|OO|O||O|||O||O|OO|OOOOOO||OOO|O|O|O|||O|OO|O|O||O||O||OOOOO|||OO|O|

# flag >>

# OO||O||O|O|||OOOO||||||O|O|||OOO||O|OOOO||O|O|OO|||||OOOO||||O||OO|OO||O||O|O|O|||||OOOOOO|O|O||OOOOOOO||O|||OOOO||OO|OO|||O|OO|O|||O|O|OO|OOOO|OOO|OOO|OOOO||O|OO||||OO||||OOO|O|O||OO||||O||OOO|||O|OO|OO||OO||OOOO|O|

SSCTF 2016 - Crypto 100 - HeHeDa WriteUp