Error Amplification in Code-based Cryptography
Error Amplification in Code-based Cryptography
复制标题
DOI：
10.13154/tches.v2019.i1.238-258
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Alexander Nilsson;T. Johansson;Paul Stankovski
中科院分区：
文献类型：
--
作者：
Alexander Nilsson;T. Johansson;Paul Stankovski
基于码的密码学是在后量子场景中实现密码原语的主要技术之一。特别地，MDPC方案是一个基本方案，从该方案中已经衍生出许多其它方案。这些方案依赖于迭代解码在解密过程中，因此有一定的小概率p有一个解密（解码）errors.In本文中，我们显示了一个非常基本和重要的性质的代码为基础的加密方案。给定一个初始的错误模式，无法解码，生成另一个消息，无法解码所需的时间严格小于1/p。我们表明这是通过开发一种方法快速生成不可解码的错误模式（错误模式链接），这也证明了密文空间中的紧密度的措施，可以利用其强大的链接到这些消息的解码难度。此外，如果边信道信息也是可用的（解码时间），那么就不再需要给出初始错误模式，因为在这种情况下可以很容易地生成一个错误模式。这些观察结果非常重要，因为它们表明，一个128位的加密方案即使使用故障率为2−128的解码器，也不能固有地免受反应攻击。事实上，除非采取明确的保护措施，否则任何级别的失败率都会带来安全问题，因为我们的方法会产生错误放大效应。最近，MDPC方案以及类似方案出现了密钥恢复反应攻击，利用解码错误来恢复密钥。还表明，知道迭代解码步骤中的迭代次数（其可以在定时攻击中接收到）也将启用并增强这种攻击。在本文中，我们应用我们的错误模式链接的方法，以显示如何提高性能的反应攻击的CPA的情况下。我们发现，在识别一个单一的解码错误（或解码步骤需要更多的时间比预期的定时攻击），我们可以自适应地创建新的错误模式，具有更高的解码错误概率比随机错误。这导致了显着改善的攻击的基础上的CPA的情况下，解码错误，它也给出了最强的已知攻击的MDPC类计划，无论是使用和不使用侧信道信息。
Code-based cryptography is one of the main techniques enabling cryptographic primitives in a post-quantum scenario. In particular, the MDPC scheme is a basic scheme from which many other schemes have been derived. These schemes rely on iterative decoding in the decryption process and thus have a certain small probability p of having a decryption (decoding) error.In this paper we show a very fundamental and important property of code-based encryption schemes. Given one initial error pattern that fails to decode, the time needed to generate another message that fails to decode is strictly much less than 1/p. We show this by developing a method for fast generation of undecodable error patterns (error pattern chaining), which additionally proves that a measure of closeness in ciphertext space can be exploited through its strong linkage to the difficulty of decoding these messages. Furthermore, if side-channel information is also available (time to decode), then the initial error pattern no longer needs to be given since one can be easily generated in this case.These observations are fundamentally important because they show that a, say, 128- bit encryption scheme is not inherently safe from reaction attacks even if it employs a decoder with a failure rate of 2−128. In fact, unless explicit protective measures are taken, having a failure rate at all – of any magnitude – can pose a security problem because of the error amplification effect of our method.A key-recovery reaction attack was recently shown on the MDPC scheme as well as similar schemes, taking advantage of decoding errors in order to recover the secret key. It was also shown that knowing the number of iterations in the iterative decoding step, which could be received in a timing attack, would also enable and enhance such an attack. In this paper we apply our error pattern chaining method to show how to improve the performance of such reaction attacks in the CPA case. We show that after identifying a single decoding error (or a decoding step taking more time than expected in a timing attack), we can adaptively create new error patterns that have a much higher decoding error probability than for a random error. This leads to a significant improvement of the attack based on decoding errors in the CPA case and it also gives the strongest known attack on MDPC-like schemes, both with and without using side-channel information.