洗衣机unb和end交替出现(洗衣机end和unb交替闪怎么解决)

洗衣机unb和end交替出现(洗衣机end和unb交替闪怎么解决)

首页家电维修洗衣机更新时间:2021-12-16 21:45:22

前言

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进制串的长度为l,x是区间[ 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定理生成素数p和q(p不等于q)。

sub_14D8函数部分代码:

即有:

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

sub_165E函数部分代码:

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

sub_1B3E函数部分代码:

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

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

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

此时有:

观察(1)式中的x,x是区间[ 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_0和k_1都是区间[0, r 1)上的随机数,因此一定有k_0 k_1 < 2 * r,此时有:

联立(5)式和(9)式,即可求出k_0和k_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----- ") _ = 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:

然后我们来看一下预期解,服务器首先要求选手提供一条椭圆曲线的a、b和p这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的值,同时我们计算出曲线的参数a和b的值为(参见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的矩阵),而矩阵M和P的值则分别来自prime.ooo和matrix.ooo这两个文件,其中prime.ooo文件存储的是一个256比特的安全素数,matrix.ooo文件存储的是一个100*5的随机矩阵,矩阵中每一个元素的值均为正整数且不超过1000。程序在首次启动时会对这两个文件进行初始化,由于程序每次会首先检查同目录下是否存在这两个文件,如果存在则直接读取已有文件而不再重新创建,因此本题中这两个文件中存储的内容对选手来讲恒定不变。

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

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

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

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

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

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

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

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

其中s_a到s_e为关于FLAG的5个share,m_a到m_e为5 X 5矩阵M在模P下的逆矩阵中同s_a到s_e对应的5个值,假设这里s_a和s_b为服务器存储到secret_id.1和secret_id.2文件中的两个share,s_c、s_d和s_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_a和input_b,然后将得到的share分别提交到功能2,设恢复出的内容为secret_a和secret_b,则有:

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

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

恢复出P以后,我们还需要恢复出m_e的值,我们可以令s_a到s_d的值均为0,令s_e的值为1,然后向功能2提交s_a到s_e这5个share,此时功能2恢复出来的即为m_e的值,但是由于s_a和s_b存入了文件,因此这里的下标a和b的值我们是未知的,但是鉴于a和b的取值范围为[1, 99](本题中split_secret返回的是shares[1:],因此下标值不会出现等于0的情况),因此我们可以遍历a和b的值,然后对于计算出的每一个m_e的值,我们将将s_e的值修改为s_e inverse(m_e, P) * (1 << 32),然后向功能4提交s_c、s_d和s_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,我们可以收集足够数量的关于FLAG的share,然后通过使用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

,

大家还看了
也许喜欢
更多栏目

© 2021 3dmxku.com,All Rights Reserved.