CryptoMiniSat Switches-Optimization for Solving Cryptographic Instances
CryptoMiniSat Switches-Optimization for Solving Cryptographic Instances
复制标题
CryptoMiniSat 交换机 - 解决加密实例的优化
DOI：
10.29007/vpd6
复制
发表时间：
2018
影响因子：
3.8
通讯作者：
Kai Weber
中科院分区：
文献类型：
--
作者：
Anastasia;O. Zendel;Werner Lennartz;Kai Weber
通过执行数百次测试运行和源代码分析，我们经验地确定了CryptoMiniSat (CMS) 5的改进参数配置，用于解决源自小型AES-64模型密码SR（3轮加密的代数已知明文攻击）的加密CNF实例（3,4,4,4）。我们最终能够在一个小时内实时重建64位长键，据我们所知，这是迄今为止从未实现过的。特别是，在没有任何假设或先前对密钥位的了解的情况下（例如以侧信道的形式，如Mohamed等人，2012年对AES的改进代数侧信道攻击）。对非确定性求解器运行时进行了统计分析，并定义了命令行参数组合，以产生最佳运行时，其范围从一开始的不到一小时到中间数小时不等。我们继续使用自动算法配置（AAC）工具，系统地扩展搜索更好的求解器配置，并成功地提供更短的求解时间。在这项工作中，我们详细阐述了我们遵循的系统分类学，以一种可追溯和可重复的方式达到我们的结果。我们调查的最终重点是发现CMS在经过适当调整后，是否确实能够解决比这里解决的问题更大、更困难的问题。在密码学研究领域，与找到问题的实际可行性相比，求解时间的长短起着次要的作用。本文给出的结果的视角可扩展性是进一步研究的对象。
Performing hundreds of test runs and a source-code analysis, we empirically identified improved parameter configurations for the CryptoMiniSat (CMS) 5 for solving cryptographic CNF instances originating from algebraic known-plaintext attacks on 3 rounds encryption of the Small AES-64 model cipher SR(3, 4, 4, 4). We finally became able to reconstruct 64-bit long keys in under an hour real time which, to our knowledge, has never been achieved so far. Especially, not without any assumptions or previous knowledge of key-bits (for instance in the form of side-channels, as in Mohamed et al., Improved Algebraic Side-Channel Attack on AES, 2012). A statistical analysis of the non-deterministic solver runtimes was carried out and command line parameter combinations were defined to yield best runtimes which ranged from under an hour to a few hours in median at the beginning. We proceeded using an Automatic Algorithm Configuration (AAC) tool to systematically extend the search for even better solver configurations with success to deliver even shorter solving times. In this work we elaborate on the systematics we followed to reach our results in a traceable and reproducible way. The ultimate focus of our investigations is to find out if CMS, when appropriately tuned, is indeed capable to attack even bigger and harder problems than the here solved ones. For the domain of cryptographic research, the duration of the solving time plays an inferior role as compared to the practical feasibility of finding a solution to the problem. The perspective scalability of the here presented results is the object of further investigations.