HackingCrypto

Codegate CTF 2020 Preliminary - Halffeed (Crypto)

Codegate CTF 2020 Preliminary

문제 파일 (9a7f846af14e09f6b32cff3a648b80f5.zip)

문제에서는 Encrypt, Decrypt, Execute로 총 3가지 기능을 지원한다.

1
2
3
4
5
1) Encrypt
2) Decrypt
3) Execute
4) Exit
>

Encrypt에 평문을 넣으면 암호문과 tag를 알려준다.

1
2
3
plaintext = 414141 <- Input
ciphertext = 6bb0bf
tag = 00ad98235751f8a8bbc89b3f668e87ab

Decrypt에는 암호문, tag, nonce를 같이 입력하면 평문을 알려준다.

1
2
3
4
nonce = 00000000000000000000000000000000  <- Input
ciphertext = 6bb0bf   <- Input
tag = 00ad98235751f8a8bbc89b3f668e87ab  <- Input
plaintext = 414141

Execute는 Decrypt하고 세미콜론을 기준으로 split하고 strip하여 cat flag가 있다면 flag를 출력해준다.

1
2
3
4
5
6
7
8
9
10
11
12
P = halffeed.decrypt(N, C, T)
if P is not None:
    cmds = P.split(b';')
    for cmd in cmds:
        if cmd.strip() == b'cat flag':
            with open('./flag') as f:
                print(f.read())
        else:
            print('[EXCEPTION] Unknown Command')
else:
    print('[EXCEPTION] Authentication Failed')
exit()

하지만 이 문제에서는 Encrypt를 할때 cat flag가 포함된 문자열을 암호화 할 수 없게 제한을 걸었다.

1
2
3
4
5
6
7
def encrypt(halffeed):
    global nonce
    P = recv_data('plaintext')

    if b'cat flag' in P:
        print('[EXCEPTION] Invalid Command "cat flag"')
        exit()

즉, Encrypt 기능과 Decrypt기능을 잘 이용해서 cat flag를 직접 암호화 하지 않으면서 cat flag가 포함된 문자가 포함된 암호문과 tag를 만들어내는것이 목표인 문제다.

암호화 로직 그래프

우선 생각하기 편하게 두 블럭짜리 암호화가 이루어지는 과정을 그림으로 표현을 해보았다.

주어진 정보 정리

  1. 처음 실행하면 nonce는 항상 0부터 시작한다.
  2. secretkey가 항상 동일 하기 때문에 생성되는 K1, K2등의 값들은 항상 동일하다.
  3. 암호문 생성 과정(XOR)과 tag 생성 과정(XOR)이 비슷하다.

공격 방법

Tag값을 직접 계산 가능

우선 xor 연산이기 때문에 plaintext가 00000000000000000000000000000000이라면 ciphertext가 T값이 된다는 것을 알 수 있다.
항상 16의 배수 길이의 문자열을 암호화 한다고 했을때, delta는 항상 0이 되며 이것은 T값을 그대로 F함수에 넣는것과 같게 된다.

편의상 문자열을 절반으로 나누었을때의 결과를 left, right라고 하자.
위에서 얘기했듯이 encryption로직에서 plaintext의 left가 0000000000000000이고, right가 T값의 right가 되어버린다면
Tag값을 계산 하는 로직과 동일한 결과를 낸다. 그렇기 때문에

결국 중요한것은 Tag

각 블럭의 Encryption의 결과로 나오는 T값들은 별로 중요하지 않고 마지막의 Tag만 검증한다.
또한, n번째 plaintext가 동일하더라도 n-1번째 블럭의 plaintext가 다르다면 n-1번째의 결과로 나오는 T값이 달라지기 때문에 n번째의 결과로 나오는 T값도 달라진다.

공격 시나리오

글 작성에 쓰인 secretkey: 31 32 33 34 35 36 37 38 39 30 31 32 33 34 35 0a

  1. 20202020202020202020202020202020 공백 문자열 암호화
    • 결과 : 0ad1de197a3e8cb8037a06a8b3077d2a
  2. 2020202020202020202020202020202000000000000000000000000000000000 두번째 블럭을 NULL로 채운것 암호화
    • 결과 : 0ad1de197a3e8cb8037a06a8b3077d2a9c549497560009b3cdaac0c7e37f334b
    • 두번째 블럭이 encryption에 사용하는 T값이 9c549497560009b3cdaac0c7e37f334b
  3. cat flag의 우측에 공백을 붙인 결과인 63617420666c61672020202020202020 문자열을 암호화 로직을 알기 때문에 직접 암호화 가능
    • 20202020202020202020202020202020 + 63617420666c61672020202020202020
    • = 0ad1de197a3e8cb8037a06a8b3077d2a + (63617420666c61672020202020202020 ^ 9c549497560009b3cdaac0c7e37f334b)
    • = 0ad1de197a3e8cb8037a06a8b3077d2aff35e0b7306c68d4ed8ae0e7c35f136b
  4. tag값을 구해내기 위해서 0000000000000000000000000000000000000000000000000000000000000000를 암호화
    • 첫번째 블럭에 다른 값을 넣게 되면 두번째 블럭으로 들어가는 T값이 달라지는데 이것을 cat flag가 암호화되고 나서 나와야 하는 T값을 cat flag를 입력하지 않고 나오게 하는데 이용할 수 있다.
    • 결과 : 2af1fe395a1eac98235a268893275d0ad59d3df3d55baeb797f3350fb3f83f60
    • 두번째 블럭이 암호화에 사용하는 T값이 d59d3df3d55baeb797f3350fb3f83f60
  5. 3번의 문자열을 넣었을때 결과로 나오는 T값을 직접 계산하고, 앞 블럭이 공백이 아닌 널문자일때 앞에서 구한 T값이 나오게 하는 plaintext를 계산
    • 3번의 input값의 T값 결과 : (9c549497560009b3^63617420666c6167) + 2020202020202020
    • = ff35e0b7306c68d42020202020202020
    • 앞 블럭이 널문자인 경우 암호화에 사용하는 T값이 d59d3df3d55baeb797f3350fb3f83f60이기 때문에, T값 결과가 ff35e0b7306c68d42020202020202020가 나오게 하는 plaintext 계산
    • = (d59d3df3d55baeb7 ^ ff35e0b7306c68d4) + 2020202020202020
    • = 2aa8dd44e537c6632020202020202020
  6. 000000000000000000000000000000002aa8dd44e537c6632020202020202020을 암호화 했을때 나오는 tag값 조회
    • = 6c13c84e2d3066e9fb520e7adbda6ef6

6번 과정에서 나온 tag값이 우리가 원래 암호화 하고자 했던 3번의 문자열의 tag값과 동일하기 때문에 문제가 풀리게 된다.

정답:

1
2
3
nonce : 00000000000000000000000000000000
ciphertext : 0ad1de197a3e8cb8037a06a8b3077d2aff35e0b7306c68d4ed8ae0e7c35f136b
tag : 6c13c84e2d3066e9fb520e7adbda6ef6

1
2
3
4
5
6
7
8
9
10
9a7f846af14e09f6b32cff3a648b80f5 ❯ python3 prob.py
1) Encrypt
2) Decrypt
3) Execute
4) Exit
> 3
nonce = 00000000000000000000000000000000
ciphertext = 0ad1de197a3e8cb8037a06a8b3077d2aff35e0b7306c68d4ed8ae0e7c35f136b
tag = 6c13c84e2d3066e9fb520e7adbda6ef6
KIMTRUTH{FLAG_IS_FLAG}
Share