Re: More problems with hash functions
Jerry Leichter writes:
> It all depends on how you define an attack, and how you choose to define your
> security. I explored the "outer edge": Distinguishability from a random
> function. For a random function from {0,1}*->{0,1}^k, we expect to have to do
> 2^k work (where the unit of work is an evaluation of the function) per
> collision. The collisions are all "independent" - if you've found N, you have
> ... N. The next one you want still costs you 2^k work.
I don't believe this correct. Joux said that for a true random function,
finding a multicollision of degree j, i.e. j distinct values which hash
to the same thing, takes 2^((j-1)*k/j) for a k-bit hash. He mentioned
a Crypto paper by David Wagner from a few years ago which showed how
to do this. See http://www.cs.berkeley.edu/~daw/papers/genbday.html .
This means that the work for a (j+1)-collision is about 2^(k/j^2) times
harder than for a j-collision, not 2^k times harder.
Now, this is not done by first finding a j-collision and then looking
for a new value that matches; that would, as you say, take 2^k times
the work. Rather, one collects enough hashes and then matches them up
in an efficient way to find the (j+1)-collision.
The wide-internal-path proposal will therefore satisfy the constraints
about multicollisions. With a 2k bit wide internal path for a k bit hash,
it will take 2^k work to find an internal collision. With some multiple
of this, Joux's attack finds large multicollisions. But as the paper by
Wagner shows, you can find arbitrarily large multicollisions in a true
random k-bit function with less than 2^k work. Since Joux's attack
takes more than this, it does not distinguish this hash construction
from a random function.
Hal
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
| > However ... *any* on-line algorithm falls to a Joux-style attack. An
| > algorithm with fixed internal memory that can only read its input linearly,
| > exactly once, can be modeled as an FSM. A Joux-style attack then is: Find
| > a pair of inputs M1 and M1' that, starting from the fixed initial state, both
| > leave the FSM in state S. Now find a pair of inputs M2 and M2' that, starting
| > from S, leave the FSM in state S'. Then for the cost of finding these two
| > collisions, we have *four* distinct collisions as before. More generally,
| > by just continuing from state S' to S'' and so on, for the cost of k
| > single collision searches, we get 2^k collisions.
|
| That's an interesting point. One counter example I can offer is my
| earlier suggestion to use a wide path internally between the stages.
| The analysis suggested that if the internal path was twice the width
| of the output of the hash, the Joux attack was avoided. Basically if
| the hash output width is n, and the internal width is 2n, then it will
| take 2^n to find an internal collision. And the overall hash strength
| is never more than 2^n against any attack, since you can exhaustively
| invert the function for that effort. So nothing based on internal
| collisions can weaken a hash built around this principle.
|
| It's not a particularly appealing design strategy due to its apparent
| inefficiency. But if you're right about the general vulnerability of
| hashes that support incremental hashing, as any useful hash surely must,
| then perhaps it is worth exploring.
It all depends on how you define an attack, and how you choose to define your
security. I explored the "outer edge": Distinguishability from a random
function. For a random function from {0,1}*->{0,1}^k, we expect to have to do
2^k work (where the unit of work is an evaluation of the function) per
collision. The collisions are all "independent" - if you've found N, you have
... N. The next one you want still costs you 2^k work. However ... no on-
line function can actually be this hard, because a Joux-style attack lets you
combine collisions and find them with much less than the expected work.
Because a Joux-style attack works exponentially well, the cost for a very
large number of collisions is arbitrarily small. Note that this has nothing
to do with the number of internal states: One can distinguish random on-line
functions (in the sense I defined) from random functions (My criterion of
"infinitely many extendible collision pairs" may be too generous; you may need
some kind of minimum density of "extendibile collision pairs".)
You can certainly "de-rate" such a function by discarding some of the bits
of the output and considering the range of the output to be {0,1}^l, l < k.
But I don't see how that helps: In the limit, collisions become arbirarily
cheap, and making collisions easier can only decrease the cost of finding
them.
If the question is how close to the ultimate limit you can get a function
*constructed in a particular way*, then, yes, passing more internal state may
help. In fact, it's the only thing that can, if you want an on-line
algorithm - you have nothing else available to vary! A full analysis in this
direction, though, should have *two* security parameters: The current one,
the size of the output; and the amount of memory required. After all, MD5
(for example) is only defined on inputs of up to 2^64 bytes. If I allow 2^64
bytes of internal state, then the "on-line" qualifier becomes meaningless.
-- Jerry
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
On Fri, 27 Aug 2004, Hal Finney wrote: >Jerry Leichter writes: >> However ... *any* on-line algorithm falls to a Joux-style attack. >That's an interesting point. One counter example I can offer is my >earlier suggestion to use a wide path internally between the stages. >The analysis suggested that if the internal path was twice the width >of the output of the hash, the Joux attack was avoided. "Avoided" is too strong a term here. What you're doing is making the course twice as long because now the runners are twice as fast. The Joux attack still "works" in principle, in that finding a series of k block collisions gives 2^k message collisions; All that you're doing by making the internal path wider is making the block collisions harder to find. When you make them harder to find in such a way as to compensate exactly for the advantage from the Joux attack, you're not "avoiding" the attack so much as "compensating for" it. Still, it looks like you're exactly right that that's one good way to have an online algorithm that the Joux attack doesn't give any advantage against; if you want a 256-bit hash, you pass at least 512 bits of internal state from one block to the next. I had another brainstorm about this last night, which was to use an encryption algorithm for the block function; that way there are no block-level collisions in the first place. Unfortunately, that doesn't cut it; even if there are no block-level collisions on the state passed forward, there can still be collisions on state passed forward for every two blocks. Instead of searching for a collision of internal state in single blocks, the attacker would then be searching for it in block pairs. Given the same amount of internal state passed between blocks, the search would be no more difficult than it is now; for the price of finding k block-length collisions, the attacker gets 2^k colliding sequences. So far, your suggestion of passing twice as much internal state between blocks looks like the only sound and simple solution yet proposed. Bear - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
Jerry Leichter writes: > However ... *any* on-line algorithm falls to a Joux-style attack. An > algorithm with fixed internal memory that can only read its input linearly, > exactly once, can be modeled as an FSM. A Joux-style attack then is: Find > a pair of inputs M1 and M1' that, starting from the fixed initial state, both > leave the FSM in state S. Now find a pair of inputs M2 and M2' that, starting > from S, leave the FSM in state S'. Then for the cost of finding these two > collisions, we have *four* distinct collisions as before. More generally, > by just continuing from state S' to S'' and so on, for the cost of k > single collision searches, we get 2^k collisions. That's an interesting point. One counter example I can offer is my earlier suggestion to use a wide path internally between the stages. The analysis suggested that if the internal path was twice the width of the output of the hash, the Joux attack was avoided. Basically if the hash output width is n, and the internal width is 2n, then it will take 2^n to find an internal collision. And the overall hash strength is never more than 2^n against any attack, since you can exhaustively invert the function for that effort. So nothing based on internal collisions can weaken a hash built around this principle. It's not a particularly appealing design strategy due to its apparent inefficiency. But if you're right about the general vulnerability of hashes that support incremental hashing, as any useful hash surely must, then perhaps it is worth exploring. Hal Finney - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
| Bear writes:
| > One interesting idea which I came up with and haven't seen a way
| > past yet is to XOR each block with a value computed from its
| > sequence number, then compute the hash function on the blocks in
| > a nonsequential order based on the plaintext of the blocks
| > in their new order.
|
| This is an interesting idea, but it does not fully prevent the Joux
| attack. This is seen most obviously in the two block case, where
| your method can at most increase the attacker's work by a factor of 2.
| Joux shows how to find a 4-collision using 2*2^(n/2) work, while it should
| take 2^(3n/4) work. In the case of a 160 bit hash this is the difference
| between 2^81 and 2^120. Doubling the work to find the 4-collision will
| not do much to address this discrepency.
|
| Even in the more general case, where Joux puts k blocks together to
| generate 2^k multicollisions, I can see a way to attack your method,
| with an increase in the work by only a factor of k^2
There's a more general problem with the algorithm: It isn't on-line. An
implementation requires either an unbounded internal state, or the ability to
re-read the input stream. The first is obviously impossible, the second a
problem for many common uses of hash functions (in communications, as opposed
to storage).
However ... *any* on-line algorithm falls to a Joux-style attack. An
algorithm with fixed internal memory that can only read its input linearly,
exactly once, can be modeled as an FSM. A Joux-style attack then is: Find
a pair of inputs M1 and M1' that, starting from the fixed initial state, both
leave the FSM in state S. Now find a pair of inputs M2 and M2' that, starting
from S, leave the FSM in state S'. Then for the cost of finding these two
collisions, we have *four* distinct collisions as before. More generally,
by just continuing from state S' to S'' and so on, for the cost of k
single collision searches, we get 2^k collisions.
The nominal security of the FSM is its number of states; for k large enough,
we certainly get "too many" collisions compared to a random function.
What this shows is that our vague notion that a hash function should behave
like a random function can't work. On-line-ness always kills that. (In
fact, even given the function random access to its input doesn't help: An FSM
can only specify a finite number of random "places" to look in the input.
If the FSM can only specify an absolute location, it can't work on arbitrarily
long inputs. If it can specify a location relative to the current position,
you can re-write the machine as a linear one that gets repeated copies of
blocks of a fixed size.)
This is really just the prefix property writ large. Define an on-line
function f:{0,1}*->{0,1}^k as one with the property that there exist
infinitely many pairs of strings Si, Si' with the property that, for any S in
{0,1}*, f(Si||S) = f(Si'||S). (In particular, this is true for S the empty
string, so f(Si) = f(Si').) Then the most we can expect of an (on-line)
hash function is that it act like a function picked at random from the set of
on-line functions. (This, of course, ignores all the other desireable
properties - we want to choose from a subset of the on-line functions.)
Getting a security parameter in there is a bit tricky. An obvious first cut
is to say an on-line function has minimum length n if the shortest Si has
length n.
Actual hash functions don't follow this model exactly. For example, MD5 needs
512+128+64 bits of internal storage* - the first for the input buffer, all of
whose bits are needed together, the second for the running hash state, the
third for the length. So there are 2^704 states in the MD5 FSM, but the
output only has 2^128 values - only 128 bits of the "state number" are used.
That in and of itself isn't an issue - it doesn't hurt, in this particular
analysis, to throw bits away in the *final* result. What does limit it is
that every 512 input bits, the FSM itself logically "mods out" 512 bits of the
state (the input buffer), and ends up in one of "only" 2^192 possible states
(and if we work with "short" strings, then only a small fraction of the 2^64
states of the length field are actually accessible). Because of this, MD5 can
at best have been chosen from on-line functions of minimum length 128, rather
than those of a minimal length up to 704. That's why keeping more internal
state *might* help - though you have to be careful, as we've seen, about how
you do it.
-- Jerry
* Actually, you need 3 more bits because the MD5 length is in octets, not
bits. This memory is hidden in any real implementation on byte-oriented
hardware.
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
On Wed, 25 Aug 2004, Hal Finney wrote: >Bear writes: >> One interesting idea which I came up with and haven't seen a way >> past yet is to XOR each block with a value computed from its >> sequence number, then compute the hash function on the blocks in >> a nonsequential order based on the plaintext of the blocks. >This is an interesting idea, but it does not fully prevent the Joux >attack. >The attacker could choose an ordering of the blocks ahead of time, and >find collisions which preserve that order. > >Joux shows that finding an 2^k collision takes k times the work to >find a single block collision. Among other things he shows how this >reduces the work to find a collision in the output of two independent >n-bit hashes from 2^n to n*2^(n/2). Your approach effectively makes >this (n^3)*2^(n/2) which is an improvement, but still not attaining >the exponential security increase expected from ideal hash functions. You are correct. Thank you for your quick and clear thought regarding the proposal. Increasing the attacker's work by a factor of n^2 where n is the number of blocks preserves the strength only where n^2 >= (2^k)/2 where k is the block size. So, for a 160-bit hash, (2^k)/2 is 2^159, and that means the proposed method preserves nominal strength only for messages longer than 2^80 blocks. Which in practical terms will not happen; I don't think 2^80 bits of storage have yet been manufactured by all the computer hardware makers on earth. I guess I momentarily forgot that with a hash function the attacker has access to the plaintext and can therefore tell unambiguously the result of the permutation of the blocks. I'll continue to think about it. Maybe I'll come up with something better. Bear - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
Bear writes: > One interesting idea which I came up with and haven't seen a way > past yet is to XOR each block with a value computed from its > sequence number, then compute the hash function on the blocks in > a nonsequential order based on the plaintext of the blocks. > > In concrete terms, you have a message of n blocks, p1 through pn. > you xor each block with a value computed by a nonlinear function > from its sequence number to get q1 through qn. Now rearrange > q1 through qn by imposing a total ordering on p1 through pn: for > example if p4 sorted before p7, you put q4 in front of q7. > Finally, you compute the hash value on the blocks q1 through qn > in their new order. This is an interesting idea, but it does not fully prevent the Joux attack. This is seen most obviously in the two block case, where your method can at most increase the attacker's work by a factor of 2. Joux shows how to find a 4-collision using 2*2^(n/2) work, while it should take 2^(3n/4) work. In the case of a 160 bit hash this is the difference between 2^81 and 2^120. Doubling the work to find the 4-collision will not do much to address this discrepency. Even in the more general case, where Joux puts k blocks together to generate 2^k multicollisions, I can see a way to attack your method, with an increase in the work by only a factor of k^2. The attacker could choose an ordering of the blocks ahead of time, and find collisions which preserve that order. Specifically, he can start searching for collisions in the first one, which WOLOG we will call q1. He can continue to search until he finds a collision which puts p1 into the first 1/k of "block address space", which will guarantee that this block will sort first. This will increase his work by a factor of k^2 (because only 1/k of the time will he get lucky, for each of the two blocks in the collision). Then he can find a collision in q2 which puts p2 into the 2nd 1/k of block-address space, guaranteeing that p2 will sort as the second block. Again this increases the work by k^2. Proceeding down the line he produces a collision which leaves the blocks in his pre-chosen order, at a cost of k^2 more work. Joux shows that finding an 2^k collision takes k times the work to find a single block collision. Among other things he shows how this reduces the work to find a collision in the output of two independent n-bit hashes from 2^n to n*2^(n/2). Your approach effectively makes this (n^3)*2^(n/2) which is an improvement, but still not attaining the exponential security increase expected from ideal hash functions. Hal Finney - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
On Wed, 25 Aug 2004, Hal Finney wrote: >Dan Carosone writes: >> My immediate (and not yet further considered) reaction to the >> description of Joux' method was that it might be defeated by something >> as simple as adding a block counter to the input each time. > >Right after the talk, Scott Fluhrer (I think it was) spoke up with >several quick ideas for avoiding the attacks, some along these lines, >some involving overlapping blocks, and so on. There was some rapid >back-and-forth between him and Joux which I could not follow, Joux >saying that these things could be dealt with, and Fluhrer finally seemed >to agree. Nobody I spoke with afterwards had a simple fix. It seems like, for every "obvious" thing you can do to get around it, it can be rearranged and applied in a different way. And the less obvious things, which actually do work, are all CPU-expensive. One interesting idea which I came up with and haven't seen a way past yet is to XOR each block with a value computed from its sequence number, then compute the hash function on the blocks in a nonsequential order based on the plaintext of the blocks. In concrete terms, you have a message of n blocks, p1 through pn. you xor each block with a value computed by a nonlinear function from its sequence number to get q1 through qn. Now rearrange q1 through qn by imposing a total ordering on p1 through pn: for example if p4 sorted before p7, you put q4 in front of q7. Finally, you compute the hash value on the blocks q1 through qn in their new order. Now the attack doesn't work; collisions against individual blocks don't combine to produce a collision on the sequence because the colliding values wouldn't have been fed into the hash function in the same order as the actual blocks. Bear - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
Dan Carosone writes: > My immediate (and not yet further considered) reaction to the > description of Joux' method was that it might be defeated by something > as simple as adding a block counter to the input each time. Right after the talk, Scott Fluhrer (I think it was) spoke up with several quick ideas for avoiding the attacks, some along these lines, some involving overlapping blocks, and so on. There was some rapid back-and-forth between him and Joux which I could not follow, Joux saying that these things could be dealt with, and Fluhrer finally seemed to agree. Nobody I spoke with afterwards had a simple fix. Recall that the attack is to first find a collision in the first block. Then you take the output of that block and use it as the input to the second block, and starting from that value find a collision in the second block. Repeat for k blocks and you have a pair of values for each block that take the input value from the previous block and produce matching outputs. Now you can choose any path among these pairs of values, of which there are 2^k, and get a collision. Presto, you have a 2^k multicollision for the cost of k single-block collisions, which departs from the ideal of a random function. Adding a block counter doesn't help because it will still take only 2^(n/2) at worst to find a collision in the second block, even though the block counter value is "2". It's true that collisions from the first block won't work in the second block, but that won't make it any harder to find second-block collisions. Hal - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
My immediate (and not yet further considered) reaction to the description of Joux' method was that it might be defeated by something as simple as adding a block counter to the input each time. I any case, I see it as a form of dictionary attack, and wonder whether the same kinds of techniques wouldn't help. -- Dan. pgpRyiFiNhXGq.pgp Description: PGP signature
Re: More problems with hash functions
Jerry Leichter writes: > Joux's attack says: Find single block messages M1 and M1' that collide on > the "blank initial state". Now find messages M2 amd M2' that collide with > the (common) final state from M1 and M1'. Then you hav four 2-block > collisions for the cost of two: M1|M2, M1'|M2, and so on. > > But even a simple XOR breaks this. M1 and M1' have the same hash H, but the > state being passed is now very different: in one case, in the > other. So M1|M2 and M1'|M2 are completely different: Both started the second > step with the compression function in state H, but the first compressed > M1 XOR M2, and the second M1' XOR M2. Okay, I misunderstood your earlier suggestion. Sorry. Rereading it: > Suppose we > did ciphertext chaining: For block i, the input to the compression function > is the compressed previous state and the xor of block i and block i-1. Then > I can no longer mix-and-match pairs of collisions to find new ones. It sounds like you're saying that that the input to the second compression function should be M1 XOR M2 instead of just M2. Like this: IV ---> COMP ---> COMP ---> COMP ---> Output ^ ^ ^ |/--> X/--> X | / | / | Block 1 Block 2 Block 3 But this is easily compensated for: if you wanted the input to the 2nd compression stage to be M2, you'd just input M1 XOR M2 instead. Then when this gets XOR'd with M1, M1 will will cancel out in the XOR and you'll have a nice clean M2 going into COMP, just as you wanted. So if you found a compression-function collision starting with IV on M1 and M1', and you found a collision starting with the common output of that stage on M2 and M2', your four collisions would be: M1 || (M1 xor M2) M1 || (M1 xor M2') M1' || (M1' xor M2) M1' || (M1' xor M2') In each case the actual input to the 2nd block compression function (after xoring with the first block input) would be M2 or M2', as desired. Hal Finney - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
| > It strikes me that Joux's attack relies on *two* features of current | > constructions: The block-at-a-time structure, and the fact that the state | > passed from block to block is the same size as the output state. Suppose we | > did ciphertext chaining: For block i, the input to the compression function | > is the compressed previous state and the xor of block i and block i-1. Then | > I can no longer mix-and-match pairs of collisions to find new ones. | | Here's how I understand what you are suggesting. Presently the hash | compression function takes two inputs: a state, and an input data block. | For SHA-1 the state is 160 bits and the input data block is 512 bits. | It outputs a state-size block of 160 bits, which gets fed into the | next block: | | IV ---> COMP ---> COMP ---> COMP ---> Output |^ ^ ^ || | | || | | | Block 1 Block 2 Block 3 | | I think you are proposing to increase the output of each block by 512 | bits in this case, so as to provide some data that can be xored into | the input data block of the next stage, a la CBC: | | IV ---> COMP ---> COMP ---> COMP ---> Output |^ \ ^ \ ^ ||\--> X\--> X || | | | Block 1 Block 2 Block 3 | | By itself, adding an xor step doesn't do anything Not true. Joux's attack says: Find single block messages M1 and M1' that collide on the "blank initial state". Now find messages M2 amd M2' that collide with the (common) final state from M1 and M1'. Then you hav four 2-block collisions for the cost of two: M1|M2, M1'|M2, and so on. But even a simple XOR breaks this. M1 and M1' have the same hash H, but the state being passed is now very different: in one case, in the other. So M1|M2 and M1'|M2 are completely different: Both started the second step with the compression function in state H, but the first compressed M1 XOR M2, and the second M1' XOR M2. All I'm left with, unless there's some cleverer attack I'm missing, is: - Find M1 and M1' that collide; - Find M2 and M2' such that M1 XOR M2 collides with M1' XOR M2', on the common initial state. Then for the cost of finding two block-level collisions, I have a collision between two-block messages (M1|M2 and M1'|M2'). But why bother? It's always been sufficient to find a collision on the *last* block, with an arbitrary initial state. (It would be nice to eliminate *this* generic weakness, but it's not clear you can and still have an on-line algorithm.) -- Jerry - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
Jerry Leichter writes: > It strikes me that Joux's attack relies on *two* features of current > constructions: The block-at-a-time structure, and the fact that the state > passed from block to block is the same size as the output state. Suppose we > did ciphertext chaining: For block i, the input to the compression function > is the compressed previous state and the xor of block i and block i-1. Then > I can no longer mix-and-match pairs of collisions to find new ones. Here's how I understand what you are suggesting. Presently the hash compression function takes two inputs: a state, and an input data block. For SHA-1 the state is 160 bits and the input data block is 512 bits. It outputs a state-size block of 160 bits, which gets fed into the next block: IV ---> COMP ---> COMP ---> COMP ---> Output ^ ^ ^ | | | | | | Block 1 Block 2 Block 3 I think you are proposing to increase the output of each block by 512 bits in this case, so as to provide some data that can be xored into the input data block of the next stage, a la CBC: IV ---> COMP ---> COMP ---> COMP ---> Output ^ \ ^ \ ^ |\--> X\--> X | | | Block 1 Block 2 Block 3 By itself, adding an xor step doesn't do anything. The attacker would still have full control of the output of the xor, since he has full control of one of its two inputs. So I think it is more appropriate to merely think of the compression function block as taking a wider state input from the previous stage, and not specify how the input data block is mixed with the previous state. This might lead to a construction in which the state passed from block to block is, say, 512 bits, rather than 160. The compression function still takes two inputs, the state and the input block, and now produces a 512 bit output. IV ===> COMP ===> COMP ===> COMP ---> Output ^ ^ ^ | | | | | | Block 1 Block 2 Block 3 (Here, the ==> are meant to depict wide paths.) For the final output of the hash, we would presumably "derate" the output of the last stage down to 160 bits and not claim the full 512 bits of security. If we didn't do this step, then the construction is precisely SHA-512 and Joux's attack still applies. This approach does appear to defeat the Joux attack. Finding a collision in a sub-block which takes a 512 bit input to a 512 bit output will take 2^256 work rather than the 2^80 in the SHA-1 compression function. So you will never find a multicollision in less work than this. And the most strength SHA-1 can provide against anything is 2^160 since that it what it takes to invert it. Since 2^256 is greater than 2^160, the construction is strong against this attack. We can also see from this analysis that making the paths 512 bits wide is overkill; they only need to be twice the claimed hash strength, or 320 bits wide in this case. Or in other words, if we took SHA-512 and only claimed it to have 256 bits of strength, it would avoid the Joux attack. However, the problem with this construction is that the inner blocks now genuinely need to have 512 bits of strength, and that may not be that easy to provide. SHA-512's compression function does claim to have that amount of collision resistance, but it is difficult to analyze such strong claims, and adding this much strength may make for a slow hash. Plus, given that we have managed to create a block with 512 bits of security, it seems a shame to throw away half of the strength to produce an output that avoids the Joux attack. I think cryptographers will look harder to try to find a way of combining sub-blocks which will retain the strength of the individual pieces rather than throwing half of it away. Hal Finney - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: More problems with hash functions
It strikes me that Joux's attack relies on *two* features of current constructions: The block-at-a-time structure, and the fact that the state passed from block to block is the same size as the output state. Suppose we did ciphertext chaining: For block i, the input to the compression function is the compressed previous state and the xor of block i and block i-1. Then I can no longer mix-and-match pairs of collisions to find new ones. Am I missing some obvious generalization of Joux's attack? (BTW, this is reminiscent of two very different things: (a) Rivest's work on "all or nothing" package transforms; (b) the old trick in producing MAC's by using CBC and only sending *some* of the final encrypted value, to force an attacker to guess the bits that weren't sent. -- Jerry - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
