Hashing to the secp256k1 Elliptic Curve

October 25, 2022

Originally posted on geometry.xyz.

Introduction

Many cryptographic protocols, such as aggregatable distributed key generation and BLS signature schemes, require hash-to-curve algorithms, which deterministically convert an arbitrary bytestring into a point on an elliptic curve. Such algorithms are not trivial because they must not only produce valid curve points, but also do so securely and efficiently.

In this post, I will summarise the state of the art of hash-to-curve functions with an emphasis on their application to the secp256k1 elliptic curve, as well as some of the security considerations and performance optimisations behind hash-to-curve algorithms in general.

Background

At Geometry, we worked with Aayush and Lakshman of 0xPARC and Personae Labs on a signature scheme that produces unique deterministic nullifiers. The scheme is meant to be compatible with existing Ethereum wallets as it works with keypairs on the secp256k1 curve. To produce a signature, the signer must derive an elliptic curve point that is the output of a hash-to-curve function over a message and their public key.

To maximise the chances that this signature scheme sees widespread adoption and standardisation, we opted for a hash-to-curve ciphersuite that is itself part of a set of functions undergoing a process of standardisation: secp256k1_XMD:SHA-256_SSWU_RO_. It is defined in Hashing to Elliptic Curves, a draft standard submitted to the Internet Research Task Force (IRTF). One should note that at the time of writing, this document is relatively new and has not yet been formally made an IETF standard.

In a future post, I will elaborate on a circom implementation of this hash-to-curve function which allows it to be used in zk-SNARK circuits.

About Hashing to Elliptic Curves

Hashing to Elliptic Curves (henceforth referrred to as the draft standard) provides specific algorithms for hashing arbitrary bytestrings to elliptic curves. It defines specific ciphersuites - a collection of constants and algorithms - for various elliptic curves, such as secp256k1, P-256, and BLS12-381. While it only provides ciphersuites for this limited set of elliptic curves, it also provides general guidance for how to construct secure ciphersuites for other curves if a reader so desires.

The hash_to_curve algorithm

For the secp256k1_XMD:SHA-256_SSWU_RO_ ciphersuite, the draft specification defines the hash_to_curve function as such:

• Given an input message msg of arbitrary length, use hash_to_field to deterministically produce two field elements u[0] and u[1].
• Compute Q0 = map_to_curve(u[0]).
• Compute Q1 = map_to_curve(u[1]).
• Compute R = Q0 + Q1 using point addition.
• Clear the cofactor of R and return the result.

hash_to_field

hash_to_field performs expand_message_xmd, which hashes msg and outputs a 96-byte array. The output u[0] is the first 48 bytes, and u[1] is the last 48 bytes. I will elaborate on expand_message_xmd in a separate section; for now, simply assume that it emits a uniformly random hash of the input.

map_to_curve

map_to_curve uses a constant-time method that always finds a point on an elliptic curve given a field element. It comes in various flavours, depending on the type of the curve and its parameters.

The draft specification prescribes the Elligator 2 method for Montgomery curves, and the twisted Edwards Elligator 2 method for twisted Edwards curves. For Weierstrass curves like secp256k1, there are three options:

• The Shallue-van de Woestijne (SW) method, which works with any elliptic curve, but is the slowest option.
• The Simplified Shallue-van de Woestijne-Ulas (SSWU) method, which applies to curves defined as $y^2 = x^3 + Ax + B$ where $A \neq 0$ and $B \neq 0$.
• The Simplified SWU method for curves where $AB$ equals 0. This is the most efficient of these three methods.

For our purposes, the Simplified SWU method where $AB$ equals 0 is relevant because the secp256k1 curve is defined with $A = 0$ and $B = 7$, so $AB = 0$.

clear_cofactor

This function converts a point on a curve into a point in the prime order subgroup. To do so is simply to multiply the point with a constant $h$. In the case of the secp256k1 curve, nothing has to be done as $h$ for this curve equals 1.

Security considerations

Any hash-to-curve function or implementation should exhibit certain security properties to preserve the security of the cryptographic protocol in which it is adopted. Otherwise, a weak hash-to-curve function can expose the protocol to attacks. As the draft standard points out, a hash-to-curve function must not only be be collision-resistant, but should also not reveal the discrete logarithm of the output point.

To reason about the security of a cryptographic protocol, cryptographers write proofs based on assumptions about its components. These theoretical assumptions can be described as models. The authors of the draft standard argue that their methods are secure in what is known as the random oracle model (ROM). As such, protocols which rely on such hash-to-curve functions can, if designed correctly, also be proven to be secure in the ROM.

The Random Oracle Model

The authors of the draft standard argue that their hash-to-curve algorithms are secure in the ROM. These functions achieve this in two ways: by ensuring that the algorithms convert input messages via hash functions into field elements that are uniformly random, and by ensuring that the output curve point of the hash-to-curve algorithm is statistically uniform.

First of all, the hash-to-field procedure relies on a method that expands a bytestring into a uniformly random bytestring. There are two variants of this method: expand_message_xof and expand_message_xmd.

expand_message_xof relies on a hash function which natively provides an output of a desired length. Since this hash function (which the recommend to be in the SHAKE XOF family) is provably secure under the ROM, it is easy to show the hash-to-field function is also secure under the ROM.

expand_message_xmd, however, relies on a hash function with a fixed-length output. While some hash functions are indifferentiable from a random oracle, or are sponge-based hash functions whose inner function is provably a random permutation or random transformation, and therefore allow one to argue that expand_message_xmd is indifferentiable from a random oracle, there are some hash functions for which this is not the case: Merkle–Damgård hash functions.

The draft standard cites Coron et al in CDMP05 who argue that the strengthened Merkle–Damgård transformation, employed in hash functions like SHA, does not meet the following security property:

the arbitrary length hash function H must behave as a random oracle when the fixed-length building block is viewed as a random oracle or an ideal block-cipher.

To allow expand_message_xmd to be provably secure in the ROM and employ Merkle–Damgård hash functions like SHA256, the authors use a construction in CDMP05 named $\text{HMAC}^f$ (p12). A rough description of this construction (which skips a suffix-padding step for simplicity) is as follows:

• Let $k$ be the number of input bytes that a Merkle–Damgård hash function $\text{MD}^f$ requires and let $m$ be the message.
• Let $m_0$ be a byte array of $k$ zeros.
• Let $y’ = \text{MD}^f([m_0 \vert\vert m])$ where $\vert\vert$ denotes concatentation.
• Return $\text{MD}^f([y’])$.

Recall that length-extension attacks work when given a hash value $h(m_a)$, an attacker is able to trivially instantiate the internal state of the underlying hash function with $h([m_a])$ in order to derive $h([m_a \vert\vert m_b])$, even if the attacker does not know the value of $m_a$. This violates a crucial property of the random oracle model – that is, it should not be the case that the hash of one message can be in any way influenced by or determined by another.

The $\text{HMAC}^f$ construction does not suffer from this issue. An attacker who wishes to derive $\text{HMAC}^f([m \vert\vert x])$ only knowing $y’$ will be unlikely to succeed. Consider what an attacker may attempt:

• Obtain $a = \text{HMAC}^f([m])$.
  • Note that $a$ is equivalent to $\text{MD}^f(\text{MD}^f([m_0 \vert\vert m]))$.
• Knowing only $\text{MD}^f$ and $y$, the attacker wants to derive $b = \text{HMAC}^f([m \vert\vert x])$ .
  • Note that $b$ is equivalent to $\text{MD}^f(\text{MD}^f([m_0 \vert\vert m \vert\vert x]))$.
• The attacker needs $\text{MD}^f([m_0 \vert\vert m])$ to equal $m_0$ so that she can initialise the internal state of $\text{MD}^f$ with $m_0$ and then proceed with the rest of $\text{MD}^f$ on $x$ to obtain $\text{MD}^f([m_0 \vert\vert m \vert\vert x])$.
• It is, however, highly unlikely that $\text{MD}^f([m_0 \vert\vert m])$ equals $m_0$.

Therefore, $\text{HMAC}^f([m])$ does not suffer from the length extension attack, and is therefore more easily proven to be secure under the ROM.

As such, expand_message_xmd implements this construction, commonly known as a hash-based message authentication code (HMAC). For reference, note that its implementation follows the following pattern. For hash-to-curve ciphersuites that use SHA256 and require a 96-byte output, expand_message_xmd is roughly defined as such:

• Let Z_pad be a byte array of 64 zeros (since $k = 64$ for SHA256). This is analogous to $m_0$ as described above.
• Construct msg_prime as the concatentation of Z_pad, the message, and some constants, such as DST_prime.
• Compute b_0 = SHA256(msg_prime). This is analogous to $y’$ as described above.
• Compute b_1 = SHA256(b_0 || 1 || DST_prime).
• Compute b_2 = SHA256(strxor(b_0, b1) || 2 || DST_prime).
• Compute b_3 = SHA256(strxor(b_0, b2) || 3 || DST_prime).
• Return b_1 || b2 || b3.

As explained above, prepending Z_pad in step 2 allows prevents length extension attacks which could allow an attacker to more easily influence the values b_1, b_2, and b_3.

Domain separation

One may notice the DST_prime constant in the expand_message_xmd algorithm above. It encodes a bytestring that represents a domain separation tag (DST), followed by the DST length as a single byte. Each ciphersuite has a unique DST, such as QUUX-V01-CS02-with-secp256k1_XMD:SHA-256_SSWU_RO_ for the secp256k1_XMD:SHA-256_SSWU_RO_ suite.

The reason for including a unique DST_prime in expand_message_xmd is to ensure that its output is specific to one and only one ciphersuite. In effect, each ciphersuite can be understood to operate with an independent random oracle, which an important security assumption for protocols proven secure under the random oracle model.

Output uniformity

In the draft standard, each elliptic curve comes with two ciphersuite: one that performs hash-to-curve, and another which performs encode-to-curve. The difference between the two is that the output of the former function is more statistically uniform than that of the latter, but the latter is more efficient. The authors state that a safe default is to use hash-to-curve, unless one is sure that nonuniformity is acceptable in one’s cryptographic protocol.

The reason that hash-to-curve differs lies in its implementation. The hash_to_curve function derives two different elliptic curve points from the input message (using the map_to_curve function) and adds them together. In contrast, the encode_to_curve function only calls map_to_curve once. As the output of map_to_curve is nonuniform, it follows that the output of encode_to_curve is nonuniform. Since hash_to_curve adds two nonuniform points, however, the output is uniform. The authors cite Brier et al which proves that this is the case.

Constant-time implementation

An important security property of the hash-to-curve ciphersuites in the draft standard is that they can be computed in constant time. This property is critical if the message to be hashed must be secret.

To have secure constant-time hash-to-curve functions is a step forward because much prior work on hash-to-curve algorithms use a try-and-increment approach, where an input message is converted into a field element, tested if it is a valid x-coordinate in the curve, and if not, it is incremented and the test is repeated.

The drawbacks of such try-and-increment methods are twofold. First, they must be performed a set number of times (n) even if one finds a valid point in n-x tries. This is to thwart side-channel timing attacks. Secondly, there is always a possibility that n is insufficient and so one has to try again with a new message. The added complexity required to handle these situations can lead to a greater chance of security vulnerabilites in a protocol, as seen in the Dragonblood vulnerabilities discovered in implementations of the WPA3 and EAP-pwd protocols.

Conclusion

In this post, I outlined various security and performance considerations made by the authors of Hashing to Elliptic Curves. I believe that a well-designed and secure set of hash-to-curve ciphersuites will greatly benefit the cryptography landscape as such functions are at the core of many important protocols. To that end, more constructive scrutiny on this draft standard is necessary.