麻省理工学院。 讲座课程＃6.858。 “计算机系统的安全性。” Nikolai Zeldovich，James Mickens。 2014年
计算机系统安全是一门有关开发和实施安全计算机系统的课程。 讲座涵盖了威胁模型，危害安全性的攻击以及基于最新科学研究的安全技术。 主题包括操作系统（OS）安全性，功能，信息流管理，语言安全性，网络协议，硬件安全性和Web应用程序安全性。
第1课：“简介：威胁模型”
第1 部分 /
第2 部分 /
第3部分第2课：“控制黑客攻击”，
第1 部分 /
第2 部分 /
第3部分第3讲：“缓冲区溢出：漏洞利用和保护”
第1 部分 /
第2 部分 /
第3部分讲座4：“特权分离”，
第1 部分 /
第2 部分 /
第3部分讲座5：“安全系统从何而来？”
第1 部分 /
第2部分讲座6：“机会”
第1 部分 /
第2 部分 /
第3部分讲座7：“本地客户端沙箱”
第1 部分 /
第2 部分 /
第3部分讲座8：“网络安全模型”
第1 部分 /
第2 部分 /
第3部分讲座9：“ Web应用程序安全性”
第1 部分 /
第2 部分 /
第3部分讲座10：“符号执行”
第1 部分 /
第2 部分 /
第3部分第11课：“ Ur / Web编程语言”
第1 部分 /
第2 部分 /
第3部分讲座12：网络安全性
第1 部分 /
第2 部分 /
第3部分讲座13：“网络协议”
第1 部分 /
第2 部分 /
第3部分第14课：“ SSL和HTTPS”
第1 部分 /
第2 部分 /
第3部分第15课：“医疗软件”
第1 部分 /
第2 部分 /
第3部分第16课：“侧面通道攻击”
第1 部分 /
第2 部分 /
第3部分 受众：您使用唐津法吗？
教授：是的，这是一种智能乘法，不需要四个计算阶段。 Karatsuba方法在.601课程中讲授，或者今天如何指定？
观众： 042。
教授： 042，非常好。 是的，这是一个非常好的方法。 几乎每个密码库都使用它。 对于那些不是我们学院毕业生的人-我之所以这样说是因为我们这里有研究生-我将在黑板上写有关Karatsuba方法的信息。 在这里，您需要计算三个值：
a
1 b
1（a
1 -a
0 ）（b
1 -b
0 ）
a
0 b
0因此，您执行了3次乘法运算，而不是4次乘法运算，事实证明您可以从这3次乘法运算结果中恢复此值a
1 b
0 + a
0 b
1 。
做到这一点的特殊方法是……让我用另一种形式表示。
因此，我们将拥有：
（2
64 + 2
32 ）（a
1 b
1 ）+
（2
32 ）（-（a
1 -a
0 ）（b
1 -b
0 ）
（2
32 +1）（a
0 b
0 ）
这不是很清楚，但是如果您计算出细节，则最终使自己确信这三行中的该值等于ab，但同时会将计算结果减一。 我们将其应用于更多的乘法的方法是，您递归地继续下去。 因此，如果您具有512位值，则可以将它们拆分为256位乘法。 您使用Karatsuba方法递归地执行三个256位乘法。 最后，您的计算将取决于机器尺寸，并且可以通过一条机器指令进行处理。
那么定时攻击在哪里？ 这些家伙如何使用唐津乘法？ 事实证明，OpenSSL担心您可能必须执行两种类型的乘法。
第一个是将两个大小近似相同的大数相乘。 当我们执行模幂运算时，这会发生很多次，因为我们将相乘的所有值的大小约为512位。 因此，当我们将c乘以y或平方时，我们将两个大小大致相同的东西相乘。 在这种情况下，Karatsuba方法很有意义，因为它减少了平方数的大小约1.58倍，从而大大加快了计算过程。
第二种乘法是OpenSSL将两个大小相差很大的数字相乘：一个很大，另一个很小。 在这种情况下，您也可以使用Karatsuba方法，但是它的工作速度比原始乘法慢。 假设您将512位数字乘以64位数字，则必须将第一个数字的每一位提高为64的幂，从而导致进程速度降低2n而不是n / 1.58加速。 因此，这些使用OpenSSL的人试图做得更聪明，而问题就从这里开始。
他们决定在有效的唐津法和小学乘法之间动态切换。 他们的启发如下。 如果您乘以的两个数字由相同数量的机器字组成，或者至少具有与32位单元相同的位数，则使用Karatsuba方法。 如果两个数字的大小相差很大，则进行平方运算或直接简单，普通乘法。
在这种情况下，您可以跟踪切换到另一种乘法的方式。 由于切换时刻并非一无所有，因此在此之后，现在是否需要更多的时间来进行乘法运算还是要比以前少得多将是显而易见的。 研究人员利用这种情况利用计时方法来组织攻击。
我想我已经完成了向大家介绍人们在实践中实施RSA时使用的所有奇怪技巧。 现在，让我们尝试将它们放在一起并在整个Web服务器中使用它们，以找出如何从输入网络数据包中“捏”我们感兴趣的位。
如果您还记得HTTPS上的讲座，则Web服务器具有一个秘密密钥。 他使用此密钥来证明自己是HTTPS或TLS上所有证书的正确所有者。 这是由于以下事实：客户端发送了一些随机选择的位，这些位使用服务器的公钥加密，服务器使用TLS协议解密此消息。 并且，如果检查了消息，则这些随机位用于建立通信会话。
但是在我们的情况下，将不检查此消息，因为它将以特殊方式创建，并且当发现额外的位不匹配时，服务器将在完成解密消息后立即返回错误。
这就是我们在这里要做的。 服务器-您可以假定它是具有开放SSL的Apache-服务器将从客户端收到一条消息，该消息被视为带有客户端创建的加密文本或某些假设的加密文本。 我们对密文c所做的第一件事是使用→（c
d mod n）= m的公式对其进行解密。
如果您还记得第一个优化，我们将应用中文余数定理并将文本分为两部分：一个部分通过mod p计算，另一部分通过mod q计算，然后将结果合并。 首先，取c并用两个量表示它：第一个称为c
0 ，它将等于mod q，第二个称为c
1 ，并且它将等于c mod p。 然后，我们将对d mod p计算c，对于d mod q计算c。
接下来，我们将切换到蒙哥马利视图，因为这将使我们的乘法非常快。 因此，SSL将与您的数字相关的下一件事情是计算c
0 '，它等于c
0 R mod q并在下面对值c1进行相同操作，我不会写下来，因为它看起来相同。
现在我们已转换为蒙哥马利形式，我们终于可以执行乘法了，这里我们将使用“滑动窗口”技术。 一旦得到c
0 '，我们就可以简单地将c
0 '提高到mod q中d的幂。 在这里，由于我们计算了d的该值，因此我们将对d的位使用“滑动窗口”，并且根据操作数的大小，我们还将使用Karatsuba方法或通常的乘法。
因此，如果事实证明该值c
0 '和先前获得的平方结果大小相同，则使用Karatsuba方法。 如果c
0 '非常小，并且以前的相乘结果很大，那么我们将以通常的方式平方和相乘。 在这里，我们使用“滑动窗口”和Karatsuba方法而不是常规乘法。
同样在此阶段，还会出现其他减少情况。 因为每次相乘，额外的减少将与我们对mod q的幂的乘积成正比，即（c
0 '）
d的值 。 在此，通过公式的简单连接，额外减少的可能性将与值c 0'mod q除以2R成正比。 正是在这个地方出现了一些影响时序的东西。
实际上，有两种可能的效果：使用Karatsuba方法而不是普通的乘法，以及出现您将要使用的其他缩写。
稍后，您将看到如何使用它。 现在，当您获得模q的结果并将获得模p的相似结果时，您最终可以在顶部和底部重新组合这两部分，并使用CRT（中文余数定理）。
结果是您从CRT获得的收益...对不起，我想我们需要首先将其从蒙哥马利表格中转换回来。 因此，在重组之前，我们将上部转换为表达式（c
0 '）
d / R mod q并返回值cd mod q。 在下部，我们相应地获得cd mod p。
现在，您可以使用CRT获得c
d mod n的值。 抱歉，字体太小，我的黑板不够用。 关于相同的事情，我们在下面得到
1 ，我们最终可以得到结果，即消息m。
因此，服务器接收它接收的传入数据包，通过整个流水线运行它，执行该流水线的两个部分，并以等于cd mod m的解密消息m结尾。 然后，他将检查此帖子的填充。 在特定攻击的情况下，我们创建的方式实际上与此添加项不匹配。 我们为启发式算法选择了值c，该启发式算法不使用正确的填充加法来加密真实消息。
因此，附加组件未通过测试，服务器将需要记录错误，将错误消息发送给客户端并断开连接。 因此，我们将测量服务器通过此管道传递消息所花费的时间。 您对服务器处理消息并结合所有这些优化的过程有任何疑问吗？
观众：我认为指标c的值存在误差。
教授：是的，您是对的，我要添加索引0，这里应该是c
0 d mod q。
受众：当您用R mod q除时，是否存在为使低位进一步减小到零而应该添加多少q的假设？
教授：是的，您是对的，在最后阶段（c
0 '）
d / R mod q可能还会有其他减少。 因此，我们应该以正确的方式进行R的除法运算，并且可能应该执行与此处的Montgomery归约法相同的操作（当我们除以R时）以将值转换回去。 由于在计算开始时尚不清楚应添加多少q，因此我们使用选择方法，销毁低位零，然后再次进行mod q，并可能进行额外的减少。 您是完全正确的，在这种情况下，它与蒙哥马利乘法的每一步的R mod q完全相同。
那么，您如何利用这一优势呢？ 攻击者如何通过衡量完成操作所需的时间来解决服务器的密钥？ 这些家伙有一个计划，该计划基于一次猜测一个私钥位。 我们可以假设秘密密钥是加密指数d，因为您知道e和n，所以这是公共密钥。 您唯一不知道的是d。
实际上，由于这种攻击相当复杂，因此他们不会直接猜测d的值。 取而代之的是，无论这两个量中的哪一个，它们都考虑q或p。 一旦您猜出p或q的重要性，就可以计算n = pq。 然后，如果您知道p和q的值，则可以计算我们前面讨论的函数φ。 这将使您能够从e的值中获得d的值。 因此，n值的这种分解非常重要；必须将其保密以确保RSA安全。
因此，实际上，这些人打算通过分析该流水线的时序来猜测q值。 他们在做什么呢？ 他们仔细选择c值的初始值，并测量其通过服务器管道的时间。
特别是，此攻击分为两部分，您必须采取一些初始步骤来猜测前几位。 然后，只要有了前几位，就可以猜测下一位。 因此，让我不再详细告诉您他们如何猜测前几位，因为考虑到他们如何猜测下一位更有趣。 如果有时间，我们将返回到演讲文章中如何描述几个初始位的猜测。
因此，假设您假设g关于此q值中的哪些位。 让该值由以下位组成：g = g
0 g
1 g
2 ...依此类推。 相反，它甚至不是g，而是q的实数，所以让我这样重写它：g = q
0 q
1 q
2 ...。 我们认为这些q是高位，并且我们正在尝试猜测越来越低的位。 假设我们知道直到位qj的q的值，然后全为零。 您不知道其余的是什么。
这些家伙试图将这个猜想g注入我们管道的这个位置：（c0'）d mod q。 因为这是使用两种类型的优化的地方：用Karatsub方法代替通常的乘法，并且根据c
0 '的值使用不同数量的附加缩写。 实际上，他们试图在流水线的这个位置引入两个不同的猜测：第一个看起来像g = q
0 q
1 q
2 ... qj 000 ... 0000，第二个看起来叫g
high ，它由相同的高位组成，但是取而代之在末尾的所有零中，有一个单位表示高位，然后再跟零：
g = q
0 q
1 q
2 ... qj 100 ... 0000
这如何帮助这些家伙了解正在发生的事情？ 有两种方法可以做到这一点。 假设我们的猜测g等于值c
0 '。 我们可以假设这些g和g
high对应于左板上给出的值c
0 '。 实际上，这样做非常简单，因为c
0 '很容易从加密的输入值c
0向后计算，只需将其乘以R。
因此，为了猜测值（c
0 '）
d ，他们只需要进行猜测，即猜测g，然后将其除以R，即除以512 mod即可。 然后他们将其引入，服务器将其乘以R并继续我们的管道方案中描述的过程。
因此，假设我们能够将我们选择的特定整数值放在正确的位置。 那么，到d mod q的计算时间c
0 '是多少？
q适用于此图片有两个可能的选项。 q可能在g和g
high的这两个值之间，因为q的下一位为0。因此，此值-qj之后的第一个0-将小于q，但是此值-q之后的1-将大于q q。 如果q的下一位为0，则会发生这种情况；如果q的下一位为1，则q可能高于这两个值。
现在我们可以说，如果q位于两个值之间，或者q位于两个值的上方，那么这两个值的解密时间将是多少。
让我们看一下q位于上方的情况。 在这种情况下，一切都差不多。 由于这两个值均小于q，因此mod q中这些事物的值将大致相同。 由于这个额外的位，它们略有不同，但是大小大致相同。 而且，额外缩减的数量，额外缩减也可能不会有太大差异，因为它与c0'mod q的值成比例。 对于小于q的g和g
高值，它们几乎都是相同的。 它们中的任何一个都不会超过q，也不会引起大量额外的减少，因为对于q大于这两个猜测的值，唐津法相对于普通计算的数量将保持不变。 根据这种关系，服务器将平等地处理g和g。 因此，服务器将为这两个值做出相同数量的附加缩写。 因此，如果您发现服务器花了相同的时间来响应这些猜测，那么您可能应该假设此时的g
高值中确实有1。
另一方面，如果q位于这两个值之间，则存在两种可能导致切换和时序变化的情况。 一件事情是，由于g
high比q稍大，因此额外切割的数量将与c 0'mod q成正比，这非常小，因为c
0 '是q加这100个额外位序列中的几个位... 00 因此，额外减少的数量将更加引人注目，并且一切都会开始更快地发生。
, , , , , : «, !». , g c
0 ' , q, , g
high q, g
high mod q . , . – , , .
c
0 ' mod q. c
0 g
high , q, , g q. , . , , . , 32- , .
, 32- , , , . , . 32 , , - . , , 32, , , , .
, , , . , q 1, , q 0, , g
high q , , .
. , . , . , , 1-2 . , , Ethernet.
, . . , 7 . , , -, , ?
: ?
: , , , , , . , .
, , 7 , , 7 . 7 g, 7 g + 1, g + 2 7 g + 400. g, g, , 7 400, ?
: , , ?
: , , , — (c
0 ')
d . . , , , mod p. , , . , g, 1, 2, 3, , .
, , – 100…00. , mod p, , mod p . « », , (c
0 ')
d , . ?
: , ?
: - , q. , q, , , .
: c
0 '?
: c
0 ', c, c
0 ' R mod n.
, «» , c
0 = mod q, c
0 = ((c
0 ' R
-1 ) mod n) mod q. R, R. c
0 ', (c
0 ')
d mod q. , , , , R. , R = 2
512 . , .
: mod p ?
:也就是说，您不知道p是什么，但是您想随机定义它？如果成功，那么您将做得很好！好吧，下周我们将开始讨论其他问题。该课程的完整版本可在此处获得。感谢您与我们在一起。 你喜欢我们的文章吗？ 想看更多有趣的资料吗？ 通过下订单或将其推荐给您的朋友来支持我们，
为我们为您发明的入门级服务器的独特模拟，为Habr用户提供
30％的折扣： 关于VPS（KVM）E5-2650 v4（6核）的全部真相10GB DDR4 240GB SSD 1Gbps从$ 20还是如何划分服务器？ （RAID1和RAID10提供选件，最多24个内核和最大40GB DDR4）。
VPS（KVM）E5-2650 v4（6核）10GB DDR4 240GB SSD 1Gbps至12月免费，在六个月内付款时，您可以在此处订购。戴尔R730xd便宜2倍？ 仅
在荷兰和美国，我们有
2台Intel Dodeca-Core Xeon E5-2650v4 128GB DDR4 6x480GB SSD 1Gbps 100电视（249美元起） ！ 阅读有关
如何构建基础架构大厦的信息。 使用价格为9000欧元的Dell R730xd E5-2650 v4服务器的上等课程？