Soreat_u's Blog

Writeup for Crypto Problems in CyBRICS CTF 2019

 Writeup

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）。

seed和power都是随机的，后面所有东西都是由这两个随机数决定的。

先提取key再说。

N = 73882271767225067628282422302548400069735434660808564149855701357643617388546710750167259617348302921921308565033188464703728096338599435641707966042336489111486646451993143053931136428343207443971020988133537590763029595507074481482058514976650388077801669364711731111970923913958083815347282871017052613916475670517
O = 31337

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

用sage来factorN:

都是一些比较小的质数。

想了想从N出发应该如何crack这个加密算法。31337轮幂模后，seed肯定巨大无比，再来取低位做stream cipher的key，这个好像真的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。
  • 听力有待提升。