WMCTF-Qualifier-2023/Crypto/signin writeup
1. challenge
Do you konw yeye5👴? Well well, let's sgin in.
https://cdn.jsdelivr.net/gh/dawnwhisper/img-bed/images/202308021949352.png
Attachment:
Chinese mainland: 链接: https://pan.baidu.com/s/1jXq_vjCSKGo7242JnndcTg?pwd=GAME 提取码: GAME
Other regions: https://drive.google.com/file/d/1Sh31au3YD_VglAOlA5UObNT2-Fu5FtSc/view?usp=sharing
Launch an instance
task.py
from Crypto.Util.number import *
from random import randrange
from secret import flag
def pr(msg):
print(msg)
pr(br"""
....''''''....
.`",:;;II;II;;;;:,"^'.
'"IlllI;;;;;;;;;;;;;Il!!l;^.
`l><>!!!!!!!!iiiii!!!!!!!!i><!".
':>?]__++~~~~~<<<<<<<<<<<<<<<<~~+__i".
.:i+}{]?-__+++~~~~~~<<<<<~~~~~~+_-?[1_!^
.;<_}{]-_++~<<<<<<<<<<<<<<<<<<<~+-?]|]+<^
.!-{t|[?-}(|((){_<<<<<<<<<_}1)))1}??]{t|]_"
!)nf}]-?/){]]]_<<<<<<<<<_]]}}{/?-][)vf?`
'!tX/}]--<]{Un[~~<<<<<~~<~-11Yz)<--?[{vv[".
.<{xJt}]?!ibm0%&Ci><<<<<<<<!0kJW%w+:-?[{uu)},
!1fLf}]_::xmqQj["I~<<<<<<>"(ZqOu{I^<?[{cc)[`
`}|x}]_+<!<+~<<__~<<<<<<+_<<_+<><++-[1j/(>
!j/{]-++___--_+~~<i;I>~~~__-______?}(jf}`
;~(|}?_++++~~++~+]-++]?+++~~~~+++-[1/]>^
;([?__+_-?]?-_-----__-]?-_+++-]{/].
l||}?__/rjffcCQQQQQLUxffjf}+-]1?'
,[)[?}}-__[/nzXXvj)?__]{??}((>.
.I[|(1{]_+~~~<~~<<<~+_[}1(1+^
,~{|)}]_++++++-?}1)1?!`
."!_]{11))1{}]-+i:'
.`^","^`'.
""".decode())
def gen_prime(bit):
while 1:
P = getPrime(bit)
if len(bin(P)) - 2 == bit:
return P
pq_bit = 512
offset = 16
P,Q = [gen_prime(pq_bit) for i in range(2)]
N = P * Q
gift = int(bin(P ^ (Q >> offset))[2+offset:],2)
pr(N)
pr(gift)
inpP = int(input())
if inpP != P:
pr(b"you lose!")
exit()
secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]
results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** offset - 1) for ri in results]
pr(bs)
pr(rs)
inpsecret = int(input())
if inpsecret == secret:
pr(flag)
2. 分析
题目有两个关卡
-
根据 分解N -
由低16位信息的38组方程求解随机数secret
io
from pwn import *
context.log_level = 'info'
r = None
def init_connect():
global r
if r is not None:
r.close()
r = process("./task.py")
# r = remote("1.13.101.243",28632)
def stage1_params():
global r
init_connect()
r.recvuntil(b'''.`^","^`'.''')
r.recvuntil(b'n')
r.recvuntil(b'n')
N = int(r.recvuntil(b'n').strip())
gift = int(r.recvuntil(b'n').strip())
print("N:", N)
print("gift:", gift)
return N, gift
def stage1_answer(p):
r.sendline(str(p).encode())
def stage2_params():
r.recvuntil(b"[")
bs = [int(b.strip()) for b in r.recvuntil(b"]").strip(b"]").split(b",")]
r.recvuntil(b"[")
rs = [int(b.strip()) for b in r.recvuntil(b"]").strip(b"]").split(b",")]
r.recvuntil(b'n')
return bs, rs
def stage2_answer(secret):
r.sendline(str(secret).encode())
print(r.recvline())
2.1 关卡一：二分法
因为异或是按位运算，因此适合使用二分法逐位还原p, q
对 , 记 , 有：
考虑 k+1 :
每次遍历k, 可以使用(a)式猜测 ,使用 (b) 式验证猜测结果， 猜测的两个 中至少有一个值是正确的。
可能有很多组解满足 ,再使用 n=pq 找到其中的正确解。
本题与上述问题有所区别，q只有高位参与了异或，低位是未知的。
可以先爆破q的低位 ql 后，再使用(a)式猜测
使用 (b) 式验证猜测结果：
-
2个猜测值都错误，则说明 ql 错误， 重新爆破 ql -
1个正确结果，则继续迭代
与上个问题不同的是，这里很难出现2个猜测值都符合的情况, 因为每一轮q参与乘法运算的bit都是确定的。
import tqdm.notebook as tqdm
from tqdm import trange
bit = 512
offset = 16
def stage1_binary_search(N, gift):
def check(q, k):
qh = q >> offset
p = (gift & (2^k-1)) ^^ qh
return (p * q - N) % 2^k == 0
def binary_search(ql):
q = ql
for k in range(bit-offset):
# q_{k+1} = q_k
if not check(q, k+1):
# q_{k+1} = q_k + 2^k
q = q + 2^(k+offset)
if not check(q, k+1):
return False
if N % q == 0:
print("found")
return q
def solve():
box = []
ql = 2
while ql.nbits() < 16:
box.append(ql)
ql = ql.next_prime()
box += list(set(range(3,2^16,2)) - set(box))
for ql in tqdm.tqdm(box):
q = binary_search(ql)
if q:
return q
q = solve()
assert N % q == 0
p = N // q
return p
N, gift = stage1_params()
p = stage1_binary_search(N, gift)
print("p:", p)
stage1_answer(p)
[x] Starting local process './task.py'
[+] Starting local process './task.py': pid 55051
N: 85466391071560677583277742717968645951511645922872920607564176037214309947198243031165275109633145830930220070328946480625646663925154505046164485944739528307309057874379030015550902797420066810340564664064567908301924007777226490133305272574205098914748291118432703918087250186637794239498083517328838030731
gift: 114371674224937117546758740929491825252031792599478421554638003622100939710944314827794073546199643845005875603218842206638455651272159928720456782859
0%| | 0/32768 [00:00<?, ?it/s]
found
p: 7570195739207543486406092314807897901568024503999628297779590606687320365025533817418641336805189316623080866597420860796827231795172847315383158330644079
2.2 关卡二：格 HNP
有同余式
方程组中 是较小值， 但每个方程的 都不相同，变量过多难以同时规约。
考虑将 单独放在等式左边，格基规约时 直接位于结果矩阵中 ，这样格中就只有 在每个方程中不同了。
运气好的话, secret 可以直接求出来。
一般情况，应以求 为目标， 然后再还原secret。
bs, rs = stage2_params()
c = Integer(pow(2, -16, p))
M = block_matrix([
[
identity_matrix(38) * p, 0
],
[
matrix([
[c*bi for bi in bs],
[-c*ri for ri in rs]
]), 1
]
])
bound = 2^(512-16)
bounds = [bound]*38 + [2^512, 1]
Q = diagonal_matrix(2^512 // b for b in bounds)
def check_secret(secret):
for bi, si in zip(bs, rs):
if bi*secret % p % 2^16 != si:
return False
return True
def calculate_secret_by_rh(rh):
rl = rs[0]
b = bs[0]
r = rh*2^16 + rl
s = r*inverse_mod(b, p)%p
return s
L = M*Q
B = L.LLL()/Q
for v in B:
indicator = v[-1]
if abs(indicator)==1:
# take a chance
s = abs(v[-2])
if check_secret(s):
print("lucky")
break
s = calculate_secret_by_rh(abs(v[0]))
if check_secret(s):
print("by rh")
break
print("secret:", s)
by rh
secret: 5931399544459657756299336491548333133819923598257428426250253671264845370029299810371919660641724170652491277235835827548316400005199590262547987436161115
stage2_answer(s)
[*] Process './task.py' stopped with exit code 0 (pid 55051)
b"b'wmctf{we1c0me_brOo0Oo!hope_y0u_h4v3_fun_iN_the_fTcmWWmcTf/}'n"
本文同步发布于
-
知乎专栏/石头的安全料理屋：https://zhuanlan.zhihu.com/p/652111683 -
微信公众号/石头的安全料理屋 -
博客: https://ssst0n3.github.io/post/%E7%BD%91%E7%BB%9C%E5%AE%89%E5%85%A8/CTF/crypto/lattice/HNP/WMCTF-Qualifier-2023Cryptosignin-writeup.html
原文始发于微信公众号（石头的安全料理屋）：WMCTF-Qualifier-2023/Crypto/signin writeup
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论