Petya中的Salsa:算法修改带来的缺陷

2016-04-14 237579人围观 ,发现 1 个不明物体 漏洞

*本文中涉及到的相关漏洞已报送厂商并得到修复,本文仅限技术研究与讨论,严禁用于非法用途,否则产生的一切后果自行承担。

此前哈勃分析系统介绍过关于修改MBR进行磁盘加密敲诈的木马Petya(http://www.freebuf.com/articles/web/100386.html)。最近Leo Stone给出了破解Petya密钥的完整爆破代码和解密工具,并指出Petya作者是采用变种的Salsa20算法来进行密钥的校验。通过查阅其给出的源代码并结合Salsa算法的说明,可以还原出Petya对算法所进行的修改,以及其流程的具体逻辑。

Salsa20

Salsa20是由Daniel J. Bernstein发明的一种分组加密算法,可以对最长2^70字节的数据进行加密,其中分组长度为2^6=64字节。此算法是对称加密算法,并且加密和解密操作是等价的,即对明文用同一密钥进行2次加密可以得到还原的明文。

Salsa的输入

Salsa需要如下输入数据:

  • Key: 密钥,16或32字节;

  • IV: 初始向量,8字节;

  • Round: 计算轮数,取值为8、12或者20;

  • Message: 明文,不超过2^70字节。

  • Salsa的输出Ciphertext是与Message等长的加密数据。

    官网引用了一个Python语言的Demo,其中给出的用法如下:

    图片1.png

    Key参数

    Key是由Petya用于磁盘加密的密钥变换而来。当用户输入密钥之后,Petya会使用此密钥进行类Salsa的计算,将结果与磁盘55扇区中保存的512字节的预留数据进行比较,若结果一致则说明密钥有效。

    Salsa的Key要求最少16字节,但是Petya中有效的密钥只有8个字节。此密钥有三种变换形式:

    1. 原始密钥:即8位密钥。为了方便用户输入,字符必须从数字和大小写字母中选取,破解源码中定义了54种有效字符;

    0.png

    2. 终端密钥:用户输入的密钥,一共16个字符,是在原始密钥每个字符之后加入字母“x”形成;

    00.png

    3. Salsa密钥:将原始密钥扩展成16字节形成,用于Salsa算法的Key。扩展方法是将原始密钥的每字节b扩展成2字节,低位为b与字符“z”对应ASCII(122)之和,高位为b*2。(Salsa算法中的数据为小端序,下同。)

    000.png

    另外值得指出的是,原始Salsa算法需要8组DWORD共32字节的Key,当输入的Key参数只有16字节时,会将此Key复制一份扩展成32字节;但是Petya的变种算法中,是将16字节Key直接分为8组WORD进行计算。

    IV参数

    初始向量,此向量被Petya保存在磁盘54扇区33偏移处开始的8字节中,在破解源码中称为Nonce。虽然储存了8字节,但是Petya仅使用了其中的0、1、4、5共4个字节,亦即两个DWORD的低WORD位。

    图片5.png

    参数扩展

    破解源码中的结构体很好的描述了Salsa算法进行运算时的数据结构:

    图片6.png

    与原版算法相比,Petya的变种算法的最大区别是将每个字段变成了2字节。其中的Key和Nounce(IV)已经讨论过了,而Const和Counter是对输入参数进行扩展的方式。

    Const是常量数据,在Salsa算法中定义如下:

    图片7.png

    其意义可以通过翻译成对应的ASCII字符看出:

    图片8.png

    而Petya在使用时,同样只取了其低WORD位进行运算。

    图片9.png

    Counter是一个计数器,初始值为0,用于记录当前分组和参与运算。在原始算法中Counter是一个64位整型值,可以加密最多2^64个分组,再乘以每组64字节长度,总共可以加密的数据量最多可达2^70字节。同样的,在Petya的变种中分组上限也受到了限制,为2^32,不过实际上Petya只用到了8个分组。

    计算轮数

    Leo Stone认为Petya仅进行了10轮运算,运算量是原始算法的一半,这其实是一个误解。在官方引用的Salsa20的实现中,标准的循环次数也仅有10次:

    图片10.png

    这是因为,每次循环中其实进行了两轮运算,在官方文档中被称为行运算轮与列运算轮(rowround、columnround),因此10次循环就已经达到了Salsa20的计算轮数。

    图片11.png

    图片12.png

    输出数据

    计算完成后,Salsa算法将每组结果前后拼接在一起,然后取与明文等长的数据,和明文进行异或运算,得到输出的密文。这也是Salsa的加密和解密操作为什么是等价的原因:将运算结果与密文进行异或运算,则可以得到明文数据。

    在解密源码中,可以看到在读取了磁盘55扇区的预留结果之后,会将其按位与0×37做异或操作:

    图片13.png

    而这一步的真正含义是,Petya使用Salsa变种算法和指定的参数,对每一位均为0×37的512字节明文进行加密操作,然后将密文写入了磁盘扇区。

    有趣的是,Petya虽然在前面的步骤中大部分采用了2字节的WORD作为数据基本长度,但是在输出组结果时,却保留了分组长度为64字节的设定。这就意味着在前述petya_matrix结构体中,每个字段都必须从2字节扩展为4字节,其高位WORD会被填充为0,而在接下来的异或操作中,就会暴露出明文的特征:

    图片14.png

    写在最后

    也许是为了能够在MBR中顺利运行的缘故,Petya对Salsa20算法进行了很多简化,包括多处将DWORD改用WORD。而其中最重要的一处改动,则是将密钥空间限制在54^8的范围之内,并且明文和密文又都是已知的,这就为暴力破解密钥提供了有利的条件。

    参考资料

    https://github.com/leo-stone/hack-petya

    https://cr.yp.to/snuffle/spec.pdf

    http://www.seanet.com/~bugbee/crypto/salsa20/

    * 作者:腾讯电脑管家(企业账号),转载请注明来自FreeBuf黑客与极客(FreeBuf.COM)

    更多精彩

    这些评论亮了

    • bbc9529 (2级) 回复
      加密和解密操作是等价的,即对明文用同一密钥进行2次加密可以得到还原的明文.
      每个字段都必须从2字节扩展为4字节,其高位WORD会被填充为0,而在接下来的异或操作中,就会暴露出明文的特征.
      )6( 亮了
    发表评论

    已有 1 条评论

    取消
    Loading...

    特别推荐

    推荐关注

    填写个人信息

    姓名
    电话
    邮箱
    公司
    行业
    职位
    css.php