糖醋小鸡块的blog
0%

2024-ByteCTF-wp-crypto

发表于 更新于 分类于 Valine：

XD

magic_lfsr

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from Crypto.Cipher import AES
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from hashlib import sha512
from secret import flag

mask1 = 211151158277430590850506190902325379931
mask2 = 314024231732616562506949148198103849397
mask3 = 175840838278158851471916948124781906887
mask4 = 270726596087586267913580004170375666103


def lfsr(R, mask):
    R_bin = [int(b) for b in bin(R)[2:].zfill(128)]
    mask_bin = [int(b) for b in bin(mask)[2:].zfill(128)]
    s = sum([R_bin[i] * mask_bin[i] for i in range(128)]) & 1
    R_bin = [s] + R_bin[:-1]
    return (int("".join(map(str, R_bin)), 2), s)


def ff(x0, x1, x2, x3):
    return (int(sha512(long_to_bytes(x0 * x2 + x0 + x1**4 + x3**5 + x0 * x1 * x2 * x3 + (x1 * x3) ** 4)).hexdigest(), 16) & 1)


def round(R, R1_mask, R2_mask, R3_mask, R4_mask):
    out = 0
    R1_NEW, _ = lfsr(R, R1_mask)
    R2_NEW, _ = lfsr(R, R2_mask)
    R3_NEW, _ = lfsr(R, R3_mask)
    R4_NEW, _ = lfsr(R, R4_mask)
    for _ in range(270):
        R1_NEW, x1 = lfsr(R1_NEW, R1_mask)
        R2_NEW, x2 = lfsr(R2_NEW, R2_mask)
        R3_NEW, x3 = lfsr(R3_NEW, R3_mask)
        R4_NEW, x4 = lfsr(R4_NEW, R4_mask)
        out = (out << 1) + ff(x1, x2, x3, x4)
    return out


key = getRandomNBitInteger(128)
out = round(key, mask1, mask2, mask3, mask4)
cipher = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)
print(f"out = {out}")
print(f"enc = {cipher.encrypt(pad(flag, 16))}")
# out = 1024311481407054984168503188572082106228007820628496173132204098971130766468510095
# enc = b'\r\x9du\xa15q\xd2\x81\x0b\xceq2\x8d)*\xe9\xf0;a\xad\xbe?\xa2\xb2\x1f\x88O\x8c\xa2[\xcb\x9a\xa9\x8d\xac\x0b\x85\xb4j@]\x0e}EF{\xb1\x91'

题目基于LFSR，随机生成128bit的key作为初始state，并用相同的key和四个不同的mask共同初始化四个不同的lfsr，之后给出270组combine过的lfsr，要求还原key来解AES，其中combine过程是这样的：

1
2
def ff(x0, x1, x2, x3):
    return (int(sha512(long_to_bytes(x0 * x2 + x0 + x1**4 + x3**5 + x0 * x1 * x2 * x3 + (x1 * x3) ** 4)).hexdigest(), 16) & 1)

这种combine的LFSR肯定首先需要测一下相关性，测试发现输出和四个lfsr的相关性分别是：

1
2
3
4
7/16
9/16
7/16
9/16

既然有相关性，比较自然的会想到correlation attack，然而由于key有128bit，所以直接用correlation attack需要爆2^128，显然不太可能，所以要用也得用fast correlation attack可能才行。

这个时候觉得完了，因为fast correlation attack我真的还没有学会，也从来没有真正意义上的自己调用过，所以想着多半是打不出了。

然而细看一下发现了一个盲点：给出的数据只有270组，怎么想调fast correlation attack估计都是不够用的，所以应该是其他方法。这个时候想到了前不久HitconCTF学到的一个零化子的思路，可以参考：

HITCON CTF 2024 Qual Crypto Writeup - Tanglee’s Blog

首先用sage求整个combine过程的真值表，并转化为一个简单一些的布尔函数看看形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
from sage.crypto.boolean_function import BooleanFunction
from Crypto.Util.number import *
from itertools import *
from hashlib import sha512

F = []
for i in product([0,1],repeat=4):
    x0,x1,x2,x3 = i
    bit = (int(sha512(long_to_bytes(x0 * x2 + x0 + x1**4 + x3**5 + x0 * x1 * x2 * x3 + (x1 * x3) ** 4)).hexdigest(), 16) & 1)
    F.append(bit)

f = BooleanFunction(F).algebraic_normal_form()
print(f)
1
x0*x1*x2*x3 + x0*x1*x3 + x0 + x1*x2*x3 + x1*x3 + x2 + x3

如果我们能找到另一个布尔函数g使得下式恒成立：

称这样的g为annihilator，那么我们就可以得到一个事实：当f为1的时候g一定为0。而这样的g可以用如下的方式找到：

1
2
g = BooleanFunction(F).algebraic_immunity(annihilator = True)
print(g)
1
(1, x0 + x2 + x3 + 1)

其中第二个返回值就是g，第一个返回值是g的degree。既然g的degree是1，这也就是说对于output中为1的地方，我们都可以拥有一个不含x1的线性等式是：

实际上测出来上面的多项式似乎应该反过来才对，也就是：

而由于四个LFSR的每个状态其实都是初始key的线性组合，比如对于LFSR1，其迭代过程可以写成一个线性等式：

那么记初始状态R和递推矩阵Li如下：

那假如output的第i个bit是1的话，其实就代表着如下线性等式成立：

下标0指得到向量的第一个值

因此output每有一个bit，我们就可以搜集到关于初始状态R的128个bit的线性等式。而实际上output共有127个bit，所以可以搜集到127组等式，虽然还是不满秩，但是小爆一下kernel就可以找到key了。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from sage.crypto.boolean_function import BooleanFunction
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha512
from itertools import *

################################################################################### part1 find annihilator g
if(0):
    F = []
    for i in product([0,1],repeat=4):
        x0,x1,x2,x3 = i
        bit = (int(sha512(long_to_bytes(x0 * x2 + x0 + x1**4 + x3**5 + x0 * x1 * x2 * x3 + (x1 * x3) ** 4)).hexdigest(), 16) & 1)
        F.append(bit)

    f = BooleanFunction(F).algebraic_normal_form()
    print(f)
    g = BooleanFunction(F).algebraic_immunity(annihilator = True)
    print(g)
    #we have:
    #if(ff(x0, x1, x2, x3) == 1):
    #    assert (x0 + x1 + x3 + 1) & 1 == 0
    #that is: x0 + x1 + x3 == 1


################################################################################### part2 convert lfsr to matrix
def LFSR_to_MAT(mask):
    temp = bin(mask)[2:].zfill(128)
    MAT = Matrix(Zmod(2), 128, 128)
    for i in range(127):
        MAT[i+1,i] = 1
    for i in range(128):
        MAT[0,i] = int(temp[i])
    return MAT
mask1 = 211151158277430590850506190902325379931
mask2 = 314024231732616562506949148198103849397
mask3 = 175840838278158851471916948124781906887
mask4 = 270726596087586267913580004170375666103
LFSR1, LFSR2, LFSR3, LFSR4 = LFSR_to_MAT(mask1), LFSR_to_MAT(mask2), LFSR_to_MAT(mask3), LFSR_to_MAT(mask4)


################################################################################### part3 solve linear equation
out = 1024311481407054984168503188572082106228007820628496173132204098971130766468510095
enc = b'\r\x9du\xa15q\xd2\x81\x0b\xceq2\x8d)*\xe9\xf0;a\xad\xbe?\xa2\xb2\x1f\x88O\x8c\xa2[\xcb\x9a\xa9\x8d\xac\x0b\x85\xb4j@]\x0e}EF{\xb1\x91'
out = bin(out)[2:].zfill(270)

L = []
for i in range(len(out)):
    if(out[i] == "1"):
        L.append((LFSR1^(i+2) + LFSR2^(i+2) + LFSR4^(i+2))[0])
L = Matrix(Zmod(2), L)
M = L.solve_right(vector(Zmod(2), [1 for i in range(out.count("1"))]))

key = M + L.right_kernel().basis()[0]
key = int("".join(map(str,key)),2)
cipher = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)
flag = cipher.decrypt(enc)
print(flag)


#ByteCTF{8a58eccb-a3b0-4064-bd26-15d475ebe2d1}



*decipher Diffie-Hellman

题目描述：

1
程序加密过程中忘记了键盘输入的内容，请根据已知的信息破译出flag

hint：

1
有限空间爆破

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Util.Padding import pad
from libnum import s2n

flag = r"ByteCTF{******}"
g = 5
p = getPrime(512)
a = random.randrange(2, p - 1)
A = pow(g, a, p)

al = getPrime(512)
m = getPrime(512)
s = getPrime(512)

outputs = []
for i in range(10):
    s = (al * s + p) % m
    outputs.append(s)

key_int = int(input("Input my public key?\n"))

while not 1 < key_int < (p - 1):
    key_int = int(input("Input correct format public key again between 2 to p-1\n"))
dh_key = pow(key_int, a, p)
key = hashlib.md5(long_to_bytes(dh_key)).digest()
cipher = AES.new(key, AES.MODE_ECB)
enc = cipher.encrypt(pad(flag.encode(), 16))
print("al = ", al)
print("m = ", m)
print("ouputs[4] = ", outputs[4])
print("ouputs[5] = ", outputs[5])
print(f'encrypted flag: {s2n(enc)}')
"""
al =  6987418709836280122539809582453286069061059342934250273196952239100173470340380619195424571025033102643293098735246498899499230393741046775729762352856927
m =  12710688490958956530748900564817776351569320915377221868023985388799130768128470437062609956810086256451091702161476567347660442541036645863742363823898071
ouputs[4] =  2728757049131678605235016854422985829565908585923048338298110282069173390888632945247368807787912947016658675182897909709569230885213734719022623969520979
ouputs[5] =  3753895881656195471988191329401971327506920732845692422476480236229772053653896503280676494663976886598118940522017209044648665134625067341824484655112146
encrypted flag: 4421203891267550791983036920779652137711362976404304304369030116210000459547739643046609216016679658345753605804218976790719901924890550963123070032471900
"""

image-20240921232506724