Как найти контрольную сумму той же контрольной суммы? (вопрос о собеседовании)

Ответ 1

Может быть какой-то умный математический способ выяснить это (или доказать, что он не существует), если вы знаете, как работает алгоритм.

Но поскольку я ленив, и CRC32 имеет только 2 ^ 32 значения, я бы переборщил его. Ожидая, что алгоритм пройдет все значения 2 ^ 32, я бы использовал Google и Stack Overflow, чтобы выяснить, есть ли у кого-то решение.

В случае SHA-1, MD5 и других криптографически безопасных алгоритмов более или менее, я бы запутался математиками, которые разработали эти алгоритмы и просто сдались.

РЕДАКТИРОВАТЬ 1: Жесткое принуждение... Я так давно нашел его; CC4FBB6A в кодировке big-endian. Там может быть еще больше. Я проверяю 4 разных кодировки: ASCII в верхнем и нижнем регистре, а также бинарные big-endian и little-endian.

РЕДАКТИРОВАТЬ 2: Грубая сила. Вот результаты:

CC4FBB6A (big-endian)
FFFFFFFF (big-endian и little-endian)
32F3B737 (верхний регистр ASCII)

Код здесь. На моем разогнанном C2Q6600, который занимает около 1,5 часов для запуска. Теперь эта программа является однопоточной, но было бы легко сделать ее многопоточной, что обеспечило бы хорошую линейную масштабируемость.

Ответ 2

Помимо Джерри Коффина и Эско Луонтолы хорошие ответы на необычную проблему, я хотел бы добавить:

Математически мы ищем X таких, что F (X) = X, где F - контрольная функция, а X - сами данные. Поскольку вывод контрольной суммы имеет фиксированный размер, а ввод, который мы ищем, имеет тот же размер, , нет гарантии, что такой X даже существует!. Очень может быть, что каждое входное значение фиксированный размер коррелирует с другим значением этого размера.

РЕДАКТИРОВАТЬ: В вашем вопросе не указывается точный способ, по которому контрольная сумма должна быть отформатирована в файле, поэтому я предположил, что вы имеете в виду байт-представление контрольной суммы. Когда появляются строки, кодировки и форматированные строки, все становится более сложным.

Ответ 3

Не имея каких-либо конкретных указаний об обратном, я бы определил контрольную сумму несуществующих данных как несуществующую контрольную сумму, поэтому создание пустого файла выполнило бы это требование.

Другим типичным методом является отрицательная контрольная сумма - то есть после того, как данные вы напишете значение, которое делает контрольную сумму всего файла (включая контрольную сумму), равным нулю. В этом случае вы пишете контрольную сумму 0, и все это получается.

Ответ 4

Грубая сила. Это Adler32, который я ранее не реализовал, и не тестировал тестирование, поэтому вполне вероятно, что я испортил его. Я бы не ожидал, что исправленная версия будет работать значительно медленнее, хотя, если я не сделал что-то колоссально неправильно.

Это предполагает, что 32-битное значение контрольной суммы записывается в файл little-endian (я не нашел неподвижную точку с ним big-endian):

#include <iostream>
#include <stdint.h>
#include <iomanip>

const int modulus = 65521;

void checkAllAdlers(uint32_t sofar, int depth, uint32_t a, uint32_t b) {
    if (depth == 4) {
        if ((b << 16) + a == sofar) {
            std::cout << "Got a fixed point: 0x" << 
                std::hex << std::setw(8) << std::setfill('0') << 
                sofar << "\n";
        }
        return;
    }
    for (uint32_t i = 0; i < 256; ++i) {
        uint32_t newa = a + i;
        if (newa >= modulus) newa -= modulus;
        uint32_t newb = b + a;
        if (newb >= modulus) newb -= modulus;

        checkAllAdlers(sofar + (i << (depth*8)), depth + 1, newa, newb);
    }
    return;
}

int main() {
    checkAllAdlers(0, 0, 1, 0);
}

Вывод:

$ g++     adler32fp.cpp   -o adler32fp -O3 && time ./adler32fp
Got a fixed point: 0x03fb01fe

real    0m31.215s
user    0m30.326s
sys     0m0.015s

[Edit: исправлено несколько ошибок, я не уверен в правильности этого кода;) В любом случае вы получаете идею: 32-битная контрольная сумма, которая использует каждый бит ввода только один раз, очень дешева для грубой силы, Контрольные суммы обычно предназначены для быстрого вычисления, тогда как хэши обычно намного медленнее, хотя они имеют поверхностно похожие эффекты. Если ваша контрольная сумма была "2 раунда Adler32" (это означает, что целевая контрольная сумма была результатом вычисления контрольной суммы, а затем вычисления контрольной суммы этой контрольной суммы), то мой рекурсивный подход не помог бы так много, было бы меньше между входами с общим префиксом. MD5 имеет 4 раунда, SHA-512 имеет 80.]

Ответ 5

Направьте его. CRC-32 дает вам строку длиной 8, содержащую цифры и буквы A-F (другими словами, это шестнадцатеричное число). Попробуйте каждую комбинацию, предоставив вам 16 ⁸= множество возможностей. Затем хешируйте каждую возможность и посмотрите, дает ли она исходную строку.

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

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