Writeup "Vinegar Factory" - AngstromCTF 2022

writeup-vinegar_factory.md

Vinegar Factory Crypto Clam managed to get parole for his dumb cryptography jokes, but after making yet another dumb joke on his way out of the courtroom, he was sent straight back in. This time, he was sentenced to 5 years of making dumb Vigenere challenges. Clam, fed up with the monotony of challenge writing, made a program to do it for him. Can you solve enough challenges to get the flag?

Connect to the challenge at nc challs.actf.co 31333. Source

We have a crypto challenge based on the Vigenère cipher: the string is encrypted by using another string as key and for each character, it applies the Caesar cipher using as shift the position of the giver characher in the used alphabet (eg. if the alphabet is made of the regular ascii letters lowercase, the key crypto coincides with applying the Caesar cipher with shift 2-17-24-15-19-14)

By connecting to the server, it sends (49 times) a string made of random noise, followed by a fake flag, the fleg word and other random noise. Before sending it though, it will be encrypted using a random 4 charactes string using the Vigenère cipher.

Our objective is to find for each message the key used to encrypt the message, decrypt the fake flag and sending it back.

Since the key is made by 4 characters and we know that every flag begins and ends with the same 4 charactes, we can get the key by reversing the algorithm and with the now found key, decrypt the message and send the cleartext back.

Also, since we have to identity the where the flag is inside the noise, we can use a regular expression to find a string that CAN be a flag: thanks to the random nature, there can be multiple fake flags, we must find the one that with the same key, correclty decrypts the beginning and the end of the flag with actf and fleg

With this script, we can find (given a possible flag) the key that can decrypt the prefix into actf

alpha = string.ascii_lowercase
off = len(alpha)
def getKey(actf_crypt):
    key = ""
    clear = "actf"
    for (r,c) in zip(actf_crypt, clear):
        #Get the position of the i-th letter for both cleartext and cypthertext
        idxCrypt = alpha.index(r)
        idxClear = alpha.index(c)
        #Get the position of the key by subtracting those values (modulo 26 - the length of the alpha array)
        idxKey = off + idxCrypt - idxClear
        idxKey = idxKey % off
        key += alpha[idxKey]
    return key

By applying this function for each substring found by the regex, we can find which one is the real one by decrypting it with the newfound key and verifying if the postfix is actually fleg

for opt in re.findall(rgx,vig):
    test_key = getKey(opt[:4])
    off2 = len(opt)-4
    decr = decrypt(opt, test_key)
    checkpoint = decr[off2:]
    if(checkpoint == "fleg"):
        ith_fleg = decr[:off2]
if ith_fleg != "":
    sh.sendline(ith_fleg.encode())

The only thing left is the regex to identify the flag: since we don't know the format of the real flag, but only of the fake ones, we need to distinguish the cases:

#Fake flag regex
rgx = "[a-z]{4}\{[a-z_]{10,50}\}[a-z]{4}"
if i == 50:
    #Relaxed regex to catch all the cases
    rgx = "[a-z]{4}\{[0-9A-Za-z_]{5,100}\}[a-z]{4}"

Here you can see the whole exploit:

from pwn import *
import re

i = 1

alpha = string.ascii_lowercase
off = len(alpha)

#Get the key that can decrypt the prefix
def getKey(actf_crypt):
    key = ""
    clear = "actf"
    for (r,c) in zip(actf_crypt, clear):
        idxCrypt = alpha.index(r)
        idxClear = alpha.index(c)
        idxKey = off + idxCrypt - idxClear
        idxKey = idxKey % off
        key += alpha[idxKey]
    return key

def decrypt(message, key):
    ret = ""
    i = 0
    for c in message:
        if c in alpha:
            ret += alpha[(off+alpha.index(c) - alpha.index(key[i])) % len(alpha)]
            i = (i + 1) % len(key)
        else:
            ret += c
    return ret


# sh = process(['python3','main.py'])
sh = remote('challs.actf.co', 31333)
intro = sh.recvline()
print(f"[i] Recv:{intro}")
while( i < 51):
    #Receive the encrypted line
    fleg = sh.recvline()
    vig = fleg.decode()
    print(f"[i] Noise: {fleg[:120]}...")
    vig = vig.split(": ")[1]
    vig = vig.strip("\n")

    ith_fleg = ""

    rgx = "[a-z]{4}\{[a-z_]{10,50}\}[a-z]{4}"
    if i == 50:
        rgx = "[a-z]{4}\{[0-9A-Za-z_]{5,100}\}[a-z]{4}"
        
    for opt in re.findall(rgx,vig):
        #Get the key to decrypt the prefix
        test_key = getKey(opt[:4])
        off2 = len(opt)-4
        #Decrypt the whole possible flag with the given key
        decr = decrypt(opt, test_key)
        checkpoint = decr[off2:]
        #If the postfix is correct
        if(checkpoint == "fleg"):
            ith_fleg = decr[:off2]
            print(f">>\t {opt} - {test_key} ---> {decr} and ends with {decr[off2:]}==fleg")
            break
    print("")
    
    i += 1
    if ith_fleg != "":
        sh.sendline(ith_fleg.encode())
    else:
        print("Can't solve "+vig+"!!!")