0
$\begingroup$

Can someone please explain the below paragraph from section 2.5 in The XEdDSA and VXEdDSA Signature Schemes? Specifically I want to understand how we are defining the family of hash functions and how is it used further?

XEdDSA and VXEdDSA require a cryptographic hash function. The default hash function is SHA-512.

We define $hash$ as a function that applies the cryptographic hash to an input byte sequence, and returns an integer which is the output from the cryptographic hash parsed in little-endian form. Given $hash$ and the curve constants $p$ and $b$, we define a family of hash functions indexed by nonnegative integers $i$ such that $2^{|p|} - 1 - i > p$.

${hash}_i(X):\\ \;\;\text{ return }{hash}(2^b - 1 - i \;||\; X)$

So $hash_0$ hashes $b/8$ bytes of $0xFF$ prior to the input byte sequence $X$, $hash_1$ changes the first byte to $0xFE$, $hash_2$ changes the first byte to $0xFD$, and so on.

Different $hash_i$ will be used for different purposes, to provide cryptographic domain separation. Note that $hash_i$ will never call $hash$ with the first $b$ bits encoding a valid scalar or elliptic curve point, since the first $|p|$ bits encode an integer greater than $p$. Note also that $hash_0$ is reserved for use by other specifications, and is not used in this document.

$\endgroup$
  • 2
    $\begingroup$ This is Section 2.5 of the XEdDSA and VXEdDSA signature schemes. In the future, please try to cite the source of these paragraphs to make it easy for others to search if they have similar problems. $\endgroup$ – user47922 May 23 '17 at 4:50
  • 1
    $\begingroup$ Could you elaborate on exactly what you don't understand about the paragraph? $\endgroup$ – user47922 May 23 '17 at 5:24
  • 1
    $\begingroup$ @galvatron I will keep in mind for future. Specifically I want to understand how we are defining the family of hash functions and how is it used further $\endgroup$ – tarun14110 May 23 '17 at 13:51
1
$\begingroup$

The hash functions are indexed to achieve domain separation. See, for example, Section 2.2.

The big idea is that if you have a secure underlying function (namely, the $hash$ function), for little cost, you can create a family of secure functions (the $hash_i$) with different outputs for a particular input $X$.

As an example of use of these indexed functions, if my input is DEAFBEAD,

  • hash_0(0xDEAFBEAD) == sha512(0xFF || 0xDEAFBEAD) == 9758ed9f853fabb2e963dc81ba617ea7dadbd802a82acdced8dc7813e908d1dfdd571b02f690487b1e1b5c7ac1938501cb0ccd00fac086a803758b5d92d811c9
  • hash_1(0xDEAFBEAD) == sha512(0xFE || 0xDEAFBEAD) == e8897c024462b42136308fbc975cebec5dcc83ae748047dd6cfa8d5a0806cb40fc1967932d605b6bb577cc1679e37fb94cba0af47ce32f5d6b56153e09f34a24
  • etc.

So throughout the document, you see $hash_1$ getting used in xeddsa_sign, $hash_2$ getting used in hash_to_point, and so on.

Each of the $hash_i$ now "does its own thing". For example, $hash_5$ may get used for signing only and $hash_6$ may get used for verification only.

The $hash_i$ are all equivalent to $hash$ in terms of security, so to my knowledge it doesn't matter which of the $hash_i$ you use for which purpose (except for $hash_0$, which is not to be used here). But this way, you get several independent secure functions derived from a single secure function.

$\endgroup$
  • $\begingroup$ thanks for the explanation. I almost understand. The only part confusing me is "hash0 hashes b/8 bytes of 0xFF prior to the input byte sequence X, hash1 changes the first byte to 0xFE, hash2 changes the first byte to 0xFD, and so on". Are we hashing byte wise? $\endgroup$ – tarun14110 May 23 '17 at 19:21
  • $\begingroup$ As an example, let $b=8$. Then $hash_0$ will prepend $2^8 - 1 - 0 = 255 = 0xFF$ to the beginning of the input, making it the new first byte. $hash_1$ will prepend $254 = 0xFE$ as the first byte, $hash_2$ will prepend $253 = 0xFD$ as the first byte, etc. Only after prepending do you hash. $\endgroup$ – user47922 May 23 '17 at 19:46

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.