Can read it better here: [https://gist.github.com/SalScotto/305e809beb45f74180f22463b3a82b3a](https://gist.github.com/SalScotto/305e809beb45f74180f22463b3a82b3a)
> 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](https://en.wikipedia.org/wiki/Vigen%C3%A8re_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`
```pythonalpha = string.ascii_lowercaseoff = 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`
```pythonfor 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:
```python#Fake flag regexrgx = "[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:```pythonfrom pwn import *import re
i = 1
alpha = string.ascii_lowercaseoff = len(alpha)
#Get the key that can decrypt the prefixdef 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+"!!!")```