糖醋小鸡块的blog
0%

Crypto趣题-流密码

发表于 更新于 分类于 Valine：

该文章主要记录一些流密码相关的趣题。

Non-neutrality

题目来源：SEETF 2023

题目描述：

1
My neutral OTPs got destroyed last year; all that’s left are the non-neutral ones.

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from secrets import randbits
from Crypto.Util.number import bytes_to_long
import os

flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}').encode()

# get a one-time-pad in which not exactly half the bits are set
def get_xorpad(bitlength):
    xorpad = randbits(bitlength)
    return xorpad if bin(xorpad).count('1') != bitlength // 2 else get_xorpad(bitlength)

def leak_encrypted_flag():
    return bytes_to_long(flag) ^ get_xorpad(len(flag) * 8)

# I managed to leak the encrypted flag a lot of times
if __name__ == '__main__':
    for _ in range(2**16):
        print(leak_encrypted_flag())

参考

很简短的题目，但是解法真的相当有趣。这篇wp主要参考：

（我不懂）密码学系列之异或运算 | Van1sh的小屋 (jayxv.github.io)

Author’s write-up for Non-neutrality - HedgeDoc

接下来进入到题目。

题目内容

题目基于MTP，他给出2^16组密文，每组密文都是如下形式：

其中ti是随机比特串，并且有一个特点是0、1的数量一定不相等。

到这里题目就描述完了，就是这么简短，并且这题其实和流密码没什么关系，就当是把产生很多异或串的过程想象成流吧。

接下来进入解题环节。

简单分析

首先，从给出的密文可以判断出flag是34字节，算上前面的填充一共是272比特，这就说明ti他0、1的数量一定不是136；同时，由于题目拿flag的语句可以知道flag就是SEE{}包裹的可见字符串。那么整理一下现在拥有的信息就是：

  • t任意一个ti，其0、1的数量一定不是136
  • flag有69个比特位已知(SEE{}就有40个比特，剩下的29个字符都是可见字符，因此MSB都是0，总共就是69个已知比特)

然后就没有思路了，找到wp过后仔细学习了一下思路，发现真的很厉害，接下来就是对这个思路的详细阐述。

详细题解

首先要定义一个量，叫做汉明重量(hamming weight)，他的含义其实就是一个比特串中1的个数。那么对于任意一个ti，如果他完全是随机的，那么可以想见他汉明重量是奇数或者是偶数的概率就是五五开。然而，题目对ti加了一个1的数量不为136的限制，这样做的结果是对这种平衡产生了破坏——因为他显然降低了汉明重量是偶数的概率。

那么我们具体量化一下这个过程，看一下ti被限制之后，其汉明重量是奇数和是偶数的概率又分别是多少。而这个计算过程很简单，我们只需要算一下1恰为136时在所有情况里的占比，然后从偶数原本的50%减去这个占比即可。

而这个占比的计算方式就是：

所以ti汉明重量为偶数和为奇数的概率之比就是：

同时，通过统计所有密文的汉明重量的奇偶性，我们就可以得到密文汉明重量为偶与汉明重量为奇的比例也是9:10。而这其实又揭露了一个信息：flag的汉明重量是偶数。

这是因为两个串异或可以看作是两个串在模2下做加法，而因为密文的汉明重量比值与ti的期望相等，所以说ti与flag异或并没有改变其汉明重量的奇偶性，因此flag的汉明重量是偶数

而最关键的一步就是如何继续利用ti中1的数量一定不是136这一个事实。

首先可以确定一点：汉明重量为奇数的密文都没有用，仅仅是冗余而已。这是因为如果密文汉明重量为奇数，结合刚才判断过的flag汉明重量为偶数的这个事实，那么ti的汉明重量就是奇数，而汉明重量为奇数的ti可以看作是没有加任何限制的，所以没什么可以作为判断依据的东西，自然就舍弃掉了。

那么现在剩下来的就是所有汉明重量为偶数的密文，这代表着他们对应的ti的汉明重量也是偶数。

而由于限制了ti中1的数量一定不是136，要利用这一点，就必须找出这个限制和每一比特取0或取1的概率之间的关系。为此需要定义一个函数f(x,k)，其含义是：

  • 汉明重量奇偶性与k相同，但是不等于k的所有长为x的比特串数量

而他的计算公式也就直接由他的定义得来：

这是因为长为x的比特串共有$2^x$个，奇偶性与k相同的就是$2^{x-1}$个，再减去恰好为k个的就是所求了。

然后很神奇的一点就来了，对于ti的每一位，其为0和为1的概率之比恰好可以用这个函数写成：

这里有一点比较好理解，就是$f(x,k) = f(x-1,k) + f(x-1,k-1)$，这是因为用组合数的递推公式展开一下就好了

另一点稍微难理解一点，那就是为什么这两个数字恰好代表0和1的概率之比？其实仔细想想就明白，因为对于所有满足上面条件的长为x的串，我们可以固定其一位是0或者1，这就把长为x的串又划分成了两种串。而如果固定该bit为0，那么对其汉明重量奇偶性没有影响，依然是k；而如果固定为1，对其汉明重量就产生了影响，剩下的串的汉明重量就应该与k-1相等，且不能恰好等于k-1

这个说法一方面又证明了一遍$f(x,k) = f(x-1,k) + f(x-1,k-1)$这个结论，同时也说明了为什么这两个数字恰好代表0和1的概率之比。因为可以理解为：在这一位取0，有f(x-1,k)个串；而取1则有f(x-1,k-1)个串。并且任意位之间其实是没有差别的，所以这两个数值的比就正好等于每一位取0和1的概率之比

理解到上面这段内容后，解题思路就很清晰了。对于每一个密文，我们将他与我们已知的部分flag比特进行异或的预处理，得到该组密文的x和k值，就能计算出该组密文对应ti的每一比特取0和取1的概率。有了这个概率后，我们检查当前还不清楚是0还是1的每一个flag的比特位，比如当密文该位置比特为1时，flag的该比特取0的概率，就是ti该比特取1的概率，也就是f(x-1,k-1)。然后我们反复进行这个过程，并将flag该比特对应的0和1的概率比进行累乘，当处理完全部密文后，就有了所有未知比特的概率比了。我们挑选其中概率差距最大的(也就是为0或为1的相应概率最高)比特加入到已知的flag中，然后如此反复就可以最终求出flag。

这里还有一些操作细节，比如出题人就是利用对数来把累乘改写成累加，并且每次更新10个比特加入flag。不过这些处理方式因人而异

处理到最后会发现由于依然涉及到概率，所以还是可能会有部分错误，不过flag是有明显语意的，因此很容易更正。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
from Crypto.Util.number import *
from math import comb,log
from tqdm import *

#tools
def binxor(bin1,bin2):
    assert len(bin1) == len(bin2)
    res = ""
    for i in range(len(bin1)):
        if(bin1[i] == bin2[i]):
            res += "0"
        else:
            res += "1"    
    return res

def count_known_index(bin1,known_index):
    res = 0
    for i in known_index:
        if(bin1[i] == "1"):
            res += 1
    return res

def func(x,k):
    return int(2**(x-1) - comb(x,k))


#part1 get data
with open(r"D:\题\历届赛题\SEETF 2023\dist_non-neutrality\nn_out.txt","r") as f:
    temp = f.readlines()
c = []
for i in temp:
    c.append(bin(int(i.strip()))[2:].zfill(272))  #notice that len of flag_bin is 271 bits and len of flag is 34 bytes


#part2 judge parity of hamming weight of flag
odd_num = 0
even_num = 0
for i in c:
    if(i.count("1") % 2 == 0):
        even_num += 1
    else:
        odd_num += 1
#print(even_num / odd_num)  #means flag's hamming weight is even at the same time


#part3 init
known_part = b"SEE{" + b"\x00"*29 + b"}"
known_part = bin(bytes_to_long(known_part))[2:].zfill(272)
known_index = []
known_index += [i for i in range(32)]  #prefix
known_index += [(34-1) * 8 + i for i in range(8)]  #suffix
known_index += [i * 8 + 32 for i in range(29)]  #MSB of every byte cause printable
known_index = sorted(known_index)


#part4 remove ci whose hamming weight is odd
C = []
for i in c:
    if(i.count("1") % 2 == 0):
        C.append(i)


#part5 
while(1):
    #means possibility of 1 for every bit
    possiblities = {}
    for t in range(272):
        if(t not in known_index):
            possiblities[t] = 0

    for i in trange(len(C)):
        resi = binxor(C[i],known_part)
        sumi = count_known_index(resi,known_index)
        x = 272 - len(known_index)
        k = 136 - sumi
        if(k <= 1):
            continue
        possible_0 = func(x-1,k)
        possible_1 = func(x-1,k-1)
        
        for j in range(len(C[i])):
            if(j in known_index):
                continue
            if(C[i][j] == "1"):
                possiblities[j] += (log(possible_0) - log(possible_1))
            else:
                possiblities[j] += (log(possible_1) - log(possible_0))
    
    
    #update
    temp = list(sorted(possiblities.items(), key = lambda kv:(abs(kv[1]), kv[0])))[::-1]
    high_level = temp[:10]
    for i in high_level:
        known_index.append(i[0])
    temp = list(known_part)
    for i in high_level:
        if(i[1] > 0):
            temp[i[0]] = "1"
        else:
            temp[i[0]] = "0"
    known_part = "".join(temp)
    print(long_to_bytes(int(known_part,2)))
    print(len(possiblities))


#SEE{__litevally_any_bias_is_bad__}
#->SEE{__literally_any_bias_is_bad__}



Neutrality

题目来源：SEETF 2022

题目描述：

1
I’ve been learning about one-time pads, but they sometimes generate more 1 bits than 0 bits or vice-versa. I think this leaks some information, so it’s better to ensure that the one-time pad is always neutral.

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from secrets import randbits
from Crypto.Util.number import bytes_to_long

# get a one-time-pad in which exactly half the bits are set
def get_xorpad(bitlength):
    xorpad = randbits(bitlength)
    return xorpad if bin(xorpad).count('1') == bitlength // 2 else get_xorpad(bitlength)

def leak_encrypted_flag():
    from secret import flag
    return bytes_to_long(flag.encode()) ^ get_xorpad(len(flag) * 8)

# I managed to leak the encrypted flag a few times
if __name__ == '__main__':
    for _ in range(200):
        print(leak_encrypted_flag())

这是上一道题目的前序版，依然基于MTP，他给出200组密文，每组密文都是如下形式：

其中ti是随机比特串，但这次的特点是0、1的数量一定相等。

而通过密文长度可以确定flag一共是40字节，所以每个ti中0、1都各有160个，这就是解题的关键。具体来说，如果把flag看成是320个0、1变量xj组成的串的话，那么对于每个ti，下面的式子都成立：

这是因为ti中有160个0、160个1，所以flag和密文有160bit相同，另外160bit相差1，累加起来就得到了上式。

有了这个式子后，由于每一个xj都是0或1，都是小量，就自然想到去造格来做。并且由于flag只有40字节，可以合理地推断他没有填充，也是以SEE{}包裹可见字符的形式，因此依然可以确定下40+35个比特位，就减小了不少格的维数。

但是这样做格的维数依然相当大，这是因为上面的式子展开是：

所以一个比特位似乎对应了xj^2与xj两个需要规约出的量，格就变成了接近500维，不太现实。

但是仔细想想会发现，由于xj只有0、1两种取值，所以xj^2=xj总是成立的，上式就可以写作：

这样格的维数就只有200多了，并且数字都很小所以很快就可以LLL出来。然后就按位置把得到的结果填回flag就好了。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from Crypto.Util.number import *

c = 

#tools
def binxor(bin1,bin2):
    assert len(bin1) == len(bin2)
    res = ""
    for i in range(len(bin1)):
        if(bin1[i] == bin2[i]):
            res += "0"
        else:
            res += "1"    
    return res

def count_known_index(bin1,known_index):
    res = 0
    for i in known_index:
        if(bin1[i] == "1"):
            res += 1
    return res


#part1 get known bits index
known_part = b"SEE{" + b"\x00"*35 + b"}"
known_part = bin(bytes_to_long(known_part))[2:].zfill(320)
known_index = []
known_index += [i for i in range(32)]  #prefix
known_index += [(40-1) * 8 + i for i in range(8)]  #suffix
known_index += [i * 8 + 32 for i in range(35)]  #MSB of every byte cause printable
known_index = sorted(known_index)


#part2 remove known bits and LLL
C = []
for i in c:
    temp = bin(i)[2:].zfill(320)
    resi = binxor(temp,known_part)
    sum1 = 160 - count_known_index(resi,known_index)
    
    vec = []
    sum2 = 0
    for j in range(320):
        if(j not in known_index):
            vec.append(1-2*int(temp[j]))
            sum2 += int(temp[j])^2
    vec.append(-(sum1 - sum2))
    C.append(vec)

C = Matrix(ZZ,C).T
L = block_matrix(
    [
        [C,identity_matrix(246)]
    ]
)
L[:,:200] *= 2^20
res = L.LLL()[0]


#part3 get flag
m = res[200:-1]

flag = list(known_part)
for i in range(320):
    if(i not in known_index):
        flag[i] = "*"

ind = 0
for i in range(320):
    if(flag[i] == "*"):
        ind = i
        break

for i in m:
    if(i == 0):
        flag[ind] = "0"
    else:
        flag[ind] = "1"
    if(all(i == "0" or i == "1" for i in flag)):
        break
    while(flag[ind] != "*"):
        ind += 1

print(long_to_bytes(int("".join(flag),2)))


#SEE{50-50_can_be_leaky_4c17bf2a20c4a8df}

然后看hashhash师傅的博客发现了另一个做法，这个做法更巧妙也更容易理解。这个做法定义了一个同态：

也就是将01串映射为1、-1组成的串，这很显然是一个同态，因为如下式子都成立：

有了这个同态后，就可以把明文串m和每一个密文串ci都逐比特映射到m’和ci’上，此时m’和ci’都可以看作是由-1、1组成的长为320的向量，并且运算变成了向量中每一个数值的乘法。那么对于每一组异或式子：

就可以看作是：

然后神奇的事情就发生了，由于向量t中，1和-1刚刚好各一半，所以其和为0，而对于等式右侧来说，他们的和就对应着向量m’和向量ci’的内积，也就是：

那么如果把两百组ci’都拼在一起成为C矩阵的话，可以看出m’就是矩阵方程xC=0的解，这说明m’是C的左核中的短向量，那么问题就变成一个简单的正交格问题了。

但是等式仅有200组而未知量有320个，所以用sage先求出左核基向量的做法太慢了，就不如直接把单位阵和C矩阵拼上做BKZ来的快。

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
from Crypto.Util.number import *

c = 
C = []
for i in range(len(c)):
    temp = bin(c[i])[2:].zfill(320)
    vec = []
    for j in temp:
        if(j == "0"):
            vec.append(1)
        else:
            vec.append(-1)
    C.append(vec)


C = Matrix(ZZ,C).T
L = block_matrix(
    [
        [C,identity_matrix(320)]
    ]
)
L[:,:200] *= 2^20

res = L.BKZ()[0]

m = res[200:]
flag1 = ""
flag2 = ""
for i in m:
    if(i == 1):
        flag1 += "0"
        flag2 += "1"
    else:
        flag1 += "1"
        flag2 += "0"
print(long_to_bytes(int(flag1,2)))
print(long_to_bytes(int(flag2,2)))


#SEE{50-50_can_be_leaky_4c17bf2a20c4a8df}