UUHash - UUHash

UUHash это алгоритм хеширования нанятые клиентами на Быстрый трек сеть. Он используется из-за его способности хэшировать очень большие файлы за очень короткий период времени даже на старых компьютерах. Однако это достигается за счет хеширования только части файла. Эта слабость делает тривиальным создание хеш-коллизии, позволяя полностью изменять большие разделы без изменения контрольная сумма.

Этот метод используется Kazaa. Слабость UUHash используется анти-p2p агентства испорченный скачивает.[1]

Как это устроено

UUHash - это 160-битная строка, которая обычно Base64 -кодируется для презентации. Это конкатенация хэша MD5 и CRC32 сумма выбранных фрагментов файла.[2][3]

Первые 307 200 байт (300 Кибибайт, один "размер блока") файла MD5 -хешированный (меньше, если файл короче). 32-битный прямой порядок байтов целочисленное значение smallhash инициализируется 0.

Если размер файла строго больше, чем один размер блока, серия блоков со смещением файла 2п MiB (n ≥ 0) и один фрагмент в конце файла хешируются с использованием CRC32 (полином 0xEDB88320 перевернут, 0x04C11DB7 нормальный). Последний кусок серии о силе двух заканчивается строго более чем один размер блока до конца файла, то есть всегда есть по крайней мере один непрочитанный байт между двумя последними блоками (если их так много).[сноска 1] Фрагмент конца файла может быть короче одного размера порции; он начинается с размера одного блока в файле или после него. CRC инициализируется с помощью smallhash и хранится в smallhash.

Так, например:

смещение 0 MiB, 300 KiB хешируется с помощью MD5
смещение 1 MiB, 300 KiB хешировано с CRC32
смещение 2 МиБ, хеширование 300 КБ ...
смещение 4 МиБ, хеширование 300 КБ ...
смещение 8 МиБ, хеширование 300 КБ ...
...
последние 300 Кбайт файла хешируются с помощью CRC32

Наконец, поразрядное дополнение smallhash (по-прежнему ноль для файлов размером до 300 КБ) выполняется XOR вместе с размером файла в байтах. 160-битный UUHash теперь представляет собой конкатенацию 128-битного хеша MD5 и последнего 32-битного smallhash ценить.

Тестовые векторы

Даны хэши (base64 и hex) для строк различной длины, содержащих только байты 0x00 или 0xFF:

Длина0x000xFF
Base64ШестнадцатеричныйBase64Шестнадцатеричный
01B2M2Y8AsgTpgAmY7PhCfv //// 8 =D41D8CD98F00B204E9800998ECF8427E -FFFFFFFF1B2M2Y8AsgTpgAmY7PhCfv //// 8 =D41D8CD98F00B204E9800998ECF8427E-FFFFFFFF
1k7iFrf4NoInN9jSQT9Wfcf7 /// 8 =93B885ADFE0DA089CDF634904FD59F71-FEFFFFFFAFlP1PQrpD / BygQnoFdilf7 /// 8 =00594FD4F42BA43FC1CA0427A0576295-FEFFFFFF
2xBA / Ei0nZ3ydsUTK4TlKZv3 /// 8 =C4103F122D27677C9DB144CAE1394A66-FDFFFFFFqyoNKN5rd // dbHKv6tCZq / 3 /// 8 =AB2A0D28DE6B77FFDD6C72AFEAD099AB-FDFFFFFF
307199 (300 Кбайт - 1)YK6 + Fj6S4MGzEC9H9Bn3gQBQ + / 8 =60AEBE163E92E0C1B3102F47F419F781-0050FBFFЯ + QujFtxa9pBOt5X6NMGsgBQ + / 8 =23E42E8C5B716BDA413ADE57E8D306B2-0050FBFF
307200 (300 КБ)kK7e2ZIs + JRup4WGNUk3JP9P + / 8 =90AEDED9922CF8946EA7858635493724-FF4FFBFFoBSYynx6vdDeUWtP5N4mAv9P + / 8 =A01498CA7C7ABDD0DE516B4FE4DE2602-FF4FFBFF
307201 (300 КБ + 1)kK7e2ZIs + JRup4WGNUk3JHOg + S0 =90AEDED9922CF8946EA7858635493724-73A0F92DoBSYynx6vdDeUWtP5N4mAv5P + wA =A01498CA7C7ABDD0DE516B4FE4DE2602-FE4FFB00
614399 (600 Кбайт - 1)kK7e2ZIs + JRup4WGNUk3JHCHqBQ =90AEDED9922CF8946EA7858635493724-7087A814oBSYynx6vdDeUWtP5N4mAqgX6Xs =A01498CA7C7ABDD0DE516B4FE4DE2602-A817E97B
614400 (600 КБ)kK7e2ZIs + JRup4WGNUk3JGlfGn0 =90AEDED9922CF8946EA7858635493724-695F1A7DoBSYynx6vdDeUWtP5N4mApKrf9g =A01498CA7C7ABDD0DE516B4FE4DE2602-92AB7FD8
614401 (600 Кбайт + 1)kK7e2ZIs + JRup4WGNUk3JGhfGn0 =90AEDED9922CF8946EA7858635493724-685F1A7DoBSYynx6vdDeUWtP5N4mApOrf9g =A01498CA7C7ABDD0DE516B4FE4DE2602-93AB7FD8
614402 (600 КБ + 2)kK7e2ZIs + JRup4WGNUk3JGtfGn0 =90AEDED9922CF8946EA7858635493724-6B5F1A7DoBSYynx6vdDeUWtP5N4mApCrf9g =A01498CA7C7ABDD0DE516B4FE4DE2602-90AB7FD8
16777216 (16 МиБ)kK7e2ZIs + JRup4WGNUk3JN / b8qg =90AEDED9922CF8946EA7858635493724-DFDBF2A8oBSYynx6vdDeUWtP5N4mAt0YF2Y =A01498CA7C7ABDD0DE516B4FE4DE2602-DD181766
17084416 (16 МиБ + 300 КБ)kK7e2ZIs + JRup4WGNUk3JN9r9qg =90AEDED9922CF8946EA7858635493724-DF6BF6A8oBSYynx6vdDeUWtP5N4mAt2oE2Y =A01498CA7C7ABDD0DE516B4FE4DE2602-DDA81366
17084417 (16 МиБ + 300 КБ + 1)kK7e2ZIs + JRup4WGNUk3JN5r9qg =90AEDED9922CF8946EA7858635493724-DE6BF6A8oBSYynx6vdDeUWtP5N4mAtyoE2Y =A01498CA7C7ABDD0DE516B4FE4DE2602-DCA81366
17391616 (16 МиБ + 600 КБ)kK7e2ZIs + JRup4WGNUk3JN + 7 + 6g =90AEDED9922CF8946EA7858635493724-DFBBFBA8oBSYynx6vdDeUWtP5N4mAt14HmY =A01498CA7C7ABDD0DE516B4FE4DE2602-DD781E66
17391617 (16 МиБ + 600 КБ + 1)kK7e2ZIs + JRup4WGNUk3JNzVMqw =90AEDED9922CF8946EA7858635493724-DCD532ACoBSYynx6vdDeUWtP5N4mAgS1uWk =A01498CA7C7ABDD0DE516B4FE4DE2602-04B5B969
17391618 (16 МиБ + 600 КБ + 2)kK7e2ZIs + JRup4WGNUk3JN / VMqw =90AEDED9922CF8946EA7858635493724-DFD532ACoBSYynx6vdDeUWtP5N4mAge1uWk =A01498CA7C7ABDD0DE516B4FE4DE2602-07B5B969

Обратите внимание, что все строки с полным блоком MD5 имеют одинаковый 128-битный префикс. Для файлов с одинаковым количеством фрагментов часть CRC отличается только из-за длины включенного файла (все фрагменты идентичны, или это было не так). Для файлов размером до 300 КиБ длину файла можно извлечь из последних четырех байтов хэша; smallhash составляет ~ 0.

Sig2Dat

Название UUHash происходит от sig2dat утилита, которая создает URI ссылки на файлы на Kazaa. Эти URI имеют форму:

sig2dat: // | Файл: удивление.mp3 | Длина: 5845871Байт | UUHash: = 1LDYkHDl65OprVz37xN1VSo9b00 =

Не считая того, что это URI формат не RFC совместимый, UUHash относится к Base64 -кодирование хеша, а не самого хеша.

Примечания

  1. ^ BitCollider / 0.4.0 реализовал это неверно

внешняя ссылка

  1. ^ Томас Меннеке.Как Overpeer смог повредить данные в сети FastTrack.2005.
  2. ^ Исходный код MLDonkey, файл src / utils / lib / fst_hash.c, дата обращения 20.08.2014
  3. ^ исходный код sig2dat, файл sig2dat.c, функция GetHashWin32, дата обращения 20.08.2014