4 ms·
EdDSA, Ed25519, Ed25519-IETF, Ed25519ph, Ed25519ctx, HashEdDSA, PureEdDSA, WTF?
- wahern 7y agoPrehashing doesn't just solve the storage issue. Imagine you want to sign a 1MB or even 1GB file with a typical hardware token. Without prehashing you'd have to send that entire 1MB or 1GB to the token, which has a throughput on the order of KB/s or maybe MB/s, and process all that data with a CPU clocked at MHz, not GHz. Breaking up the file into chunks doesn't help, and might even make things slower, not to mention the added complexity introduced to your file signature format. The obvious solution is to hash the data and sign the hash, just as is done for every other signature scheme. The downside is that now your signature scheme is only as strong as the hash. But if it turns out that SHA-512 isn't collision resistant, you have much bigger problems. PureEdDSA has its elegance, and, sure, use it if you can. But supporting off-chip private keys (e.g. hardware tokens) is sometimes far more important to security. If you're creating an API, keep that in mind.
- dependenttypes 7y ago> But if it turns out that SHA-512 isn't collision resistant, you have much bigger problems. Does it though? Most protocols are moving towards preimage resistance nowadays. That being said, ed25519ph is easier to protect against fault attacks, see https://github.com/jedisct1/libsodium/issues/170 https://github.com/jedisct1/libsodium/issues/170
- nullc 7y ago> if it turns out that SHA-512 isn't collision resistant, you have much bigger problems Ehhh.. collision resistance is a much harder property than second-preimage resistance, and many protocols don't have strong dependencies on collision resistance. Narrow-ish pipe MD style hash functions are particularly brittle against collisions, since finding one collision immediately gives you an infinite family of collisions. You could preserve most of the protection against collision resistance with the two layer hashing by having a signer specified nonce at the interior hash. The token couldn't validate that the nonce matched the one it specified, but an attack would require the host be compromised as well. If the nonce was a hash of the EdDSA R value and checked by verifiers too then the fact that the token can't check wouldn't be a problem. Alternatively, if the inner hash were a tree-structured hash, the token could validate the inner-hash nonce directly. (though depending on the tree, doing it that way might weaken the collision protection). Regardless, it's not strictly necessary to lose that protection just to enable blind-signing-tokens.
- dchest 7y agoPlease stop saying "you have much bigger problems", this cliché is dangerous and unproductive.
- beart 7y agoI don't see why that's dangerous. it's just a rephrasing of "this assumes x holds true" and if it doesn't none of this matters.
- krick 7y agoI don't know what's the parent's problem, but "this assumes x holds true" is actually much more clear and straight-forward, which really helps to stay on track with the discussion. At the very least it allows the opponent to ask if there's something available w/o this assumption, which "you have bigger problems" barely does.
- kwantam 7y agoA slightly unfortunate trend in protocol design has been to prepend rather than append "info" fields to hash inputs. In other words, we tend to see H(info || msg) instead of H(msg || info) There are some good reasons to prefer append to prepend. One practical reason is that---related to what's discussed in the article---if we have to compute two values H(msg || info_1) H(msg || info_2) we can do this with just one pass over msg (though admittedly in a non-blackbox way, namely, by saving an intermediate state of the hash computation). In contrast, for a well-designed hash function there should not be any way to save work when computing H(info_1 || msg) H(info_2 || msg) and this lack of work savings is one of the reasons we tend to get prehash modes. In addition, prepending to msg comes with a range of subtle security issues. As an example, for Merkle-Damgaard hashes like SHA-2 a proper prefix design needs to pad the prefix to a multiple of H's block length. This is to ensure that msg starts on a block boundary, which means that the hash digests as much of msg as possible in a single invocation of the compression function. Otherwise, if msg is short and it gets broken across a block boundary, this can make meet-in-the-middle--style attacks easier. In contrast, appending the info string guarantees that msg starts at a block boundary, which is a small nicety. Moreover, one can easily guarantee in a black-box way (and independent of the value/encoding/&c of the info string) that msg ends at a block boundary (just by padding msg). This can be useful as a defense against some kinds of power analysis in the case that msg is a secret [1]. To be sure: appending also requires care---and care is always required when a Merkle-Damgaard hash! (Sponges like SHA-3 are more resistant to misuse.) At the very least, whatever is appended to msg should be prefix-free, and you will likely want to stop length extension attacks and related issues (see [2] for further discussion of this). But in general my take is that the set of footguns for append is a subset of the prepend ones, and I hope that more folks go towards appending in the future. [1] https://eprint.iacr.org/2017/985 https://eprint.iacr.org/2017/985 [2] https://cs.nyu.edu/~dodis/ps/merkle.pdf https://cs.nyu.edu/~dodis/ps/merkle.pdf
- baby 7y agoInteresting! I was wondering why KangarooTwelve[1] did something different and appends the customization string instead of prepending it. I thought it was a bit annoying because it doesn't allow you to pre-compute the customization string, but I hadn't think of your usecase. [1]: https://tools.ietf.org/html/draft-irtf-cfrg-kangarootwelve-02 https://tools.ietf.org/html/draft-irtf-cfrg-kangarootwelve-0...
- dathinab 7y agoDon't confuse EdDSA with ECDSA, I was stumped for a moment until I realized my mistake ;=)
- jchook 7y agoTo be sure, none of these are quantum-ready.
- spopejoy 7y agoYes but ED-448 is Spinal-Tap Grade