SM3碰撞漏洞

微信小程序国密算法SM3碰撞原理揭秘
2021.3.10

2021年2月，蜚语安全在对客户产品进行安全代码审计时，发现其依赖的微信小程序sm-crypto 开源NodeJS国密算法库中的SM3算法实现（该算法库使用NodeJS对国密算法中的SM2，SM3和SM4三个算法进行了实现，并封装成接口提供给开发者使用。该国密算法库的具体实现在GitHub上开源：https://github.com/wechat-miniprogram/sm-crypto，其中sm3的实现在文件src/sm3/index.js中，微信小程序官方的参考文档链接为 https://developers.weixin.qq.com/miniprogram/dev/extended/utils/sm-crypto.html ）存在重大的实现错误，导致不同的输入可被编码为相同的bitstring，进而进行SM3计算后产生“伪”hash碰撞效果。

影响

该问题影响sm-crypto的0.2.2及之前版本。由于该国密库为微信小程序官方提供的国密库，因此使用该库的都会受该碰撞的影响。根据GitHub上的信息，我们发现该作者的另一个NodeJS的库sm-crypto（https://github.com/JuneAndGreen/sm-crypto）也受该问题的影响。

根据GitHub上代码的dependent信息，光GitHub上就有260个开源项目依赖该微信小程序的国密算法库，57个项目依赖该作者NodeJS的sm-crypto库，而通过npm安装使用的sm-crypto和miniprogram-sm-crypto的开发者和项目则可能更多。

问题分析

该SM3碰撞问题来源于sm3算法的实现文件src/sm3/index.js中。该SM3算法直接接收字符串作为输入，并通过以下函数将字符串转成二进制流：

const binary = str2binary(str)

再进行后续的填充以及SM3的变换等。而str2binary函数的具体实现如下：

function str2binary(str) {
  let binary = ''
  for (let i = 0, len = str.length; i < len; i++) {
    const ch = str[i]
    binary += leftPad(ch.codePointAt(0).toString(2), 8)
  }
  return binary
}

该函数使用codePointAt函数对字符串中的每一个字符，获取其编码点值，并通过toString(2)转成二进制形式后，再使用自己实现的leftPad函数对二进制串进行高位补0的操作，leftPad函数实现如下：

function leftPad(input, num) {
  if (input.length >= num) return input

  return (new Array(num - input.length + 1)).join('0') + input
}

可以看到，leftPad的逻辑是：如果input的长度大于等于num，则直接返回，否则根据num的值对input的高位补0。我们注意到在str2binary函数中，调用leftPad函数时，num参数被设置为8。所以当传入的input的二进制长度是低于8比特的时候，是没有问题的，但是一旦input长度大于8，则leftPad函数就不会对其高位补0，而是直接返回。而我们知道所有的中文字符码点值都是超过1字节、也就是8比特的，因此中文字符在转成二进制形式后，并没有高位补0。一旦有这些中文字符在字符串中被拼接后，会导致最终进行SM3计算的二进制数据很可能不是8比特对齐的！

Proof-of-Concept

由于在这个转换过程中，没有对超过1字节字符的二进制表示进行8比特对齐，导致我们只要精心构造，就可能找到两个不同的字符串，使得这两个字符串在转换后最终得到相同的二进制表示。例如8个16比特的字符（UTF-16编码），如果最高比特位都为0，则通过该算法库中实现的二进制转换函数最终得到的二进制串是8*15=120比特，而这120比特的二进制串，同时也可以表示成多种形式，例如7个16比特的字符（最高比特位是1）拼上任意一个8比特的字符，或6个16比特的字符（最高比特位是1）拼上任意2个8比特的字符等，总共有数种组合，如下所示：8*15 = 120 = 7*16+1*8 = 5*16+3*8 = 4*16+5*8 = 3*16+7*8 = ...

因此只要仔细研究相应的编码，让8个15比特编码的字符和最终变换后的字符都是可见字符，就可以构造出两个完全不同的字符串输入，在经过微信小程序官方NodeJS国密算法库的初始化变换后，会变成同样的二进制串输入到SM3核心变换函数中，并最终得到同样的SM3哈希值！

JS的codePointAt函数返回的就是UTF16的码点值，利用上述方法，将任选的8个中文字符的二进制串（最高比特位为0）重新分割，使其也能够表示成其他中文字符（最高比特位需为1）与常见8比特可见字符的组合即可。这里我们随意构造了一组，其二进制串为：

100111000100111 100111000011001 
100111000001010 100100000001001 
100110000001011 100111000001101 
100111010010000 100111001010001

使用该函数的字符到二进制转换方式，原始字符串为：丧丙上䠉䰋不亐乑，重新对其二进制进行分割，如下：

1001110001001111 00111000 01100110 
01110000 01010100 1000000010011001 
1000000101110011 1000001101100111 
01001000 01001110 01010001

同样以该函数的二进制转换方式，字符串为：鱏8fpT肙腳荧HNQ。

将这两个字符串传入该国密算法库的SM3函数，即可获得本文开头的碰撞结果。由此可知诸如这类的碰撞还可以构造很多。完整的POC.js代码如下：

const sm3 = require('miniprogram-sm-crypto').sm3
s1 = "丧丙上䠉䰋不亐乑"
console.log(s1)
s2 = "鱏8fpT肙腳荧HNQ"
console.log(s2)
h1 = sm3(s1)
console.log(h1)
h2 = sm3(s2)
console.log(h2)
console.log(h1 == h2)

安装好nodejs环境后，可直接使用如下命令验证：

node POC.js

使用该方法可以构造多组能够实现碰撞的字符串输入，甚至可能能够构造出两组有意义的字符串并形成SM3的碰撞！

修复方案

目前sm-crypto已经修复了该问题，需要将版本升级至目前最新的0.2.4。其修复思路是将输入的字符全部转成UTF-8编码的二进制串，再进行SM3计算。        事实上，国密SM3的规范仅仅约定了输入应当是二进制串或字节流，而非字符串。字符串如何转换成二进制串则需要依赖开发者选择不同的编码方式（如UTF-8，UTF-16等）。而该库SM3碰撞的本质原因正是由于其对字符串编码转换实现的错误导致。目前该库的修复方案是统一将字符转成UTF-8编码。这的确是一种方法但也对开发者失去了一些自由度，其实可以将SM3算法以二进制或字节数组为输入，同时提供不同编码方式的字符转字节数组的接口，供开发者使用，或由开发者自行实现字符转字节数组的方式。