boot2root 2020 Writeup

この大会は2020/12/6 18:30(JST)~2020/12/7 18:30(JST)に開催されました。
今回もチームで参戦。結果は2386点で124チーム中46位でした。
自分で解けた問題をWriteupとして書いておきます。

Euler's Empire (Cryptography)

pow(2, pow(2, t), n) = pow(2, pow(2, t, phi(n)), n)であることを使って復号する。nを素因数分解し、phiを算出する。

n = 611738359 * 648863389 * 775357619 * 806952673 * 834612803 * 848994661 * 856368371 * 914351299 * 940957051 * 973139887
from Crypto.Util.number import *

n = 126176329335043454027341235009057683290541781096785538088437185779950106283534462102786883
t = 1138895128842708275167
z = 22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165185658681843519312254372108072512792854040590016772780908271525769845284796145687079308339

c = 22456023784134158064387550786352078427103553489348641216173010466267938277785173301732037264951635050700506776189809535326121257316490294752439819127486709456258090566784874248887194200916292508316349668172694553726134727726937633467532396106605496205841004277926961591604901357597262377953003319850049478502819166543968493292912201066602832545685929727421332846592671475883986049409546411338070434784675992855275254782158499562211464363321053581615280674425860714715529804670567409115827118589244016504450514019111124308126165145471041974060620715112664770187765206877310029241277556084680387431469989638143534950344

ps = [611738359, 648863389, 775357619, 806952673, 834612803, 848994661, 856368371, 914351299, 940957051, 973139887]
phi = 1
for p in ps:
    phi *= p - 1

l = pow(2, pow(2, t, phi), n)
m = c ^ l ^ z
flag = long_to_bytes(m)
print flag
b00t2root{Eul3r_w4s_4_G3niu5}

Try try but don't cry (Cryptography)

フラグの前半と後半をXORしたあと、base64またはhexエンコードしている。base64やhexデコードを一回ずつしながら元に戻し、11バイトまで戻したら、フラグが"b00t2root{"で始まり、"}"で終わることを使って、復号する。

with open('chall.txt', 'r') as f:
    c = f.read()

c = c.decode('hex')
c = c.decode('hex')
c = c.decode('base64')
c = c.decode('hex')
c = c.decode('hex')
c = c.decode('hex')
c = c.decode('hex')
c = c.decode('hex')
c = c.decode('base64')
c = c.decode('base64')
c = c.decode('base64')
c = c.decode('base64')
c = c.decode('base64')
c = c.decode('base64')
c = c.decode('base64')
c = c.decode('hex')

head_flag = 'b00t2root{'
tail_flag = '}'

flag1 = chr(ord(c[-1]) ^ ord(tail_flag))
flag2 = ''
for i in range(len(head_flag)):
    flag2 += chr(ord(c[i]) ^ ord(head_flag[i]))

flag = head_flag + flag1 + flag2 + tail_flag
print flag
b00t2root{fantasticcc}

007 (Cryptography)

暗号化の処理概要は以下の通り。

・アルファベット小文字のみ、何回かシーザー暗号(シフト数不明)
 ⇒結局1回シフト数不明の暗号をしているのと変わらない。
・base64エンコード
・文字列の0番目と1番目でXORを繰り返し、連結。最後は先頭と末尾でXOR。
・base64エンコード

XORではprintableな文字列に復号できることを前提に復号し、あとはシーザー暗号で"b"から始まることを前提に復号する。

import string

def rot(s, num):
    l = ''
    for i in s:
        if(ord(i) in range(97, 97 + 26)):
            l += chr((ord(i) - 97 + num) % 26 + 97)
        else:
            l += i
    return l

def decrypt_xor(s, k):
    d = chr(k)
    for i in range(len(s) - 1):
        d += chr(ord(s[i]) ^ ord(d[-1]))
    return d

def is_base64(s):
    b64chars = string.letters + string.digits + '/+'
    b64 = s.rstrip('\n').rstrip('=')
    for i in range(len(b64)):
        if b64[i] not in b64chars:
            return False
    return True

cipher = 'MRU2FDcePBQlPwAdVXo5ElN3MDwMNURVDCc9PgwPORJTdzATN2wAN28='
l = cipher.decode('base64')

for code in range(32, 127):
    cipher = decrypt_xor(l, code)
    if is_base64(cipher):
        break

cipher = cipher.decode('base64')
flag = rot(cipher, ord('b') - ord(cipher[0]))
print flag
b00t2root{Bond. James Bond.}

brokenRSA (Cryptography)

e = 4のため、通常のRSA暗号として復号できない。Tonelli-Shanks Algorithmにより、平方剰余を2回繰り返すことによってフラグを求める。

#!/usr/bin/python3
from Crypto.Util.number import *
def legendre(a, p):
    return pow(a, (p - 1) // 2, p)

def tonelli_shanks(a, p):
    if legendre(a, p) != 1:
        raise Exception("not a square (mod p)")

    q = p - 1
    s = 0
    while q % 2 == 0:
        q >>= 1
        s += 1

    for z in range(2, p):
        if legendre(z, p) == p - 1:
            break

    m = s
    c = pow(z, q, p)
    t = pow(a, q, p)
    r = pow(a, (q + 1) // 2, p)

    t2 = 0
    while True:
        if t == 0: return 0
        if t == 1: return r
        t2 = (t * t) % p
        for i in range(1, m):
            if t2 % p == 1:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        m = i
        c = (b * b) % p
        t = (t * c) % p
        r = (r * b) % p

n = 11183632493295722900188836927564142822637910363304123337597708503476804292242860556684644449701772313571249316546794463854991452685201761786385895405863639
c = 8939043592146774508422725937231398285333145869395369605787177287036646137314173055510198460479672008589091362568215564488685390459997440273900039337645280

r = tonelli_shanks(c, n)
rs = [r, n - r]

for i in range(len(rs)):
    m = tonelli_shanks(rs[i], n)
    flag = long_to_bytes(m)
    if flag.startswith(b'b00t2root'):
        print(flag.decode())
        break
b00t2root{finally_legendre_symbol_came_in_handy}

The Heist (Cryptography)

IVと鍵は同じもので暗号化されているので、IVを求め、鍵として渡せば、フラグが表示される。

[平文1ブロック目] ^ IV                  --(暗号化)--> [暗号文1ブロック目]
[平文2ブロック目] ^ [暗号文1ブロック目] --(暗号化)--> [暗号文2ブロック目]

以下の方針でIVを求める。

1.aaaaaaaaaaaaaaaa\x10...\x10 を暗号化
・aaaa... ^ IV  -> ct1
・\x10... ^ ct1 -> ct2

2.ct2を復号
・\x10... ^ ct1 ^ ivが表示される。
 ⇒iv = \x10... ^ ct1 ^ 復号結果

以上を元にスクリプトにする。

import socket

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

def str_xor(s1, s2):
    return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(s1, s2))

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('157.230.237.229', 2200))

try_pt = 'a' * 16
data = recvuntil(s, ': ')
print data + '2'
s.sendall('2\n')

h_try_pt = try_pt.encode('hex')
data = recvuntil(s, ': ')
print data + h_try_pt
s.sendall(h_try_pt + '\n')

data = recvuntil(s, '\n').rstrip()
print data
try_ct = data.split(':  ')[1].decode('hex')

data = recvuntil(s, ': ')
print data + '3'
s.sendall('3\n')

xor_key = str_xor(try_ct[:16], chr(16) * 16)

h_try_ct = try_ct[16:].encode('hex')
data = recvuntil(s, ': ')
print data + h_try_ct
s.sendall(h_try_ct + '\n')

data = recvuntil(s, '\n').rstrip()
print data
try_pt = data.split(':  ')[1].decode('hex')

key = str_xor(try_pt, xor_key).encode('hex')
data = recvuntil(s, ': ')
print data + '1'
s.sendall('1\n')

data = recvuntil(s, ': ')
print data + key
s.sendall(key + '\n')

data = recvuntil(s, '\n').rstrip()
print data

実行結果は以下の通り。

1. Enter key and get flag
2. Encrypt plaintext
3. Decrypt ciphertext

Enter option: 2
Enter hex plaintext: 61616161616161616161616161616161
Ciphertext:  d035b7dd8704f7b634a65a25e29d931045f8da8740a09825fd6512895d3618b7

1. Enter key and get flag
2. Encrypt plaintext
3. Decrypt ciphertext

Enter option: 3
Enter hex ciphertext: 45f8da8740a09825fd6512895d3618b7
Plaintext:  b04ad7a8ee7193ce41c52b5c9ee2f172

1. Enter key and get flag
2. Encrypt plaintext
3. Decrypt ciphertext

Enter option: 1
Enter hex key: 706f706579657468657361696c6f7272
b00t2root{th3y_4r3_g0ing_t0_k1ll_u5}
b00t2root{th3y_4r3_g0ing_t0_k1ll_u5}