1
$\begingroup$

Can someone please explain the below paragraph from section 7 in The XEdDSA and VXEdDSA Signature Schemes?

The below para states that we are hashing twice (I am not able to get that). How pre-hashing will help in this case.

Pre-hashing: Except for XEdDSA verification, the signing and verification algorithms hash the input message twice. For large messages this could be expensive, and would require either large buffers or more complicated APIs.

To prevent this, APIs may wish to specify a maximum message size that all implementations must be capable of buffering. Protocol designers can specify "pre-hashing" of message fields to fit within this. Designers are encouraged to use pre-hashing selectively, so as to limit the potential impact from collision attacks (e.g. pre-hashing the attachments to a message but not the message header or body).

$\endgroup$
3
$\begingroup$

Note the following three lines in XEdDSA: $\newcommand{\opn}{\operatorname}$

  1. $r=\opn{hash}(a\parallel M\parallel Z)\bmod q$
  2. $R=rB$
  3. $h=\opn{hash}(R\parallel A\parallel M)\bmod q$

As you can see, the hash input of the third instruction depends on the hash output of the first instruction. And even worse you can't "just append" said output, it ahs to come first.

Now assume that you have a large message (like one gigabyte in size). While you could stream-process the first hash easily, you would have to buffer the full message so that you can feed it into the second hash invocation, requiring you to either a) have a stupid large statically-allocated buffer or b) significantly limit message size or c) use dynamic allocation (which is really slow).

So how can we fix this? Pre-Hashing. Assume that the "$M$" for the signing algorithm isn't actually the 1GB M, but rather the fixed-size $\opn{hash}(M)$. Now we can use a small, constant-sized buffer to store the "$M$" and we can just stream-compute $\opn{hash}(M)$, meaning we don't need unnecessarily large buffers there either. However the obvious downside of doing pre-hashing is that a collision on the hash easily translates into a forgery attack on the signature scheme (as $\opn{hash}(M)$ and $\opn{hash}(M')$ have the same hash, they are essentially the same message for the signature algorithm even though $M\neq M'$).


I said "stream-process" here multiple times, so I'll give you a quick understanding what it means. In actual implementations of hash functions you usually find the following three functions:

hash_init(context*)
hash_update(context*,byte* data)
hash_final(context*,byte* digest)

So you normally initialize some context for the hash, then you update the context with data a few times and finally extract the hash value (the digest) out of the context. Most hash functions are designed to support this style of implementation and allow context to be a compile-time-sized structure so that if you get a stream of data, you can continually call hash_update and then discard the message part's buffer (if you have no further use for it, that is). So in this case, you end up with a small context structure, a small message-part buffer as opposed to one giant full-message-buffer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.