前言

这次比赛的密码题还是很好玩的,虽然我太菜了做不出来,但是我还是要复现学习一下,希望以后能做出密码题来吧。


babyrsa

附件地址:附件

题目给了三个文件,除了加密后的flag之外还有两个用于加密的脚本,观察脚本,可以发现题目跟一般的RSA有所不同,使用的是有限域上多项式形式的RSA,详情可以看这个PDF:附件 ,加密和解密流程都写在PDF中了,只要理解一下这道题就很好就解了。因为本地没有安装sage的缘故,所以我是用在线工具来解题:https://sagecell.sagemath.org/

payload:

P=PolynomialRing(GF(2),'x')
e = 31337
n = P('略')
R.<a> = GF(2^2049)
c = 十进制密文略
c = P(R.fetch_int(c))
p, q = list(factor(n))
#print p 821
#print q 1227
phi = 2 ** 2048 * (1 - 1 / 2 ** 821) * (1 - 1 / 2 ** 1227)
d = inverse_mod(e, phi)
m = pow(c, d, n)
m = R(m).integer_representation()
print hex(m)[2:-1].decode('hex')

运行getflag。


zer0lfsr

附件地址:附件

writeup:https://github.com/p4-team/ctf/tree/master/2019-03-23-0ctf-quals/crypto_lfsr

题目给了两个文件,分别是加密后的flag和加密脚本。首先分析一下脚本,脚本定义了三个48位未知字符串,而flag就是这三个字符串拼接起来再sha256一下,所以我们解题的关键就是获取这三个字符串。接下来我们看看加密方法,可以看到密文的每一位都是一次加密后的结果,而加密的过程则是对三个字符串进行异或和与等操作,最后还会生成新的一位添加在字符串的后面。

比赛的时候看到这题目,唯一的感想就是:好多可能性啊!这可咋整呀?

后来知道了z3约束求解器的存在,这题目就好办了,writeup脚本如下:

# -*- coding:utf8 -*-
from libnum import n2s
from z3 import *
import hashlib


def combine(x1, x2, x3):
    return (x1 * x2) ^ (x2 * x3) ^ (x1 * x3)


def solve_3_lfsr(keystream, relevant_bit_indices, length, mask_length):
    len_mask = (2 ** (mask_length + 1) - 1)
    result_bits = map(long, "".join([bin(ord(c))[2:].zfill(8) for c in keystream]))
    s = Solver()
    x = BitVec('x', length)  # z3中只有BitVec类型支持异或操作
    y = BitVec('y', length)  # BitVec表示无符号数
    z = BitVec('z', length)
    inits = [x, y, z]
    for result in result_bits:
        combs = []
        new_inits = []
        for index in range(3):  # 无符号数的移位需要使用LShR,表示逻辑移位
            relevant_bit1 = (inits[index] & (1 << relevant_bit_indices[index][0]))
            bit1_value = LShR(relevant_bit1, relevant_bit_indices[index][0])
            relevant_bit2 = inits[index] & (1 << relevant_bit_indices[index][1])
            bit2_value = LShR(relevant_bit2, relevant_bit_indices[index][1])
            single_lfsr_result = bit1_value ^ bit2_value
            combs.append(single_lfsr_result)
            new_init = ((inits[index] << 1) & len_mask) ^ single_lfsr_result
            new_inits.append(new_init)
        s.add(combine(combs[0], combs[1], combs[2]) == result)  # 约束条件
        inits = new_inits
    s.check()
    model = s.model()
    x_res = int(str(model[x]))
    y_res = int(str(model[y]))
    z_res = int(str(model[z]))
    return x_res, y_res, z_res


with codecs.open("C:/Users/19807/Desktop/release/keystream", 'rb', 'utf8') as input_file:
    data = input_file.read()
    mask1 = (47, 22)
    mask2 = (47, 13)
    mask3 = (47, 41)
    x, y, z = solve_3_lfsr(data[:24], [mask1, mask2, mask3], 48, 48)
    init1, init2, init3 = map(n2s, [x, y, z])
    print "flag{" + hashlib.sha256(init1 + init2 + init3).hexdigest() + "}"

基本把加密流程写一遍然后约束求解即可,运行getflag。


zer0des

附件:附件

没找到writeup,日后再复现。


zer0mi

附件:附件

太菜了…基础太差了,writeup和论文都看不透,日后变强了再回来复现吧…

论文:http://www.docin.com/p-986595706.html

writeup:https://github.com/miszcz2137/ctf-writeups/blob/master/0ctf2019/zer0mi/write-up.md


babysponge

地址:附件

writeup:https://github.com/wonrzrzeczny/CTF-writeups/blob/master/0ctf%202019/babysponge/readme.md https://github.com/p4-team/ctf/tree/master/2019-03-23-0ctf-quals/crypto_keccak

题目给了两个文件,一个是加密文件,另一个则是简单的服务器的代码,我们稍微看一下代码,可以看到getflag的条件其实就只有一个:找到两个哈希加密后结果相同的不同字符串。

简单看一下加密方法,可以看到使用的是海绵函数:

https://zh.wikipedia.org/wiki/%E6%B5%B7%E7%B6%BF%E5%87%BD%E6%95%B8 需要梯子

https://en.wikipedia.org/wiki/Sponge_function 没有梯子就用谷歌翻译看英文版吧

在源代码中还给了一些其他哈希算法的调用,我们对比一下可以发现,题目所使用的capacity只有48位,比起其他算法来说太小了,这里就是出题人留下的一个hint,我们思考一下题目的加密过程:

  1. 生成长度为200的state,然后开始Absorb步骤。
  2. 如果剩下的明文长度>=rate,则将其与state的前rate异或,然后将整个state进行KeccakF1600加密。
  3. 如果剩下的明文长度<rate,则进入第二个步骤padding。
  4. 最后进入Squeeze步骤输出结果。

在加密的过程中,有capacity长度的state是不参与异或的,而异或的结果则很好控制,所以我们可以考虑这么一种攻击方式:寻找两个长度为rate的msg,他们在进行第一步骤的加密后,后capacity位的结果相同。然后我们对其中一个msg填充长度为rate的空字节,这样它进行循环进行第二次第一步骤加密的时候,前rate位的异或结果就不会发生改变。与此同时,我们将另一个msg的前rate位与这个msg的前rate位进行异或,然后将它们填充到另一个msg后面。这样一来,我们就可以保证他们在第二次第一步骤加密的时候,前rate位的异或结果是相同的,也就能保证他们的最终结果相同了。

因为capacity较小的缘故,所以这种爆破方式是可行的。

参考writeup中的脚本,爆破上一段时间即可getflag。


Orz


Crypto CTF

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!

Gopher-HTTP2
0CTF/TCTF2019 Web题解