0%

2017年全国大学生信息安全竞赛Crypto(未更新完)

发表于 更新于

传感器1
传感器2
Classical

传感器1

已知ID为0x8893CA58的温度传感器的未解码报文为：3EAAAAA56A69AA55A95995A569AA95565556
此时有另一个相同型号的传感器，其未解码报文为： 3EAAAAA56A69AA556A965A5999596AA95656
请解出其ID，提交flag{hex（不含0x）}

看报文格式像差分曼切斯特编码，转换成二进制

1
2
3
bin(0x3EAAAAA56A69AA55A95995A569AA95565556)

'0b1111101010101010101010101001010110101001101001101010100101010110101001010110011001010110100101011010011010101010010101010101100101010101010110'

可以看到二进制除了前4位，后面都是10,01，差分曼切斯特有跳变为"0"，无跳变为"1"

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
id1 = 0x8893CA58
msg1 = 0x3EAAAAA56A69AA55A95995A569AA95565556
msg2 = 0x3EAAAAA56A69AA556A965A5999596AA95656

def calc(msg):
    id=''
    s = bin(msg)[6:]
    for i in range(2, len(s), 2):
        if s[i-2:i] == s[i:i+2]:
            id += '0'
        else:
            id += '1'
    return hex(int(id, 2)).upper()

print(calc(msg1))
---------------------------------
0X24D8893CA584181

可以看到id是取结果的5到13位，所以第二个id

1
print('flag{' + hex(int(calc(msg2),2)).upper()[5:13] + '}')

flag{8845ABF3}

传感器2

已知ID为0x8893CA58的温度传感器未解码报文为：3EAAAAA56A69AA55A95995A569AA95565556
为伪造该类型传感器的报文ID（其他报文内容不变），请给出ID为0xDEADBEEF的传感器1的报文校验位（解码后hex），以及ID为0xBAADA555的传感器2的报文校验位（解码后hex），并组合作为flag

使用上一题的代码和报文

1
2
3
4
5
6
7
8
msg1 = 0x3EAAAAA56A69AA55A95995A569AA95565556
msg2 = 0x3EAAAAA56A69AA556A965A5999596AA95656

print(calc(msg1))
print(calc(msg2))
---------------------------------
0X24D8893CA584181
0X24D8845ABF34119

可以观察到除了ID不同外，剩余部分只有最后两位不同，猜测为CRC8

1
2
3
4
5
6
7
crc8 = crcmod.predefined.mkCrcFun('crc-8')

hex(crc8(bytes().fromhex('024D8893CA5841')))
hex(crc8(bytes().fromhex('024D8893CA5841')))
---------------------------------
'0x81'
'0x19'

可见正确

1
2
3
4
5
6
7
8
9
10
11
12
from crcmod.predefined import mkCrcFun

def CRC8(s):
	crc8 = mkCrcFun('crc-8')
	return hex(crc8(bytes().fromhex(s)))[2:].upper()

A1 = '024DDEADBEEF41'
A2 = '024DBAADA55541'

print('flag{' + CRC8(A1) + CRC8(A2) + '}')
---------------------------------
flag{B515}

flag:

flag{B515}

Classical

这题是典型的Knapsack problem，和PlaidCTF 2015中Lazy一题相似，这里翻译一下Lazy这题的解题思路，可能不太准确，原文：http://gnoobz.com/plaid-ctf-2015-lazy-writeup.html

在查看代码之前，我已经怀疑这可能是关于Merkle-Hallman背包密码系统，经过快速测试后，我被证明是正确的。 原则上，这个系统的想法是生成一个超级递增的数字序列

$$ \forall j: xj > \sum{i=0}^{j-1} x_i. $$

为了隐藏这个超级递增性质，我们进一步选择随机$r$和模数$N$并计算序列$(y_i)$其中 $y_i = rx_i \ mod N$。 公钥由$(y_i)$给出并且私钥由$((x_i),r,N)$给出。 现在要加密消息$m$，我们将它分成位$(b_i)$和计算 $c = \ sum_i y_i b_i$。 然后通过首先计算$c'= cr ^ { - 1} \ mod N$并从 $c'$ 恢复 $(b_i)$ 来完成解密，这可能是由于$(x_i)$的超级递增性质。 因此，我们将检查第一个$x_i \ leq c'$产生第一位,然后更新$c''= c'-x_i$ 并重新开始。

幸运的是，攻击这个方案也不是很困难。我们可以用矩阵来解方程

$$c = y_1b_1 + y_2b_2 + \cdots + y_Nb_N$$
对于 $b_i \in {0,1}$. 这是通过考虑矩阵来实现的
$$
\begin{pmatrix}
y_1 & 1 & 0 & \cdots & 0 \
y_2 & 0 & 1 & \cdots & 0 \
\vdots & \vdots & \vdots & \ddots & \vdots \
y_N & 0 & 0 & \cdots & 1 \
-c & 0 & 0 & \cdots & 0 \
\end{pmatrix}
$$
并使用LLL还原。经过一点测试，找到正确的行（基本上是寻找0和1），猜测一些未恢复的字符和标志读取

代码实现：https://github.com/everping/ctfs/blob/master/2015/4/plaidctf/crypto/lazy/solve.py

以下摘至FlappyPig的Writeup：https://www.anquanke.com/post/id/86431

加密代码生成了超递增的sk后，使用sk * mask % N作为pk进行使用。flag被用于选取pk求和得到sum。

是典型的Knapsack problem，使用Shamir Attack进行攻击。在github上有很多此类加密方案的攻击办法：

https://github.com/taniayu/merklehellman-lll-attack

https://github.com/kutio/liblll

https://github.com/sonickun/ctf-crypto-writeups/tree/4c0841a344bc6ce64726bdff4616fe771eb69d1e/2015/plaid-ctf/lazy

攻击方法为首先构造矩阵，通过lllattack求得新的矩阵，选取最短的向量即可。

flag:

flag{M3k13_he11M4N_1ik3s_1Att1ce}