MD5的实现与“破解”

MD5的实现与“破解”

一、 概述

MD5（Message-Digest Algorithm 5）是一种广泛使用的密码散列函数。它于1991年由罗纳德·里维斯特设计出来，是MD4的改进版本。MD5的主要功能是提供一种将任意长度的消息转换成固定长度（128位，即16字节）的摘要的方法。这个过程通常被称为“散列”。

MD5的设计目的是为了提供一种安全的方式来存储和验证信息，比如在数据库中安全地存储密码。MD5散列是不可逆的，这意味着从产生的摘要中，无法恢复原始数据。先来看看MD5的一些简单的实际运用：

• 登录界面：在我们的登录界面中，我们需要输入账号密码，而后台收到用户输入的账号密码之后就会与数据库中的账号密码进行校验，那么现在有个疑问，如果黑客拖走了整个数据库，那么是不是所有用户的账号密码都裸奔了呢？其实不是，有了MD5实现，用户在数据库中的账号密码都是一个个散列值，黑客拖走了数据库但是他得到的也是散列值而不是真实的密码，没有一些特殊手段他也不能进行登录。
• 下载：我们在官网下载软件的时候一般都可以得到一个MD5值，如果我们不在官网下载而是在某某软件园下载的话，我们可以根据某某软件园下载的软件的MD5值与官网进行比较，来看看这个软件有没有被修改过。

然而，随着计算能力的增强和对MD5算法的深入分析，它在安全性方面的局限性逐渐暴露出来。特别是在2000年以后，研究人员发现了MD5的多个弱点，使得攻击者可以相对容易地生成相同MD5摘要的不同消息，这种情况被称为“碰撞”。因此，MD5不再被认为是一种安全的散列函数，尤其是在需要高安全性的场合。尽管如此，MD5由于其计算速度快和实现简单，在很多非安全性要求的应用中仍然在使用。例如，在一些老旧系统中，MD5仍用于验证数据完整性和生成文件的检验和。但在安全性要求较高的应用中，通常推荐使用更安全的散列函数，如SHA-256。

二、 MD5简单介绍

上面也说了，MD5的主要功能是提供一种将任意长度的消息转换成固定长度(128位/32个十六进制位/16字节)的摘要的方法，这个过程通常被称为“散列”，而通过这个密码散列函数的到的值，一般叫做散列值。先来看看一个MD5加密的例子：

序号	原始值	散列值(32个十六进制)
1	Hello World	B10A8DB164E0754105B7A99BE72E3FE5
2	Hello World	B10A8DB164E0754105B7A99BE72E3FE5
3	Hello World!	ED076287532E86365E841E92BFC50D8C

通过上面的表格MD5加密的例子可以得到，相同的原始值无论加密多少次，得到的散列值都是一样的，而相似度极大的原始值比如上面就多了一个感叹号，得到的散列值也是大有不同的。所以这为上面讲到的“登录界面”，“下载”的实现提供了基础。

三、 MD5的实现

MD5的实现大致可以分成3个主要部分：填充对齐，分块，多轮压缩。下面就来详细并且通俗的讲一下这个过程。首先我们知道所有文件实质上都是一个个由0/1比特位组成的，现在我们有一个文件M，它的比特位为N，即N是由一堆的01组成的东东。

• 填充对齐：不管N是多少位，输入的消息位数被填充为512整数倍位的内容。填充的规则就是在原始消息的末尾添加一个1然后用0补充(一定要有一个1)，直到只剩下64位，而剩下的64位则用来表示消息长度(以位为单位)。这时候就会有有疑问了如果原始消息长度为1000位，要是补齐的话不够65位，这样的情况也要继续补齐到1536位而不是1024位。甚至是原始消息长度刚好1024位也是这样——继续补齐！最终的内容就是一个为512整数倍的内容。大体如下所示：

原始数据(n位)	填充内容1(1~512位)	填充内容2(64位)
1011001…01001	1…000000000	表示消息长度的01串

• 分块：MD5的长度是固定了，它的作者规定了将这128个比特位分成4个部分，即32个比特位/8个十六进制数。之后，会设定4个32位(8个十六进制)整数作为初始的哈希值，通常用A、B、C、D来表示——A = 0x67452301，B = 0xEFCDAB89，C = 0x98BADCFE，D = 0x10325476。同样，填充后的比特内容也会被分为多个512位的大块。
• 多轮压缩：进入多轮压缩这一步，从第一个512位大块开始对每一个大块上进行多轮压缩，把当前散列值(md5的四个部分)的四个部分A、B、C、D分别复制一份。压缩一共有四轮，每轮使用数据块和和md5的四个部分进行一系列包括与、或、非和循环移位的位操作。把abcd各自更新4次，四轮压缩一共把abcd更新了16次，完成4四轮压缩之后把abcd加回去当前散列值的四个部分，散列值更新。接着就是下一个大块。大体如下图所示，具体的与或非循环移位操作不必深究：

下面附上C++的MD5加密代码，感兴趣可以研究一下：

#include <iostream>
#include <cstring>
#include <cstdint>
#include <string>

class MD5 {
public:
    MD5(const std::string& message) {
        init();
        update(reinterpret_cast<const uint8_t*>(message.c_str()), message.length());
        finalize();
    }

    const uint8_t* digest() const {
        return buffer;
    }

    std::string toString() const {
        const char hexDigits[] = "0123456789abcdef";
        std::string str;
        for (int i = 0; i < 16; ++i) {
            str.append(1, hexDigits[(buffer[i] >> 4) & 0x0F]);
            str.append(1, hexDigits[buffer[i] & 0x0F]);
        }
        return str;
    }

private:
    void init() {
        h0 = 0x67452301;
        h1 = 0xEFCDAB89;
        h2 = 0x98BADCFE;
        h3 = 0x10325476;
        unprocessedBytes = 0;
        size = 0;
    }

    void update(const uint8_t* msg, size_t length) {
        size += length;
        size_t i = 0;

        if (unprocessedBytes > 0) {
            if (length + unprocessedBytes >= 64) {
                memcpy(&processedBytes[unprocessedBytes], msg, 64 - unprocessedBytes);
                processBlock(processedBytes);
                length -= 64 - unprocessedBytes;
                i += 64 - unprocessedBytes;
                unprocessedBytes = 0;
            }
        }

        for (; i + 63 < length; i += 64) {
            processBlock(msg + i);
        }

        if (i < length) {
            memcpy(processedBytes, msg + i, length - i);
            unprocessedBytes = length - i;
        }
    }

    void finalize() {
        uint8_t finalBlock[128];
        size_t finalBlockSize = unprocessedBytes;

        memcpy(finalBlock, processedBytes, unprocessedBytes);

        finalBlock[finalBlockSize++] = 0x80;
        if (finalBlockSize > 56) {
            memset(finalBlock + finalBlockSize, 0, 64 - finalBlockSize);
            processBlock(finalBlock);
            finalBlockSize = 0;
        }

        memset(finalBlock + finalBlockSize, 0, 56 - finalBlockSize);
        uint64_t sizeInBits = size * 8;
        memcpy(finalBlock + 56, &sizeInBits, 8);

        processBlock(finalBlock);

        memcpy(buffer, &h0, 4);
        memcpy(buffer + 4, &h1, 4);
        memcpy(buffer + 8, &h2, 4);
        memcpy(buffer + 12, &h3, 4);
    }

    void processBlock(const uint8_t* block) {
        uint32_t a = h0;
        uint32_t b = h1;
        uint32_t c = h2;
        uint32_t d = h3;

        uint32_t M[16];
        for (int i = 0; i < 16; ++i) {
            M[i] = (block[i * 4 + 0] << 0) |
                (block[i * 4 + 1] << 8) |
                (block[i * 4 + 2] << 16) |
                (block[i * 4 + 3] << 24);
        }

        // 主循环
        for (unsigned int i = 0; i < 64; ++i) {
            uint32_t F, g;
            if (i < 16) {
                F = (b & c) | ((~b) & d);
                g = i;
            }
            else if (i < 32) {
                F = (d & b) | ((~d) & c);
                g = (5 * i + 1) % 16;
            }
            else if (i < 48) {
                F = b ^ c ^ d;
                g = (3 * i + 5) % 16;
            }
            else {
                F = c ^ (b | (~d));
                g = (7 * i) % 16;
            }

            uint32_t D = d;
            d = c;
            c = b;
            b = b + leftRotate((a + F + K[i] + M[g]), S[i]);
            a = D;
        }

        h0 += a;
        h1 += b;
        h2 += c;
        h3 += d;
    }

    static inline uint32_t leftRotate(uint32_t x, uint32_t c) {
        return (x << c) | (x >> (32 - c));
    }

    uint32_t h0, h1, h2, h3;
    uint8_t buffer[16];
    uint8_t processedBytes[64];
    size_t unprocessedBytes;
    uint64_t size;

    static constexpr uint32_t K[64] = {
        0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
        0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
        0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
        0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
        0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
        0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
        0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
        0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
        0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
        0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
        0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
        0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
        0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
        0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
        0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
        0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
    };

    static constexpr uint32_t S[64] = {
        7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
        5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
        4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
        6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21
    };
};

int main() {
    std::string message;
    std::cout << "Enter message: ";
    std::getline(std::cin, message);

    MD5 md5(message);
    std::cout << "MD5 digest: " << md5.toString() << std::endl;

    return 0;
}

四、 MD5的“破解”

我们已经知道了它的加密过程吧，现在我们来破解它。首先我们先明确一点，我们需要的是什么，是原文还是寻找能产生相同散列值的内容。MD5事实上是一个散列函数而不是一个加密函数，他不是一个可逆的过程，即不能通过散列值得出原始内容，就像你不能由一个128位的散列值恢复成一部2个G的电影，这是违背信息论的。同样前面也讲过多轮压缩的过程中也会进行与或非等操作，比如：1(原文)|1=1，你能通过后两个1来确认前面的是1还是0吗？这显然是不能的。那这样我们攻击个屁！

仔细想想，破解它一定要得到原始内容吗？我们好像忽略了一个东西，那就是消息内容和散列值是一一对应的吗？显然不是，原始内容是无穷无尽的，而散列值只有那128位，这可以得出一个散列值对应的也是无穷个原始内容，而这个原始内容我们很难找到罢了。去寻找两个能产生一样散列值的不同原始内容，叫做“碰撞”。

对于MD5的破解，大体上可以分成3类，原像攻击，第二原像攻击，碰撞攻击：

• 原像攻击：原像攻击是由MD5散列值推出算出原始数据，这好比于暴力破解，但是事实上实现却是很困难的，对于一个100位的数，它的组合有2的100次方中情况，何况是1000位甚至更多呢？所以原像攻击在目前并没有成功攻击的案例。
• 第二原像攻击：第二原像攻击是给定了一个MD5值和原始数据，需要找到一个与给定输入具有相同散列值的不同输入。第二原像攻击的目标是针对一个特定的、已知的消息，找到另一个不同的消息，使得两者产生相同的哈希值。
• 碰撞攻击：碰撞攻击是先并没有MD5值和原始数据，攻击者要做的就是要找到两个不同的消息，这两个消息被MD5散列函数处理之后产生相同的哈希值，关键就是这两个消息都是由攻击者选择的，而不是基于一个已知的特定消息。

五、MD5的“破解”方法

1. 暴力破解：穷举法&字典法

穷举法和字典法都是利用计算机资源没有太多头绪尝试碰撞已知的MD5码。对于穷举法，就是不断尝试各种字符的排列组合，看哪一个组合可以对的上，这个方法的缺点就是太耗费时间，一个8位数的字母和数字组合的密码的组合有两百万亿种；对于字典法，就是把已知的常见的密码和对应的散列值存在一起，这种方法相对于穷举法更加理性一些，缺点就是耗费空间。

2. 时间和空间的折中：哈希链表法&彩虹表法

2.1. 哈希链表法的过程

1. 生成链：

   • 起始点：选择一系列可能的原始值（如密码）作为链的起始点。
   • 交替应用：对每个起始点先应用哈希函数（如MD5），再应用还原函数，重复这个过程多次，形成一条哈希链。

2. 存储链端点：

   • 只存储每条链的起始点和终点，不存储中间过程的值。

3. 破解过程：

   • 当你有一个目标哈希值需要破解时，使用还原函数对它进行处理，并检查是否与已存储链的末端匹配。
   • 如果匹配，沿着对应链条使用相同的哈希和还原函数回溯，直到找到产生目标哈希值的原始值。

2.2. 哈希链表可能遇到的疑惑

1. 为什么不能直接逆向哈希值：
   • 哈希函数（如MD5）是设计为单向且不可逆的。这意味着不能直接从哈希值推导出确切的原始值。
2. 还原函数的作用和限制：
   • 还原函数不是逆哈希函数。它只是从哈希值生成可能的原始值，而这个值可能不是实际产生哈希的真实数据，也就是再哈希一次不能得到原来的值。
   • 还原函数的输出是基于算法的任意决定，并不保证能覆盖所有可能的原始值。
3. 为什么需要回溯：
   • 由于还原函数并不能保证找到正确的原始值，所以需要通过回溯过程来验证每个可能的原始值，看它是否真的能产生目标哈希值。
   • 这种方法考虑到了哈希碰撞的情况，即不同的原始值可能产生相同的哈希值。

2.3. 哈希链表举例

H(X)：生成信息摘要的哈希函数，比如MD5，SHA256。

R(X)：从信息摘要种转化为另一个字符串的还原函数，其中R(X)的定义域是H(X)的值域，R(X)的值域是H(X)的定义域，需要注意的就是这两个并非反函数关系。

通过交替运算H和R若干次，可以形成一个链条，假设原文是aaaaaa，哈希长度位32位，那么哈希链表就是这样子：

同时我们只需要将首段和尾端存入哈希表里面。那接下来就来演示一下获得原文的过程：
给定信息摘要：920ECF10，R(920ECF10)=kiebgt，查询哈希表可以找到首段是aaaaaa，因此摘要920ECF10极有可能在这个链表里面。接下来从aaaaaa开始，重新交替运算R(X)H(X)，看看摘要值时候是其中一次H(X)的结果，如果是的话，前面一个节点就是可能的原文。

2.4. 彩虹表法的过程

彩虹表是哈希链表法的一种改进。它通过引入“彩虹”效果来减少链之间的重叠和冲突。彩虹表的关键特点包括：

1. 不同的还原函数：在构建彩虹表的每一步中，使用不同的还原函数。这意味着即使两条链在某一点具有相同的中间哈希值，由于接下来使用的还原函数不同，它们也会分叉成不同的路径。
2. 优化的存储与搜索：这种方法减少了链之间的重叠和碰撞，使得彩虹表在存储和搜索时更为高效。

2.5. 区别

1. 处理碰撞和重叠：彩虹表通过使用多种还原函数来减少链之间的碰撞和重叠，而传统的哈希链表法在这方面效率较低。
2. 存储和效率：彩虹表通常比传统的哈希链表更有效率，因为它们减少了重复计算，并优化了搜索过程。
3. 实现复杂性：彩虹表的实现相对于传统的哈希链表更复杂，因为它需要管理和应用多种还原函数。

2.6. 关于中间值的疑惑

在彩虹表中，一条哈希链从一个特定的起始点（原始密码候选）开始，通过交替应用哈希函数和还原函数，形成了一系列的中间值。这条链实际上在“探索”一系列可能的密码。

不同的潜在密码：每次应用还原函数时，都可能产生一个不同的潜在密码。因此，一条链实际上代表了从起始点出发，通过多次变换能够到达的多个不同的潜在密码。而这个潜在密码我来梳理一下，这里用彩虹表来解释，在彩虹表中，一个明文A应用一次哈希函数得到一个散列值A，然后散列值应用一次还原函数得到明文B，明文B应用哈希函数得到散列值B，同理得到明文C，散列值C…假如里面存在潜在相同的散列值，那么可以得到前一个的还原函数是有效的，这个还原函数恰巧将上一个散列值给还原成我们想要的明文，这个明文又被哈希函数转化为那个相同的散列值。

3. 差分攻击

利用差分攻击破解MD5是在2004年我国山东大学的王小云教授及其团队发现的，他们找到了快速发现大量MD5碰撞的方法，即找到两个原始消息使他们的MD5散列值相同，并于2005年发表，他们的研究基于模块化差分，大体思路是先找到局部碰撞，然后分析差分如何传播，找到差分路径，再利用消息修改技术最后得到能产生碰撞的消息对。

差分攻击是一种密码分析技术，它被用来破解加密算法，包括哈希函数如MD5。然而，需要注意的是，差分攻击主要用于对称加密算法，而对于哈希函数，特别是像MD5这样的，通常采用的是其他类型的攻击方法，如碰撞攻击。不过，为了解释差分攻击的原理，我会首先描述它在对称加密算法中的应用，然后讨论它在哈希函数中的应用情景。

3.1. 差分攻击原理

在对称加密算法中

1. 基本原理：

   • 差分攻击依赖于观察当输入改变时输出如何变化的模式。攻击者会对加密算法的输入进行小的、有控制的改变，并观察输出的差异。
   • 目的是找出输入和输出之间的相关性，从而推断出加密密钥或算法的一部分内部操作。

2. 步骤：

   • 选择一对明文，它们之间有已知的差异。
   • 加密这两个明文，观察密文之间的差异。
   • 通过分析这些差异，尝试推断加密密钥或算法的某些特性。

在哈希函数中

1. 碰撞攻击：

   • 在哈希函数（如MD5）中，差分攻击通常是用于寻找碰撞的一种方法。这意味着寻找两个不同的输入，它们产生相同的哈希值。
   • 攻击者会尝试微小改变输入，并分析如何影响哈希值的改变，从而找到两个哈希值相同的不同输入。

2. MD5的脆弱性：

   • MD5由于设计上的缺陷，对这类攻击特别敏感。已经有多种方法展示了如何找到MD5的碰撞，即两个不同的输入产生相同的哈希值。

3.2. 举例说明

差分攻击

4. 相同前缀碰撞

李德刚, 杨阳, 曾光. 基于选择前缀攻击的哈希函数多文件格式碰撞[J]. 密码学报, 202X, X(X): 1–16. [DOI: 10.13868/j.cnki.jcr.000659]

相同前缀碰撞方法，该方法利用两组消息块序列，通过精心设计，使得它们经过MD5处理后能够产生相同的中间哈希值（IHV）。在此基础上，可以在这些块之后附加任意长度相同的后缀而不影响碰撞结果。这个过程包括：

1. 选择消息块：从两个不同的消息块对 {B0, B1} 和 {B′0, B′1} 开始，这些块在内容上略有差异。

2. 构建碰撞：通过对这些消息块的处理，确保它们在经历MD5哈希过程后，即使有不同的输入块，也能得到相同的中间哈希值（IHV）。

3. 附加后缀：在经过处理的块后面附加任意相同的后缀（S），产生的完整消息为 {P||Sr||B0||B1||S} 和 {P||Sr||B′0||B′1||S}，其中 P 是前缀，Sr 是填充部分，保证整个消息长度符合MD5处理的要求。

4. 结果：最终，这两个完整的消息将产生相同的MD5哈希值，即使它们在 {B0, B1} 与 {B′0, B′1} 部分有所不同。

这个方法也应用到了差分原理。