3 ms·

> Otherwise, if msg is short and it gets broken across a block boundary, this can make meet-in-the-middle--style attacks easier. Can you elaborate? Take SHA-51

by pbsd 7y ago

> Otherwise, if msg is short and it gets broken across a block boundary, this can make meet-in-the-middle--style attacks easier. Can you elaborate? Take SHA-512/256 with some awkward prefix size, let's say 127 bytes. Which attacks, presumably not side-channel based, become possible? In any case, I am not convinced in the least by this suffix pitch. Handwaving that "prefix-freeness" needs to be checked, when that's something that is constantly gotten wrong and results in real breaks is a bit naïve. On the other hand, I have real trouble thinking of a real break caused by prefixing. The Ed25519 paper you link to does not point to prefixing as the culprit either; that just happened to be where the key was, and the lack of randomness makes power analysis possible. Without randomness, suffixing would suffer a similar fate.

kwantam 7y ago
SHA-512/256 is already quite misuse-resistant, so it's entirely plausible that there's nothing to worry about in this specific case. But if we limit ourselves to standard Merkle Damgaard hashes (i.e., not ChopMD), then the specific concern is that putting a small amount (say, a few bytes) of msg at the end of one block lets us, in effect, look for collisions between two M-D hash functions where one has an attacker-chosen IV. Here, the key property is that the IV space is large enough to be useful but small enough to be feasibly searchable. For SHA-2, this does not currently appear to be a problem, but the conservative move is to rule this out by construction. HMAC does this, for example (and as I'm certain you know, HMAC-SHA-1 remains plausibly secure in spite of all of the attacks on SHA-1). Regarding prefix-freeness: I completely agree with you that this is easy to get wrong, and I didn't intend to hand-wave about this in the least. Note, however, that the requirement for prefix-freeness obtains for both prepend and append! So this isn't actually an argument against appending. Regarding the power analysis: apologies, I should have been clearer on this point. One interpretation of the Ed25519 paper I linked is that the issue has to do with putting the secret in the same block as attacker-controlled bytes, because this gives the attacker a lot more power to extract information about the secret via power analysis. Even without randomness, this attack would be much harder to pull off (perhaps even impossible) if the secret were padded to a full block length. My point was just: don't put secrets and attacker-controlled data in the same block. And suffixing always lets us do this by applying a padding routine that is independent of the info string to msg.
- deleted 7y ago
  [deleted]

by pbsd 7y ago

kwantam 7y ago

SHA-512/256 is already quite misuse-resistant, so it's entirely plausible that there's nothing to worry about in this specific case. But if we limit ourselves to standard Merkle Damgaard hashes (i.e., not ChopMD), then the specific concern is that putting a small amount (say, a few bytes) of msg at the end of one block lets us, in effect, look for collisions between two M-D hash functions where one has an attacker-chosen IV. Here, the key property is that the IV space is large enough to be useful but small enough to be feasibly searchable. For SHA-2, this does not currently appear to be a problem, but the conservative move is to rule this out by construction. HMAC does this, for example (and as I'm certain you know, HMAC-SHA-1 remains plausibly secure in spite of all of the attacks on SHA-1). Regarding prefix-freeness: I completely agree with you that this is easy to get wrong, and I didn't intend to hand-wave about this in the least. Note, however, that the requirement for prefix-freeness obtains for both prepend and append! So this isn't actually an argument against appending. Regarding the power analysis: apologies, I should have been clearer on this point. One interpretation of the Ed25519 paper I linked is that the issue has to do with putting the secret in the same block as attacker-controlled bytes, because this gives the attacker a lot more power to extract information about the secret via power analysis. Even without randomness, this attack would be much harder to pull off (perhaps even impossible) if the secret were padded to a full block length. My point was just: don't put secrets and attacker-controlled data in the same block. And suffixing always lets us do this by applying a padding routine that is independent of the info string to msg.

deleted 7y ago
[deleted]