第八讲数据加密标准DES.ppt

第八讲 数据加密标准(DES),1974年，IBM 向美国国家标准局(NBS)提交了一个名为 LUCIFER的加密算法。NBS将其转给了国家安全局 (NSA) 进行审定，之后就得到了一个名为数据加密标准DES的算法。1977年，NBS 正式将其用于无限制级的政府通讯。,从1975年起，围绕DES的争论就没有停止。许多学者担心NSA无形的手对算法产生的干预。如： (1) NSA可能修改算法以安装陷门。 (2) NSA将原先的128位密钥缩短到56位。 (3) 算法内部的运行机理始终没有得到明确解释。例如，差分分析。 许多NSA设计算法的原理在90年代逐渐清晰起来，但在70年代这些的确另人迷惑。,DES已经使用了三十多年，因此，2000年，国家标准与技术研究所(NIST)决定使用新的系统代替DES。但是DES仍然值得研究，它代表了一类曾经非常流行的对称加密算法。 DES是分组密码，每个分组为64比特数据。 64比特明文通过加密最后成为64比特密文。 DES 的核心是一个被称为Feistel系统的部件。,本讲提要,简化DES型算法 差分分析 DES DES不是一个群 破译DES 口令安全,1 简化 DES型算法,一轮 Feistel系统,一轮 Feistel系统(续),一轮 Feistel系统 (续) 函数 f(Ri-1，Ki),一轮Feistel系统(续) 扩张函数,S-盒,一轮Feistel系统(续),2 差分分析,思路：通过适当选择明文得到密文比较它们的差异以推导出使用的密钥。我们从前面的操作可以看出密钥与E(Ri-1)进行异或得到结果，因此，我们可以通过再次异或移除由密钥引入的部分随机性。,2.1 针对三轮的差分分析,2.1 针对三轮的差分分析(续),2.1 针对三轮的差分分析(续),2.1 针对三轮的差分分析(续),2.2 针对四轮的差分分析,四轮差分分析是建立在三轮基础之上的，但是要扩展到四轮还需要使用一些统计方面的知识。这里我们关注S-盒的一些弱点。,2.2 针对四轮的差分分析 (续),2.2 针对四轮的差分分析 (续),2.2 针对四轮的差分分析 (续),2.3 关于差分分析,(1) 我们注意到前面的例子表明差分攻击至少和强力攻击有相同的速度。然而，对于更优异的系统如DES ，在一定的轮数下，差分攻击的效率将明显快于搜索全部密钥空间的强力攻击。 (2) Mitsuru Matsui 发明了另一种名为线性攻击的分析方法。这一攻击使用线性估计来描述分组密码的行为。线性分析可以看作是一种效率改进的新型差分分析 (理论上需要大约 243 明-密文对) 。但是并没有证据显示其可以有效的在实际中攻击DES。,3 DES,DES的密钥通常写为64比特，但每8比特有一位奇偶效验位，可以忽略，因此，实际只有56比特。算法只使用不超过64位的标准算术操作和逻辑操作，所以在70年代仅使用硬件就可以容易地实现算法。算法的重复特性非常适合专用芯片执行。起初采用软件执行的DES显得笨拙，但目前的软件执行效果也相当不错。,3.1 DES 算法描述,3.1 DES 算法描述(续),3.2 初始计算,3.3 函数 f(Ri-1， Ki),3.3 函数 f(Ri-1，Ki) (续),3.3 函数 f(Ri-1， Ki) (续),3.3 函数 f(Ri-1， Ki) (续),3.4 密钥变换,3.4 密钥变换 (续),3.5 DES的安全,DES存在关于密钥长度、叠代次数、S-盒设计准则的问题。特别是S-盒以常量形式给出，但并未明确说明这些常量为何以这种形式出现。虽然IBM声称这些是经过17年大量密码分析得出的结果，但是人们还是十分担心NSA的介入可能为算法安装陷门以利于其解密。,3.5 DES的安全 (续) 在90年代初期，IBM 终于公开了S-盒设计的基本原理。 (1) 每个S-盒为6比特输入和4比特输出。这是1974年芯片处理数据的最大能力。 (2) S-盒的输出不应该和输入接近线性的函数关系。 (3) S-盒的每一行都应该包括全部0到15这16个数字。 (4) 如果输入每个S-盒的两个数据有一位不相同，则输出必须有至少两位不同。,3.5 DES的安全 (续) (5) 如果两个S-盒输入的前两位不同但最后两位相同，则输出必不相等。 (6) 对于每个给定的异或XOR值存在32种可能的输入对。这些输入对可以得到相应异或XOR 输出。所有这些输出不得有8个的值完全相同。 这一原则显然是用来阻止差分分析的。 (7) 这一原则与(6)类似，只是这里考虑3个S-盒的情况。 (详细论述，参见 “D. Coppersmith, The data encryption standard and its strength against attacks“),4 DES 不是一个群,选择两个密K1和K2加密明文P得到EK2(EK1(P)。这样的做法是否可以增加安全性？如果攻击者有足够的存储空间，这样做提供的安全保障有限。进一步，如果两次加密等于单次加密，密码的安全性将比我们想象的还要弱。例如，这一条件要是对DES成立，那么穷尽搜索256的密钥空间将被搜索大约228的密钥空间所替代。,5 破译DES,5.1 DES已显老迈 (1) 1977年，Diffie和Hellman 估计如果花费2千万美元制造一台机器大约仅需一天就可以破译DES。 (2) 1993年，Wiener利用开关技术设计了更加有效的破译DES设备。 (3) 到1996年逐渐形成了三种破译DES的基本方法。一种方法是利用分布计算。一种是设计专用攻击芯片。折中的方法是使用可编程逻辑门阵列。,5.1 DES已显老迈(续) (4) 分布计算方法破译DES变得十分流行，特别是在Internet兴起和壮大的情况下。1997年，RSA数据安全公司开展了破译DES密钥和其加密消息的竞赛。仅仅5个月，Rocke Verser 就在搜索了25% 的密钥空间后发现密钥。接下来，RSA 数据安全公司又开展了第二次竞赛。结果用时39天搜索了密钥空间的85%发现了对应密钥。,5.1 DES已显老迈(续) (5) 1998年，电子领域基金会(EFF)展开了一项名为DES破译的计划。计划的基本思想是：一般使用的计算机对于完成破译DES的任务来说不是最优的。计划使用的结构是硬件用来判定排除大量不可能的密钥并返回那些可能的密钥。软件则用来处理每一个可能的密钥，判定这些密钥是否确实为密码系统使用的密钥。结果是计划使用1500个芯片平均在大约4.5天可以完成对DES 的破译。,5.1 DES已显老迈(续) (6) 有传言说根据预先处理的不同，NSA可以在3到5分钟成功破译DES。而在机器方面的开销仅有5万美元。 #上述结果说明对于90年代晚期的计算技术而言，加密系统使用56比特的密钥显得过短，不能提供强有利的安全保护。,5.2 增加安全性的DES变化,5.2 增加安全性的DES变化 (续),6 口令安全,问题. 口令一般与每一个实体相关联，是一个6到10或更多的方便记忆的字符串。口令由实体和系统共享。为了获得访问系统资源的权限(例如，计算帐户，打印机，或软件应用)， 实体输入身份-口令对。系统则核实对于相应的身份和口令输入是否正确。如果正确，系统就按照身份分配实体相应的访问授权。系统通过实体展示其掌握口令秘密来将其与声称身份挂钩。,6.1 口令方案 存储口令文件 加密口令文件,6.1 口令方案(续) (3) 降低口令映射速度 (4) 口令加盐 为了使口令猜测攻击无效，每一个口令条目都增加t比特的随机串叫做盐，将盐和口令一同作为单向函数的输入。口令Hash值和盐一同记入口令文件，以供验证使用。 (5) 口令短语,6.2 常见攻击 (1) 重放固定口令 (2) 穷尽搜索口令 攻击的成功依赖于在成功发现口令之前需要验证的口令数量以及每次验证测试所需要的时间。 (3) 口令猜测或字典攻击 在线/离线口令猜测攻击,6.3 实例 UNIX口令系统,6.3 实例 UNIX口令系统(续) (1) 口令盐。UNIX口令盐是将12位的随机串与用户选择口令关联。这 12位的随机串做为DES的标准扩展函数E的一个变量，提供4096种不同的变化情形，也就是盐的第1比特对应输入的第1比特和第25比特，第2比特对应输入的第2比特和第26比特如此下去。如果盐比特值为1，则输入的相对应位做交换，如果盐比特值为0，则保持不变。Hash口令值和盐都保存在系统口令文件的一条目录之中。对于单个用户而言，口令的安全并没有增加，但对于字典攻击整体口令文件而言，对于每一个可能口令却增加了4096种不同的口令测试计算。,6.3 实例 UNIX口令系统(续) (2) 防止使用现成的DES芯片攻击系统。由于DES的扩展计算需要使用盐，因此，标准的DES算法不再能执行UNIX口令算法。如果攻击者希望采用硬件加速攻击，他就不能直接选择一般商用DES芯片，而要自己设计DES芯片。这毫无疑问增加了攻击成本。,谢谢!,