2023 CCE Quals

With Team “02vs04”

crypto - Wrong Implementation

먼저 Message를 알고 Encrypt에 의해 xor되는 정보는 동일하기 때문에 두 ciphertext를 xor하고 Message를 xor해주면 플래그의 뒷부분을 얻을 수 있다.

그리고 보면 key가 7자리 자연수의 str + ABCDEFABC로 고정되어 있기 때문에 가능한 key의 수가 9000000개밖에 존재하지 않는다. 충분히 전수조사를 통해 올바른 키를 구할 수 있다.

ex.py

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from pwn import *
from tqdm import trange

enc_msg =  31214112203883461538912621847140725647435826042420979977417027226834401610883458792474503120620360328700798549521671
enc_flag = 31214112203883461538912621847140725647435727300325983746492013560576717160853375226573567873228174306246287909482836

flag_2 = b"2980625bbcfa2f2958da}"

Message = "Hello, Alice!. My flag is here.".encode()

enc_msg = long_to_bytes(enc_msg)




enc = xor(enc_msg, b"\x00" * 17 + Message)


for i in trange(1000000, 10000000):
    key = str(i).encode() + "ABCDEFABC".encode()
    assert len(key) == 16

    Cipher = AES.new(key=key, mode=AES.MODE_ECB)
    a = set(list(Cipher.decrypt(enc[-16:])))

    if len(a) == 2:
        pt = Cipher.decrypt(enc)

        print(pt)

b'cce2023{a80107b0ac3bc0000000000000000\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b'

"cce2023{a80107b0ac3bc2980625bbcfa2f2958da}"

crypto - The miracle

제약 조건이 몇 존재한다.

N은 p * q로 표현되면서 십진수 표현에 약 250비트 가량의 문자열이 포함되어 있어야 한다. (문제 설명에는 앞쪽에 있어야 한다고 되어있는데 중간에 있어도 된다. 근데 앞쪽이 편하다.)

e 또한 250비트 가량의 문자열이 포함되어야 하며, 절댓값이 너무 작은 경우는 배제된다.

p, q가 512비트이기에 다행히 제약 250비트가 큰 문제가 되지 않는다. 500비트가 넘어가면 살짝은 귀찮아졌을지도 모른다. 조건을 만족하는 n을 구하는 방법은 필요한 135글자(250비트) 뒤에 많은 0을 붙여 주어서 p*q로 표현 가능한 범위인 1023비트 ~ 1024비트가 되게 만들어준다.

근데 10씩 곱해주다 보니 1023, 1024를 점프해서 필요 스트링 앞에 숫자를 하나 더 넣어주었다. 이를 n_base라고 하자. 그리고 소수 p를 고르고 $\left\lfloor n_base / p \right\rfloor$의 값에서 소수가 될때까지 1을 더해주면 좋은 pq쌍을 구할 수 있다.

이 문제의 핵심은 e를 p-1의 배수가 되게 만들어 pow 후의 결과가 p의 배수가 되게 만드는 것이다. Pow한 결과에서 128비트만을 숨겨놨기 때문에 LLL을 통해서 쉽게 복구할 수 있을 것으로 보인다.

ex.sage

from pwn import *
from Crypto.Util.number import *
import random

io = remote("20.196.200.237", 2580)

n_pfx = 12718281828459045235360287471352662497757247093699959574966967627724076630353
e_pfx = 3141592653589793238462643383279502884197169399375105820974944592307816406286

p = 10472248798148684305914511700419339800175397042519524432660853347874909276697824401438766832062766929661304904284940008789941041544806678388614572567643171
q = 12144747583448763569821639376537564467149289084421268874590213062689120295781217102298952495518391037726796906494519998213441943865561185014687044471066047

n = p * q
phi = (p - 1) * (q - 1)

e = e_pfx * 10**200

e += (-e) % (p - 1) + 1

assert e % (p - 1) == 1

test = random.randrange(0, 2^128)
assert pow(test, e, n) % p == test

io.sendline(str(p))
io.sendline(str(q))
io.sendline(str(e))

io.recvuntil("First Outputs\n")
res = eval(io.recvline())

print(res.bit_length())

weight = 2^1024

M = [[0, res, weight], [1, 2^896, 0], [0, p, 0]]
M = Matrix(M).LLL()



for v in M:
    if v[2] == weight:
        a = ZZ(v[0])
        b = ZZ(v[1])

print(a.bit_length())

assert (a * 2^896 + res) % p == b

next_z = pow(a, e, n)

next_out = next_z % (2^896)
next_state = next_z >> 896

io.sendline(str(next_out))
io.sendline(str(next_state))


io.interactive()

crypto - NZK-SIARK

필자의 코드가 수많은 반복과 난독화로 인해 400줄인 관계로 부득이하게 풀이과정만 작성하도록 하겠다.

먼저 모든 연산은 8비트의 엔트로피를 가진 GF(2) polynomial ring 위에서 정의되어 있다. 크게 중요하지는 않다. 가장 중요한 부분은 get_sbox_and_verify에서 허용되는 값의 종류가 x가 1 ~ 255면 1/x로 제한되지만, x=0일때는 256개의 값이 모두 들어갈 수 있다.

내부에서 귀찮은 연산을 진행하지만 천만다행히도 모두 일대일 대응이기 때문에 원하는 256개의 값을 모두 조작할 수 있다는 사실에서 시작한다.

키를 입력받고 round key generation은 전 round key를 get_sbox_and verify에 넣어서 조작된다. 위에서 설명했듯이 255가지는 입력할 수 있는 값이 하나밖에 없지만, 0일 경우만은 원하는 값을 넣을 수 있기 때문에 key에서 4바이트만은 다음에 쓰기 위해 0으로 고정시켜두고 12바이트를 맘대로 조작할 수 있다.

Substitution 또한 get_sbox_and_verify함수를 이용해서 진행된다. 함수에 들어가기 전에 0을 가지고 있으면 또 임의의 조작이 가능하다는 뜻이다.

위에서 초기 키에서 12바이트를 맘대로 고를 수 있다고 했는데 그러면 처음으로 sub를 진행하기 전에 0이 12번 등장하게 설정해줄 수 있다. 그러면 state의 16바이트 중 12바이트가 자유로워진다.

벌써 필요한 자유도가 16바이트인데 12바이트에다가 다음 keygen을 할때 넣을 4바이트까지 해서 16바이트의 자유도가 완성됐다. 목표는 라운드를 질질 끌지 않고 두 번째 sbox에 들어갈 때는 state의 16바이트가 모두 0인것이다. 이게 가능하면 복호화 연산을 통해 ciphertext를 만드는 state의 16바이트를 맘대로 설정할 수 있다.

이제 슬프게도 shift_row, Mix column을 뚫고 어떻게 0 12바이트를 만들 수 있을지에 대한 고찰이 필요하다.

첫 add round key 이후에는 123번째 column이 0벡터, 4번째 column이 고정된 벡터이다. 이를 row shift하면 왼쪽아래 – 오른쪽위를 잇는 대각선에만 0이 아닌 값이 존재하게 된다.

Mix column과정을 봐보면 이제는 선형대수학이 등장할 차례이다. 주어진 mat에 대각선이 고정된 matrix를 곱해서 두번째 키쌍이랑 같은 결과가 나와야 한다. 다시 키 생성과정에 집중하는 것이 포인트이다. 첫 column을 f라고 하면 2, 3, 4번째 column은 f + constant로 표현된다. 즉 지금 사용할 Key matrix는 F + K꼴로 표현가능하다(F = [f, f, f, f], K는 상수).

Mat의 역행렬을 좌측해 곱하고 mat-1K를 양변에서 빼주면 아직도 좌변은 대각선만 고정이고, 우변은 mat-1F이다. 근데 F의 column들이 다 같으니깐 고정된 대각선의 값 4개를 한 벡터로 바꿔서 a = mat-1f의 예쁜 식을 구할 수 있다. Mat*a = f가 되므로 f벡터를 성공적으로 구할 수 있다. 이제 이 시나리오를 구현하는 건 다른 문제이다. 정말 오래 걸렸다.

[+]

그냥 처음에 16바이트의 키를 입력할 때 16바이트가 전부 같게 설정하면 해결되는 문제였다. 너무 어렵게 돌아가서 풀었다.

필자 빼고는 아무도 이렇게 푼 사람이 없을 것으로 보인다.