Rating:

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`

```python
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`

```python
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:

```python
#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:
```python
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+"!!!")
```

Original writeup (https://gist.github.com/SalScotto/305e809beb45f74180f22463b3a82b3a).