SECCON13 challenges writeup(reiwa_rot13, dual_summon, Tidal wave) JP
reiwa_rot13
description
solves: 127
---
Reiwa is latest era name in Japanese(from 2019). it's latest rot13 challenge!
note: Please submit the flag as it is.
source
from Crypto.Util.number import *
import codecs
import string
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from flag import flag
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 137
key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')
key = key.encode()
rot13_key = rot13_key.encode()
print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))
key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))
solution
この問題は key
と rot13_key
の関係に注目することが大切です。
今回は英小文字のみなので、各文字ごとに a~m
であれば+13、n~z
であれば-13されます。
今回は10文字しかないので、+13と-13をすべての文字で試しても1024通りしかありません。
これは以下のコードで列挙することができます
for mask in tqdm(range(1<<10)):
diff = 0
for i in range(10):
if ((mask >> i) & 1) == 1:
diff += 13*256**i
else:
diff -= 13*256**i
あとはRSAの平文の差がわかるとき、Franklin Reiter's Attack と呼ばれる攻撃方法が成立することを知っていればそのライブラリを使ったり、ソースコードを利用することで解くことができます。
import hashlib
from tqdm import tqdm
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.number import long_to_bytes
import sys
sys.setrecursionlimit(2000)
n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag = b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"
# reference: https://zenn.dev/anko/articles/ctf-crypto-rsa
def franklinReiter(n, e, r, c1, c2):
R.<x> = Zmod(n)[]
f1 = x^e - c1
f2 = (x + r)^e - c2
return - polygcd(f1, f2).coefficients()[0]
def polygcd(a, b):
if(b == 0):
return a.monic()
else:
return polygcd(b, a % b)
for mask in tqdm(range(1<<10)):
diff = 0
for i in range(10):
if ((mask >> i) & 1) == 1:
diff += 13*256**i
else:
diff -= 13*256**i
m = int(franklinReiter(n, e, diff, c1, c2))
key = hashlib.sha256(long_to_bytes(m)).digest()
cipher = AES.new(key, AES.MODE_ECB)
res = cipher.decrypt(encyprted_flag)
if res.startswith(b"SECCON{"):
print(res)
break
dual_summon
description
solves: 63
---
You are a beginner summoner. It's finally time to learn dual summon
nc dual-summon.seccon.games 2222
source
from Crypto.Cipher import AES
import secrets
import os
import signal
signal.alarm(300)
flag = os.getenv('flag', "SECCON{sample}")
keys = [secrets.token_bytes(16) for _ in range(2)]
nonce = secrets.token_bytes(16)
def summon(number, plaintext):
assert len(plaintext) == 16
aes = AES.new(key=keys[number-1], mode=AES.MODE_GCM, nonce=nonce)
ct, tag = aes.encrypt_and_digest(plaintext)
return ct, tag
# When you can exec dual_summon, you will win
def dual_summon(plaintext):
assert len(plaintext) == 16
aes1 = AES.new(key=keys[0], mode=AES.MODE_GCM, nonce=nonce)
aes2 = AES.new(key=keys[1], mode=AES.MODE_GCM, nonce=nonce)
ct1, tag1 = aes1.encrypt_and_digest(plaintext)
ct2, tag2 = aes2.encrypt_and_digest(plaintext)
# When using dual_summon you have to match tags
assert tag1 == tag2
print("Welcome to summoning circle. Can you dual summon?")
for _ in range(10):
mode = int(input("[1] summon, [2] dual summon >"))
if mode == 1:
number = int(input("summon number (1 or 2) >"))
name = bytes.fromhex(input("name of sacrifice (hex) >"))
ct, tag = summon(number, name)
print(f"monster name = [---filtered---]")
print(f"tag(hex) = {tag.hex()}")
if mode == 2:
name = bytes.fromhex(input("name of sacrifice (hex) >"))
dual_summon(name)
print("Wow! you could exec dual_summon! you are master of summoner!")
print(flag)
solution
この問題のゴールは異なる2つの鍵で共通の平文で同じtagを生成することです。
この問題はnonceが固定化されている脆弱性が存在しているため、平文とXORされる前の値(固定値)を知ることができそうです。
この問題を解くうえで、GCMのtag多項式演算の加算はXORと同じであることを知っておく必要があります。GCMはこちらの動画で紹介しています。ここまでついてこれていない人はこちらの動画を見てください: https://youtu.be/nXi3Mpufe5M?si=xcf2Q3du3lDpvNZw
step1: Hの導出
まずは一つの鍵で暗号化する機能(summon)を使って、GCM内部の状態をリークします。
今回平文の長さは16bytesである必要があるため、tagは以下の式で生成されます。
この式の
ここで、
これらの平文を用いて、tagを2つ生成してみましょう。
ここで、
あとは平方剰余を求めるだけですね。この問題を解くうえでは
step2: 共通するtagの生成
前のステップでそれぞれの鍵に対応する
さて、ここで共通のタグが生成される平文
source code
import os
set_verbose(0)
os.environ['PWNLIB_NOTERM'] = '1'
os.environ['TERM'] = 'linux'
from Crypto.Cipher import AES
import secrets
from pwn import remote
from logger import logger
F.<a> = GF(2**128, modulus=x**128 + x**7 + x**2 + x + 1)
def to_poly(x):
bs = Integer(int.from_bytes(x, "big")).bits()[::-1]
return F([0] * (128 - len(bs)) + bs)
def to_bytes(x):
v = int(bin(x.integer_representation())[2:].zfill(128)[::-1], 2)
return v.to_bytes(128 // 8, "big")
def encrypt(number, plaintext):
logger.info(io.recvuntil(">")) # summon or dualsummon
io.sendline('1')
logger.info(io.recvuntil(">")) # number
io.sendline(str(number))
logger.info(io.recvuntil(">")) # plaintext
io.sendline(plaintext.hex())
io.recvline()
tag = bytes.fromhex(io.recvline().split(b"=")[1].strip().decode('utf-8'))
return b"", tag
L = a^120
io = remote(os.getenv("SECCON_HOST"), int(os.getenv("SECCON_PORT")))
plaintext1 = b"a"*16
plaintext2 = b"a"*15 + b"b"
c1, t1 = encrypt(1, plaintext1)
c2, t2 = encrypt(1, plaintext2)
t1, t2 = to_poly(t1), to_poly(t2)
c1, c2 = to_poly(c1), to_poly(c2)
H1 = ((t1+t2) / (a^127 + a^126)).sqrt()
S1 = t1 + c1*H1*H1 + L*H1
k1 = to_poly(plaintext1) + c1
c1, t1 = encrypt(2, plaintext1)
c2, t2 = encrypt(2, plaintext2)
t1, t2 = to_poly(t1), to_poly(t2)
c1, c2 = to_poly(c1), to_poly(c2)
H2 = ((t1+t2) / (a^127 + a^126)).sqrt()
S2 = t1 + c1*H2*H2 + L*H2
k2 = to_poly(plaintext1) + c1
plaintext1 = to_poly(plaintext1)
plaintext2 = to_poly(plaintext2)
m = to_bytes((k2*H2*H2 + L*H2 + S2 + k1*H1*H1 + L*H1 + S1)/(H1*H1 + H2*H2))
io.recvuntil(">")
io.sendline("2") # dual summon
io.sendline(m.hex())
io.recvline()
print(io.recvline())
Tidal wave
description
solves: 19
---
A torrent of data.
source
import random
from Crypto.Util.number import getPrime
import secrets
from flag import flag
def get_Rrandom(R):
return secrets.randbelow(int(R.order()))
def make_G(R, alphas):
mat = []
for i in range(k):
row = []
for j in range(n):
row.append(alphas[j]^i)
mat.append(row)
mat = matrix(R, mat)
return mat
def split_p(R, p, prime_bit_length, length):
step = ceil(prime_bit_length/length)
res = []
while p > 0:
res.append(ZZ(p % (2**step)))
p >>= step
return vector(R, res)
def make_random_vector(R, length):
error_range = 2^1000
res = []
for _ in range(length):
res.append(R(secrets.randbelow(int(error_range))))
return vector(R, res)
def make_random_vector2(R, length):
error_cnt = 28
res = vector(R, length)
error_pos = random.sample(range(length), error_cnt)
for i in error_pos[:error_cnt//2]:
res[i] = get_Rrandom(R)*p
for i in error_pos[error_cnt//2:]:
res[i] = get_Rrandom(R)*q
return vector(R, res)
n, k = 36, 8
prime_bit_length = 512
p = getPrime(prime_bit_length)
q = getPrime(prime_bit_length)
N = p*q
R = Zmod(N)
alphas = vector(R, [get_Rrandom(R) for _ in range(n)])
G = make_G(R, alphas)
dets = [G.submatrix(0,i*k-i,8,8).det() for i in range(5)]
double_alphas = list(map(lambda x: x^2, alphas))
alpha_sum_rsa = R(sum(alphas))^65537
keyvec = vector(R, [get_Rrandom(R) for _ in range(k)])
pvec = split_p(R, p, prime_bit_length, k)
p_encoded = pvec*G + make_random_vector(R, n)
key_encoded = keyvec*G + make_random_vector2(R, n)
print(f"{N=}")
print(f"{dets=}")
print(f"{double_alphas=}")
print(f"{alpha_sum_rsa=}")
print(f"{p_encoded=}")
print(f"{key_encoded=}")
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
key = hashlib.sha256(str(keyvec).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
encrypted_flag = cipher.encrypt(pad(flag, AES.block_size))
print(f"{encrypted_flag=}")
step1: alphaの導出
この問題はまず
今回求める行列は Vandermonde matrix (https://en.wikipedia.org/wiki/Vandermonde_matrix) という名前がついています。
その行列式は以下の形式になることが知られています。今回は正方行列ではないので、これを少しずつずらして複数与えられます。
また今回の問題では、
しかしながらすべて
ここで、
頑張って求めても良いですが、 groebner_basis
を求めることで、この式変形を自動的に求めることができます。これはsagemathにも実装されており、簡単に使うことができます。(https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/multi_polynomial_ideal.html)
もちろん、これらの式すべての groebner_basis を求めることで
そこで、まずは行列式と、
これらは最大でも8次なので、現実的な時間で計算することができます。
ここではまだ答えが求まらないので、variety
を利用することができないため、variety
ではなく groebner_basis
を利用することが大切です
def get_alphas():
PR = PolynomialRing(R,"x",n)
xs = PR.gens()
length = k
l = 1
polys = []
for l in range(5):
print("---", l, "---")
offset = l * 7
poly = 1
for i in range(length):
for j in range(0, i):
poly *= (xs[i+offset] - xs[j+offset])
poly -= dets[l]
polys.append(poly)
for i in range(n):
x2s = []
for i in range(length):
polys.append(xs[i+offset]^2 - double_alphas[i+offset])
I = ideal(polys)
basis = I.groebner_basis()
param_sum = 0
coefficients = []
for i in range(1, len(basis)):
print(basis[i]
この実行結果は以下のようになります。
x0 + 101167463165697523840879155236135415366380424009464416331763855106184994633902302674087295255438751596774946284741606345729143993302112286520469294367507812315056318317781265297438013015868686890078715661635388273272226617417231986427962523043300715969264411559608335541462289882989793354071670690306513709519*x35
x1 + 99816305691223099820353394198653556348673685338452752390709712662751963955018291035690933586495874204856425012304440226888304154089937984356244091799405992883850252885469253083907806945264024073842402938150768910238393582861876052386054944373525820386502846106714272089979496347781222903621586813884929103048*x35
x2 + 153947320566716262616994979410188678739855205152591327118109633632831079874904201207623989372460852121565808503574990737588802732830815358621180239941162812988178974481362876713673930653580228231369894797024458703841541697777606681268859123289780674638214333073327446050895932236334966741881459108747047657435*x35
...
この結果を用いることで、上記求めた係数の和を
また、
以下のコードで
def get_alphas():
PR = PolynomialRing(R,"x",n)
xs = PR.gens()
length = k
l = 1
polys = []
for l in range(5):
print("---", l, "---")
offset = l * 7
poly = 1
for i in range(length):
for j in range(0, i):
poly *= (xs[i+offset] - xs[j+offset])
poly -= dets[l]
polys.append(poly)
for i in range(n):
x2s = []
for i in range(length):
polys.append(xs[i+offset]^2 - double_alphas[i+offset])
I = ideal(polys)
basis = I.groebner_basis()
param_sum = 0
coefficients = []
for i in range(1, len(basis)):
param_sum += -basis[i].coefficient(xs[-1])
coefficients.append(-basis[i].coefficient(xs[-1]))
param_sum += 1
last_alpha = alpha_sum_rsa / (param_sum^65537) / pow(double_alphas[-1], 32768)
predict_alphas = []
for c in coefficients:
predict_alphas.append(c*last_alpha)
predict_alphas.append(last_alpha)
return predict_alphas
step2: pの導出
次に
ただし、
この問題は典型的なLWE(Learning with Errors)問題です。
CVP(Closest Vector Problem)という問題を解くことでもこの問題を解くことができます。
CVPを求めるためには https://github.com/rkm0959/Inequality_Solving_with_CVP これが便利です。
しかしながら、これで
今回の問題は
def get_p(alphas):
error_range = 2^1000
G = make_G(R, alphas)
r = p_encoded
GZZ = G.change_ring(ZZ)
NI = (N) * matrix.identity(ZZ, n)
Ik = matrix.identity(ZZ, k)
Zero = matrix(ZZ, n, k)
step = ceil(prime_bit_length/k)
# [m1, m2, ..., mk, k1, k2, ..., kn]
mat = block_matrix(
[
[GZZ , Ik ],
[NI , Zero ]
]
)
lb = [ZZ(r[i]) - error_range for i in range(n)] + [0 for i in range(k)]
ub = [ZZ(r[i]) + error_range for i in range(n)] + [2**step for i in range(k)]
load("./rkm.sage")
result, applied_weights, fin = solve(mat, lb, ub)
pbar = 0
for i in range(k):
pbar += R(fin[i] * 2^(step*i))
PR.<x> = PolynomialRing(R)
f = x + pbar
x0 = f.small_roots(X=2^step, beta=0.3)[0]
return ZZ(x0 + pbar)
step3: keyvecの復元
最後にkeyvecを求める問題です。
実は、この問題はmod pとmod qを取るとGeneralized Reed Solomon (https://doc.sagemath.org/html/en/reference/coding/sage/coding/grs_code.html) の復元そのものです。
sagemathの機能を使うと簡単に求めることができます。
def test_p(p, c, alphas):
F = GF(p)
alphas = alphas.change_ring(F)
l = []
for i in range(n):
l.append(F(i))
row = []
G = make_G(F, alphas)
C = codes.GeneralizedReedSolomonCode(alphas, k)
return C.decode_to_message(c)
def get_keyvec(alphas, p, q):
R = Zmod(N)
G = make_G(R, alphas)
from params import key_encoded
key_encoded = vector(key_encoded)
alphas = vector(alphas)
mp = test_p(p, key_encoded, alphas).change_ring(ZZ)
mq = test_p(q, key_encoded, alphas).change_ring(ZZ)
mm = []
for i in range(len(mp)):
mm.append(crt([mp[i], mq[i]], [p, q]))
return vector(mm)
これでkeyvecを復元することができたので、この問題を解くことができました。
from params import *
R = Zmod(N)
n, k = 36, 8
prime_bit_length = 512
def make_G(R, alphas):
mat = []
for i in range(k):
row = []
for j in range(n):
row.append(alphas[j]^i)
mat.append(row)
mat = matrix(R, mat)
return mat
def get_alphas():
PR = PolynomialRing(R,"x",n)
xs = PR.gens()
length = k
l = 1
polys = []
for l in range(5):
print("---", l, "---")
offset = l * 7
poly = 1
for i in range(length):
for j in range(0, i):
poly *= (xs[i+offset] - xs[j+offset])
poly -= dets[l]
polys.append(poly)
for i in range(n):
x2s = []
for i in range(length):
polys.append(xs[i+offset]^2 - double_alphas[i+offset])
I = ideal(polys)
basis = I.groebner_basis()
param_sum = 0
coefficients = []
for i in range(1, len(basis)):
param_sum += -basis[i].coefficient(xs[-1])
coefficients.append(-basis[i].coefficient(xs[-1]))
param_sum += 1
last_alpha = alpha_sum_rsa / (param_sum^65537) / pow(double_alphas[-1], 32768)
predict_alphas = []
for c in coefficients:
predict_alphas.append(c*last_alpha)
predict_alphas.append(last_alpha)
return predict_alphas
def get_p(alphas):
error_range = 2^1000
G = make_G(R, alphas)
r = p_encoded
GZZ = G.change_ring(ZZ)
NI = (N) * matrix.identity(ZZ, n)
Ik = matrix.identity(ZZ, k)
Zero = matrix(ZZ, n, k)
step = ceil(prime_bit_length/k)
# [m1, m2, ..., mk, k1, k2, ..., kn]
mat = block_matrix(
[
[GZZ , Ik ],
[NI , Zero ]
]
)
lb = [ZZ(r[i]) - error_range for i in range(n)] + [0 for i in range(k)]
ub = [ZZ(r[i]) + error_range for i in range(n)] + [2**step for i in range(k)]
load("./rkm.sage")
result, applied_weights, fin = solve(mat, lb, ub)
pbar = 0
for i in range(k):
pbar += R(fin[i] * 2^(step*i))
PR.<x> = PolynomialRing(R)
f = x + pbar
x0 = f.small_roots(X=2^step, beta=0.3)[0]
return ZZ(x0 + pbar)
def test_p(p, c, alphas):
F = GF(p)
alphas = alphas.change_ring(F)
l = []
for i in range(n):
l.append(F(i))
row = []
G = make_G(F, alphas)
C = codes.GeneralizedReedSolomonCode(alphas, k)
return C.decode_to_message(c)
def get_keyvec(alphas, p, q):
R = Zmod(N)
G = make_G(R, alphas)
from params import key_encoded
key_encoded = vector(key_encoded)
alphas = vector(alphas)
mp = test_p(p, key_encoded, alphas).change_ring(ZZ)
mq = test_p(q, key_encoded, alphas).change_ring(ZZ)
mm = []
for i in range(len(mp)):
mm.append(crt([mp[i], mq[i]], [p, q]))
return vector(mm)
alphas = get_alphas()
p = ZZ(get_p(alphas))
q = ZZ(N // p)
print(f"{p=}")
keyvec = get_keyvec(alphas, p, q)
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
key = hashlib.sha256(str(keyvec).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(encrypted_flag)
print(flag)
Discussion