> For the complete documentation index, see [llms.txt](https://docs.cooku222.kr/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-no-sub-please.md). # \[DreamHack] No sub please! #### 문제 링크 [ No sub please!AES에서 SubBytes 기능을 없애봤어요! 이 암호는 과연 안전할까요? 주어진 AES.py는 블록암호: AES에 제시된 코드와 동일합니다. Exploit Tech: AES without SubBytes에서 함께 실습하는 문제입니다.dreamhack.io](https://dreamhack.io/wargame/challenges/1120) #### 문제
#### WriteUp \*AES의 SubBytes 단계가 없을 경우에 대한 워게임 해당 문제는 실제 AES와 같은 결과를 내어 알려진 취약점이 존재하지 않는 암호임에 유의할 것 -> secret을 어떻게 복구하는가?에 주안점을 두고 보면 좋을 문제 ``` from AES import AES_implemented import os # For real AES without modification, this challenge is unsolvable with modern technology. # But let's remove a step. ret = lambda x: None AES_implemented._sub_bytes = ret AES_implemented._sub_bytes_inv = ret # Will it make a difference? secret = os.urandom(16) key = os.urandom(16) flag = open("flag.txt", "r").read() cipher = AES_implemented(key) secret_enc = cipher.encrypt(secret) assert cipher.decrypt(secret_enc) == secret print(f"enc(secret) = {bytes.hex(secret_enc)}") while True: option = int(input("[1] encrypt, [2] decrypt: ")) if option == 1: # Encryption plaintext = bytes.fromhex(input("Input plaintext to encrypt in hex: ")) assert len(plaintext) == 16 ciphertext = cipher.encrypt(plaintext) print(f"enc(plaintext) = {bytes.hex(ciphertext)}") if plaintext == secret: print(flag) exit() elif option == 2: # Decryption ciphertext = bytes.fromhex(input("Input ciphertext to decrypt in hex: ")) assert len(ciphertext) == 16 if ciphertext == secret_enc: print("No way!") continue plaintext = cipher.decrypt(ciphertext) print(f"dec(ciphertext) = {bytes.hex(plaintext)}") ``` -> AES 암호에서 SubBytes 과정에 해당하는 \_sub\_bytes 함수를 제거하였고, 복호화 과정에서 SubBytes의 역연산인 \_sub\_bytes\_inv 함수 또한 제거 -> 임의의 16바이트 key를 이용해 secret을 암호화한 암호문이 주어지고, 다음의 두 가지 기능이 주어진다. \- 임의의 16바이트 평문 암호화 \- secret의 암호문을 제외한 임의의 16바이트 암호문 복호화 이 때, secret을 알아내는 것이 목적임 -> 삭제된 SubBytes 과정은 혼돈(Confusion) 성질을 담당함. 이 과정이 사라지게 되면 암호의 평문과 암호문 사이에 선형 관계를 가지게 됨. 혼돈이란? \- 암호화된 결과물(암호문)과 키 사이의 관계를 복잡하게 만드는 것 \=> 암호문에서 키에 대한 정보를 최대한 알 수 없도록 만드는 성질 #### Exploit 선형 관계가 가지는 특징 \- 선형 관계를 가지는 변형 AES 암호의 암호화 함수는 다음과 같은 특징을 지닌다.
a, b는 임의의 16바이트 평문을 의미하고, enc(0)의 0은 16개의 NULL 바이트로 이루어진 평문을 의미함. 위 성질은 복호화 함수 또한 만족함.
-> secret\_enc를 직접 복호화하지 않고도, 다른 암호문들의 복호화 결과를 통해 secret을 복구할 수 있다. 이 성질은 아핀 성질(Affine Property)라고 불림. **아핀 성질(Affine Property)** \- 수학적으로는 선형적 성질에 약간의 상수항이 더해진 형태를 의미함 \- f(x) = Ax+b <- 선형 함수에 상수만 더한 형태
\=>따라서 아래의 식이 성립함.
차분(Difference) 관점으로 식을 변형하면 다음과 같음. 차분은 두 메시지 사이의 차이의 다른 표현이며, 두 메시지를 XOR 연산한 결과값을 가짐.
공통으로 d라는 차분을 가지는 평문쌍을 암호화했을 경우의 암호문의 차분 또한 동일하다. SubBytes가 없는 AES는 평문과 암호문 사이에 상관관계가 명확한, 안전하지 못한 암호임 #### +) Appendix GF(2^128) 유한체 128비트의 선형성 \- SubBytes 과정 없이는, AES 암호는 F2 위에 128개 변수들을 이용해 완벽히 선형적으로 표현할 수 있음. MixColumn 과정에서도 간략하게 설명되었던 F2유한체는 다음과 같은 특징을 가지고 있다. \- 원소가 0과 1로 2개 뿐이고, 2를 modulus로 하는 덧셈 연산과 같은 기능을 가진다. \- XOR 연산이 F2에서는 덧셈으로 정의됨 이 중 둘째 특징을 다음의 표를 통해 확인함.
\- 두 번째 특징에 의해 AddRoundKey 과정에서 XOR연산이 등장함에도 불구하고 암호는 선형 체계를 유지함. 달리 말해, 평문과 암호문의 관계는 확산으로 인한 비트 이동과 F2위에서의 선형합만으로 표현 가능. 평문의 128비트를 F2의 128개의 원소 p0, p1, ..., p127로 표현하고, 암호문의 128비트 또한 c0, c1, ..., c127로 표현하면, 다음을 만족함. \- 0\~127 사이의 모든 i에 대해 키의 값과 관계 없이 ci = a0p0+a1p1+...+a127p127 + k를 만족하는 F2의 상수값 a0, a1, ... , a127이 존재함. \- F2의 변수 K의 값은 AddRoundKey 과정으로부터 결정되며, 암호문의 128개 비트별로 다른 값을 가짐. 따라서, 다음과 같이 표현됨.
i에 0\~127 사이의 모든 값을 대입해 하나의 행렬 방정식으로 구성하면 다음과 같다.
128\*128의 행렬 A는 키의 값과 상관없이 값을 구할 수 있는 행렬임에 주목하자면, 또한 2^128개의 평문과 암호문 쌍이 항상 일대일 대응되므로, A는 역행렬이 존재하는 행렬임. 복호화 과정 또한 c=Ap+k와 같이 선형식으로 표현 가능함. F2 위에서의 연산이기 때문에, 뺄셈은 덧셈과 동일함에 유의하겠습니다.
이와 같이 F2의 원소 128개로 이루어진 유한체를 GF(2^128)또는 F2^128과 같이 쓰임. #### 선형 관계의 확인 \- 임의의 16바이트 키에 대해서도 항상 성립함 ``` from AES import AES_implemented import os ret = lambda x: None AES_implemented._sub_bytes = ret AES_implemented._sub_bytes_inv = ret xor = lambda a, b: bytes([i ^ j for i, j in zip(a, b)]) secret = os.urandom(16) key = os.urandom(16) cipher = AES_implemented(key) for _ in range(1000): a = os.urandom(16) b = os.urandom(16) diff = os.urandom(16) # 1 val1 = xor(cipher.encrypt(a), cipher.encrypt(b)) val2 = xor(cipher.encrypt(xor(a, b)), cipher.encrypt(bytes(16))) assert val1 == val2 # 2 val1 = xor(cipher.decrypt(a), cipher.decrypt(b)) val2 = xor(cipher.decrypt(xor(a, b)), cipher.decrypt(bytes(16))) assert val1 == val2 # 3 val1 = xor(cipher.encrypt(a), cipher.encrypt(xor(a, diff))) val2 = xor(cipher.encrypt(b), cipher.encrypt(xor(b, diff))) assert val1 == val2 # 4 val1 = xor(cipher.decrypt(a), cipher.decrypt(xor(a, diff))) val2 = xor(cipher.decrypt(b), cipher.decrypt(xor(b, diff))) assert val1 == val2 ``` #### Exploit Secret의 복호화
-> 양변에 dec(b)를 XOR 연산해주면 다음과 같다.
\=> 임의의 16바이트 b를 생성하여, dec(0), dex(a XOR b), dec(b)의 결과를 얻은 후, 세 평문을 XOR 연산해주면 dex(a)의 결과를 얻을 수 있다. secret\_enc의 값을 a에 대입하면 secret의 값을 알 수 있다. ``` from pwn import * import os # io = process(["python3", "chall.py"]) io = remote("host3.dreamhack.games", 20224) xor = lambda a, b: bytes([i ^ j for i, j in zip(a, b)]) io.recvuntil(b"= ") secret_enc = bytes.fromhex(io.recvline().decode()) def encrypt(plaintext): io.sendline(b"1") io.sendline(bytes.hex(plaintext).encode()) io.recvuntil(b"= ") ciphertext = bytes.fromhex(io.recvline().decode()) return ciphertext def decrypt(ciphertext): io.sendline(b"2") io.sendline(bytes.hex(ciphertext).encode()) io.recvuntil(b"= ") plaintext = bytes.fromhex(io.recvline().decode()) return plaintext b = os.urandom(16) p1 = decrypt(bytes(16)) p2 = decrypt(xor(secret_enc, b)) p3 = decrypt(b) p = xor(p1, xor(p2, p3)) encrypt(p) io.interactive() ``` --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-no-sub-please.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.