On Sun, 29 Aug 2004, John Denker wrote:
>bear wrote: >> >> H2(H1) = H1( H1(M) xor H1( TT( M))) > >I think that was intended to be something like > > H2(M) = H1( H1(M) xor H1( TT( M))) > ^ Actually, it was intended to take a hash function as an argument and define a new hash function which is Joux-resistant in terms of it. Perhaps JR(H1)(M) = H1( H1 (M) xor H1( TT( M))) would have communicated the intent more clearly. Anyway, functions on functions that return functions kind of need lambda calculus for clear expression, which is why there was scheme pseudocode restating the definition following this. >OK, it looks like we are in agreement on the general >outline of a reasonable method for splinting broken hash >functions. >However I think the given example of a "Trivial Transformation" >is _too_ trivial. There are too many common strings for which >swapping halves of the first block leaves the string unchanged. Good point. I don't want to mess with the IV's though, because some hash functions may depend for their security on the exact value of the IV. > Also, I don't like the XOR function suggested above. It > is linear and totally lacking in one-wayness. That's compensated, I think, by the outer application of H1. But Hal Finney's response proposes using a 2n-bit to n-bit hash function on the concatenation of the two H1 results, which is definitely better. > That means > that an attacker has the option of making equal-and-opposite > (or in the case of XOR, just equal :-) changes in the H1 > output and the H1prime output, leaving the result of the > XOR unchanged. It still requires finding a double collision, so the work factor should be the same. > Therefore I restate my preference for combining the H1 and > H1 prime results nonlinearly, perhaps like this: > Hnew(M) = H1(M (+) H1prime(TT(M))) > where (+) denotes the string-concatenation operator. Okay, if your H1 and H1prime are nonidentical hash functions, I don't think you're getting any added security from the trivial-transformation here; Its purpose in my construction was to force divergence of the internal state between the two hash functions; why is it included in yours? >In case anybody didn't notice, bear's idea of applying the TT >operator within a given block has some good properties. In >particular it strengthens the hashing of short messages, >including one-block messages. > >However IMHO using a truly "trivial" transformation is really >under-doing it. Perhaps we should be thinking in terms of >Tasteful Transformations rather than Trivial Transformations. :-) You're right about that; a trivial transformation makes it too easy to construct an attack by constructing a block that reads the same under transformation as it does plaintext. Instead of swapping first and second halves of the block, probably the first block of the message should be replaced by its hash. Responding to your issue about xor being too insecure, by taking Hal Finney's suggestion of using a wider hash function to combine the outputs, And redefining TT for greater strength, the construction becomes H2(M) = Hnew (H1 (M) + H1( TT(M))) Where H2 is the Joux-resistant version of H1, which is our desired objective. TT now means replacing the first block of the message by its hash value under H1, and + denotes concatenation. However, this requires implementing an Hnew, which must take a *single* large block of input (the size of two H1 blocks) and produce a single H1-sized block of output. Since we all seem to agree that an Hnew is needed to make the suggestion concrete, what definition of Hnew do you prefer? > Also I suggest the transformation should be applied to each > and every block of the second stream, not just the first > block. Why? Divergence in internal state ought to be complete after the first block; constructing a message that would force the internal states of the two hash functions to ever reconverge would require the same work factor either way. I don't think a long-range permutation buys us anything. It's cheap and it doesn't hurt. We can include it if it makes us feel any more secure; but why should it make us feel any more secure? Bear --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]