Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Automated Identification of Cryptographic Primitives in Binary Code With Data Flow Graph Isomorphism

今天要介绍的一篇论文Automated Identification of Cryptographic Primitives in Binary Code with Data Flow Graph Isomorphism 来自AsiaCCS’15,这篇论文讨论的主题和我们小组的研究方向类似,讨论了二进制代码中密码算法的识别工作。

摘要

作者提出了一种自动化检测二进制文件中对称密钥算法和它们参数的方法,核心思想基于数据流图的同构(Data Flow Graph Isomorphism)

该工作可以适应编译器优化和源代码细微变化(但是回避了代码混淆问题)

Related Work

作者首先回顾了已有的一些二进制代码中密码算法识别方法

基于数据常量的检测方法

检测对称密钥算法经常包含特殊的常数

检测常数的工具: Findcrypt2 (IDA plugin) [14], KANAL (PEiD plugin), H&C Detector, 这些工具基于静态分析,而有些时候常数会动态生成,导致检测失败。

常数检测可能是检测过程中有效的第一步,但这并不能被当做一种检测密钥算法的独立手段

基于 input / output 关系的识别方法

这个方法是目前精度较高的,基本没有false positive,这里作者引用了我们在ISC‘11会议上发表的论文Detection and Analysis of Cryptographic Data Inside Software

Solution Overview

论文的方法包括三个步骤:

  1. 根据所给的汇编代码建立相应的DFG
  2. 根据重写规则规范化DFG
  3. 根据加密算法的graph signature 寻找同构子图

Data flow graph construction

常数

寄存器

内存: load store

Normalization

三种类型的重写规则:normalization rules, memory simplification rules, general simplification rules.

Normalization Rules

Memory Access Simplification Rules

3条规则:

  1. store after store:前一条没有作用的store可以被移除
  2. load after store:load的输出与store的输入相等,那么load可以被移除
  3. load after load:两个操作的输出相同,那么它们可以被merge

aliasing issue

General Simplification Rules

Common Subexpression Elimination

如果两个表达式拥有一样的输入输出,那么可以去掉其中的一个

Constant Simplification Rules

适用于以下情况:

  1. 如果算术逻辑运算的操作数都是常数,可以用计算结果代替
  2. 如果算术或逻辑运算的一个操作数等于该操作的identify element或absorbing element

Signature生成

为密码算法生成相应的签名。目前还没有自动方法,只能手工生成签名

macro signature: 当匹配成功时,增加一个节点继续匹配

Subgraph isomorphism

使用乌尔曼子图同构算法

Experimental results

作者主要测试了三个算法XTEA MD5 AES 测试了Crypto++, LibTomCrypt 和 Botan三个密码学算法库

存在的问题

只能检测比较简单的算法如XTEA, MD5 和 AES. 公钥算法无法检测

有一些密码学库使用了MMX指令集,这个也不支持