# One Time Pad
## Baby One Time Pad
challenge.py

#!/usr/bin/env python3

# "BabyOneTimePad" challenge for KalmarCTF 2023
# based on "EasyOneTimePad"
# original challenge by shalaamum
# idea to make this easier variant by killerdog

import os

PASS_LENGTH_BYTES = 128

def encrypt_otp(cleartext, key = os.urandom(PASS_LENGTH_BYTES)):
    # key is as long as the cleartext, so as you do not get the key this will be unbreakable!
    ciphertext = bytes([key[i % len(key)] ^ x for i,x in enumerate(cleartext.hex().encode())])
    return ciphertext, key


if __name__ == '__main__':
    print('According to Wikipedia:')
    print('"In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is not smaller than the message being sent."')
    print('So have fun trying to figure out my password!')
    password = os.urandom(PASS_LENGTH_BYTES)

    enc, _ = encrypt_otp(password)
    print(f'Here is my password encrypted with a one-time pad: {enc.hex()}')
    print('Actually, I will give you my password encrypted another time.')
    print('This time you are allowed to permute the password first')
    permutation = input('Permutation: ')
    try:
        permutation = [int(x) for x in permutation.strip().split(',')]
        assert set(permutation) == set(range(PASS_LENGTH_BYTES))
        enc, _ = encrypt_otp(bytes([password[permutation[i]] for i in range(PASS_LENGTH_BYTES)]))
        print(f'Here is the permuted password encrypted with another one-time pad: {enc.hex()}')
    except:
        print('Something went wrong!')
        exit(1)
    password_guess = input('What is my password: ')
    try:
        password_guess = bytes.fromhex(password_guess)
    except:
        print('Something went wrong!')
        exit(1)
    if password_guess == password:
        with open('flag.txt', 'r') as f:
            flag = f.read()
            print(f'The flag is {flag}')
    else:
        print('Nope.')

Đầu tiên, đoạn code khởi tạo một mật khẩu bằng cách sử dụng os.urandom để tạo một chuỗi ngẫu nhiên có độ dài 128 byte.

Sau đó, hàm encrypt_otp được sử dụng để mã hóa chuỗi này bằng OTP. Đầu vào của hàm là mật khẩu và một khóa được tạo ngẫu nhiên có độ dài bằng với mật khẩu. Hàm trả về ciphertext và key

Mã hóa được thực hiện bằng cách XOR từng byte của chuỗi plaintext với từng byte của khóa. Kết quả là một chuỗi byte được mã hóa.

Sau đó, đoạn code cho phép người dùng giải mã chuỗi đã mã hóa bằng cách yêu cầu người dùng nhập chuỗi đã mã hóa dưới dạng chuỗi hex. Nếu chuỗi được giải mã đúng, thì đoạn code sẽ in ra "The flag is ..." nếu không đúng thì sẽ in ra "Nope."

Cuối cùng, đoạn code cho phép người dùng mã hóa lại mật khẩu bằng cách sử dụng một hoán vị cho phép thay đổi vị trí của các byte trong chuỗi mật khẩu. Kết quả được mã hóa bằng một OTP khác. Người dùng được yêu cầu nhập chuỗi đã mã hóa này dưới dạng chuỗi hex và đoạn code sẽ kiểm tra xem chuỗi đã nhập có đúng với mật khẩu đã mã hóa hay không.

Tóm lại, đoạn code thực hiện mã hóa một chuỗi bằng một mã một lần và cho phép người dùng giải mã. Nó cũng cho phép người dùng mã hóa lại mật khẩu bằng cách sử dụng một hoán vị.

Với n = PASS_LENGTH_BYTES = 128
Giả sử biểu thị các byte của mật khẩu thành $P_0,P_1,P_2,...P_{n-1}$ sau khi mã hóa thành hex,ta đặt ${p'}_i$ và ${p}_i$ là 2 byte tương ứng với $P_i$ (${p'}_i$ là 4 bit đầu)

Biểu thị chuỗi byte random thành $r_0,r_1,r_2,...r_{n-1}$
Sau lần mã hóa đầu nhận được $r_0$ ^ ${p'}_0$, $r_1$ ^ $p_0$, ...., $r_{n-2}$ ^ ${p'}_{n/2 - 1}$, $r_{n-1}$ ^ $p_{n/2 - 1}$, $r_0$ ^ ${p'}_{n/2}$, ..., $r_{n-1}$ ^ $p_{n -1}$

| ${p'}_0$ | $p_0$ | ${p'}_1$ | $p_1$ | ... | ${p'}_{n/2-1}$ | $p_{n/2-1}$ | ${p'}_{n/2}$ | $p_{n/2}$ | ... | $p_{n-1}$ |
| -------- | ----- | -------- | ----- | --- | -------------- | ----------- | ------------ | --------- | --- | --- |
| $r_0$ | $r_1$ | $r_2$ | $r_3$ | ... | $r_{n-2}$ | $r_{n-1}$ | $r_0$ | $r_1$ | ... |$r_{n-1}$

Sử dụng hoán vị n-1,0,1,2,...,n-2 Lần mã hóa thứ 2 sẽ trả về
$r_0$ ^ ${p'}_{n-1}$,$r_1$ ^ $p_{n-1}$,$r_3$ ^ ${p'}_0$,$r_4$ ^ $p_0$ ...
Những gì chúng ta có thể làm bây giờ là đoán $r_0$ và $r_1$. Sau đó, từ lần mã hóa đầu tiên, chúng tôi sẽ có thể nhận được ${p'}_0$ và $p_0$ bằng cách xem hai byte đầu tiên. Chuyển sang mã hóa thứ hai, đến lượt chúng ta sẽ có thể sử dụng mã hóa đó để trích xuất $r_2$ và $r_3$ bằng cách xem byte thứ ba và thứ tư. Cứ tiếp tục như vậy ta có thể suy ra toàn bộ khoá. Điều này chỉ yêu cầu một nửa đầu tiên của bản mã (cộng với hai byte thứ hai do hoán vị).
Tiếp theo chúng ta giải 2 bản mã xem có thu được cùng 1 plaintext dạng hex hay không , kiểm tra các kí tự của plaintex xem có từ 0 đến f không.

import itertools
import functools
from pwn import *


PASS_LENGTH_BYTES = 128

def full_key(enc_id, enc_perm, first_kb, second_kb):
    key = bytes([first_kb, second_kb])
    pt_hex = b''
    for i in range((PASS_LENGTH_BYTES // 2) - 1):
        pt_hex += bytes([enc_id[2*i] ^ key[2*i]])
        pt_hex += bytes([enc_id[2*i + 1] ^ key[2*i + 1]])
        key += bytes([enc_perm[2*i + 2] ^ pt_hex[2*i]])
        key += bytes([enc_perm[2*i + 3] ^ pt_hex[2*i + 1]])
    return key

def decrypt(key, enc):
    pt = bytes([key[i % len(key)] ^ x for i,x in enumerate(enc)])
    return pt

remote = pwnlib.tubes.process.process('./challenge.py')
remote.recvuntil(b'pad: ')
enc_id = bytes.fromhex(remote.recvuntil(b'\n').strip().decode())
permutation = [PASS_LENGTH_BYTES - 1] + list(range(PASS_LENGTH_BYTES-1))
to_send = ','.join([str(x) for x in permutation]).encode()
remote.send(to_send + b'\n')
remote.recvuntil(b'pad: ')
enc_perm = bytes.fromhex(remote.recvuntil(b'\n').strip().decode())

pt_hex = None
for first_kb, second_kb in itertools.product(range(256), repeat=2):
    key = full_key(enc_id, enc_perm, first_kb, second_kb)
    pt_from_id_hex = decrypt(key, enc_id)
    pt_from_perm_hex = decrypt(key, enc_perm)
    pt_from_perm_hex = pt_from_perm_hex[2:] + pt_from_perm_hex[:2]
    if pt_from_perm_hex != pt_from_id_hex:
        continue
    pt_hex = pt_from_id_hex
    if not all([x in '0123456789abcdef'.encode() for x in pt_hex]):
        continue
    break
if pt_hex is None:
    exit(0)
remote.recvuntil(b'password: ')
remote.send(pt_hex + b'\n')
print(remote.recvline().strip().decode())

Flag: `kalmar{why_do_default_args_work_like_that_0.0}`

## Easy OTP
challenge.py

import os

PASS_LENGTH_BYTES = 128

def encrypt_otp(cleartext):
    key = os.urandom(len(cleartext))
    ciphertext = bytes([key[i % len(key)] ^ x for i,x in enumerate(cleartext.hex().encode())])
    return ciphertext, key


if __name__ == '__main__':
    print('According to Wikipedia:')
    print('"In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is not smaller than the message being sent."')
    print('So have fun trying to figure out my password!')
    password = os.urandom(PASS_LENGTH_BYTES)

    enc, _ = encrypt_otp(password)
    print(f'Here is my password encrypted with a one-time pad: {enc.hex()}')
    print('Actually, I will give you my password encrypted another time.')
    print('This time you are allowed to permute the password first')
    permutation = input('Permutation: ')
    try:
        permutation = [int(x) for x in permutation.strip().split(',')]
        assert len(permutation) == PASS_LENGTH_BYTES
        assert set(permutation) == set(range(PASS_LENGTH_BYTES))
        enc, _ = encrypt_otp(bytes([password[permutation[i]] for i in range(PASS_LENGTH_BYTES)]))
        print(f'Here is the permuted password encrypted with another one-time pad: {enc.hex()}')
    except:
        print('Something went wrong!')
        exit(1)
    password_guess = input('What is my password: ')
    try:
        password_guess = bytes.fromhex(password_guess)
    except:
        print('Something went wrong!')
        exit(1)
    if password_guess == password:
        with open('flag.txt', 'r') as f:
            flag = f.read()
            print(f'The flag is {flag}')
    else:
        print('Nope.')

Ở challenge này là one time pad không an toàn khi khóa được sử dụng lại và ta có thể khai thác lỗ hổng này để khôi phục bản rõ. Cụ thể, với hai bản mã c1 và c2 được mã hóa bằng cùng một khóa k, ta có thể tính toán XOR của c1 và c2, kết quả là XOR của hai bản rõ p1 và p2. Nếu biết một trong các bản rõ, chẳng hạn như p1, thì chúng ta có thể tính toán bản rõ khác bằng cách XOR p1 với XOR(c1, c2)

$p_2$ = $p_1$ $\oplus$ $c_1$ $\oplus$ $c_2$
Phần viết sau đây giả định rằng PASS_LENGTH_BYTES=32 để minh họa, đối với challenge, PASS_LENGTH_BYTES =128 , nhưng điều này không quan trọng đối với cách thức hoạt động của giải pháp.Trước tiên, mật khẩu được chuyển đổi thành chuỗi hex, tăng gấp đôi độ dài của nó. Sau đó, mỗi byte của chuỗi hex được mã hóa bằng byte tương ứng của khóa bằng XOR. Vì cùng một byte của khóa được sử dụng hai lần để mã hóa một byte của chuỗi hex, nên đây không phải là cách sử dụng an toàn của OTP, vì có thể khôi phục XOR của hai byte văn bản gốc bằng cách XOR các byte bản mã tương ứng với nhau. nếu r là một byte ngẫu nhiên và chúng ta biết $x \oplus r$ và $y \oplus r$, chúng ta có thể phục hồi $x \oplus y = (x \oplus r) \oplus (y \oplus r)$
Điều này cho phép khôi phục một nửa byte sau mật khẩu nếu chúng ta biết nửa đầu và ngược lại
Đặt $x=(x_0, ..., x_{31})$ là một nửa byte sau mật khẩu .

Để khôi phục một nửa byte mật khẩu đầu, ta cần tính XOR của hai bản mã được mã hóa bằng cùng một khóa, được một chuỗi byte. Sau đó, ta có thể dựng một ma trận A trên vành F2[x]/x^8, trong đó phép cộng tương ứng với XOR, sao cho Ax bằng với XOR của hai bản mã, trong đó x là một vectơ của các nửa sau của byte mật khẩu. A là ma trận 16x32 có thể mô tả là ma trận khối (id id), với id là ma trận vuông 16x16 . Điều này là do mỗi byte của mật khẩu có hai nửa và mỗi nửa được XOR với một byte khóa tương ứng. Do đó, XOR của hai bản mã chứa thông tin về cả hai nửa của mỗi byte.

    1 2 ...           32
 1 (1 0 ... 0 1 0 ... 0)
 2 (0 1 ... 0 0 1 ... 0)
 . (          .        )
 . (          .        )
   (          .        )
 16(0 0 ... 1 0 0 ... 1)

Để có được ma trận 32x32 , ta cần thêm 16 hàng khác vào A, bằng cách chọn một hoán vị xen kẽ các chỉ số của một nửa byte sau mật khẩu với các chỉ số của một nửa byte đầu mật khẩu. Sau đó, ta có thể tính XOR của hai bản mã được mã hóa bằng cùng một khóa bằng cách sử dụng hoán vị đã chọn và xây dựng ma trận B 32x32 trên vành F2[x]/x^8 sao cho Bx bằng XOR của hai bản mã sử dụng hoán vị đã chọn, trong đó x là vectơ của tất cả 32 nửa byte sau mật khẩu. Để B có rank(31), ta có thể bổ sung các hàng ,mỗi có các số 0 và đúng hai số 1 như sau:

 
 (1 1 0 0 ... 0 0 0 0 0 0 0 ... 0 0 0)
 (0 0 1 1 ... 0 0 0 0 0 0 0 ... 0 0 0)
 (         .                         )
 (         .                         )
 (0 0 0 0 ... 1 1 0 0 0 0 0 ... 0 0 0)
 (0 0 0 0 ... 0 0 0 1 1 0 0 ... 0 0 0)
 (0 0 0 0 ... 0 0 0 0 0 1 1 ... 0 0 0)
 (                           .       )
 (                           .       )
 (0 0 0 0 ... 0 0 0 0 0 0 0 ... 1 1 0)
 (0 0 0 0 ... 0 0 1 0 0 0 0 ... 0 0 1)

Tương ứng với hoán vị 0,2,...,14,17,...,29,16,1,3,...,15,18,...,30,31
Chọn hoán vị này và đoán x31, chúng ta sẽ có thể xác định tất cả các x0,...,x30 khác từ x31. Nhưng lưu ý rằng tất cả giá trị phải là ký tự ASCII từ '0' đến '9' hoặc 'a' đến 'f'. Vì vậy, chúng ta phải đoán qua tất cả 16 khả năng cho x31 và kiểm tra xem các giá trị tương ứng của x0, ..., x30 có nằm trong tập hợp đó hay không và loại bỏ các giá trị cho x31 trong trường hợp không phải như vậy. Cuối cùng, chúng ta đoán một trong những giá trị có thể còn lại của x31
Hoán vị dùng solve challenge :[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 64, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 127]
Thay vì đoán x31 chúng ta sẽ đoán byte cuối là x127,còn giải pháp thì tương tự phần trình bày ở trên.

solve.py

import itertools
import functools
import sage.all
from sage.rings.finite_rings.finite_field_constructor import FiniteField as GF
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
import pwnlib.tubes.process
import pwnlib.tubes.remote
PASS_LENGTH_BYTES = 128

F = GF(2)
P = PolynomialRing(F, ['x'])


@functools.cache
def int_to_polynomial(value):
    x = P.gens()[0]
    value = int(value)
    assert value >= 0
    result = P(0)
    i = 1
    e = 0
    while i <= value:
        if i & value:
            result += x**e
        i = i << 1
        e += 1
    return result

@functools.cache
def polynomial_to_int(poly):
    return int(poly.change_ring(sage.all.ZZ)(2))

def solve_half(enc_id, enc_perm):
    assert len(enc_id) == PASS_LENGTH_BYTES
    assert len(enc_perm) == PASS_LENGTH_BYTES
    ALLOWED_CHARACTERS = '0123456789abcdef'

    print('Xoring to get relations...')
    target = [enc_id[i] ^ enc_id[i + (PASS_LENGTH_BYTES // 2)]
                     for i in range(0, PASS_LENGTH_BYTES // 2)]
    target += [enc_perm[i] ^ enc_perm[i + (PASS_LENGTH_BYTES // 2)]
                     for i in range(0, PASS_LENGTH_BYTES // 2)]
    print('Constructing target vector without guess in polynomial ring...')
    target = [int_to_polynomial(x) for x in target]
    print('Constructing matrix')
    matrix_rows = []
    for i in range(PASS_LENGTH_BYTES // 2):
        matrix_rows.append(([0]*i + [1] + [0]*((PASS_LENGTH_BYTES // 2) - i - 1)) * 2)
    for i in itertools.chain(
            range(0, (PASS_LENGTH_BYTES // 2) - 1, 2),
            range((PASS_LENGTH_BYTES // 2) + 1, PASS_LENGTH_BYTES - 2, 2)):
        matrix_rows.append([0]*i + [1,1] + [0]*(PASS_LENGTH_BYTES - i - 2))
    matrix_rows.append(
            [0]*(PASS_LENGTH_BYTES // 2) + [1] + [0]*((PASS_LENGTH_BYTES // 2) - 2) + [1])
    matrix_rows.append([0]*(PASS_LENGTH_BYTES - 1) + [1])
    M = sage.all.matrix(P, matrix_rows)
    possible_password = []
    for guess in ALLOWED_CHARACTERS:
        print(f'Guessing "{guess}" for the last byte')
        guess = int_to_polynomial(ord(guess))
        target_vector = sage.all.vector(target + [guess])
        password = []
        for x in M.solve_right(target_vector):
            assert x.is_integral()
            password.append(polynomial_to_int(x.numerator()))
        password = bytes(password)
        if all(chr(x) in ALLOWED_CHARACTERS for x in password):
            print(f'Found possible solution: {password.decode()}')
            possible_password.append(password)
    return possible_password


remote = pwnlib.tubes.process.process('./challenge.py')
remote.recvuntil(b'pad: ')
enc_id = bytes.fromhex(remote.recvuntil(b'\n').strip().decode())
permutation = list(range(0,PASS_LENGTH_BYTES // 2, 2)) \
        + list(range((PASS_LENGTH_BYTES // 2) + 1,PASS_LENGTH_BYTES - 2, 2)) \
        + [PASS_LENGTH_BYTES // 2]
permutation += list(range(1,PASS_LENGTH_BYTES // 2, 2)) \
        + list(range((PASS_LENGTH_BYTES // 2) + 2,PASS_LENGTH_BYTES, 2)) \
        + [PASS_LENGTH_BYTES - 1]
remote.send(','.join([str(x) for x in permutation]).encode() + b'\n')
remote.recvuntil(b'pad: ')
enc_perm = bytes.fromhex(remote.recvuntil(b'\n').strip().decode())

print('Trying to solve for least significant bits...')
lsb = solve_half(enc_id[1::2], enc_perm[1::2])
print(f'Found {len(lsb)} solutions for the least significant bits!')

print('\nTrying to solve for most significant bits...')
msb = solve_half(enc_id[0::2], enc_perm[0::2])
print(f'Found {len(msb)} solutions for the most significant bits!')


lsb = lsb[0].decode()
msb = msb[0].decode()
password = []
for i in range(PASS_LENGTH_BYTES):
    password.append(int(lsb[i],16) + (int(msb[i],16)<<4))
password = bytes(password)
remote.recvuntil(b'password: ')
remote.send(password.hex().encode() + b'\n')
answer = remote.recvuntil(b'\n').decode()
print(answer)

Trying to solve for least significant bits...
Xoring to get relations...
Constructing target vector without guess in polynomial ring...
Constructing matrix
Guessing "0" for the last byte
Guessing "1" for the last byte
Guessing "2" for the last byte
Guessing "3" for the last byte
Guessing "4" for the last byte
Found possible solution: 8e466258f0c7f5b958d9fa4b3bf01946ed1b1517751e34f59d2e7a755bce39a2034080abe16facb3d19e027f9ee53fad08077ee4dafcf94f460e8ceceb388a34
Guessing "5" for the last byte
Guessing "6" for the last byte
Guessing "7" for the last byte
Guessing "8" for the last byte
Guessing "9" for the last byte
Guessing "a" for the last byte
Guessing "b" for the last byte
Guessing "c" for the last byte
Guessing "d" for the last byte
Guessing "e" for the last byte
Guessing "f" for the last byte
Found 1 solutions for the least significant bits!

Trying to solve for most significant bits...
Xoring to get relations...
Constructing target vector without guess in polynomial ring...
Constructing matrix
Guessing "0" for the last byte
Guessing "1" for the last byte
Guessing "2" for the last byte
Guessing "3" for the last byte
Guessing "4" for the last byte
Guessing "5" for the last byte
Guessing "6" for the last byte
Guessing "7" for the last byte
Guessing "8" for the last byte
Guessing "9" for the last byte
Guessing "a" for the last byte
Guessing "b" for the last byte
Guessing "c" for the last byte
Guessing "d" for the last byte
Guessing "e" for the last byte
Guessing "f" for the last byte
Found possible solution: 0ebf7c89dab99f4b46fb2c2e5e13055c97c66654223ebf36dac8cdf814e147cb92671cc743f9fb6f3e24e0871cbbc172fb228f740698d9b69abf773f13ececef
Found 1 solutions for the most significant bits!
The flag is kalmar{guess_i_should_have_read_the_whole_article}