Частота столкновений для усеченных хэшей SHA1

Question

С моим веб-приложением я храню кэшированные файлы с именем файла, сгенерированным хэшем, в различных подкаталогах для оптимизации уровней производительности. Один из способов, с помощью которого я мог бы повысить производительность, - это убедиться, что сгенерированные имена соответствуют структуре имен файлов 8.3, поэтому NTFS не нужно генерировать короткие имена файлов (я не смогу установить это в реестре).

Чтобы сделать это, хотя мне пришлось бы урезать хеш (я думал SHA1) до 8 символов, очевидно, это значительно увеличит вероятность столкновения. То, что я хотел бы знать, какова вероятность столкновения?

Я видел ответ здесь о полных коэффициентах коллизий SHA1, но моя математика ужасна, так что вычисление значения далеко от меня.

Answer 1

Поскольку SHA-1Выходные данные распределены равномерно, вы можете приблизить частоту столкновений, используя парадокс дня рождения:

Предположим, вы продолжаете n биты SHA-1 на выходе, есть ~50% вероятность того, что у вас будет столкновение в наборе, содержащем 2^(n/2) записи, или, другими словами, ваша частота столкновений примерно 1/2^(n/2)

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

Итак, здесь, если мы предположим, что каждый символ равен 1 байту (8 бит), то вы, скорее всего, столкнетесь с коллизией, если у вас ~2^(8*8/2) = 4294967296 записи (следовательно, частота столкновений будет 2.32 * 10^-8 что очень мало).

Учитывая частоту столкновений, которую вы обнаружили с помощью своей тестовой программы, ToSHA1Fingerprint() Функция возвращает шестнадцатеричную строку, которая означает, что ее подстрока из 8 символов представляет только 4 байта, и, следовательно, приблизительная частота столкновений, основанная на приведенной выше формуле, равна 1/2^(4*8/2) = 0.000015258789 или же 0.002%,

Answer 2

Похоже, что в любом случае частота столкновений слишком высока для моих нужд, я получаю тестирование на ~0,004% с использованием следующего кода.

const int Iterations = 10;
const int Maxitems = 360000;

for (int i = 0; i < Iterations; i++)
{
    List<string> paths = new List<string>();

    for (int j = 0; j < Maxitems; j++)
    {
        string path = Path.GetRandomFileName().ToSHA1Fingerprint()
                                              .Substring(0, 8);

        paths.Add(path);
    }

    int count = paths.Distinct().Count();

    double collisionRate = ((Maxitems - count) * 100D) / Maxitems;
    collisions.Add(collisionRate);
}

double averageCollisionRate = collisions.Average();