Masalah
Pragyan 2018 - Improper encryption (100pts)
Two brothers, Shivam and Mit were fighting for the only computer they had in their house. Watching this their father got angry and locked the computer with a strong password of length 28 which consists of alphabets. To unite them he gave them a puzzle to solve.
He used two random strings and added the half-half of password in each string at some random position. He wanted to apply one-time-pad on both strings . So he used a smaller key 'k' of length 14(contains only english alphabets), and used some pseudo random generator, to get a longer key(K) of suitable size. Then he XOR each string with the generated key(K),and get encrypted message M1, and M2. He gave Shivam M1 and Mit M2 and asked them to find the password.
Also, to help them he also generated a string of suitable size by repeating k several times and then applied one time pad on it by larger key(K) to get M3.
Shivam and Mit come to you with M1, M2, and M3. Help them find the password.
M1=2d142303073d05392c3d3e273c2a1a211f082b280d2d0e332025380301352a122a151c3a342e362d2723171904011c0c0c292b3d0122063e2e1e2a08102a2d3d0b2e102123141c280f0c373d2b380d3d0301301f2d281935233239330f3a102b123b0d2a
M2=29190f1b18390707093a290b2d0b113f37332533333a0c3d1a29160a2f100a1d0034323b1b2e1225252500182531391d13260c21211019242d0a0a123b362d232d3a3a0a083c0e363c183a032b332d252c5637252d047b522a1e462a2a2909081705033d
M3=15350a23053f04272a2f12113a2137202a3022081616090c32162b0b32333413161725072508391f3c36192e1e1e37030b361a2a26163337130628020b34352d1a2e143d3f0a1b1d13012a19223c2b1f0c172b3406033808061d1a2306133011080e1839
First 14 letter of password is: sAldnJfpUGlciN
Penyelesaian
Ini adalah OTP yang dapat diselesaikan dengan teknik Crib Dragging. Lihat petunjunknya disini:
Many time pad crib drag attack.
XOR m1 with m3
XOR 14 length substrings of (m1 XOR m3) with given 14 length password beginning
Check to see if result is alpha
Log all potential seeds (k).
With all potential seeds,
XOR repeating rotated k with m3 to get the OTP (K).
Decrypt m1 and m2 with K.
Check for string pctf in m1 and m2
Solusinya:
#/usr/bin/python3
import re
#
# Many Time Pad Crib Drag
#
# Helper XOR functions
def xor_bytes(m1, m2):
return bytes(a ^ b for a, b in zip(m1, m2))
def repeating_key_xor(a, b):
q, r = divmod(len(a), len(b))
return xor_bytes(a, b * q + b[:r])
# m1 contains the beginning half of the password at a random location
# m1 is m1_decoded XOR K (the OTP)
m1 = bytearray.fromhex(
'2d142303073d05392c3d3e273c2a1a211f082b28'
'0d2d0e332025380301352a122a151c3a342e362d'
'2723171904011c0c0c292b3d0122063e2e1e2a08'
'102a2d3d0b2e102123141c280f0c373d2b380d3d'
'0301301f2d281935233239330f3a102b123b0d2a'
)
# m2 contains the second half of the password at a random location
# m2 is m2_decoded XOR K (the OTP)
m2 = bytearray.fromhex(
'29190f1b18390707093a290b2d0b113f37332533'
'333a0c3d1a29160a2f100a1d0034323b1b2e1225'
'252500182531391d13260c21211019242d0a0a12'
'3b362d232d3a3a0a083c0e363c183a032b332d25'
'2c5637252d047b522a1e462a2a2909081705033d'
)
# m3 contains the seed for K (k) repeated over and over
# m3 is k repeated XOR K (the OTP)
m3 = bytearray.fromhex(
'15350a23053f04272a2f12113a2137202a302208'
'1616090c32162b0b32333413161725072508391f'
'3c36192e1e1e37030b361a2a2616333713062802'
'0b34352d1a2e143d3f0a1b1d13012a19223c2b1f'
'0c172b3406033808061d1a2306133011080e1839'
)
m1_xor_m3 = xor_bytes(m1, m3)
# Known beginning 14 characters of password
known = b'sAldnJfpUGlciN'
# Find potential seeds (k)
guesses = []
for k in range(len(m1_xor_m3)-len(known)+1):
# (m1 XOR m3) substring XOR known gives us a potential k.
res = xor_bytes(known, m1_xor_m3[k:k+len(known)])
# We know that k has to be alpha
if res.isalpha():
guesses.append((res, k))
for guess in guesses:
# Rotate guess based on position
guess = guess[0][0:len(known)-k%len(known)] + guess[0][len(known)-k%len(known):]
# Generate potential OTP
K = repeating_key_xor(m3, guess)
# Decode message with OTP
m1_decoded = xor_bytes(m1, K).decode()
m2_decoded = xor_bytes(m2, K).decode()
# Check if flag is in message
if 'pctf' in m1_decoded+m2_decoded:
print('k:', guess.decode())
print('K:', K.decode())
print('m1:', m1_decoded)
print('m2:', m2_decoded)
print('flag:', re.search('pctf{.+}', m1_decoded+m2_decoded).group(0))
break