我(以及其他许多人)一直对现代密码学的内部工作原理(块密码)着迷。

现在,设计和分析的“黑艺术”资源这些密码中稀疏的;特别是对于入门级。 Schneier指南等可用信息似乎已经过时(由于其年代久远)。

开始设计和/或分析现代密码学的“最佳”(阅读:推荐)策略的普遍共识是什么分组密码? (此外,该问答将代表我们在出现类似的算法设计问题时可以向人们指出的地方。)

评论

如果您想结束这个问题,请阅读以下内容:1)并不是“太宽泛”,因为在这里只能应用数量非常有限的策略,而这严格限于分组密码的领域。 2)它不是“基于观点的”,因为在如何处理此主题以使其客观地承担责任方面,至少存在一些共识。 3)这不是有关密码设计质量的问题的重复,因为我在这里不询问它们。 4)这不是“参考建议”,因为策略并不严格要求它们。

您能否支持Schneier指南已过时的声明?

实际上,我想说的是,即使Schneier的指南在过去15年中没有任何参考,它仍然是一个不错的开始。它仍然保留了许多技术的参考,这些技术是当今设计和攻击的基础。

评论不作进一步讨论;此对话已移至聊天。

#1 楼

为了设计和分析密码,我们必须确定密码应该完成的工作。简而言之,我们希望能够以仅授权人员可以执行或反转转换的方式转换信息。我们可以将这种转换称为“加密”。可能存在未经授权的方,尽管有机会,他们仍可能/将尝试这样做,但他们不应该能够获得受加密方法保护的任何信息。即使所涉及的工作量很大,很重要,这也适用。我们可以将未经授权的各方称为对手。如果不是出于这两个极端实用的方面,那么“一时间垫”将是无与伦比的,具有信息理论上的安全性,实现简单性和最高效率(每个字符只需添加一个字符!)。 OTP并不是分组密码,但是它是一个很好的参考点。

不幸的是,一个时间垫要求密钥材料与要加密的信息一样长,并且需要提前准备时间由授权方决定。这违反了我们上面列出的两个实际需求,因此我们必须设计其他算法,以重新使用更小的密钥。

一种诱惑是保持加密算法本身的秘密。不幸的是,保守算法的秘密意味着算法的所有用户都知道加密/解密的秘密。随着知道该秘密的用户数量的增加,该秘密被对手侵害的可能性也随之增加。这将无法达到最初的设计目标,并且在实用性和要保护的机密大小方面仅比OTP稍好一些。

这导致了第三个最成功的选择:使用一种公开的算法,该算法将所需的保密性集中到该算法使用的密钥中。

无论使用哪种方法进行加密,信息都可能受到攻击攻击对手。加密的工作是抵抗这种攻击,并保护信息。这意味着几件事:




由于现代密码使用密钥来授权当事方执行转换,所以对手的目标是获取密钥



获得密钥意味着加密明文和解密密文的能力,违反了密码的原始设计目标。


类似于锁的方式在门上使用钥匙
您只需要保护钥匙,而不能阻止任何人知道有锁
钥匙可以重复使用,并且使用寿命很长。
密钥应相对较小-常见128到256位



即使对手,密钥也必须保持安全:


拥有大量密文
知道消息的明文内容,以及每条消息的相应密文
可以欺骗授权方为对手加密/解密消息


选择随意加密或解密的消息。
可以适应或修改将来的加密/解密查询,以响应过去的查询。








现代密码的大多数复杂性来自于保护密钥的尝试,并由此扩展了明文。设计具有可重用密钥的密码将需要了解如何攻击密码和密钥。为了设计密码,您必须学会像对手一样思考,并研究密码如何被破解。

标准攻击

任何新密码都必须防范几种通用攻击方法:蛮力搜索,差分密码分析和线性密码分析。




暴力破解意味着攻击者简单地猜测所有可能的键值组合,直到找到正确的键为止。最坏的情况下,时间复杂度为$ 2 ^ N $,其中$ N $是键的宽度位


时间复杂度仅在密钥均匀随机的情况下才是准确的
64位对于现代计算机而言被认为太低
128位目前被认为是安全的
即使面对未来的量子计算机,256位也被认为永远是安全的







差分密码分析利用了特定差异的概率输入($ t_1 $和$ t_1'$)之间的($ \ Delta_1 $)将传播到特定的输出差异($ \ Delta_2 $)



测试所有可能的输入差异,有可能返回概率有一些输出差异。几个特定的​​差异$ \ Delta_1 $和$ \ Delta_2 $被称为差异并记为($ \ Delta_1 \ Rightarrow \ Delta_2 $)。 '$)成立,可以更有效地利用这种行为来打击密码
可以在这里找到带有代码的相对简单的教程

可以在此处找到Biham和Shamir的原始论文<线性密码分析利用给定输入的位子部分与函数输出中的位子部分相关的可能性


通过按位屏蔽选择了一个位的子部分

可利用的关系是,如果输入和输出位的子部分的汉明权重的奇偶性相同
这种关系越规则地发生,线性密码分析就会越有效
可以在这里找到一个相对简单的带代码的教程

在这里可以找到Matsui的原始论文



线性和差分密码分析可以提供提示关于密码的内部状态,直到某一点。这可以减少对手必须猜测的一部分密钥的可能值的数量。就现代密码的密码分析而言,这些被认为是最强大的工具中的两个。

分组密码结构

密码结构主要分为两类:Feistel网络和替换置换网络。

Feistel网络的基本设计是将消息块分为左右两半。具有良好扩散性和混乱性的键控函数应用于右半部分,并将其输出添加到左半部分。然后将两半交换,并重复该过程。解密与反向键执行的操作大致相同,因此就实现复杂性而言,此构造相对较轻。 DES是Feistel网络的一个示例。针对DES有差分和线性攻击。

替代置换网络的设计通常比Feistel网络的左右一半更精细。例如,在Rijndael密码(也称为高级加密标准(AES))中,消息以16 x 1字节状态操作,排列为4行4列。它包含4个主要步骤:字节替换,行换位,mixColumns步骤以及通过XOR添加密钥材料。

许多(如果不是全部)现代分组密码是由重复迭代相同的核心功能构成的,通常在每个应用程序之间使用多个不同的密钥。通常,这些密钥是由用户实际提供给密码的主密钥派生的。我们将以此方式生成的密钥称为循环密钥,并且将其生成密钥调度的过程。

循环密钥的导出方式会影响密码的安全性和效率。理想情况下,任何回合密钥信息的恢复应尽可能少地透露其他回合密钥或主密钥。这是OTP的优势之一:密钥材料字节的恢复(即通过已知的明文攻击)在恢复密钥的其他字节方面没有任何帮助。通常也认为,快速生成圆形密钥材料是有利的,因为具有较慢密钥调度的密码可能具有更大的延迟和/或较低的吞吐量。

设计圆形函数

为了知道要使用的操作,我们需要知道需要完成的操作:



扩散


在任何地方翻转一个输入位应该平均翻转(大约)一半的输出位
按字节移位,旋转和换位可以帮助扩展给定部分位的影响
按位移位可以也可以使用,但是在软件上可能相对较慢(但在硬件上可能很快)



混乱/非线性


密钥和密文之间的关系应该很复杂
高斯消除法可以破坏线性密码。
不同领域的混合算法可以提供非线性(即xor和加法模256)
布尔功能离子可以提供非线性



仅通过正确的键即可反转


如果在某个时候引入了秘密(密钥)材料,则密码只会提供机密性。


在应用任何回合之前和应用所有回合之后在输入上应用键称为键白化,这很常见。通常为1(即每轮之后)
键加法通常是通过xor和加法模(2 ** wordsize_in_bits)来完成,或者两者都



弱键”




因此,我们的目标是将消息与键组合在一起,并以扩散和非线性的方式翻转很多位。
理想地,我们希望我们的运算组合能够产生类似于随机排列的输出。

一些可用的说明是:



Xor



用于组合两个输入(即消息)和键)
是它自己的逆(对合)


不需要减法指令来求逆


位切片
需要用于非线性的加法/布尔函数/ s-box查找



加法


用于组合两个输入
需要单独的减法指令来反转
倾向于翻转低位比特而不是高位比特



查找表


对于良好的微分/线性特性很有用
有效等效于非线性函数的缓存输入/输出
在利用缓存的计算机上可能容易受到定时攻击



布尔函数


对非线性有用
选择和多数函数是一些例子


选择


逻辑上,如果C则为B,否则为A
c ^(a&(b ^ c))(对于数学家:$ c \ oplus(a \ wedge(b \ oplus c))$)
位切片操作


大多数


(a和b)| (a和c)| (b&c)(对于数学家:$(a \ wedge b)\ vee(a \ wedge c)\ vee(b \ wedge c)$)







旋转/移位


用于通过单词扩散和携带/传播差异
通常由固定完成数量,但不一定



转置根据秘密数据可能容易受到定时攻击(需要考虑与秘密有关的内存访问)
包括循环


>

就像输入位的混洗(排列)一样操作
仅修改给定的位位置,而不修改其值(不修改汉明权重)
是线性变换
示例:Keccak置换,特别是Rho和Pi步骤
可以提供“弱对齐”



伪Hadamard变换:


提供扩散
由SAFER和Twofish使用




上述操作的一些示例组合:



Rijndael由消息上的addRoundKey,mixColumns,shiftRows和subBytes组成:逐字节换位

mixColumns是一种线性变换,与shiftRows一起提供扩散
addRoundKey将具有状态的键异或为




DES舍入功能由扩展排列,键混合,s-box应用程序和位排列组成。


扩展对S-box进行补偿,使其从6位变为4位。
密钥通过异或运算每轮应用一次
S盒提供对差分密码分析的抵抗力
位置换提供扩散
蛇回合函数由混合键异或,4×4 S盒和线性变换组成。并行(位切片设计)
线性混合提供扩散




TEA仅使用加法,移位和XOR:


异或/加法产生非线性并应用关键材料
移位/加法提供扩散至少两种不同的方法:基于S盒的设计



可以提供非常好的线性/微分特性和良好的性能
由于搜索空间巨大,可能很难找到好的大型S盒
倾向于与线性混合层结合使用进行扩散

Rijndael策略:


使用具有最佳最差情况微分/线性特性的s-box
使用混合层旨在提高扩散速率的下限
注意在最坏情况下如何设计



可以提供清晰的证据证明对差分/线性攻击的抵抗力
/>


基于ARX的设计(加法,旋转,异或)

与s-box相比,它们本质上不利于基于定时的侧信道攻击基于基础的构造


固定数量的加法,异或运算通常是在恒定时间内实现的。


PC上的快速性能(尤其是如果可以的话)避免内存访问/粘到寄存器)
紧凑/简单的实现(不需要查找表所需的空间)
与基于s-box的设计相比,分析差分/线性攻击的安全性不那么直接



许多密码使用一组常数。每一轮,都会通过加法/异或将新的常数引入状态。这可以通过使连续的回合不同来帮助防止滑动攻击。

中断回合函数

在对任何新设计应用线性和/或差分密码分析之前,请考虑运行一些统计检验。统计测试可以很快告诉您您的最新设计是否已完全损坏。请注意,统计测试无法确认设计是否在密码上安全,而只能确认设计不安全。

一些示例测试可能是:


雪崩测试


使用给定的密钥生成随机数据块(即,对递增计数器进行加密),并测量连续输出之间的汉明距离(测量数据的扩散)一系列具有不同键的连续值,并测量前一组随机数据与新集之间的汉明距离(测量键的扩散)
br />
使用密码(例如,通过加密递增计数器)生成大量(> 1MB)数量的伪随机数据
将数据传递给诸如ent,dieharder或NIST测试套件之类的工具



在您的设计和os.urandom上运行上述测试:理想情况下,两个结果应该没有区别。提出攻击时,请先尝试攻击简化版本(单次)的密码。寻找设计中的最薄弱点。
尝试针对FEAL进行练习,它有一个主要弱点,对于学习差分/线性密码分析和滑动攻击非常有用。是学习线性密码分析和蛮力搜索的有用方法

一旦解决了这些问题,除了通用的线性/差分密码分析,实际上还有许多其他攻击方法
您可能会在这里找到一些与密码分析相关的软件

数学和可视化

如果发现可视化和图表很有用,则此页面可能对您很有趣。
如果您不太了解数学,请尝试学习一些表示法。您想了解的许多信息将写在科学研究论文中,并以数学语言编写。

在阅读论文以及进行密码分析/密码设计时将被证明有用的一些主题是:


基本集理论br />基本线性代数

有限域


评论


$ \ begingroup $
数学和可视化中“学习一些符号”的链接(en.wikibooks.org/wiki/Category:Mathematical_logic)断开。
$ \ endgroup $
– abraza
17-10-2在7:06

#2 楼

没有明确定义的,明确的最佳学习路径。但是,根据我自己的经验,我建议按以下顺序解决以下问题:线性密码分析:从Matsui的文章开始,实现您自己的DES,并尝试在简化版本中进行尝试。版本(例如8轮而不是完整的16轮)。您可能还想看看Pascal Junod的这份报告。
差异密码分析:本书对此做了详尽的解释(Biham免费提供PDF格式)。实际上,这也是DES算法本身的一个很好的来源,因此您也将希望使用它来实现线性密码分析。再次,在简化的DES上实施差分密码分析。
继续阅读Boomerang攻击和相关攻击(放大的回旋镖,矩形等)。这些可以看作是差分攻击的扩展变体,其主要的教学优势是可以说明攻击者“作弊”的许多方式。在正式的背景下。
那么该是应对AES竞争的时候了。前面的所有步骤实际上都旨在为您提供足够的术语背景信息,并且也许更重要的是,培训您阅读研究文章,以便您可以阅读比赛中显示的所有内容。

通常,我采用“动手实践”的方法,这意味着我可以通过实施这些方法来进行尝试。我发现,就我而言,这对理解很有帮助。但是最终,分析分组密码的关键是要拥有对这些年来积累的各种设计和攻击的广泛了解,而这只有通过阅读大量研究文章才能实现。

具有实施经验也是处理以分组密码(即边信道攻击)的当前热门话题的要求。特别是,已经针对许多经典AES实现演示了基于缓存行为的定时攻击(在实验室条件下,而不是“狂野的”),并且在设计可防止此类攻击的实现技术方面已经做了很多努力。 >

评论


$ \ begingroup $
我还发现Heys的“线性和差分密码分析教程”使用了5轮带有16位块长的SPN网络和四个4x4 Sbox,这是密码分析的很好的介绍,它可以模拟攻击也就是说,枫,岩浆,Mathematica只需很少的计算工作。
$ \ endgroup $
– kodlu
2016年9月6日在22:06