<
分组密码(Feistel密码结构)
>
上一篇

护网杯-easy laravel-Writeup
下一篇

EmpireCMS_V7.5的一次审计

分组密码(Feistel密码结构)

目录


  1. 1分组密码

  2. 2代换密码

  3. 3扩散和混肴

  4. 4Feistel密码结构

  5. 4.1Feistel加密结构

  6. 4.2Feistel解密结构

  7. 4.3护网杯-Crypto-fez分析

1分组密码

​ 分组密码是将明文消息编码后的数字序列划分成长为N的分组(长为N的矢量),分别在密钥k=(k0,k1,…kt-1)的控制下变换成等长的输出数字序列(这个序列是长为M的向量,即输入和输出分组的长度可以不同)。它与流密码的不同在于输出的每一位数字不仅与相应时刻输入的明文数字有关,而是与一组长为n的明文数字有关。分组密码的本质实际上是字长为n的数字序列的代换密码。

​ 为保证安全性,设计的算法应满足要求:

1.分组长度n要足够大,防止明文穷举攻击奏效。

2.密钥量要足够大(即向量k要足够长),并且尽可能消除弱的密钥,使所有密钥同等的好,防止密钥穷举攻击奏效。但密钥本身又不能过长,否则难以管理。

3.由密钥确定置换的算法要足够复杂,以抵抗差分攻击和线性攻击。

4.加解密运算简单且易于实现。

5.数据扩展和差错传播尽可能小 。

2代换密码

​ 如果明文和密文分组的长都为n比特,则显然每个明文分组都对应有2^n个可能的取值。为了保证加密运算可逆(否则无法解密,因为分组密码是单钥密码),明文的每个分组在特定加密算法作用之后应当产生唯一的一个密文分组,称明文分组到密文分组的可逆变换为代换。 可以知道,不同可逆变换的个数有(2^n)!个 ,也就意味着密钥的长度为(2^n)!比特。

PS:从实现的角度看,分组长度很大的可逆代换是不实际的。即便分组长度仅为64比特,对应的密钥长度也将约为10^21比特,非常难以处理;然而长度太小又不能满足上述关于算法安全性的第一条要求。因此,实际中常将分组分为较小的子段,例如可将n长向量的代换变为设计m个较小的子代换,称每个子代换为代换盒,简称为S盒。例如,对于48比特输入的DES密码,用8个S盒来实现,这样每个S盒的输入仅为6比特。

3扩散和混肴

目的:扩散和混淆的目的是抗击敌手对密码系统的统计分析。如果敌手知道明文的某些统计特性(如不同字母出现的频率,特定的单词或短语),而这些统计特性如果以某种方式在密文中反映了出来,那么敌手就有可能得到加密密钥的一部分或一个可能的密钥集合。因此需要引入扩散和混淆的方法。

​ 所谓扩散,就是将明文的统计特性扩散到密文中去,实现方式是使得密文的每一位由明文中的多位产生。这样明文的统计特性就被散布开了,因而在密文中每一字母出现的概率将更接近于相等,使敌手难以通过统计分析得到有用的信息。

​ 所谓混淆,就是使密文和密钥之间的统计关系变得尽可能复杂,使敌手无法得到密钥。这样敌手即便得到了密文之间的某些统计关系,也难以得到密钥。

4Feistel密码结构

大多数分组密码的结构本质上都是基于Feistel网络结构 。

4.1Feistel加密结构

Feistel加密算法的输入是长为2w的明文和一个密钥K=(K1,K2…,Kn)。将明文分组分成左右两半L和R,然后进行n轮迭代,迭代完成后,再将左右两半合并到一起以产生密文分组。其第i轮迭代的函数为:

其中Ki是第i轮的子密钥,“+”表示异或运算,F表示轮函数。一般地,各轮子密钥彼此各不相同,且轮函数F也各不相同。代换过程完成后,在交换左右两半数据,这一过程称为置换。Feistel网络的结构如下:

img

Feistel网络的安全性参数:

1.分组大小

2.密钥大小

3.子密钥产生算法 该算法复杂性越高,则密码分析越困难(ps:并非加密算法,Feistel网络结构本身就是加密算法或其重要组成部分,是无需保密的)。

4.轮数 单轮结构远不足以保证安全,一般轮数取为16。

5.轮函数 结构越复杂越难分析

4.2Feistel解密结构

​ 本质上与加密过程一样,将密文作为输入,以相反次序使用子密钥,保证加密和解密可以采用同一算法。以16轮加密为例,在加密过程中,LE16=RE15,那么在解密过程中,LD1=RD0=LE16=RE15,其中E表示加密(Encode),D表示解密(Decode)。

4.3护网杯Crypto例题-fez分析

题目如下:

fez.py

import os
def xor(a,b):
    assert len(a)==len(b)
    c=""
    for i in range(len(a)):
        c+=chr(ord(a[i])^ord(b[i]))
    return c
def f(x,k):
    return xor(xor(x,k),7)
def round(M,K):
    L=M[0:27]
    R=M[27:54]
    new_l=R
    new_r=xor(xor(R,L),K)
    return new_l+new_r
def fez(m,K):
    for i in K:
        m=round(m,i)
    return m

K=[]
for i in range(7):
    K.append(os.urandom(27))
m=open("flag","rb").read()
assert len(m)<54
m+=os.urandom(54-len(m))
test=os.urandom(54)
print test.encode("hex")
print fez(test,K).encode("hex")
print fez(m,K).encode("hex")

fez.log

048d26224aae9f6be49f13202c0b173c2346909fcbba868d5d9b7431002957c5c01c546530f84e45b8a3892526401c007bca7d39b0b7
69d41820c61c7e8fb47fde8f09064f24af72dc6251e97e72bdc2d7c0b4696110ef84f30da6ac88b7059500f8e814cec9e9e13bcafad8
32e7094533a1e76ac8acdeb882c0d6965ca954d75dfd00e759b5aff9663f41d49ae70ee18fd3c067ad7ae577433ad2512b764f4b2eb2

分析fez.py,由Feistel密码加密结构可知为Feistel加密方法:

img

轮函数也是异或,进行了7轮迭代。

这里给出了print出的值,所以知道

  1. test的值 记为test
  2. test加密的值 记为 testans
  3. flag加密的值 记为ans

test和用flag填充的m的长度都为54

加密使用的K值是不知道的,所以写不出解密函数,但可以通过给出的testansans异或使K消掉

记最后一轮flag加密后的为L7R7,test加密的为tL7tR7,初始test为tL0tR0

ai=tLi^Li=tRi+1^Ri+1^tLi+1^Li+1

而且Ri=Li+1

所以ai=ai+1^tLi+1^Li+1

最终得到L0和R0

exp

import os
def xor(a,b):
    assert len(a)==len(b)
    c=""
    for i in range(len(a)):
        c+=chr(ord(a[i])^ord(b[i]))
    return c

test='048d26224aae9f6be49f13202c0b173c2346909fcbba868d5d9b7431002957c5c01c546530f84e45b8a3892526401c007bca7d39b0b7'.decode('hex')
testans='69d41820c61c7e8fb47fde8f09064f24af72dc6251e97e72bdc2d7c0b4696110ef84f30da6ac88b7059500f8e814cec9e9e13bcafad8'.decode('hex')
ans='32e7094533a1e76ac8acdeb882c0d6965ca954d75dfd00e759b5aff9663f41d49ae70ee18fd3c067ad7ae577433ad2512b764f4b2eb2'.decode('hex')

tL7=testans[0:27]
tR7=testans[27:54]
L7=ans[0:27]
R7=ans[27:54]

tL0=test[27:54]
tR0=test[0:27]
# a6=tR7^R7^tL7^L7^tR1

# tL6^L6
a6=xor(xor(tR7,R7),xor(tL7,L7))

a5=xor(xor(tL7,L7),a6)

a4=xor(a6,a5)

a3=xor(a5,a4)

a2=xor(a4,a3)

a1=xor(a3,a2)

a0=xor(a2,a1)

L0=xor(tL0,a1)

R0=xor(tR0,a0)

print R0+L0

运行结果

python fez_exp.py
flag{festel_weak_666_lol88fj3820}叡↓泺y:;铸醛o磋萸?
Top
Foot