How The Columns Have Turned
4 minutos de lectura
Se nos proporciona un código en Python para cifrar la flag (source.py), y también tenemos dialog.txt y encrypted_messages.txt:
import os
with open('super_secret_messages.txt', 'r') as f:
SUPER_SECRET_MESSAGES = [msg.strip() for msg in f.readlines()]
def deriveKey(key):
derived_key = []
for i, char in enumerate(key):
previous_letters = key[:i]
new_number = 1
for j, previous_char in enumerate(previous_letters):
if previous_char > char:
derived_key[j] += 1
else:
new_number += 1
derived_key.append(new_number)
return derived_key
def transpose(array):
return [row for row in map(list, zip(*array))]
def flatten(array):
return "".join([i for sub in array for i in sub])
def twistedColumnarEncrypt(pt, key):
derived_key = deriveKey(key)
width = len(key)
blocks = [pt[i:i + width] for i in range(0, len(pt), width)]
blocks = transpose(blocks)
ct = [blocks[derived_key.index(i + 1)][::-1] for i in range(width)]
ct = flatten(ct)
return ct
class PRNG:
def __init__(self, seed):
self.p = 0x2ea250216d705
self.a = self.p
self.b = int.from_bytes(os.urandom(16), 'big')
self.rn = seed
def next(self):
self.rn = ((self.a * self.rn) + self.b) % self.p
return self.rn
def main():
seed = int.from_bytes(os.urandom(16), 'big')
rng = PRNG(seed)
cts = ""
for message in SUPER_SECRET_MESSAGES:
key = str(rng.next())
ct = twistedColumnarEncrypt(message, key)
cts += ct + "\n"
with open('encrypted_messages.txt', 'w') as f:
f.write(cts)
dialog = "Miyuki says:\n"
dialog += "Klaus it's your time to sign!\n"
dialog += "All we have is the last key of this wierd encryption scheme.\n"
dialog += "Please do your magic, we need to gather more information if we want to defeat Draeger.\n"
dialog += f"The key is: {str(key)}\n"
with open('dialog.txt', 'w') as f:
f.write(dialog)
if __name__ == '__main__':
main()
Miyuki says:
Klaus it's your time to sign!
All we have is the last key of this wierd encryption scheme.
Please do your magic, we need to gather more information if we want to defeat Draeger.
The key is: 148823505998502
ETYDEDTYAATOSTTUFTEETHIVHMVOSFNANDHEGIIIOCESTHTCHDHNRNYALSRPDAIRDCEEIFREEEEOETLRTRNLEEUNBEOIPYLTNOVEOAOTN
EECNEMOTCYSSSEORIRCETFDUCEDAATAPATWTTSKTTRROCEANHHHAIHOGPTTGROIEETURAFYUIPUEEONOISECNJISAFALRIUAVSAAVPDES
GTNOERUTOIAOTIGRESHHBTSEHLORSRSSNTWINTEAUEENTAEEENOICCAFOSHDORLUFHRIALNGOYPNCEIGTAYAPETHCEOUATEFISTFBPSVK
SNUTCAGPEEPWLHITEDFNDMPNWSHFORSLEOAIPTAPEOOOAOTGOSESNADRITRAEREOSSNPECUHSNHENSAATETTPSIUIUOOHPNSKTNIRYHFT
WFAFDDSGIMMYTADNHRENINONSRSUMNITAHIANSUOEMAAEDAIFLOTFINEAYNEGYSNKROEOGFTCTNLYIIOODLOIRERVTAROTRROUNUTFAUP
La idea aquí es programar el algoritmo inverso, vamos a ver qué es lo que hace:
- Genera una semilla con un Generador de Números Pseudo-Aleatorios (Pseudo Random Number Generator, PRNG) y utiliza la siguiente iteración como clave para el algoritmo de cifrado
- Deriva una clave utilizando una función
deriveKey - Separa el mensaje en bloques de la misma anchura
- Transpone los bloques (es decir,
[[1, 2], [3, 4]]se transforma en[[1, 3], [2, 4]]) - Luego coge cada elemento de la clave derivada para ordenar los bloques y revertir cada bloque
- Finalmente, elimina los bloques con la función
flatten(o sea, que[[1, 2], [3, 4]]se transforma en[1, 2, 3, 4])
Vamos a comenzar por analizar la implementación de PRNG:
class PRNG:
def __init__(self, seed):
self.p = 0x2ea250216d705
self.a = self.p
self.b = int.from_bytes(os.urandom(16), 'big')
self.rn = seed
def next(self):
self.rn = ((self.a * self.rn) + self.b) % self.p
return self.rn
La función next está mal hecha, ya que ((self.a * self.rn) + self.b) % self.p es lo mismo que self.b % self.p, y self.b tiene un valor fijo. Por tanto, next siempre devuelve el mismo valor, y tenemos este valor en dialog.txt: 148823505998502.
Ahora, tenemos que invertir el algoritmo de cifrado de twistedColumnarEncrypt:
def twistedColumnarEncrypt(pt, key):
derived_key = deriveKey(key)
width = len(key)
blocks = [pt[i:i + width] for i in range(0, len(pt), width)]
blocks = transpose(blocks)
ct = [blocks[derived_key.index(i + 1)][::-1] for i in range(width)]
ct = flatten(ct)
return ct
Como sabemos la clave, que es siempre la misma, la clave derivada también será siemre la misma. Por tanto, la anchura de los bloques es constante, por lo que podemos empezar separando el texto cifrado en bloques:
def twisted_columnar_decrypt(ct, key):
derived_key = derive_key(key)
width = len(key)
length = len(ct) // len(key)
blocks = [list(ct[i:i + length]) for i in range(0, len(ct), length)]
Nótese que length no es width, debido a la transposición. La relación entre width y length es: len(ct) = length * width.
Ahora, tenemos que asignar el texto claro en el índice de la clave derivada, el bloque correspondiente invertido. Puede ser un poco confuso, pero es solo la operación inversa. Finalmente, hay que transponer los bloques y eliminarlos con flatten:
def twisted_columnar_decrypt(ct, key):
derived_key = derive_key(key)
width = len(key)
length = len(ct) // len(key)
blocks = [list(ct[i:i + length]) for i in range(0, len(ct), length)]
pt = blocks.copy()
for i in range(width):
pt[derived_key.index(i + 1)] = blocks[i][::-1]
pt = transpose(pt)
pt = flatten(pt)
return pt
Solo tenemos que leer los archivos proporcionados y realizar el descifrado. Este es el texto claro:
$ python3 solve.py
THELOCATIONOFTHECONVOYDANTEISDETERMINEDTOBEONTHETHIRDPLANETAFTERVINYRYOUCANUSELIGHTSPEEDAFTERTHEDELIVERYS
THECARGOISSAFEWENEEDTOMOVEFASTCAUSETHERADARSAREPICKINGUPSUSPICIOUSACTIVITYAROUNDTHETRAJECTORYOFTHEPLANETA
BECAREFULSKOLIWHENYOUARRIVEATTHEPALACEOFSCIONSAYTHECODEPHRASETOGETINHTBTHISRNGISNOTSAFEFORGENETINGOUTPUTS
DONTFORGETTOCHANGETHEDARKFUELOFTHESPACESHIPWEDONTWANTANYUNPLEASANTSURPRISESTOHAPPENTHISSERIOUSMISSIONPOPO
IFYOUMESSUPAGAINILLSENDYOUTOTHEANDROIDGRAVEYARDTOSUFFERFROMTHECONSTANTTERMINATIONOFYOURKINDAFINALWARNINGM
$ python3 solve.py | grep -E HTB.+
BECAREFULSKOLIWHENYOUARRIVEATTHEPALACEOFSCIONSAYTHECODEPHRASETOGETINHTBTHISRNGISNOTSAFEFORGENETINGOUTPUTS
Por lo que la flag es:
HTB{THISRNGISNOTSAFEFORGENETINGOUTPUTS}
El script completo se puede encontrar aquí: solve.py.