[CODEGATE 2020 예선] Halffeed

문제에서는 halffeed.py와 prob.py라는 두 파이썬 파일이 있었다.

halffeed.py 에는 Halffeed라는 암호화/복호화 방법이 만들어져있고

prob.py에서는 이 암호를 들고와서 문제에서 사용하고 있다.

 

여기서는 우리가 모르고 있는 임의의 16byte 비밀키가 있고 이 키를 이용하여 암호화/복호화를 진행하고 있다

총 3가지 메뉴, Encrypt / Decrypt / Execute 가 있으며,

Encrypt를 한번 실행할 때 마다 카운터가 하나씩 돌면서 nonce가 0부터 하나씩 커져나가기 시작한다.

문제의 목표는 'cat flag'가 포함된 평문에 대한 암호문을 Execute메뉴에서 넣으면, 플래그가 출력된다

 

당연하겠지만, Encrypt에서는 'cat flag'가 포함된 문자열을 입력받게 되면 그대로 종료되는 필터링이 걸려있다.

Encrypt 에서는 입력이 key, nonce, plaintext , 출력이 tag , ciphertext이다.

 

입력에 따라 ciphertext만 바뀌는 것이 아니라 tag라는 값도 바뀌어서 우리는 원하는 plaintext에 대응되는

tag 와 ciphertext를 만들어내야한다.

 

우선 Halffeed의 암호화과정을 살펴보자.

(참고로 AES는 ECB모드를 이용한다)

과정을 보면, 평문이 16바이트가 아니라면, delta라는 변수에 값이 들어가고,

nonce와 키를 AES 암호화를 반복하여 T , K라는 두 값을 만들어 낸다.

이를 이용해서 feed_plus라는 함수로 넘어가서 ciphertext를 만들어내는 과정을 볼 수 있다.

여기서 보면 또 data가 16바이트보다 작을 때 패딩이 일어나는데, 굉장히 신경쓰여서 그냥 항상 data는 16바이트를 주기로 하고, 저 부분들은 무시하기로 했다.

feed_plus를 요약하자면,

암호화 과정에서처럼 입력을 T , plaintext라고 두면,

 

enc_data = T ^ plaintext

tag = T^plaintext[:8] + plaintext[8:] 이다.

 

다시 암호화 과정으로 돌아가보면,  T , block = self.feed_plus(T,plaintext)

즉, 나중 T를 잠시 T'이라고 두면

 

T ' = T ^ plaintext[:8] + plaintext[8:]

block = T ^ plaintext 이다.

 

결국 cipher += T ^ plaintext 가 되는 것이다.

잘 생각해보면,초기 T는 nonce와 secret_key에 의해 결정되는 것이므로

key는 고정되어있고, nonce를 항상 0으로 고정해준다면 초기 T는 상수가 되는 것이다.

그 말은 즉, 위와 같이 plaintext를 0으로 주게 된다면,

ciphertext = T , 즉 초기 T는 항상 88b984e5929369260f24c8e9a74cc38e 가 되는 것이다.

 

이처럼 우리는 암호화에 이용되는 T를 구하기 위해서는 평문의 입력으로 '0'을 넣어주면 된다

이제 우리는, 마음대로 원하는 평문에 대한 ciphertext는 만들 수 있으므로, 남은 것은 tag를 만드는 것이다.

암호화 과정에 대해 살펴보면, 우리는 K라는 값을 사용하는데, 이를 한번 사용하고 다음 반복문을 넘어간다면,

K를 키로 하여, K를 AES암호화 하게 된다.

 

이전의 초기 T를 구할때와 동일하게, nonce만 0으로 고정해준다면, 초기 K도 변하지 않을 것이고,

i번째 K는 항상 상수값으로 일정하다는 것 또한 알 수 있다.

그러면 여기서 이런 생각을 떠올렸다.

 

plaintext 1 = '0' * 16 + ';cat flag;000000' 이라고 했을 때,

이 plaintext를 암호화했을 때 생기는 tag를 만들어보자!

 

tag는 plaintext와의 xor로 만들어지기 때문에 손쉽게 조작할 수 있을 것으로 추측했다.

여기서 블록을 2개로 한 이유는, 1개로 해 버리면 동일 tag를 만들기 위해 동일 plaintext를 입력해야 하는데,

블록을 2개로 해서 첫번째 블록을 거친 후에 2번째 블록을 암호화할 때 사용되는 T값이 다르다면

';cat flag;000000' 와 다른 plaintext를 입력하여 최종적으로 같은 tag를 만들 수 있기 때문이다.

 

T가 변하는 과정을 살펴보면 다음과 같다.

 

초기 T ⇒ T ' ⇒ T_2= AES(T') ⇒ T_2 ' ⇒AES(T_2') ⇒ AES(AES(T_2 '))

 

여기서 마지막에 AES암호화가 2번 있는 것은 최종적으로 tag를 출력할 때 암호화를 한번 거치기 때문이다.

여기서 필자가 하려는 짓은 2개의 plaintext을 만들어서 다음처름 하려고 한다.

 

1번 plaintext : 초기 T ⇒ T(a) ⇒ T_2(a) = AES(T(a)) ⇒ T(c)

2번 plaintext : 초기 T ⇒ T(b) ⇒ T_2(b) = AES(T(b)) ⇒ T(c)

 

1번 plaintext의 1번 블록은 '\x00' * 16 이므로,

2번 plaintext의 1번 블록은 '\x10' + '\x00' * 15 로 하겠다.

우선 우리는 T_2(a) 와 T_2(b)를 구해야 하는데, 이는 이전과 동일하게

그 다음 블록을 0으로 채워버리면 ciphertext에 그 T값이 나올 것이다.

T_2(a) = 0x932f02187cd4bd95352df1a25f633863

T_2(b) = 0x087e8fb8549372c8f7a2ac75559194da

암호화 과정을 다시 들고 와보면

 

T ' = T ^ plaintext[:8] + plaintext[8:]

즉, T(c) = (T_2(a) ^ plaintext)[:8] + plaintext[8:] 인 것이다.

 

여기서부터는 단순 코딩 문제이다.

T(c)를 구한 후, T(c) = T_2(b) ^ plain[:8] + plain[8:] 이므로

 

plain = (T(c) ^ T_2(b))[:8] + T(c)[8:]

tag = 3203fe25e27b4e82f01d1257fbd09480

 

이제, 여기서 구한 2번째 블록에다가 1번째 블록('\x10' + '\x00' * 15)를 붙이고

이 평문에 해당하는 tag를 만들면, 우리가 원하는 tag와 동일한 값이 나올 것이다.

그러면 이제 ciphertext를 만들어 보면,

 

'\x00' * 16에 대한 cipher : 88b984e5929369260f24c8e9a74cc38e

';cat flag;' + '\x00' * 6에 대한 cipher : T_2(a) ^ plaintext

= a84c636c5cb2d1f45216f1a25f633863

 

이 두 블록을 붙여, Execute목록에 넣으면 플래그가 나오게 된다.

(대회가 끝난 후에 서버가 따혀서 flag는 직접 만들어서 로컬에서 작동시킴)