Cryptanalysis with COPACOBANA
Cryptanalysis with COPACOBANA
复制标题
DOI：
10.1109/tc.2008.80
复制
发表时间：
2008-11
影响因子：
3.7
通讯作者：
Tim Güneysu;Timo Kasper;M. Novotný;C. Paar;Andy Rupp
中科院分区：
文献类型：
--
作者：
Tim Güneysu;Timo Kasper;M. Novotný;C. Paar;Andy Rupp
密码的密码分析通常涉及大量计算。通常选择加密算法的安全参数，以便利用可用的计算资源进行攻击是不可行的。因此，在密码分析问题缺乏数学突破的情况下，解决所涉及的计算的一种有前途的方法是构建比现成计算机表现出（得多）更好的性能成本比的专用硬件。本贡献展示了利用成本优化并行破码器 (COPACOBANA) 机器的各种密码分析应用，该机器是一个由 120 个现场可编程门阵列 (FPGA) 组成的高性能低成本集群。 COPACOBANA 似乎是公开文献中报道的唯一针对密码破解任务进行优化的可重构并行 FPGA 机器。根据实际算法的不同，并行硬件架构的性能可以比传统计算机高出几个数量级。在这项工作中，我们利用 COPACOBANA 令人印象深刻的计算能力，重点研究密码分析算法的新颖实现。我们描述了对对称密码的各种详尽的密钥搜索攻击，并演示了对电子护照（e-passport）中使用的安全机制的攻击。此外，我们描述了时间-内存权衡技术，该技术可用于攻击 GSM 语音加密中使用的流行 A5/1 算法。此外，我们还介绍了非对称密码系统上更复杂的密码分析的有效实现，例如椭圆曲线密码系统 (ECC) 和 RSA 的数字协分解。尽管 COPACOBANA 无法打破大多数实际应用中使用的参数长度的 RSA 或椭圆曲线，但我们对人为短位长度的算法的攻击使我们能够对现实世界的位长度推断出更可靠的安全估计。这对于得出有关非对称密钥长度寿命的估计特别有用。
Cryptanalysis of ciphers usually involves massive computations. The security parameters of cryptographic algorithms are commonly chosen so that attacks are infeasible with available computing resources. Thus, in the absence of mathematical breakthroughs to a cryptanalytical problem, a promising way for tackling the computations involved is to build special-purpose hardware exhibiting a (much) better performance-cost ratio than off-the-shelf computers. This contribution presents a variety of cryptanalytical applications utilizing the cost-optimized parallel code breaker (COPACOBANA) machine, which is a high-performance low-cost cluster consisting of 120 field-programmable gate arrays (FPGAs). COPACOBANA appears to be the only such reconfigurable parallel FPGA machine optimized for code breaking tasks reported in the open literature. Depending on the actual algorithm, the parallel hardware architecture can outperform conventional computers by several orders of magnitude. In this work, we focus on novel implementations of cryptanalytical algorithms, utilizing the impressive computational power of COPACOBANA. We describe various exhaustive key search attacks on symmetric ciphers and demonstrate an attack on a security mechanism employed in the electronic passport (e-passport). Furthermore, we describe time-memory trade-off techniques that can, e.g., be used for attacking the popular A5/1 algorithm used in GSM voice encryption. In addition, we introduce efficient implementations of more complex cryptanalysis on asymmetric cryptosystems, e.g., elliptic curve cryptosystems (ECCs) and number cofactorization for RSA. Even though breaking RSA or elliptic curves with parameter lengths used in most practical applications is out of reach with COPACOBANA, our attacks on algorithms with artificially short bit lengths allow us to extrapolate more reliable security estimates for real-world bit lengths. This is particularly useful for deriving estimates about the longevity of asymmetric key lengths.