ångstromCTF 2020 writeup [Crypto]

ångstromCTF 2020 のCryptoのwriteupです。

Keysar (40pts)

Keyed Caesar Cipherというのがあるらしいので、オンラインデコーダーで復号しました。
actf{yum_delicious_salad}

Reasonably Strong Algorithm (70pts)

n = 126390312099294739294606157407778835887
e = 65537
c = 13612260682947644362892911986815626931

とのこと。
$n = 126390312099294739294606157407778835887$と小さめなので、素因数分解できます。

$ ./msieve -q -v 126390312099294739294606157407778835887
prp19 factor: 9336949138571181619
prp20 factor: 13536574980062068373
elapsed time 00:00:01
$ python3 -c "print(9336949138571181619*13536574980062068373)"
126390312099294739294606157407778835887

あとは復号するだけです。

n = 126390312099294739294606157407778835887
e = 65537
c = 13612260682947644362892911986815626931

p = 9336949138571181619
q = 13536574980062068373

print(p*q, p*q==n)

def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return c0, a0, b0

x = 65537
y = (p-1)*(q-1)
print(ex_euclid(x,y))
print(x*ex_euclid(x,y)[1]+y*ex_euclid(x,y)[2])

d = ex_euclid(x,y)[1]+y
print(d)

m = pow(c,d,n)

print(m)
print(hex(m))

m = str(hex(m))[2:]
ans = ""
while(m):
    ans += chr(int(m[:2], 16))
    m = m[2:]
print(ans)

$ python3 solve.py 
126390312099294739294606157407778835887 True
(1, -4273630645468012607018318131265493055, 2216)
1
122116681453826726664714315157880092841
505669976011892616877716395432178557
0x616374667b31306d696e757465737d
actf{10minutes}

Wacko Images (90pts)

謎の画像とプログラムが渡されます。
元画像の各ピクセルのRGBの3値と$key=[41,37,23]$について、それぞれ掛けて251で割った余りを新しい画像のピクセルの値にしています。

その逆のことをするプログラムを書けばできます。

from numpy import *
from PIL import Image

flag = Image.open(r"enc.png")
img = array(flag)

key = [41, 37, 23]

a, b, c = img.shape

for x in range (0, a):
    for y in range (0, b):
        pixel = img[x, y]
        for i in range(0,3):
            for j in range(256):
                if pixel[i] == j * key[i] % 251:
                    pixel[i] = j
        img[x][y] = pixel

enc = Image.fromarray(img)
enc.save('dec.png')

dec

無理やり読みます。actf{m0dd1ng_sk1llz}

Confused Streaming (100pts)

flagのバイナリ列とkeystreamのxorが出力されます。

整数a,b,cを

  • $b^2\geq 4ac$
  • $a,b,c\neq 0$
  • $-1000\lt a,b,c \lt 1000$
  • $b^2-4ac$は平方数でない

という条件で入力すると、
$key = \sqrt{b^2-4ac}-b$となり、
keystreamではランダムな$100\leq e\leq 1000, 1\leq d\leq 100$を用いて、

  • $ret1 = key^e$の小数部分
  • $ret2 = ret1 * 2^d$
  • yield [ret2の整数部分]%2
    を返しています。

$|key|$が0.5未満であれば$key^e$は1未満なので$ret1=|key^e|=|key|^e$であり、
$|key|^e2^d \lt |key|^e2^e\lt 1^e$なのでret2の整数部分は必ず0になります。これにより、出力されるバイナリはflagそのものになります。

$ nc crypto.2020.chall.actf.co 20601
a: 1
b: 100
c: 4
01100001011000110111010001100110011110110110010001101111011101110110111001011111011101000110111101011111011101000110100001100101010111110110010001100101011000110110100101101101011000010110110001111101

$ python3
>>> from binascii import *
>>> a = int('01100001011000110111010001100110011110110110010001101111011101110110111001011111011101000110111101011111011101000110100001100101010111110110010001100101011000110110100101101101011000010110110001111101',2)
>>> unhexlify('%x'%a)
b'actf{down_to_the_decimal}'

one time bad (100pts)

プログラムは実行されるとint(time.time())をrandom.seedに設定しています。よって、こちらがnc misc.2020.chall.actf.co 20301に接続した直後に

import time
print(int(time.time()))

を実行するなどしてtimeの値を記録すれば、記録したtimeからいくつか整数を引いた数がプログラムで使われているtimeです。

そのため、timeから1ずつ引きながら、プログラムとrandomの呼び出し回数が一致するように気を付けながら同様のプログラムを実行し、base64エンコードされたx,kの値が一致するtimeを探せばよいです。

たとえば、手元で記録したtimeが1584781158、プログラムの1) Request sampleの実行結果が

> 1
JS8NMTkVBwQNIwcxDSk6Ax0HPis2DS4SBAEA with key VENPVnpSV01od3VDQ3F1elNOV0lxVEtZRVZo

の場合を考えます。

以下のプログラムを実行します。

import random, time
import string
import base64
import os

def otp(a, b):
    r = ""
    for i, j in zip(a, b):
        r += chr(ord(i) ^ ord(j))
    return r

def genSample():
    p = ''.join([string.ascii_letters[random.randint(0, len(string.ascii_letters)-1)] for _ in range(random.randint(1, 30))])
    k = ''.join([string.ascii_letters[random.randint(0, len(string.ascii_letters)-1)] for _ in range(len(p))])
    x = otp(p, k)
    return x, p, k

def randmake(bs):
    random.seed(bs)
    print("###", bs)
    x,p,k = genSample()
    print(x)
    print(p)
    print(k)
    print(base64.b64encode(x.encode()).decode(), "with key", base64.b64encode(k.encode()).decode())
    x,p,k = genSample()
    print(x)
    print(p)
    print(k)
    print(base64.b64encode(x.encode()).decode(), "with key", base64.b64encode(k.encode()).decode())

base_seed = 1584781158

#make()
for i in range(5):
    randmake(base_seed - i)

### 1584781158


'482!
bzznypDGX
npmIMHvfV
DAoXJzQ4MiEO with key bnBtSU1IdmZW
 :
WDxb
wVzX
IBICOg== with key d1Z6WA==
### 1584781157
0271        
            9&";"6
TJrQRDTpFalYzbZwgfunkaFTL
PzcceUTxBPeRCDALEuhUdqdbT
BDARMjcRAAgEMQkLOSYbOyITHTsPECI2GA== with key UHpjY2VVVHhCUGVSQ0RBTEV1aFVkcWRiVA==
''/8%*     !&$
mJgLRgYtLONcePwBrzwgrdkzHTSCE
JveXGixZqaBjfUVdVwPtlyLUpDviK
JzwCFBUOIS49LgwJAwUhJiQNJxMeHScvOBAlKg4= with key SnZlWEdpeFpxYUJqZlVWZFZ3UHRseUxVcER2aUs=
### 1584781156
$4+6626+2=4*0)
pEhGlzXLjAZtBhWXMemGedpqfz
TGrsGLnRvsXBiZVeytGwgMqjkO
JAIaNCs2Nh4cMgI2KzIBPTQRKjACKQEbDTU= with key VEdyc0dMblJ2c1hCaVpWZXl0R3dnTXFqa08=
$>707 3,"*3
fkfIuTMYaaPIhaJfKonugSQSke
BxrwgcHibVJIvRfDajxjqWNRXr
JBMUPhI3BTADNxoAHjMsIioFFh8WBB8BMxc= with key Qnhyd2djSGliVkpJdlJmRGFqeGpxV05SWHI=
### 1584781155
6%;
cYjb
koOY
CDYlOw== with key a29PWQ==
(63
cDqu
KrBg
KDYzEg== with key S3JCZw==
### 1584781154
. +6
qlBgCGPIeTrrNXOyNIibGYeKAWh
TCOVzRWMhwuCCquzSNWIqTKYEVh
JS8NMTkVBwQNIwcxDSk6Ax0HPis2DS4SBAEA with key VENPVnpSV01od3VDQ3F1elNOV0lxVEtZRVZo
";>7/9
BrGkwXmIWrybyQn
JPVeLfjUBEjMfhN
CCIRDjs+BxwVNxMvHzkg with key SlBWZUxmalVCRWpNZmhO

これを見ると、timeが1584781154の時に一回目のgensample()の結果のx,kをbase64エンコードしたJS8NMTkVBwQNIwcxDSk6Ax0HPis2DS4SBAEA with key VENPVnpSV01od3VDQ3F1elNOV0lxVEtZRVZoが一致しています。よってプログラムで使われているtimeは1584781154であると確認できます。
あとは、ncの接続を閉じずに2) Try your luck at decrypting something!を呼びます。ここで問題はちゃんと

> 2
CCIRDjs+BxwVNxMvHzkg

になっています。答えはpの値、BrGkwXmIWrybyQnとなります。

> 2
CCIRDjs+BxwVNxMvHzkg
Your answer: BrGkwXmIWrybyQn
actf{one_time_pad_more_like_i_dont_like_crypto-1982309}