点击蓝字
关注我们
前言
密码学是网络空间安全领域唯一的理论支撑，大家都认为密码学是安全压舱石。
密码学对安全的关键意义不言而喻。对于安全领域的非密码学大师来说，对密码学的理解可能仅限于玩CTF基本的凯撒密码和围栏密码涉及分析padding oracle attack等待，然后阅读最新的手动编程论文来解决一些问题。
我们对密码学的安全性了解不够。本系列文章的核心来自我们在学习相关文献时的学习记录。我们希望提高我们对压舱石安全性的理解。
具体来说，在本文中，我们将介绍密码学安全的定义以及如何确保安全；然后介绍古典密码及其本质缺陷，然后引出一次密度；然后定义攻击模型和安全目标，并通过分析引出随机性的重要性。为了便于理解，本文将始终举例说明，并给出由于对密码学安全理解不足而发生的实际安全事故。
安全性
密码学的安全性不同于计算机的安全性。
计算机安全，我们以软件安全为例，其目标是防止攻击者利用程序代码触发漏洞，而密码学安全的目标是使定义明确的问题无法求解。对于软件安全，软件要么安全，要么不安全，但对于密码领域的程序，安全不是绝对的，我们可以计算破解加密算法所需的工作量，即量化其安全，但不能绝对称为安全。
密码安全可分为理论安全和计算安全两种。当攻击者拥有无限的时间和资源或无法破译密码时，它被称为理论安全，也被称为无条件安全下面将介绍一个秘密是典型的；如果密码算法不能在给定的时间和资源中被打破，则称为计算安全，这与攻击者的能力、目标和其他条件密切相关，我们将根据不同的条件建立不同的攻击模型和安全目标。
例如，密码算法E的密钥K是128比特，加密过程是C=E(K,P)，已知的明文-密文对(P,C),但是不知道K。
求K，这个问题不是理论安全的，因为我们可以穷举2^128种可能性；但这个问题是安全计算的，因为即使一秒钟就能穷举1000亿K,要穷举
2^128K的成本超过1000 000 000 000 000 000 在实践中是安全的。
形式化和测量
我们可以在这里给出正式的定义。对于密码方案，攻击者最多可以执行t操作，攻击成功的概率不高于ε，则该方案是(t,ε)-此时，破解密码算法的难度下限是安全的。注意，这意味着没有攻击者在执行小于t次的操作时可以获得概率ε成功率，但这并不意味着攻击者可以成功执行t次，也不意味着需要多少次才能成功。因此，t实际上是攻击算法所需操作量的下界。
以攻击128比特密钥的对称密码算法为例。理想情况下，这个密码是1到2^128之间的任何t值都是
(t,2/2^12)-安全，最好的攻击是暴力破解。我们可以计算以下三种可能的攻击成功概率：
1.t=1.说明攻击者尝试了一把密钥并使用它ε=1/2^128的概率成功
2.t=2^128说明攻击者尝试了所有的密钥，其中一个一定是成功的，所以成功的概率ε=1
3.t=2^64此时成功概率为64ε=
2^-64，也就是说，当攻击者尝试所有密钥的一小部分时，成功的概率与尝试的密钥数量成正比。
从这个例子中以看出，对于1到2^n比特之间的任意t，n比特密钥的密码最多是
(t,t/2^n)-安全，因为无论密码有多强大，暴力破解总是可以成功的，实际上的关键是它能抵抗暴力攻击多久。
我们可以对(t,ε)-进一步简化了安全。我们说，当攻击成功至少需要t次时，它被称为t-在这里，我们实际上假设安全ε是接近1的概率，通过比特表示安全性，”n说明打破比特安全需要2^n次操作。
在操作次数之前，我们可以通过对数来确定其安全强度。假设需要1万次操作，其安全强度为log2 1000000=20比特。
其他因素
虽然比特安全在比较不同密码的安全强度时非常有用，但它没有提供足够的关于攻击成本的信息通过比特安全并不能解释任何问题。例如，两个密码都有128比特密钥和128比特安全，但第一个密码比第二个密码快100倍。事实上，暴力破解第二个密码2^第一个密码可用于128次
100x2^128次操作，如果以第一个快密码为标准，则需要破解慢密码
2^134.64次操作。
那么，这能说明第二密码比第一密码安全吗？当然不是，所以我们还需要考虑其他因素。
并行性
每次攻击需要两次攻击^第一次攻击只能串行，第二次攻击可以并行。假设我们有
2^16=65536个处理器可分为65536个独立任务，每个任务只需执行
2^40次操作即可。
也就是说，即使并行攻击和顺序攻击执行相同数量的操作，并行攻击也比顺序攻击快6536倍。
内存
这实际上与攻击中使用的空间成本有关，即攻击需要多次内存搜索、内存访问速度、访问数据大小等，这对时间至关重要。例如，在当前CPU从寄存器读取数据需要一个周期CPU从DRAM读数据需要100个周期。
预计算
这通常被称为攻击的离线阶段。这些操作只需执行一次，可以在以下攻击中重复使用。例如，彩虹表破解hash就是这一类，虽然预计计算彩虹表要花很多时间，但在实际攻击过程中很快就能实施。
目标数量
攻击目标越多，攻击面越大，攻击者可以获得更多关于密钥的信息。例如，需要2个目标是n比特的密钥^n第二次尝试二次尝试，才能找到正确的密钥，但如果攻击目标是多个n比特密钥，P，攻击者分别使用M个不同的密文n加密比特密钥。如果攻击者想破解M密钥中的每一个，仍然需要
2^n二次操作，但如果只需要破解M中的一个，那么只需要
2^n/M次操作。
也就是说，攻击成本随着目标数量增加而降低。
安全性证明
我们通常通过数学证明来评估密码算法的安全性。
在密码学中，它被称为证明安全。它可以证明密码方案至少与解决另一个已知的困难问题相同。只要困难问题仍然存在，方案就是安全的。这种证明方法被称为规则，它来自复杂的理论。
根据使用的困难问题类型，安全证明可分为数学问题和密码问题两类。
与数学问题有关
解决这类问题至少和解决一些数学问题一样困难。
密码学中一个着名的数学难题就是大数分解，RSA依赖它。RSA通过计算C=p^e mond n来加密明文p，其中，e和大数n=pq是公钥。
通过P=c^d mond n解密，其中d是和e、n私钥。
若能分解n，然后你可以从公钥中恢复私钥来破解RSA;如果有私钥，可以分解n。
换句话说，恢复RSA私钥和分解大数n是等价问题，这就是我们所说的合同。
与密码问题有关
这种方案与另一个密码方案进行比较，并证明第二个密码方案只有在第一个密码方案被破解时才能破解。这种方法通常用于证明对称密码的安全性。
然而，可以证明安全性并不适用于所有类型的算法。有些密码算法没有被证明是安全的，比如AES，AES一些众所周知的问题既不与数学问题或密码问题有关，我们仍然使用它们AES，因为很多专家试图破解它，但失败了。此时的安全性证明，我们已经成为灵感：经过多轮密码分析，密码算法的安全冗余仍然很高，我们相信它是安全的。
安全证明错误
我们已经说过安全证明很重要，但是密码大佬在证明安全证明的时候还是可能犯错的。OAEP证明是典型的例子。OAEP是一种使用RSA在许多应用程序中使用安全加密的方法，OAEP在给出的安全证明中，声称其抵抗选择密文攻击的有效期为7年，但后来发现证明是错误的，结论也是错误的。之后给出了新的证据，结论是OAEP选择密文攻击是安全的。
古典密码
古典密码是计算机发明前的密码，算法作用于字母而不是特征。最经典的古典密码是凯撒密码和维吉尼亚密码，这里不再介绍两者的基本知识背景。
凯撒密码
凯撒密码很容易破解，只需将密文向前移动3位即可得到响应。这样，安程度非常低，在古罗马时期经常被使用，不过实际上，前些年意大利警方还通过破译一种凯撒密码的变种抓到了黑手党头目。要增强凯撒密码的安全性，可以改变移位的位数，不过即使这么做了，攻击者最多尝试25次也就可以解密了。
维吉尼亚密码
维吉尼亚密码虽然比凯撒密码安全了很多，但还是容易被攻破。
举个例子，明文“THEY DRINK THE TEA"通过密钥”DUH“加密后的密文为”WBLBXYLHRWBLWYH“
第一步找出密钥的长度。我们注意到密文中WBL出现了2次，间隔9个字母，这意味着相同的3个字母被用同样的移位模式加密，所以密钥长度要么是9，要么能够整除9.而在英语中，THE是最常出现的3个字母的组合，所以我们可以认为这个重复的3个字母为THE,那么可能的密钥就是DUH.
第二步使用频率分析法找出字母分布的不均匀性。在英语中E是最常见的字母，所以如果密文中X出现次数最多，那么X对应的明文很可能就是E
工作原理
通过上面对两种古典密码的简单分析，我们已经知道密码的工作原理主要就是置换和模式。
置换是指能够变换一个对象的函数，且对每个对象都有唯一的逆（如凯撒密码中的3字母移位），而模式则是通过置换处理任意长度的消息的算法（如凯撒密码中的模式就是对每个字母施加相同的置换，而维吉尼亚密码中则是对不同位置的字幕施加不同的置换）
置换
并不是任意置换都是安全的，为了保证安全，置换需要满足：密钥确定置换，只要密钥保密，则置换保密。不同的密钥确定不同的置换。置换应当看起来随机，经过置换的密文应该没有显著的特征或者可识别的模式。
如果满足以上条件，则称这种置换为安全置换，但是这仅是建立安全密码的必要不充分条件，因为其还和模式相关。
操作模式
在说明操作模式为什么也是建立安全密码的必要条件之前，我们举个例子。
假设我们现在已经有一种安全的置换:A->X,B->M,N->L
那么对于香蕉的英文BANANA则有密文：MXLXLX
我们注意到，仅仅对明文中的所有字母施加相同的置换，在密文中会表现出一种重复的模式，攻击者分析这种模式，即使不能获得完整的信息，但是也能获得一部分信息，比如在这个例子的密文中我们看到在字母的第2，4，6位出现相同的字母，在3，5位出现了相同的字母，如果攻击者知道密文对应的是一种水果，那么攻击者很容易推测出这是BANANA，而不是ORANGE等其他水果。
从这个例子可以看出模式的重要性，模式通过对相同的字母施加不同的置换从而降低了明文中重复字母在密文中表现出的特征的风险。以维吉尼亚密码为例，如果密钥长度为N，那么就有N种不同的置换被施加在连续长度为N的字母串上，不过如果N并非足够长，我们就可以通过频率分析对其进行攻击。所以，如果维吉尼亚密码并应用于加密与密钥长度相同的明文，则频率分析就失效了。
一次一密
我们回过头来在看古典密码，它注定是不安全的，以我们现在的计算能力分分钟就能攻破它。我们知道，为了确定安全，置换应该看起来是随机的，最好的方法就是从所有置换的集合中随机选择每个置换。实际上可以选择的置换有很多，对于字母表，有26!，约等于2^88种置换，但是古典密码却只能使用其中的一小部分。
此外，置换不仅仅可以通过字母移位进行，还可以使用其他操作如乘法、加法等，这便是现代密码了，比如给定128比特密钥，然后进行一定比特位的操作来加密单个字母。
古典密码是绝对不安全的，那么有没有绝对安全的密码呢？
有的，那便是我们这里有介绍的一次一密。
一次一密有绝对的保密性，即使攻击者有无限的计算能力，也无法了解除明文长度以外的任何信息。
设明文为P,密钥为K，其长度与P相等，密文为C，则一次一密的加密过程为:
这个符号是异或运算符
解密则是
一次一密的关键在于密钥K只能使用一次。如果使用两次，设分别将明文P1,P2加密为C1,C2，则攻击者通过如下运算
可以得到P1,P2的异或结果，从而导致信息泄露（当攻击者这知道一条明文时，就可以通过上式结果推出另一条明文）
一次一密的不便之处在于密钥长度需要和明文一样，除了这个缺点外，是非常完美的。香农在上世纪40年代的时候就已经证明了其安全性。
香农指出，要实现完美的保密，一次一密的密钥必须至少与明文一样长，这样攻击者就无法在给定密文的情况下排除任何可能的明文。
这是非常直观的，如果K是随机的，那么C也是随机的，因为随机字符串与任何固定字符串异或得到的结果也是随机的。随机比特串第一位为0的概率为1/2，一个随机比特与另一比特异或的结果为0的概率为1/2，在任意长度的比特串上这一点都成立。换句话说，对于不知道K的攻击者而言，即使其拥有的时间和算力是无限的，但是对他而言C依然是随机的。
假设C长度为128比特，那么有2^128种可能的密文，对于攻击者而言,
就有2^128种可能的明文。如果密钥长度小于128，即可能的密钥少于
2^128种，那么攻击者可以排除某些明文。比如密钥为64比特，那么攻击者可以确定
2^64种可能的明文，这就排除了大多数的128位比特串。
此时攻击者可能不知道明文是什么，但是其知道明文不是什么，从而破坏了完美保密性。
现在我们已经知道，古典密码不安全，一次一密不实用，那么怎么设计安全和实用兼顾的密码呢？
攻击模型与安全性
如果一个密码体制是安全的，必须要定义好对应的攻击模型和安全性目标。攻击模型是关于攻击者可能与密码算法如何交互以及攻击者能力的一系列假设。在进一步分析之前，我们要先了解Kerckhoff原则，其指出，密码的安全性应仅取决于密钥的保密性，而不应取决于密码算法的保密性。
黑盒模型
如果攻击者只能看到密码模型的输入和输出，则称其为黑盒模型。黑盒模型中依据从最弱到最强的顺序列举如下：
唯密文攻击(ciphertext-only attackers,COA)：仅知道密文，但不知道相关的明文，也不知道有哪些可以选择的明文。此时攻击者是完全被动的，无法执行加密或解密操作
已经明文攻击(known-plaintext attackes,KPA):知道密文以及其对应的明文。此时攻击者也是被动的，不过它可以获得一系列明文-密文对，其中明文是随机选择的。
选择明文攻击(chosen-plaintext attacks,CPA):可以对选定的明文进行加密并得到对应的密文。此时的攻击者是主动的
选择密文攻击(chosen-ciphertext attackers,CCA):可以进行加密和解密。注意，这个模型只是表示攻击者可以介入加密和查看明文的情况，其解密的内容并不一定足以攻破系统。
灰盒模型
灰盒模型中，攻击者可以访问密码的实现，比如对于智能卡、嵌入式系统等，攻击者对其拥有物理访问权限，从而可以篡改算法的内部结构。这类模型中最典型的一类就是侧信道攻击。
侧信道攻击依赖于密码实现的信息源，攻击者观察密码实施时的模型特征，比如对于软件而言，可以观察其执行时间、错误消息、返回值、分支等，对于硬件而言，可以观察其功耗、电磁辐射等。
侵入式攻击也属于灰盒模型，其可以通过激光故障注入等方法改变芯片的行为。
安全目标
我们之前一直都没有明确定义密码的安全目标，只是笼统地说，能让攻击者对密码一无所示的就是好方法，实际上这是远远不够的。实际上，已经有两个常用的安全目标了。
1.不可区分性（indistinguishability,IND）：密文应与随机字符串没有区别。关于这一点，可以通过一个game说明。
设攻击者选定两个明文，收到两者的密文之一，攻击者无法分辨出这是哪个明文对应的密文
2.不可展性(non-malleability，NM)：给定密文C1,应该不可能创建另一个密文C2,使其对应的明文P2以有意义的方式与P1相关
IND-CPA
上述的安全目标仅在于具体的攻击模型结合时才有用，一般我们会写作GOAL-MODEL，如IND-CPA，表示的是针对选择明文攻击者的不可区分性。
以IND-CPA为例，这是最重要的安全概念之一，这也称为语义安全，只要密钥保密，密文就不会泄露任何有关明文的信息，当对同一明文加密两次时，加密系统会返回不同的密文。
IND-CPA的关键是随机化，我们还是以IND game为例。设攻击者选择两个明文P1,P2并接受两个明文之一对应的密文但是不知道它对应的是哪一个明文。在CPA模型中，攻击者可以执行加密以获得大C1=E(K,P1)，C2=E(K,P2)，如果加密不是随机的，那么攻击者查询Ci是否等于C1或C2就可以确定对哪个明文加密，从而赢得game。
实现IND-CPA最简单的方式就是使用确定性随机比特发生器(deterministic random generator,DRBG)，它可以返回给定的某些秘密值的随机比特：
E(K,R,P)=(DBRG(K||R)异或P,R)
上式中的R是每次加密随机选择的字符串，并与密钥K一起提供给DRBG,如果其生成的是真随机比特串，那么该密码的就是IND-CPA安全的。
这里我们只是简单分析了IND-CPA,这种GOAL-MODEL组合还有很多，比如NM-CPA,NM-CCA,IND-CPA,IND-CCA等，他们之间的一些关系是很明显的：IND-CCA蕴含着IND-CPA,NM-CCA蕴含着NM-CPA,因为CPA攻击者可以做的事情CCA攻击者也可以做。
以上我们都还是考虑了对称密码，对于非对称密码而言，由于任何攻击者都可以使用公钥加密，所以模型默认都是CPA的
弱密码算法
尽管我们已经介绍了相关的密码学概念，但是在实际中如果没有选择适当的密码算法、模型等，还是会造成严重的危害。
在GSM时代，手机通信的加密使用了A5/1的算法，通过建立查找表便可以对其进行攻击。在参考连接6中，可以看到详细的情况。
错误模型
即使密码使用者学习过安全模型，但还是有可能使用错误模型。很多通信协议确实使用了在CPA或CCA中安全的算法，但是实际中有些攻击是不需要涉及CPA中的加密查询或CCA中的解密查询的，比如对于Padding oracle attack而言，只需要进行有效性查询即可，在这种攻击方案下，只有密文对应的明文有适当的填充时，密文才有效，如果填充不正确，解密就会失败，攻击者可以通过观察解密是否失败进行攻击。
这种攻击方案，打CTF的师傅们应该很熟悉了，这里也不再进一步说明，有兴趣的话也可以参考《白帽子讲web安全》中的相关章节。
随机性
我们已经知道，在密码系统中，需要随机性来保证安全。可以说，其中的关键就在于随机比特的生成，其依赖于熵源以及从熵源产生随机比特的算法。
熵源由随机数发生器(RNG)提供，算法由伪随机数发生器(PRNG)提供。
RNG的作用是利用模拟世界中的熵在数字系统中生成不可预测的比特，比如从温度、噪声、静电测量中采样出比特信息，也可以从传感器，IO，系统日志等提取正在运行的OS中的熵。而PRNG的作用则是从一些真正随机的比特生成许多人为的随机比特。
总结来说，RNG以非确定的方式从模拟源生成真随机比特，不保证高熵，而PRNG以确定的方式从数字源生成看起来随机的比特，并具有最大熵。
在随机性方面可能出现哪些问题呢？
熵源不理想
一开始的Netscape浏览器的SSL代码是根据如下所示的伪码计算出128比特的PRNG种子的
这里的问题在于，PID和microseconds是可以被猜测的，如果可以猜到seconds，那么microseconds就只有10^6个可能的值
这是Log(10^6)的熵，大约20比特
另外，PID和PPID各15比特，所以本应有15+15=30比特的熵，但是在标注的1中，可看到，PPID和PID有3比特的重叠，所以只能产生15+12=27比特的熵
所以一共的熵为20+27=47比特，但是128比特的种子应该128比特的熵才对。这是熵源不理想的典型例子。
启动时熵不足
前些年有研究人员扫描整个互联网并从TLS证书和SSL主机中提取公钥，发现一些系统具有相同的公钥，私钥也非常相似。这是非常不合常理的，因为一般情况下，对于两个不同的大数n=pq，n'=p'q'，p与p'不相等，q与q'不相等，但是研究人员发现经常会有n与n'不相等的情况下，p=p'
后面发现这其中的原因是，尽管使用了不错的PRNG，但由于在初次启动时会尽早生成公钥，所以在收集到足够的熵之前，如果基础熵源选取相同，那么不同系统中的PRNG会产生相同的随机比特。
会生成相同的密钥，是由于以下伪码中的密钥生成方案造成的
如果两个系统的种子相同，运行上述代码后会生成相同的p,q，也就会生成相同的n。而只有研究人员发现的，在不同密钥中存在共享素数，则是因为在密钥生成过程中注入了额外的熵，如下所示
如果两个系统使用相同的种子运行上述代码，会生成相同的p，但是由于prng.add_entropy()注入了熵，会得到不同的q
对于n=pq，n'=pq'的情况，会有什么为题呢？
这里的关键在于，通过计算n和n‘的最大公约数就可以恢复出p。
非加密PRNG
PRNG很常见，在不涉及密码学的场合中也有其身影，我们可以分为加密PRNG和非加密PRNG。非加密PRNG的作用一般是用于生成良好均匀的分布，常用于科学模型、视频游戏中，它只关心比特之间的概率分布的质量，但是不关心它的可预测性，所以在密码程序中不应使用非加密PRNG.
但是实际上，很多编程语言中都用的是非加密PRNG，比如libc中的rand,drand48,PHP中的rand,mt_rand,Python中的random模运算，Ruby中的Random类等。最常见的非加密PRNG就是Mersenne Twister(MT)算法了，它可以产生没好友统计偏差的符合一致分布的随机比特，但是这些比特是可预测的，给定一些MT产生的一些比特，可以预测接下来会出现哪些比特。
MT算法比加密PRNG简单多了，其内部状态是一个由624个32比特字组成的数组S，其初始值为S1,S2,...S624,运行一次后变为S2,...S625...其中的Sk+624可以通过如下计算：
初始状态的比特可以表示为输出比特之间的异或，反之亦然。
如果将其应用于密码系统则会造成危害。
MediaWiki使用随机性生成诸如安全令牌、临时密码等信息，按理来说，此处的随机性应是不可预测的，但是旧版本的MediaWiki使用了非加密PRNG来生成这些令牌和密码，其源码部分如下
从代码中可以看到mt_rand()
这就是我们一直在说的Mersenne Twister，利用它攻击者就可以预测未来的令牌和临时密码。
参考
1.Shoup V. OAEP reconsidered[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2001: 239-259.
2.https://www.semanticscholar.org/paper/Understanding-brute-force-Bernstein/3bf374700ec98ea5d1b7658ec85c472f2fe4d952
3.https://link.springer.com/article/10.1007/s00145-003-0213-5
4.https://dl.acm.org/doi/10.1145/800070.802212
5.https://www.schneier.com/academic/archives/1998/01/cryptanalytic_attack.html
6.https://zh.wikipedia.org/wiki/A5/1
7.https://guidanceshare.com/wiki/Non-cryptographic_PRNG
8.https://www.mediawiki.org/wiki/Manual:Config_script/it
9.https://blog.cryptographyengineering.com/2012/03/09/surviving-bad-rng/
10.https://www.cs.umd.edu/class/fall2018/cmsc818O/papers/ps-and-qs.pdf征集原创技术文章中，欢迎投递
投稿邮箱：edu@antvsion.com
文章类型：黑客极客技术、信息安全热点安全研究分析等安全相关
通过审核并发布能收获200-800元不等的稿酬。
更多详情，点我查看！
体验靶场实操，戳“阅读原文”体验