Hitcon2021 Crypto Writeup

2021-12-14

字数统计: 1.9k字 | 阅读时长≈ 9分

第一次和Tea Deliverers打比赛，被学长带飞了，这次crypto方向的题目还是比较友好的，但是我写题和exp写的是真慢。td最后总排名第三。简单记录一下 crypto 方向题目的解法和exp。hitcon总体赛题质量还是非常顶的。

so easy rsa [210pts]

源码：

from gmpy2 import next_prime, is_prime
from random import randint
from Crypto.Util.number import bytes_to_long

class Rand:
    def __init__(self):
        self.seed = randint(2, 2**512)
        self.A = next_prime(randint(2, 2**512))
        self.B = next_prime(randint(2, 2**512))
        self.M = next_prime(randint(2, 2**512))
        for _ in range(10000):
            self.next()
    
    def next(self):
        self.seed = self.seed * self.A + self.B
        self.seed = self.seed % self.M
        return self.seed

    def __str__(self):
        return f"{self.A}, {self.B}, {self.M}"
        

def gen_prime(r):
    while True:
        v = r.next()
        if is_prime(v):
            return v

r = Rand()
p,q = gen_prime(r), gen_prime(r)
n = p*q
e = 65537
flag = bytes_to_long(open('flag','rb').read())
val = pow(flag, e, n)

print(n)
print(r)
print(val)

实现了一个简单的LCG伪随机数生成器，并且用该随机数生成器生成了p，q。利用LCG的特性，我们测试发现，p，q生成的过程，一般在1000轮以下，也就是next的执行次数，这个轮次完全可以爆破。利用LCG的方程： $output=A*x+B \ \ mod\ \ M$ 。得到p,q之间满足关系： $q=A_i*p+B_i \ \ mod \ \ M$ 。 $A_i,B_i$ 可以直接递推，也可以算通式。我们确定每个轮次直接p，q可能存在的关系，解下面的模方程： $(A_i*x+B_i)x=n \ \ mod \ \ M$ ，如果 $gcd(x,n)!=1$ ，则分解成功。之后进行解密即可。

# sage
from gmpy2 import next_prime, is_prime
from random import randint
from Crypto.Util.number import bytes_to_long, inverse, long_to_bytes
n=198148795890507031730221728469492521085435050254010422245429012501864312776356522213014006175424179860455397661479243825590470750385249479224738397071326661046694312629376866307803789411244554424360122317688081850938387121934893846964467922503328604784935624075688440234885261073350247892064806120096887751
A,B,M=1677936292368545917814039483235622978551357499172411081065325777729488793550136568309923513362117687939170753313352485633354858207097035878077942534451467, 5687468800624594128838903842767411040727750916115472185196475570099217560998907467291416768835644005325105434981167565207313702286530912332233402467314947, 1244793456976456877170839265783035368354692819005211513409129011314633866460250237897970818451591728769403864292158494516440464466254909969383897236264921
cipher=48071438195829770851852911364054237976158406255022684617769223046035836237425012457131162001786019505606941050117178190535720928339364199078329207393922570246678871062386142183424414041935978305046280399687623437942986302690599232729065536417757505209285175593543234585659130582659013242346666628394528555
e = 65537
R.<x> = PolynomialRing(Integers(M))

for i in range(1,2000):
    a=ZZ(pow(A,i,M))
    b=ZZ((sum(A_list)+1)*B%M)
    A_list.append(a)
    B_list.append(b)
    poly=(a*x+b)*x-n
    r=poly.roots()
    print("[+] rounds %d "%i,r)
    if len(r)==0:
        continue
    if gcd(r[1][0],n)!=1 or gcd(r[0][0],n)!=1:
        print("[+] find good solution",r)
        res=[gcd(r[1][0],n),gcd(r[1][0],n)]
        break

print(res)

p=243910118538351506548384880034426728169248862274637495579956619639346929105044407816656098657792419005522183874367421793338227934532131627126006227183679
q=ZZ(n/p)

assert p*q==n
d=inverse_mod(e,(p-1)*(q-1)))
print(long_to_bytes(int(pow(cipher,d,n))))
# hitcon{so_weak_randomnessssss}

a little easy rsa [240pts]

源代码:

from Crypto.Util.number import *

N = 1024
P = 211
p = getPrime(P)
q = getPrime(N-P)
n = p*q
print(n.bit_length())
d = p
e = inverse(d, (p-1)*(q-1))
flag = bytes_to_long(open('flag','rb').read())

print(n)
print(e)
print(pow(flag, e, n))

其实一开始感觉有很多方法可以尝试，p，q相差看似很大，但是分解不出来，另外解密指数p大约是 $N^{0.2}$ ，很小，看似可以满足Wiener Attack的条件，但也是因为p，q相差过大，不能用，只可以在p，q比较接近的情况下才能Wiener Attack。只剩下e本身的特性了。注意到： $e*p=1 \ \ mod (p-1)(q-1)$ ，也就是解密的公式： $a^{e*p}=a \ mod\ n$ 。同样地就有： $a^{e*p}=a \ \ mod\ \ p$ ，而由费马定理，也就是模p乘法群的阶为p-1， $a^p=a \ \ mod \ \ p$ 。那么对于任意整数，我们就有： $a^e=a \ \ mod \ \ p$ 。所以 $gcd(a^e-a \ mod\ n ,n)=p$ 。这样就分解了n，之后正常RSA解密即可。 $e == 1 mod (p-1)$

算完发现可能非预期了，和coppersmith有关。

from Crypto.Util.number import *
n=73105772487291349396254686006336120330504972930577005514215080357374112681944087577351379895224746578654018931799727417401425288595445982938270373091627341969888521509691373957711162258987876168607165960620322264335724067238920761042033944418867358083783317156429326797580005138985469248465425537931352359757
e=4537482391838140758438394964043410950504913123892269886065999941390882950665896428937682918187777255481111874006714423664290939580653075257588603498124366669194458116324464062487897262881136123858890202346251370203490050314565294751740805575602781718282190046613532413038947173662685728922451632009556797931
c=14558936777299241791239306943800914301296723857812043136710252309211457210786844069103093229876701608756952780774067174377636161903673229776614350695222134040119114881027349864098519027057618922872932074441000483969146246381640236171500856974180238934543370727793393492372475990330143750179123498797867932379

a=pow(2,e,n)
p=GCD(a-2,n)
q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
flag=long_to_bytes(pow(c,d,n))
print(flag)
# b'hitcon{~~so_triviAl_coPper5mitH~~}\n'

so easy but not rsa [305pts]

源代码：

from Crypto.Util.number import bytes_to_long as b2l
from Crypto.Util.number import long_to_bytes as l2b
import random

load('secretkey.sage')

Zx.<x> = ZZ[]
def convolution(f,g):
  return (f * g) % (x^n-1)

def balancedmod(f,q):
  g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
  return Zx(g)  % (x^n-1)

def randomdpoly(d1, d2):
  result = d1*[1]+d2*[-1]+(n-d1-d2)*[0]
  random.shuffle(result)
  return Zx(result)

def invertmodprime(f,p):
  T = Zx.change_ring(Integers(p)).quotient(x^n-1)
  return Zx(lift(1 / T(f)))

def invertmodpowerof2(f,q):
  assert q.is_power_of(2)
  g = invertmodprime(f,2)
  while True:
    r = balancedmod(convolution(g,f),q)
    if r == 1: return g
    g = balancedmod(convolution(g,2 - r),q)

def keypair():
  while True:
    try:
      f = randomdpoly(61, 60)
      f3 = invertmodprime(f,3)
      fq = invertmodpowerof2(f,q)
      break
    except Exception as e:
      pass
  g = randomdpoly(20, 20)
  publickey = balancedmod(3 * convolution(fq,g),q)
  secretkey = f
  return publickey, secretkey, g

def encode(val):
    poly = 0
    for i in range(n):
        poly += ((val%3)-1) * (x^i)
        val //= 3
    return poly

def encrypt(message, publickey):
  r = randomdpoly(18, 18)
  return balancedmod(convolution(publickey,r) + encode(message), q)


n, q = 263, 128
publickey, _, _ = key # key = keypair()

flag = b2l(open('flag', 'rb').read())
print(encrypt(flag, publickey))
print(publickey)

# generate a lots of random data
data = [ random.getrandbits(240) for _ in range(200)]
for random_msg in data:
    print(l2b(random_msg).hex(), encrypt(random_msg, publickey))

注意到这句话generate a lots of random data，那么其实这题也就和NTRU格密码关系不大，但我一直往NTRU格密码方向想，直到zzh拿了一血，orz。这是典型的MT19937伪随机数生成器的问题，题目特意生成了连续的200*240比特的MT19937的随机数。那么完全可以恢复出之前的MT19937的状态。之后尝试加密flag时候的offset（找到 r = randomdpoly(18, 18) 时的MT19937矩阵的状态即可），直到解密出来的字符串满足flag的要求。

l = []
with open('prob/data') as f:
    lines = f.readlines()
for line in lines[2:]:
    l.append(int(line.split()[0], 16))

MT = [None] * 1600
for i in range(200):
    for j in range(7):
        MT[i * 8 + j] = (l[i] >> (j * 32)) & (2 ** 32 - 1)

def untempering(y):
    y ^= y >> 18
    y ^= (y << 15) & 0xEFC60000
    y ^= (
        ((y << 7) & 0x9D2C5680)
        ^ ((y << 14) & 0x94284000)
        ^ ((y << 21) & 0x14200000)
        ^ ((y << 28) & 0x10000000)
    )
    y ^= (y >> 11) ^ (y >> 22)
    return y

for i in range(1600):
    if MT[i] is not None:
        MT[i] = untempering(MT[i])

MT = [None] * 624 * 2 + MT

from z3 import *

for i in range(624):
    if MT[i] is None:
        MT[i] = BitVec(f'x_{i}', 32)
    else:
        MT[i] = BitVecVal(MT[i], 32)

s = Solver()
for i in range(624, len(MT)):
    y = (MT[i - 624] & 0x80000000) | (MT[i - 624 + 1] & 0x7FFFFFFF)
    new_value = MT[i + 397 - 624] ^ LShR(y, 1) ^ (0x9908B0DF & SignExt(31, Extract(0, 0, y)))
    if MT[i] is not None:
        MT[i] = BitVecVal(MT[i], 32)
        s.add(new_value == MT[i])
    else:
        MT[i] = new_value

print(s.check())
m = s.model()
seeds = [None] * 624
for i in range(624):
    seeds[i] = m.evaluate(MT[i]).as_long()

import random
random.setstate((3, tuple(seeds) + (0,), None))

def decode(poly):
    msg = 0
    for i in range(n-1, -1, -1):
        msg *= 3
        msg += int(poly[i]) + 1
    return msg

for i in range(624 * 2):
    random.setstate((3, tuple(seeds) + (0,), None))
    for j in range(i):
        random.getrandbits(32)
    r = randomdpoly(18, 18)
    flag = decode(balancedmod(enc_flag - convolution(publickey,r), q))
    try:
        flag = l2b(flag)
        print(flag)
    except:
        pass

still not rsa [321pts]

NTRU格密码的选择密文攻击，找到了两篇paper：

paper1：A Chosen-Ciphertext Attack against NTRU

paper2 : Imperfect Decryption and an Attack on the NTRU Encryption Schem

这里不再详细叙述NTRU格加密流程与理论叙述，想要了解可以参考wiki或者其他博客。

比赛的时候两篇论文都仔细读了，第一篇看的是paper1，发现利用paper1的攻击适合可选择的明文比较少的情况，一般只需要两次或者不超过几十次（穷举量），paper1的穷举量与f和g的结构相关，定义k=f AND G，AND指相应多项式次数的系数进行与运算，当多项式k的非0次数项较少时，不超过3（在NTRU的n比较大时，具体可以根据不同NTRU格参数的信息进行本地测试），我们可以简单选择两个密文对私钥进行攻击。记多项式k的非0系数的个数为collision，几种标准的NTRU参数的collision概率如下，collision越小，私钥攻击的穷举量越少。

该攻击的原理如下：

$cipher=c*h+c$ ，其中c是整数，h是公钥，并且c的选取要保证 $c\ |\ p ，并且q/4<c<q/2$ 。具体推导可以参考paper，如果我们得的解密的信息为m，那么私钥可以通过下面等式恢复： $f ≡ −qk * m^{−1} \ mod \ p$ 。从这个式子我们就可以明白为什么collision需要比较小，因为它直接决定了密钥恢复的穷举量。

本次赛题中给的是标准NTRU密码体系的case B参数，当然修改了部分参数，我在本地测试发现f和g的碰撞collision<=3的概率在0.1%，小于2的概率在0.01%，需要nc重连至少10000次，而且每次还需要进行不小的穷举量。肯定是不可行的。当然这篇paper的价值在于可以只通过一次选择密文恢复密钥。

另外一篇paper的算法就是本题的解法，它利用的是NTRU密码的一个特性：Decryption Fault，即解密错误。具体实现算法3即可，其中Decryption Fault的产生可以从加密时选择非0系数比较少的随机多项式r，m进行随机选择即可。

注意这只是恢复了一个等价密钥，另外需要完全恢复还需要乘以一个$x^k$或者$-x^k$，至于k，进行穷举即可。得到一组Decryption Fault之后就可以进行本地爆破。

脚本如下

from Crypto.Util.number import bytes_to_long as b2l
from Crypto.Util.number import long_to_bytes as l2b
from Crypto.Cipher import AES
from hashlib import sha256
import random, os, binascii

Zx.<x> = ZZ[]
def convolution(f,g):
  return (f * g) % (x^n-1)

def balancedmod(f,q):
  g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
  return Zx(g)  % (x^n-1)

def randomdpoly(d1, d2):
  result = d1*[1]+d2*[-1]+(n-d1-d2)*[0]
  random.shuffle(result)
  return Zx(result)

def invertmodprime(f,p):
  T = Zx.change_ring(Integers(p)).quotient(x^n-1)
  return Zx(lift(1 / T(f)))

def invertmodpowerof2(f,q):
  assert q.is_power_of(2)
  g = invertmodprime(f,2)
  while True:
    r = balancedmod(convolution(g,f),q)
    if r == 1: return g
    g = balancedmod(convolution(g,2 - r),q)

def keypair():
  while True:
    try:
      f = randomdpoly(61, 60)
      f3 = invertmodprime(f,3)
      fq = invertmodpowerof2(f,q)
      break
    except Exception as e:
      pass
  g = randomdpoly(15, 15)
  publickey = balancedmod(3 * convolution(fq,g),q)
  secretkey = f
  return publickey, secretkey, g

def encode_old(val):
    poly = 0
    for i in range(n):
        poly += ((val%3)-1) * (x^i)
        val //= 3
    return poly

def encode(val):
    poly = 0
    for i in range(n):
        c = val % q
        poly += (((c + q//2) % q) - q//2) * (x^i)
        val //= q
    return poly

def decode(poly):
    msg = 0
    for i in range(n-1, -1, -1):
        msg *= q
        msg += int(poly[i]) % q
    return msg

def decrypt(ciphertext, secretkey):
  f = secretkey
  f3 = invertmodprime(f,3)
  a = balancedmod(convolution(encode(ciphertext), f), q)
  return balancedmod(convolution(a, f3), 3)

n, q = 167, 128

def encrypt(message, publickey):
  r = randomdpoly(61, 60)
  return balancedmod(convolution(publickey,r) + message, q), r

from pwn import remote
r = remote("54.92.57.54", 31337)
iv = bytes.fromhex(r.recvline().decode())
flag_enc = bytes.fromhex(r.recvline().decode())
publickey = Zx(r.recvline().decode())
msgs = []
rpolys = []
print('send')
for i in range(1000):
    random_msg = encode_old(random.getrandbits(100))
    encrypted_msg, rpoly = encrypt(random_msg, publickey)
    r.sendline(l2b(decode(encrypted_msg)).hex())
    msgs.append(random_msg)
    rpolys.append(rpoly)
print('recv')
for i in range(1000):
    decrypted = Zx(r.recvline().decode())
    if decrypted != msgs[i]:
        print(i, '-----found-----')
        fp = balancedmod(decrypted - msgs[i], 3)
        fpinv = balancedmod(invertmodprime(fp, 3), 3)
        for i in range(n):
            newkey = balancedmod(convolution(x^i, fpinv), 3)
            key = sha256(str(newkey).encode()).digest()
            flag = AES.new(key, AES.MODE_CBC, iv).decrypt(flag_enc)
            if b'hitcon' in flag:
                print(flag)

magic rsa [262pts]

源码：

import os
from Crypto.Util.number import *
from hashlib import *
from binascii import unhexlify
from gmpy2 import next_prime, is_prime

LEN = 17
magic = os.urandom(LEN)
print("Magic:", magic.hex())
print('Coud you use it to do encryption as hash?')

magic_num = bytes_to_long(magic)
try:
    N = int(input('N:>'))
    e = int(input('E:>'))
    data = unhexlify(input('data:>'))
    if N >> (384 - LEN*8) == magic_num:
        data2 = sha384(data).digest()
        num1 = bytes_to_long(data)
        num2 = bytes_to_long(data2)
        if pow(num1, e, N) == num2:
            print(open('flag','r').read())
        else:
            print('try harder!!!')
    else:
        print('try harder!')
except Exception as e:
    print('invalid')

分析：

求m使得： m^e = byets_to_long (sha384(m)) mod N。其中N和e我们都可以自由选择，但是N限定高17*8位，并且N必须有384比特长。

实际上这就是一个离散对数的求解问题，对于这种高位数的离散对数，我们可以使用Pohlig-Hellman算法，条件是N必须是一个光滑阶的素数，所谓光滑阶要求，素数N的阶N-1进行素数分解后，它的素因子都比较小，这个上界可以参考一般离散对数求解的复杂度 $\sqrt{N}$ ，因此最大素因子不超2^50次，对于sagemath来说都是很快就能解的。关于DLP一个详细的解析博客可以参考Lazzero师傅的博客：离散对数。

至于为什么找素数，这是因为素数存在原根，原根可以生成整个循环群，即dlp一定有解，否则对于一般的N，可能N的阶比N本身小很多，这会导致sha384(m)后大概率不在m所在阶群内，当然非素数也可以，只是需要额外穷举。

利用素数光滑阶群的特点，这题直接穷举即可，注意我们不要改变N的低位，我们只穷举固定17*8的高位后，剩下的最高位的2个字节，即2^16，这样不仅N的分解很快（相当于只要分解高位），还很容易找到满足条件的光滑阶素数，如果找不到满足条件的，重连即可。简单穷举脚本如下：

magic_num = 0xcc5123495bada9ef3219e6fe522fd88277
for i in range(65536):
    n = magic_num * 2 ** (384 - LEN*8) + i * 2 ** (384 - LEN*8 - 16)
    if is_prime(n + 1):
        f = factor(n)
        if all(p < 2 ** 40 for p, e in f):
            print(f)
            num1 = primitive_root(n+1)
            data = int(num1).to_bytes(2, 'big')
            print(data.hex())
            data2 = hashlib.sha384(data).digest()
            num2 = int.from_bytes(data2, 'big')
            e = discrete_log(Zmod(n+1)(num2), Zmod(n+1)(num1))
            if int(pow(num1, e, n+1)) == num2:
                print('solved')
                print(n+1)
                print(e)
                print(data.hex())

magic dlog [262pts]

相比上题，要求N是素数，思路同时，脚本同上。

当然预期解是一篇论文，给定一个范围，寻找最近的光滑阶的素数P，是用LLL做的，如果这题限制多一点，就需要实现论文的方法了。

预期解论文：Finding Smooth Integers in Short Intervals Using CRT Decoding。