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

Это довольно просто решить с помощью атаки на день рождения. Вот как я это сделал в 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 ³¹ значений. В конечном итоге вы обнаружите столкновение, но это может занять много времени.

Просто оставьте это работать на ночь, и, если повезет, вы получите ответ утром:

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()

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

Я предполагаю, что пробел в конце строк в вопросе был намеренным, поэтому я оставил его.

Фрэнк - один из лучших студентов. TopicId {59220691223} 6026d9b3 23898bcd7ecdbcbcd575b0a1d9dc22fd9e60074aefcbaade494a50ae

Фрэнк - один из лучших студентов. TopicId {59220691223} 6026d9b3 1ba780bb9973e7cfc8c9f74a35b54448d441a61cc9bf8db0fcae5280

На самом деле потребовалось около 7 миллиардов попыток, чтобы найти кого-то с помощью грубой силы, намного больше, чем я ожидал.

Я считаю, что 2 ^ 32 составляет примерно 4,3 миллиарда, поэтому шанс не найти совпадения после 4,3 миллиарда попыток составляет около 36,78%.

На самом деле я нашел совпадение примерно после 7 миллиардов попыток, вероятность отсутствия совпадений из 7 миллиардов попыток была меньше 20%.

Это код C ++, который я использовал для работы в 7 потоках, каждый поток получает свою начальную точку и завершается, как только в любом потоке обнаруживается совпадение. Каждый поток также обновляет свой прогресс до cout каждые 1 миллион попыток.

Я быстро перешел к тому месту, где было найдено совпадение на threadId = 5, поэтому его выполнение занимает меньше минуты. Но если вы измените начальную точку, вы можете поискать другие совпадения.

И я также не уверен, как можно использовать Флойд и Брент, поскольку в строках должен использоваться один и тот же topicId, поэтому вы ограничены как префиксом, так и суффиксом.

/*
To compile go get picosha2 header file from https://github.com/okdshin/PicoSHA2 
Copy this code into same directory as picosha2.h file, save it as hash.cpp for example.
On Linux go to command line and cd to directory where these files are. 

To compile it:
g++ -O2 -o hash hash.cpp -l pthread

And run it:
./hash

*/

#include <iostream>
#include <string>
#include <thread>
#include <mutex>

// I used picoSHA2 header only file for the hashing
// https://github.com/okdshin/PicoSHA2
#include "picosha2.h"


// return 1st 4 bytes (8 chars) of SHA256 hash
std::string hash8(const std::string& src_str) {
    std::vector<unsigned char> hash(picosha2::k_digest_size);
    picosha2::hash256(src_str.begin(), src_str.end(), hash.begin(), hash.end());
    return picosha2::bytes_to_hex_string(hash.begin(), hash.begin() + 4);
}

bool done = false;
std::mutex mtxCout;

void work(unsigned long long threadId) {
    std::string a = "Frank is one of the \"best\" students topicId{",
        b = "Frank is one of the \"top\" students topicId{";
        
    // Each thread gets a different starting point, I've fast forwarded to the part 
    // where I found the match so this won't take long to run if you try it, < 1 minute.
    // If you want to run a while drop the last "+ 150000000ULL" term and it will run 
    // for about 1 billion total (150 million each thread, assuming 7 threads) take 
    // about 30 minutes on Linux.
    // Collision occurred on threadId = 5, so if you change it to use less than 6 threads  
    // then your mileage may vary.
    
    unsigned long long start = threadId * (11666666667ULL + 147000000ULL) + 150000000ULL;
    unsigned long long x = start;
    
    for (;;) {
        // Not concerned with making the reading/updating "done" flag atomic, unlikely
        // 2 collisions are found at once on separate threads, and writing to cout 
        // is guarded anyway.
        
        if (done) return;
        std::string xs = std::to_string(x++);
        std::string hashA = hash8(a + xs + "} "), hashB = hash8(b + xs + "} ");
        
        if (hashA == hashB) {
            std::lock_guard<std::mutex> lock(mtxCout);
            std::cout << "*** SOLVED ***" << std::endl;
            std::cout << (x-1) << std::endl;
            std::cout << "\"" << a << (x - 1) << "} \" = " << hashA << std::endl;
            std::cout << "\"" << b << (x - 1) << "} \"  = " << hashB << std::endl;
            done = true;
            return;
        }
        
        if (((x - start) % 1000000ULL) == 0) {
            std::lock_guard<std::mutex> lock(mtxCout);
            std::cout << "thread: " << threadId << " = " << (x-start) 
                << " tries so far" << std::endl;
        }
    }
}

void runBruteForce() {
    const int NUM_THREADS = 7;
    std::thread threads[NUM_THREADS];
    for (int i = 0; i < NUM_THREADS; i++) threads[i] = std::thread(work, i);
    for (int i = 0; i < NUM_THREADS; i++) threads[i].join();
}

int main(int argc, char** argv) {
    runBruteForce();
    return 0;
}