Improper encryption (100pts) - Escape

improper.py

#/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

output

k: ttpisnotsecure
K: aAzJvQkSYJqdHDCTZYQfybziQcYnFGDzeyJsVmZjNSmZnwDmdBiOEcARgrXkxZZYiKwHMooichYwMHXzobYQrwHausuWuvSdzklM
m1: LUYIqlnjuwOCtnYuEQzNtOtZqFamGrnhOlVIbClGipzCjvXahkBrDAGlIlrchpwdbegin{sAldnJfpUGlciN__QTVALdzLCOhPag
m2: HXuQnhlTPpXoeORkmjtUJXvTKJOdiWNgeMxHMCHOkvmBKF}pwdendsXvJxRyClwzDqMBESa__pctf{u_C4nt_s33_m3}__Zlmnop
flag: pctf{u_C4nt_s33_m3}

Problem

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