我只是想知道是否有可能对一个算法使用固定数量的随机二元或算术运算的算法进行估计，即需要多少（输入，输出）对才能对该算法进行逆向工程。此外，如果有任何（输入、输出）组合，则使用固定计算能力（在常规冯诺依曼架构上）进行逆向工程的计算时间。
到目前为止，我发现的唯一一件事是关于逻辑深度以及如何比较算法的复杂性。
时间逆向工程“随机”算法
逆向工程
密码分析
2021-06-21 04:11:28
1个回答
事实上，已经有一些工作试图将混淆前后程序的实际复杂性与其逆向难度联系起来。
关于这一点的开创性论文是 Collberg 等人的技术报告。从 1997 年开始 [ 1 ]。它定义了对不同类型的混淆进行分类并根据与原始程序相比增加的复杂性对它们进行排序的效力度量。
不幸的是，这种对混淆变换进行分类的方法非常幼稚。主要是因为程序的复杂性让您知道处理它需要多少操作，但不知道简化它的难度有多大。
例如，在程序中添加大量不必要的变量和额外的循环会增加其复杂性。然而，对程序进行简单静态分析的优化器可以恢复原始程序。
相反，用一个简单的查找表替换复杂的指令序列，可以完美地模仿这个指令序列将降低程序的复杂性，但是仅仅通过查看表找出原始指令序列可能是很难。
因此，除了一些非常特殊的情况外，程序的复杂性并不是衡量其逆向难度的可靠方法。
事实上，我们没有任何完整和客观的方法来衡量混淆的好坏......密码学家也没有办法说密码系统是安全的（但是，他们拥有的工具可以让他们比我们更有信心现在在我们的计划中，所以我们应该仔细看看他们做了什么，因为这些天我们的领域变得越来越亲密......只是我个人的感觉）。
[1] Christian Collberg、Clark Thomborson 和 Douglas Low的混淆转换分类法。技术报告 #148，奥克兰大学，1997 年。