破解hash算法

Author Avatar
白日鸡生蛋 2月6日
  • 在其它设备中阅读本文章

前言
  有小伙伴问我哪个哈希算法被谁破解了,怎么破解的。那我就写一下吧。
  指路:
   一种防机器人识别的验证码生成器
   重要提醒:验证码生成器的哈希算法存在安全漏洞,已替换为 MD5 算法

被谁破解了
  其实是被我自己破解了。我做这个项目的时候,就非常注重安全问题。在决定采用 hash 算法之前,就翻阅了不少关于该算法的资料,其中有提到 hash 算法只能通过暴力破解,所以我就没有再考虑该算法的安全问题了。在项目正式发布后,我一直专注于提高验证码的防机器人能力,在原来(图一)的基础上增加了更多的干扰元素(如图二所示),并增强对比度以保证人看得清。但效果病不理想,过滤率一直在 90.5% 左右。
图一
图二
  无举下,只能寻求他法,最终做成了这个样子(图三)。经连续一万次测试过滤率达 100%。(10 亿次测试跑了差不多 3 天了还没结束,日志文件已经 200MB 了,我也许不应该搞那么多内容输出的)
图三
  我很满意,同时我又将目光投向了 hash 算法。
  时正午夜,辗转反侧之际,突然此算法就被我破解了。
怎么破解的
  首先,我们来回顾以下这个 hash 算法。

s[0]*63^(n-1) + s[1]*63^(n-2) + ... + s[n-1]

  验证码的长度为 4,于是

hash = ((s[0]*63+s[1])*63+s[3])*63+s[4]

  我们来逆推一下,

s[3] = hash % 63 + 63 * n, n为自然数
s[2] = (hash - s[3]) / 63 % 63 + 63 * n, n为自然数
s[1] = ((hash - s[3]) / 63 - s[2]) / 63 % 63 + 63 * n, n为自然数
s[0] = (((hash - s[3]) / 63 - s[2]) / 63 - s[1]) / 63

  又因为 s[m]∈58[48, 57]∪[65, 71]∪[97,122] 所以 n = 0 或 1。
  从中可以看出逆推的不确定性来自于 n 的取值。因为 s[m] 大于 63 的概率为 32/42,所以每个 n 都取 1,成功破解的概率为

(32 / 42) ^ 3 ≈ 0.4423

  但事实上我们既有 s[m] 准确的取值范围,可以对 n 的取值作进一步的限制,因此成功破解的概率可以大于 0.4423。
后记
  替换成 MD5 算法后被算法破解的几率几乎为 0,但不防暴力破解。这个项目只用了 32 个字符,字符串长度为 4,因而仅有 32^4 个情况,我们只要把这几种情况(对于计算机来说确实只是几种情况)的 MD5 码全部计算出来,就可以成功破解了。解决的方法就是把原来字符串拼接上一个随机字符串,再计算 MD5 码。