定时攻击和良好的编码习惯

#1 楼

TL; DR位于底部。

定时攻击的一般概念如下：


秘密数据对软件的定时产生影响衡量时间安排
攻击者计算影响力$ ^ {-1} $以获取秘密数据

基本弱点：if( secret )


可利用基础对定时攻击敏感的代码如下所示：

if(secret)
{
  do_A();
}
else
{
  do_B();
}

想法是，计算A的时间与计算B的时间不同。因此，知道了这一区别，您可以计算出秘密。

让我们看一下更接近真实代码的以下代码。
这是RSA解密的核心操作：$ a ^ d \ bmod n $，具有密钥$ d $：如果密码的值为if，则将执行(exp[i] >> j) & 1。如果密码的值是1，则将不执行任何操作。因此，根据密码的不同，执行时间也会有所不同。

让我们对代码进行一些改进：

typedef unsigned long long uint64;
typedef uint32_t uint32;

/* This really wants to be done with long integers */
uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      if((exp[i] >> j) & 1)
        r = ((uint64)a*r) % mod;
    }
  }
  return r;
}

在这段代码，您可能会认为，因为我们在依赖秘密r = ((uint64)a*r) % mod的0语句的两个分支上执行相同的操作：


1赋值。
1乘法
1模运算

执行任何一个分支的时间都将是相同的，对吗？

好...否。因为... if是一个无效变量，并且编译器当然会注意到它，并将优化代码。 “此变量无用，将其清除！”。因此，编译后的代码将与您之前遇到的计时漏洞之前的代码相同。 />

现代CPU具有分支预测。
和指令缓存。

因此，我们需要摆脱这种分支弱点。

删除分支

如何删除类似这样的分支：

typedef unsigned long long uint64;
typedef uint32_t uint32;

/* This really wants to be done with long integers */
uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1, t;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      if((exp[i] >> j) & 1)
        r = ((uint64)a*r) % mod;
      else
        t = ((uint64)a*r) % mod;
    }
  }
  return r;
}

我们将其替换为以下内容：

if (s)
  r = do_A()
else
  r = do_B()

由于我们需要快速的代码，因此可以将(exp[i] >> j) & 1扩展为全一个/全-零掩码，并使用XOR代替加法，并使用AND代替乘法。

所以回到我们的平方乘：其中t（作为条件移动）是同名的汇编程序指令（不使用任何预测）或定义为以下内容：

r = s * do_A() + (1 - s) * do_B()

另一个缺点： s


想法如下，处理器的缓存包含表。并且由于可以在同一时间范围内访问缓存中的所有内容，因此您的秘密是安全的。

uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1,t;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      t = ((uint64)a*r) % mod;
      cmov(&r, &t, (exp[i] >> j) & 1);
    }
  }
  return r;
}

这是正确的……如果仅运行此代码。但是，您总是在CPU上同时运行其他代码，因此表的某些部分如下所示：

/* decision bit b has to be either 0 or 1 */
void cmov(uint32 *r, const uint32 *a, uint32 b)
{
  uint32 t;
  b = -b; /* Now b is either 0 or 0xffffffff */
  t = (*r ^ *a) & b;
  *r ^= t;
}

我们假设攻击者具有控制缓存的哪一部分损坏。因此，如果cmov是table[secret]，那么您将立即从缓存中得到响应。但是，如果secret是0x0001，则缓存无效。因此，CPU将必须从堆栈/存储器中重新加载该值。这会花费更长的时间，因为我们存在时间上的差异...我们可能会出现时间上的攻击。<​​br />
反制措施非常复杂，我将不再赘述。

参考资料

答案的大部分来自这张幻灯片：彼得·施瓦贝（Peter Schwabe）在2016年Crypto Summer School-克罗地亚的定时攻击和对策。

一些有趣的读物：

Osvik，Shamir，Tromer，2006：
缓存攻击和对策：以AES为例。
http://eprint.iacr.org/2005/271/

AlFardan，Paterson，2013年：幸运的十三：打破TLS和DTLS记录协议。
http：//www.isg .rhul.ac.uk / tls / Lucky13.html

Yarom，福克纳，2014年：冲洗+重新加载：高分辨率，低噪声，L3缓存侧通道攻击。
http： //eprint.iacr.org/2013/448/

Benger，van de Pol，Smart，Yarom，2014年：“哦，啊……只是一点点”：少量的旁通道可以走很长的路。
http://eprint.iacr.org/2014/161/

Bernstein，2005年：对AES的缓存定时攻击。
http：/ /cr.yp.to/papers.html#cachetiming

Brickell，2011年：提高平台安全性的技术。
http://www.chesworkshop.org/ches2011/presentations/Invited% 201 / CHES2011_Invited_1.pdf

伯恩斯坦，施瓦贝，2013年：警告语。
https://cryptojedi.org/peter/data/chesrump-20130822.pdf
https ：//cryptojedi.org/peter/data/cacheline.tar.bz2

Yarom，Genkin，Heninger，2016：CacheBleed：A Timing Atta参见OpenSSL恒定时间RSA
https://ssrg.nicta.com.au/projects/TS/cachebleed/

汉堡，2009年：使用矢量置换指令加速AES。 > http://mikehamburg.com/papers/vector_aes/vector_aes.pdf

Biham，1997年：“一种快速的新DES在软件中的实现。”
http：//www.cs。 technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1997/CS/CS0891

TL; DR

如果您阅读并跳过了整个答案，那么就意味着您肯定不想编写加密代码。

如果您确实阅读了整个答案，那么您可能会理解为什么用以下方法编写加密代码是个坏主意给出了多种解决方法。

#2 楼

以下示例在现实生活中难以利用，并且无法在网络上使用，但是它很容易理解和推断。

考虑服务器上检查MAC正确性的一段代码。

int compare_mac(unsigned char *mac1, unsigned char *mac2, size_t n)
{
    for (; n--; mac1++, mac2++) {
        if (*mac1 != *mac2) {
            return *mac1 - *mac2;
    }
    return 0;
}

如果MAC不匹配，则该功能会提前退出。换句话说，第一个字节不同的两个MAC将几乎立即返回，而仅最后一个字节不同的MAC将需要更多时间进行比较。

现在假设恶意用户试图发送一个不知道密钥的消息。假设他也可以非常准确地计时，足以区分几个指示。他可以简单地发送随机MAC并给响应计时，并找出MAC的每个字节，每个字节最多256个猜测。他首先猜测第一个字节，然后猜测第二个字节，等等。换句话说，他将最多需要对服务器进行$ 256n $的调用才能伪造MAC。

如果上面的编码没有早日返回，并且对于长度为$ n $的所有输入都是恒定时间，那么攻击者将需要对服务器的$ 256 ^ n $调用来伪造MAC。

显然，这是一个巨大的差异。

实际上，您可能无法区分一些指令，尤其是在网络上。但是，其他时序泄漏可能会更大，使用一些基本的统计分析可以使您走得更远。