Midnight Sun CTF 2020 Writeup

闲着没事做，水了水几道简单的crypto。

Verifier

白给题，直接可以得到签名,flag如下

# midnight{number_used_once_or_twice_or_more}

Pybonhash

题面：

#! /usr/bin/env python 3.6 (3379)
#coding=utf-8
import string, sys, hashlib, binascii
from Crypto.Cipher import AES
from flag import key
# 42 bits key
if not len(key) == 42:
    raise AssertionError
data = open(sys.argv[1], 'rb').read()
# data >= 191
if not len(data) >= 191:
    raise AssertionError

FIBOFFSET = 4919
MAXFIBSIZE = len(key) + len(data) + FIBOFFSET

# 斐波那契数列
def fibseq(n):
    out = [
     0, 1]
    for i in range(2, n):
        out += [out[i - 1] + out[i - 2]]

    return out


FIB = fibseq(MAXFIBSIZE)
i = 0
output = ''
#  len(data) == 204
while i < len(data):
    data1 = data[FIB[i] % len(data)]
    key1 = key[(i + FIB[FIBOFFSET + i]) % len(key)]
    i += 1
    data2 = data[FIB[i] % len(data)]
    key2 = key[(i + FIB[FIBOFFSET + i]) % len(key)]
    i += 1
    tohash = bytes([data1, data2])
    toencrypt = hashlib.md5(tohash).hexdigest()
    thiskey = bytes([key1, key2]) * 16
    cipher = AES.new(thiskey, AES.MODE_ECB)
    enc = cipher.encrypt(toencrypt)
    output += binascii.hexlify(enc).decode('ascii')

print(output)

咋一看很像RC4，仔细一看，好像不是。然后开始了诡异的胡思乱想，看到data，和key都是两位组合的很容易想到爆破，不过我爆破的姿势好像不太对（说到底还是菜），多亏了V师傅的指点，最后勉强搞了出来。赛后看了其他巨巨的思路，发现纯暴力也能做。~菜~

方法一：

爆破key，还原data，如果data不满足md5的格式（也就是16进制），则爆破key失败，反之成功，脚本如下：

# coding=utf-8
def fibseq(n):
    out = [
     0, 1]
    for i in range(2, n):
        out += [out[i - 1] + out[i - 2]]

    return out

MAXFIBSIZE = 4919+192+42+1
FIB = fibseq(MAXFIBSIZE)
FIBOFFSET = 4919
i = 0
cnt = 0
key = [j for j in range(42)]
res = []
while i < 204:
    key1 = key[(i + FIB[FIBOFFSET + i]) % len(key)]
    i += 1
    key2 = key[(i + FIB[FIBOFFSET + i]) % len(key)]
    i += 1
    res.append(key1)
    res.append(key2)
keyseq = res

from Crypto.Cipher import AES



with open("hash.txt")as f:
    enc = f.read()
FIBOFFSET = 4919


# len(key) == 42:


def bruteforce(s):
    for key1 in range(126):
        for key2 in range(126):
            thiskey = bytes([key1, key2]) * 16
            cipher = AES.new(thiskey, AES.MODE_ECB)
            enc = cipher.decrypt(bytes.fromhex(s))
            flag = 0
            for i in enc:
                if chr(i) in '0987654321abcdef':
                    flag += 1
            if flag >= 32:
                return (thiskey[:2]).decode()
    print("no")
    return ""


table = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ{} ,."\'?!'
key = ""
for i in range(0,len(enc),64):
# print(enc[i:i+64])
    key+=bruteforce(enc[i:i+64])
# print(flag)

key = list(key)
print(key)
flag = ['']*42
for i in range(204):
    pos = keyseq[i]
    if flag[pos] == '':
        flag[pos] = key[i]

print(''.join(flag))

方法二：

纯暴力，也是我一开始的想法，贴出一位巨巨的脚本

import binascii,hashlib
from Crypto.Cipher import AES
s=open('hash.txt').read().strip()
s=binascii.unhexlify(s.encode())
n=len(s)//32
kl=42
key=[-1]*kl
# 一开始没有用map，导致写的很麻烦。
fr={}
for i in range(256):
    for j in range(256):
        tohash = bytes([i,j])
        fr[hashlib.md5(tohash).hexdigest().encode()]=(i,j)
FIBOFFSET = 4919
MAXFIBSIZE = 500 + FIBOFFSET
def fibseq(n):
    out = [0, 1]
    for i in range(2, n):
        out += [out[(i - 1)] + out[(i - 2)]]
    return out
FIB = fibseq(MAXFIBSIZE)
def setkey(x,y):
    if key[x]==-1:
        key[x]=y
    assert key[x]==y
for i in range(n):
    t=s[i*32:i*32+32]
    for k1 in range(256):
        for k2 in range(256):
            thiskey = bytes([k1, k2]) * 16
            cipher = AES.new(thiskey, AES.MODE_ECB)
            v = cipher.decrypt(t)
            if v in fr:
                x,y=fr[v]
                setkey(((i*2 + FIB[(FIBOFFSET + i*2)]) % kl),k1)
                setkey(((i*2+1 + FIB[(FIBOFFSET + i*2+1)]) % kl),k2)
print(bytes(key))

rsa_yay

一道魔改题，源于15年的ASIS,大致就是素数p，q的选择是十六进制下的emirp数，方法参考篇writeup，脚本稍微改一下，换成16进制。exp如下：

n = 0x7ef80c5df74e6fecf7031e1f00fbbb74c16dfebe9f6ecd29091d51cac41e30465777f5e3f1f291ea82256a72276db682b539e463a6d9111cf6e2f61e50a9280ca506a0803d2a911914a385ac6079b7c6ec58d6c19248c894e67faddf96a8b88b365f16e7cc4bc6e2b4389fa7555706ab4119199ec20e9928f75393c5dc386c65
def t(a, b, k):
    if k == 64:
        if a*b == n:
            print(a, b)
        return
    for i in range(16):
        for j in range(16):
            # we try to guess the last not-already-guessed digits of both primes
            a1 = a + i*(16**k) + j*(16**(127-k))
            b1 = b + j*(16**k) + i*(16**(127-k))
            if a1*b1 > n:
            # a1 and b1 are too large
                continue
            if (a1+(16**(127-k)))*(b1+(16**(127-k))) < n:
             # a1 and b1 are too small
                continue
            if ((a1*b1)%(16**(k+1))) != (n%(16**(k+1))):
            # The last digits of a1*b1 (which won't change later) doesn't match n
                continue
            # this a1 and b1 seem to be a possible match, try to guess remaining digits
            t(a1, b1, k+1)


for i in range(16):
    t(i*(16**64), i*(16**64), 0)
a = 8149647373983803351750886568540598477647671089400013740300059155182763355863916783703939054112148224308893530604866892896459967322672335047042674959531533
b = 10940426841622676366921134263606230797852377049845508023073731851498778062165943872403574214831422325352658084111135335937429027508321743816310547640134073
# def check(a,b,n):
#     if a*b == n and is_prime(a) and is_prime(b):
#         return true
#     return false
# print(check(a,b,n))
from gmpy2 import *
c = 0x3ea5b2827eaabaec8e6e1d62c6bb3338f537e36d5fd94e5258577e3a729e071aa745195c9c3e88cb8b46d29614cb83414ac7bf59574e55c280276ba1645fdcabb7839cdac4d352c5d2637d3a46b5ee3c0dec7d0402404aa13525719292f65a451452328ccbd8a0b3412ab738191c1f3118206b36692b980abe092486edc38488
phi = (a-1)*(b-1)
e = 65537
d = invert(e,phi)
m = powmod(c,d,n)
print(bytes.fromhex(hex(int(m))[2:]))
# midnight{d1vid3_and_c0nqu3r}

原题是十进制下的emirp数，这道题改成了16进制，理论上算法是可以在任意进制下进行的，脚本如下：

def toBaseLen(n,base):
    res = 0
    while n:
        n /= base
        res += 1
    return res

def reverse(p, q, k,n,base):
    length = toBaseLen(int(n ** (0.5)),base)
    if k == length//2:
        if p*q == n:
            print(p, q)
        return
    for i in range(base):
        for j in range(base):
            # we try to guess the last not-already-guessed digits of both primes
            # i*(base**k) => low bits for p, j*(base**(length-k)) => high bits for p
            p1 = p + i*(base**k) + j*(base**(length-1-k))
            # j*(base**k) => low bits for q, i*(base**(length-k)) => high bits for q
            q1 = q + j*(base**k) + i*(base**(length-1-k))
            if p1*q1 > n:
            # p1 and p1 are too large try another possbilty
                continue
            if (p1+(base**(length-1-k)))*(q1+(base**(length-1-k))) < n:
             # p1 and q1 are too small
                continue
            if ((p1*q1)%(base**(k+1))) != (n%(base**(k+1))):
            # The last digits of p1*q1 (which won't change later) doesn't match n
                continue
            # this p1 and q1 seem to be a possible match, try to guess remaining digits
            reverse(p1, q1,k+1,n,base)

def recover(n,base):
    length = toBaseLen(int(n ** (0.5)),base)
    for i in range(base):
        reverse(i * (base ** (length//2)), i * (base ** (length//2)), 0,n,base)

n = 96625026258243847573409818496863323701263098903763852023545761611791709216811107267542165430964579259522298451526132008185222687761090848204091423802692364769972220056711777368241636068930481983326336008292996182181592439935225401031046612784081789404589006319867469931488138437604142110067838082819866575831
base = 2

recover(n,base)