menu gh0st
MTP攻击
147 浏览 | 2021-03-06 | 阅读时间: 约 7 分钟 | 分类: CRYPTO学习 | 标签: CRYPTO
请注意,本文编写于 194 天前,最后修改于 141 天前,其中某些信息可能已经过时。

Many-Time-Pad 攻击

​ 前段时间遇到了MTP攻击的题目,然后在安全客上找到一篇文章,这里做一个总结归纳(大部分是安全客文章内容)这是链接

​ 本文讨论的加密方式是异或XOR。准备一个 key 字符串,然后利用 key 去异或相同长度的明文,得到密文。如果每个密文都利用新的 key 去加密,那么这种方式称为“一次一密”(One-Time-Pad)OTP是无条件安全的:即使攻击者拥有无限的计算资源,都不可能破译OTP加密的密文。

​ 然而,一次一密的密钥分发是比较困难的。首先,Alice 想要 给 Bob 发送长度为 n 的信息,则必须在这之前传送长度为 n 的密钥,相当于传输的数据总量翻了倍。其次,尽管密文是无条件安全的,但密钥的传输信道未必是安全的,攻击者一旦窃听了密钥,则可以解密密文。

​ 这里有一个投机取巧的方法—— Alice 造一个比较长的密钥,然后用非常秘密的方式告诉 Bob. 接下来,Alice 每次向 Bob 发送信息,都把明文异或上这个约定好的字符串;Bob 收到信息之后,把密文异或上 key, 于是就可以拿到明文。整个过程只需要传送一次密钥,这是很高效的。这种方式称为 Many-Time-Pad (MTP).

​ 但是,上述的 MTP 办法是不安全的。攻击者如果截获了足够多的密文,就有可能推断出明文、进而拿到密钥。这个缺陷是异或运算的性质带来的。

例题

methon one

​ 为解决这类问题,我们的攻击流程是:分析密钥长度,解出明文。

​ 为了分析密钥长度,我们利用汉明距离(Hamming distance)来猜测密钥长度。首先解释下什么是汉明距离,汉明距离其实是在二进制层面观测两个等长字符串的比特位差异。可以看下下面的例子:

hamming("1011", "1111") == 1
hamming("1111", "0000") == 4
hamming("1111", "1111") == 0

​ 从这里我们可以看到,10111111有两个比特位存在差异,所以汉明距离为1。有一种快速的求解汉明距离的方法就是将等长字符串异或。将两个二进制的字符异或后计算值为1的比特位个数,就是最后的汉明距离。具体的代码如下:

def bxor(a, b):     # xor two byte strings of different lengths
    if len(a) > len(b):
        return bytes([x ^ y for x, y in zip(a[:len(b)], b)])
    else:
        return bytes([x ^ y for x, y in zip(a, b[:len(a)])])

def hamming_distance(b1, b2):
    differing_bits = 0
    for byte in bxor(b1, b2):
        differing_bits += bin(byte).count("1")
    return differing_bits

​ 但是知道了汉明距离又怎么得到密钥长度?通过查阅资料我们可以得到,两个以ascii编码的英文字符的汉明距离是2-3之间,也就是说正常英文字母的平均汉明距离为2-3(每比特),任意字符(非纯字母)的两两汉明距离平均为4。另外我们也容易知道,正确分组的密文与密文的汉明距离等于明文与明文的汉明距离(可以通过按正确密钥长度分组的密文与密文异或等于明文与明文异或证明)。

​ C1 ⊕ C2 = (M1 ⊕ key) ⊕ (M2 ⊕ key) = M1 ⊕ M2

​ 这样,我们可以知道,当我们使用了正确的密钥长度后,两两字母进行计算汉明距离,那么这个值与平均值相差应该是趋于最小。为了增加效率,我们不需要对每一对分组都计算汉明距离,只需取出前几对就可说明问题。当然为了排除偶然误差,结果不应该只取最小的那一个密钥长度,而是酌情多取几组。这里基于例题的代码如下:

import base64

def bxor(a, b):     # xor two byte strings of different lengths
    if len(a) > len(b):
        return bytes([x ^ y for x, y in zip(a[:len(b)], b)])
    else:
        return bytes([x ^ y for x, y in zip(a, b[:len(a)])])

def hamming_distance(b1, b2):
    differing_bits = 0
    for byte in bxor(b1, b2):
        differing_bits += bin(byte).count("1")
    return differing_bits

text = ''
with open("cipher.txt","r") as f:
    for line in f:
        text += line
b = base64.b64decode(text)

normalized_distances = []

for KEYSIZE in range(2, 40):
    #我们取其中前6段计算平局汉明距离
    b1 = b[: KEYSIZE]
    b2 = b[KEYSIZE: KEYSIZE * 2]
    b3 = b[KEYSIZE * 2: KEYSIZE * 3]
    b4 = b[KEYSIZE * 3: KEYSIZE * 4]
    b5 = b[KEYSIZE * 4: KEYSIZE * 5]
    b6 = b[KEYSIZE * 5: KEYSIZE * 6]

    normalized_distance = float(
        hamming_distance(b1, b2) +
        hamming_distance(b2, b3) +
        hamming_distance(b3, b4) +
        hamming_distance(b4, b5) + 
        hamming_distance(b5, b6) 
    ) / (KEYSIZE * 5)

    normalized_distances.append(
        (KEYSIZE, normalized_distance)
    )
normalized_distances = sorted(normalized_distances,key=lambda x:x[1])

print(normalized_distances)

#以下是运行结果:
[(2, 2.4), (5, 2.52), (3, 2.8), (29, 2.8344827586206898), (31, 3.0258064516129033), (18, 3.077777777777778), (15, 3.1333333333333333), (13, 3.1384615384615384), (14, 3.157142857142857), (19, 3.1578947368421053), (20, 3.16), (16, 3.1625), (37, 3.1945945945945944), (6, 3.2), (39, 3.2153846153846155), (11, 3.2181818181818183), (8, 3.225), (12, 3.2333333333333334), (34, 3.2529411764705882), (7, 3.257142857142857), (30, 3.26), (33, 3.2606060606060607), (26, 3.269230769230769), (17, 3.2705882352941176), (21, 3.2857142857142856), (9, 3.2888888888888888), (25, 3.296), (22, 3.3), (28, 3.307142857142857), (24, 3.316666666666667), (32, 3.31875), (35, 3.32), (38, 3.3210526315789473), (23, 3.3391304347826085), (27, 3.3851851851851853), (10, 3.48), (36, 3.4944444444444445), (4, 3.55)]

​ 从结果可以看到密钥长度29比较接近且靠前,事后证明29是正确的,这样我们从前往后取作为密钥长度来进行后面的密钥的猜解就可以大大增加我们的效率,相对于暴力遍历来说。知道密钥长度之后就解出明文。

​ 在此之前我们再提出另一个性质:空格和所有小写字母异或结果是相应的大写字母,空格和所有大写字母异或是相应的小写字母。为了证明这个小技巧,可以使用一个python脚本来遍历输出。

results = []
value = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
for asc1 in value:
    print(asc1,"^0x20---->",chr(ord(asc1)^0x20))

这样当两个密文按照字节异或后的结果处于字母表的ascii值之间,我们就可以有很大的概率认为异或的明文字符之一是空格,那么根据这个规律,我们可以依次遍历出密钥的每个字节,当捕获的密文组足够多,我们就可以有相当大的概率解出整个密钥,因为当密文组够多,我们有很大的概率得到每个密钥对应异或的字节位上的明文为空格,然后依次异或出密钥。为此,有一个常用英文符号两两异或的脚本,遍历输出非空格下,两者异或的结果是字母表区间的python脚本,如下:

results = []
verifycode = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
value = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ,/."'?! :'

for asc1 in value:
    for asc2 in value:
        result = ord(asc1) ^ ord(asc2)
        if chr(result) in verifycode and asc1 != ' ' and asc2 != ' ':
            results.append((asc1, asc2))

filtedresult = []
setresult = set(results)
for i in setresult:
    for j in setresult:
        if set(i) != set(j) and set(i) not in filtedresult:
            filtedresult.append(set(i))

print("verify len:", len(filtedresult))
print("result:", filtedresult)

​ 运行这个脚本,会发现有349种可能的情况,那么是不是说明运用空格这个点来破解不合理?其实不然,要知道,这349中可能性里面,没有哪一个字符可以满足与任何一个字母异或都是字母区间,这就是说,空格及有无可挑剔的最大可能。这样一来,我们可以分别按照密钥将密文重新分组,将异或用一个密钥字节的密文合并成一组,这样一来我们就可以拥有密钥长度个组,每个组都是明文异或同一个密钥字节得来的密文。取其中一个分组,将里面的字符两两异或,记录每个字符与其他每一个字符异或出现结果是字母的次数,取最大次数(因为根据概率学,明文空格情况下,该次数应该是最大的,当然不排除极小概率的特殊情况)的字符我们将推断其明文为空格,然后异或出该分组的密钥字节。

​ 例如:密文是1234567890abcde,而且得到密钥长度为3,则分为三组,A:1470c;B:258ad;C:369be,三组组内两两异或,其中异或得到字符次数最多的就是明文空格所在处。每个分组做如下的操作:每个分组做嵌套循环,内循环,外循环。设置外循环计数值possible*_space=0,max_*possible=0,设置内循环计数值maxpossible=0,依次取出每个分组中的每一个字节做与其他字节两两抑或进行内循环,如果结果是字母,我们就把内循环计数值maxpossible+1,在每个内循环结束后进行max*_possible的更新(与内循环maxpossible做对比),并记录当前字节的位置到possible_*space,然后外循环继续。直至遍历完所有的字节。取出maxpossible对应的字节位置`possiblespace处的字节码,我们把它对应的明文假设成空格(根据之前的讨论)然后将该位置的字节和0x20`(空格)异或;找出相应位置的密钥字节。代码如下:

def break_single_key_xor(text):
    key = 0
    possible_space=0
    max_possible=0
    letters = string.ascii_letters.encode('ascii')
    for a in range(0, len(text)):
        maxpossible = 0
        for b in range(0, len(text)):
            if(a == b):
                continue
            c = text[a] ^ text[b]
            if c not in letters and c != 0:
                continue
            maxpossible += 1
        if maxpossible>max_possible:
            max_possible=maxpossible
            possible_space=a
    key = text[possible_space]^ 0x20
    return chr(key)

text = ''
with open("cipher.txt","r") as f:
    for line in f:
        text += line

b = base64.b64decode(text)

for KEYSIZE in range(2, 40):
    # KEYSIZE=29
    block_bytes = [[] for _ in range(KEYSIZE)]
    for i, byte in enumerate(b):
        block_bytes[i % KEYSIZE].append(byte)
    keys = ''
    try:
        for bbytes in block_bytes:
            keys += break_single_key_xor(bbytes)
        key = bytearray(keys * len(b), "utf-8")
        plaintext = bxor(b, key)
        print("keysize:", KEYSIZE)
        print("key is:", keys, "n")
        s = bytes.decode(plaintext)
        print(s)
    except Exception:
        continue

​ 这里分析密钥长度是爆破的方式,如果采用之前的汉明距离会优化很多,代码如下:

import base64
import string

def bxor(a, b):     # xor two byte strings of different lengths
    if len(a) > len(b):
        return bytes([x ^ y for x, y in zip(a[:len(b)], b)])
    else:
        return bytes([x ^ y for x, y in zip(a, b[:len(a)])])

def hamming_distance(b1, b2):
    differing_bits = 0
    for byte in bxor(b1, b2):
        differing_bits += bin(byte).count("1")
    return differing_bits

def break_single_key_xor(text):
    key = 0
    possible_space=0
    max_possible=0
    letters = string.ascii_letters.encode('ascii')
    for a in range(0, len(text)):
        maxpossible = 0
        for b in range(0, len(text)):
            if(a == b):
                continue
            c = text[a] ^ text[b]
            if c not in letters and c != 0:
                continue
            maxpossible += 1
        if maxpossible>max_possible:
            max_possible=maxpossible
            possible_space=a
    key = text[possible_space]^ 0x20
    return chr(key)

text = ''
with open("cipher.txt","r") as f:
    for line in f:
        text += line
b = base64.b64decode(text)

normalized_distances = []

for KEYSIZE in range(2, 40):
    #我们取其中前6段计算平局汉明距离
    b1 = b[: KEYSIZE]
    b2 = b[KEYSIZE: KEYSIZE * 2]
    b3 = b[KEYSIZE * 2: KEYSIZE * 3]
    b4 = b[KEYSIZE * 3: KEYSIZE * 4]
    b5 = b[KEYSIZE * 4: KEYSIZE * 5]
    b6 = b[KEYSIZE * 5: KEYSIZE * 6]

    normalized_distance = float(
        hamming_distance(b1, b2) +
        hamming_distance(b2, b3) +
        hamming_distance(b3, b4) +
        hamming_distance(b4, b5) + 
        hamming_distance(b5, b6) 
    ) / (KEYSIZE * 5)
    normalized_distances.append(
        (KEYSIZE, normalized_distance)
    )
normalized_distances = sorted(normalized_distances,key=lambda x:x[1])

for KEYSIZE,_ in normalized_distances[:5]:
    block_bytes = [[] for _ in range(KEYSIZE)]
    for i, byte in enumerate(b):
        block_bytes[i % KEYSIZE].append(byte)
    keys = ''
    try:
        for bbytes in block_bytes:
            keys += break_single_key_xor(bbytes)
        key = bytearray(keys * len(b), "utf-8")
        plaintext = bxor(b, key)
        print("keysize:", KEYSIZE)
        print("key is:", keys, "n")
        s = bytes.decode(plaintext)
        print(s)
    except Exception:
        continue

methon two

​ 上面是先利用汉明距离分析密钥长度然后根据空格的特性求解,还有一种是采用词频攻击的方式。上面我们在分析完密钥长度后对密文进行了分组,就有了一组组类似凯撒加密的密文,只不过他们组不成完整的词或句子,如果我们单单暴力遍历256种密钥可能,那么结果我们也缺少一个衡量的指标,别说256中可能够你看的,而且没有一种是成词成句的。我们可以给英文中的字母根据百分比附一个权重,然后依次计算256组解密后的“明文”总权重,当总权值最高时,我们有理由相信这时的密钥字节是正确的。因为当截获的密文足够多,我们可以得到分布十分贴近字频规律的明文,这样算出来的总权值就越大。关于字频的统计特性,我们可以在网上搜到很多权重赋值版本。下面是相应的代码:

import base64
import string

def bxor(a, b):     # xor two byte strings of different lengths
    if len(a) > len(b):
        return bytes([x ^ y for x, y in zip(a[:len(b)], b)])
    else:
        return bytes([x ^ y for x, y in zip(a, b[:len(a)])])

def hamming_distance(b1, b2):
    differing_bits = 0
    for byte in bxor(b1, b2):
        differing_bits += bin(byte).count("1")
    return differing_bits

def score(s):
    freq = {}
    freq[' '] = 700000000
    freq['e'] = 390395169
    freq['t'] = 282039486
    freq['a'] = 248362256
    freq['o'] = 235661502
    freq['i'] = 214822972
    freq['n'] = 214319386
    freq['s'] = 196844692
    freq['h'] = 193607737
    freq['r'] = 184990759
    freq['d'] = 134044565
    freq['l'] = 125951672
    freq['u'] = 88219598
    freq['c'] = 79962026
    freq['m'] = 79502870
    freq['f'] = 72967175
    freq['w'] = 69069021
    freq['g'] = 61549736
    freq['y'] = 59010696
    freq['p'] = 55746578
    freq['b'] = 47673928
    freq['v'] = 30476191
    freq['k'] = 22969448
    freq['x'] = 5574077
    freq['j'] = 4507165
    freq['q'] = 3649838
    freq['z'] = 2456495
    score = 0
    string=bytes.decode(s)
    for c in string.lower():
        if c in freq:
            score += freq[c]
    return score

def break_single_key_xor(b1):
    max_score = 0
    english_plaintext = 0
    key = 0

    for i in range(0,256):
        b2 = [i] * len(b1)
        try:
            plaintext = bxor(b1, b2)
            pscore = score(plaintext)
        except Exception:
            continue
        if pscore > max_score or not max_score:
            max_score = pscore
            english_plaintext = plaintext
            key = chr(i)
    return key

text = ''
with open(r"cipher.txt", "r") as f:
    for line in f:
        text += line
b = base64.b64decode(text)

normalized_distances = []

for KEYSIZE in range(2, 40):
    # 我们取其中前6段计算平局汉明距离
    b1 = b[: KEYSIZE]
    b2 = b[KEYSIZE: KEYSIZE * 2]
    b3 = b[KEYSIZE * 2: KEYSIZE * 3]
    b4 = b[KEYSIZE * 3: KEYSIZE * 4]
    b5 = b[KEYSIZE * 4: KEYSIZE * 5]
    b6 = b[KEYSIZE * 5: KEYSIZE * 6]
    b7 = b[KEYSIZE * 6: KEYSIZE * 7]

    normalized_distance = float(
        hamming_distance(b1, b2) +
        hamming_distance(b2, b3) +
        hamming_distance(b3, b4) +
        hamming_distance(b4, b5) +
        hamming_distance(b5, b6) 
    ) / (KEYSIZE * 5)
    normalized_distances.append(
        (KEYSIZE, normalized_distance)
    )
normalized_distances = sorted(normalized_distances, key=lambda x: x[1])

for KEYSIZE, _ in normalized_distances[:5]:
    block_bytes = [[] for _ in range(KEYSIZE)]
    for i, byte in enumerate(b):
        block_bytes[i % KEYSIZE].append(byte)
    keys = ''

    for bbytes in block_bytes:
        keys += break_single_key_xor(bbytes)
    key = bytearray(keys * len(b), "utf-8")
    plaintext = bxor(b, key)
    print("keysize:", KEYSIZE)
    print("key is:", keys, "n")
    s = bytes.decode(plaintext)
    print(s)

​ 这里有一些总结:

  1. 在异或加密中,明文和明文异或等于密文和密文异或,并且二者的汉明距离一样。
  2. 空格和所有小写字母异或结果是相应的大写字母,空格和所有大写字母异或是相应的小写字母。除了空格以外,仍旧有一些组合可以出现异或结果是大小写字母,但是空格出现时,结果在大小写字母间的概率最大。
  3. 两个以ascii编码的英文字符的汉明距离是2-3之间,也就是说正常英文字母的平均汉明距离为2-3(每比特),任意字符(非纯字母)的两两汉明距离平均为4。
  4. 在破解这类问题的三步走:猜解密钥长度;根据密钥长度分组,依次求解密钥每个字节得出密钥;最后根据密钥还原出明文。

methon three

​ 例题为:

BUUCTF: [AFCTF2018]你听过一次一密么?

25030206463d3d393131555f7f1d061d4052111a19544e2e5d54
0f020606150f203f307f5c0a7f24070747130e16545000035d54
1203075429152a7020365c167f390f1013170b1006481e13144e
0f4610170e1e2235787f7853372c0f065752111b15454e0e0901
081543000e1e6f3f3a3348533a270d064a02111a1b5f4e0a1855
0909075412132e247436425332281a1c561f04071d520f0b1158
4116111b101e2170203011113a69001b47520601155205021901
041006064612297020375453342c17545a01451811411a470e44
021311114a5b0335207f7c167f22001b44520c15544801125d40
06140611460c26243c7f5c167f3d015446010053005907145d44
0f05110d160f263f3a7f4210372c03111313090415481d49530f

​ 我们将C1和其他各组密文异或得到:

....S....N.U.....A..M.N...
...Ro..I...I....SE....P.I.
.E..H...IN..H...........TU
..A.H.R.....E....P......E.
...RT...E...M....M....A.L.
d...V..I..DNEt........K.DU
.......I....K..I.ST...TiS.
.....f...N.I........M.O...
.........N.I...I.S.I..I...
....P....N.OH...SA....Sg..

​ 由上面的结果和空格的性质我们可以知道,如果某一列中出现的字符数越多,这个位置的明文越可能是空格。所以我们对于每一条密文Ci,拿去异或其他所有密文。然后去数每一列有多少个英文字符,作为”Mi在这一位是空格”的评分。上面的事情做完时候,依据评分从大到小排序,依次利用 “某个明文的某一位是空格” 这种信息恢复出所有明文的那一列。如果产生冲突,则舍弃掉评分小的。不难写出代码:

import Crypto.Util.strxor as xo
import libnum, codecs, numpy as np

def isChr(x):
    if ord('a') <= x and x <= ord('z'): return True
    if ord('A') <= x and x <= ord('Z'): return True
    return False

def infer(index, pos):
    if msg[index, pos] != 0:
        return
    msg[index, pos] = ord(' ')
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(' ')

dat = []

def getSpace():
    for index, x in enumerate(c):
        res = [xo.strxor(x, y) for y in c if x!=y]
        f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
        cnt = [f(pos) for pos in range(len(x))]
        for pos in range(len(x)):
            dat.append((f(pos), index, pos))

c = [codecs.decode(x.strip().encode(), 'hex') for x in open('Problem.txt', 'r').readlines()]

msg = np.zeros([len(c), len(c[0])], dtype=int)

getSpace()

dat = sorted(dat)[::-1]
for w, index, pos in dat:
    infer(index, pos)

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))

​ 执行结果是:

Dear Friend, T%is tim< I u
nderstood my m$stake 8nd u
sed One time p,d encr ptio
n scheme, I he,rd tha- it 
is the only en.ryptio7 met
hod that is ma9hemati:ally
 proven to be #ot cra:ked 
ever if the ke4 is ke)t se
cure, Let Me k#ow if  ou a
gree with me t" use t1is e
ncryption sche e alwa s...

​ 显然这不是最终结果,我们得修正几项。把 "k#now" 修复成 "know",把 "alwa s" 修复成 "always"。代码如下:

def know(index, pos, ch):
    msg[index, pos] = ord(ch)
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(ch)

know(10, 21, 'y')
know(8, 14, 'n')

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))

​ 最终结果是:

Dear Friend, This time I u
nderstood my mistake and u
sed One time pad encryptio
n scheme, I heard that it 
is the only encryption met
hod that is mathematically
 proven to be not cracked 
ever if the key is kept se
cure, Let Me know if you a
gree with me to use this e
ncryption scheme always...

​ 我们成功恢复了明文!那么 key 也很好取得了:把 C1 异或上 M1 即可。

key = xo.strxor(c[0], ''.join([chr(c) for c in msg[0]]).encode())
print(key)

# b'afctf{OPT_1s_Int3rest1ng}!'

​ 完整的exp:

import Crypto.Util.strxor as xo
import libnum, codecs, numpy as np

def isChr(x):
    if ord('a') <= x and x <= ord('z'): return True
    if ord('A') <= x and x <= ord('Z'): return True
    return False

def infer(index, pos):
    if msg[index, pos] != 0:
        return
    msg[index, pos] = ord(' ')
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(' ')

def know(index, pos, ch):
    msg[index, pos] = ord(ch)
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(ch)

dat = []

def getSpace():
    for index, x in enumerate(c):
        res = [xo.strxor(x, y) for y in c if x!=y]
        f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
        cnt = [f(pos) for pos in range(len(x))]
        for pos in range(len(x)):
            dat.append((f(pos), index, pos))

c = [codecs.decode(x.strip().encode(), 'hex') for x in open('Problem.txt', 'r').readlines()]

msg = np.zeros([len(c), len(c[0])], dtype=int)

getSpace()

dat = sorted(dat)[::-1]
for w, index, pos in dat:
    infer(index, pos)

know(10, 21, 'y')
know(8, 14, 'n')

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))

key = xo.strxor(c[0], ''.join([chr(c) for c in msg[0]]).encode())
print(key)

​ 另外一题[De1CTF2019]xorz

from itertools import *
from data import flag,plain

key=flag.strip("de1ctf{").strip("}")
assert(len(key)<38)
salt="WeAreDe1taTeam"
ki=cycle(key)
si=cycle(salt)
cipher = ''.join([hex(ord(p) ^ ord(next(ki)) ^ ord(next(si)))[2:].zfill(2) for p in plain])
print cipher
# output:
# 49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c

​ 从题目代码我们可以得到 m[i]⊕k[i]⊕s[i],其中 s 已知,故实际上我们拿到了 m[i]⊕k[i]。在这里 k 是有周期的,且周期不超过38。如果知道了 k 的周期,那么用 Many-Time-Pad 就可以成功攻击。由于 len(key) 并不大,从大到小枚举 len(key),肉眼判断是否为flag即可。最后发现 len(key)=30 是满足要求的。

from itertools import cycle
import codecs, numpy as np
import Crypto.Util.strxor as xo

salt="WeAreDe1taTeam"
si=cycle(salt)

c = codecs.decode('49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c', 'hex')

a = [r ^ ord(next(si)) for r in c]  # a[i] = m[i] ^ k[i]

def div(sz):
    ret = [''.join([chr(ch) for ch in a[i*sz : (i+1)*sz]]).encode() for i in range(len(a)//sz)]
    # if len(a) % sz != 0:
        # ret.append(a[len(a)//sz*sz:])
    print('\n'.join(map(lambda x:codecs.encode(x, 'hex').decode(), ret)))
    return ret

sz = 30
t = div(sz)

#上面输出的数据放到1.txt里面,然后执行下面的mtp攻击

import Crypto.Util.strxor as xo
import libnum, codecs, numpy as np

def isChr(x):
    if ord('a') <= x and x <= ord('z'): return True
    if ord('A') <= x and x <= ord('Z'): return True
    return False

def infer(index, pos):
    if msg[index, pos] != 0:
        return
    msg[index, pos] = ord(' ')
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(' ')

dat = []

def getSpace():
    for index, x in enumerate(c):
        res = [xo.strxor(x, y) for y in c if x!=y]
        f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
        cnt = [f(pos) for pos in range(len(x))]
        for pos in range(len(x)):
            dat.append((f(pos), index, pos))

c = [codecs.decode(x.strip().encode(), 'hex') for x in open('1.txt', 'r').readlines()]

msg = np.zeros([len(c), len(c[0])], dtype=int)

getSpace()

dat = sorted(dat)[::-1]
for w, index, pos in dat:
    infer(index, pos)

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))
key = xo.strxor(c[0], ''.join([chr(c) for c in msg[0]]).encode())
print(key)

最后贴上基本是粘贴的博客

https://www.anquanke.com/post/id/161171#h3-6

https://www.ruanx.net/many-time-pad/

发表评论

email
web

全部评论 (共 2 条评论)

    2021-03-07 22:57
    nnyyds,dlddw
      2021-03-07 22:58
      @qz呜呜呜,zzyyds