SHA256 найти частичное столкновение - PullRequest
Новая
       38

SHA256 найти частичное столкновение

0 голосов
/ 16 марта 2020

У меня есть два сообщения: 

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

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

Мне нужно найти SHA256 частичное столкновение этих двух сообщений ( 8 цифр ). Следовательно, первые 8 дайджестов SHA256 (messageA) == Первые 8 дайджестов SHA256 (messageB)

Мы можем поместить любые буквы и цифры в {}, оба {} должны иметь одинаковые string

Я пытался использовать метод грубой силы и день рождения с таблицей ha sh, чтобы решить эту проблему, но это стоит слишком много времени. Я знаю алгоритм определения цикла, такой как Флойд и Брент , однако я понятия не имею, как построить цикл для этой проблемы. Есть ли другие способы решения этой проблемы? Большое вам спасибо!

1 Ответ

2 голосов
/ 16 марта 2020

Это довольно тривиально, чтобы решить с атакой на день рождения. Вот как я это сделал в 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)

Если ваша попытка заняла слишком много времени, чтобы найти решение, либо вы либо просто допустили ошибку в своем кодировании, либо использовали неверный тип данных.

* Тип данных словаря 1024 * реализован с использованием таблиц ha sh. Это означает, что вы можете искать элементы словаря в постоянное время. Если бы вы реализовали seen, используя список вместо dict в приведенном выше коде, тогда поиск в строке 11 занял бы очень много времени.

Edit:

Если два 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()

Если вы спешите, возможно, вам стоит использовать графический процессор для ускорения вычислений ha sh.

...