Insecurity of Tweak Chain Hashing

Authors:
Thomas Ristenpart

Abstract:
For my final project in Professor Rogaway's ECS 227 I investigated Tweakable Block Ciphers by Liskov, Rivest, and Wagner. They introduce several modes of operation, one of which is Tweak Hash Chaining, a hash function built from tweakable blockciphers. They leave the security of TCH as an open question. I answered this question in the negative, showing attacks against TCH when it is instantiated with either tweakable blockciphers given in their paper.

References:
Manuscript

Full Version:
This is available as a pdf

List of Updates:
(Feb 1, 2006) It's been brought to my attention that there's some confusion as to who "got there first" regarding these attacks on TCH. After a chat with John, it is definitely the case that Black et al. beat me to the punch, and had them as early as 2002 (the exact nature of these attacks unbeknownst to me while I was working on the project). Their Eurocrypt paper (linked below) appeared slightly after I did my attacks, but John had posted a note about it on his website much earlier than December 2003. I'm sorry if this caused any confusion: John and company should get the credit! I'll leave my write-up of the attacks here for the curious reader, but one should reference their paper in regards to these attacks.

(Earlier update) My result has been subsumed by Black, Cochran, and Shrimpton, who have shown that no efficient blockcipher-based hash functions are secure. The TCH mode of operation suggested by Liskov et al. falls into this efficient category. Check out their paper.