backtalk

Description

Category: Crypto

Source: WPICTF 2019

Points: 500

Author: Jisoon Park(js00n.park)

Description:

We caught two WPI students sending illegal secrets on our network... can you find out what they said?

made by rm -k and acurless
capture_final.pcapng

Write-up

주어진 pcapng 파일을 열어보면 TCP 통신 내역을 볼 수 있다. follow를 이용해서 내용을 살펴보자.

g, mod, pub 값이 있는 걸로 봐서는 대수 기반의 key exchange 알고리즘인 것 같다. DH(diffie-hellman) 아니면 elgamal일 것 같았는데, enc_key가 mod 보다 작은 값 하나로 구성된 것을 보니 elgamal은 아닌 것 같다. (elgamal은 암호문이 두 개의 값으로 구성된다.)

DH 프로토콜이라고 가정하고, 공격 방법을 생각해 보자. 사실 떠오르는 방법이 없었는데, DH의 wiki에 아래와 같은 말이 있었다.

The order of G should have a large prime factor to prevent use of the Pohlig–Hellman algorithm to obtain a or b.

order of G가 뭔지는 모르겠지만, Pohlig–Hellman algorithm이라는 것을 찾아봤다.

a = b^x mod p로 정의된 식에서, a, b, p로부터 x를 찾아내는 계산법이었다. 여기를 보니 p - 1이 작은 소수들의 곱으로 표현되면 Pohlig–Hellman algorithm을 사용할 수 있다고 한다. 당장 p - 1을 인수분해 해보자.

yafu를 이용해서 인수분해를 시도해 보았더니, 0.0004초만에 아래와 같은 결과를 확인할 수 있었다.

p - 1 = 2^5 * 3^13 * 5^12 * 7^14 * 11^2 * 13^13 * 17^10 * 19^4 * 23^14 * 29^12

Pohlig–Hellman algorithm 자체를 이해할 수는 없어서, 구현체를 찾아보았다.

python 구현체를 찾아서 이용해 봤지만, 한참을 기다려도 연산이 끝나지 않았다.

다른 좋은게 없을까 고민하다가 sage가 생각나서 sage 구현체를 찾아서 시도해봤더니 바로 x를 찾을 수 있었다.

DH 알고리즘에서 x는 private key이고, 상대방의 public key pub에 대해 pub^x mod p를 계산한 값이 shared_secret이다.

private key를 찾았으니 shared secret은 쉽게 계산할 수 있다.

다음에 온 메세지는 enc_key인데, 길이가 8로 나누어 떨어지지 않는 것을 보니 당연히 암호화 키 자체는 아니고, shared secret으로 암호화 해서 보낸 어떤 값인 것 같다.

어떤 식으로 암호화 한 것일까 고민해 보다가, shared secret과 데이터의 곱이 아닐까 싶어서 shared secret의 p에 대한 역수를 구해서 곱해주었더니 16바이트 길이의 값을 얻을 수 있었다.)

enc_key 다음에 오는 데이터가 32 바이트이니, 아마도 AES를 이용한 암호문이 아닐까 싶어서 위에서 얻은 16바이트 데이터를 key로 하여 AES-ECB 복호화를 시도하였더니 flag를 얻을 수 있었다.(code)

Flag : WPI{sTRuk_byA_$m0otH_cR!mIn@1}