[HN Gopher] EdDSA, Ed25519, Ed25519-IETF, Ed25519ph, Ed25519ctx,...
___________________________________________________________________
EdDSA, Ed25519, Ed25519-IETF, Ed25519ph, Ed25519ctx, HashEdDSA,
PureEdDSA, WTF?
Author : baby
Score : 80 points
Date : 2020-03-13 18:33 UTC (4 hours ago)
(HTM) web link (www.cryptologie.net)
(TXT) w3m dump (www.cryptologie.net)
| wahern wrote:
| Prehashing 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.
| dchest wrote:
| Please stop saying "you have much bigger problems", this cliche
| is dangerous and unproductive.
| beart wrote:
| I 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 wrote:
| I 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.
| dependenttypes wrote:
| > 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
| nullc wrote:
| > 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.
| kwantam wrote:
| A 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
|
| [2] https://cs.nyu.edu/~dodis/ps/merkle.pdf
| baby wrote:
| Interesting! 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-0...
| oconnor663 wrote:
| > In contrast, for a well-designed hash function there should
| not be any way to save work when computing...
|
| This property, that making a small change at the front of the
| message requires repeating almost all of the work to re-hash
| the whole message, doesn't apply to K12 or BLAKE3. Their tree
| structures make it possible to reuse most of the work you did
| the first time. (This is essentially the same thing as being
| able to hash different parts of the message in parallel,
| which is the design goal of both algorithms.)
|
| With BLAKE3, if you wanted to force someone to repeat all the
| work, the cleanest way to do it would be to change the key.
| baby wrote:
| > doesn't apply to K12 or BLAKE3. Their tree structures
| make it possible to reuse most of the work you did the
| first time
|
| not so much in practice, due to the tree structure not
| being triggered before you hash a chunk (8192 bytes for
| K12).
___________________________________________________________________
(page generated 2020-03-13 23:00 UTC)