ångstromCTF 2021 Exclusive Cipher
References
- Szymański, Ł. (2021). ångstromCTF 2021: Exclusive Cipher. szymanski.ninja. https://szymanski.ninja/en/ctfwriteups/2021/angstromctf/exclusive-cipher/
Question
Clam decided to return to classic cryptography and revisit the XOR cipher! Here's some hex encoded ciphertext:
ae27eb3a148c3cf031079921ea3315cd27eb7d02882bf724169921eb3a469920e07d0b883bf63c018869a5090e8868e331078a68ec2e468c2bf13b1d9a20ea0208882de12e398c2df60211852deb021f823dda35079b2dda25099f35ab7d218227e17d0a982bee7d098368f13503cd27f135039f68e62f1f9d3cea7c
The key is 5 bytes long, and the flag is somewhere in the message.
Analysis
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{.
Solution
In an XOR Cipher, it is known that possible_key = ciphertext ^ known_cleartext. The python script attached:
- slices the ciphertext to all possible 5 characters-long (assuming 2 hexadecimal digits are equivalent to 1 ASCII characters) sections,
- computes
possible_key = ciphertext ^ known_cleartext, for a known substring ofactf{, - expands the key to the ASCII length of the message,
- 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.
- recomputes the XOR to possibly decode the message
- 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)):
key_expanded.append(short_key[ii])
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}")
print()
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
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']}")
- 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!
Flag: actf{who_needs_aes_when_you_have_xor}
Top comments (0)