第四十二个知识点:看看你的C代码为蒙哥马利乘法,你能确定它可能在哪里泄漏侧信道路吗?

时间:2022-01-05 21:15:51

第四十二个知识点:看看你的C代码为蒙哥马利乘法,你能确定它可能在哪里泄漏侧信道路吗?

几个月前(回到3月份),您可能还记得我在这个系列的52件东西中发布了第23件(可以在这里找到)。这篇文章的标题是“编写一个C程序来实现蒙哥马利算法”,并包含了实现的一部分。在本文中,我们将研究这个实现,并了解它如何泄漏信息,从而对泄漏的情况有一个实际的了解。

在继续之前,我想提醒你一下我的上一篇文章,它研究了SPA和DPA攻击的区别。从那里你会记得,SPA攻击使用一个或很少的痕迹的发现趋势和工作模式(如时间或指令序列)而DPA攻击使用很多的痕迹,旨在推导算法的中间值,因此秘密信息通过使用机密数据和正确的泄漏模型的假设。之前看蒙哥马利乘法算法从一开始就那么值得说明的是,如果假设的秘密数据和相应的泄漏模型可以推导出算法,DPA攻击方式可以用来得到中间值将意味着该算法将泄漏被处理的数据。因此,如果这些数据是秘密的,那么我们已经可以说,通过使用DPA风格的攻击,这个算法将会泄漏。

然而,正如我在上一篇文章中提到的,我们知道DPA风格的攻击比SPA要难得多,因为它们需要形成秘密数据假设的能力,更多的痕迹和它们的成功将在很大程度上取决于设备产生的噪音。接下来的问题是,我们的实现将如何被利用正在执行的指令的时间或顺序等内容,实现SPA泄露攻击。为了理解这件事,我将算法分成了四个阶段,我们感兴趣的是条件语句或循环之类的东西,因为它们可能被用于时间侧信道攻击。

1.GCD操作

这里我们进行了一个GCD操作,为了计算\(r^{-1}\)和\(m\)满足\(rr^{-1} = 1 + mm^{'}\)。如果我们假设因此,如果我们假设扩展gcd操作的算法在恒定时间内运行,那么我们可以假设该操作是安全的。

2.将乘数转换到蒙哥马利空间

这个阶段计算\(abar = ar \mod m\)和\(bbar = br \mod m\),因此这是一个简单操作,常数运行时间不会泄露信息。

3.进行蒙哥马利乘法运算

条件语句会泄露侧信道信息!

首先指令if (ulo<tlo) uhi=uhi+1会让我们在特定平台进行实现的时候,通过观察执行时间或功率跟踪,可以了解是否执行了这个条件,以及这些ulo是否高于tlo。

另外指令if (ov>0||ulo>=m) ulo=ulo-m,这回暴露条件是否达到,然后泄露内部值的信息。

4.取逆操作

这里我们计算了\(ur^{-1} \mod m\) ,实际上就是\(ab \mod m\)。就像阶段1和2没有泄漏一样,我们也可以说这个阶段不会泄漏。