# HalfFeed.encrypt pseudo code
@ Declare
sK <- open('./secretkey', 'rb').read()
N <- b'\x00' * 16
P <- input()
@ Initialize
D <- (len(P) % 16).to_bytes(16, 'little') # if len(P) is 16, equate to N
Kn <- AES(sK, N)
T0 <- AES(Kn, N)
K0 <- AES(Kn, Kn)
if len(P) % 16 != 0 then
P <- P + b'\x01' + b'\x00' * (15 - len(P))
fi
@ Loop
for i <- 0 until i < len(P) / 16 steps i < i + 1
do
if i = 0 then
C0 <- T0 ^ P[ i*16 : (i+1)*16 ]
else
Ci <- C0 + ... + Ci-1 + Ti ^ P[ i*16 : (i+1)*16 ]
fi
Ti+1 <- Ti ^ ( P[ i*16 : i*16+8 ] + Ci[ i*16+8 : (i+1)*16 ] )
Ti+1 <- AES(Ki, Ti+1)
Ki+1 <- AES(Ki, Ki)
end
@ Final
T <- AES(Ki, Ti ^ D)
C <- Ci
return C, T
#0
P0 = b'\x00' * 11 + b';cat '
P1 = b'flag;' + b'\x00' * 11
P2 = b'\x00' * 16
우리는 P0+P1에 대한 암호문 C와 T를 구해야 한다.
임의의 P와 이에 대한 암호문 C를 i >= 0에 대하여 다음과 같이 정의하자.
P_{0}는 P[0:16]이라는 뜻이다.
또한 HalfFeed.encrypt 의사 코드에서 확인한 바 각 루프에서 P_{i}와 xor 되는 T_{i}를 계산하는 식은 다음과 같다.
<<< N이 고정이면 항상 같다.
<<< P_{i-1}의 영향을 받는다.
P_{i} ^ T_{i} = C_{i}이기 때문에 임의의 T_{i}를 구하는 방법은 다음과 같다.
#1
P = P0+P2라 할 때, 이에 대한 암호문 C를 구한다. C_{0}를 C0라고 하자.
또한 P_{0}가 P0일 때 T_{1}은 다음과 같다.
P0로 만들어진 T_{1}이란 의미로 저렇게 이름 지었다.
#2
암호문을 만드는 과정은 P_{i} ^ T_{i}이다. 즉 P=P0+P1에 대한 C_{1}은 다음과 같이 구할 수 있다. 이를 C1이라 하자.
#3
HalfFeed.encrypt 의사 코드에서 붉게 표시한 코드를 전개해 보자.
즉 AES로 암호화하기 전에 평문의 앞 8바이트만 T와 xor 하고 AES로 암호화하는 걸 알 수 있다.
#4
붉게 표시한 T_{i+1}에 내가 원하는 값을 넣을 수 있다면 내가 원하는 T값을 구하는 게 가능해진다. 만약 다음 값을 넣을 수 있다면
P0+P1에 대한 T값을 구할 수 있다. 위 식의 값을 A라고 하자.
#5
이제 임의의 P_{0}에 대한 T_{1}과 A를 xor 한 후, 임의의 P_{0}와 A^T_{1}을 이어 붙여 HalfFeed.encrypt하면 P0+P1에 대한 T를 알 수 있다. 단 이때 A^T_{1}의 앞 8바이트만 취하고, 뒤 8바이트는 모두 널 바이트를 넣는다.
#6
그럼 다음의 과정을 거치게 된다.
@ 1Round
@ 2Round
@ Final
# Solve
P0 = b'\x00' * 11 + b';cat '
P1 = b'flag;' + b'\x00' * 11
P2 = b'\x00' * 16
N = P2
C, T = HF.encrypt(N, P0+P2)
C0 = C[0:16]
T0 = P0 ^ C0
T1 = P2 ^ C[16:32]
C1 = P1 ^ T1
A = C1[0:8] + b'\x00' * 8
_, T2 = HF.encrypt(N, P2+P2)
Z = (T2 ^ A)[0:8] + b'\x00' * 8
C = C0 + C1
N = N
T = HF.encrypt(N, P2+Z)[1]