changed 6 years ago  
Linked with GitHub
tags: writeups

Writeup for xorz in 2019 De1CTF

Problem

题目描述：

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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的文章。

里面的核心思路就是：

  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}

Select a repo