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

Question

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

Допустим, это CRC-32, поэтому этот файл должен иметь длину 4 байта.

Answer 1

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

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

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

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

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

CC4FBB6A (big-endian)
FFFFFFFF (с прямым порядком байтов и с прямым порядком байтов)
32F3B737 (прописные буквы ASCII)

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

Answer 2

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

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

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

Answer 3

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

Предполагается, что значение 32-битной контрольной суммы записывается в файл с прямым порядком байтов (я не нашел фиксированной точки с этим байтом с прямым порядком байтов):

#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

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

Answer 4

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

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

Answer 5

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

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

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