Writeup for Crypto Problems in CyBRICS CTF 2019

Zakukozh

Description

题目描述如下图:

意思是说,这是一个被Affine Cipher(仿射密码)加密过的一个图片文件,试着解密。

Analysis

仿射密码是个什么东西? wiki

说白了,就是一个线性变换。

看到只是mod 26,心里一喜,爆破分分钟啊。瞬间又意识到这是个二进制文件,应该不会是mod 26这么简单,估计是mod 256,但这个爆破也分分钟(后面可以看到,其实都不要用1秒)。

题目里面另外一个信息:图片

图片格式也就那么几种,能说的上来的也就png,jpg,… 好吧,说不出来了。

那么。。直接拖进WinHex,再把一个真正的png图片拖进来,对比分析一下:

仿射密码就说明,映射是一一对应的。这可以从上图看出,png里面一样的byte,在映射后的bin中也是一样的!由此推断:是png格式的图片没错了。

开始写脚本喽!

Script

这肯定是mod 256了,有两个未知数a, b,那么就有256*256=65536种可能,爆破起来肯定不要太快。其实,仿射密码里的a是有限制的,要满足gcd(a, 256) == 1,这样还可以减少点计算量。

爆破a, b

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import GCD, inverse

# d^-1(x) = a^-1 (x - b) % 256

pre = [0x89, 0x50, 0x4e]
post = [0x60, 0x09, 0xeb]

for a in range(256):
    if GCD(a,256)!=1:
        continue
    inv_a = inverse(a, 256)
    for b in range(256):
        q = 1
        for i in range(3):
            if (inv_a * (post[i] - b) ) % 256 != pre[i]:
                q=0
                break
        if(q):
            print(a, b)
            # 15, 89

结果瞬间就有了,a = 15, b = 89。那么接下来只需要一个一个解密就行了:

1
2
3
4
5
6
7
8
9
a = 15
inv_a =  239
b = 89
with open("zakukozh.bin", "rb") as f1:
    t = f1.read()
    with open("flag.png", "wb") as f2:
        for c in t:
            p = inv_a * (c - b) % 256
            f2.write(bytes[p])

打开写好的文件,获得flag:

Summary

还是需要再深入了解下图片文件的格式,这样分析起来就更有感觉了。

Fast Crypto

Description

意思就是说,这是一个very modern的加密算法,试着凭借一个secret message来解密这个WAV文件。

Analysis

加密脚本:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import json
from tqdm import tqdm
from egcd import egcd
from pathlib import Path
import sys


def get_next(a, power, N):
    b = a ** power % N
    return b, b % 256


if not Path('public.key').exists():
    print("Key file not found")
    exit(1)


if len(sys.argv) != 3:
    print("Usage: python3 cryptor.py <filename_in> <filename_out>")
    exit(1)


try:
    key = json.loads(Path('public.key').open().read())
    data = Path(sys.argv[1]).open('rb').read()
except Exception as e:
    print("Error during keyfile load: {}".format(e))
    exit(1)
else:
    seed = int(input("Input seed value (int16): "))
    if seed < 0 or seed > 2**16:
        print("Invalid seed. Encryption may be too slow.")
        exit(1)
    power = int(input("Input power value (2-16): "))
    if power < 2 or power > 16:
        print("Invalid power. Encryption may be too slow.")
        exit(1)

    if egcd(power, key['N'])[0] != 1:
        print("Invalid power value")
        exit(1)

    # calculate offset
    for _ in range(key['O']):
        seed = get_next(seed, power, key['N'])[0]

    with Path(sys.argv[2]).open('wb') as w:
        for i in tqdm(range(len(data))):
            seed, bt = get_next(seed, power, key['N'])
            w.write(bytes([data[i] ^ bt]))

分析后得到以下信息:

  • seed: [0, 2**16]
  • power: [2, 16]
  • 先对seed做key['O']=31337幂模运算。
  • 再用seed的低8-bit来和数据异或(也就是相当于一个stream cipher)。

seedpower都是随机的,后面所有东西都是由这两个随机数决定的。

先提取key再说。

N = 73882271767225067628282422302548400069735434660808564149855701357643617388546710750167259617348302921921308565033188464703728096338599435641707966042336489111486646451993143053931136428343207443971020988133537590763029595507074481482058514976650388077801669364711731111970923913958083815347282871017052613916475670517
O = 31337

出于直觉,验证了一下N和O是否为质数。发现O是个质数,但是N不是。

sagefactorN:

都是一些比较小的质数。

想了想从N出发应该如何crack这个加密算法。31337轮幂模后,seed肯定巨大无比,再来取低位做stream cipherkey,这个好像真的crack不了。

一个比较奇怪的地方是,它的那个幂模运算居然是:

1
2
3
def get_next(a, power, N):
    b = a ** power % N
    return b, b % 256

为什么不用python自带的基于快速幂(猜测,但多半就是了)的pow()函数呢?这样先乘方,再取余的算法实在是需要太大的运算量了。

未果,睡了一会儿。


醒来的时候,感觉可以用brute-force,2**16才只是65536,再加上power的15种可能,总共就65536*15=983040种可能,爆破起来肯定很快(后面可以看到,快不快还是要取决于算法的optimization)。

顺着它的思路写脚本:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from tqdm import tqdm

N = 73882271767225067628282422302548400069735434660808564149855701357643617388546710750167259617348302921921308565033188464703728096338599435641707966042336489111486646451993143053931136428343207443971020988133537590763029595507074481482058514976650388077801669364711731111970923913958083815347282871017052613916475670517
O = 31337

raw = [82, 73, 70, 70]
enc = [0x46, 0x83, 0x49, 0x44]

head = []
for i in range(8):
    head.append(raw[i] ^ enc[i])
# head = [20, 202, 15, 2, 239, 26, 199, 210]

# brute-force
for power in range(2, 17):
    print(power)
    for s in tqdm(range(2**16+1)):
        seed = s
        for _ in range(O):
            seed = pow(seed, power, N)
        q = 1
        for i in range(4):
            seed = pow(seed, power, N)
            bt = seed & 255
            if bt != head[i]:
                q = 0
                break
        if(q):
            print(s, power)

说明一下:前面关于raw, enc, head的一段。题目提示加密前的文件格式是.wav,去找了一下wav文件的开头,是以RIFF为开头的前4个byte数据,记为raw;再对加密后文件开头的4个byte(记为enc)分别异或,得到的结果head应当为stream key的前4个byte,以此作为验证的依据。这里4个byte数据已经足够了,因为256^4=4294967296 » 983040=2^16*15。

可是这个脚本跑起来却很慢:

这可能要跑一天才能跑完,开多进程可以快一些,但总的来说,还是要需要小时级别的时间。

思考应当如何优化算法。回过头来看代码时,发现O轮那个循环实在是有点费时间,每次都需要31337次pow(),即使是快速幂也顶不住啊。

O轮pow(),也就是相当于直接幂power**O,可以改写成pow(seed, power**O, N)。但是2**31337已经是个超级无敌变态大的数字了,这里应该还可以再优化一下。

幂模,联想到了欧拉定理pow(a, phi(n), n) = 1。也就是说,那个幂其实是个周期性的东西,pow(a, k*phi(n)+b, n) = pow(a, b, n),可以对幂mod phi(n),结果仍然不变。

再回到这题,前面分析到,N不是一个质数并且能够被轻易地质因数分解。那么,计算phi(N)就是一个很简单的事情了。

有了phi(N),就还能再改写成pow(seed, pow(power, O, phi_N), N),这就快多了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from tqdm import tqdm

N = 73882271767225067628282422302548400069735434660808564149855701357643617388546710750167259617348302921921308565033188464703728096338599435641707966042336489111486646451993143053931136428343207443971020988133537590763029595507074481482058514976650388077801669364711731111970923913958083815347282871017052613916475670517
phi_N = 73518206147262443676837361159127776505334808540008666455558114391523228702493449359589995596913129043911224919282022228135566170964663692657377830877081156633758852294230067854975206472518946297562604445162853306974953289714803969929459936619828333107726452353102277743999390152590440267776000000000000000000000000000
O = 31337

raw = [82, 73, 70, 70]
enc = [0x46, 0x83, 0x49, 0x44]

head = []
for i in range(8):
    head.append(raw[i] ^ enc[i])
# head = [20, 202, 15, 2, 239, 26, 199, 210]

# brute-force
for power in range(2, 17):
    print(power)
    for s in tqdm(range(2**16+1)):
        seed = s
        seed = pow(seed, pow(power, O, phi_N), N)
        q = 1
        for i in range(4):
            seed = pow(seed, power, N)
            bt = seed & 255
            if bt != head[i]:
                q = 0
                break
        if(q):
            print(s, power)

这相比之前,简直就像火箭一样快。修改power的值,手动多进程了一下,很快就跑出来了:

(注意换行那边)

所以seed=4485, power=7

接着就是decode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
from tqdm import tqdm


power = 7
seed = 4485
N = 73882271767225067628282422302548400069735434660808564149855701357643617388546710750167259617348302921921308565033188464703728096338599435641707966042336489111486646451993143053931136428343207443971020988133537590763029595507074481482058514976650388077801669364711731111970923913958083815347282871017052613916475670517
phi_N = 73518206147262443676837361159127776505334808540008666455558114391523228702493449359589995596913129043911224919282022228135566170964663692657377830877081156633758852294230067854975206472518946297562604445162853306974953289714803969929459936619828333107726452353102277743999390152590440267776000000000000000000000000000
O = 31337

seed = pow(seed, pow(power, O, phi_N), N)

with open("enc.wav", "rb") as fin:
    data = fin.read()
    with open("flag.wav", "wb") as fout:
        for i in tqdm(range(len(data))):
            seed = pow(seed, power, N)
            bt = seed & 255
            fout.write(bytes([data[i] ^ bt]))

打开解密后的wav文件,一开始还听不出来,多听了好几遍(吐槽一下这个文本转语音),才听出来The flag is cybrics bracket b l u m underscore b l u m underscore crypto rear bracket,也就是cybrics{blum_blum_crypto}。提交,正确!

Summary

  • 了解到了wav文件的一些基本格式。
  • 学到了一手from tqdm import tqdm,可以进度条显示。
  • 看来,密码题还是需要爆破啊。
  • 学到了一点算法的optimization
  • 听力有待提升。