本题源自2019年36C3 CTF，对基于Speck的hash算法找原像或第二原像，解法是中间相遇（Meet-In-The-Middle)
题目
CTF time：bacon
100秒内解出服务器给你的hash所对应的数据：
#!/usr/bin/env python3
import os, signal
def Speck(key, blk):
assert tuple(map(len, (key, blk))) == (9,6)
S = lambda j,v: (v << j | (v&0xffffff) >> 24-j)
ws = blk[:3],blk[3:], key[:3],key[3:6],key[6:]
x,y, l1,l0,k0 = (int.from_bytes(w,'big') for w in ws)
l, k = [l0,l1], [k0]
for i in range(21):
l.append(S(16,l[i]) + k[i] ^ i)
k.append(S( 3,k[i]) ^ l[-1])
for i in range(22):
x = S(16,x) + y ^ k[i]
y = S( 3,y) ^ x
x,y = (z&0xffffff for z in (x,y))
return b''.join(z.to_bytes(3,'big') for z in (x,y))
# did I implement this correctly?
assert Speck(*map(bytes.fromhex, ('1211100a0908020100', '20796c6c6172'))) == b'\xc0\x49\xa5\x38\x5a\xdc'
def H(m):
s = bytes(6)
v = m + bytes(-len(m) % 9) + len(m).to_bytes(9,'big')
print(v.hex())
for i in range(0,len(v),9):
s = Speck(v[i:i+9], s)
print(s.hex())
return s
signal.alarm(100)
h = os.urandom(6)
print(h.hex())
s = bytes.fromhex(input())
if H(s) == h:
print('The flag is: {}'.format(open('flag.txt').read().strip()))
else:
print('Nope.')
Speck
Speck是一种ARX（add–rotate–xor）密码，不是置换代换，也就没有S盒。支持多种分组密文长度。单个分组总是包含两个单字，每个单字可以由16位、24位、32位、48位或64位比特组成。相关密文由2、3或4个词汇组成。编码的循环函数包含两次反转计算：将右单字添加到左单字，异或密文与左单字；之后异或左单字与右单字。循环的次数取决于参数的选择如下:
| 块大小(bits) | 秘钥大小(bits) | 循环次数 |
|---|---|---|
| 2×16=32 | 4×16=64 | 22 |
| 2×24=48 | 3×24=72 | 22 |
| 4×24=96 | 23 | |
| 2×32=64 | 3×32=96 | 26 |
| 4×32=128 | 27 | |
| 2×48=96 | 2×48=96 | 28 |
| 3×48=144 | 29 | |
| 2×64=128 | 2×64=128 | 32 |
| 3×64=192 | 33 | |
| 4×64=256 | 34 |
分析
这道题首先应该是实现了一版正确的Speck算法（key：72bit，block：48bit），可以参考simonspeckciphers，这个库进行结果对比。然后自己实现了一个基于Speck的hash算法，步骤是：把输入的数据按9个字节（72bit），然后在补上一个9字节的数据长度，然后用输入的分组当做每一次的轮秘钥去加密上一次加密结果，初始数据为6个字节（48bit）的0，所以最后的hash也为6个字节。所以题目需要我们给出一段数据，使得这段数据经过题目中的H函数运算后等于题目给出的随机数即可拿到flag。所以这道题我们要攻击Speck还是攻击H呢？一个是加密算法，一个是Hash算法，让我先看看这两种算法在安全性上的要求吧！
对于密码算法的最高的安全性要求是：
- 不能从密文中获得明文的任何数据，只有一次一密能达到这个要求
- 至少是不能从一些明密文的信息中恢复出秘钥（CPA，CCA）
对于hash算法的安全性要求是：
- 抗原像
- 抗第二原像
- 抗碰撞
可见，这道题目的要求是找到一段数据能计算出对应的Hash，而且貌似实现了一版正确的Speck算法，感觉还是攻击H函数的概率比较大一些，是这样么？我们来再具体的看一下H函数：
def H(m):
s = bytes(6)
v = m + bytes(-len(m) % 9) + len(m).to_bytes(9,'big')
print(v.hex())
for i in range(0,len(v),9):
s = Speck(v[i:i+9], s)
print(s.hex())
return s
H函数把我们每次输入的消息当成Speck算法的秘钥进行运算，讨论我们输入的消息是两个分组或者三个分组时：
所以综上，本题是攻击题目中的Hash算法，即H函数，并不需要研究Speck算法本身，只要写出其解密函数即可
解法
所以就是先随机M1，生成一堆C1’数据在本地，这里采用python的字典对象，因为字典对象的是通过hashmap存储的，查找索引复杂度为O(1),然后把这个对象序列化保存在本地：
#!/usr/bin/env python3
import os, signal
import time
import random
import pickle
def Speck(key, blk):
assert tuple(map(len, (key, blk))) == (9,6)
S = lambda j,v: (v << j | (v&0xffffff) >> 24-j)
ws = blk[:3],blk[3:], key[:3],key[3:6],key[6:]
x,y, l1,l0,k0 = (int.from_bytes(w,'big') for w in ws)
l, k = [l0,l1], [k0]
for i in range(21):
l.append(S(16,l[i]) + k[i] ^ i)
k.append(S( 3,k[i]) ^ l[-1])
for i in range(22):
x = S(16,x) + y ^ k[i]
y = S( 3,y) ^ x
x,y = (z&0xffffff for z in (x,y))
return b''.join(z.to_bytes(3,'big') for z in (x,y))
time_start=time.time()
d={}
z = bytes(6)
for i in range(pow(2,25)):
m1 = os.urandom(9)
s1=Speck(m1,z)
d[s1]=m1
data = pickle.dumps(d)
f = open('m1data', 'wb')
f.write(data)
f.close()
time_end=time.time()
print('totally cost',time_end-time_start)
运行大概20多分钟后生成一个900多M的序列化对象：
➜ ls -alh m1data
-rw-r--r-- 1 wangyuxuan staff 928M 12 29 14:05 m1data
先加载m1data到内存中，然后连接服务器，并长度分组去解密服务端给的数据得到s2，随机m2，解密s2，与内存中的C1’进行比较：
#!/usr/bin/env python3
import os, signal
import time
import random
import pickle
from pwn import *
context(log_level='debug')
def Speck_reverse(key, result):
assert tuple(map(len, (key, result))) == (9,6)
S = lambda j,v: (v << j | (v&0xffffff) >> (24-j))
S_reverse = lambda j,v:( (v&0xffffff) >> j | v << (24-j))
ws = result[:3],result[3:], key[:3],key[3:6],key[6:]
x,y, l1,l0,k0 = (int.from_bytes(w,'big') for w in ws)
l, k = [l0,l1], [k0]
################################ first layer
for i in range(21):
l.append(S(16,l[i]) + k[i] ^ i)
k.append(S( 3,k[i]) ^ l[-1])
# reverse
for i in range(22):
S3y = y^x
y = S_reverse(3,S3y)
S16x = (x^ k[22-i-1])-y
x = S_reverse(16,S16x)
x,y = (z&0xffffff for z in (x,y))
return b''.join(z.to_bytes(3,'big') for z in (x,y))
f = open('m1data', 'rb')
data = f.read()
d = pickle.loads(data)
m3=(18).to_bytes(9,'big')
while 1:
time_start=time.time()
io = remote("78.47.89.248",1952)
a = io.recvline()[:12]
random_num = bytes.fromhex(str(bytes.decode(a)))
s2 = Speck_reverse(m3,random_num)
for i in range(pow(2,21)):
m2 = os.urandom(9)
s1=Speck_reverse(m2,s2)
if s1 in d:
print("s1: "+s1.hex())
print("m1: "+d[s1].hex())
print("m2: "+m2.hex())
io.sendline(d[s1].hex()+m2.hex())
io.recv()
break
time_end=time.time()
print('totally cost',time_end-time_start)
io.close()
开了4个进程，一会就获得了flag：
