A Decade of TTH: Its Selection and Uncertain Future

NMDC and ADC rely on the Tiger Tree Hash to identify files. DC requires a cryptographic hash function to avoid the previous morass of pervasive similar, but not identical, files. A bare cryptographic hash primitive such as SHA-1 did not suffice because not only did the files need identification as a whole but in separate parts, allowing reliable resuming and multi-source downloading, and per-segment integrity verification (RevConnect unsuccessfully attempted to reliably use multi-source downloading precisely because it could not rely on cryptographic hashes).

Looking for inspiration from other P2P software, I found that BitTorrent used (and uses) piecewise SHA-1 with per-torrent segment sizes. Since the DC share model asks that same hash function work across entire shares, this does not work. eDonkey2000 and eMule, with per-user shares similar to those of DC, resolved this with fixed, 9MB piecewise MD4, but this segment size scaled poorly, ensured that fixing corruption demanded at least 9MB of retransmission, and used the weak and soon-broken MD4. Gnutella, though, had found an elegant, scalable solution in TTH.

This Tiger Tree hash, which I thus copied from Gnutella, scales to both large and small files while depending on what was at the time a secure-looking Tiger hash function. It smoothly, adaptively sizes a hash tree while retaining interoperability between all such sizes of files files on a hub. By 2003, I had released BCDC++ which used TTH. However, the initial version of hash trees implemented by Gnutella and DC used the same hash primitive for leaf and internal tree nodes. This left it open to collisions, fixed by using different leaf and internal hash primitives. Both Gnutella and DC quickly adopted this fix and DC has followed this second version of THEX to specify TTH for the last decade.

Though it has served DC well, TTH might soon need a replacement. The Tiger hash primitive underlying it by now lists as broken due to a combination of a practical 1-bit pseudocollision attack on all rounds, a similarly feasible full collision on all but 5 of its 24 rounds, and full, albeit theoretical, 24-round pre-images (“Advanced Meet-in-the-Middle Preimage Attacks”, 2010, Guo et al). If one can collide or find preimages of Tiger, one can also trivially collide or find preimages of TTH. We are therefore investigating alternative cryptographic hash primitives to which we might transition as Tiger looks increasingly insecure and collision-prone, focusing on SHA-2 and SHA-3.

10 Responses to A Decade of TTH: Its Selection and Uncertain Future

  1. ophite1 says:

    Might I suggest Skein (rhymes with “rain”). Skein was a frontrunner SHA-3 finalist.

    Unlike Keccak (selected as SHA-3 largely because of the sponge construction being very different to SHA-2, although this is still a matter of some controversy and was recognised as something of an unnecessary and arbitary choice), Skein is very fast and efficient in software on existing processors (~5.5 cycles per byte). Skein 512-256 is both more secure and faster than SHA-256, and faster than SHA-3 256.

    Crucially, unlike the other contenders, Skein actually features a native parallelizable tree hash among its configurable options as part of the hash specification!

    A Skein Tree Hash (STH?) could be created simply by setting the block size (4K? You could have more than one layer of leaves if you wanted: 4K/1M?). Fast parallelizable routines already exist on multiple platforms which could work well for this. It might possibly even end up faster than TTH on multicore, and is undoubtedly much more secure.

    Please consider STH as a viable successor to TTH. I think it’s got just what it takes.

    http://www.skein-hash.info/sites/default/files/skein1.3.pdf
    http://www.skein-hash.info/sites/default/files/NIST_CD_102610.zip

  2. cologic says:

    I’ll indeed consider Skein with its tree hash as a TTH replacement. The NIST report on SHA-3 finalists [1] finds that Skein has a large security margin, along with BLAKE is the fastest function on x86 and x86, twice as fast as Keccak and SHA-512 and almost three times as fast as SHA-256 depending on specific CPU (figures 1-3). Further, I’m definitely open to replacement not just of Tiger but the current Merkle Hash Trees that so inefficiently, inelegantly, and in an ad-hoc manner prepended 0x00 and 0x01 bytes.

    I have a couple of concerns about Skein: first, while Python 3.4 already supports Keccak and OpenSSL assuredly will, Skein may remain less easy to use efficiently especially in commonly interpreted languages where one depends on the user installing native libraries to achieve reasonable speed. Relatedly, just as the ARMv8 architecture has specific support for SHA-1 and SHA-2, future CPUs may add Keccak support, while they won’t for Skein. Neither of these is a tremendously strong objection, but worth noting.

    I’ll wait to see how SHA-3 standardization of Keccak progresses, partly because the Keccak authors have also discussed an as-yet not fully specified tree hashing mode. However, because both Skein & Keccak have or will have official tree hashing modes (whereas SHA-2 does not), Skein does look more attractive to me than SHA-2; it’s useful to have a cryptographically peer-reviewed hash function as a whole, including the tree hashing, not simply hash primitive. I therefore currently do favor Keccak or Skein.

    [1] “Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition”, http://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf

  3. ophite1 says:

    Regarding Python: see PySkein. Already implemented. Even includes the hash tree mode as far as I can see.

    I wouldn’t expect to see hardware rollout for either new hash algorithm in anything significant within the next 3 years. In fact, hardware support for even SHA-256 is still extremely rare and only usually specified in near-future platforms such as AArch64 (as you state). Meanwhile, future x86 processor archs such as Haswell are not taking the AES-NI direction and supporting individual ciphers/hashes with dedicated core space, but instead extending microarchitecture and vector processing with instructions that actively assist many different constructs, such as RORX, MULX, PCLMULQDQ and other similar instructions, so as to broaden their options and utility.

    So as far as I can see, the mode most important to DC implementors in the foreseeable future is efficient software implementation (with as much instruction set assistance as possible) on current and near-future processors.

    I submit that Skein 512-256 wins that race, compellingly. Current unpublished results, broadly speaking, bearing in mind that results from Haswell engineering samples may not be reliable (cycles per byte in 4K blocks, lower is better):
    TIGER/192: Ivy Bridge: ~6 c/b
    SHA-256: Ivy Bridge: 13-14 c/b; Haswell (AVX2/RORX wide MultiBlock): ~7 c/b?
    Keccak: Ivy Bridge: 10-11 c/b; Haswell (AVX2/RORX sponge MultiBlock): ~8 c/b?; ARMv7: 97.37 c/b (!!)
    Skein-512-256: Ivy Bridge: 4.8-5.5 c/b; Haswell (AVX2/RORX wide MultiBlock): ~3 c/b?; ARMv7 (skein-arm): 15.4 c/b (25.2 even without NEON)

    Published results from 2012 (slightly worse reading for Keccak!): http://eprint.iacr.org/2012/004.pdf

    As near as I can tell, it therefore looks like a Skein Tree Hash based on Skein-512 with a 256-bit output and 4K blocks (or, possibly, a 4096 byte/1048576 byte multilevel tree, if multiple levels of leaves can be supported without upheaval?) would be both significantly faster than Tiger Tree Hash, naturally parallelizable, and much more secure than TTH. A similar tree hash construct based on Keccak (whether using wide blocks thanks to the sponge construct or short blocks) or SHA-256, would be roughly speaking, around half the speed or worse, and would be slower than TTH, not faster.

    I find a speed difference of that magnitude highly compelling in deciding between two functions of similar security. Bearing in mind also that Skein received its close scrutiny and cryptanalysis during the competition including the tree-hash mode, and Keccak did not, it makes me hard not to consider a potential Skein Tree Hash a significantly stronger proposal.

    There is no rush to implement SHA-3 in anything – as Schneier points out, there is no compelling need to, given what was learned during the competition, and SHA-256 still seeming to stand fast in its existing roles, despite NIST’s apparent anxiety. There is not even a TLS ciphersuite specified in a draft that includes SHA-3 yet, and FIPS 180-5 is still in early unpublished drafts as far as I can tell.

    I therefore suspect a similar situation, library-wise, as to the AES finalists; crypto libraries are perhaps more likely to implement Keccak alongside Skein and possibly BLAKE, much as they implemented Rijndael alongside Twofish and Serpent. Perhaps more so, given the relative performance (Rijndael was the fastest in the pack: Keccak, decidedly not so). Your thoughts are appreciated.

    • cologic says:

      I agree both that the speed difference with negligible demonstrated cryptographic weakness compels one to keep Skein in mind and that by passing through the intense cryptanalytic scrutiny of the NIST competition complete with its tree hash mode it has relative to DC’s needs demonstrated by default a higher empirical security than Keccak. The inglorious history of Merkle Hash Trees in P2P applications underlines the value especially of this latter distinction.

      As such, it seems warranted, barring a surprisingly critical break in Tiger within the next several months, to wait not only for Keccak’s NIST-standardized tree hashing mode but additionally peer review of it minimally tantamount to that focused upon Skein’s tree hashes during the competition before considering an entire Keccak-based cryptosystem to possess a comparable expected security as one premised upon a hash primitive of Skein.

      This lack of rush to implement SHA-3 that you observe implise, further, that by the time the process of standardizing and peer-reviewing Keccak’s upcoming tree hasing mode adequately occurs, the library support landscape likely may evolve sufficiently such that evaluating hash functions currently by that metric can and should should wait and does not meaningfully discriminate between Keccak and Skein.

  4. klondike says:

    This is not just a thing of Skein being faster, the session hash is used also to protect the user password on the (many) unencrypted ADC servers around and to ensure CIDs and PIDs are valid.

    A problem with Skein is that it has some already working Cryptanalisys, yeah it isn’t over the full hash function but this things usually build over time so collisions or preimages may be possible in the future.

    Also about the speed, keep into mind that SHA-3 is more likely to get hardware acceleration, as is the case with AES, in the future than skein so in the future, this speed differences may reverse.

    Anyways, as cologic says we still should wait and see, the change will happen but we are still waiting for the dust to settle with SHA-3 before making a choice.

    • ophite1 says:

      All the useful entrants have cryptanalysis results. That’s the entire point of having the competition, and it’s how you judge how strong they are relative to each other.

      All attacks build over time – they never get worse! The point however of a competition is to place them before intense academic public scrutiny, to know where they can be now with the different entries and learn from that, and that information was used to refine all of the entries – including not just Skein but also Keccak, which experienced practical collisions, distinguishers and even preimages in reduced-round versions as well as zero-sums in the building blocks and an unaligned rebound attack. The point of this reduced-round analysis is to judge how far each of the hashes are from breaking – pretty damn far in the case of the finalists! – and to strengthen them via refinement where needed. That distance is the security margin, and in general the more the better (although of course that has to be balanced with performance and other desirable characteristics). Don’t mistake those for suggesting that any of them are in any way weak in any practical sense: that’s fundamentally misreading the results. I’d be worried if they did NOT have any cryptanalysis, because then we would not know in relative terms how secure they looked.

      All of the SHA-3 finalists have comfortable security margins for the foreseeable future and are at least as strong as the SHA-2 functions (none of which have any known practical attacks either and, as Schneier remarks, a surprisingly comfortable margin considering moves were made to replace them), which are stronger than SHA-1 (which should be regarded as potentially collidable in practice, although as yet none have been publically demonstrated as it’s slightly harder to extend the attack than originally expected). TIGER/192 is probably about as strong as SHA-1 on current results: looking wobbly, about to fall, paper-thin margin, should move off it.

      Any of the SHA-2 or SHA-3 functions would be a potentially good choice for a replacement. I make the particular case for Skein-512-256 (Skein v1.3 of course, as specified in the final round) because alone among all those functions it has a native parallellizable tree hash mode as part of its definition which faced the gauntlet of the competition and survived intact, and it is also among the very fastest of its class (notably, faster than the current TIGER/192), despite also being among the ones with a high security margin.

      • klondike says:

        The problem is that you should also look towards the future. The reason why these competitions tend to choose a winner is so people can then focus their efforts on this winner, either on breaking them or on making them more efficient. See AES for example, there is AES-NI, AES support in other processors too, but what about the other finalists? Nothing in hardware, at most fast software implementations which took some time.

      • ophite1 says:

        The reason for the competition was to advance the state of the art in the face of some compelling results against MD5 and SHA-1 that made NIST fear for the future of SHA-2 (though it appears these fears have not come to pass, and there are now strong recommendations that SHA-2 need not be deprecated – we have SHA-3 in reserve “just in case”). We’ve learned a lot about hash cryptanalysis in the intervening time. (Actually, there were many leading cryptographers, including Schneier, who respectfully suggested that NIST perhaps need not pick a winner.)

        AMD and Intel have both made it clear that they don’t need to and won’t add direct exclusive hash (or RSA) acceleration support for any algorithm in the next few generations (there are too many already-deployed algorithms – MD5, SHA-1, SHA-256, SHA-512 – and they’d need to spend individual die space on each of them). Rather, they will add reusable extensions (notably PCLMULQDQ and AVX2) which can be used to very significantly increase the efficiency of software implementations of many different algorithms (including all the above Keccak and Skein, as well as RSA/DH/ECDH/ECDSA etc and non-cryptographic algorithms too), and extensions like those are in Ivy Bridge, Haswell, Piledriver, Steamroller, Jaguar.

        Given such primitives, Skein performs damn well (and still faster than Keccak).

      • klondike says:

        I know the recommendations about SHA-2 not needing deprecation, still it hash problems like length extension attacks which don’t happen with Keccak, and maybe others.

        I also know perfectly what AVX2 and similar will accomplish, and I doubt I’m the only one wishing to see how things like the gather instruction perform on S-Boxes. Still I will remain very skeptic of such instructions sets until I can see an implementation of AES using those as fast as the AES-NI implementation, but I really doubt we’ll get to see that because AVX2 is meant to be used for handling the calculation over various datasets at once and not over a single one.

        Also, even if Intel and AMD are not planning on adding support for SHA-2 or SHA-3 in the near future (neither did they with AES BTW) things may change. The authors of Keccak coming from the embeddded world know better than anybody the importance of embedded systems. So have parts of the DC community too since there are requests for clients able to run on an Android phone or an ARM NAS. It’s more likely this platforms will be the ones taking the lead in such steps as has happened before and so far I have yet to see a similar statemetnt coming from them.

  5. poy says:

    Keccak authors have submitted a paper describing a flexible tree hashing, called “Sakura”: http://eprint.iacr.org/2013/231 (still an RFC).

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s