10. Security Considerations

Security Considerations

This section contains additional security considerations about the hash-to-curve mechanisms described in this document.

10.1. Properties of Encodings

Each encoding type (Section 3) accepts an arbitrary byte string and maps it to a point on the curve sampled from a distribution that depends on the encoding type. It is important to note that using a nonuniform encoding or directly evaluating one of the mappings of Section 6 produces an output that is easily distinguished from a uniformly random point. Applications that use a nonuniform encoding SHOULD carefully analyze the security implications of nonuniformity. When the required encoding is not clear, applications SHOULD use a uniform encoding.

Both encodings given in Section 3 can output the identity element of the group G. The probability that either encoding function outputs the identity element is roughly 1/r for a random input, which is negligible for cryptographically useful elliptic curves. Further, it is computationally infeasible to find an input to either encoding function whose corresponding output is the identity element. (Both of these properties hold when the encoding functions are instantiated with a hash_to_field function that follows all guidelines in Section 5.) Protocols that use these encoding functions SHOULD NOT add a special case to detect and "fix" the identity element.

When the hash_to_curve function (Section 3) is instantiated with a hash_to_field function that is indifferentiable from a random oracle (Section 5), the resulting function is indifferentiable from a random oracle ([MRH04] [BCIMRT10] [FFSTV13] [LBB19] [H20]). In many cases, such a function can be safely used in cryptographic protocols whose security analysis assumes a random oracle that outputs uniformly random points on an elliptic curve. As Ristenpart et al. discuss in [RSS11], however, not all security proofs that rely on random oracles continue to hold when those oracles are replaced by indifferentiable functionalities. This limitation should be considered when analyzing the security of protocols relying on the hash_to_curve function.

10.2. Hashing Passwords

When hashing passwords using any function described in this document, an adversary who learns the output of the hash function (or potentially any intermediate value, e.g., the output of hash_to_field) may be able to carry out a dictionary attack. To mitigate such attacks, it is recommended to first execute a more costly key derivation function (e.g., PBKDF2 [RFC8018], scrypt [RFC7914], or Argon2 [RFC9106]) on the password, then hash the output of that function to the target elliptic curve. For collision resistance, the hash underlying the key derivation function should be chosen according to the guidelines listed in Section 5.3.1.

10.3. Constant-Time Requirements

Constant-time implementations of all functions in this document are STRONGLY RECOMMENDED for all uses, to avoid leaking information via side channels. It is especially important to use a constant-time implementation when inputs to an encoding are secret values; in such cases, constant-time implementations are REQUIRED for security against timing attacks (e.g., [VR20]). When constant-time implementations are required, all basic operations and utility functions must be implemented in constant time, as discussed in Section 4. In some applications (e.g., embedded systems), leakage through other side channels (e.g., power or electromagnetic side channels) may be pertinent. Defending against such leakage is outside the scope of this document, because the nature of the leakage and the appropriate defense depend on the application.

10.4. encode_to_curve: Output Distribution and Indifferentiability

The encode_to_curve function (Section 3) returns points sampled from a distribution that is statistically far from uniform. This distribution is bounded roughly as follows: first, it includes at least one eighth of the points in G, and second, the probability of points in the distribution varies by at most a factor of four. These bounds hold when encode_to_curve is instantiated with any of the map_to_curve functions in Section 6.

The bounds above are derived from several works in the literature. Specifically:

Shallue and van de Woestijne [SW06] and Fouque and Tibouchi [FT12] derive bounds on the Shallue-van de Woestijne mapping (Section 6.6.1).
Fouque and Tibouchi [FT10] and Tibouchi [T14] derive bounds for the Simplified SWU mapping (Sections 6.6.2 and 6.6.3).
Bernstein et al. [BHKL13] derive bounds for the Elligator 2 mapping (Sections 6.7.1 and 6.8.2).

Indifferentiability of encode_to_curve follows from an argument similar to the one given by Brier et al. [BCIMRT10]; we briefly sketch this argument as follows. Consider an ideal random oracle Hc() that samples from the distribution induced by the map_to_curve function called by encode_to_curve, and assume for simplicity that the target elliptic curve has cofactor 1 (a similar argument applies for non-unity cofactors). Indifferentiability holds just if it is possible to efficiently simulate the "inner" random oracle in encode_to_curve, namely, hash_to_field. The simulator works as follows: on a fresh query msg, the simulator queries Hc(msg) and receives a point P in the image of map_to_curve (if msg is the same as a prior query, the simulator just returns the value it gave in response to that query). The simulator then computes the possible preimages of P under map_to_curve, i.e., elements u of F such that map_to_curve(u) == P (Tibouchi [T14] shows that this can be done efficiently for the Shallue-van de Woestijne and Simplified SWU maps, and Bernstein et al. show the same for Elligator 2). The simulator selects one such preimage at random and returns this value as the simulated output of the "inner" random oracle. By hypothesis, Hc() samples from the distribution induced by map_to_curve on a uniformly random input element of F, so this value is uniformly random and induces the correct point P when passed through map_to_curve.

10.5. hash_to_field Security

The hash_to_field function, defined in Section 5, is indifferentiable from a random oracle [MRH04] when expand_message (Section 5.3) is modeled as a random oracle. Since indifferentiability proofs are composable, this also holds when expand_message is proved indifferentiable from a random oracle relative to an underlying primitive that is modeled as a random oracle. When following the guidelines in Section 5.3, both variants of expand_message defined in that section meet this requirement (see also Section 10.6).

We very briefly sketch the indifferentiability argument for hash_to_field. Notice that each integer mod p that hash_to_field returns (i.e., each element of the vector representation of F) is a member of an equivalence class of roughly 2^k integers of length log2(p) + k bits, all of which are equal modulo p. For each integer mod p that hash_to_field returns, the simulator samples one member of this equivalence class at random and outputs the byte string returned by I2OSP. (Notice that this is essentially the inverse of the hash_to_field procedure.)

10.6. expand_message_xmd Security

The expand_message_xmd function, defined in Section 5.3.1, is indifferentiable from a random oracle [MRH04] when one of the following holds:

H is indifferentiable from a random oracle,
H is a sponge-based hash function whose inner function is modeled as a random transformation or random permutation [BDPV08], or
H is a Merkle-Damgaard hash function whose compression function is modeled as a random oracle [CDMP05].

For cases (1) and (2), the indifferentiability of expand_message_xmd follows directly from the indifferentiability of H.

For case (3), i.e., where H is a Merkle-Damgaard hash function, indifferentiability follows from [CDMP05], Theorem 5. In particular, expand_message_xmd computes b_0 by prefixing the message with one block of zeros plus auxiliary information (length, counter, and DST). Then, each of the output blocks b_i, i >= 1 in expand_message_xmd is the result of invoking H on a unique, prefix-free encoding of b_0. This is true, first because the length of the input to all such invocations is equal and fixed by the choice of H and DST, and second because each such input has a unique suffix (because of the inclusion of the counter byte I2OSP(i, 1)).

The essential difference between the construction discussed in [CDMP05] and expand_message_xmd is that the latter hashes a counter appended to strxor(b_0, b_(i - 1)) ({#hashtofield-expand-xmd}, step 10) rather than to b_0. This approach increases the Hamming distance between inputs to different invocations of H, which reduces the likelihood that nonidealities in H affect the distribution of the b_i values.

We note that expand_message_xmd can be used to instantiate a general- purpose indifferentiable functionality with variable-length output based on any hash function meeting one of the above criteria. Applications that use expand_message_xmd outside of hash_to_field should ensure domain separation by picking a distinct value for DST.

10.7. Domain Separation for expand_message Variants

As discussed in Section 2.2.5, the purpose of domain separation is to ensure that security analyses of cryptographic protocols that query multiple independent random oracles remain valid even if all of these random oracles are instantiated based on one underlying function H.

The expand_message variants in this document (Section 5.3) ensure domain separation by appending a suffix-free-encoded domain separation tag DST_prime to all strings hashed by H, an underlying hash or extendable-output function. (Other expand_message variants that follow the guidelines in Section 5.3.4 are expected to behave similarly, but these should be analyzed on a case-by-case basis.) For security, applications that use the same function H outside of expand_message should enforce domain separation between those uses of H and expand_message, and they should separate all of these from uses of H in other applications.

This section suggests four methods for enforcing domain separation from expand_message variants, explains how each method achieves domain separation, and lists the situations in which each is appropriate. These methods share a high-level structure: the application designer fixes a tag DST_ext distinct from DST_prime and augments calls to H with DST_ext. Each method augments calls to H differently, and each may impose additional requirements on DST_ext.

These methods can be used to instantiate multiple domain-separated functions (e.g., H1 and H2) by selecting distinct DST_ext values for each (e.g., DST_ext1, DST_ext2).

(Suffix-only domain separation.) This method is useful when domain-separating invocations of H from expand_message_xmd or expand_message_xof. It is not appropriate for domain-separating expand_message from HMAC-H [RFC2104]; for that purpose, see method 4.

To instantiate a suffix-only domain-separated function Hso, compute

  Hso(msg) = H(msg || DST_ext)

   DST_ext should be suffix-free encoded (e.g., by appending one
   byte encoding the length of DST_ext) to make it infeasible to
   find distinct (msg, DST_ext) pairs that hash to the same value.

   This method ensures domain separation because all distinct
   invocations of H have distinct suffixes, since DST_ext is
   distinct from DST_prime.

2. (Prefix-suffix domain separation.) This method can be used in the same cases as the suffix-only method.

   To instantiate a prefix-suffix domain-separated function Hps,
   compute

  Hps(msg) = H(DST_ext || msg || I2OSP(0, 1))

   DST_ext should be prefix-free encoded (e.g., by adding a one-byte
   prefix that encodes the length of DST_ext) to make it infeasible
   to find distinct (msg, DST_ext) pairs that hash to the same
   value.

   This method ensures domain separation because appending the byte
   I2OSP(0, 1) ensures that inputs to H inside Hps are distinct from
   those inside expand_message.  Specifically, the final byte of
   DST_prime encodes the length of DST, which is required to be
   nonzero (Section 3.1, requirement 2), and DST_prime is always
   appended to invocations of H inside expand_message.

3. (Prefix-only domain separation.) This method is only useful for domain-separating invocations of H from expand_message_xmd. It does not give domain separation for expand_message_xof or HMAC-H.

   To instantiate a prefix-only domain-separated function Hpo,
   compute

  Hpo(msg) = H(DST_ext || msg)

   In order for this method to give domain separation, DST_ext
   should be at least b bits long, where b is the number of bits
   output by the hash function H.  In addition, at least one of the
   first b bits must be nonzero.  Finally, DST_ext should be prefix-
   free encoded (e.g., by adding a one-byte prefix that encodes the
   length of DST_ext) to make it infeasible to find distinct (msg,
   DST_ext) pairs that hash to the same value.

   This method ensures domain separation as follows.  First, since
   DST_ext contains at least one nonzero bit among its first b bits,
   it is guaranteed to be distinct from the value Z_pad
   (Section 5.3.1, step 4), which ensures that all inputs to H are
   distinct from the input used to generate b_0 in
   expand_message_xmd.  Second, since DST_ext is at least b bits
   long, it is almost certainly distinct from the values b_0 and
   strxor(b_0, b_(i - 1)), and therefore all inputs to H are
   distinct from the inputs used to generate b_i, i >= 1, with high
   probability.

4. (XMD-HMAC domain separation.) This method is useful for domain- separating invocations of H inside HMAC-H (i.e., HMAC [RFC2104] instantiated with hash function H) from expand_message_xmd. It also applies to HKDF-H (i.e., HKDF [RFC5869] instantiated with hash function H), as discussed below.

   Specifically, this method applies when HMAC-H is used with a non-
   secret key to instantiate a random oracle based on a hash
   function H (note that expand_message_xmd can also be used for
   this purpose; see Section 10.6).  When using HMAC-H with a high-
   entropy secret key, domain separation is not necessary; see
   discussion below.

   To choose a non-secret HMAC key DST_key that ensures domain
   separation from expand_message_xmd, compute

  DST_key_preimage = "DERIVE-HMAC-KEY-" || DST_ext || I2OSP(0, 1)
  DST_key = H(DST_key_preimage)

   Then, to instantiate the random oracle Hro using HMAC-H, compute

  Hro(msg) = HMAC-H(DST_key, msg)

   The trailing zero byte in DST_key_preimage ensures that this
   value is distinct from inputs to H inside expand_message_xmd
   (because all such inputs have suffix DST_prime, which cannot end
   with a zero byte as discussed above).  This ensures domain
   separation because, with overwhelming probability, all inputs to
   H inside of HMAC-H using key DST_key have prefixes that are
   distinct from the values Z_pad, b_0, and strxor(b_0, b_(i - 1))
   inside of expand_message_xmd.

   For uses of HMAC-H that instantiate a private random oracle by
   fixing a high-entropy secret key, domain separation from
   expand_message_xmd is not necessary.  This is because, similarly
   to the case above, all inputs to H inside HMAC-H using this
   secret key almost certainly have distinct prefixes from all
   inputs to H inside expand_message_xmd.

   Finally, this method can be used with HKDF-H [RFC5869] by fixing
   the salt input to HKDF-Extract to DST_key, computed as above.
   This ensures domain separation for HKDF-Extract by the same
   argument as for HMAC-H using DST_key.  Moreover, assuming that
   the input keying material (IKM) supplied to HKDF-Extract has
   sufficiently high entropy (say, commensurate with the security
   parameter), the HKDF-Expand step is domain-separated by the same
   argument as for HMAC-H with a high-entropy secret key (since a
   pseudorandom key is exactly that).

10.8. Target Security Levels

Each ciphersuite specifies a target security level (in bits) for the underlying curve. This parameter ensures the corresponding hash_to_field instantiation is conservative and correct. We stress that this parameter is only an upper bound on the security level of the curve and is neither a guarantee nor endorsement of its suitability for a given application. Mathematical and cryptographic advancements may reduce the effective security level for any curve.