胖蔡说技术
随便扯扯

MD5算法与彩虹表

什么是MD5?

MD5是一种被广泛使用的加密散列函数,最初常使用于校验文件传输后的完整性校验,通过校验文件传输前后的md5的异同来判断文件的传输完整性。现在被广泛使用在软件的密码加密中。可以将任何输入(数字、字符串或任何长度的文件)转换为包含 32 个十六进制字符的输出。

MD5的特点

  • 不可逆
MD5加密的过程本身就是一个衰减的过程,其最终的结果是对原始数据的一个有损计算。所以,我们无法通过最终生成的结果反向还原原始信息。理论上无法破解(不包括暴力破解等一些非常规的方式)
  • 恒定性
MD5加密在原始消息一致的情况下,加密产生的MD消息摘要也是恒定不变的。
  • 不唯一性
MD5 散列由 32 个十六进制字符组成。每个字符有 16 个可能的值,因此只有 16^32 个不同的 MD5 哈希值。那是3.402823e+38个不同的值,这是一个巨大的数字,但不是无限的,所以必然与MD5算法发生冲突。但是在现实生活中,在实际使用中遇到此类问题的可能性极低。2005 年 3 月,中国山东大学的王晓云和余洪波发表了一篇文章,他们描述了一种算法,该算法可以找到两个具有相同 MD5 哈希的 128 字节的不同序列。相关示例可以参考Peter Selinger网站的经典案例:https://www.mscs.dal.ca/~selinger/md5collision/

MD5加密类型

普通加密

常规MD5加密是以512位分组来处理输入信息,且每一分组又被划分16个32位子分组, MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成,将这四个32位分组级联后将生成一个128位散列值。 使用JS实现如下:
284f356fd49ddc5
加密流程
  • 求模补位
在MD5算法中,首先需要对信息进行填充,使其位长对512求余的结果等于448。因此,信息的位长(Bits Length)将被扩展至N512+448,N为一个非负整数,N可以是零。填充的方法如下,在信息的后面填充一个1和无数个0,直到满足上面的条件时才停止用0对信息的填充。
  • 扩展长度
完成求模补位后,将原始数据长度以64位的数据表示形式(二进制)添加到求模补位后的结果后面 。经过这两步的处理,信息的位长=N512+448+64=(N+1)*512,即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。
  • 初始化
MD5运算要用到一个128位的MD5缓存器,用来保存中间变量和最终结果。该缓存器又可看成是4个32位的寄存器A、B、C、D,初始化为:
A : 01 23 45 67 
B: 89 ab cd ef
C: fe dc ba 98 
D: 76 54 32 10
  • 数据段处理
首先定义4个非线性函数F、G、H、I,对输入的报文运算以512位数据段为单位进行处理。对每个数据段都要进行4轮的逻辑处理,在4轮中分别使用4个不同的函数F、G、H、I。每一轮以ABCD和当前的512位的块为输入,处理后送入ABCD(128位)。信息摘要最终处理成以A, B, C, D 的形式输出。也就是开始于A的低位在前的顺序字节,结束于D的高位在前的顺序字节。

加盐

为防止外部通过MD5反查密码明文,需要对MD5摘要结果掺入其他信息,称之为加盐。加盐的过程:
  • 生成一个随机数添加到需要加密的密文中(如时间戳)
  • 生成摘要,去盐校验【需要知道盐值】
// 代码实现采用node-crypto

// 加盐

let name = 'abcd'
let password = '123'
var timestamp = Date.parse(new Date()) / 1000
let user_ticket = utils.md5(utils.md5(utils.md5(name + utils.md5(password))) + timestamp)
console.log(user_ticket) =>0b3298cb3c20b08318c185aec803a929 //加盐的结果


// 去盐校验
let name = 'abcd'
let password = '123'
var timestamp = Date.parse(new Date()) / 1000
let load_password = utils.md5(utils.md5(name + utils.md5(password))) //储存密码
let user_ticket_client = utils.md5(utils.md5(utils.md5(name + utils.md5(password))) + timestamp) //客户端密码
let user_ticket_service = utils.md5(load_password + timestamp) //服务端再次加密计算 储存密码加 时间戳
console.log(user_ticket_client == user_ticket_service) => true //客户端已经加密和服务端再次加密做对比

彩虹表

 

彩虹表(Rainbow Table)是一种破解哈希算法的技术,是一款跨平台密码破解器,主要可以破解MD5、HASH等多种密码。它的性能非常让人震惊,在一台普通PC上辅以NVidia CUDA技术,对于NTLM算法可以达到最高每秒103,820,000,000次明文尝试(超过一千亿次),对于广泛使用的MD5也接近一千亿次。更神奇的是,彩虹表技术并非针对某种哈希算法的漏洞进行攻击,而是类似暴力破解,对于任何哈希算法都有效(包含md5)。 彩虹表是在字典法破解的基础上,通过时间内存替换法大幅度提高hash算法的破解速度,具体的破解算法内容过于高深不做探讨,有兴趣的小伙伴可参考该方面相关的专业论文:

获取彩虹表

彩虹表可以使用RainbowCrack或Cain来生成。RainbowCrack官网提供生成彩虹表的源码。一般的我们只需要下载已经生成的彩虹表就可以,文件较大,做好心理准备(大约120G左右)。点击下载。

使用

彩虹表破解可以使用专业的工具破解,常用工具有:
感兴趣的可是尝试破解玩玩

相关阅读

赞(0) 打赏
转载请附上原文出处链接:胖蔡说技术 » MD5算法与彩虹表
分享到: 更多 (0)

请小编喝杯咖啡~

支付宝扫一扫打赏

微信扫一扫打赏