Mamor's Blog
0%

XOR加密

发表于 分类于
本文字数： 12k 阅读时长 ≈ 11 分钟

简介

异或加密，是密码学中的一种简单加密算法，通常会在出现在Re或Crypto中，用于已知key对flag进行逐位异或，通常会与其他加密算法一起对flag进行加密。本篇将简要介绍异或加密在CTF密码学中的应用，对题目进行简要分析。

【笔者水平有限(密码学小白)，可能会有理解错误的地方，不吝赐教Orz】

异或运算

异或 是一个数学运算符，缩写XOR，应用于逻辑运算，在数学中符号记作“⊕”。如果两个值不相同，那么异或结果为1；如果两个值相同，则异或结果为0。异或运算有如下性质：

交换律：A⊕B=B⊕A

结合律：A⊕(B⊕C)=(A⊕B)⊕C

恒等律：A⊕0=A

自 逆：A⊕A=0

DEMO1

题目描述

1
2
3
4
KEY1 = a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313
KEY2 ^ KEY1 = 37dcb292030faa90d07eec17e3b1c6d8daf94c35d4c9191a5e1e
KEY2 ^ KEY3 = c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1
FLAG ^ KEY1 ^ KEY3 ^ KEY2 = 04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf

题目分析

KEY1 ^ (KEY2 ^ KEY1)

= KEY1 ^ KEY1 ^ KEY2【交换律】

= 0 ^ KEY2 【自逆】

= KEY2 【恒等律】

同理可得 KEY2 ^ (KEY2 ^ KEY3) = KEY3

FLAG ^ KEY1 ^ KEY3 ^ KEY2 = TMP

两侧同时异或KEY1 KEY2 KEY3 可得到FLAG

WP

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

KEY1 = int('a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313', 16)
KEY2_xor_KEY1 = int('37dcb292030faa90d07eec17e3b1c6d8daf94c35d4c9191a5e1e', 16)
KEY2_xor_KEY3 = int('c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1', 16)

KEY2 = KEY1 ^ KEY2_xor_KEY1
KEY3 = KEY2 ^ KEY2_xor_KEY3

FLAG = int('04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf', 16) ^ KEY1 ^ KEY2 ^ KEY3

print(FLAG)
print(long_to_bytes(FLAG))

# 159805433661873705497880084580614789222721324997857681199215485
# b'crypto{x0r_i5_ass0c1at1v3}'

2023MoeCTF xorrrrrrrrr

题目描述

DESCRIPTION: 芝士什么运算？

此题包含一个result.log 和一个task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
flag = open('flag.txt','rb').read()
assert flag.startswith(b'moectf{') and flag.endswith(b'}')
article = open('article.txt','rb').read()

import random

# 对两个字节序列进行异或操作的函数 
# zip(x,y)  异或运算x^y 得到的结果bytes()转换
strxor = lambda x,y: bytes([a^b for a,b in zip(x,y)])

result = []

for i in range(100):
    range_start = random.randint(0, len(article) - len(flag))  # 任意位置开始
    mask = article[range_start:range_start + len(flag)]  # 开始位置 flag长度位
    result.append(strxor(flag,mask))

with open("result.log","w") as fs:
    fs.writelines([str(i)+"\n" for i in result])

题目分析

res = flag ^ mask mask 为 article中 随机取得一段内容

已知 flag的前段部分为moectf{ 异或res，可以得到部分 mask 即部分文章内容碎片(7位的随机)【当时做的时候卡到这里了】

1
2
3
4
5
6
7
8
9
10
flag1 = b"moectf{"
data = eval("["+",".join(open("result.log").readlines())+"]")
for x in data:
    strxor = lambda x, y: bytes([a ^ b for a, b in zip(x, y)])
    tmps = []
    for x in data:
        # 已知前面部分明文
        print((tmp := strxor(flag1, x)))
        tmps.append(tmp)

在这些碎片中存在多处 大似相同的片段 然后取部分内容 匹配出相似的片段【看的wp 看了好久才懂了点 太菜了...Orz】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for i in range(100):
    tmp2 = tmps[i][1:6]
    # print(tmp2)
    for j in range(i+1,100):
        if tmp2 in tmps[j]:
            print(i,j,tmps[i],tmps[j])

# print(tmps)
print(len(tmps))

# 28 33 b'ms. Spe' b'ams. Sp'
# 相差较小中间也包含标点符号  最像同一个片段
c1 = data[33]
c2 = data[28]

# moectf{
flag = [ord('m')] + 71*[0]
# 再次进行异或
for x in range(1,72):
    flag[x] = flag[x-1] ^ c1[x] ^ c2[x-1]

print(flag)
print(bytes(flag))

WP

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
flag1 = b"moectf{"
data = eval("["+",".join(open("result.log").readlines())+"]")
# 参考wp https://github.com/XDSEC/MoeCTF_2023/blob/main/Challenges/Crypto/xorrrrrrrrr/writeup.ipynb
# 可得到 元素为 bytes类型的数组
# print(data)

for x in data:
    strxor = lambda x, y: bytes([a ^ b for a, b in zip(x, y)])
    # print(len(x))
    assert len(x) == 72
    tmps = []
    tmps2 = []
    for x in data:
        # 已知前面部分明文 moectf{
        tmp = strxor(flag1, x)
        tmps.append(tmp)
        # You will learn how to  ... 拼不出来

for i in range(100):
    tmp2 = tmps[i][1:6]
    # print(tmp2)
    for j in range(i+1,100):
        if tmp2 in tmps[j]:
            print(i,j,tmps[i],tmps[j])

# print(tmps)
print(len(tmps))

# 28 33 b'ms. Spe' b'ams. Sp'
# 相差较小  中间包含同一标点 最像同一个片段
c1 = data[33]
c2 = data[28]

# moectf{
flag = [ord('m')] + 71*[0]

for x in range(1,72):
    flag[x] = flag[x-1] ^ c1[x] ^ c2[x-1]

# print(flag)
print(bytes(flag))

# b'moectf{W0W_y0U_HaVe_mastered_tHe_x0r_0Peart0r!_0iYlJf!M3rux9G9Vf!JoxiMl}'

2019 De1CTF XORZ

汉明距离

在做这个题目之前 先简单了解下什么是汉明距离。【看到这题一脸懵，看了WP后才懂了些】

汉明距离【Hamming distance】

在信息论中，两个等长字符串之间的汉明距离 是两个字符串对应位置的不同字符的个数。

简单来说 汉明距离度量了通过替换字符的方式将字符串x变成y所需要的最小的替换次数。比如

1011101与1001001 之间的汉明距离是2。

2143896与2233796之间的汉明距离是3。

"toned"与"roses"之间的汉明距离是3。

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
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

题目分析

参考文章 https://www.anquanke.com/post/id/161171#h2-0

1.去盐

key 38个十六进制数，30个未知字符

[2:].zfill(2) si去掉前两位的0x

salt key都是通过cycle()循环利用，其中salt已知，所以先考虑异或将salt去掉

c = p ^ ki ^ si

c ^ si = p ^ ki

由于c、si均为已知的可求出来。

1
2
3
4
5
6
7
8
9
10
11
12
c = '49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c'
salt = "WeAreDe1taTeam"
si2 = cycle(salt)
nosalt = ''
for i in range(int(len(c)/2)):
    temp = c[i*2:i*2+2]
    # print(binascii.a2b_hex(temp))
    temphex_int = ord(binascii.a2b_hex(temp).decode())
    # p = chr(temphex_int ^ ord(next(si2)) ^ ord(next(ki2)))
    temp_re = hex(temphex_int ^ ord(next(si2)))[2:].zfill(2)
    nosalt = nosalt + temp_re

2.猜解密钥长度

密钥key长度小于38 其中已知位数8位，所以未知位数长度小于30

这里就可以用到汉明距离来猜解密钥长度。快速求解汉明距离的方法 就是 将等长字符串 进行异或。两个二进制字符异或后计算值为1的 比特位格式 就是最后的汉明距离。

1
2
3
hamming("1010", "1111") == 2
hamming("1111", "0000") == 4
hamming("1111", "1111") == 0

大写字母A-Z ascii 65-90 65对应二进制 01000001 90对应二进制 01011010

小写字母a-z ascii 97-122

65对应二进制 01000001

90对应二进制 01011010 字母汉明距离平均为2-3

汉明距离 密钥长度猜解之间的联系：

两个以 Ascii编码的英文字符 之间的汉明距离是 23 所以正常英文字母的评价汉明距离为 23 【每比特】，任意字符（非纯字母）的两两汉明距离 平均为4。

正确分组的密文与密文直接的汉明距离 等于明文与明文之间的汉明距离【通过按正确密钥长度分组的密文与密文异或等于明文与明文异或证明】

所以 当使用正确的密钥长度后，两两字母进行计算汉明距离，这个值会趋于最小。

3.密文解密

1.异或加密中 使用相同密钥加密的明文和密文加存在这个规律： 密文和密文异或 等于 明文和明文异或。

2.空格和所有小写字母异或的结果是对应的大写字母； 空格和所有大写字母异或的结果是对应的小写字母。

除空格外，有些组合可出现异或结果是大小写字母，但是空格出现时，结果在大小写字母间的概率最大。

直接用文章的轮子Orz https://www.anquanke.com/post/id/161171#h2-0 第一步去掉salt后即可直接使用

WP

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
import binascii
import base64
import string
from itertools import *

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("6.txt","r") as f:
#     for line in f:
#         text += line

# b = base64.b64decode(text)

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)


c='49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c'
salt="WeAreDe1taTeam"
si2=cycle(salt)
nosalt=''
for i in range(int(len(c)/2)):
    temp=c[i*2:i*2+2]
    # print(binascii.a2b_hex(temp))
    temphex_int=ord(binascii.a2b_hex(temp).decode())
    # p = chr(temphex_int ^ ord(next(si2)) ^ ord(next(ki2)))
    temp_re= hex(temphex_int ^ ord(next(si2)))[2:].zfill(2)
    nosalt=nosalt+temp_re


b=binascii.a2b_hex(nosalt)

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

References

https://fitzbc.github.io/2019/08/04/De1CTF-xorz-Writeup/

https://www.anquanke.com/post/id/161171#h2-0

欢迎关注我的其它发布渠道

------------- 💖 🌞 本 文 结 束 😚 感 谢 您 的 阅 读 🌞 💖 -------------