Коллизии ставок для обрезанных SHA1- хэшей

Question

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

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

Я видел ответ here на полной скорости столкновений хэшей SHA1, но моя математика ужасна, поэтому вычисление ценности намного превосходит меня.

Answer 1

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

Предположим, вы держите n биты SHA-1 выхода, есть ~ 50% вероятность того, что вам или, другими словами, ваша ставка равна 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();