SJTU-CTF 2019 WriteUp Crypto

BabyLCG

100 pts, 23 solved

Is this LCG secure?

1. 下载 server.py，分析任务流程，注意全程必须在 60 秒内完成（signal.alarm(60)）

server.py

from flag import FLAG
import random
import signal
import hashlib
from Crypto.Util.number import *

class LCGPrng():
    def __init__(self, seed, m, c, p):
        self.state = seed
        self.m = m
        self.c = c
        self.p = p

    def next(self):
        self.state = (self.state * self.m + self.c) % self.p
        return self.state


def proof_of_work():
    prefix = long_to_bytes(random.getrandbits(64))
    print 'prefix = {}'.format(prefix.encode('hex'))
    challenge = raw_input('> ')
    tmp = hashlib.sha256(prefix + challenge).digest()
    if tmp.startswith('\xdd\xdd\xdd'):
        return True
    else:
        return False

def new_lcg():
    p = 0
    m = getPrime(63)
    c = random.randint(2**62,2**63)
    s = random.randint(2**62,2**63)
    while p<m or p<c or p<s:
        p = getPrime(64)
    return LCGPrng(s,m,c,p)

def challenge0():
    print("challenge 0:")
    lcg = new_lcg()
    print(lcg.p)
    print(lcg.m)
    print(lcg.c)
    print(lcg.state)
    for i in range(3):
        res = int(raw_input())
        if res!=lcg.next():
            exit(-1)

def challenge1():
    print("challenge 1:")
    lcg = new_lcg()
    print(lcg.p)
    print(lcg.m)
    print(lcg.state)
    print(lcg.next())
    for i in range(3):
        res = int(raw_input())
        if res!=lcg.next():
            exit(-1)

def challenge2():
    print("challenge 2:")
    lcg = new_lcg()
    print(lcg.p)
    print(lcg.state)
    print(lcg.next())
    print(lcg.next())
    for i in range(3):
        res = int(raw_input())
        if res!=lcg.next():
            exit(-1)

def challenge3():
    print("challenge 3:")
    lcg = new_lcg()
    print(lcg.state)
    print(lcg.next())
    print(lcg.next())
    print(lcg.next())
    print(lcg.next())
    print(lcg.next())
    for i in range(3):
        res = int(raw_input())
        if res!=lcg.next():
            exit(-1)

welcome = """
             _
 _ _ _  ___ | | ___  ___ ._ _ _  ___
| | | |/ ._>| |/ | '/ . \| ' ' |/ ._>
|__/_/ \___.|_|\_|_.\___/|_|_|_|\___.

"""

def main():
    if not proof_of_work():
        exit(-1)
    signal.alarm(60)
    print(welcome)
    print("welcome to LCGLAB")
    challenge0()
    challenge1()
    challenge2()
    challenge3()
    print(FLAG)

if __name__=="__main__":
    main()

1. 首先是 proof_of_work，要求碰撞出开头为 '\xdd\xdd\xdd' 的 sha256 摘要

2. 破解脚本：

import string
import sys
import random
import hashlib
import itertools

prefix = sys.argv[1].decode('hex')
length = 8
for combo in itertools.combinations_with_replacement(string.lowercase + string.digits, length):
    digest = hashlib.sha256(prefix + ''.join(combo)).digest()
    if digest.startswith('\xdd\xdd\xdd'):
        print(''.join(combo))
        break

4. challenge 0: 已知 p, m, c，直接按定义计算即可

5. challenge 1: 已知 p, m 和两个连续随机数，脚本如下：

def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0] * multiplier) % modulus
    return increment

c = crack_unknown_increment([state1, state2], p, m)

6. challenge 2: 已知 p 和三个连续随机数，脚本如下：

def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

m, c = crack_unknown_multiplier(states, p)

其中 modinv 函数定义如下：

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

def modinv(b, n):
    g, x, _ = egcd(b, n)
    if g == 1:
        return x % n
    else:
        raise Exception('No modular inverse')

注：modinv 有时会出现 g = -1 且结果错误的情况，原因未知，但可以多次进行尝试，选择 g = 1 的情况通过测试。

7. challenge 3: p, m, c 全部未知，但已知六个连续随机数，脚本如下：

def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2 * t0 - t1 * t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, modulus)

p, m, c = crack_unknown_modulus(states)

其中 gcd 函数定义如下：

def gcd(a,b):
    if a % b == 0:
        return b
    else :
        return gcd(b, a % b)

8. 经过紧张刺激的复制粘贴后得到 flag: 0ops{LCG_1s_n0o0o0o0o0ot_s4fe}

BabyRSA

100 pts, 24 solved

Can you break the RSA cryptosystem?

1. 下载得到 babyrsa.py 和 enc

babyrsa.py

from flag import FLAG
from Crypto.Util.number import *
import gmpy2
import random

while True:
    p = int(gmpy2.next_prime(random.randint(10**0x1ff, 10**0x200-1)))
    q = int(str(p)[0x100:]+str(p)[:0x100])
    if gmpy2.is_prime(q):
        break
m = bytes_to_long(FLAG)
n = p*q
e = 65537
c = pow(m,e,n)
with open("enc","wb") as f:
    f.write(str(n))
    f.write("\n")
    f.write(str(c))

2. 可以得知，$p$ 是 $[10^{511},10^{512} - 1]$ 的一个质数（512 位），$q$ 是 $p$ 的后 256 位和前 256 位连接而成的一个质数，记 $p$ 的前 256 位为 $a$，后 256 位为 $b$，则：

$$
\begin{align}
p &= 10^{256} \times a + b \\
q &= 10^{256} \times b + a \\
\nonumber n &= pq \\
&= 10^{512} \times ab + 10^{256} (a^2 + b^2) + ab \\
\end{align}
$$

由于 $10^{255} < a, b < 10^{256}$ ，因此 $10^{510} < ab < 10^{512}$，即 $ab$ 为 511 位或 512 位；$a^2 + b^2$ 为 511 或 514 位（可能存在进位）；又由 $n$ 有 1024 位可知 $ab$ 为 512 位 。

观察 $(3)$ 的结构可知：$ab$ 覆盖 $n$ 的第 513~1024 位和第 1~512 位，$a^2 + b^2$ 最多覆盖 $n$ 的第 257~770 位，综合考虑各区间的重合情况，推断出将 $n$ 的前 255 位和后 257 位连接可得到 $ab$，进而计算出 $a^2 + b^2$ 和 $a+b$，最终得到 $a$ 和 $b$ 。

得到 $a$ 和 $b$ 后即可根据标准的 RSA 解密流程进行解密，得到 flag: 0ops{5fd16b247a1690974315f55128769ac64cb4315ef80f018d1d99282a64a719b1}，全部脚本如下：

from math import isqrt
from Crypto.Util.number import *

f = open('enc')
lines = f.readlines()
n = int(lines[0])
c = int(lines[1])
product = int(str(n)[:255] + str(n)[1024-257:]) # a*b
square_sum = (n - 10**512 * product - product) // 10**256
sum = isqrt(square_sum + 2 * product)

delta = sum * sum - 4 * product
delta_root = isqrt(delta)
a = (sum + delta_root) // 2
b = (sum - delta_root) // 2

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b%a,a)
    return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x%m

p = (10 ** 256) * a + b
q = (10 ** 256) * b + a
e = 65537
phi = (p - 1) * (q - 1)
d = modinv(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

BabyBlock

100 pts, 27 solved

Can you break the AES cryptosystem?

1. 下载 babyblock.py：

babyblock.py

#!/usr/bin/env python3
# coding=utf-8

import os
from Crypto.Cipher import AES
from Crypto.Util import Counter

def enc(msg, key):
    ctr = Counter.new(128,  initial_value=sum(msg))
    cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
    return cipher.encrypt(msg)

if __name__ == '__main__':
    key = os.urandom(16)
    with open('flag', 'rb') as f:
        flag = f.read()
    assert len(flag) == 30
    enc_flag = enc(flag, key)

    print("Welcome to the perfect AES encryption system!")
    print(f"Here is your encrypted flag: {enc_flag}")
    for i in range(30):
        try:
            plaintext = input("Please input your plaintext: ")
            plaintext = bytes.fromhex(plaintext)
            ciphertext = enc(plaintext, key)
            print(f"Here is your ciphertext: {ciphertext}")
        except Exception:
            print('Error!')
            break
    print('Bye~')

可以看到使用的是 AES-128-CTR 的加密方式，计数器初始值为明文各字符 ASCII 值之和，整个加密过程使用的密钥相同。由于同密钥且计数器相同时加密过程退化为简单异或运算，因此可以根据 enc_flag ^ flag = enc_msg ^ msg 的关系得到 flag。

2. 要保证每次加密过程的计数器相同首先需要获得 sum(flag)，已知 flag 长度为 30，前缀为 0ops{，可枚举前缀与 flag 相同的字符串 msg，若 sum(msg) == sum(flag)，则计数器相同且密钥相同， flag 密文与 msg 密文的前 5 位相同，由此可得到计数器初值，脚本如下（需安装 pwntools）：

getsum.py

from pwn import *
prefix = b'0ops{'
def solve():
    msg = list(prefix) + [0] * (30 - len(prefix))
    cur = len(prefix)
    cnt = 0
    while cur < 30:
        for i in range(0, 256):
            if cnt % 30 == 0:
                sh = remote(host='host', port='10080')
                print(sh.recvline())
                enc_flag = str(sh.recvline(), encoding='ascii')
                print(enc_flag)
                enc_flag = eval(enc_flag[enc_flag.find('flag: ') + 6:-1])
            msg[cur] = i
            request = bytes(msg).hex()
            print(request)
            sh.sendline(request)
            enc_msg = str(sh.recvline(), 'ascii')
            enc_msg = enc_msg[enc_msg.find('ciphertext: ') + 12:-1]
            enc_msg = eval(enc_msg)
            cnt += 1
            if enc_msg[:5] == enc_flag[:5]:
                print('Matched: ', request)
                print(sum(bytes.fromhex(request)))
                return
        cur += 1
    sh.close()

solve()

暴力破解得到计数器初值为 2740，对应字符串为 306f70737bffffffffffffffffbf00000000000000000000000000000000

3. 由于是简单异或加密，故通过 msg 明文、msg 密文和 flag 的异或运算可得 flag：0ops{Don't_Reu5e_n0nCe_1n_CTR}，脚本如下：

getflag.py

from pwn import *

sh = remote(host='host', port='10080')
print(sh.recvline())
enc_flag = str(sh.recvline(), encoding='ascii')
print(enc_flag)
enc_flag = eval(enc_flag[enc_flag.find('flag: ') + 6:-1])
request = '306f70737bffffffffffffffffbf00000000000000000000000000000000'
msg = bytes.fromhex(request)
sh.sendline(request)
enc_msg = str(sh.recvline(), 'ascii')
enc_msg = enc_msg[enc_msg.find('ciphertext: ') + 12:-1]
enc_msg = eval(enc_msg)

flag = str()
for i in range(30):
    flag += chr((msg[i] ^ enc_msg[i]) ^ enc_flag[i])
print(flag)

Mixed Cipher

200 pts, 19 solved

Can you break the mixed cipher?

1. 下载并解压压缩包，得到两个文件 mc.py 和 output

mc.py

import random
from string import *
from itertools import cycle
from secret import key, message

assert len(key) < 50
assert all(c in (digits + ascii_letters + punctuation + ' \n') for c in key + message)

t = list(ascii_lowercase)
random.shuffle(t)
d = dict(zip(ascii_lowercase, t))
d.update({k.upper(): v.upper() for k, v in d.items()})
mapping = str.maketrans(d)
enc = bytes(ord(x) ^ ord(y) for x, y in zip(message.translate(mapping), cycle(key)))
with open('output', 'wb') as f:
    f.write(enc)

可以得知，key 和 message 仅由字母、数字和标点符号组成

string.punctuation:
由在 C 区域设置中被视为标点符号的 ASCII 字符所组成的字符串: !"#$%&'()*+,-./:;<=>?@[\]^_{|}~

建立了一个小写字母的映射表后对 message 进行简单替换加密，逐字符与 key 异或后写入 output

2. 由于 message 是英文文章，综合加密方式，可先爆破密钥 key 的长度，然后爆破 key。幸运的是，xortool 能够同时完成这两份工作：

4. 可以看到概率最大的密钥长度是 29（尽管概率不算高但相信也无妨），同时 xortool 也给出了可能的密钥列表，不妨打开看看：

5. 看来答案很明显了，key = secret_xor_key_for_u_to_crack，由于异或是可逆运算，因此可以得到简单替换加密后的密文，利用 quipquip 可破解加密：

明文如下：

Hackers solve problems and build things, and they believe in freedom and voluntary mutual help. To be accepted as a hacker, you have to behave as though you have this kind of attitude yourself. And to behave as though you have the attitude, you have to really believe the attitude.
But if you think of cultivating hacker attitudes as just a way to gain acceptance in the culture, you'll miss the point. Becoming the kind of person who believes these things is important for you - for helping you learn and keeping you motivated. As with all creative arts, the most effective way to become a master is to imitate the mind-set of masters - not just intellectually but emotionally as well.
Or, as the following modern Zen poem has it:
To follow the path:
look to the master,
follow the master,
walk with the master,
see through the master,
become the master.
So, if you want to be a hacker, repeat the following things until you believe them:
1. The world is full of fascinating problems waiting to be solved.
Being a hacker is lots of fun, but it's a kind of fun that takes lots of effort. The effort takes motivation. Successful athletes get their motivation from a kind of physical delight in making their bodies perform, in pushing themselves past their own physical limits. Similarly, to be a hacker you have to get a basic thrill from solving problems, sharpening your skills, and exercising your intelligence.
If you aren't the kind of person that feels this way naturally, you'll need to become one in order to make it as a hacker. Otherwise you'll find your hacking energy is sapped by distractions like sex, money, and social approval.
(You also have to develop a kind of faith in your own learning capacity - a belief that even though you may not know all of what you need to solve a problem, if you tackle just a piece of it and learn from that, you'll learn enough to solve the next piece - and so on, until you're done.)
2. No problem should ever have to be solved twice.
Creative brains are a valuable, limited resource. They shouldn't be wasted on re-inventing the wheel when there are so many fascinating new problems waiting out there.
To behave like a hacker, you have to believe that the thinking time of other hackers is precious - so much so that it's almost a moral duty for you to share information, solve problems and then give the solutions away just so other hackers can solve new problems instead of having to perpetually re-address old ones.
Note, however, that "No problem should ever have to be solved twice." does not imply that you have to consider all existing solutions sacred, or that there is only one right solution to any given problem. Often, we learn a lot about the problem that we didn't know before by studying the first cut at a solution. It's OK, and often necessary, to decide that we can do better. What's not OK is artificial technical, legal, or institutional barriers (like closed-source code) that prevent a good solution from being re-used and force people to re-invent wheels.
(You don't have to believe that you're obligated to give all your creative product away, though the hackers that do are the ones that get most respect from other hackers. It's consistent with hacker values to sell enough of it to keep you in food and rent and computers. It's fine to use your hacking skills to support a family or even get rich, as long as you don't forget your loyalty to your art and your fellow hackers while doing it.)
3. Boredom and drudgery are evil.
Hackers (and creative people in general) should never be bored or have to drudge at stupid repetitive work, because when this happens it means they aren't doing what only they can do - solve new problems. This wastefulness hurts everybody. Therefore boredom and drudgery are not just unpleasant but actually evil.
To behave like a hacker, you have to believe this enough to want to automate away the boring bits as much as possible, not just for yourself but for everybody else (especially other hackers).
(There is one apparent exception to this. Hackers will sometimes do things that may seem repetitive or boring to an observer as a mind-clearing exercise, or in order to acquire a skill or have some particular kind of experience you can't have otherwise. But this is by choice - nobody who can think should ever be forced into a situation that bores them.)
4. Freedom is good.
Hackers are naturally anti-authoritarian. Anyone who can give you orders can stop you from solving whatever problem you're being fascinated by - and, given the way authoritarian minds work, will generally find some appallingly stupid reason to do so. So the authoritarian attitude has to be fought wherever you find it, lest it smother you and other hackers.
(This isn't the same as fighting all authority. Children need to be guided and criminals restrained. A hacker may agree to accept some kinds of authority in order to get something he wants more than the time he spends following orders. But that's a limited, conscious bargain; the kind of personal surrender authoritarians want is not on offer.)
Authoritarians thrive on censorship and secrecy. And they distrust voluntary cooperation and information-sharing - they only like 'cooperation' that they control. So to behave like a hacker, you have to develop an instinctive hostility to censorship, secrecy, and the use of force or deception to compel responsible adults. And you have to be willing to act on that belief.
5. Attitude is no substitute for competence.
To be a hacker, you have to develop some of these attitudes. But copping an attitude alone won't make you a hacker, any more than it will make you a champion athlete or a rock star. Becoming a hacker will take intelligence, practice, dedication, and hard work.
Therefore, you have to learn to distrust attitude and respect competence of every kind. Hackers won't let posers waste their time, but they worship competence - especially competence at hacking, but competence at anything is valued. Competence at demanding skills that few can master is especially good, and competence at demanding skills that involve mental acuteness, craft, and concentration is best.
If you revere competence, you'll enjoy developing it in yourself - the hard work and dedication will become a kind of intense play rather than drudgery. That attitude is vital to becoming a hacker.
6. The flag is 0ops{H4ck_th3_M1xed_C1pher_16afb28ced}.

flag: 0ops{H4ck_th3_M1xed_C1pher_16afb28ced}

LFSR

200 pts, 11 solved

Do you know lfsr?

Introduction

反馈移位寄存器（FSR, Feedback Shift Register），是指将前一输出序列作为反馈函数的参数，再将反馈函数的输出再用作输入的 移位寄存器；而 LFSR (线性反馈移位寄存器，Linear Feedback Shift Register)，顾名思义，就是反馈函数为线性函数的 FSR，可用于生成伪随机数。

寄存器的初值称为“种子”，每个输出序列含有的元素个数称为 FSR 的“级数”，一般地，一个 n 级反馈移位寄存器如下图所示（图源）

影响下一状态的比特位称为 tap ，tap 的设定表示为 LFSR 的特征多项式，其中所有项的系数都必须为 0 或 1。例如，当 tap 的位置在第 0，4，5，6 个比特位（从左向右），n = 8 时，特征多项式为：

$$ 1+x^4+x^5+x^6 $$

Berlekamp-Massey Algorithm

Berlekamp-Massey 算法（B-M 算法）用于构造一个最短的 LFSR 以满足给定的二进制输出序列。一方面可用于寻找级数尽可能小的 LFSR 来生成随机性大的输出序列，而另一方面可用于根据已知输出序列反推 LFSR。

Solution

1. 下载给定的压缩包并解压，得到两个文件 chall.py 和 enc：

chall.py

from secret import KEY,MASK

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask
        i = self.init & self.mask & self.lengthmask
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output

LENGTH = 64
assert(KEY.bit_length()==LENGTH)
assert(MASK.bit_length()==LENGTH)
l = lfsr(KEY,MASK,LENGTH)

#file getflag
#getflag: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/l, for GNU/Linux 2.6.32, BuildID[sha1]=0fa1c13a2d36aa4d3c03504f473af5685807a786, not stripped

with open("getflag","rb") as f:
    data = f.read()

with open("enc","wb") as f:
    for d in data:
        t = ord(d)
        m = 0
        for i in range(7,-1,-1):
            tmp = (t&(1<<i))>>i
            tmp ^= l.next()
            m += (tmp<<i)
        f.write(chr(m))

2. 可以看到这是一个 64 级的 LFSR，且初始状态（KEY）和特征多项式（由 MASK 决定）都未知，利用这个 LFSR 对 getflag 文件进行异或加密后写入 enc，目标是还原 KEY 和 MASK，进而还原 LFSR，最后解密得到 getflag

3. 首先的突破口在于题目给出了 getflag 为 64 位的 ELF 文件，由于 ELF 文件的前 128 位由文件属性决定，因此可以得知 getflag 的前 128 位明文：

7F 45 4C 46 02 01 01 00 00 00 00 00 00 00 00 00

4. 再看加密过程，for d in data 中的 d 是读入的一个 ASCII 字符，内层循环周期为 8，i 从 7 递减到 0，第一行 t&(1<<i)>>i 取到 t 的第 i 位（从二进制低位数起），与 LSFR 的下一个输出进行异或运算后移位到原来的位置累加到 m。

   简而言之，d 是 ASCII 字符，t 的二进制有 8 位，取 LFSR 连续的 8 个输出组成一个 8 位二进制数，如 1 0 1 0 1 1 1 1 组成 10101111，将其与 t 按位异或得到 m，将 m 对应的 ASCII 字符写入 enc。

5. 因此，将已知的 getflag 前 128 位，与 enc 的前 128 位异或，可得到 LFSR 的前 128 位输出：

E7 37 65 9A 94 5C 9D 55 16 2F 2F 2A A5 9E 3A 8E

6. 已知前 128 位输出，即 2*n 的输出序列，就可利用 B-M 算法反推特征多项式（MASK），利用在线工具或将源码下载到本地运行（bma.py）:

得到特征多项式：
$$
\begin{split}
\begin{align}
&x^{64} + x^{63} + x^{62} + x^{59} + x^{56} + \\
&x^{55} + x^{54} + x^{47} + x^{46} + x^{44} + \\
&x^{43} + x^{41} + x^{39} + x^{38} + x^{37} + \\
&x^{35} + x^{34} + x^{29} + x^{27} + x^{26} + \\
&x^{24} + x^{23} + x^{21} + x^{20} + x^{19} + \\
&x^{18} + x^{17} + x^{16} + x^{14} + x^{12} + \\
&x^3 + x^2 + x^1 + 1
\end{align}
\end{split}
$$

7. 将特征多项式翻译为 MASK，即

MASK = 0b1111000000001010111111011011010000110111010110110000001110010011

特征多项式中每一项的指数（除 $x^{64}$ 外）代表一个 tap 的位置，系数为该比特位的值（0 或 1），注意是从左到右数（即从高位向低位），如 $x^2$ 表示 MASK 从高位起的第 3 个比特为 1。

8. 接下来需要根据 MASK 和已知输出序列还原初始状态（KEY）。根据 LFSR 的性质，每一个输出由输出序列的前 64 个值决定，也就是说第 64 个输出由初始状态的第 1 位（从低位起），以及已知的第 1~63 个输出决定。因此，可以利用前 63 个输出和第 64 个输出得到 KEY 的第 1 位；用 KEY 的第 1 位+前 62 个输出和第 63 个输出得到 KEY 的第 2 位，依此类推可以还原出 KEY，脚本如下：

getkey.py

data = '11100111001101110110010110011010100101000101110010011101010101010001011000101111001011110010101010100101100111100011101010001110'
LEN = 64
LMASK = 2**(LEN+1) - 1
MASK = 0b1111000000001010111111011011010000110111010110110000001110010011
key = 0b0
init = int(data[:LEN-1], 2)

for n in range(0, LEN): # calculate the nth bit of key
    i = init & MASK & LMASK
    output = 0
    for j in range(LEN-1):
        output ^= (i & 1)
        i = i >> 1
    bit = int(data[LEN-n-1]) ^ output
    key |= bit << n
    init = (init >> 1) | (bit << (LEN-2)) # update output sequence

print(bin(key))

得到 KEY：

KEY = 0b1001110001100010110101110100011110001111011010001011001010110011

9. 最后根据加密过程编写解密脚本：

dec.py

import struct

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask
        i = self.init & self.mask & self.lengthmask
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output

MASK = 0b1111000000001010111111011011010000110111010110110000001110010011
KEY = 0b1001110001100010110101110100011110001111011010001011001010110011
LENGTH = 64
l = lfsr(KEY, MASK, LENGTH)

with open('enc', 'rb') as f:
    data = f.read()

with open('getflag', 'wb') as f:
    for ch in data:
        tmp = 0
        for i in range(7, -1, -1):
            tmp += l.next() << i
        t = ch ^ tmp
        f.write(struct.pack('B', t))

注：脚本使用 Python 3.8 编写，Python 2 的二进制文件 I/O 实现方式有所不同

10. Linux 环境下运行 getflag 即可得到 flag: 0ops{B3rlek4mp_Mas5ey_4lg0r1thm}

CRC Forgery

200 pts, 13 solved

Can you forge CRC?

crc.py

#!/usr/bin/env python3
# coding=utf-8

import binascii
import os
import random

def b2n(b):
    res = 0
    for i in b:
        res *= 2
        res += i
    return res

def n2b(n, length):
    tmp = bin(n)[2:]
    tmp = '0'*(length-len(tmp)) + tmp
    return [int(i) for i in tmp]

def s2n(s):
    return int(binascii.hexlify(s), 16)

def crc64(msg):
    msg = n2b(s2n(msg), len(msg)*8)
    msg += const
    for shift in range(len(msg)-64):
        if msg[shift]:
            for i in range(65):
                msg[shift+i] ^= poly[i]
    res = msg[-64:]
    return b2n(res)

const = n2b(0xdeadbeeffeedcafe, 64)
poly  = n2b(0x10000000247f43cb7, 65)

if __name__ == '__main__':
    # with open('/home/ctf/flag', 'r') as f:
    with open('/home/ctf/flag', 'r') as f:
        flag = f.read()

    try:
        print("Welcome to the CRC Forgery Challenge!")
        raw = os.urandom(256)
        pos = random.randint(0, 248)
        raw_hex = bytearray(binascii.hexlify(raw))
        for i in range(8):
            raw_hex[(pos+i)*2] = ord('_')
            raw_hex[(pos+i)*2+1] = ord('_')
        raw_hex = bytes(raw_hex)
        print(f"Here is the message: {raw_hex.decode('ascii')}")
        ans = input("Please fill the blank: ")
        ans = bytes.fromhex(ans)
        assert len(ans) == 8

        raw = bytearray(raw)
        for i in range(8):
            raw[pos+i] = ans[i]
        raw = bytes(raw)
        if crc64(raw) == 0x1337733173311337:
            print(f"Great! Here is your flag: {flag}")
        else:
            print(f"Wrong! Bye~")
    except Exception:
        print("Error!")

Analysis

b2n 将二进制列表转换为整数，n2b 将整数转换为二进制列表并在高位补 0 以达到给定长度，s2n 将字符串通过十六进制表示转换为整数。

const 和 poly 分别是长度为 64 和 65 的二进制列表，crc64 函数先将 msg 转换为二进制表示，并在末尾加上 const，遍历 msg 主要部分的每一位，如果该位为 1，则从该位起将接下来的 65 位与 poly 异或。

msg 长度为 256 字节，随机选取 0~248 字节中的一位，从这一位开始删去连续的 8 字节，要求补全这 8 个字节，使得 msg 的 CRC64 为特定值。

e.g.:

Welcome to the CRC Forgery Challenge!
Here is the message: d57e039b24d034________________d5c8d3d0f5685183d316865bfb6cbaa8c67f731fe654c77edd30defd25389ae5490bbc379d559d19c487b09ffa9cda850fa29e489de7955b2e90403cc40d1857385c2c084fdceaa912c5d72c63dddf28eb0ce7dced219432333bebc5f9904f16c5fe2659382f19a4c656cd10ef0e7a031afc0e39e6ff51333aea7f2f15452859314f9972ebc3a0d7f7ec389561d7e6a2a2773fd900b41023290c81ea2b7ee760db528b2fa374922b541f38a0038170d8ef26a3e7d75825513f8fc4f8846f08dc40ba6ab219c6dfc77fcae080b66d753d72b91ad0b44e188e23371a5c04892426490daaf9fc8a7db4de54b87c57be6518d6
Please fill the blank:

将 msg 分为横线前后两段，在第一段后补 8 个字节的 0，由于第一段明文已知，故可计算出在循环到横线前一位时，横线部分受到的影响 x ，即 0 ^ x = x = before；对于第二段，在末尾补上目标的 CRC 值，倒推可得到横线处应填内容受到 x 影响后的值 after，即 blank ^ x = after，则根据 blank = before ^ after 可得到答案。

Solution

solve.py

# coding=utf-8

import binascii
import os
import random

def b2n(b):
    res = 0
    for i in b:
        res *= 2
        res += i
    return res

def n2b(n, length):
    tmp = bin(n)[2:]
    tmp = '0'*(length-len(tmp)) + tmp
    return [int(i) for i in tmp]

def s2n(s):
    return int(binascii.hexlify(s), 16)

def crc64(msg, const):
    msg = n2b(s2n(msg), len(msg)*8)
    msg += const
    for shift in range(len(msg)-64):
        if msg[shift]:
            for i in range(65):
                msg[shift+i] ^= poly[i]
    res = msg[-64:]
    return b2n(res)

const = n2b(0xdeadbeeffeedcafe, 64)
poly  = n2b(0x10000000247f43cb7, 65)
crc = n2b(0x1337733173311337, 64)

msg1 = input()
msg1 = bytes.fromhex(msg1)
msg2 = input()
msg2 = bytes.fromhex(msg2)
before = crc64(msg1, [0] * 64)
msg2 = n2b(s2n(msg2), len(msg2) * 8) + const
reverse = n2b(0, len(msg2)) + crc

for shift in range(len(msg2) - 1, -1, -1):
    if msg2[shift] != reverse[shift + 64]:
        for i in range(65):
            reverse[shift + i] ^= poly[i]

after = b2n(reverse[:64])
print(hex(before ^ after)[2:])

脚本直接利用原有 crc64 函数计算得到 before，reverse 为 64 位的 0 （倒推后得到 after） + msg 的第二段明文 msg2 + 目标 CRC 值。运行脚本，分别输入 msg 的两段明文，得到结果为 2b193b04d145dd5d，flag: 0ops{CRC_i5_m0d_In_FiNite_fie1d}

官方解析：

这里的 CRC64 本质上是求一个大数在 $GF(2^{64})$ 下对应的值，只需在有限域下进行一次减法和一次除法即可；输入值和 CRC 值也存在线性关系，也可通过求解线性方程组解决。

References

1. 攻击线性同余生成器(LCG)
2. Linear Feedback Shift Register - CTF Wiki
3. Linear-feedback shift register - Wikipedia