Hack Dat Kiwi 2017 Writeup

この大会は2017/10/13 13:00(JST)~2017/10/15 13:00(JST)に開催されました。
今回もチームで参戦。結果は605点で306チーム中53位でした。
自分で解けた問題をWriteupとして書いておきます。

PS 1 (Crypto 100)

AESの変形問題。内部の処理の回数などを変更し、簡易化されている。16バイトのブロック暗号で、pboxだけが位置を変更していることに注目して、復号してprintableなテキストに復号されるよう総当たりする。その際、sboxやpboxはphpのソースにデバッグログを入れて、具体的な値を取り出しておく。問題の暗号をテキストファイルenc.txtに保存しておき、次のコードで復号する。

from math import *

BLOCK_SIZE = 16

def get_sbox_for_seed_1396_rounds_1():
    sbox = [70, 162, 120, 88, 97, 191, 116, 211, 240, 171, 174, 123, 47, 59,
            64, 29, 255, 101, 196, 108, 253, 201, 35, 13, 164, 38, 77, 148,
            57, 17, 37, 132, 183, 159, 220, 20, 93, 80, 232, 78, 248, 151, 202,
            43, 214, 8, 75, 213, 113, 12, 66, 112, 217, 106, 128, 129, 145,
            203, 15, 204, 223, 53, 76, 147, 215, 34, 168, 49, 119, 144, 130,
            110, 33, 71, 158, 250, 83, 231, 208, 190, 243, 14, 44, 199, 124,
            170, 68, 5, 115, 89, 210, 79, 143, 26, 226, 99, 63, 138, 154, 184,
            18, 16, 39, 56, 94, 193, 52, 176, 172, 1, 109, 157, 22, 156, 103,
            149, 62, 179, 160, 185, 254, 104, 251, 141, 135, 225, 238, 200,
            92, 133, 126, 117, 153, 169, 180, 237, 87, 228, 150, 2, 230, 249,
            161, 244, 139, 252, 122, 207, 167, 21, 114, 173, 111, 105, 42, 0,
            73, 28, 205, 187, 166, 55, 32, 48, 229, 216, 30, 61, 182, 189, 65,
            140, 188, 233, 127, 60, 227, 7, 19, 131, 31, 146, 45, 175, 9, 91,
            177, 90, 125, 96, 23, 40, 194, 67, 86, 155, 10, 136, 224, 212, 51,
            25, 84, 241, 247, 234, 50, 222, 236, 74, 100, 6, 219, 163, 186,
            239, 245, 81, 72, 118, 195, 95, 165, 98, 178, 246, 242, 181, 102,
            198, 82, 152, 218, 192, 121, 221, 107, 197, 142, 58, 4, 24, 85,
            235, 137, 36, 206, 69, 46, 11, 27, 41, 134, 209, 54, 3]
    return sbox

def get_pbox_for_seed_1396_rounds_1():
    pbox = [4, 10, 7, 5, 6, 13, 8, 14, 15, 9, 11, 2, 0, 1, 3, 12]
    return pbox

def pad(message, block_size):
    length = int(max(floor((len(message)-1)/block_size)+1, 1)*block_size)
    return message + ' ' * (length - len(message))

def sbox(block, reverse = False):
    sbox = get_sbox_for_seed_1396_rounds_1()
    out = ''
    if reverse:
        for i in range(BLOCK_SIZE):
            out += chr(sbox.index(ord(block[i])))
    else:
        for i in range(BLOCK_SIZE):
            out += chr(sbox[ord(block[i])])
    return out

def pbox(block, reverse = False):
    pbox = get_pbox_for_seed_1396_rounds_1()
    out = [' '] * BLOCK_SIZE
    if reverse:
        for i in range(BLOCK_SIZE):
            out[pbox[i]] = block[i]
    else:
        for i in range(BLOCK_SIZE):
            out[i] = block[pbox[i]]
    return ''.join(out)

def xbox(block, key):
    out = ''
    for i in range(BLOCK_SIZE):
        out += chr((ord(block[i]) ^ ord(key[i])) % 256)
    return out

def ps2_block(block, key, decrypt = False):
    key = pad(key, BLOCK_SIZE)

    if decrypt:
        block = xbox(block, key)
        block = pbox(block, decrypt)
        block = sbox(block, decrypt)
    else:
        block = sbox(block, decrypt)
        block = pbox(block, decrypt)
        block = xbox(block, key)
    return block

with open('enc.txt', 'r') as f:
    data = f.read().split(' ')

blocks = []
block = ''
for i in range(len(data)):
    block += chr(int(data[i], 16))
    if i % BLOCK_SIZE == BLOCK_SIZE - 1:
        blocks.append(block)
        block = ''

keys = []
indexes = [4, 10, 7, 5, 6, 13, 8, 14, 15, 9, 11, 2, 0, 1, 3, 12]

for index in indexes:
    for code in range(256):
        fail = False
        len_keys = len(keys)
        if len_keys > 0:
            try_key = keys[len_keys - 1] + chr(code)
        else:
            try_key = chr(code)
        for block in blocks:
            res = ps2_block(block, try_key, True)
            if (ord(res[index]) >= 32 and ord(res[index]) <= 126) \
                or ord(res[index]) == 10 or ord(res[index]) == 13:
                pass
            else:
                fail = True
                break
        if fail == False:
            keys.append(try_key)
            break

dec = ''
for block in blocks:
    dec += ps2_block(block, keys[15], True)

print dec

復号結果は次の通り。

A flag is a piece of fabric (most often rectangular or quadrilateral) with a distinctive design that is used as a symbol, as a signaling device, or as decoration. The term flag is also used to refer to the graphic design employed, and flags have since evolved into a general tool for rudimentary signalling and identification, especially in environments where communication is similarly challenging (such as the maritime environment where semaphore is used). National flags are potent patriotic symbols with varied wide-ranging interpretations, often including strong military associations due to their original and ongoing military uses. Flags are also used in messaging, advertising, or for other decorative purposes. The study of flags is known as vexillology, from the Latin word vexillum, meaning flag or banner.

Due to the use of flags by CTFs, "flag" is also '2qR4twRCoMq7SQb3' in this challenge.
2qR4twRCoMq7SQb3

PS 2 (Crypto 100)

考え方はPS 1と同じ。ただRound数が2になり、複雑性が増す。影響する位置が2箇所に増えることを考慮して、総当たりする。

from math import *

BLOCK_SIZE = 16
ROUNDS = 2

def get_sbox_for_seed_7_rounds_2():
    sbox = []
    sbox1 = [124, 222, 151, 54, 2, 132, 254, 8, 155, 15, 135, 24, 196, 209,
            228, 43, 57, 201, 200, 18, 110, 14, 88, 130, 4, 70, 95, 193, 11,
            23, 51, 138, 241, 198, 187, 244, 77, 185, 251, 227, 202, 128, 249,
            141, 83, 220, 178, 136, 165, 123, 154, 27, 143, 240, 150, 145, 53,
            245, 84, 63, 9, 126, 192, 248, 73, 121, 233, 147, 60, 229, 113, 7,
            102, 109, 149, 186, 79, 74, 69, 247, 205, 223, 20, 91, 212, 168,
            236, 13, 160, 66, 72, 169, 197, 19, 162, 26, 140, 139, 170, 206,
            112, 36, 213, 225, 144, 99, 159, 226, 177, 232, 217, 117, 195, 238,
            216, 156, 137, 199, 167, 49, 28, 252, 218, 215, 10, 114, 242, 133,
            29, 142, 92, 119, 180, 55, 97, 71, 161, 22, 48, 85, 255, 31, 219,
            189, 6, 182, 98, 152, 127, 35, 210, 164, 33, 179, 118, 40, 62, 108,
            183, 81, 38, 44, 234, 224, 93, 82, 52, 21, 101, 104, 105, 96, 129,
            76, 50, 148, 30, 172, 56, 175, 203, 17, 89, 235, 208, 239, 12, 34,
            107, 204, 111, 153, 0, 87, 116, 94, 188, 176, 120, 46, 42, 246,
            163, 181, 65, 214, 67, 90, 125, 122, 32, 68, 166, 115, 58, 103,
            100, 61, 158, 237, 25, 3, 146, 39, 106, 1, 173, 47, 207, 16, 131,
            243, 5, 37, 190, 86, 231, 250, 194, 134, 157, 230, 191, 41, 78,
            253, 171, 211, 64, 45, 184, 80, 59, 75, 221, 174]
    sbox2 = [53, 33, 193, 239, 51, 36, 212, 61, 41, 115, 145, 9, 96, 84, 119,
            209, 49, 52, 226, 144, 47, 105, 95, 127, 130, 15, 233, 162, 72,
            126, 45, 129, 160, 240, 109, 206, 17, 67, 7, 63, 181, 158, 74, 13,
            236, 187, 223, 26, 235, 194, 172, 25, 39, 4, 152, 168, 23, 131, 73,
            98, 248, 116, 217, 150, 99, 71, 101, 118, 137, 108, 178, 55, 0,
            243, 70, 237, 175, 32, 6, 155, 224, 182, 179, 8, 188, 75, 174, 207,
            196, 234, 42, 184, 92, 255, 77, 189, 68, 165, 40, 200, 14, 214,
            247, 16, 198, 59, 249, 112, 90, 253, 254, 57, 170, 167, 64, 103,
            230, 222, 46, 164, 204, 88, 97, 37, 89, 157, 219, 147, 78, 3, 93,
            86, 215, 82, 106, 154, 135, 91, 10, 213, 87, 5, 18, 252, 180, 76,
            113, 159, 43, 146, 79, 244, 227, 163, 29, 58, 69, 250, 203, 140, 1,
            35, 216, 218, 124, 60, 132, 238, 142, 134, 197, 220, 136, 205, 211,
            50, 24, 65, 201, 80, 192, 22, 56, 173, 183, 102, 229, 246, 94, 171,
            133, 100, 208, 107, 31, 81, 148, 156, 48, 21, 27, 251, 241, 153,
            195, 199, 191, 225, 12, 149, 34, 202, 169, 111, 125, 120, 161, 114,
            110, 245, 20, 228, 66, 231, 54, 122, 38, 186, 11, 121, 221, 44,
            123, 190, 177, 30, 151, 141, 19, 176, 83, 85, 139, 232, 138, 2,
            117, 104, 143, 210, 62, 166, 185, 128, 28, 242]
    sbox.append(sbox1)
    sbox.append(sbox2)
    return sbox

def get_pbox_for_seed_7_rounds_2():
    pbox = []
    pbox1 = [7, 14, 9, 2, 0, 8, 15, 1, 10, 3, 11, 4, 13, 12, 6, 5]
    pbox2 = [3, 12, 13, 0, 7, 1, 6, 9, 2, 5, 10, 14, 4, 8, 11, 15]
    pbox.append(pbox1)
    pbox.append(pbox2)
    return pbox

def pad(message, block_size):
    length = int(max(floor((len(message)-1)/block_size)+1, 1)*block_size)
    return message + ' ' * (length - len(message))

def sbox(block, round = 0, reverse = False):
    sbox = get_sbox_for_seed_7_rounds_2()
    out = ''
    if reverse:
        for i in range(BLOCK_SIZE):
            out += chr(sbox[round].index(ord(block[i])))
    else:
        for i in range(BLOCK_SIZE):
            out += chr(sbox[round][ord(block[i])])
    return out

def pbox(block, round = 0, reverse = False):
    pbox = get_pbox_for_seed_7_rounds_2()
    out = [' '] * BLOCK_SIZE
    if reverse:
        for i in range(BLOCK_SIZE):
            out[pbox[round][i]] = block[i]
    else:
        for i in range(BLOCK_SIZE):
            out[i] = block[pbox[round][i]]
    return ''.join(out)

def xbox(block, key):
    out = ''
    for i in range(BLOCK_SIZE):
        out += chr((ord(block[i]) ^ ord(key[i])) % 256)
    return out

def ps2_block(block, key, decrypt = False):
    key = pad(key, BLOCK_SIZE)

    if decrypt:
        for i in range(ROUNDS-1, -1, -1):
            block = xbox(block, key)
            block = pbox(block, i, decrypt)
            block = sbox(block, i, decrypt)
    else:
        for i in range(ROUNDS):
            block = sbox(block, i, decrypt)
            block = pbox(block, i, decrypt)
            block = xbox(block, key)
    return block

with open('enc.txt', 'r') as f:
    data = f.read().split(' ')

blocks = []
block = ''
for i in range(len(data)):
    block += chr(int(data[i], 16))
    if i % BLOCK_SIZE == BLOCK_SIZE - 1:
        blocks.append(block)
        block = ''

keys = []
indexes1 = [7, 14, 9, 2, 0, 8, 15, 1, 10, 3, 11, 4, 13, 12, 6, 5]
indexes2 = [3, 12, 13, 0, 7, 1, 6, 9, 2, 5, 10, 14, 4, 8, 11, 15]

for index1 in indexes2:
    index = indexes1[index1]
    for code1 in range(256):
        for code2 in range(256):
            fail = False
            len_keys = len(keys)
            if len_keys > 0:
                try_key = ''.join(keys) + chr(code1)
            else:
                try_key = chr(code1)
            try_key += chr(code2) * (16 - len(try_key))
            for block in blocks:
                res = ps2_block(block, try_key, True)
                if (ord(res[index]) >= 32 and ord(res[index]) <= 126) \
                    or ord(res[index]) == 10 or ord(res[index]) == 13:
                    pass
                else:
                    fail = True
                    break
            if fail == False:
                keys.append(chr(code1))
                break
        if fail == False:
            break

dec = ''
for block in blocks:
    dec += ps2_block(block, ''.join(keys), True)

print dec

実行結果は以下の通り。

An Easter egg is an intentional inside joke, hidden message, or feature in an interactive work such as a computer program, flag is 4y7u1t2CELXdPVoI, video game or DVD menu screen. The name is used to evoke the idea of a traditional Easter egg hunt.

Released in 1979, Atari's Adventure contained the first hidden message in a video game to have been discovered by its players; the message is "Created by Warren Robinett", and was inserted by Robinett, the game's programmer.[2] According to Robinett, the term Easter egg was applied by Atari personnel on being alerted to the secret addition.[3] Since Atari did not publicly credit game designers, Robinett inserted the message after the game's completion partially in an attempt to gain some recognition for his work.[2] In 2004, an earlier Easter egg was found in Video Whizball, a 1978 game for the Fairchild Channel F system, displaying programmer Bradley Reid-Selth's surname.
4y7u1t2CELXdPVoI

Survey (25)

アンケートに答えるだけ。

hsABf8jG3VK93hQf