首页 > 其他分享 >52 Things: Number 42: Look at your C code for Montgomery multiplication above; can you determine whe

52 Things: Number 42: Look at your C code for Montgomery multiplication above; can you determine whe

时间:2024-04-13 13:46:19浏览次数:28  
标签:information code Look 泄漏 attacks leak ulo DPA SPA

52 Things: Number 42: Look at your C code for Montgomery multiplication above; can you determine where it could leak side channel information?

52件事:数字42:看看上面蒙哥马利乘法的C码;你能确定它可能在哪里泄露侧通道信息吗?   This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this post (spoiler alert!) we enumerate various flavours of side-channel attacks.
这是一系列博客文章中的最新一篇,旨在解决“每个博士生都应该知道的52件事”做密码学:这是一组问题,旨在让博士生在第一年结束时了解他们应该知道什么。在这篇文章(剧透提醒!)中,我们列举了各种各样的侧面渠道攻击。


A few months ago (back in March) you may remember I posted for the 23rd of the 52 things in this series (can be found here). The article was entitled “Write a C program to implement Montgomery arithmetic” and contained parts of an implementation to do this. In this article we are going to look at this implementation and see how it could leak information to give us a practical idea of what leakage may look like.
几个月前(早在三月份),你可能还记得我为本系列52件事中的23 rd 发帖(可以在这里找到)。这篇文章的标题是“编写一个C程序来实现Montgomery算术”,并包含了实现这一点的部分内容。在这篇文章中,我们将研究这个实现,看看它是如何泄漏信息的,从而为我们提供一个关于泄漏可能是什么样子的实用想法。   Before progressing however I would like to remind you of my last post which examined the difference between SPA and DPA attacks. You will remember from there that SPA attacks use a single or very few traces and work by spotting trends in the pattern (such as timing or instruction sequences) while DPA attacks use many traces and aim to derive intermediate vales of an algorithm and thus the secret information by using hypotheses of the secret data and a correct leakage model. Before looking at the Montgomery multiplication algorithm then it is worth stating from the outset that if hypotheses of secret data and corresponding leakage models can be derived for the algorithm, DPA style attacks can be used to derive intermediate values which will mean that the algorithm will leak data being processed. If this data is therefore secret, we can already say that this algorithm is going to leak through using DPA style attacks.
然而,在继续之前,我想提醒您我的上一篇文章,该文章研究了SPA和DPA攻击之间的区别。从那时起,您将记住,SPA攻击使用单个或极少数跟踪,并通过发现模式中的趋势(如时序或指令序列)来工作,而DPA攻击使用许多跟踪,旨在通过使用秘密数据的假设和正确的泄漏模型来推导出算法的中间值,从而导出秘密信息。在研究Montgomery乘法算法之前,值得从一开始就指出,如果可以为该算法导出秘密数据的假设和相应的泄漏模型,则可以使用DPA型攻击来导出中间值,这意味着该算法将泄漏正在处理的数据。因此,如果这些数据是秘密的,我们已经可以说,该算法将通过使用DPA类型的攻击而泄漏。   As mentioned in my last post however, we know that DPA style attacks are significantly harder than SPA as they require the ability to form hypotheses of secret data, more traces and their success will depend significantly on the noise produced by the device. The question then is how our implementation will leak using SPA attacks where things such as timing or sequences of instructions being executed can be exploited. To understand this lets look at each of the four stages I presented for the algorithm last time separately. Things we are interested in are things such as conditional statements or loops as this may be exploited for timing attacks.
然而,正如我在上一篇文章中所提到的,我们知道DPA式的攻击比SPA更难,因为它们需要形成秘密数据假设的能力,更多的痕迹,并且它们的成功将在很大程度上取决于设备产生的噪声。然后的问题是,我们的实现将如何使用SPA攻击进行泄漏,在SPA攻击中,执行的指令的时序或序列等内容可能会被利用。为了理解这一点,让我们分别来看一下我上次为算法提出的四个阶段中的每一个。我们感兴趣的是条件语句或循环,因为这可能会被用于定时攻击。

1. The GCD Operation 1.GCD操作

This section uses the binary extended gcd operation to find the integers r-1 and m’ such that rr-1 = 1 + mm’. If we assume therefore that our algorithm for the extended gcd operation runs in constant time then we can assume that this operation is safe.
本节使用二进制扩展gcd运算来查找整数r -1 和m',使得rr -1 =1+mm'。因此,如果我们假设我们的扩展gcd操作的算法在恒定时间内运行,那么我们可以假设这个操作是安全的。

 

2. Transform the Multipliers
2.变换乘法器

This stage computes abar = ar mod m and bbar = br mod m and therefore as this is a simple operation, it is unlikely to leak provided the operations and instructions required (such as the multiplier) run in constant time.
此阶段计算abar=ar mod m和bbar=br mod m,因此由于这是一个简单的操作,如果所需的操作和指令(如乘法器)在恒定时间内运行,则不太可能泄漏。

 

3. Montgomery Multiplication
3.蒙哥马利乘法

This is the main section of the algorithm. The first sub-stage to of the function is to calculate t = abar*bbar and in the same way as the previous two stages we can assume no leakage.
这是算法的主要部分。函数的第一个子阶段是计算t=abar*bbar,与前两个阶段相同,我们可以假设没有泄漏。   The second stage however is the computation of u = (t + (tm’ mod r)m)/r and it is here that we encounter two conditional statements the first i:
然而,第二阶段是u=(t+(tm'mod r)m)/r的计算,并且在这里我们遇到两个条件语句,第一个i:   if (ulo < tlo) uhi = uhi + 1;
如果(ulo<tlo)uhi=uhi+1;
  which allows for a carry as we have a 128 bit implementation on a 64 bit architecture (see article for more information). Observing the time of execution or a power trace will therefore give insight into whether or not this conditional was executed and therefore whether or not these ulo was higher than tlo.
这允许进位,因为我们在64位体系结构上有128位的实现(有关更多信息,请参阅文章)。因此,观察执行时间或功率跟踪将深入了解该条件是否被执行,从而了解这些ulo是否高于tlo。
  Again we have a second conditional statement which tests if u >= m.
再次,我们有第二个条件语句,它测试u是否>=m。
  if (ov > 0 || ulo >= m)
如果(ov>0||ulo>=m)
ulo = ulo - m;
ulo=ulo-m;
  This will also reveal whether either of these conditions is true and thus leak information about the values being worked on
这也将揭示这些条件中的任何一个是否属实,从而泄露有关正在处理的值的信息.

4. The Inverse Transformation
4.逆变换

Here we compute ur-1 mod m which is the product of a and b modulo mIn the same way as stages 1 and 2 did not leak we can also say that this stage will not leak.
在这里,我们计算ur -1 mod m,它是a和b模m的乘积。以与阶段1和阶段2没有泄漏相同的方式,我们也可以说这个阶段不会泄漏。

标签:information,code,Look,泄漏,attacks,leak,ulo,DPA,SPA
From: https://www.cnblogs.com/3cH0-Nu1L/p/18107530

相关文章

  • [CF1954] Educational Codeforces Round 164 (Rated for Div. 2) 题解
    [CF1954]EducationalCodeforcesRound164(RatedforDiv.2)题解A.PaintingtheRibbon最优策略是染\(\lceil\dfrac{n}{m}\rceil\)个颜色,然后Bob会把剩下的都染成这个颜色voidwork(){intn,m,k,c;cin>>n>>m>>k;c=(n+m-1)/m;......
  • [CF1942] CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes! A~E 题解
    [CF1942]CodeTONRound8(Div.1+Div.2,Rated,Prizes!A~E题解A.FarmerJohn'sChallenge只有两种情况,一种是单调递增,这时\(k=1\),另一种是所有数都相同,这时\(k=n\)。B.BessieandMEX首位可以确定,然后从前往后增量构造\(p\)即可。voidwork(){cin>>......
  • 基于codesys的看门狗操作
    循环任务CODESYS支持多种任务类型,其中最为常见的任务类型是循环任务,循环任务是指任务函数被每隔一段时间调用一次,而且任务应该在任务间隔时间内执行完。但是如果任务没有在规定的时间内执行完怎么办呢?看门狗对于只有打工命的工控技术来说,是永远没有躺平一说,于是“祭出”看门狗......
  • LeetCode四则
    1.给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例1:输入:nums=[2,7,11,15],targ......
  • atcoder beginer 347 (abc347) D E 题解
     D就是二进制下,哪些位置有重合(两个1),哪些位置没有重合(1个1,1个0),剩下的都是0。xor的结果<2^60,就是小于60位(二进制下)。注意要有要求两个数需要是2^60,于是要有大小的判断,因为有的a,b会2^60,但是按照题目要求,这个情况不行。比如xor的结果,60位都是1,然后a、b各有60个1,那么需要有30个1......
  • atcoder beginer 348 (abc348) D E F 题解
     E非常经典的树上操作(树上DP)。父节点到某个子节点,值是如何变化的。1#include<cstdio>2#include<cstdlib>3#include<cstring>4#include<cmath>5#include<cstdbool>6#include<string>7#include<algorithm>8#include<iost......
  • vscode配置gdb调试外部程序
    有一个工程是用qtcreator编译的我现在用vscode远程访问的这个工程,目前只能在vscode界面编辑代码。编译需要在qtcreator下面。刚开始也只能在qtcreator下面调试(debug,打断点)目前在vscode里面安装了gdb工具之后,就可以直接调试qtcreator编译好的二进制文件了。而且可以打断点......
  • Python程序员Visual Studio Code指南5调试
    5调试当运行程序时终端输出错误时,可以参考编辑器中的"问题"面板来解决遇到的问题。不过,并非所有错误都会导致错误。可能出现的情况是,程序执行成功,但输出结果与预期不同。出现这种情况时,下一步就是找出程序中的错误。这个过程被称为调试。您可以尝试通过注释代码行(从而禁止代码......
  • 使用 flash_download_tool 下载 Vscode PlatformIO 开发 ESP32 的 bin 文件
    一言蔽之:先使用PlatformIO的命令找到PlatformIO是怎么烧录的,然后照葫芦画瓢即可。前提,VScode已经能够烧录固件了,使用PlatformIO打开所需的项目。打开VScode终端执行:piorun-v-tupload执行了之后,PlatformIO就开始编译固件并上传了,找到关键性的东西<lambda>(["up......
  • WDS故障排除 Script:X:\Deploy\Scripts\LiteTouch.wsf Code:80040049
    简介:不知道是因为微软换了咖喱程序员还是怎么了,居然有发布错误。还偷摸放GitHub的微软文档。memdocs/memdocs/configmgr/mdt/known-issues.mdatmain·MicrosoftDocs/memdocs(github.com)X:\Deploy\Scripts\LiteTouch.wsfScript:X:\Deploy\Scripts\LiteTouch.wsfCode......