Problem: [WMCTF 2024]K-Cessation
思路
- 解题大致思路
参考链接：https://blog.xmcve.com/2024/09/10/WMCTF-2024-Writeup/#title-6
根据密文的值，我们可以判断出轮子中部分位置的值是相反的。比如密文第一个值是2，那么说明wheel中第一位和第二位不同
密文第4个值是3，说明wheel中第5，6位和第七位不同。根据这些约束，我们可以解方程得到wheel
from typing import List, Union, Literal from Crypto.Util.number import long_to_bytes import secrets import random, string, re class K_Cessation: ''' ## Background: K-Cessation cipher is a cipher that uses a K bit wheel to pick the next cipher bit from plaintext bit. When encryption starts, the wheel starts at the last bit of the wheel. The wheel loops around when it reaches the end. For every plaintext bit, the wheel is rotated to the next bit in the wheel that matches the plaintext bit, and the distance rotated is appended to the ciphertext. Therefore, if the wheel is not known, it is not possible to decrypt the ciphertext. Or is it? ## Example: To encode "youtu.be/dQw4w9WgXcQ" in 64-Cessation with the wheel 1100011011100011100110100011110110010110010100001011111011111010: 1. convert the plaintext to bits: 01111001 01101111 01110101 01110100 01110101 00101110 01100010 01100101 00101111 01100100 01010001 01110111 00110100 01110111 00111001 01010111 01100111 01011000 01100011 01010001 2. from wheel[-1] to the next "0" bit in the wheel, distance is 3, the current wheel position is wheel[2] 3. from wheel[2] to the next "1" bit in the wheel, distance is 3, the current wheel position is wheel[5] 4. repeat the steps until all bits is encoded 5. the result is 3312121232111411211311221152515233123332223411313221112161142123243321244111111311111112111131113211132412111212112112321122115251142114213312132313311222111112 ## Challenge: A flag is encoded with 64-Cessation cipher. The wheel is not known. The ciphertext is given in ciphertext.txt. The flag is only known to be an ascii string that is longer than 64 characters. No part of the flag is known, which means the flag is NOT in WMCTF{} or FLAG{} format. When submitting, please make the flag in WMCTF{} format. The most significant bit of each byte is flipped with a random bit. You need to extract the flag from the ciphertext and submit it. For your convenience, a salted sha256 hash of the flag is given in flag_hash.txt. ''' def __is_valid_wheel(self): hasZero = False hasOne = False for i in self.wheel: if not isinstance(i, int): raise ValueError("Wheel must be a list of int") if i == 0: hasZero = True elif i == 1: hasOne = True if i > 1 or i < 0: raise ValueError("Wheel must be a list of 0s and 1s") if not hasZero or not hasOne: raise ValueError("Wheel must contain at least one 0 and one 1") def __init__(self, wheel: List[int]): self.wheel = wheel self.__is_valid_wheel() self.state = -1 self.finalized = False def __find_next_in_wheel(self, target: Literal[1, 0]) -> List[int]: result = 1 while True: ptr = self.state + result ptr = ptr % len(self.wheel) v = self.wheel[ptr] if v == target: self.state = ptr return [result] result += 1 def __iter_bits(self, data: bytes): for b in data: for i in range(7, -1, -1): yield (b >> i) & 1 def __check_finalized(self): if self.finalized: raise ValueError("This instance has already been finalized") self.finalized = True def encrypt(self, data: Union[str, bytes]) -> List[int]: self.__check_finalized() if isinstance(data, str): data = data.encode() out = [] for bit in self.__iter_bits(data): rs = self.__find_next_in_wheel(bit) # print(f"bit={bit},rs={rs},state={self.state}") out.extend(rs) return out def decrypt(self, data: List[int]) -> bytes: self.__check_finalized() out = [] for i in data: assert type(i) == int self.state = self.state + i self.state %= len(self.wheel) out.append(self.wheel[self.state]) long = "".join(map(str, out)) return long_to_bytes(int(long, 2)) # generate a random wheel with k bits. def random_wheel(k=64) -> List[int]: return [secrets.randbelow(2) for _ in range(k)] # the most significant bit of each byte is flipped with a random bit. def encode_ascii_with_random_msb(data: bytes) -> bytes: out = bytearray() for b in data: assert b < 128, "not ascii" b = b ^ (0b10000000 * secrets.randbelow(2)) out.append(b) return bytes(out) # for your convenience, here is the decoding function. def decode_ascii_with_random_msb(data: bytes) -> bytes: out = bytearray() for b in data: b = b & 0b01111111 out.append(b) return bytes(out) ct = [2, 1, 1, 3, 1, 1, 3, 2, 1, 4, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 3, 1, 6, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 3, 2, 1, 1, 3, 1, 1, 1, 3, 4, 1, 3, 1, 2, 2, 4, 2, 5, 1, 1, 1, 3, 2, 1, 4, 2, 2, 1, 2, 1, 3, 1, 1, 1, 1, 1, 2, 3, 1, 2, 1, 1, 1, 1, 3, 4, 1, 2, 2, 4, 2, 5, 1, 2, 1, 2, 2, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 4, 3, 1, 2, 1, 3, 1, 3, 3, 2, 1, 3, 1, 6, 2, 1, 1, 2, 1, 2, 1, 3, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 2, 3, 1, 1, 4, 1, 3, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 5, 2, 4, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 3, 1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 5, 1, 1, 1, 3, 1, 1, 2, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 1, 1, 4, 3, 1, 3, 4, 1, 1, 1, 2, 1, 3, 1, 6, 1, 2, 1, 1, 3, 2, 3, 1, 2, 2, 1, 3, 2, 1, 2, 2, 2, 3, 3, 3, 1, 1, 2, 4, 1, 1, 1, 1, 1, 4, 2, 1, 4, 1, 2, 3, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 2, 1, 2, 1, 1, 1, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 4, 2, 1, 4, 2, 4, 2, 2, 3, 1, 2, 2, 2, 1, 3, 3, 1, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 1, 1, 3, 1, 1, 4, 2, 5, 2, 1, 3, 1, 1, 2, 3, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 3, 1, 2, 3, 4, 4, 3, 2, 4, 2, 1, 4, 2, 4, 1, 2, 1, 3, 1, 2, 1, 1, 1, 3, 2, 1, 2, 2, 2, 3, 3, 1, 2, 1, 3, 1, 1, 1, 2, 1, 3, 4, 2, 1, 4, 1, 2, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 4, 2, 1, 4, 1, 1, 1, 1, 2, 4, 4, 3, 2, 4, 2, 1, 1, 1, 1, 1, 1, 1, 4, 2, 2, 3, 1, 1, 1, 2, 1, 3, 1, 4, 1, 2, 4, 1, 2, 3, 4, 1, 3, 1, 1, 1, 2, 4, 1, 1, 1, 4, 1, 1, 4, 2, 1, 4, 2, 2, 1, 1, 1, 1, 1, 2, 3, 2, 1, 4, 3, 3, 4, 4, 3, 2, 4, 2, 1, 1, 3, 2, 4, 1, 1, 2, 3, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 1, 1, 1, 4, 3, 3, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 4, 2, 5, 1, 1, 4, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 2, 1, 2, 4, 3, 1, 1, 1, 1, 3, 4, 3, 1, 1, 4, 1, 6, 2, 1, 1, 1, 3, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 3, 1, 1, 5, 4, 1, 2, 2, 4, 1, 6, 1, 2, 1, 1, 3, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 4, 2, 2, 3, 1, 2, 3, 1, 3, 4, 1, 1, 3, 4, 2, 5, 1, 1, 1, 3, 2, 2, 3, 2, 1, 2, 2, 2, 2, 3, 1, 2, 1, 3, 3, 3, 1, 1, 2, 1, 3, 3, 1, 1, 4, 2, 5, 2, 4, 1, 2, 4, 1, 2, 1, 2, 1, 1, 1, 2, 3, 1, 2, 4, 1, 1, 4, 4, 1, 1, 2, 3, 2, 4, 2, 5, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 2, 1, 1, 3, 1, 1, 2, 1, 2, 3, 1, 1, 1, 3, 4, 1, 1, 2, 1, 1, 1, 2, 4, 2, 1, 1, 3, 1, 2, 1, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 2, 3, 1, 1, 1, 3, 4, 1, 1, 2, 3, 1, 2, 3, 1, 6, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 4, 2, 1, 4, 1, 2, 3, 1, 1, 2, 1] wheels = [( 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1), ( 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0)] for wheel in wheels: c = K_Cessation(wheel) pt = c.decrypt(ct) pt = decode_ascii_with_random_msb(pt) print(pt) """ b';\x10\n\x1d\x13\x1a*\x12<\x0b9$,LL4N18 \x0b\r\nH\x17RH\x17L \x08N\x0cLR\x19N\x11\x1b N\x11JH\x1aK\x1bRNH\x0c \x0f\rO\x19O\n\x11\x1bRK\x1dJ\x1a\x11\x1c\x1a \x11O\x08R\x18O \x0cO\x13\tLR\x0b\x17L L\x06L\x0cRN\x11 1O\x16\x0b\x1e"' b'DoubleUmCtF[S33K1NG_tru7h-7h3_w1s3-f1nd_1n57e4d-17s_pr0f0und-4b5ence_n0w-g0_s0lv3-th3_3y3s-1n_N0ita]' """
EXP
- 具体攻击代码
总结
- 对该题的考点总结