Ezdsa

Description

Category: Crypto

Source: Midnightsun CTF 2019

Points: 223

Author: Jisoon Park(js00n.park)

Description:

Someone told me not to use DSA, so I came up with this.

Service: nc ezdsa-01.play.midnightsunctf.se 31337
Download: EZDSA.tar.gz

Author: grocid is available for questions in #midnightsun @ freenode
Status: Online, last check at 2019-04-06 22:15:31 UTC

Write-up

(종료 후 타 팀의 writeup을 참고하여 풀었습니다 ㅜㅠ)

문제 사이트에 접속해보면 내가 제출하는 base64 인코드된 메세지를 서명해주는 서비스를 이용할 수 있다.

첨부로 주어진 서명 코드를 살펴보면, DSA를 구현하고 있는 것을 확인할 수 있다.

class PrivateSigningKey:

    def __init__(self):
        self.gen = 0x44120dc98545c6d3d81bfc7898983e7b7f6ac8e08d3943af0be7f5d52264abb3775a905e003151ed0631376165b65c8ef72d0b6880da7e4b5e7b833377bb50fde65846426a5bfdc182673b6b2504ebfe0d6bca36338b3a3be334689c1afb17869baeb2b0380351b61555df31f0cda3445bba4023be72a494588d640a9da7bd16L
        self.q = 0x926c99d24bd4d5b47adb75bd9933de8be5932f4bL
        self.p = 0x80000000000001cda6f403d8a752a4e7976173ebfcd2acf69a29f4bada1ca3178b56131c2c1f00cf7875a2e7c497b10fea66b26436e40b7b73952081319e26603810a558f871d6d256fddbec5933b77fa7d1d0d75267dcae1f24ea7cc57b3a30f8ea09310772440f016c13e08b56b1196a687d6a5e5de864068f3fd936a361c5L
        self.key = int(FLAG.encode("hex"), 16)

    def sign(self, m):

        def bytes_to_long(b):
            return long(b.encode("hex"), 16)

        h = bytes_to_long(sha1(m).digest())
        u = bytes_to_long(Random.new().read(20))
        assert(bytes_to_long(m) % (self.q - 1) != 0)

        k = pow(self.gen, u * bytes_to_long(m), self.q)
        r = pow(self.gen, k, self.p) % self.q
        s = pow(k, self.q - 2, self.q) * (h + self.key * r) % self.q
        assert(s != 0)

        return r, s

flag를 hex encoding 하여 private key로 사용하고 있고, 다른 부분은 일반적인 DSA와 동일한데 k를 생성하는 부분만 다른 것을 확인할 수 있다. 원래는 난수를 생성하여 그대로 k로 사용하는데, 여기서는 g와 난수와 입력한 값을 이용하도록 되어 있다.

k를 공격하면 무슨 일이 일어날지 상상해보자. k가 0이면 그렇게 만들 수도 없겠지만 r은 1이고 s는 0이 되어 아무것도 할 수 있는게 없다.

k가 1이라면, s = (h + key * r) mod q 가 되는데 s, h, r, q를 모두 알 수 있으니 key를 계산해낼 수 있게 된다. k를 1로 만드는 방법을 열심히 고민해보자.

k = g^{u * m} mod q에서, m을 0으로 넣어주면 k가 1이 되겠지만, 바로 윗줄의 assert를 통과하지 못할 것이다. 이 assert 문을 다시 보면 m이 (q - 1)의 배수인지 확인하는데, 이걸 확인하는 이유는 m = t(q - 1)인 경우 페르마의 소정리에 의해서 k가 1이 되기 때문이다.

어.. 그런데 m = (q - 1)/2라면 어떨까. 일단 assert문에는 걸릴지 않을테고, u가 짝수이면 페르마의 소정리가 적용되게 될텐데 u는 그냥 임의로 생성하고 있으니 50%의 확률로 k가 1이 될것이다.(upbhack팀의 writeup에 따르면, u가 홀수라도 k가 1이 된다고 하는데, 이해는 잘 되지 않았다.)

exploit을 작성해 보자.

(q - 1)/2를 base64로 인코딩하여 보내면 성공적으로 r, s를 받아온다.

k가 1일테니 r = (g % p) % q일 것이라서 미리 계산해 둘 수도 있었지만 어쨌든 r^-1 mod q를 계산한 후, (s - h) r^-1 mod q를 계산하면 flag인 key를 얻을 수 있었다.

Flag : th4t_w4s_e4sy_eh?