声明

本文不是在教你破解, 如果只是想破解Excel保护, 请出门右转找百度/Google, 这里仅仅只是对其中的算法原理做研究, 请勿用于非法用途!

描述

Excel可以在菜单->审阅下设置保护工作表, 保护下的工作表不可以选中复制/查看单元格公式或编辑, 是一个简单实用的保护功能.

但是这个保护也确实太”简单”了点, 只要在网上一搜, 有无数的文章教你如何轻松破解, 其中最为广泛的大体有两种:

  1. 是通过一段VBS脚本直接破解保护, 这是因为Excel本身的这个加密强度不大, 可以直接破解, 但是只适用一些老版本, 比如Excel 97. 但是Excel 2013对这个算法进行了强化, 这个方案不再有用.
  2. 针对Excel 2013后的版本, 虽然加密强度够了, 但是文件格式也变成了xlsx, 其本质不过是一系列xml文件的压缩包, 如果手动删除对应加密的描述, 便可以起到”爆破”破解的效果.

其实我还发现与”爆破”类似的还有一种另存为xls(老版本)的方法, 强行通过”降维打击”, 将加密程度退化到老版本, 再破解的方法.

研究目标

不过今天不是在研究如何破解, 而是聚焦在这个老版本的Excel里的加密算法本身.

不管你在保护工作表时输入什么样的密码, Excel都会将其计算成一个16位的散列值, 比如“excel” 这个密码字符串(不含引号), 对应的散列值为0xC7AC, 存在Excel文件里面大概就是长这样:

  1. <sheetProtection password="C7AC" sheet="1" objects="1" selectLockedCells="1" selectUnlockedCells="1"/>

今天就来研究一下这个密码是如何得到的, 以及网上流传的VBS破解脚本为什么能够破解它.

散列值算法

关于如何计算这个散列值, 网上有一些说法, 其中一个人(Kohei Yoshida)的文章指出其算法遵照了 Office Open XML Specification 中提出的加密标准, 但是Excel又在其基础上做了改动, 但是也被文章作者还原出来了其方法, 大体上就是算出最终值后还需要再加一个”魔数”才能得到最终的散列值, 下面还会说到. 其实评论中已经有人说了在官方的Excel文件格式说明的4.18.4小节有算法的详细说明.

另一个容易搜索到的算法说明在这里, 这个里面的算法写的更详细, 也被更多的人引用, 而且也确实就是这个算法, 它具体是这样的:

  1. 对于原密码的每一位按其索引位置, 用ASCII码做RoL(左移旋转), 左移就是所有二进制位左移一位, 旋转意味着左移到最高位时, 不会溢出而是将进位移到最右端:
    • 左移: 十进制数字2的二进制表示: (10), 左移一位就是(100), 相当于十进制中乘以2
    • 旋转: 这里限制位数16位, 而且有符号, 最高位始终为0, 所以(0100 0000 1101 0000)左移时要把次高位上的1转到最后面, 变成(0000 0001 1010 0001)

比如密码”excel”, 对应的ASCII码分别是 0x65, 0x78, 0x63, 0x65, 0x6C, 分别RoL 1,2,3,4,5位:

  1. 0x65 RoL 1 = 0xCA
  2. 0x78 RoL 2 = 0x1E0
  3. 0x63 RoL 3 = 0x318
  4. 0x65 RoL 4 = 0x650
  5. 0x6C RoL 5 = 0xD80

然后将结果全部异或(XOR), 结果: 0x9E2

  1. 将第1步的结果和字符串长度异或: 0x9E2 XOR 0x5=0x9E7
  2. 将第2步结果和魔数 0xCE4B 异或: 0x9E7 XOR 0xCE4B= 0xC7AC

这个就是最终的散列值结果.

这个时候回头看Kohei Yoshida的算法, 就会发现他还原的算法和这个是一样, 这是他的核心代码, 我在里面加了注释和算法步骤对应:

  1. sal_uInt16 cchPassword = strlen(szPassword);
  2. sal_uInt16 wPasswordHash = 0;
  3. if (!cchPassword)
  4.     return wPasswordHash;
  6. const char* pch = &szPassword[cchPassword];
  7. while (pch-- != szPassword)
  8. {
  9.     // 这里用了位运算的高级技巧, 将一个值右移14位并AND掩码0x01, 相当于单取第15位的值并移到最右边
  10.     // 将一个值左移1位并AND掩码0x7FFF, 相当于将其左移但是截断最高位, 使其不溢出
  11.     // 两者合并做OR操作, 就是对应算法第一步中的RoL
  12.     wPasswordHash = ((wPasswordHash >> 14) & 0x01) | 
  13.                     ((wPasswordHash << 1) & 0x7fff);
  14.     wPasswordHash ^= *pch;
  15. }
  17. wPasswordHash = ((wPasswordHash >> 14) & 0x01) | 
  18.                 ((wPasswordHash << 1) & 0x7fff);
  20. // 这里对应算法第三步的魔数, (0x8000 | ('N' << 8) | 'K')的结果就是0xCE4B
  21. // 这里我很佩服作者能想出这么复杂的步骤来算出这个魔数, 不知道他试了多少次
  22. wPasswordHash ^= (0x8000 | ('N' << 8) | 'K');
  23. // 这里对应前面算法第二步, 因为异或运算服从结合律, 所以顺序颠倒是没有问题的
  24. wPasswordHash ^= cchPassword;

上面的程序用了C/C++语言, 而且还用了位运算, 有点”晦涩难懂”, 所以我也用Python做了一个简单的还原:

  1. def rotate(value, index):
  2.     for _ in range(0, index + 1):
  3.         value = value << 1
  4.         if value >= 32768:
  5.             value -= 32768
  6.             value += 1
  7.     return value
  9. def get_hash(password):
  10.     result = 0
  11.     for index, c in enumerate(password):
  12.         result ^= rotate(ord(c), index)
  13.     result ^= len(password)
  14.     result ^= 0xce4b
  15.     return result
  17.  print(format(get_hash("excel"), '02X')) 
  18.  # 输出: C7AC

散列碰撞

散列算法或者Hash算法在某些场合又称作“指纹算法”, 因为它具备和指纹一样的特性, 假如两个对象A和B分别生成散列值HA和HB:

  1. 如果十几行代码竟能破解Excel? Excel工作表保护密码的算法和破解研究 - 图1, 那么A和B可能大概率是同一个东西
  2. 如果十几行代码竟能破解Excel? Excel工作表保护密码的算法和破解研究 - 图2, 那么A和B一定不是同一个东西

这就和指纹一样, 如果指纹不一样, 显然是两个人, 如果指纹一样, 那么大概率就是同一个人, 所以指纹相同是一个很强的证据. 但是理论上也是有概率出现相同指纹的, 只是这个概率超级低, 低到历史上发现指纹以来到今天为止, 还没听说过谁和谁指纹相同(手机指纹识别算法因为需要容错性, 所以还是有可能的, 但是要说实际指纹一致的真没有).

但是如果发生了这样的情况, 就将这种情况称之为“碰撞”.

一个合格的散列函数, 需要具备:

  1. 抗碰撞能力: 一般位数越多, 可能性也越多, 抗碰撞能力越强. 以指纹举例, 检查指纹需要十来个特征点, 每个特征点又有十来种情况, 组合起来至少上百亿种情况, 碰撞概率很低
  2. 抗篡改能力: 微小的改动, 最终的散列值却相差巨大, 难以反推出规律. 还是以指纹举例, 双胞胎, 几乎相同的DNA, 这样的情况下, 他们的指纹往往大体结构相似, 但是细节不同, 在专家眼里, 还是属于不一样的指纹. 这是说的相同的DNA, 如果是父母孩子这样略有不同的DNA, 指纹差距更大了, 所以指纹的抗篡改能力也很强

那前面这个Excel散列函数能力如何呢:

  1. 抗碰撞能力:
    它的最终散列值是16位, 但是由于其算法原因最高位始终为1, 所以其有效长度是15位, 也就是说它只有2的15次方=32768种可能性.

对比 MD5 算法, 其散列长度为128位, 有着2的128次方种可能性, 其设计的碰撞预期为十几行代码竟能破解Excel? Excel工作表保护密码的算法和破解研究 - 图3, 基本上是个天文数字, 即便后来大牛王小云破解了它, 也只是将其碰撞预期降低到十几行代码竟能破解Excel? Excel工作表保护密码的算法和破解研究 - 图4, 从一个很大的天文数字变成一个较小的天文数字, 虽然对地球人来说依旧大的毫无概念, 但是对计算机来说, 可碰撞性大大增强, 所以MD5也被认为在一些重要场合下强度不足.
再比如Excel 2013新版的散列算法使用了SHA-512, 其长度为512位, 强度大大超过现有算力, 基本上不可破解了.

  1. 抗篡改能力:
    我们来看看Excel散列函数的抗篡改能力:

ExcelHash(“excel”)=0xC7AC
ExcelHash(“excem”)=0xC78C
ExcelHash(“excen”)=0xC7EC
怎么说呢, 基本上规律性已经很明显了, 不用我多说了吧.

对比MD5:
MD5(“excel”)=bf57c906fa7d2bb66d07372e41585d96
MD5(“excem”)=6feb7d8c53aa71f5ba9db94e4d0bf1c3
MD5(“excen”)=2930bd01946b356dd2ea4a57edaa8e52

显然这样的抗篡改能力才是合格的.

现在我们已经知道Excel的这个散列函数强度不高, 规律性又明显, 那我们就可以用一个小范围的测试值在有限的时间内穷举它.

总所周知, 所有的散列函数本质是有损压缩, 所以哪怕这个散列函数再垃圾, 我们也不可能还原出它的原密码, 所以想通过这个法子窃取原密码的同学可以断了这个念想了.

但是如果仅仅是破解的话, 我们只要精心构造一个能产生相同散列值的字符串就可以了. 这个方法也就是最开始的标题”散列碰撞”, 或者”Hash碰撞”.

VBS脚本中的碰撞算法

那有没有这样一个算法呢? 当然有! 之前说的网上流传的VBS脚本就是这个算法, 通过研究代码可以知道它构造了这样一系列字符串来执行碰撞:

总长12位, 前11位不是A就是B, 第12位则是一个范围很大的字符.

比如前面例子里的密码“excel”, 散列值0xC7AC, 通过这个VBS脚本算出来的一个碰撞字符串为“AABAAABAAABV”, 它的散列值也是0xC7AC.

也就是说你新建一个Excel, 保护工作表, 输入密码excel, 保存为xls(务必是这个格式, 因为只有老格式才使用这个算法), 然后重新打开它, 点击撤销保护, 输入密码AABAAABAAABV, Bingo! 开了!

通过简单的排列组合计算可以得出, 这个算法构造的字符串个数为十几行代码竟能破解Excel? Excel工作表保护密码的算法和破解研究 - 图5, 大约19万种组合, Excel散列值大约有3万种组合, 这里用了多出6倍的组合来碰撞, 那么做到全覆盖了吗? 我写了一个程序来检验这196608种组合, 确定了它确实做到了全覆盖, 也就是说无论你在Excel里面设置什么密码, 我都可以在这196608种组合中找到一个碰撞来解开它!

这里要提一句, Excel散列函数中大量使用了异或运算, 异或(XOR, exclusive or)是个很神奇的逻辑运算符, 它服从结合律, 交换律和自反律. 特别是自反律: A XOR B XOR B = A, 有一种对称加密法就是基于异或, 使用一串随机的key来异或原文, 得到密文, 然后接收者通过这个key再和密文异或, 就能得到原文, 只要这个key不遗失, 密码就是安全的, 这篇文章讲的很详细.

前面我是通过穷举来证明那种碰撞算法是全覆盖的, 那么是不是可以从异或的数学特性上证明其完整性呢? 但是我是个数学渣渣, 自己研究是研究不出来的, 搜了一圈也没有发现相关的研究, 倒是发现异或在数学上可能和群论有关系, 这里有篇文章提到了一些信息学算法(线性基什么的)会用到异或的特性, 但是对研究这里的碰撞算法没什么帮助.

不过这不妨碍我接下来的研究, 如何改进这个碰撞算法, 以最小/最优的碰撞组合来碰撞呢?

我的碰撞算法

前面提到, Excel散列值有2的15次方, 也就是32768种组合. 最小的碰撞组合也至少要有32768种才行, 网上流行的破解脚本使用了19万种组合, 能不能将它缩小范围, 甚至就缩小到32768种呢?

答案是可以!

其实循着原来的碰撞算法的思路就能发现优化空间, 首先原算法为什么需要12位碰撞字符串, 因为按照散列算法, 每一位的字符需要依次左移, 如果位数不够, 显然高位的字节位永远为0, 组合不全, 所以字符串位数是硬要求, 12位显然足够了.

那么为什么前11位只能是A或者B呢, 从他们的ASCII码的二进制表示可以看出来:

A的ASCII码是0x41, 二进制(1000001)
B的ASCII码是0x42, 二进制(1000010)

可以看到他们的最右边一位分别是1和0, 这样两个字符就能组合出在这一位的两种不同组合, 所以, 其实不是非要AB的组合, 只要是二进制结尾分别是1和0的两个字符都可以, 比如CD, oz甚至{~这样一个组合都可以. 但是反之如果这两个字符串结尾都是1或者都是0, 就不行, 比如AC, 结尾都是1, 就不行, 无论这样的字符组合多少位, 最终组合出来的都会少一半的覆盖, 只有16384种组合.

那现在我们在11位上有了不同组合, 剩下的4位怎么办, 所以最后一个字符需要扩大范围, VBS脚本中使用了从32到127的范围, 字符从空格到波浪线(~), 一共96个字符, 它们完全可以覆盖4位也就是2的4次方16种可能性. 所以这就是VBS脚本中碰撞算法的设计.

要优化它也很容易, 首先AB这种双字母组合不需要变, 但是位数可以缩短, 因为可用字符编号从32到127, 一共96位, 咱们取个整64(二进制的整), 是2的6次方, 所以15-6=9, AB这种组合长度从11位缩小到9位就可以了, 而第10位也不需要32到127这么大范围了, 只需要32到95一共64个字符就可以了, 总结一下最终的组合数十几行代码竟能破解Excel? Excel工作表保护密码的算法和破解研究 - 图6, 刚刚好覆盖所有的组合, 不多也不少. 我们来实测一下:

之前说过 ExcelHash(“excel”)=0xC7AC, 用优化后的碰撞算法算出对应的碰撞字符串是AAABBBABB\, 不出意外, 成功解锁, 总共10位, 比之前的算法短了2位.

咱们再换一个前导组合试试, 换个奇葩点的组合<=, 算出碰撞字符串<=<<<===<6, 不出意外, 再次解锁!

通过我之前写的穷举验证程序, 这个算法确实做到了全覆盖.

  1. def collision(password):
  2.     target_hash = get_hash(password)
  3.     for i in itertools.product("AB", repeat=9):
  4.         for n in range(32, 96):
  5.             pwd = "".join(i) + chr(n)
  6.             if get_hash(pwd) == target_hash:
  7.                 return pwd
  8.     raise Exception("Not found, which is impossible!")
  10. print(collision("excel")) 
  11. # 输出: AAABBBABB\

其他的碰撞算法

我在搜索相关的东西时,也发现了一个其他人设计的碰撞算法, 他使用了3个范围从64到95的字符做主要组合, 每个字符有32种可能, 3个就是十几行代码竟能破解Excel? Excel工作表保护密码的算法和破解研究 - 图7种组合, 组合计数上也覆盖了, 但是单单3个字符是不够的, 前面说过, 密码位数也有硬要求, 所以他在每个字符间插入了四个点(….)作为填充, 虽然下面有评论说他的算法有问题, 但是经过我的测试, 这个算法是全覆盖的, 是完整的, 对应上面的密码例子, 这里的和密码”excel”碰撞的字符串是@….J….X

虽然他这个字符串位数有11位, 但是他使用的不同字符个数很少, 而且也做到了刚刚好覆盖, 也是一个很不错的算法.

总结

从Excel保护破解到算法研究, 虽然绕了这么大一圈, 但是收获却很多. 首先, 这个程度的破解大概是普通人能接触到的范围比较广的程序中(Excel)加密算法强度最低的破解了, 写成程序不过十来行.

但是里面运用的知识还是比较复杂的, 刚开始看到那个VBS程序的时候完全无法逆推它为什么这么设计, 如果不看它的算法, 完全没有思路如何构造那样的碰撞(密码学和数学知识的匮乏), 到后来慢慢理解的它的思路, 再到后来能继续优化这个思路, 这个过程确实很有意思.

各位能看到这也不容易, 欢迎留言/评论/点赞/分享, Good Luck, Have Fun!