DEV Community

Omri Bornstein
Omri Bornstein

Posted on • Updated on • Originally published at

ångstromCTF Exclusive Cipher

ångstromCTF 2021 Exclusive Cipher



Clam decided to return to classic cryptography and revisit the XOR cipher! Here's some hex encoded ciphertext:

Enter fullscreen mode Exit fullscreen mode

The key is 5 bytes long, and the flag is somewhere in the message.


Assuming 2 hexadecimal digits are equivalent to 1 ASCII characters, a possible key can be found by XORing the ciphertext with the known 5-bytes long substring actf{.


In an XOR Cipher, it is known that possible_key = ciphertext ^ known_cleartext. The python script attached:

  1. slices the ciphertext to all possible 5 characters-long (assuming 2 hexadecimal digits are equivalent to 1 ASCII characters) sections,
  2. computes possible_key = ciphertext ^ known_cleartext, for a known substring of actf{,
  3. expands the key to the ASCII length of the message,
  4. rotates the key to deal with cases where the known clear text is not in an index that is a multiple of the key length.
    • Thanks to @Levon for this suggestion.
  5. recomputes the XOR to possibly decode the message
  6. and prints the possible message as ASCII.

Initial Python Code

from typing import List
from doctest import testmod
from textwrap import wrap

def xor(s: List[int], t: List[int]) -> List[int]:
    :param s: list of non-negative integers
    :param t: list of non-negative integers
    :return: XOR of the ith number of both lists
    return [a ^ b for a, b in zip(s, t)]

def expand_key(short_key: List[int], size: int) -> List[int]:
    :param short_key: list of non-negative integers
    :param size: positive integer
    :return: short_key * (size // len(short_key)) + short_key[:size - len(key_expanded)]

    >>> expand_key([1, 2, 3, 4, 5], 9)
    [1, 2, 3, 4, 5, 1, 2, 3, 4]
    assert size > len(short_key)
    key_expanded = short_key * (size // len(short_key))
    for ii in range(size - len(key_expanded)):
    return key_expanded

ciphertext_text = input("hex-encoded ciphertext: ")
known_cleartext = input("known cleartext (with length of key): ")
hint = input("hint (such as 'flag'): ")

cipher_ascii = [int(letter, 16) for letter in wrap(ciphertext_text, 2)]
known_cleartext_ascii = [ord(letter) for letter in known_cleartext]

for i in range(len(cipher_ascii) - len(known_cleartext)):
    key = xor(cipher_ascii[i:i + len(known_cleartext)], known_cleartext_ascii)
    expanded_key = expand_key(key, len(cipher_ascii))
    message_ascii = xor(cipher_ascii, expanded_key)
    message_text = "".join(map(chr, message_ascii))
    if known_cleartext in message_text and hint in message_text:
        print(f"key: {key} ('{''.join(map(chr, key))}')")
        print(f"message: {message_text}")
Enter fullscreen mode Exit fullscreen mode

Improved Python Code

from typing import TypedDict, List
from textwrap import wrap
from pwn import xor

class XORSolution(TypedDict):
    key: List[int]
    cleartext: str

def decode_xor(ciphertext_hex: str, known_cleartext: str, hint: str) -> List[XORSolution]:
    output = []
    cipher_ascii = bytes(int(letter, 16) for letter in wrap(ciphertext_hex, 2))
    for i in range(len(cipher_ascii)):
        key = list(xor(cipher_ascii[i:i + len(known_cleartext)], known_cleartext.encode()))
        for ii in range(len(key)):
            rotated_key = key[-ii:] + key[:-ii]
            cleartext = str(xor(cipher_ascii, rotated_key))[2:-1]
            if known_cleartext in cleartext and hint in cleartext:
                output.append({"key": rotated_key, "cleartext": cleartext})
    return output
Enter fullscreen mode Exit fullscreen mode

Python Script Output

  • A Python script that prints all valid solutions for the full ciphertext and the ciphertext without the first character:
ciphertext_hex1 = "ae27eb3a148c3cf031079921ea3315cd27eb7d02882bf724169921eb3a469920e07d0b883bf63c018869a5090e8868e331078a68ec2e468c2bf13b1d9a20ea0208882de12e398c2df60211852deb021f823dda35079b2dda25099f35ab7d218227e17d0a982bee7d098368f13503cd27f135039f68e62f1f9d3cea7c"
known_cleartext1 = "actf{"
hint1 = "flag"

for solution in decode_xor(ciphertext_hex1, known_cleartext1, hint1):
    print(f"key: {solution['key']})")
    print(f"message: {solution['cleartext']}")

for solution in decode_xor(ciphertext_hex1[2:], known_cleartext1, hint1):
    print(f"key: {solution['key']})")
    print(f"message: {solution['cleartext']}")
Enter fullscreen mode Exit fullscreen mode
  • The output of the screen described immediately above:
key: [237, 72, 133, 93, 102])
message: Congratulations on decrypting the message! The flag is actf{who_needs_aes_when_you_have_xor}. Good luck on the other crypto!
key: [72, 133, 93, 102, 237])
message: ongratulations on decrypting the message! The flag is actf{who_needs_aes_when_you_have_xor}. Good luck on the other crypto!
Enter fullscreen mode Exit fullscreen mode

Flag: actf{who_needs_aes_when_you_have_xor}

Discussion (0)