[zer0pts] dirty laundry

문제에서는 chall.py 와 이에 해당하는 output.txt가 주어져있다.

 

class PRNG256(object):
    def __init__(self, seed):
        self.mask = (1 << 256) - 1
        self.seed = seed & self.mask

    def _pick(self):
        b = ((self.seed>>0)^(self.seed>>2)^(self.seed>>5)^(self.seed>>10)^1)&1  # 1 or 0
        self.seed = ((self.seed>>1)|(b<<255)) & self.mask
        return b

    def rand(self):
        x = 0
        for i in range(256):
            x = (x << 1) | self._pick()
        return x

PRIME = getStrongPrime(1024)
prng = PRNG256(PRIME)

 

chall.py 에는 위와 같은 256 bit PRNG 생성코드가 만들어져 있고,

 

PRIME =
 getStrongPrime(1024)
prng = PRNG256(PRIME)

def paillier_enc(m, p, noise):
    p = next_prime(p + noise)
    q = getStrongPrime(512)
    n = p * q
    g = (1 + prng.rand() * n) % n**2
    c = pow(g, m, n**2) * pow(prng.rand(), n, n**2) % n**2
    return n, g, c

def make_shares(secret, k, shares, prime=PRIME):
    PR, x = PolynomialRing(GF(prime), name='x').objgen()
    f = PR([secret] + [ZZ.random_element(prime) for _ in range(k-1)])
    xy = []
    pubkey = []
    for x in range(1, shares+1):
        noise = prng.rand()
        n, g, y = paillier_enc(f(x) + noise, prime, noise)
        pubkey.append([n, g])
        xy.append([x, y])
    return pubkey, xy

secret = bytes_to_long(flag)
pubkey, shares = make_shares(secret, 3, 5)

print("[+] len(flag):", len(flag))
print("[+] pubkey:", pubkey)
print("[+] shares:", shares)

 

또 이를 이용한 pailier 암호화와 share 함수가 주어져있다.

우리가 하고자 하는 것은 make_shares(secret , 3 , 5) 이므로 이대로 따라가보자

.

이 입력대로라면, 위 코드에 따라 f = secret + ax + ax^2 이라는 함수가 된다.

그리고 이를 pailier 암호화에 넣는데, 여기서 주목해야할 부분은 g이다.

 

g = (1 + prng.rand() * n) % n**2

 

prng.rand() 는 256bit이고, n은 1024 + 512 = 1536 bit이므로 두 곱은 1792 bit가 된다.

그런데 n ** 2 는 3072bit이므로 나누기는 아무 의미가 없어진다.

이렇게 되면 우리는 g , n을 알고 있기 때문에 prng.rand() 값을 알 수 있다.

 

g = (1 + prng.rand() * n)
prng.rand() = (g - 1) // n

 

이제 이 prng.rand()를 이용하여 prng의 초기 seed를 구해보려고 한다.

PRNG256 클래스를 다시 살펴보자.

 

class PRNG256(object):
    def __init__(self, seed):
        self.mask = (1 << 256) - 1
        self.seed = seed & self.mask

    def _pick(self):
        b = ((self.seed>>0)^(self.seed>>2)^(self.seed>>5)^(self.seed>>10)^1)&1  # 1 or 0
        self.seed = ((self.seed>>1)|(b<<255)) & self.mask
        return b

    def rand(self):
        x = 0
        for i in range(256):
            x = (x << 1) | self._pick()
        return x

 

우리가 알고 있는 값인 prng.rand() 는 rand 함수의 결과이며, 이는 self.pick()의 반환값 256개가 합쳐진 것이다.

prng.rand() 값을 안다는 것은, self.pick() 함수에서의 모든 반환값을 우리가 가지고 있음을 의미한다.

또, _pick에서 보면 그 반환값이 seed의 MSB로 가게 되므로 우리는 rand() 함수가 끝난 후의 seed도 알 수 있다.

 

코드를 살펴보면 prng.rand() 가 한번 이루어지고, 그 다음 결과값을 우리가 얻어낸 것이므로

2번만 역연산을 해주면 초기 seed를 알 수 있다.

 

#reverse
def rev(self):
        tmp = str(bin(self.seed))[2:]
        tmp = (256-len(tmp)) * '0' + tmp
        tmp = int(tmp[::-1],2)
        for i in range(256):
            bit = ( tmp) & 1
            tmp = tmp >> 1
            self.seed = self.seed & self.mask_2
            b = (bit ^ (self.seed >> 1) ^ (self.seed >> 4) ^ (self.seed >> 9) ^ 1) & 1
            self.seed = (self.seed << 1) + b

 

PRNG256 클래스 안에 rev함수를 다시 만들어 주고 우리는 seed를 얻어 냈다.

즉, 문제에서 사용하는 15번의 prng.rand()의 값을 모두 얻어낸 것이다.

이번엔 pailier_enc 함수를 살펴보자

 

def paillier_enc(m, p, noise):
    p = next_prime(p + noise)
    q = getStrongPrime(512)
    n = p * q
    g = (1 + prng.rand() * n) % n**2
    c = pow(g, m, n**2) * pow(prng.rand(), n, n**2) % n**2
    return n, g, c

 

c 에서 보면, pow( prng.rand(), n , n**2) 는 우리가 아는 값이므로,

pow(g , m , n**2) 를 얻어낼 수 있다. 이 값을 C라고 하자.

또 그 값은 아래와 같이 나타낼수 있다.

 

C = pow(g , m , n**2 )

 = (1 + prng.rand() * n )^ (f(x) + noise) (mod n**2) 

 

여기서 이를 좀 간단히 나타낼 수 있다.

 

이용할 식 :( 1 + n)^ x (mod n**2) = 1  + nx 
 (위 식을 전개해보면, 이차항부터는 n**2를 계수로 항상 가지기 때문)

​

C (mod n**2)= (1 + prng.rand() * n )^ (f(x) + noise) (mod n**2) 

= (1 + prng.rand() * n * ( f(x) + noise)) (mod n**2)

C-1 (mod n**2 ) = (prng.rand() * n * ( f(x) + noise)) (mod n**2)

 

여기서, 우변이 n의 배수이기 때문에 좌변도 n의 배수이다.

합동식의 성질을 이용하여 양변을 n으로 나누면 양변이 (mod n)으로 바뀐다.

 

(C - 1) // n (mod n) = (prng.rand() * (f(x) + noise) (mod n)

 

여기서 prng.rand() , noise 이 두 값은 우리가 아는 값이므로 f(x)를 얻어낼 수 있다.

잠시 정리하자면, 우리는 f(1) ~f(5)를 얻어냈다.

 

f(x) = secret + ax + bx^2

f(1) = secret + a + b (mod prime)
f(2) = secret + 2a + 4b (mod prime)
f(3) = secret + 3a + 9b (mod prime)
f(4) = secret + 4a + 16b (mod prime)
f(5) = secret + 5a + 25b (mod prime)

 

이제 남은것은 prime만 계산해주면 된다..!!

 

f(1) + f(3) - 2f(2) = 2b
f(2) + f(4) - 2f(3) = 2b
f(3) + f(5) - 2f(4) = 2b

 

이를 이용해서 위의 연산의 실제 결과들을 비교하여 우리는 prime 값을 얻어낼 수 있다.

 

>>> (f[1] + f[3] - 2 *f[2])
mpz(15811421083594511222443737739252635264048880525922585588301936609228995378847100219077025996330637679748201495232713488175501419093889756582141854326794585932757033416010075789093873549925885865427721464977303837867972880212881542442858600772700056257381545416159374874599314719160184896130245018676138377339)

>>> (f[2] + f[4] - 2 *f[3]) 
mpz(15811421083594511222443737739252635264048880525922585588301936609228995378847100219077025996330637679748201495232713488175501419093889756582141854326794585932757033416010075789093873549925885865427721464977303837867972880212881542442858600772700056257381545416159374874599314719160184896130245018676138377339)

>>> (f[3] + f[5] - 2 *f[4]) 
mpz(-124774146038784351164660695638844469856057176985103369924500484527626445042767085680881218533371013137755309524956122804303169360720687143840617652657883917066736244248204558778941905728536041360624781514852127873619283658133441911094549580928196987208500641692108582717297358074519511405222407995323945125710)

 

1 , 2번째는 값이 같은데 3번째만 다른 것을 보니 둘의 차이가 곧 prime이 될 것이다.

(prime의 배수이긴 한데, 실제로 prime이 나옴)

이를 이용해 연산을 해주면 flag를 얻어낼 수 있다.