时间戳

首页 > 解决方案 > SHA256 查找部分冲突

algorithm - SHA256 查找部分冲突

问题描述

我有两条信息：

messageA: "Frank is one of the "best" students topicId{} "

messageB: "Frank is one of the "top" students topicId{} "

我需要找到这两条消息（8 位）的 SHA256 部分冲突。因此，SHA256(messageA) 的前 8 个摘要 == SHA256(messageB) 的前 8 个摘要

我们可以在 中放任何字母和数字{}，两个 {} 应该有相同的字符串

我已经尝试过使用哈希表的蛮力和生日攻击来解决这个问题，但它花费了太多时间。我知道像Floyd 和 Brent这样的循环检测算法，但是我不知道如何为这个问题构建循环。有没有其他方法可以解决这个问题？太感谢了！

标签： algorithmcryptographycryptanalysis

解决方案

用生日攻击来解决这个问题非常简单。这是我在 Python (v2) 中的做法：

def find_collision(ntries):
    from hashlib import sha256
    str1 = 'Frank is one of the "best" students topicId{%d} '
    str2 = 'Frank is one of the "top" students topicId{%d} '
    seen = {}
    for n in xrange(ntries):
        h = sha256(str1 % n).digest()[:4].encode('hex')
        seen[h] = n
    for n in xrange(ntries):
        h = sha256(str2 % n).digest()[:4].encode('hex')
        if h in seen:
            print str1 % seen[h]
            print str2 % n

find_collision(100000)

如果您的尝试花费了太长时间才找到解决方案，那么您要么只是在某处编码错误，要么您使用了错误的数据类型。

Python 的字典数据类型是使用哈希表实现的。这意味着您可以在恒定时间内搜索字典元素。如果您seen在上面的代码中使用列表而不是字典来实现，那么第 11 行的搜索将花费更长的时间。

编辑：

如果这两个topicId标记必须相同，那么——正如评论中所指出的——别无选择，只能通过大约 2 31个值的某个位置。您最终会发现碰撞，但可能需要很长时间。

让它在一夜之间运行，如果运气好的话，你会在早上得到答案：

def find_collision():
    from hashlib import sha256
    str1 = 'Frank is one of the "best" students topicId{%x} '
    str2 = 'Frank is one of the "top" students topicId{%x} '
    seen = {}
    n = 0
    while True:
        if sha256(str1 % n).digest()[:4] == sha256(str2 % n).digest()[:4]:
            print str1 % n
            print str2 % n
            break
        n += 1

find_collision()

如果您赶时间，您可以考虑使用 GPU 来加速哈希计算。

推荐阅读