Saturday, November 5, 2011

PHP's hash(): how tiger192,3 and tiger192,4 differ

PHP lists a handful of hash algorithms for Tiger:
  • tiger128,3 tiger160,3 tiger192,3
  • tiger128,4 tiger160,4 tiger192,4
What's the difference?  Which one is standard?  Is one harder to break?  Why don't any of the outputs match either of Wikipedia's examples?



The first number—128, 160, or 192—is easy.  It's the number of bits of output, so the 128/160/192 variants will return 16/20/24 bytes of output.  By default, it's in ASCII format, so the actual strings are 32/40/48 characters.  The shorter versions are simply the first bytes of the longer output, so any of the tiger___,3 functions will output a hash starting "24f0130c63ac93321616" when hashing the empty string.

I had to dip into the source code to understand the second number.  It is the number of passes that PHP performs when computing the hash.  The compression function (the compress macro) is set up to perform either 3 or 4 passes, with a key scheduling between each.  The code is slightly tricky because they store the distinction between 3 and 4 passes in 1 bit of the hash context, as the number of additional passes to perform.

The algorithms ending in ",3" are the standard Tiger algorithm; their output for the empty string matches the empty string's hash in the testtiger code from the Tiger website.  But the output is not in MSB-first order; see the note about Wikipedia below.  (The bug was filed with PHP as #60221; this naturally spawned #61307 when their fix changed the output order in PHP 5.4.0.)

The algorithms ending in ",4" are non-standard, and should perform 33% slower because there's 33% more work being done.  As I understand it, this extends Tiger to 32 rounds (from 24), which should make it significantly harder to break.  Disclaimer: I'm not a crypto expert, so you should consult with experts if you want accurate, up-to-date information on the security of your specific application.  Ideally, you'd be using a well-vetted library that already made a secure choice.

For the last question, Wikipedia prints the output MSB-first, but testtiger and PHP before 5.4.0 don't.  The testtiger code prints each 64-bit chunk in byte-swapped order: so 3293...f024 in the output is printed as 24f0...9332.  Therefore, although PHP's 3-pass algorithm is standard Tiger, its hashes won't match any software that chose the MSB-first representation instead.  (For instance, the Digest::Tiger NOTE for the Perl implementation explains that it returns hashes MSB-first.)  In that case, one of them needs to be reordered before the match is attempted.

No comments: