2020 회고

대학원

대학원에 들어갔습니다. 좋은 랩에는 들어갔지만 좋은 주제를 찾지 못해서 초반에 많이 방황했었습니다. 다행히도 좋은 랩에 들어간 덕에 교수님과 랩의 여러 사람들이 케어를 많이 해주셨고 현재는 좋은 주제로 연구를 진행하고 있습니다.

그런데도 해결되지 않는 것이 있다면 무기력증이나 귀찮음 같습니다. 연구를 진행하다보면 특정 포인트에서 더 할 의욕이 안 나는 경우가 잦은데, 비단 이것을 ‘내가 연구 주제에 흥미가 없는 것이 아닐까?’ 하고 생각하다보면 그건 또 아니기에 참 아리송한 일이 아닐 수 없습니다.

내년 목표는 ‘꼭 연구를 완성시키자’입니다. 아마 내년 3월 전에는 눈에 보이는 무언가를 만들 수 있을 거라고 생각합니다.

우울증

작년부터인가 재작년부터인가 겪고는 있었다고 생각했지만 올해가 정말 증상이 심해졌습니다. 불면증과 무기력증, 만성 피로까지 겹쳐져서 상당히 고생을 많이 했고 결국 정신과에 가서 치료와 상담을 병행하게 되었습니다. 올해 초에 새 환경에서 적응하느라 좀 심해진 것이 아닌가 싶기도 합니다.

다행히도 현재는 약을 먹으면서 호전이 되고 있지만, 약을 가끔 빼먹으면 불면증에 잠을 제대로 못 자고 있기에 나으려면 갈 길이 먼 것 같습니다.

CTF

포항공대를 졸업하면서 자연스럽게 포항공대 보안 동아리인 PLUS 현역이 아니게 되었습니다. 그래도 종종 PLUS와 같이 CTF를 뛰긴 했지만, 개인적으로 만족스럽게 CTF를 뛰지는 못했습니다. koreanbadass로 DEF CON CTF Finalist가 되기는 했지만 역시 만족스러운 결과는 아니었다고 생각하고요.

그 이후로 여러 대회를 거치면서 한국에서 CTF 팀을 찾는 것에 염증을 느끼게 되었고, 여러모로 징징 글도 썼습니다.

해당 트윗 이후 먼저 Super Guesser 의 sqrtrev님으로부터 연락이 와서 시험삼아 같이 CTF를 뛰어보았는데 만족스럽게 뛸 수 있었고, 그 후 perfect blue 의 knapstack님으로부터도 연락을 받아 2개의 팀에 들어가게 되었습니다.

그 결과 멋진 팀원들도 만나고, HITCON CTF 1등을 거머쥐면서 DEF CON CTF 시드도 획득할 수 있었습니다. 개인적으로 HITCON CTF 1등은 지금까지 CTF를 하면서 가장 큰 성과라고 생각합니다.

아, 올해 사이버작전경연대회와 Bingo CTF, pbctf에서도 문제를 출제했었습니다. 문제 출제는 처음이었는데 좋은 경험이었다고 생각합니다. 내년도 출제할 수 있었으면 좋겠네요.

그 외

올해 rkm0959님을 만나서 같이 암호학과 관련된 활동을 많이 할 수 있었습니다. 바킹독님과 함께 NSUCRYPTO도 나가서 은상도 타고, Super Guesser에서 같이 암호와 관련된 문제들을 풀 수 있어서 정말 다행이라고 생각합니다.

우울증과 관련해서 저에게 도움을 준 사람들이 많이 있습니다. 우울증과 관련해서 상담해준 승엽이형에게 고맙다는 말 전하고 싶고, 자주 말 걸어준 모두에게 감사하다는 말씀을 드립니다.

요즘 들어 게임에 크게 흥미가 떨어진 상태였는데 최근에는 마이마이를 다시 해보고 있습니다.

PT를 받고 있습니다. 운동 정말 힘든 거 같습니다. 제 저질 체력에 눈물이 납니다.

내년에는 좀 더 나은 사람이 될 수 있었으면 좋겠습니다. 좋아하는 공부를 좀 더 열심히 할 수 있었으면 좋겠다고 생각합니다. 내년의 목표는 여러가지가 있습니다.

  • 연구 열심히 하기
  • 운동 평균만큼은 할 수 있게 되기
  • 일본어 공부
  • 위스키 공부
  • 암호학 공부 (Elliptic Curves: Number Theory and Cryptography 취미 삼아 읽기?)
  • 리버싱 공부 (어떤 스택을 더 쌓을 수 있을지…)
  • 포너블 공부?
  • 일본 여행 가기 (가능하면 ㅠ)
  • 코로나 끝나가면 사람들 좀 만나기

다 이룰 수 있었으면 좋겠네요. 그러기에는 시간이 별로 없는 거 같은데…

서버 이전

오랫동안 함께한 서버를 버리고 옮기게 되었습니다.

여러가지 사유가 있지만, 가장 큰 이유는 무지한 상태에서 서버를 사용한 나머지 다양한 업보가 쌓였다는 것입니다. (virtualenv 없이 Python을 사용하다보니 무언가 꼬이고… root 계정은 살아있고…)

이번에는 좀 더 현명하게 사용하기 위해 노력해야겠습니다. 파이팅 ㅎㅎ

Coppersmith’s method

긴 글은 아니고, Coppersmith’s method에 대해서 공부하고 싶으신 분들을 위한 요약 글입니다.

기본

기본적인 Coppersmith’s method를 이해하는데 도움이 되는 글은 역시 Alexander May의 “New RSA Vulnerabilities Using Lattice Reduction Methods”라는 글이 아닐 수 없네요.

Coppersmith’s method의 근본이 되는 Lattice와 LLL theorem에 대해서 간략하게 설명하며, Coppersmith’s method의 univariate case와 multivariate case, 그리고 그 응용들에 대해서 자세히 설명합니다.


또한 sage를 통해서 간단한 경우에 대해서 Coppersmith’s method를 어떻게 사용할 수 있는지를 알아보는 일본어 글도 찾아볼 수 있습니다. (SageMathを使ってCoppersmith’s Attackをやってみる)

다만 해당 글의 코드는 엄밀하지 못하기 때문에, 아래 PPT도 한 번 읽어보시는 것을 추천합니다.


작년 겨울에 위의 문서들을 바탕으로 PLUS 동아리에서 세미나를 할 때 사용한 PPT를 첨부합니다. (퀄리티가 좋지 못한 점 양해 부탁드려요 ㅎㅎ)

심화

Boneh-Durfee Attack

Boneh-Durfee Attack의 기본에 대해서 이해하고 싶으시다면 ebmoon님의 “RSA Attack Using LLL – Understanding Boneh-Durfee Attack” 문서를 참고하시는 것을 추천합니다.

Sage로 작성한 Boneh-Durfee Attack 코드는 RSA-and-LLL-attacks repository에서 확인하실 수 있습니다.

On Factoring Given Any Bits

한 때 트위터에서 소개했던 코드입니다. (링크)

“Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits” 논문을 바탕으로 작성한 것으로, random한 위치의 bit를 모르는 경우 뿐만 아니라 multivariate linear equation을 푸는 코드입니다.

그 외

Partial information으로부터 key를 복구하는 방법에 대해서 다양하게 다룬 “How to recover cryptographic keys from partial information”라는 PPT도 참고하기 좋습니다.

[zer0pts CTF 2020] dirty laundry

Do you wanna air my dirty laundry?


How to solve

Recovering PRNG

The challenge uses 256-bit LFSR PRNG, of which seed is the lower 256-bit of 1024-bit prime number.

Let’s see pailler_enc unction.

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

The value p is 1024-bit, so n should be 1536-bit. This means that g = (1 + prng.rand() * n) % n**2 is just same as g = 1 + prng.rand() * n, beacuse prng.rand() is only 256-bit.

So, you can get some prng.rand() values from gs, and then recover the PRNG by reversing the PRNG steps.

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
        self.seed = ((self.seed>>1)|(b<<255)) & self.mask
        return b

    def _rev(self):
        b = ((self.seed>>255)^(self.seed>>1)^(self.seed>>4)^(self.seed>>9)^1)&1
        self.seed = ((self.seed<<1)|b) & self.mask

    def rev(self):
        for i in range(256):
            self._rev()

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

with open('output.txt', 'r') as f:
    ln = len("[+] pubkey: ")
    lines = f.readlines()
    pubkeys = eval(lines[1][ln:])
    shares = eval(lines[2][ln:])

g1 = (pubkeys[0][1] - 1) // pubkeys[0][0]
g1_rev = int(format(g1, '0256b')[::-1], 2)

prng2 = PRNG256(g1_rev)

prng2.rev()
prng2.rev()

Recovering msg from ciphertexts

Now we know every prng.rand() values. Then, how can we recover m from c = pow(g, m, n**2) * pow(prng.rand(), n, n**2) % n**2?

First, we know pow(prng.rand(), n, n**2), so we can get pow(g, m, n**2).

About pow(g, m, n**2), let’s use the lemma:

(1+n)^x \equiv 1+nx (\textrm{mod}\ n^2)

and L function from the Paillier cryptosystem. (Check out Background section of the wikipedia article.)

Let’s name the prng.rand() of g = 1 + prng.rand() * n as noise. Then,

g \equiv 1 + n \cdot noise \equiv (1 + n)^{noise} (\textrm{mod}\ n^2)

g^m \equiv (1 + n)^{noise \cdot m} \equiv 1 + n \cdot noise \cdot m (\textrm{mod}\ n^2)

Therefore, if the value of pow(g, m, n**2) is x, we can get m by

L(x) \cdot noise^{-1}\ \textrm{mod}\ n.

# ...
noises = [ [ prng2.rand() for j in range(3) ] for i in range(5) ]

assert all([ noises[i][1] == (pubkeys[i][1] - 1) // pubkeys[i][0] for i in range(5) ])

from Crypto.Util.number import inverse
msgs = []
for i in range(5):
    n = pubkeys[i][0]
    gm = shares[i][1] * pow(inverse(noises[i][2], n**2), n, n**2) % (n**2)
    assert (gm - 1) % n == 0
    m = ((gm - 1) // n) * inverse(noises[i][1], n) % n
    # Actually the input m of paillier_enc is f(x) + noise.
    # Removing noise here
    m -= noises[i][0]
    msgs.append(m)

Recovering PRIME and flag

Let’s see the make_shares funciton.

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

We can write f = PR([secret] + [ZZ.random_element(prime) for _ in range(k-1)]) as ax^2 + bx + secret with unknown a, b.

We know the values f(1), f(2), f(3), f(4), f(5), but we still don’t know PRIME value.

To recover PRIME, follow these steps:

f(1) = a + b + secret (\textrm{mod}\ PRIME)
f(2) = 4a + 2b + secret (\textrm{mod}\ PRIME)
f(3) = 9a + 3b + secret (\textrm{mod}\ PRIME)
f(4) = 16a + 4b + secret (\textrm{mod}\ PRIME)
f(5) = 25a + 5b + secret (\textrm{mod}\ PRIME)

f(2) - f(1) = 3a + b (\textrm{mod}\ PRIME)
f(3) - f(2) = 5a + b (\textrm{mod}\ PRIME)
f(4) - f(3) = 7a + b (\textrm{mod}\ PRIME)
f(5) - f(4) = 9a + b (\textrm{mod}\ PRIME)

f(3) - 2f(2) + f(1) = 2a (\textrm{mod}\ PRIME)
f(4) - 2f(3) + f(2) = 2a (\textrm{mod}\ PRIME)
f(5) - 2f(4) + f(3) = 2a (\textrm{mod}\ PRIME)

Those three values should be same in mod PRIME. Let’s see the values.

# ...
diff1 = [msgs[i + 1] - msgs[i] for i in range(4)]
diff2 = [diff1[i + 1] - diff1[i] for i in range(3)]

print(diff2)
[15811421083594511222443737739252635264048880525922585588301936609228995378847100219077025996330637679748201495232713488175501419093889756582141854326794585932757033416010075789093873549925885865427721464977303837867972880212881542442858600772700056257381545416159374874599314719160184896130245018676138377339, 15811421083594511222443737739252635264048880525922585588301936609228995378847100219077025996330637679748201495232713488175501419093889756582141854326794585932757033416010075789093873549925885865427721464977303837867972880212881542442858600772700056257381545416159374874599314719160184896130245018676138377339, -124774146038784351164660695638844469856057176985103369924500484527626445042767085680881218533371013137755309524956122804303169360720687143840617652657883917066736244248204558778941905728536041360624781514852127873619283658133441911094549580928196987208500641692108582717297358074519511405222407995323945125710]

The third value is different from the others. It means the difference between the third and the others is the multiple of PRIME, because it should be same in mod PRIME.

The difference is:

140585567122378862387104433378097105120106057511025955512802421136855440421614185899958244529701650817503511020188836292478670779814576900422759506984678502999493277664214634568035779278461927226052502979829431711487256538346323453537408181700897043465882187108267957591896672793679696301352653014000083503049

and it’s actually a prime number. Therefore, it must be PRIME.

Now we know the value of PRIME, we can decrypt the flag.

Here is the full solver.

from Crypto.Util.number import long_to_bytes, inverse

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
        self.seed = ((self.seed>>1)|(b<<255)) & self.mask
        return b

    def _rev(self):
        b = ((self.seed>>255)^(self.seed>>1)^(self.seed>>4)^(self.seed>>9)^1)&1
        self.seed = ((self.seed<<1)|b) & self.mask

    def rev(self):
        for i in range(256):
            self._rev()

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

with open('output.txt', 'r') as f:
    ln = len("[+] pubkey: ")
    lines = f.readlines()
    pubkeys = eval(lines[1][ln:])
    shares = eval(lines[2][ln:])

g1 = (pubkeys[0][1] - 1) // pubkeys[0][0]
g1_rev = int(format(g1, '0256b')[::-1], 2)

prng2 = PRNG256(g1_rev)

prng2.rev()
prng2.rev()

noises = [ [ prng2.rand() for j in range(3) ] for i in range(5) ]

assert all([ noises[i][1] == (pubkeys[i][1] - 1) // pubkeys[i][0] for i in range(5) ])

msgs = []
for i in range(5):
    n = pubkeys[i][0]
    gm = shares[i][1] * pow(inverse(noises[i][2], n**2), n, n**2) % (n**2)
    assert (gm - 1) % n == 0
    m = ((gm - 1) // n) * inverse(noises[i][1], n) % n
    m -= noises[i][0]
    msgs.append(m)

diff1 = [msgs[i + 1] - msgs[i] for i in range(4)]
diff2 = [diff1[i + 1] - diff1[i] for i in range(3)]

p = diff2[1] - diff2[2] # It is prime!

a = diff2[0] * inverse(2, p) % p
b = (diff1[0] - 3 * a) % p
secret = (msgs[0] - a - b) % p
print(long_to_bytes(secret))

The flag is zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!!}.

[zer0pts CTF 2020] nibelung

nc 18.179.178.246 3002
(This was all of the description)


Overview

From the organizer’s write-up(Link):

FiniteGeneralLinearGroup is just a matrix class over a finite field.
We can encrypt and decrypt arbitrary messages.
Encryption is defined as: Y = UXU^{-1}.
Decryption is defined as: X = U^{-1}YU.
The size of matrix (from the server) is 6×6.

How to solve

You cannot decrypt the flag directly, because it only accepts the matrix with values in the range 0~255.

Let’s think about (i, j)-th entry of the UXU^{-1}.

(UXU^{-1})_{i, j} = \sum_{i' = 1}^6 \sum_{j'=1}^6 U_{i, i'} X_{i', j'} U^{-1}_{j', j}

If you send the matrix X which has 1 in the (i, j)-th entry and 0 in the others, you can get U_{k, i} U^{-1}_{j, l} values for every (k, l).

Notice that (UXU^{-1})_{i, j} is a linear combination of X_{i', j'} and U_{i, i'} U^{-1}_{j', j}. Because we now know U_{i, i'} U^{-1}_{j', j} values, we can construct the linear system with 36 variables and 36 equations. We can solve the system with sage.

Here’s the extractor code for getting U_{i, i'} U^{-1}_{j', j} values.

from pwn import *
import base64

f = open('data', 'w')

r = remote('13.231.224.102', 3002)
r.recvuntil('Encrypted Flag:\n')

eF = r.recvuntil('p = ')[:-5]
p = r.recvuntil('=')[:-1]

eF = eF.replace('\n', ',') + '\n'
f.write(p + eF)

for i in range(36):
    target = b'\x00' * i + b'\x01' + b'\x00' * (35 - i)
    target = base64.b64encode(target)
    r.sendline('1')
    r.sendline(target)
    r.recvuntil('Encrypted:\n')
    v = r.recvuntil('=')[:-2]
    v = v.replace('\n', ',') + '\n'
    f.write(v)

f.close()

Here’s the sage solver for the linear system.

from itertools import product as iproduct

# [i][j][i_][j_] = U[i][j] * U**-1[i_][j_]
UUm1_coef = [ [ [ [None for i in range(6)] for j in range(6) ] for k in range(6) ] for l in range(6) ]

with open('data', 'r') as f:
    p = int(f.readline()[:-1])
    eF = eval(f.readline()[:-1])

    for i, j in iproduct(range(6), repeat=2):
        mat = eval(f.readline()[:-1])
        for i_, j_ in iproduct(range(6), repeat=2):
            UUm1_coef[i_][i][j][j_] = mat[i_][j_]

mat = [ [0 for i in range(36)] for j in range(36) ]
vec = [ eF[i // 6][i % 6] for i in range(36) ]

for i, j, i_, j_ in iproduct(range(6), repeat=4):
    mat[i * 6 + j][i_ * 6 + j_] += UUm1_coef[i][i_][j_][j]
    mat[i * 6 + j][i_ * 6 + j_] %= p

R = IntegerModRing(p)
M = Matrix(R, mat)
b = vector(R, vec)
ans = M.solve_right(b)

flag = ''
for i in range(36):
    flag += chr(ans[i])
print(flag)

The flag is zer0pts{r1ng_h0m0m0rph1sm_1s_c00l}.

« Older posts

© 2021 RBTree.insert()

Theme by Anders NorenUp ↑