# Vigenere + CTR Write-up for Tuning Machine

>From: Firebird CTF 2024
>Tags: Crypto
>Problem author: v1nc3
>Problem statement:
>[Everything is in there](https://ash-files.firebird.sh/23/vigctr.py)
>
>Solved by: Jackylkk2003

## Foreword

~~It looks like we have a very wordy problem statement.~~

~~Should this problem also carry a reverse for reversing the encryption?~~

~~Or should it be a misc rev like Math Formula?~~

## Everything that is in "there"

import secrets

SHIFT = 65
MOD = 26
BLOCKLENGTH = 20

def add(block1,block2):
    assert(len(block1)<= len(block2))
    assert(len(block2)<= BLOCKLENGTH)
    b1upper = block1.upper()
    b2upper = block2.upper()
    b1 = [ ord(b1upper[i])-SHIFT for i in range(len(block1))]
    b2 = [ ord(b2upper[i])-SHIFT for i in range(len(block1))]
    s = [ (b1[i] + b2[i]) % MOD for i in range(len(block1))]
    slist = [ chr(s[i]+SHIFT) for i in range(len(block1))]
    sum = ''.join(slist)
    return(sum)

def sub(block1,block2):
    assert(len(block1)<= len(block2))
    assert(len(block2)<= BLOCKLENGTH)
    b1upper = block1.upper()
    b2upper = block2.upper()
    b1 = [ ord(b1upper[i])-SHIFT for i in range(len(block1))]
    b2 = [ ord(b2upper[i])-SHIFT for i in range(len(block1))]
    s = [ (b1[i] - b2[i]) % MOD for i in range(len(block1))]
    slist = [ chr(s[i]+SHIFT) for i in range(len(block1))]
    sum = ''.join(slist)
    return(sum)

def get_blocks(s):
    blocks = []
    i = 0
    while(i + BLOCKLENGTH<len(s)):
        blocks.append(s[i:i+BLOCKLENGTH])
        i = i + BLOCKLENGTH
    blocks.append(s[i:len(s)])
    return(blocks)

def random_block():
    l = []
    for _ in range (BLOCKLENGTH):
        l.append(chr(secrets.randbelow(MOD)+SHIFT))
    b= ''.join(l)
    return(b)


def vigenere_enc(block,key):
    return(add(block,key))

def vigenere_dec(block,key):
    return(sub(block,key))

def ctr(num):
    decimal_num = 0
    power = len(num) - 1
    for digit in num:
        decimal_num += (ord(digit) - ord('A')) * (MOD ** power)
        power -= 1

    decimal_num += 1

    result = ""
    while decimal_num > 0:
        remainder = decimal_num % MOD
        result = chr(remainder + ord('A')) + result
        decimal_num //= MOD

    return(result)

def keygen():
    return(random_block())

def get_iv():
    return(random_block())

def vigenere_ctr_enc(message, key):
    blocks = get_blocks(message)
    nonce = get_iv()
    ctxt = nonce
    for b in blocks:
        to_add = vigenere_enc(nonce, key)
        ctxt += add(b, to_add)
        nonce = ctr(nonce)
    return(ctxt)

def vigenere_ctr_dec(ctxt, key):
    blocks = get_blocks(ctxt)
    nonce = blocks[0]
    ptxt = ""
    for i in range(1, len(blocks)):
        to_add = vigenere_enc(nonce, key)
        ptxt += sub(blocks[i], to_add)
        nonce = ctr(nonce)
    return(ptxt)
        
def read_flag():
    f = open("flag.txt","r")
    flag = f.read()
    f.close()
    return(flag)

if __name__ == "__main__":
    KEY = keygen()
    FLAGTEXT = read_flag()
    CTXT = vigenere_ctr_enc(FLAGTEXT,KEY)
    PTXT = vigenere_ctr_dec(CTXT,KEY)
    assert(PTXT == FLAGTEXT)
    print(CTXT)

# Output : ULDGWMFOXRNTKTVECMMNPQPAJYLJPIXJQUTYRQIQLQSURMZGYUTTPMHOHJAKNQKFFYGTPWXTMFWKHELLZYYFSUDNFKHOZAQIFQDPLUEFFPAILDTXQWWWKIGSVPPTMMWQMODAIBCODZTDSYUQBFSMLSILAZZHVXNTHPUASMZQBBSQZIKHQCLQFQXQAUJGMKACTYBBVMCXUMJOC
# flag is composed of uppercase English characters only without punctuation nor spaces, wrap the flag with 'firebird{...}' before submission

## Observations

1. The functionaility of each function
- add
- Elementwise (without carrying) add 2 blocks and mod MOD.
- Drop the excess characters in block2 if any.
- sub
- Same as add, but do subtraction instead.
- get_blocks
- Split the string into blocks of length (at most) BLOCKLENGTH = 20.
- random_block
- Self explanatory...
- vigenere_enc & vigenere_dec
- Just calls add and sub respectively.
- In encryption For each block, add the block with the key without carrying.
- Decryption do subtraction instead.
- ctr
- Increment a block's rightmost element by 1, with carrying.
- keygen & get_iv
- Just calls random_block.
- vigenere_ctr_enc
- Adds key and an incrementing nonce to the blocks.
- Initial nonce will be prepended to the cipher text
- Nonce is increment by 1 (with carrying) for each block.
- vigenere_ctr_dec
- Decrypts a ciphertext that is encrypted with vigenere_ctr_enc given a key
- read_flag
- Self explanatory
2. Property of the blocks
- We can treat the blocks as base 26 numbers, where A=0, and Z=25
- key = 'A' * 20 basically does nothing.
3. Encryption weakness
- The ctr and nonce part does not make a great difference to the encryption, since we can access the nonce from the ciphertext (The first block, i.e. the first 20 characters).

## Solution

First, we deal with the nonce and ctr part of the encryption. Since this encryption works by summation, it does not matter if we decrypt the vigenere part or ctr part first, or even simultaneously.

We can eliminate the nonce by calling `vigenere_ctr_dec`.

> How? You don't have the key!

`vigenere_ctr_dec` contains 2 parts, eliminating nonce and subtracting the key. We only want the first part. As stated above, a key of 'A' * 20 does nothing, both in encryption and decryption. We can pass it into the decryption function.

import secrets

SHIFT = 65
MOD = 26
BLOCKLENGTH = 20

# The functions are omitted. They are unchanged.

if __name__ == "__main__":
    # KEY = keygen()
    KEY = 'A' * 20
    # FLAGTEXT = read_flag()
    # CTXT = vigenere_ctr_enc(FLAGTEXT,KEY)
    # CTXT is copied from the output.
    CTXT = 'ULDGWMFOXRNTKTVECMMNPQPAJYLJPIXJQUTYRQIQLQSURMZGYUTTPMHOHJAKNQKFFYGTPWXTMFWKHELLZYYFSUDNFKHOZAQIFQDPLUEFFPAILDTXQWWWKIGSVPPTMMWQMODAIBCODZTDSYUQBFSMLSILAZZHVXNTHPUASMZQBBSQZIKHQCLQFQXQAUJGMKACTYBBVMCXUMJOC'
    PTXT = vigenere_ctr_dec(CTXT, KEY)
    # assert(PTXT == FLAGTEXT)
    print(PTXT)

# Output : ULDGWMFOXRNTKTVECMMNPQPAJYLJPIXJQUTYRQIQLQSURMZGYUTTPMHOHJAKNQKFFYGTPWXTMFWKHELLZYYFSUDNFKHOZAQIFQDPLUEFFPAILDTXQWWWKIGSVPPTMMWQMODAIBCODZTDSYUQBFSMLSILAZZHVXNTHPUASMZQBBSQZIKHQCLQFQXQAUJGMKACTYBBVMCXUMJOC
# flag is composed of uppercase English characters only without punctuation nor spaces, wrap the flag with 'firebird{...}' before submission

After running this script, we got the output:
`VFMUNMGVSRKQGBYUPEWDRFPOVAUSBDGAFTMKFXOWTFHZJMBFSFKACMBGFSZWFNVZWIYZITUVPHVEDERZRJBZJDVUOMGEGDBSIWUBBEMNQARCPXQHYIHKBNHLYNRKFTNYOBVSQGEDTLBANERUWAUCEKFXPPPDOQZWLFUKEIESPTNJJFGXTAQCABGIG`

This is still a ciphertext, encrypted with vigenere cipher. That is, each block are added with the key in elementwise manner.

We can put this output into online Vigenere solver, for example, our good friend [dCode](https://www.dcode.fr/vigenere-cipher). We only know the key length = 20, so we set it and decode.

Here is the first result returned.


There are many recognizable words from the text. It is very very likely that we got the correct answer.

So we got the plaintext:
`ISTOLETHISIDEAFROMTHESWITSHEREENDSTHEFLAGSOTHEORIGINALIDEAWASACTUALLYUSINGCBCMODEWITHVIGENERECIPHERFORTHOSEOFYOUWHOHAVEPLAYEDLAKECTFOFLASTYEARYOUSHOULDKNOWANYWAYSBECAREFULWHENUSINGNONCE`.

## Flag

According to the requirements,

>flag is composed of uppercase English characters only without punctuation nor spaces, wrap the flag with 'firebird{...}' before submission

So the flag we found is `firebird{ISTOLETHISIDEAFROMTHESWITSHEREENDSTHEFLAGSOTHEORIGINALIDEAWASACTUALLYUSINGCBCMODEWITHVIGENERECIPHERFORTHOSEOFYOUWHOHAVEPLAYEDLAKECTFOFLASTYEARYOUSHOULDKNOWANYWAYSBECAREFULWHENUSINGNONCE}`.

Submit it and win ~~scores of this challenge~~ wrong flag.

> Looks like the flag is incorrect. It looks so long btw.

With some careful inspection, there is a string `HEREENDSTHEFLAG` in the plaintext.

So the real flag is: `firebird{ISTOLETHISIDEAFROMTHESWITS}`.

## Fun facts

1. I am blind. I cannot see the phrase `HEREENDSTHEFLAG`.
2. Is this even the intended solution?
3. Although we use 'A' * 20 in our solution, any strings with length 20 consisting of all uppercase letters should also be fine.
4. The plaintext (with proper spacing) is `I STOLE THIS IDEA FROM THE SWITS ...`. For some unknown reason, before I wrote this write-up, I have been thinking it is `IS TO LET HIS IDEA FROM THE SWITS ...` and I have been struggling to understand what the first sentence means.
6. Fun fact 2 is not a fact.