Key-Recovery Attacks on ASASA
Key-Recovery Attacks on ASASA
复制标题
DOI：
10.1007/s00145-017-9272-x
复制
发表时间：
2015-11
影响因子：
3
通讯作者：
Brice Minaud;Patrick Derbez;Pierre-Alain Fouque;Pierre Karpman
中科院分区：
文献类型：
--
作者：
Brice Minaud;Patrick Derbez;Pierre-Alain Fouque;Pierre Karpman
该建筑是 Biryukov、Bouillaguet 和 Khovratovich 在 2014 年 Asiacrypt 上推出的新设计方案。它的多功能性通过构建两个公钥加密方案、一个秘密密钥方案以及白盒方案的超级 S 盒子组件来说明。然而，两个公钥密码系统之一最近在 Crypto2015 上被 Gilbert、Plût 和 Treger 破解。作为我们的主要贡献，我们提出了一种新的代数密钥恢复攻击，能够立即破解秘密密钥方案以及剩余的公钥方案，时间复杂度分别为 和 （两种情况下的安全参数均为 128 位）。此外，我们提出了对同一公钥方案的第二次独立利益攻击，它启发式地将破坏该方案的问题减少到具有易于处理的参数的实例。这允许密钥恢复的时间复杂度。最后，作为一个附带结果，我们概述了一种针对白盒方案的非常有效的启发式攻击，该攻击在一分钟内就在笔记本电脑上破坏了声称具有 64 位安全性的实例。
Theconstruction is a new design scheme introduced atAsiacrypt 2014by Biryukov, Bouillaguet and Khovratovich. Its versatility was illustrated by building two public-key encryption schemes, a secret-key scheme, as well as super S-box subcomponents of a white-box scheme. However, one of the two public-key cryptosystems was recently broken atCrypto2015 by Gilbert, Plût and Treger. As our main contribution, we propose a new algebraic key-recovery attack able to break at once the secret-key scheme as well as the remaining public-key scheme, in time complexityand, respectively (the security parameter is 128 bits in both cases). Furthermore, we present a second attack of independent interest on the same public-key scheme, which heuristically reduces the problem of breaking the scheme to aninstance with tractable parameters. This allows key recovery in time complexity. Finally, as a side result, we outline a very efficient heuristic attack on the white-box scheme, which breaks instances claiming 64 bits of security under one minute on a laptop computer.