Editing UUHash

{{Short description|Hash algorithm on the FastTrack network}}
'''UUHash''' is a [[hash function|hash algorithm]] employed by clients on the [[FastTrack]] network. It is employed for its ability to hash very large files in a very short period of time, even on older computers. However, this is achieved by only hashing a fraction of the file. This weakness makes it trivial to create a hash collision, allowing large sections to be completely altered without altering the [[checksum]].

This method is used by [[Kazaa]]. The weakness of UUHash is exploited by anti-[[Peer-to-peer file sharing|p2p]] agencies to [[Data corruption|corrupt]] downloads.<ref>
Thomas Mennecke.
[http://www.slyck.com/story1019.html How Overpeer was able to corrupt data on the FastTrack network].
2005.
</ref>

==How it works==

The UUHash is a 160-bit string that is usually [[Base64]]-encoded for presentation. It is a concatenation of an MD5 hash and a [[CRC32]] sum of selected chunks of the file.<ref>[http://sourceforge.net/projects/mldonkey/files/mldonkey/3.1.5/mldonkey-3.1.5.tar.bz2 MLDonkey source code], file ''src/utils/lib/fst_hash.c'', retrieved 2014-08-20</ref><ref>[https://web.archive.org/web/20091026175246/http://www.geocities.com/vlaibb/sig2dat/sig2dat3.11.a-src.zip sig2dat source code], file ''sig2dat.c'', function ''GetHashWin32'', retrieved 2014-08-20</ref>

The first 307,200 bytes (300 [[Kibibyte]], one "chunk size") of the file are [[MD5]]-hashed (less if file is shorter). The 32 bit [[little endian]] integer value ''smallhash'' is initialized to 0.

If the file is strictly larger than one chunk size, a series of chunks at file offsets of 2<sup>n</sup> MiB (n ≥ 0) and one chunk right at the end of the file are hashed using a CRC32 (polynomial 0xEDB88320 reversed, 0x04C11DB7 normal). The last chunk of the power-of-two series ends strictly ''more'' than one chunk size before the end of the file, i.e. there is always at least one unread byte between the last two chunks (if there are that many chunks).<ref group=footnote>[http://sourceforge.net/projects/bitcollider/ BitCollider/0.4.0] implemented this unfaithfully</ref> The end-of-file chunk may be shorter than one chunk size; it starts at or after one chunk size into the file. The CRC is initialized using ''smallhash'' and stored into ''smallhash''.

So, for example:
:offset 0 MiB, 300 KiB hashed with MD5
:offset 1 MiB, 300 KiB hashed with CRC32
:offset 2 MiB, 300 KiB hashed...
:offset 4 MiB, 300 KiB hashed...
:offset 8 MiB, 300 KiB hashed...
:...
:last 300 KiB of file hashed with CRC32

Finally, the bitwise complement of ''smallhash'' (still zero for files up to 300 KiB) is XORed together with the file size in bytes. The 160-bit UUHash is now the concatenation of the 128-bit MD5 hash and the final 32-bit ''smallhash'' value.

=== Test Vectors ===

Given below are hashes (base64 and hex) for strings of various lengths containing only <code>0x00</code> or <code>0xFF</code> bytes, generated by sig2dat.

Note ''here'' that all strings that have a complete MD5 chunk have the same 128-bit prefix because their first chunks are the same (either 0x00 or 0xFF). For files that have the same number of chunks the CRC part differs only because of the included file length (all chunks are identical, or this weren't the case). For files up to 300 KiB, the file length can be extracted from the last four bytes of the hash; ''smallhash'' is ~0.

{|class="wikitable"
! Input
! Base64
! Hexadecimal
|-
| 0 bytes
| <code>1B2M2Y8AsgTpgAmY7PhCfv////8=</code>
| <code>[[MD5#MD5 hashes|D41D8CD98F00B204E9800998ECF8427E]]-FFFFFFFF</code>
|-
| <code>0x00</code>, 1 byte
| <code>k7iFrf4NoInN9jSQT9Wfcf7///8=</code>
| <code>93B885ADFE0DA089CDF634904FD59F71-FEFFFFFF</code>
|-
| <code>0xFF</code>, 1 byte
| <code>AFlP1PQrpD/BygQnoFdilf7///8=</code>
| <code>00594FD4F42BA43FC1CA0427A0576295-FEFFFFFF</code>
|-
| <code>0x00</code>, 2 bytes
| <code>xBA/Ei0nZ3ydsUTK4TlKZv3///8=</code>
| <code>C4103F122D27677C9DB144CAE1394A66-FDFFFFFF</code>
|-
| <code>0xFF</code>, 2 bytes
| <code>qyoNKN5rd//dbHKv6tCZq/3///8=</code>
| <code>AB2A0D28DE6B77FFDD6C72AFEAD099AB-FDFFFFFF</code>
|-
| <code>0x00</code>, 307199 bytes (300 KiB - 1)
| <code>YK6+Fj6S4MGzEC9H9Bn3gQBQ+/8=</code>
| <code>60AEBE163E92E0C1B3102F47F419F781-0050FBFF</code>
|-
| <code>0xFF</code>, 307199 bytes (300 KiB - 1)
| <code>I+QujFtxa9pBOt5X6NMGsgBQ+/8=</code>
| <code>23E42E8C5B716BDA413ADE57E8D306B2-0050FBFF</code>
|-
| <code>0x00</code>, 307200 bytes (300 KiB)
| <code>kK7e2ZIs+JRup4WGNUk3JP9P+/8=</code>
| <code>90AEDED9922CF8946EA7858635493724-FF4FFBFF</code>
|-
| <code>0xFF</code>, 307200 bytes (300 KiB)
| <code>oBSYynx6vdDeUWtP5N4mAv9P+/8=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-FF4FFBFF</code>
|-
| <code>0x00</code>, 307201 bytes (300 KiB + 1)
| <code>kK7e2ZIs+JRup4WGNUk3JHOg+S0=</code>
| <code>90AEDED9922CF8946EA7858635493724-73A0F92D</code>
|-
| <code>0xFF</code>, 307201 bytes (300 KiB + 1)
| <code>oBSYynx6vdDeUWtP5N4mAv5P+wA=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-FE4FFB00</code>
|-
| <code>0x00</code>, 614399 bytes (600 KiB - 1)
| <code>kK7e2ZIs+JRup4WGNUk3JHCHqBQ=</code>
| <code>90AEDED9922CF8946EA7858635493724-7087A814</code>
|-
| <code>0xFF</code>, 614399 bytes (600 KiB - 1)
| <code>oBSYynx6vdDeUWtP5N4mAqgX6Xs=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-A817E97B</code>
|-
| <code>0x00</code>, 614400 bytes (600 KiB)
| <code>kK7e2ZIs+JRup4WGNUk3JGlfGn0=</code>
| <code>90AEDED9922CF8946EA7858635493724-695F1A7D</code>
|-
| <code>0xFF</code>, 614400 bytes (600 KiB)
| <code>oBSYynx6vdDeUWtP5N4mApKrf9g=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-92AB7FD8</code>
|-
| <code>0x00</code>, 614401 bytes (600 KiB + 1)
| <code>kK7e2ZIs+JRup4WGNUk3JGhfGn0=</code>
| <code>90AEDED9922CF8946EA7858635493724-685F1A7D</code>
|-
| <code>0xFF</code>, 614401 bytes (600 KiB + 1)
| <code>oBSYynx6vdDeUWtP5N4mApOrf9g=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-93AB7FD8</code>
|-
| <code>0x00</code>, 614402 bytes (600 KiB + 2)
| <code>kK7e2ZIs+JRup4WGNUk3JGtfGn0=</code>
| <code>90AEDED9922CF8946EA7858635493724-6B5F1A7D</code>
|-
| <code>0xFF</code>, 614402 bytes (600 KiB + 2)
| <code>oBSYynx6vdDeUWtP5N4mApCrf9g=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-90AB7FD8</code>
|-
| <code>0x00</code>, 16777216 bytes (16 MiB)
| <code>kK7e2ZIs+JRup4WGNUk3JN/b8qg=</code>
| <code>90AEDED9922CF8946EA7858635493724-DFDBF2A8</code>
|-
| <code>0xFF</code>, 16777216 bytes (16 MiB)
| <code>oBSYynx6vdDeUWtP5N4mAt0YF2Y=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-DD181766</code>
|-
| <code>0x00</code>, 17084416 bytes (16 MiB + 300 KiB)
| <code>kK7e2ZIs+JRup4WGNUk3JN9r9qg=</code>
| <code>90AEDED9922CF8946EA7858635493724-DF6BF6A8</code>
|-
| <code>0xFF</code>, 17084416 bytes (16 MiB + 300 KiB)
| <code>oBSYynx6vdDeUWtP5N4mAt2oE2Y=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-DDA81366</code>
|-
| <code>0x00</code>, 17084417 bytes (16 MiB + 300 KiB + 1)
| <code>kK7e2ZIs+JRup4WGNUk3JN5r9qg=</code>
| <code>90AEDED9922CF8946EA7858635493724-DE6BF6A8</code>
|-
| <code>0xFF</code>, 17084417 bytes (16 MiB + 300 KiB + 1)
| <code>oBSYynx6vdDeUWtP5N4mAtyoE2Y=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-DCA81366</code>
|-
| <code>0x00</code>, 17391616 bytes (16 MiB + 600 KiB)
| <code>kK7e2ZIs+JRup4WGNUk3JN+7+6g=</code>
| <code>90AEDED9922CF8946EA7858635493724-DFBBFBA8</code>
|-
| <code>0xFF</code>, 17391616 bytes (16 MiB + 600 KiB)
| <code>oBSYynx6vdDeUWtP5N4mAt14HmY=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-DD781E66</code>
|-
| <code>0x00</code>, 17391617 bytes (16 MiB + 600 KiB + 1)
| <code>kK7e2ZIs+JRup4WGNUk3JNzVMqw=</code>
| <code>90AEDED9922CF8946EA7858635493724-DCD532AC</code>
|-
| <code>0xFF</code>, 17391617 bytes (16 MiB + 600 KiB + 1)
| <code>oBSYynx6vdDeUWtP5N4mAgS1uWk=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-04B5B969</code>
|-
| <code>0x00</code>, 17391618 bytes (16 MiB + 600 KiB + 2)
| <code>kK7e2ZIs+JRup4WGNUk3JN/VMqw=</code>
| <code>90AEDED9922CF8946EA7858635493724-DFD532AC</code>
|-
| <code>0xFF</code>, 17391618 bytes (16 MiB + 600 KiB + 2)
| <code>oBSYynx6vdDeUWtP5N4mAge1uWk=</code>
| <code>A01498CA7C7ABDD0DE516B4FE4DE2602-07B5B969</code>
|}

==Sig2Dat==
The name UUHash derives from the [https://web.archive.org/web/20091026175246/http://www.geocities.com/vlaibb/tools.html sig2dat] utility which creates [[Uniform Resource Identifier|URI]]s referencing files on Kazaa. These URIs are of the form:
 sig2dat://|File: surprise.mp3|Length:5845871Bytes|UUHash:=1LDYkHDl65OprVz37xN1VSo9b00=

Not considering the fact that this [[URI]] format is not [[Request for Comments|RFC]] compliant, UUHash refers to the [[Base64]]-encoding of the hash and not the hash itself.

==Notes==
{{reflist|group=footnote}}

==External links==
{{reflist}}

{{DEFAULTSORT:Uuhash}}
[[Category:Cryptographic hash functions]]