LG

Description

Category: Crypto

Source: VolgaCTF 2019 Qualifier

Points: 100

Author: Jisoon Park(js00n.park)

Description:

WazzUP! My homie bought a new UltraSmartTV, but he forgot a secret key from an admin panel. After a few attempts to crack this "smart" IoT device it started to generate new passwords on its own, and now we are stuck.

Can you help?

nc lg.q.2019.volgactf.ru 8801

Second host: nc 95.213.235.103 8801

Write-up

문제 서버에 접속해 보면 난수로 보이는 숫자 10개를 주고 다음에 올 숫자를 맞춰보라고 한다.

숫자 사이에 뭔가 규칙성이 있을 것 같은데, Smart TV랑 무슨 상관인지는 모르겠다.

문제를 보고 수열에서 점화식을 찾으면 될것 같다는 생각을 했었는데, 숫자가 커졌다 작아졌다 하는걸 보니 modulus 가 붙어있는 수열일 것 같았다.

수열을 배운지 하도 오래 되어서 기억나는 수열이 등차, 등비, 조화 수열밖에 없었는데 모두 정수 형태인걸 보아 조화 수열은 아닌 것 같고, 등차와 등비수열인지를 먼저 확인해 보았다.

등차수열이라면 x_n = x_{n - 1} + a mod p로 정의될 수 있을 것인데, 문제에서 주어진 수열을 만족하는 a를 찾을 수 없었다.

등비수열이라면 x_n = a x_{n - 1} mod p으로 정의될 텐데, 마찬가지로 수열을 만족하는 a를 찾을 수 없었다.

혹시 hash chain일까 싶어서 생각나는 hash 알고리즘들을 적용해 보았지만 아니었다.

100점짜리 문제인데 말도 안되는 복잡한 건 없을 것 같다는 생각에 등차와 등비를 섞은 걸까 싶어서 x_n = a x_{n - 1} + b mod p로 식을 세워봤는데, 이건 방정식을 풀 수가 없었다. 혹시나 비슷한게 있지 않을까 싶어서 검색을 해보았더니, PRNG 중에 LCG(Linear congruential generator)라는게 나왔다. 문제 이름인 LG와 비슷한것이, 왠지 이게 맞는 것 같다.

LCG를 풀려면 a, b, p 세 가지 파라미터의 값을 알아내야 한다. 이건 또 어떻게 하는거지 싶어서 역시 검색을 해봤더니 p를 확률적으로 알아내는 계산법이 있었다.

A linear congruential generator is defined by s_n+1 = a s_n + b mod m, where m is the modulus. In its simplest form, the generator just outputs s_n as the nth pseudorandom number.

To recover m, define t_n = s_n+1 - s_n and u_n = |t_n+2 t_n - t²_n+1|; then with high probability you will have m = gcd(u₁, u₂, ..., u₁₀). 10 here is arbitrary;

The key idea: t_n+1 = s_n+1 - s_n = (a s_n - b) - (a s_n-1 - b) = a s_n - a s_n-1 = a t_n mod m, and t_n+2 = a² t_n mod m, and t_n+3 = a³ t_n mod m. Therefore t_n+2 t_n - t_n+1² = 0 mod m, i.e., |t_n+2 t_n - t_n+1²| is a random multiple of m. Nifty number theory fact: the gcd of two random multiples of m will be m with probability 6/π² = 0.61; and if you take the gcd of k of them, this probability gets very close to 1 (exponentially fast in k).

잘은 모르겠지만 멋진 것 같다.

어쨌든, 위의 방법으로 계산해보았더니 그럴듯한 p를 구할 수 있었다. 이제 a를 찾아보자.

x₁ = a x₀ + b mod p이고, x₂ = a x₁ + b mod p이니, 두 식을 빼면 x₂ - x₁ = a (x₁ - x₀) mod p이고, 이는 t₁ = a t₀ mod p로 쓸 수 있다.

t₀, t₁, p를 모두 알고 있으니, t₀^-1 mod p를 구해서 양쪽에 곱해주면 a를 계산할 수 있다.

b는 더 간단하게 s₁ - a s₀ mod p를 계산해서 구할 수 있다.

p, a, b를 모두 찾았으니, 서버에서 보내준 수열을 검증해 보면 제대로 된 값임을 확인할 수 있고 다음에 올 값도 계산할 수 있다. (p를 계산하는게 확률적이라 그런지 여러번 해보면 안될 때도 있었다.)

예측한 값을 서버로 보내면 flag를 확인할 수 있다.(코드)

Flag : VolgaCTF{pR3d1ct1ng_1s_n0t_oNlY_f0r_0O0rAculs}