MOCSCTF 2024 Write-Up - One Time Pad Challenge

One Time Pad is a crypto challenge in MOCSCTF 2024. It is a standard Python crypto challenge, which as the name suggests, involves exploiting encryption padding weakness.

This is the problem and solution to the challenge One Time Pad 4, which is the last question in the One Time Pad series and uses all the techniques required in the previous parts.

The Problem

import string
import random
from secret import flag

MIN = 100
MAX = 200

def generate_key(length):
    characters = string.ascii_letters.lower()
    key = ''.join(random.choices(characters, k=length))
    return key

def encrypt(plaintext, key, start_index):
    c = []
    i = 0
    for p in plaintext:
        if start_index + i == len(key):
            start_index = 0
            i = 0
        c.append(ord(p) ^ (ord(key[start_index + i])) % 256)
        i += 1
    return c

def random_replace(origial_key):
    random_num = random.randint(0,26)
    replaced_key = ""
    for char in origial_key:
        replaced_key += chr(((ord(char) - ord('a') + random_num) % 26) + ord('a'))
    return replaced_key


key = generate_key(random.randint(MIN,MAX))

position = 0
enc_flag = encrypt(flag, key, position)
position += len(flag)
print("This is the encrypted flag")
print(enc_flag)
print()
print("******************Welcome to MOCSCTF One-Time Pad Level Four!******************")
ui = ''
while len(ui) <= len(key):
    ui = input("Input your data for encrypt:").rstrip()
    replaced_key = random_replace(key)
    ciphertext = encrypt(ui, replaced_key, position)
    position += len(ui)
    if position > len(key):
        position = position % len(key)
    print("Here you are:",ciphertext)

Observation

In the main loop:

  1. The replace_key is generated every loop based on key
  2. In random_replace function, notice random_num is only generated once, therefore the whole random_replace function is essentially generating a new key by running Caesar cipher on the original key.
  3. The encrypt function itself is trivial to read, it is a performing character-wise XOR between plaintext and key, the start_index is passed in and keeps track of the current character position of key being used and wraps around the key length if it runs over the end
  4. In the main loop there is a similar wrap-around function to update position by + len(ui) then wrap around % len(key)

Therefore, provided that the generated_key is between 100 to 200 characters, we can input a sufficiently long string (400+ characters), and the program will begin to encrypt our known string using character-wise XOR with a Caesar ciphered key, from there we can work backwards finding the ciphered key and subsequently brute force the original key.

Solution

  1. Start by connecting to the challenge server:
┌──(root㉿Eric-PC)
└─# nc 34.150.35.67 30104
This is the encrypted flag
[57, 58, 59, 48, 33, 58, 35, 26, 17, 13, 8, 1, 56, 0, 29, 39, 22, 22, 30, 4, 17, 28]

******************Welcome to MOCSCTF One-Time Pad Level Four!******************
Input your data for encrypt:

Now we know the flag is 22 characters long.

  1. Provide a 1000 characters string of ‘a’s (Tip: generate by running "a"*1000 in python)
Input your data for encrypt:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Here you are: [10, 16, 11, 22, 22, 9, 9, 25, 14, 22, 9, 18, 15, 16, 12, 18, 20, 13, 5, 23, 3, 8, 22, 6, 5, 3, 19, 3, 3, 27, 13, 14, 16, 15, 16, 15, 6, 18, 8, 12, 23, 10, 25, 6, 0, 16, 13, 9, 16, 22, 11, 8, 10, 20, 8, 10, 21, 9, 19, 12, 27, 23, 23, 12, 2, 12, 6, 10, 9, 12, 11, 9, 15, 18, 3, 6, 5, 18, 6, 4, 2, 15, 27, 21, 14, 17, 17, 16, 25, 2, 4, 0, 24, 13, 19, 25, 10, 2, 23, 2, 18, 5, 11, 23, 2, 18, 22, 16, 15, 24, 2, 18, 13, 15, 15, 23, 20, 9, 25, 7, 2, 4, 11, 9, 2, 11, 10, 15, 18, 19, 5, 20, 16, 14, 3, 17, 20, 22, 11, 9, 15, 10, 14, 0, 27, 20, 16, 10, 16, 11, 22, 22, 9, 9, 25, 14, 22, 9, 18, 15, 16, 12, 18, 20, 13, 5, 23, 3, 8, 22, 6, 5, 3, 19, 3, 3, 27, 13, 14, 16, 15, 16, 15, 6, 18, 8, 12, 23, 10, 25, 6, 0, 16, 13, 9, 16, 22, 11, 8, 10, 20, 8, 10, 21, 9, 19, 12, 27, 23, 23, 12, 2, 12, 6, 10, 9, 12, 11, 9, 15, 18, 3, 6, 5, 18, 6, 4, 2, 15, 27, 21, 14, 17, 17, 16, 25, 2, 4, 0, 24, 13, 19, 25, 10, 2, 23, 2, 18, 5, 11, 23, 2, 18, 22, 16, 15, 24, 2, 18, 13, 15, 15, 23, 20, 9, 25, 7, 2, 4, 11, 9, 2, 11, 10, 15, 18, 19, 5, 20, 16, 14, 3, 17, 20, 22, 11, 9, 15, 10, 14, 0, 27, 20, 16, 10, 16, 11, 22, 22, 9, 9, 25, 14, 22, 9, 18, 15, 16, 12, 18, 20, 13, 5, 23, 3, 8, 22, 6, 5, 3, 19, 3, 3, 27, 13, 14, 16, 15, 16, 15, 6, 18, 8, 12, 23, 10, 25, 6, 0, 16, 13, 9, 16, 22, 11, 8, 10, 20, 8, 10, 21, 9, 19, 12, 27, 23, 23, 12, 2, 12, 6, 10, 9, 12, 11, 9, 15, 18, 3, 6, 5, 18, 6, 4, 2, 15, 27, 21, 14, 17, 17, 16, 25, 2, 4, 0, 24, 13, 19, 25, 10, 2, 23, 2, 18, 5, 11, 23, 2, 18, 22, 16, 15, 24, 2, 18, 13, 15, 15, 23, 20, 9, 25, 7, 2, 4, 11, 9, 2, 11, 10, 15, 18, 19, 5, 20, 16, 14, 3, 17, 20, 22, 11, 9, 15, 10, 14, 0, 27, 20, 16, 10, 16, 11, 22, 22, 9, 9, 25, 14, 22, 9, 18, 15, 16, 12, 18, 20, 13, 5, 23, 3, 8, 22, 6, 5, 3, 19, 3, 3, 27, 13, 14, 16, 15, 16, 15, 6, 18, 8, 12, 23, 10, 25, 6, 0, 16, 13, 9, 16, 22, 11, 8, 10, 20, 8, 10, 21, 9, 19, 12, 27, 23, 23, 12, 2, 12, 6, 10, 9, 12, 11, 9, 15, 18, 3, 6, 5, 18, 6, 4, 2, 15, 27, 21, 14, 17, 17, 16, 25, 2, 4, 0, 24, 13, 19, 25, 10, 2, 23, 2, 18, 5, 11, 23, 2, 18, 22, 16, 15, 24, 2, 18, 13, 15, 15, 23, 20, 9, 25, 7, 2, 4, 11, 9, 2, 11, 10, 15, 18, 19, 5, 20, 16, 14, 3, 17, 20, 22, 11, 9, 15, 10, 14, 0, 27, 20, 16, 10, 16, 11, 22, 22, 9, 9, 25, 14, 22, 9, 18, 15, 16, 12, 18, 20, 13, 5, 23, 3, 8, 22, 6, 5, 3, 19, 3, 3, 27, 13, 14, 16, 15, 16, 15, 6, 18, 8, 12, 23, 10, 25, 6, 0, 16, 13, 9, 16, 22, 11, 8, 10, 20, 8, 10, 21, 9, 19, 12, 27, 23, 23, 12, 2, 12, 6, 10, 9, 12, 11, 9, 15, 18, 3, 6, 5, 18, 6, 4, 2, 15, 27, 21, 14, 17, 17, 16, 25, 2, 4, 0, 24, 13, 19, 25, 10, 2, 23, 2, 18, 5, 11, 23, 2, 18, 22, 16, 15, 24, 2, 18, 13, 15, 15, 23, 20, 9, 25, 7, 2, 4, 11, 9, 2, 11, 10, 15, 18, 19, 5, 20, 16, 14, 3, 17, 20, 22, 11, 9, 15, 10, 14, 0, 27, 20, 16, 10, 16, 11, 22, 22, 9, 9, 25, 14, 22, 9, 18, 15, 16, 12, 18, 20, 13, 5, 23, 3, 8, 22, 6, 5, 3, 19, 3, 3, 27, 13, 14, 16, 15, 16, 15, 6, 18, 8, 12, 23, 10, 25, 6, 0, 16, 13, 9, 16, 22, 11, 8, 10, 20, 8, 10, 21, 9, 19, 12, 27, 23, 23, 12, 2, 12, 6, 10, 9, 12, 11, 9, 15, 18, 3, 6, 5, 18, 6, 4, 2, 15, 27, 21, 14, 17, 17, 16, 25, 2, 4, 0, 24, 13, 19, 25, 10, 2, 23, 2, 18, 5, 11, 23, 2, 18, 22, 16, 15, 24, 2, 18, 13, 15, 15, 23, 20, 9, 25, 7, 2, 4, 11, 9, 2, 11, 10, 15, 18, 19, 5, 20, 16, 14, 3, 17, 20, 22, 11, 9, 15, 10, 14, 0, 27, 20, 16, 10, 16, 11, 22, 22, 9, 9, 25, 14, 22, 9, 18, 15, 16, 12, 18, 20, 13, 5, 23, 3, 8, 22, 6, 5, 3, 19, 3, 3, 27, 13, 14, 16, 15, 16, 15, 6, 18, 8, 12, 23, 10, 25, 6, 0, 16, 13, 9, 16, 22, 11, 8, 10, 20, 8, 10, 21, 9, 19, 12, 27, 23, 23, 12, 2, 12, 6, 10, 9, 12, 11, 9, 15, 18, 3, 6, 5, 18, 6, 4, 2, 15, 27, 21, 14, 17, 17, 16, 25, 2, 4, 0, 24, 13, 19, 25, 10, 2, 23, 2, 18, 5, 11, 23, 2, 18, 22, 16, 15, 24, 2, 18, 13, 15, 15, 23, 20, 9]

  1. Identity the Caesar ciphered key. Using a syntax highlighting editor, you can find the Here you are value repeats at [10, 16, 11, 22 …, 0, 27, 20, 16], however since the start_index when encrypting this ‘a’s is 22 because the program has already encrypted the 22-characters flag. Therefore the Caesar-ciphered encryption key responsible for encrypting the original flag actually corresponds to the last 22 characters [11, 10, 15, 18 … 0, 27, 20, 16], i.e. the start of next encryption block.

  2. Create a Python program to reverse the XORs and brute force the Caesar cipher shift amount.

e = [57, 58, 59, 48, 33, 58, 35, 26, 17, 13, 8, 1, 56, 0, 29, 39, 22, 22, 30, 4, 17, 28]
remote_key = [
  k ^ ord('a')  # This 'a' is from our known plaintext made of entirely 'a's
  for k in [11, 10, 15, 18, 19, 5, 20, 16, 14, 3, 17, 20, 22, 11, 9, 15, 10, 14, 0, 27, 20, 16]
]

for shift in range(26):
  replaced_key = [
    ((k - ord('a') + shift) % 26) + ord('a')  # This 'a' is for performing Caesar cipher in lower case space
    for k in remote_key
  ]
  if chr(e[0] ^ replaced_key[0]) == 'M':  # We know the flag starts with MOCSCTF{
    print(''.join(
      chr(e[i] ^ replaced_key[i])
      for i in range(len(e))
    ))

Runs and prints the flag MOCSCTF{hard_to_count}.