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. 分析

题目有两个关卡

  1. 根据 $N=pq, p\oplus q$ 分解N
  2. 由低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

对 $n=pq, g=p\oplus q$ , 记 $p_k \equiv p \pmod {2^{k}}$ , 有：

$$ \begin{align*} & n_k \equiv p_kq_k \pmod {2^k} \newline & p_k = g_k \oplus q_k \end{align*} $$

考虑 k+1 :

$$ \begin{align*} & q_{k+1} = {q_k, 2^k+q_k} \qquad (a) \newline & p_{k+1} = g_{k+1} \oplus q_{k+1} \newline & n_{k+1} \equiv p_{k+1}q_{k+1} \pmod {2^{k+1}} \qquad (b) \end{align*} $$

每次遍历k, 可以使用(a)式猜测 $q_{k+1}$ ,使用 (b) 式验证猜测结果， 猜测的两个 $q_{k+1}$ 中至少有一个值是正确的。

可能有很多组解满足 $p_{512}q_{512}=n_{512}$ ,再使用 n=pq 找到其中的正确解。

本题与上述问题有所区别，q只有高位参与了异或，低位是未知的。

$n=pq, qh = q»offset, g=p\oplus qh $

可以先爆破q的低位 ql 后，再使用(a)式猜测 $qh_{k+1}$

$p_{k+1} = g_{k+1} \oplus qh_{k+1}$

使用 (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

有同余式

$$ \begin{align*} &r_i \equiv b_i * secret \pmod p \newline &r_i \equiv rs_i \pmod {2^{16}} \newline \Rightarrow& \newline &rh_i * 2^{16} + rl_i \equiv b_i * secret \pmod p\newline \Rightarrow& \newline &\underbrace{rh_i}_{? ~~ 496bit} * 2^{16} + rl_i = b_i * \underbrace{secret}_{?~~512bit} + \underbrace{k_i}_{?~~512bit}p \end{align*} $$

方程组中 $rh_i$ 是较小值， 但每个方程的 $rh_i, k_i$ 都不相同，变量过多难以同时规约。

考虑将 $rh_i$ 单独放在等式左边，格基规约时 $rh_i$ 直接位于结果矩阵中 ，这样格中就只有 $k_i$ 在每个方程中不同了。

$$ \begin{align*} &rh_i * 2^{16} + rl_i \equiv b_i * secret \pmod p \newline \Rightarrow& \newline &rh_i \equiv 2^{-16}*(b_i * secret - rl_i) \pmod p \newline \Rightarrow& \newline &rh_i = k_ip + 2^{-16}*(b_i * secret - rl_i) \newline \end{align*} $$

$$ \begin{align*} &AL \newline =&[k_1, \dots, k_n, secret, 1] \begin{bmatrix} p& \newline &\ddots\newline &&p\newline b_12^{-16}&\cdots &b_n2^{-16}&1 \newline -rs_12^{-16}&\cdots &-rs_n2^{-16}&&1 \newline \end{bmatrix}\newline =&[rh_1, \cdots, rh_n, secret, 1] \end{align*} $$

运气好的话, secret 可以直接求出来。

一般情况，应以求 $rh_i$ 为目标， 然后再还原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"

本文同步发布于