分析DEF CON CTF Quals 2020中Crypto方向题目

阅读量    129526 |

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

前言

DEF CON CTF Quals 2020中共有三道CRYPTO方向题目(两道CRYPTO、一道RE+CRYPTO),题目难度适中,比赛期间三道题目都出现了非预期解,本文对这三道题目的预期解和非预期解都进行一下分析。

 

coooppersmith

题目描述

I was told by a cooopersmith that I should send hackers encrypted messages because it is secure.
coooppersmith.challenges.ooo 5000

130/500 pts, 41 solves

附件

解题思路

本题程序要求选手输入一个长度不超过120的16进制串,然后会以PEM格式打印RSA公钥,并在"Question"字符串下一行打印了一个16进制串,最后接收一个用户输入:

Please input prefix IN HEX with length no more than 120: deadbeef
Your public key:
-----BEGIN RSA PUBLIC KEY-----
MIIBCQKCAQA72hJsgSuPfUh1+EVHJMilCiEw5W5IiWOjdfRnuqdn2rsuvJSazeUg
3X0MITlZbIgM9oh7KP3uk6cGjF1HyOI1eAE4Yf8zLXHfVbFg5cx5ZcIJ7twrFgIV
Bz8kwTim8nt1bNf3AwPXpMJFr23BLMV6qaAGFcoffxgcEVz6hrHZDJYDXRfDlLGN
8a2x2w45dTLy53HR5GKV4xE4JoY9bJp7zmdJ/AVPD241XcHxDCaYh6qKeOjPAXLM
MJXR4qjHNfOJ9clzn57+V0553dPOkwsTdhtnjLo1lCuNurHinfiqQgpvJF4p7T2R
n3YE9HhPghwbiX6wwunBP4x5qI0qn47hAgMBAAE=
-----END RSA PUBLIC KEY-----
Question: 
0ffd37508c4a598298d94f0c2765114cd30ee97f7e739eb16bd9242aad138d518dc9c64be16e277975a79f96f2bc6dc18c84ee5d2056d1055f7125ee680a55b6364a66a6aa6f83743f5be558b08550586ba52bba59576bbebbf55ca06c12a43784dcbe37bef705e37ed30e73ecab4ed0d48569a9c6756d40f1f363005951d0a15b173673958b0fdc39a0b3aa3e21b71e9fa59f5552caaa656c90cea0920e15105f6f26899d4a6604b52f76f4e6ecd842a5c95aee0213b1abe48a6d36a2e34f57769cbcb963cc23765f253d998b8f21a9b7997cf42837d7b218ccab8d885a170bf589a6b41d9e6250c3a68c10429682dc1e65f7233aab8350a48fd13862734d8a

对程序进行逆向分析,定位到sub_1E25函数,程序首先通过sub_1D4E函数接收用户输入,然后通过sub_18C4处理我们输入的16进制字符串。

sub_1E25函数部分代码:

sub_18C4函数部分代码:

sub_18C4函数的返回值为r,用户输入的16进制串的10进制整数形式为u,用户输入的16进制串的长度为lx是区间[ 0, 2^(2 * (128 - l)) )上的一个随机数,则有:

接下来该函数会检查生成的r是否为素数,若为素数则返回r,否则将r值加1,继续判断是否为素数,若直到[r // 2^(4 * (128 - l))]不等于u时仍然不能找到一个素数r,则重新执行(1)式生产一个新的r并重复上述过程,直到找到一个素数r并返回该值。

接下来sub_1DD8函数会根据r的值来生成公私钥对,sub_1DD8函数调用sub_14D8函数,根据r的值采用Pocklington定理生成素数pqp不等于q)。

sub_14D8函数部分代码:

即有:

其中k_0k_1是区间[0, r + 1)上的2个随机数,接下来sub_165E函数根据pq来生成一对RSA公私钥,然后sub_1E25函数再通过PEM_write_RSAPublicKey函数以PEM格式打印公钥(e = 65537, N = p * q)。

sub_165E函数部分代码:

接下来程序调用sub_1B3E函数,该函数首先生成2个32比特的随机数xy,然后使用前面生成的RSA公钥对字符串"What's the sum of " + str(x) + " and " + str(y) + "?"进行加密,并将加密后的密文以16进制形式打印给选手,此即为"Question"字符串后面的16进制串。接下来接收用户输入,如果用户输入的数等于x + y的值,则将FLAG经过前面生成的RSA公钥加密后的密文打印给选手,否则程序结束。

sub_1B3E函数部分代码:

因此为了拿到FLAG,我们需要通过分解N计算出程序使用的公钥对应的私钥,然后先使用该私钥解密"Question"字符串后面的密文,得到随机数xy的值,再提交x + y的值,得到FLAG的密文,最后再使用该私钥对FLAG的密文进行解密,即可得到FLAG

根据(2)式和(3)式,本题中N的表达式为:

在得到N的表达式后,首先说一下非预期解,非预期解无需用到任何Coppersmith相关攻击,对(4)式变形可得:

此时有:

观察(1)式中的xx是区间[ 0, 2^(2 * (128 - l)) )上的一个随机数,当我们输入长度为最大长度120的16进制串时,x会落入[0, 2^16)这样一个小区间,此时我们可以穷举一个小区间,此时我们可以穷举x的值,对于穷举的每一个x,根据(1)式计算出其相应的r,然后根据(6)式是否成立来判断计算出的r是否正确,这样一来我们即可恢复出r的值。

恢复出r的值之后,对(5)式等式两边同除以2 * r,有:

此时有:

由于本题中p不等于q,根据(2)式和(3)式可知k_0不等于k_1,由于k_0k_1都是区间[0, r + 1)上的随机数,因此一定有k_0 + k_1 < 2 * r,此时有:

联立(5)式和(9)式,即可求出k_0k_1,从而成功分解N,继而解密密文拿到两个随机数的值,提交两个随机数的和拿到FLAG的密文,再次进行解密即可拿到FLAG

接下来说一下预期解,本题原本是想考察Coppersmith相关攻击,观察(4)式,设:

则有:

f(x) = 2 * r * x + 1, x in Zmod(N),然后我们仍然可以穷举r,此时我们可以通过Coppersmith相关攻击中计算计小整数解的方式来获取到x的值(也即k_0的值,k_1同理),POC如下(注意在SageMath下使用small_roots方法计算小整数解时要求多项式为首一多项式,因此我们需要将多项式形式做一个变形):

sage: P.<x> = PolynomialRing(Zmod(N))
....: f = x + inverse_mod(2 * r, N)
....: res = f.small_roots(X = r, beta = 0.4)
....: k_0 in res
....:
True

这样一来即可分解N,后面的步骤和前面相同,然后按照前面所说的步骤依次提交和计算即可拿到FLAG

p.s.

根据(4)式中N的表达式,本题还可直接采用Coron attack(即双变量版本的Coppersmith攻击)来分解N,相关实现可见这里

解题脚本

#!/usr/bin/env sage

import rsa
from gmpy2 import iroot
from pwn import *
from Crypto.Util.number import *

io = remote('coooppersmith.challenges.ooo', 5000)
#io = process("./service")

user_input = '000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111'

io.sendline(user_input)
_ = io.recvline()
pkeydata = io.recvuntil("-----END RSA PUBLIC KEY-----\n")
_ = io.recvline()
sum_ct = int(io.recvline().strip(), 16)

pubkey = rsa.PublicKey.load_pkcs1(pkeydata)
N = pubkey.n
e = pubkey.e

for x in range(0, 2**16):
    r = int(user_input, 16) * 2**32 + x
    if (N - 1) % r == 0:
        break

P.<x> = PolynomialRing(Zmod(N))
f = x + inverse_mod(2 * r, N)
res = f.small_roots(X = r, beta = 0.4)
k_0 = int(res[0])
p = 2 * r * k_0 + 1
q = N // p

d = inverse(e, (p - 1) * (q - 1))
sum_pt = pow(sum_ct, d, N)

tmp = long_to_bytes(sum_pt)
tmp = tmp[:-1].split(b"of ")[1].split(b" and ")
sum = int(tmp[0]) + int(tmp[1])

io.sendline(str(sum))
_ = io.recvline()
ct = int(io.recvline().strip(), 16)
pt = pow(ct, d, N)

FLAG = long_to_bytes(pt)
print(FLAG)

# OOO{Be_A_Flexible_Coppersmith}

 

notbefoooled

题目描述

What’s the trick to not be foooled?
notbefoooled.challenges.ooo 5000
143/500 pts, 30 solves

附件

解题思路

首先先说一下非预期解,本题本身预期是使用python3版本的SageMath来部署本题的Sage脚本,但是在部署时错误的使用了python2版本来部署,而本题在接受用户输入时直接使用了input函数,因此我们可以使用input函数的任意代码执行漏洞来直接拿到FLAG

然后我们来看一下预期解,服务器首先要求选手提供一条椭圆曲线的abp这3个参数的值,要求该曲线为anomalous曲线(即曲线的阶等于p)且p的值大于某一阈值,接下来服务器会随机选择该曲线的一个基点G并打印给选手,然后要求选手提交该曲线上的一个点G * k,随后服务器会用Smart’s attack对选手提供的曲线和点进行攻击,如果服务器成功计算出了k,则选手失败并中断连接,否则选手拿到FLAG

那么接下来我们要分析的问题就是一条anomalous曲线在什么情况下会使得题目中给出的Smart’s attack的实现失效,查阅论文资料可以发现,Smart’s attack的思路是通过将F_p上的曲线提升到Q_p上来实现对ECDLP的化简计算的:

但是当提升后的Q_p上的曲线同F_p上的曲线同构(即出现canonical lift的情况)时,在(1)式(计算k的最终表达式)中的分子和分母均为0,此时我们无法再正确计算出k的值:

那么我们的问题就变成了如何生成一条anomalous曲线使得它到Q_p的trivial lift就是canonical lift,根据该篇论文我们可以看到,一个较为简单的方案就是直接选择d = 3, D = 3的情况(此时j不变量的值等于0),此时素数p应满足的表达式形如:

本题中的阈值预期p的值在220到225比特之间,因此我们可以在[2^113, 2^114]区间内穷举v的值(保证生成的p的值大于最大值),对于每一个v计算出一个p的值,同时我们计算出曲线的参数ab的值为(参见3.2节):

由于j不变量的值等于0因此a的值直接为0,同时由于d % 8 == 3因此s的值为1,然后对于得到的每一组(p, a, b),生成椭圆曲线并检查曲线的阶是否等于素数p,若等于则向服务器提交该组(p, a, b),然后接收服务器返回的点G,生成一个随机数k并提交点G * k即可得到FLAG

p.s.

实际上从论文中我们也可以看到,canonical lift出现的情况的概率约为1/p,我们本题之所以能够很快找到一种办法使得Smart’s attack失效,是因为本题中Smart’s attack的SageMath实现是有缺陷的(可以参见crypto.stackexchange中的这一问题),当我们实现Smart’s attack时,如果我们恰好落入了canonical lift的情况,只需要对lift随机化即可,即一个更为有效的Smart’s attack应该是将本题中的这行代码:

Eqp = EllipticCurve(Qp(p, 8), [ZZ(t) for t in E.a_invariants()])

修改为:

Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

这样一来在很大程度上即可避免出现Smart’s attack攻击失败的这种情况。

解题脚本

#!/usr/bin/env sage

from pwn import *

'''
BITS = 113

def p_gen(BITS):
    for i in range(2**BITS, 2**(BITS + 1)):
        koeff = 1 + 3 * i * i
        if koeff % 4 != 0:
            continue
        p = koeff // 4
        if not is_prime(p):
            continue
        j_invar = 0
        a = 0
        b = (54 * 3 * pow(3 * 12**3, inverse_mod(2, p), p)) % p
        E = EllipticCurve(GF(p), [a, b])
        if p == E.order():
            return (a, b, p)
'''

a = 0
b = 839808
p = 80879840001451919384001045261062739512883607574894458541090782884541
E = EllipticCurve(GF(p), [a, b])

io = remote("notbefoooled.challenges.ooo", 5000)

io.sendlineafter("a = ", str(a))
io.sendlineafter("b = ", str(b))
io.sendlineafter("p = ", str(p))

_ = io.recvuntil(b"generator: (")
tmp = io.recvline().strip().replace(b')', b'').split(b", ")
G = E(int(tmp[0]), int(tmp[1]))

k = randrange(1, p)
P = k * G

io.sendlineafter("x = ", str(P[0]))
io.sendlineafter("y = ", str(P[1]))

io.recv()

# OOO{be_Smarter_like_you_just_did}

 

ooo-flag-sharing

题目描述

Share flags safely with the latest OOO service!
ooo-flag-sharing.challenges.ooo 5000

135/500 pts, 36 solves

附件

解题思路

本题自定义了一个(5,100)门限的密钥共享协议,share的计算方式如下:

矩阵S中的100个元素代表100个share,矩阵X的第一个元素代表secret,其余4个元素代表区间[0, P]上的4个随机数(即计算时会将secret填充为一个5 X 1的矩阵),而矩阵MP的值则分别来自prime.ooomatrix.ooo这两个文件,其中prime.ooo文件存储的是一个256比特的安全素数,matrix.ooo文件存储的是一个100*5的随机矩阵,矩阵中每一个元素的值均为正整数且不超过1000。程序在首次启动时会对这两个文件进行初始化,由于程序每次会首先检查同目录下是否存在这两个文件,如果存在则直接读取已有文件而不再重新创建,因此本题中这两个文件中存储的内容对选手来讲恒定不变。

而已知任意5个share,我们即可根据下式恢复出矩阵X

其中矩阵X的第一个元素即为secret,从而实现对secret的恢复。这里可以注意到,(1)式没有在模P下进行计算,而(2)式是在模P下进行计算的,这一漏洞为我们后面的攻击提供了可能,我们可以先记下这一漏洞。

接下来我们来看一下题目的流程,用户每次连接到服务器时,服务器会要求选手输入一个用户名,若不为程序设置的几个保留用户名,则会在同目录下创建一个shares/用户名目录,下次连接时如果还输入相同用户名则不再重复创建。接下来程序向选手提供了四个功能:

  • 功能1

选手可以提供一个secret,然后程序将secret的16进制形式的md5哈希值的前6个字符作为secret_id,选手可以设置将其分享给num个人(num>=5),程序会根据secret的值生成numshare,然后将其随机置换,置换后的第一个share的值会保存在服务器上的该用户文件夹下的secret_id.1文件中,其余的share会打印给选手。

  • 功能2

选手可以提供一个secret_id,再提供若干个share,服务器会使用该secret_id对应的一个share和选手提供的share来尝试恢复出secret,并将恢复出的内容打印给选手。

  • 功能3

服务器将FLAG作为secret来生成5个share,然后将其随机置换,置换后的第一个share的值会保存在服务器上的该用户文件夹下的secret_id.1文件中,第二个share的值会保存在服务器上的该用户文件夹下的secret_id.2文件中,其余的3个share会打印给选手。同时程序随机生成一个3字节的字节串,将其16进制形式的字符串来作为secret_id

  • 功能4

选手可以提供一个secret_id,再提供若干个share,服务器会使用该secret_id对应的两个share和选手提供的share来尝试恢复出secret,若恢复出的内容以b"OOO{"开头,则会打印给选手恢复成功的提示。

接下来我们分析一下如何借助这些功能拿到FLAG,我们先来看一下预期解,首先我们执行一次功能3,拿到一个secret_id和3个share,设此时FLAG表示为:

其中s_as_e为关于FLAG的5个sharem_am_e5 X 5矩阵M在模P下的逆矩阵中同s_as_e对应的5个值,假设这里s_as_b为服务器存储到secret_id.1secret_id.2文件中的两个shares_cs_ds_e为打印给选手的三个share,注意到在本题中,整数和字节串之间的转换是采用小端模式,此时功能4中检查字节串形式的FLAG是否以b"OOO{"开头即等价于检查整数形式的FLAG的低32位是否为:

01111011010011110100111101001111

那么假设选手将s_e的值修改为s_e + inverse(m_e, P) * (x << 32),此时根据(3)式,程序恢复出的结果将变为(FLAG + x << 32) % P,由于该操作是在模P下进行的,因此此时我们就可以将程序中的功能4看成一个ORACLE,然后在区间[0, P >> 32]上用二分搜索即可求出FLAG的值,即当(FLAG + x << 32) >= P的时候,此时恢复出的内容将不再以b"OOO{"开头;当(FLAG + x << 32) < P的时候,此时恢复出的内容仍以b"OOO{"开头,我们可以通过这种方法找到一个最小的x,使得(FLAG + x << 32) >= P成立,此时P - (x << 32)的值转换为字节串y后,b"OOO{" + y[4:]即为字节串形式的FLAG,从而我们恢复出了FLAG的内容。

那么要想按照这种利用ORACLE + 二分搜索的方法恢复出FLAG,首先我们需要先从服务器上泄漏出素数P的值,我们可以先利用两次功能1,提交两个其整数形式的值大于P的不同的字节串作为secret,设其对应的整数形式的值分别input_ainput_b,然后将得到的share分别提交到功能2,设恢复出的内容为secret_asecret_b,则有:

将同余式转化为等式,有:

因此我们利用最大公约数恢复出P

恢复出P以后,我们还需要恢复出m_e的值,我们可以令s_as_d的值均为0,令s_e的值为1,然后向功能2提交s_as_e这5个share,此时功能2恢复出来的即为m_e的值,但是由于s_as_b存入了文件,因此这里的下标ab的值我们是未知的,但是鉴于ab的取值范围为[1, 99](本题中split_secret返回的是shares[1:],因此下标值不会出现等于0的情况),因此我们可以遍历ab的值,然后对于计算出的每一个m_e的值,我们将将s_e的值修改为s_e + inverse(m_e, P) * (1 << 32),然后向功能4提交s_cs_ds_e + inverse(m_e, P) * (1 << 32)进行测试,若功能4显示提示恢复成功,则可以认为此时的m_e恢复正确,此时所有需要的未知量我们都已确定,我们再使用上面提到的ORACLE + 二分搜索的方法恢复出FLAG即可。

接下来我们看一下非预期解,本题的非预期解可以直接在不使用功能4的情况下恢复出FLAG,首先我们需要恢复出矩阵M(即matrix.ooo文件中的内容),观察(1)式,假设我们使用多次(大于5次即可)功能1拿到若干组share,若我们将这些share组合成一个新的矩阵S,根据(1)式,对于新的矩阵S的转置中的每一个行向量,都可以由矩阵M的转置中的所有行向量的线性组合来表示,鉴于矩阵M中元素的值远远小于矩阵X和矩阵S中的元素的值,因此我们可以通过对矩阵S使用LLL算法进行格基规约,然后对规约后的矩阵的行向量之间的线性组合进行遍历,每得到一个所有元素的值均在区间[0, 1000)的行向量,即为矩阵M中的一个列向量,但是得到这些列向量之后我们无法确认这些列向量之间的排列顺序,因此可以尝试对其排列组合进行穷举,同时,由于本题中split_secret返回的是shares[1:],因此我们这种情况下无法准确恢复出矩阵M中的第一行,不过已经足够本题中恢复FLAG,鉴于X矩阵中的元素均小于P,我们可以收集足够数量的关于FLAGshare,然后通过使用LLL算法进行格基规约来解方程求出FLAG即可,相关实现可参考这里

解题脚本

#!/usr/bin/env python3

from pwn import *
from math import gcd
from Crypto.Util.number import *

def fun_1(io, secret, num):
    io.sendlineafter('Choice: ', '1')
    io.sendlineafter('Enter secret to share: ', secret)
    _ = io.recvuntil("Your secret's ID is: ")
    secret_id = io.recvline().strip()
    io.sendlineafter('Number of shares to make: ', str(num))
    _ = io.recvuntil('Your shares are: ')
    shares = eval(io.recvline().strip())
    return secret_id, shares

def fun_2(io, secret_id, shares):
    io.sendlineafter('Choice: ', '2')
    io.sendlineafter("Enter the secret's ID: ", secret_id)
    io.sendlineafter('Enter your shares of the secret: ', str(shares))
    _ = io.recvuntil('Your secret is: ')
    secret = io.recvline().strip()
    secret = eval(secret)
    return secret

def fun_3(io):
    io.sendlineafter('Choice: ', '3')
    io.recvuntil("Our secret's ID is: ")
    secret_id = io.recvline().strip()
    io.recvuntil("Your shares are: ")
    shares = eval(io.recvline().strip())
    return secret_id, shares

def fun_4(io, secret_id, shares):
    io.sendlineafter('Choice: ', '4')
    io.sendlineafter("Enter the secret's ID: ", secret_id)
    io.sendlineafter("Enter your shares of the secret: ", str(shares))
    res = io.recvline()
    return res.startswith(b"Congrats!")

def recover_P(io):
    input_a = b'~' * 40
    input_b = b'~' * 41
    secret_id, shares = fun_1(io, input_a, 5)
    secret_a = fun_2(io, secret_id, shares)
    secret_id, shares = fun_1(io, input_b, 5)
    secret_b = fun_2(io, secret_id, shares)
    kp = int.from_bytes(input_a, 'big') - int.from_bytes(secret_a, 'little')
    gp = int.from_bytes(input_b, 'big') - int.from_bytes(secret_b, 'little')
    P = gcd(kp, gp)
    if not isPrime(P):
        for i in range(2, 100, 2):
            if isPrime(P // i):
                P = P // i
                break
    return P

def recover_m_e(io, secret_id, shares, P):
    known_idx = [share[0] for share in shares]
    for a in range(1, 100):
        for b in range(a + 1, 100):
            if (a in known_idx) or (b in known_idx):
                continue
            m_e = int.from_bytes(fun_2(io, secret_id, [(a, 0), (b, 0), (known_idx[0], 0), (known_idx[1], 0), (known_idx[2], 1)]), 'little')
            token = fun_4(io, secret_id, shares[:-1] + [(shares[2][0], (shares[2][1] + (1 << 32) * inverse(m_e, P)) % P)])
            if token:
                return m_e

def binary_search_x(io, secret_id, shares, P, m_e):
    low = 0
    high = P >> 32
    while low <= high:
        x = (low + high) // 2
        token = fun_4(io, secret_id, shares[:-1] + [(shares[2][0], (shares[2][1] + (x << 32) * inverse(m_e, P)) % P)])
        if token:
            low = x + 1
        else:
            high = x - 1
    return x

if __name__ == "__main__":
    io = remote("ooo-flag-sharing.challenges.ooo", 5000)
    io.sendlineafter("Username: ", "roadicing")
    secret_id, shares = fun_3(io)
    P = recover_P(io)
    m_e = recover_m_e(io, secret_id, shares, P)
    x = binary_search_x(io, secret_id, shares, P, m_e)
    FLAG = b"OOO{" + (P - (x << 32)).to_bytes(32, 'little')[4:]
    print(FLAG)

# OOO{ooo_c4nt_ke3p_secr3ts!}

 

参考资料

[1] https://www.tandfonline.com/doi/abs/10.1080/00207160212708?journalCode=gcom20
[2] https://github.com/ubuntor/coppersmith-algorithm
[3] https://wstein.org/edu/2010/414/projects/novotney.pdf
[4] https://link.springer.com/content/pdf/10.1007/s001459900052.pdf
[5] http://www.monnerat.info/publications/anomalous.pdf
[6] https://csrc.nist.gov/csrc/media/events/workshop-on-elliptic-curve-cryptography-standards/documents/papers/session1-miele-paper.pdf
[7] https://crypto.stackexchange.com/questions/70454/why-smarts-attack-doesnt-work-on-this-ecdlp
[8] https://gist.github.com/nomeaning777/8c8cc446fdf1e7a151ae30d72600c312

分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多