35c3CTF Crypto Writeup
35c3CTF Crypto writeup
c3系列CTF题目质量还是很高的。这次比赛有两道Crypto，都属于中等难度。下面是我的Writeup。其中第二道的思路参考了https://sectt.github.io/writeups/35C3CTF/crypto_postquantum/README
unofficial
题目描述
The NSA gave us these packets, they said it should be just enough to break this crypto.
Difficulty estimate: medium
题目分析
题目给了两个文件 server.py 和surveillance.pcap
打开server.py发现代码并不复杂。首先看一下加密用的密钥的生成过程：
def keygen():
return [rand() for _ in range(N)]会随机生成４０个数字，其中随机的具体过程如下：
def rand():
return int.from_bytes(os.urandom(bits // 8), 'little')可以看到是调用的操作系统的urandom，而不是python 自己的伪随机函数,因此无法预测出随机数。即密钥是40个无法预测的随机数。
接着分析加密过程：
import os, math, sys, binascii
from secrets import key, flag
from hashlib import sha256
from Crypto.Cipher import AES
p = 21652247421304131782679331804390761485569
bits = 128
N = 40
if __name__ == '__main__':
# key = keygen() # generated once & stored in secrets.py
challenge = keygen()
print(' '.join(map(str, challenge)))
response = int(input())
if response != sum(x*y%p for x, y in zip(challenge, key)):
print('ACCESS DENIED')
exit(1)
print('ACCESS GRANTED')
cipher = AES.new(
sha256(' '.join(map(str, key)).encode('utf-8')).digest(),
AES.MODE_CFB,
b'\0'*16)
print(binascii.hexlify(cipher.encrypt(flag)).decode('utf-8'))题目告诉我们，key只随机生成一次，除了key以外，还会调用keygen生成４０个随机数作为challenge,challenge每次都是不同的。初始化完成之后，会把生成的challenge打印给用户，之后会接受用户输入。用户的输入要满足一定的条件才能继续,否则显示ACCESS DENIED。如图所示：
继续分析用户输入需要满足的条件：
response ＝＝ sum(x*y%p for x, y in zip(challenge, key))等式的右边是让key 和 challenge中对应的数字两两相乘并求和，即
如果满足条件，服务器会用对key字符串进行sha256签名的结果作为AES密钥，对flag进行加密，并返回密文。由于key保持不变，所以每次返回的密文其实都是一样的。如果我们想要对密文进行解密就必须要恢复key。
分析完脚本，我们再分析题目给的流量包。用wireshark打开流量包，发现流量包记录了40次客户端与服务端的交互数据。第一次的交互数据如图所示：
一开始是服务端发送的40个随机数，然后客户端发送了response(图中红色部分)，response满足条件，服务端打印了ACCESS GRANTED 和加密后的密文aef8c15e422dfb8443fc94aa9b5234383d8ee523d6da9c4875ccf0d2cf24b1c3fa234e90b9f9757862d242063dbd694806bc54582deddbcbcc。观察后面的流量，发现确实每次返回的密文都相同。检查流量中的40次交互过程，发现其中39次都成功，但有一次失败。失败的如下图所示：
解题思路
总结一下题目的已知条件
- 我们有AES加密的密文
- 要解密密文必须恢复
key，key是40个随机整数 key是随机生成的，并且使用的是系统随机数，而不是伪随机算法- 我们可以从流量中提取出39个关于
key的等式，其中只有key是未知的，challenge和response都是可以从流量中获得的。
这样我们可以把求解key的问题转换为线性代数问题。key为40个未知数 x1 ... x40。每个等式都是关于ｘi的方程。
这39个等式构成一个40元一次线性方程组，对该方程组求解即可得到key。用矩阵表示这个乘法为
常识上说，要解40元一次线性方程组必须要有40个等式，我们只有39个等式，无法求解。但只要有一些线性代数知识就可以知道，非齐次线性方程组的解的情况其实是和矩阵Challenge的秩有关。等式的数量少于未知数的数量有可能无解也有可能有无数个解。我们可以用sagemath对该非齐次线性方程组求解，可求得一个特解。经尝试，该特解恰好就是key,可以直接解出密文。
解题脚本
from sage.all import *
p = 21652247421304131782679331804390761485569
I = Integers(p)
CHM = Matrix(I,CH)
AWM = vector(I,AW)
KM=CHM.solve_right(AWM)
from Crypto.Cipher import AES
from hashlib import sha256
key=list(KM)
print len(key)
print ' '.join(map(str, key)).encode('utf-8')
cipher = AES.new(sha256(' '.join(map(str, key)).encode('utf-8')).digest(),AES.MODE_CFB,b'\0'*16)
c = "aef8c15e422dfb8443fc94aa9b5234383d8ee523d6da9c4875ccf0d2cf24b1c3fa234e90b9f9757862d242063dbd694806bc54582deddbcbcc"
c=c.decode("hex")
print repr(c)
print cipher.decrypt(c)flag 35C3_as_an_att4ck3r_I_am_b1as3d_t0wards_b1ased_r4nd0mness
post quantum
题目描述
Somebody asked for more crypto challenges, so we made one in the middle of the night. Now you better solve it.
题目分析
题目给了两个脚本challenge.py generate.py和一个文件夹data
先看一下generate.py
from challenge import CodeBasedEncryptionScheme
from random import SystemRandom
from os import urandom
if __name__ == "__main__":
cipher = CodeBasedEncryptionScheme.new()
random = SystemRandom()
for i in range(1024 + 512):
pt = urandom(2)
ct = cipher.encrypt(pt)
with open("plaintext_{:03d}".format(i), "wb") as f:
f.write(pt)
with open("ciphertext_{:03d}".format(i), "wb") as f:
f.write(ct)
assert(pt == cipher.decrypt(ct))
with open("flag.txt", "rb") as f:
flag = f.read().strip()
if len(flag) % 2 != 0:
flag += b"\0"
cts = list()
for i in range(len(flag) // 2):
cts.append(cipher.encrypt(flag[i*2:i*2 + 2]))
for i, ct in enumerate(cts):
with open("flag_{:02d}".format(i), "wb") as f:
f.write(ct)引入了出题人的加密系统CodeBasedEncryptionScheme,观察其加密过程，发现其一次加密２个字节。首先先加密了1024+512=1536组随机内容，并且加明文和对应的密文都给了我们。最后再２字节２字节的加密flag。揣摩出题人的意图，猜测应该是希望我们根据题目所给的1536组明密文对，恢复出密钥，然后再进行解密。
可以看看所给的明密文对。明文为２字节，密文长0x126字节
接着分析具体的加密过程。先看密钥的生成：
bitlength=48
def keygen(cls, bitlength):
key = SystemRandom().getrandbits(bitlength)
key = BitVector(size=bitlength, intVal = key)
return key密钥为随机生成的48bit,并构成一个向量。继续分析加密过程，在加密之前，会对输入的内容做一个编码：
def add_encoding(self, message):
message = int.from_bytes(message, 'big')
message = BitVector(size=self.key_length // 3, intVal=message)
out = BitVector(size=self.key_length)
for i, b in enumerate(message):
out[i*3 + 0] = b
out[i*3 + 1] = b
out[i*3 + 2] = b
return out该编码过程会把输入的２个字节先转换为长为16的比特向量，随后会将这个向量复制２次，构成一个与key等长的长为48的比特向量。比如输入的message为b"AC",得到的编码结果为000111000000000000000111000111000000000000111111之后才会真正进行加密。
def encrypt(self, message):
message = self.add_encoding(message)
columns = [
BitVector(
size=self.key_length,
intVal=self.random.getrandbits(self.key_length)
)
for _ in range(self.key_length)
]
# compute the noiseless mask
y = matrix_vector_multiply(columns, self.key)
# mask the message
y ^= message
# add noise: make a third of all equations false
for i in range(self.key_length // 3):
noise_index = self.random.randrange(inverse_error_probability)
y[i * 3 + noise_index] ^= 1
columns = [bitvector_to_bytes(c) for c in columns]
columns = b"".join(columns)
return columns + bitvector_to_bytes(y)首先，会随机生成48个长为48比特的向量，构成矩阵columns，随后该矩阵与Key向量相乘再异或编码后的message向量。用公式描述如下：
运算完成后还会有一个add noise的过程，简单来说就是对于Y，每3个比特中就会有一个比特被随机翻转，生成Y'。最后会将比特序列columns | Y'转换为字节输出。密文输出的长度为(48*48+48)/8=294=0x126个字节。
同时出题人还给出了解密脚本，其基本原理为，已知columns和key，可以有:
生成的X'中，每三个比特会有１个比特的噪音，可以从３个比特中挑选出相同的两个来去除噪音，最后获得X即明文。
解题思路
总结一下题目的已知条件
- 我们有flag加密后的密文
- 我们有解密算法，需要恢复key
- 我们有若干组明密文对
- 如果没有噪音，给我们一组明密文对
M,C,w我们有如下等式
根据数学运算性质，我们有
也就是说，如果没有噪音，我们可以很方便的恢复key。那我们该如何去除噪音呢？
一个简单的思路是加密一次共引入16个噪音，每个噪音有３个可能位置，一共有3^16^种情况。可以通过穷举来去除噪音，对恢复Key。对于每一个恢复出的key，可以用其解密后续的密文，并与对应的明文比较，来判断key是否恢复正确，需要注意的是对于一组明密文对，可能有多个满足条件的key，导致多解的出现，因此可以多挑选几组明密文对来进行检查。此外，因为爆破量较大，因此用c实现。具体思路如下:
- 选取某一个明密文对C,M,Cols (脚本是选的flag的开头两个字母'35'及其对应的密文)
- 穷举3^16^种噪音，从中挑选出一个噪音E
- 用噪音E对C进行去噪得到Y
- 用Y,M,Cols 根据公式可以恢复出Key，其中求逆矩阵通过sage完成
- 选取若干组明密文对（脚本选取了２组）
- 用恢复的Key解密这些密文，并把解密结果与明文比较
- 如果结果与明文存在不匹配，则恢复错误，回到第２步
- 如果匹配则用Key对完整的flag进行解密
- 对于所有解密出的flag，人工判断是否是正确解
我的脚本选取了２组明密文对对Key进行检查，运行10分钟遍历了所有的情况。最后只得到了一个解,并且这个解的确解出了正确的flag。我的脚本如下，其中部分基础函数来自于https://sectt.github.io/writeups/35C3CTF/crypto_postquantum/solve.c
解题脚本
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
void print_array(int *mask, int len) {
for (int i = 0; i < len; i++) {
printf("%d, ", mask[i]);
}
puts("");
}
int cols0[48][48] = {
{0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0,
1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0},
{1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0,
0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1,
1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0},
{0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,
1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1},
{0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1,
0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1},
{0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1,
1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1,
0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0},
{0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1,
1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0},
{1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1,
1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1,
1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1},
{1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0},
{0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0,
0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0},
{1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0,
1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0},
{1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0,
1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1},
{0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0,
1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0},
{1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1,
1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1},
{0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,
1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0},
{0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0,
0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1},
{1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1,
1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0},
{0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1,
0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0,
1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1},
{1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1,
0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1,
1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0},
{1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0,
1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0},
{1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0,
0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0},
{1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0,
0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1,
1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1,
1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0,
0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1,
0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0},
{0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0,
0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1},
{0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0,
1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0},
{1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0,
0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1},
{1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1,
0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0},
{0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0,
1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0},
{1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1,
0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1,
1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1},
{1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0,
0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0},
{1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1},
{0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1,
1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1},
{1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1,
0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1},
{0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1,
0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1},
{1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0,
0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0,
0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0}};
int cols0Inv[48][48] = {
{1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0},
{1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0,
0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0},
{0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1,
0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1},
{1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1,
0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1},
{0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0,
0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1},
{0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0,
1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0,
1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1,
1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0},
{1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0},
{0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0,
0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0},
{1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1,
0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1},
{1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0,
1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0,
1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0},
{1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0,
0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0,
1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1,
0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0},
{0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1},
{0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1,
1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1,
1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1},
{1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1},
{1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0,
0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1},
{1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1,
1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0,
1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1},
{1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0,
0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1},
{1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0},
{0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1},
{0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1,
1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1},
{1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1,
1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1},
{1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0,
0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1},
{0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1},
{0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1,
0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1},
{1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0},
{1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1,
0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1},
{1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0,
0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1},
{1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1,
0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1},
{0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0,
1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1},
{1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0,
1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1},
{1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1,
0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1},
{1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0,
1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0},
{1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0,
1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0},
{1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1,
1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0,
1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1},
{1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1,
0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1},
{1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1,
0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1}};
int flag0xorflagcipher0[48] = {1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1,
1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1,
1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0};
int *matrix_vector_multiply(int a[48][48], int v[48]) {
int sz = 48;
int *res = calloc(sz, sizeof(int));
for (int i = 0; i < sz; i++) {
for (int j = 0; j < sz; j++) {
res[i] ^= a[j][i] * v[j];
}
}
return res;
}
int *bytes_to_bits(char *message, int sz) {
int *res = calloc(sz * 8, sizeof(int));
for (int i = 0; i < sz; i++) {
for (int j = 0; j < 8; j++) {
res[(i * 8) + j] = (message[i] >> (7 - j)) & 0x1;
}
}
return res;
}
char *bits_to_bytes(int *message, int sz) {
char *res = calloc(sz / 8, 1);
for (int i = 0; i < sz; i += 8) {
for (int j = 0; j < 8; j++) {
res[i / 8] |= ((message[i + j] << (7 - j)));
}
}
return res;
}
char *decode(int *message) {
int *out = malloc((48 / 3) * sizeof(int));
int decoded_bit;
for (int i = 0; i < 48 / 3; i++) {
if (message[i * 3] == message[i * 3 + 1])
decoded_bit = message[i * 3];
else if (message[i * 3] == message[i * 3 + 2])
decoded_bit = message[i * 3];
else if (message[i * 3 + 1] == message[i * 3 + 2])
decoded_bit = message[i * 3 + 1];
else
assert(0);
out[i] = decoded_bit;
}
char *res = bits_to_bytes(out, 48 / 3);
free(out);
return res;
}
void hex(char *s, int len) {
for (int i = 0; i < len; i++) {
printf("%02hhx", s[i]);
}
puts("");
}
int* readCipher(int colls[48][48],const char* filename){
FILE *fp;
int* y;
char buffer[294 - 6];
char y_buf[6];
fp = fopen(filename, "rb");
for (int j = 0; j < 294 - 6; j += 6) {
char b[6];
fread(b, 6, 1, fp);
int *cb = bytes_to_bits(b, 6);
memcpy(colls[j / 6], cb, 48 * sizeof(int));
free(cb);
}
fread(y_buf, sizeof(y_buf), 1, fp);
y = bytes_to_bits(y_buf, sizeof(y_buf));
fclose(fp);
return y;
}
char* decrypt(int key[48],int* y,int colls[48][48]) {
int *aux = matrix_vector_multiply(colls, key);
int m_xor_e[48];
for (int i = 0; i < 48; i++) {
m_xor_e[i] = y[i] ^ aux[i];
}
char *m = decode(m_xor_e);
free(aux);
return m;
}
void decryptflag(int key[48]) {
FILE *fp;
char filename[64];
char buffer[294 - 6];
char y_buf[6];
int colls[48][48];
for (int i = 0; i < 31; i++) {
sprintf(filename, "./data/flag_%02d", i);
fp = fopen(filename, "rb");
for (int j = 0; j < 294 - 6; j += 6) {
char b[6];
fread(b, 6, 1, fp);
int *cb = bytes_to_bits(b, 6);
memcpy(colls[j / 6], cb, 48 * sizeof(int));
free(cb);
}
fread(y_buf, sizeof(y_buf), 1, fp);
int *y;
y = bytes_to_bits(y_buf, sizeof(y_buf));
int *aux = matrix_vector_multiply(colls, key);
int m_xor_e[48];
for (int i = 0; i < 48; i++) {
m_xor_e[i] = y[i] ^ aux[i];
}
char *m = decode(m_xor_e);
// hex(m, 2);
printf("%s", m);
free(aux);
free(y);
fclose(fp);
}
puts("");
}
int* y_1;
int colls1[48][48];
int* y_2;
int colls2[48][48];
int check(int* key){
//only read once
if(!y_1){
y_1 = readCipher(colls1,"./data/ciphertext_001");
y_2 = readCipher(colls2,"./data/ciphertext_000");
}
char* result = decrypt(key,y_1,colls1);
if (result[0] == (char)0x62 && result[1] == (char)0xd4) {
result = decrypt(key,y_2,colls2);
if(result[0]==(char)0x16 && result[1]==(char)0xdb){
free(result);
return 1;
}
}
free(result);
return 0;
}
int* recover_key(int mask[48]) {
int key_start[48];
for (int i = 0; i < 48; i++) {
key_start[i] = flag0xorflagcipher0[i] ^ mask[i];
}
int *key = matrix_vector_multiply(cols0Inv, key_start);
return key;
}
int main() {
unsigned long total=pow(3,16);
int mask[48];
unsigned long i = 0;
for(;i<total;i++){
if(i%400000 ==0){
printf("%ld\n",i);
}
//clear mask
for(int tmp=0;tmp<48;tmp++){
mask[tmp]=0;
}
//set mask
int num=i;
for(int tmp=0;tmp<16;tmp++){
mask[tmp*3+num%3]=1;
num=num/3;
}
int* key=recover_key(mask);
if(check(key)){
decryptflag(key);
}
free(key);
}
}flag 35C3_let's_hope_these_Q_computers_will_wait_until_we're_ready