流密码密钥重用

0x00 前言

最近参加了De1CTF,其中的密码学题目xorz就需要对流密码重用加密后的密文进行爆破攻击,从而得到加密明文和密钥.介于之前接触过流密码相关的题目但没有进行细致归纳,故在此进行归纳总结.

0x01 异或运算

异或运算,也是在模2域上进行的加法,遵循以下法则:

1 xor 1 = 0
0 xor 0 = 0
1 xor 0 = 1
0 xor 1 = 1

下面通过cryptopals set1中的题目进行说明.

0x02 Cryptopals Set1

题目链接:https://cryptopals.com/sets/1

Set0 函数储备

# 十六进制字符串转化为字节数组
def hex_to_bytelist(hexString):
	return [ord(c) for c in hexString.decode('hex')]

# 字节数组转化为十六进制字符串
def bytelist_to_hex(bytelist):
	return ''.join(hex(x)[2:] if x > 15 else '0' + hex(x)[2:] for x in bytelist)

# 字符串转化为十六进制字符串
def str_to_hex(string):
	return string.encode('hex')

# 十六进制字符串转化为字符串
def hex_to_str(hexString):
	return hexString.decode('hex')

# 字节数组转化为字符串
def bytelist_to_str(bytelist):
	return hex_to_str(bytelist_to_hex(bytelist))

# 字符串转化为字节数组
def str_to_bytelist(string):
	return hex_to_bytelist(str_to_hex(string))

# 字节数组异或
def xor(b1, b2):
	result = []
	for i in range(len(b1)):
		result.append(b1[i]^b2[i])
	return result

# 将字符串string以n字节长度的大小进行切分,切分后的每块合为一个列表
def chunks(string, n):
	for i in xrange(0, len(string), n):
		yield string[i:i+n]

Challenge2 Fixed XOR

题目要求:实现一个函数,输入为两个等长的字符串,输出为这两个字符串的异或结果.功能为实现两个等长的字符串异或.
实现方法:

先使用Set0中的str_to_bytelist()方法将字符串转化为字节数组;
然后调用xor()方法进行异或操作;
最后调用bytelist_to_hex()方法将得到的字节数组转化为十六进制字符串.
脚本如下:

def bytelist_to_hex(bytelist):
	return ''.join(hex(x)[2:] if x > 15 else '0' + hex(x)[2:] for x in bytelist)
def hex_to_bytelist(hexString):
	return [ord(c) for c in hexString.decode('hex')]
def xor(b1, b2):
	result = []
	for i in range(len(b1)):
		result.append(b1[i]^b2[i])
	return result
if __name__ == '__main__':
	s1 = hex_to_bytelist('1c0111001f010100061a024b53535009181c')
	s2 = hex_to_bytelist('686974207468652062756c6c277320657965')
	print bytelist_to_hex(xor(s1,s2))

Challenge3 Single-byte XOR cipher

题目要求:给定一个十六进制字符串hexString,它是某个字符串与一个单字符key异或进行加密之后得到的结果.现在已知hexString,我们需要找到key,来解密字符串.
实现方法:

在这个挑战中,我们可以从0-255遍历字符key,对所给的密文进行逐字符异或解密;
通过解密后的英文文本中的字符频率,来对测试key解密结果进行评估.选择出得分最高的key,即可能为正确的key.
脚本如下:

CHARACTER_FREQ = { #字符频率表
    'a': 0.0651738, 'b': 0.0124248, 'c': 0.0217339, 'd': 0.0349835, 'e': 0.1041442, 'f': 0.0197881, 'g': 0.0158610,
    'h': 0.0492888, 'i': 0.0558094, 'j': 0.0009033, 'k': 0.0050529, 'l': 0.0331490, 'm': 0.0202124, 'n': 0.0564513,
    'o': 0.0596302, 'p': 0.0137645, 'q': 0.0008606, 'r': 0.0497563, 's': 0.0515760, 't': 0.0729357, 'u': 0.0225134,
    'v': 0.0082903, 'w': 0.0171272, 'x': 0.0013692, 'y': 0.0145984, 'z': 0.0007836, ' ': 0.1918182}

def get_score(string): #计算字符串的频率得分
    score = 0
    for ch in string:
        ch = ch.lower()
        if ch in CHARACTER_FREQ:
            score += CHARACTER_FREQ[ch]
    return score

def singlebyte_xor(key, string): #单字符异或加密
    res = ""
    for i in string:
        ch = chr(key ^ ord(i))
        res += ch
    return res

def traversal_singlebyte(string): #遍历单个字符解密,评估
    candidate = []
    for key in range(256):
        plaintext = singlebyte_xor(key, string)
        score = get_score(plaintext)
        res={'key': key, 'plaintext': plaintext, 'score': score}
        candidate.append(res)
    #取得分最高的返回
    return sorted(candidate, key = lambda c:c['score'])[-1]

hexString="1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736"
print traversal_singlebyte(hexString.decode('hex'))

Challenge5 Implement repeating-key XOR

题目要求:实现一个函数,给定待加密的字符串和密钥,该函数通过使用重复密钥异或(repeating-key XOR)的方法,加密一段英文文本,返回加密后的结果.
直接贴出实现脚本:

def repeatingkey_xor(string, key):
    res="" #字符串连接<存放每一次加密后的结果
    #xrange方法使得每次处理len(key)长度的字符串
    for i in xrange(0, len(string), len(key)):
        res += bytelist_to_hex(xor(str_to_bytelist(string[i:i+len(key)]), str_to_bytelist(key)))
    return res

string = "Burning 'em, if you ain't quick and nimble\nI go crazy when I hear a cymbal"
key = "ICE"
print repeatingkey_xor(string, key)

Challenge6 Break repeating-key XOR

题目要求:在该挑战中提供了一个文件challenge6.txt,文件中是使用重复密钥异或方法加密后,再经过base64编码后得到的文本,我们需要找到密钥,对其进行解密.
实现方法:

猜测密钥长度KEYSIZE,在一定范围内爆破;
对于每个KEYSIZE,求得每个解密块两两之间的汉明距离,对KEYSIZE取平均值;
选取2-3个最小汉明距离的KEYSIZE;
获取KEYSIZE之后,对每一块的对应字节组合后的字符串与单字符异或,从而可以破解密钥;
对不同KEYSIZE解密之后的明文进行评估,选取得分最高的一组.
对于汉明距离的解释说明及整个爆破过程的具体解法可以参考Hamming Distance的内容.
脚本如下:

def hamming_distance(s1, s2):
        dis = 0
        for i in range(min(len(s1), len(s2))):
            b = bin(ord(s1[i]) ^ ord(s2[i]))
            dis += b.count('1')
        return dis

def guess_keysize(string):
    keys = []
    for keysize in range(2, 40):
        blocks = []
        count = 0
        dis = 0
        for i in range(0, len(string), keysize):
            count += 1
            blocks.append(string[i:i+keysize])
            if count == 4:
                break
        #选取四个块,两两组合求汉明距离
        pairs = itertools.combinations(blocks, 2)
        for (x, y) in pairs:
            dis += hamming_distance(x, y)
        ndis = dis / keysize
        key = {'keysize': keysize, 'distance': ndis}
        keys.append(key)
    return sorted(keys, key=lambda c:c['distance'])[0:3]

def guess_key(keysize, string):
    key = ''
    for i in range(keysize):
        now_str = ''
        #获取每个块相同位置的字符
        for index, ch in enumerate(string):
            if index % keysize == i:
                now_str += ch
        key += chr(traversal_singlebyte(now_str)['key'])
    return key

def break_repeatingkey_xor(string):
    keysizes = guess_keysize(string)
    candidate = []
    plains = []
    for keysize in keysizes:
        key = guess_key(keysize['keysize'], string)
        #二元组:重复密钥异或解密明文,对应密钥key
        plains.append((hex_to_str(repeatingkey_xor(string, key)), key))
    return sorted(plains, key=lambda c:get_score(c[0]))[-1]

f = open('challenge6.txt', 'r')
s = f.read()
string=base64.b64decode(s)
res=break_repeatingkey_xor(string)
print 'plaintext: \n'+res[0]
print 'key: \n'+res[1]

0x03 xorz

题目来源: 2019.8.3-8.5 De1ctf Crypto
题目描述: xorzzz…
题目附件中的py脚本如下:

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

解题思路:
拿到题目之后关注运算代码段:

1	cipher = ''.join([hex(ord(p) ^ ord(next(ki)) ^ ord(next(si)))[2:].zfill(2) for p in plain])

可以发现密文通过key、salt和plain逐位异或得到.题目中已知salt,可以通过逐位异或还原key和plain的异或值.下面可以想到的方法就是爆破,使用上面提到的Break repeating-key XOR脚本,可以爆破出最有可能的明文,从而得到flag,结果如下:
xorz.png-283.2kB