###### tags: `writeups`

# Writeup for xorz in 2019 De1CTF

## Problem
题目描述：

`crypto_xorz.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

## Analysis
就是一个`stream cipher`。

`key`是`flag`，长度小于38。还加了`salt`，不过这里的`salt`已经给了，可以直接异或回去得到`key^data`。

from itertools import cycle

output = '49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c'
salt="WeAreDe1taTeam"

si = cycle(salt)
output = bytes.fromhex(output)

output = b''.join([bytes([o ^ ord(next(si))]) for o in output])
# b'\x1e]L\x05Q\x04G\x1co#OU\x01U[Z\x01N]\x00\x1c*TG\x05U\x06LD>#[L\x0eY\x03VT*\x13\nBB3ZGU\x1aY\n\x13o\x1d]MD\x0b\tVw6\x13\x18\x0b_\x18@\x15!\x0eOT\x1c\x07ZG\x06N_\x00\x1e*Oq\x18DC\x0cG>$\x13\x01\x1a\x10\x05V\x15=\x1eOE\x06\x14A\x15\x19\x01G\n\x19o\x03[\x0cDC\x18[2.\x13\x08\x06C\x1dZ\x07*F8Y\x01U\\[U\nT\x1c\x1a&\x00VM_\x05LE>2DL\nCMC\x18*\x0b\x1cT\nUAZU\n^\x1b\x0fa:\\\x1f\x10\x02\x1eVw:Z\x02\x06\x10\x08R\x06<J\x18X\x1a\x1d\x15A\x1d\x17\x11\x1b\x05!\x13F\x08P\x10LG"9VL\x07U\x01Z\x13\'\x1e\nUU;ZGU\x1aT\x01\x0e*\x06\x13\x0bU\x06\x00Z90\x13\x18\x0c\x10\x0fR\x07*J\x1b^\x1b\x16]P\x06NA\x1d\x05!\x11\x1f#_\x11LG6$G\tO\x10\x03\\\x06o\x19\x02T\x02\x19\x19\x15\x11\x0bB\x06\x18*TG\x02\x10\x01\t\x13>9E\x05\x17U\tg\x1bo\x0b\x01HN\x06P[\x06\x1bP\x03J)\x11R\x1eDC\x1bZ#?\x13\x18\x0bU\x08\x13\x15#\x05\x01T@7@AU\x03HO\x0c&\x02VMG\n\x18@{w]\x03\x11\x10\x00JT)\x03\x19TN\x06P[\x06\x0bBO\t.\x1aw\x04C\x10\x19R32\x13\x03\rUMU\x1b \x06\x06B\x06U]P\x14\x1cEO\x0c=\x1b^MC\x06\x1eE>9TL\x17X\x08VX\x18\x02\x00\x11\x02\x10TC\x10\x1d\x11\x1a\x04<\x03R\x14U\x07LG?2\x13\x00\n[\x08]\x11<\x19O^\x08UT\x15\x18\x0f_C>\'\r\x13\x1dB\x0c\x19Ww?V\r\x11D\r@T<\x06\x0eG\x0bUT[\x11NG\x0e\x19<\x15_MG\x11\tG4?\x13\x18\x0c\x10\x0fVZ\x00\x04\x03HN\x18L\x15\x05\x02P\x08\x1f*TG\x05E\x10LU6%\x13%CS\x02F\x1a;J\x02HN\x12T\\\x1bBe\x07\x0b;T@\x05UC\x18[6#\x13\x01\x02[\x08@T"\x0fOB\x07\x1b\x15T\x02\x0fC\x0b\x19o\x19VM@\x02\x05]y'

本来想着一个一个单词异或上去看看能不能得到一些有意义的字符串，不过这样效率太低了。

在网上找到一篇很好的讲解`stream cipher`的[文章](https://www.anquanke.com/post/id/161171)。

里面的核心思路就是：
1. 根据**汉明距离**估算出`key`的可能长度。
2. 再根据**字频分析**爆破出`key`。

稍微修改了一下里面的脚本，算出了`key`：

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



b = b'\x1e]L\x05Q\x04G\x1co#OU\x01U[Z\x01N]\x00\x1c*TG\x05U\x06LD>#[L\x0eY\x03VT*\x13\nBB3ZGU\x1aY\n\x13o\x1d]MD\x0b\tVw6\x13\x18\x0b_\x18@\x15!\x0eOT\x1c\x07ZG\x06N_\x00\x1e*Oq\x18DC\x0cG>$\x13\x01\x1a\x10\x05V\x15=\x1eOE\x06\x14A\x15\x19\x01G\n\x19o\x03[\x0cDC\x18[2.\x13\x08\x06C\x1dZ\x07*F8Y\x01U\\[U\nT\x1c\x1a&\x00VM_\x05LE>2DL\nCMC\x18*\x0b\x1cT\nUAZU\n^\x1b\x0fa:\\\x1f\x10\x02\x1eVw:Z\x02\x06\x10\x08R\x06<J\x18X\x1a\x1d\x15A\x1d\x17\x11\x1b\x05!\x13F\x08P\x10LG"9VL\x07U\x01Z\x13\'\x1e\nUU;ZGU\x1aT\x01\x0e*\x06\x13\x0bU\x06\x00Z90\x13\x18\x0c\x10\x0fR\x07*J\x1b^\x1b\x16]P\x06NA\x1d\x05!\x11\x1f#_\x11LG6$G\tO\x10\x03\\\x06o\x19\x02T\x02\x19\x19\x15\x11\x0bB\x06\x18*TG\x02\x10\x01\t\x13>9E\x05\x17U\tg\x1bo\x0b\x01HN\x06P[\x06\x1bP\x03J)\x11R\x1eDC\x1bZ#?\x13\x18\x0bU\x08\x13\x15#\x05\x01T@7@AU\x03HO\x0c&\x02VMG\n\x18@{w]\x03\x11\x10\x00JT)\x03\x19TN\x06P[\x06\x0bBO\t.\x1aw\x04C\x10\x19R32\x13\x03\rUMU\x1b \x06\x06B\x06U]P\x14\x1cEO\x0c=\x1b^MC\x06\x1eE>9TL\x17X\x08VX\x18\x02\x00\x11\x02\x10TC\x10\x1d\x11\x1a\x04<\x03R\x14U\x07LG?2\x13\x00\n[\x08]\x11<\x19O^\x08UT\x15\x18\x0f_C>\'\r\x13\x1dB\x0c\x19Ww?V\r\x11D\r@T<\x06\x0eG\x0bUT[\x11NG\x0e\x19<\x15_MG\x11\tG4?\x13\x18\x0c\x10\x0fVZ\x00\x04\x03HN\x18L\x15\x05\x02P\x08\x1f*TG\x05E\x10LU6%\x13%CS\x02F\x1a;J\x02HN\x12T\\\x1bBe\x07\x0b;T@\x05UC\x18[6#\x13\x01\x02[\x08@T"\x0fOB\x07\x1b\x15T\x02\x0fC\x0b\x19o\x19VM@\x02\x05]y'


normalized_distances = []


for KEYSIZE in range(2, 38):
    # 我们取其中前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)
# keysize: 30
# key is: W3lc0m3tOjo1nu55un1ojOt3m0cl3W
# ...

得到*flag*:`de1ctf{W3lc0m3tOjo1nu55un1ojOt3m0cl3W}`