H4CHKING GAME - Cryptography, Season1 : Lattice

Season1 : Lattice

 

output.txt

0.00MB

prob.py

0.00MB

 

 

prob.py 코드를 돌리면 flag.txt 파일을 이용한 output.txt 파일이 만들어지면서 Public key, Encrypted Flag 값이 생성된다. 그리고 우리한테 주어진 건 특정 output.txt. 즉, 우리는 결과를 보고 flag.txt 내용이 뭐였는지 찾아야 하는 문제다. 

 

 

여기에서 q는 512-bit 소수이고, 비밀값 f와 g는 q에 비해 매우 작은 값으로 생성된다.

공개되는 값은 q와 h이고, f와 g는 공개되지 않는다.

 

h는 다음과 같이 만들어진다.

h = inverse(f, q) * g mod q

 

따라서 f와 g를 알고 있다면 다음과 같은 관계를 만들 수 있다.

 

 

f * h - g = k * q

 

 

여기서 k는 어떤 정수이다.

 

즉, 공개된 q와 h만 가지고 있지만 그 안에 작은 값 f와 g가 숨어 있다고 볼 수 있음.

 

 

 

평문을 m, 랜덤값을 r이라고 하면 암호문은 대략 다음과 같은 형태이다.

cipherText = r * h + m mod q

여기서도 중요한 점은 평문과 r이 모두 작은 값이라는 것이다.

따라서 단순히 큰 수를 이용한 암호가 아니라, 작은 비밀값을 이용한 modular 연산이라는 점에서 lattice 공격을 생각할 수 있다.

 

 

 

 

 

q가 512-bit이기 때문에 f와 g는 대략 256-bit 정도의 크기를 가진다.

 

근데 q 자체는 512-bit이다.

 

그래서 q : 큰 값, f : 작은 값, g : 작은 값 이라는 걸 알 수 있음

그리고 공개키 h에는 f와 g의 관계가 들어 있다.

f * h - g = k * q

따라서 이 관계를 만족하는 작은 f와 g를 찾는 문제로 바뀐다.

 

또 이런 형태의 작은 정수 관계는 Lattice Reduction을 이용해서 공격할 수 있음.

 

from sympy import Matrix

X = 1 << 256

B = Matrix([
    [X, h],
    [0, -q]
])

L = B.lll()

for row in L.tolist():
    print(row)

LLL을 적용하면 lattice 안에서 짧은 벡터를 찾을 수 있다.

문제에서 f와 g가 작은 값으로 제한되어 있기 때문에 LLL 결과에서 f와 g와 관련된 짧은 벡터를 확인할 수 있다.

 

 

 

-> LLL 결과를 이용해서 복구한 값

f =
17133994769118733245106419501651631672408766369813411765950821120296864522768

g =
45615557025682965876658577161674935476325132389508728014840975441281203904609

 

 

이제 f와 g를 얻었으므로 암호문을 복호화할 수 있다.

 

우선 암호화는

cipherText = r * h + plainText mod q

 

여기에 f를 곱하면 h에 포함되어 있던 f의 역원 관계를 이용할 수 있다.

 

그래서 복호화는

f * cipherText = r * g + f * plainText

여기서 g로 나머지를 구하면 r * g 부분이 사라짐

따라서 f의 역원을 이용하면 원래 평문을 복구할 수 있다.

 

 

from Crypto.Util.number import inverse, long_to_bytes

a = (f * cipherText) % q
m = (a * inverse(f, g)) % g

flag = long_to_bytes(m)

print(flag)

 

 

 

 

[정리]

이 문제에서 가장 중요한 건 f와 g가 매우 작다는 것. 공개된 q와 h를 이용해서 작은 f와 g를 찾는 문제로 바뀐다

그리고 Lattice를 구성하고 LLL을 적용하면 이 값을 찾을 수 있음

 

1. f * h - g = k * q 확인
2. Lattice 구성(f, g가 작은 값이라는 점 이용해서)
3. f, g 복구
4. 암호문에 f 적용
5. g를 이용해 랜덤값 제거
6. 평문 복구
7. long_to_bytes 함수

=> H4CGM{latt1c3_l0v3s_bas1s}