2 minutes
DDC 2023 Regionals - One Time Too Much
We are given a python script that encrypts two strings (both with the flag appended) with a random one time pad:
import os
# read flag in as bytes
with open("flag.txt", "rb") as f:
flag = f.read()
# XOR's two bytestrings together.
def xor(a,b):
xor_result = b''
for i in range(len(a)):
xor_result += bytes([a[i]^b[i]])
return xor_result
# sample a completely random 200 byte one time pad!
one_time_pad = os.urandom(200)
# two similar messages are sent using the same pad.
msg1 = b'was the flag for the challenge ' + flag
msg2 = b'yeah, the flag was definitely ' + flag
enc_msg_1 = xor(msg1,one_time_pad)
enc_msg_2 = xor(msg2,one_time_pad)
# convert bytes to/from hex for easy storage
assert bytes.fromhex(enc_msg_1.hex()) == enc_msg_1
print(f'enc_msg_1 = {enc_msg_1.hex()}')
print(f'enc_msg_2 = {enc_msg_2.hex()}')
and the output of this script:
enc_msg_1 = b3e67510220da045ac68b2d3f5f5c7d4b8cd6c7bb914003103707dc964328221955fc12856efcf6a756147dcef6bb64c23dafb2df3a4f79f32e4791dce3a7f59662ed7e094a0af9b3d7e276e56d3c514ffd050dfa9d6be25e026c3ae
enc_msg_2 = bde267587a45b10daf24b5d8b4f488d1f9ca247afc11013e06687dcb7a77e6219267ce2951f3d246457b46f7df6abd7608c7ff25c99af58833f0741ddb1c524e6223d7f5b2cbe98c3973145c5ed7ca09d3c051d4b3fda321e83eb4
We can most of the one time pad by xoring the known plaintext and ciphertext to recreate it:
def xor(a,b):
xor_result = b''
for i in range(len(a)):
xor_result += bytes([a[i]^b[i]])
return xor_result
msg1 = b'was the flag for the challenge '
enc_msg_1 = bytes.fromhex("b3e67510220da045ac68b2d3f5f5c7d4b8cd6c7bb914003103707dc964328221955fc12856efcf6a756147dcef6bb64c23dafb2df3a4f79f32e4791dce3a7f59662ed7e094a0af9b3d7e276e56d3c514ffd050dfa9d6be25e026c3ae")
otp = xor(msg1, enc_msg_1)
print(otp)
$ python crack_otp.py
b'\xc4\x87\x060Ve\xc5e\xca\x04\xd3\xb4\xd5\x93\xa8\xa6\x98\xb9\x04\x1e\x99whPo\x1c\x18\xa
We still havent recreated enough to decrypt the flag.
We observe that msg1
is one character longer then msg2
:
In [1]: msg1 = b'was the flag for the challenge '
...: msg2 = b'yeah, the flag was definitely '
In [2]: len(msg1)
Out[2]: 31
In [3]: len(msg2)
Out[3]: 30
We can use this extra character to recreate 31 bytes of the one time pad and then use the 31st byte to decrypt the first byte of the appended flag in the second, then add that byte to the first cleartext, calculate the 32nd byte of the one time pad and rinse and repeat this process for all bytes of the flag.
The solve script would look like this:
def xor(a,b):
xor_result = b''
for i in range(len(a)):
xor_result += bytes([a[i]^b[i]])
return xor_result
msg1 = b'was the flag for the challenge '
msg2 = b'yeah, the flag was definitely '
enc_msg_1 = bytes.fromhex("b3e67510220da045ac68b2d3f5f5c7d4b8cd6c7bb914003103707dc964328221955fc12856efcf6a756147dcef6bb64c23dafb2df3a4f79f32e4791dce3a7f59662ed7e094a0af9b3d7e276e56d3c514ffd050dfa9d6be25e026c3ae")
enc_msg_2 = bytes.fromhex("bde267587a45b10daf24b5d8b4f488d1f9ca247afc11013e06687dcb7a77e6219267ce2951f3d246457b46f7df6abd7608c7ff25c99af58833f0741ddb1c524e6223d7f5b2cbe98c3973145c5ed7ca09d3c051d4b3fda321e83eb4")
otp = xor(msg1, enc_msg_1)
for _ in range(len(otp)-1, len(enc_msg_2)):
char = xor(otp, enc_msg_2)[-1].to_bytes(1, 'big')
msg1 += char
otp = xor(msg1, enc_msg_1)
print(f"\notp = {otp}")
print(f"\nmsg1 = {xor(enc_msg_1, otp)}")
print(f"\nmsg2 = {xor(enc_msg_2, otp)}")
$ python solve.py
otp = b'\xc4\x87\x060Ve\xc5e\xca\x04\xd3\xb4\xd5\x93\xa8\xa6\x98\xb9\x04\x1e\x99whPo\x1c\x18\xa7\x03W\xa2e\xd1\x1c\xba\\#\x9d\xa1\x19*\x0e2\xa8\xb0\x04\xd8)|\xae\x92@\x96\xfb\x96\xfcF\x91\x18q\xa2C +\x03O\xbb\x8c\xed\xff\x9b\xe9X\x1fK1;\xb6\xa4z\x8c\x8f\x1f\x91\xec\x89\xcaL\x8dC\xbe\xa4'
msg1 = b'was the flag for the challenge DDC{turns_out_one_time_actually_really_4real_means_ONE_time}\n'
msg2 = b'yeah, the flag was definitely DDC{turns_out_one_time_actually_really_4real_means_ONE_time}\n'
And we got the flag: DDC{turns_out_one_time_actually_really_4real_means_ONE_time}