Overcoming Dragonblood: Hashing Data To An Elliptic Curve Point (or Scalar) In A Constant Time

Let’s say we have almost 2²⁵⁶ integer point values. This will give us…
Photo by Tim Mossholder on Unsplash

Overcoming Dragonblood: Hashing Data To An Elliptic Curve Point (or Scalar) In A Constant Time

Let’s say we have almost 2²⁵⁶ integer point values. This will give us 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 different (x,y) points. Can we find a way to hash some data onto one of these points, and so it is not possible to know the data that resulted in that point, and that it is highly unlikely for two different data elements to end up with the same data point?

In ECC (Elliptic Curve Cryptography) we often have to hash our data to a scalar value or to a point on the curve. Once hashed, it is difficult to reverse the operation (unless we did a brute-force search for it). We can either encode-to-curve (non-uniform) to hash-to-curve. Overall we often use the method of encoding/hashing to a curve with PAKE (password-authenticated key exchange), IBE (Identity-based Encryption) and within Verifiable Random Functions (VRF) and Oblivious Pseudorandom Functions (VOPRF).

One method of doing this is to hash to a value, and then find the nearest point — known as “try-and-increment” or “hunt-and-peck”. Unfortunately, these do not have a constant time implementation and could be open to side-channel analysis. One example of an attack against this is with WPA3, and where the Dragonblood vulnerability exploited a side-channel attack on the hashing of a password to the curve.

One method of overcoming these side channel attacks is proposed an Internet-Draft standard by the Internet Engineering Task Force (IETF)[here] related to “Hashing to Elliptic Curves”:

In this case, we encoding and hashing a value into a point using the Cloudflare CIRLC library. The main hashing methods are SHA-256, SHA-384 and SHA-512, and these match to the curves of P-256, P384 and P521, respectively.

For the hashing of our data to a scalar, we use the ExpandMessageXmd function. This produces a uniformly random byte string using a cryptographic hash function H() that outputs b bits. Overall we typically use SHA-256 or SHA-512 for the hashing function. As an input, we use a message string and a DST (Domain Separation Tag) string. The method defined [here]:

expand_message_xmd(msg, DST, len_in_bytes)
Parameters:
   - H, a hash function (see requirements above).
   - b_in_bytes, b / 8 for b the output size of H in bits.
     For example, for b = 256, b_in_bytes = 32.
   - s_in_bytes, the input block size of H, measured in bytes (see
     discussion above). For example, for SHA-256, s_in_bytes = 64.
   Input:
   - msg, a byte string.
   - DST, a byte string of at most 255 bytes.
     See below for information on using longer DSTs.
   - len_in_bytes, the length of the requested output in bytes,
     not greater than the lesser of (255 * b_in_bytes) or 2^16-1.
   Output:
   - uniform_bytes, a byte string.
   Steps:
   1.  ell = ceil(len_in_bytes / b_in_bytes)
   2.  ABORT if ell > 255
   3.  DST_prime = DST || I2OSP(len(DST), 1)
   4.  Z_pad = I2OSP(0, s_in_bytes)
   5.  l_i_b_str = I2OSP(len_in_bytes, 2)
   6.  msg_prime = Z_pad || msg || l_i_b_str || I2OSP(0, 1) || DST_prime
   7.  b_0 = H(msg_prime)
   8.  b_1 = H(b_0 || I2OSP(1, 1) || DST_prime)
   9.  for i in (2, ..., ell):
   10.    b_i = H(strxor(b_0, b_(i - 1)) || I2OSP(i, 1) || DST_prime)
   11. uniform_bytes = b_1 || ... || b_ell
   12. return substr(uniform_bytes, 0, len_in_bytes)

The DST is selected which is unique to the domain, and which will include the Suite ID. The format for this is:

// Suite ID: CURVE_ID || "_" || HASH_ID || "_" || MAP_ID || "_" || ENC_VAR || "_"

and where:

HASH_ID is EXP_TAG || ":" || HASH_NAME
EXP_TAG, we have "XMD" for expand_message_xmd
MAP_ID - "SSWU" for Simplified SWU (Map-to-curve method)
ENC_VAR is "RO" for hash_to_curve, and "NU", is encode_to_curve.

Using a DST string of “P256_XMD:SHA-256_SSWU_RO_”, the Golang call for the Kryptography library, and for 48 byte output is:

xmd, _ := core.ExpandMessageXmd(sha256.New, msg, []byte("P256_XMD:SHA-256_SSWU_RO_"), 48)

After this, we convert xmd into a Big Integer:

v := new(big.Int).SetBytes(xmd)

And then calculate this value modulo of the order of the curve:

res := v.Mod(v, elliptic.P256().Params().N)

Suite ID

The DST is selected which is unique to the domain, and which will include the Suite ID. The format for this is:

// Suite ID: CURVE_ID || "_" || HASH_ID || "_" || MAP_ID || "_" || ENC_VAR || "_"

and where:

HASH_ID is EXP_TAG || ":" || HASH_NAME
EXP_TAG, we have "XMD" for expand_message_xmd
MAP_ID - "SSWU" for Simplified SWU (Map-to-curve method)
ENC_VAR is "RO" for hash_to_curve, and "NU", is encode_to_curve.

.Using a DST string of “P256_XMD:SHA-256_SSWU_RO_”, the Golang call for the Kryptography library, and for 48-byte output is:

xmd, _ := core.ExpandMessageXmd(sha256.New, msg, []byte("P256_XMD:SHA-256_SSWU_RO_"), 48)

After this, we convert xmd into a Big Integer:

v := new(big.Int).SetBytes(xmd)

And then calculate this value modulo of the order of the curve:

res := v.Mod(v, elliptic.P256().Params().N)

Coding

We can use the Kryptology library developed by Coinbase to implement the matching [here]:

package main
import (
 "fmt"
 "os"
 "github.com/cloudflare/circl/group"
)
func main() {
 var G group.Group
 Msg := "abc"
 curvetype := "P256"
 argCount := len(os.Args[1:])
 if argCount > 0 {
  curvetype = os.Args[1]
 }
 if argCount > 1 {
  Msg = os.Args[2]
 }
 DstNU := "QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_NU_"
 DstRO := "QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_RO_"
 switch curvetype {
 case "P256":
  G = group.P256
  DstNU = "QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_NU_"
  DstRO = "QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_RO_"
  // _NU_ encode to curve
  // _RO_ hash to curve
 case "P384":
  G = group.P384
  DstNU = "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_NU_"
  DstRO = "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_RO_"
 case "P521":
  G = group.P521
  DstNU = "QUUX-V01-CS02-with-P521_XMD:SHA-512_SSWU_NU_"
  DstRO = "QUUX-V01-CS02-with-P521_XMD:SHA-512_SSWU_RO_"
 }
 myhash := G.HashToElementNonUniform([]byte(Msg), []byte(DstNU))
 fmt.Printf("Message: %s\n", Msg)
 fmt.Printf("Curve group: %s\n", curvetype)
 fmt.Printf("\n== Encode to curve ===\n")
 fmt.Printf("Destination: %s\n", DstNU)
 fmt.Printf("Point (Non-uniform - encode to curve):\n%v\n", myhash)
 myhash3 := G.HashToElement([]byte(Msg), []byte(DstRO))
 fmt.Printf("\n== Hash to curve ===\n")
 fmt.Printf("Destination: %s\n", DstRO)
 fmt.Printf("Point (Element - hash to curve):\n%v\n", myhash3)
 fmt.Printf("\n== Scalar ===\n")
 fmt.Printf("Destination: %s\n", DstNU)
 myhash2 := G.HashToScalar([]byte(Msg), []byte(DstNU))
 fmt.Printf("Scalar:\n%v\n", myhash2)
 fmt.Printf("Destination: %s\n", DstRO)
 myhash4 := G.HashToScalar([]byte(Msg), []byte(DstRO))
 fmt.Printf("Scalar:\n%v\n", myhash4)
}

A sample run [here]:

Message: abc
== Encode to curve ===
Destination: QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_NU_
Curve group: P256
Point (Non-uniform - encode to curve):
x: 0xfc3f5d734e8dce41ddac49f47dd2b8a57257522a865c124ed02b92b5237befa4
y: 0xfe4d197ecf5a62645b9690599e1d80e82c500b22ac705a0b421fac7b47157866

== Hash to curve ===
Destination: QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_RO_
Curve group: P256
Point (Element - hash to curve):
x: 0xbb8b87485551aa43ed54f009230450b492fead5f1cc91658775dac4a3388a0f
y: 0x5c41b3d0731a27a7b14bc0bf0ccded2d8751f83493404c84a88e71ffd424212e

== Scalar ===
Scalar:
0x08536fc53220301da264515f370cb8eaf6de3a2f163f2ad565758f3b3faccdcf

The “NU_” (encode to curve) matches the test vector at [here], and has 32 bytes (256 bits) for each co-ordinate value. The test vector for “RO_” (hash to curve) is [here]. For P-384 [here]:

Message: abc

== Encode to curve ===
Destination: QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_NU_
Curve group: P384
Point (Non-uniform - encode to curve):
x: 0x1f08108b87e703c86c872ab3eb198a19f2b708237ac4be53d7929fb4bd5194583f40d052f32df66afe5249c9915d139b
y: 0x1369dc8d5bf038032336b989994874a2270adadb67a7fcc32f0f8824bc5118613f0ac8de04a1041d90ff8a5ad555f96c

== Hash to curve ===
Destination: QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_RO_
Curve group: P384
Point (Element - hash to curve):
x: 0xe02fc1a5f44a7519419dd314e29863f30df55a514da2d655775a81d413003c4d4e7fd59af0826dfaad4200ac6f60abe1
y: 0x1f638d04d98677d65bef99aef1a12a70a4cbb9270ec55248c04530d8bc1f8f90f8a6a859a7c1f1ddccedf8f96d675f6

== Scalar ===
Scalar:
0x9fa3abf517300a1ae4e1ff4f0751732258c1e94582e7ebcd230fc06b172533469e8182a992d54b436820ae8120fdf4de

This has 48 bytes (384 bits) for each coordinate. For P-521 [here]:

Message: abc

== Encode to curve ===
Destination: QUUX-V01-CS02-with-P521_XMD:SHA-512_SSWU_NU_
Curve group: P521
Point (Non-uniform - encode to curve):
x: 0xc720ab56aa5a7a4c07a7732a0a4e1b909e32d063ae1b58db5f0eb5e09f08a9884bff55a2bef4668f715788e692c18c1915cd034a6b998311fcf46924ce66a2be9a
y: 0x3570e87f91a4f3c7a56be2cb2a078ffc153862a53d5e03e5dad5bccc6c529b8bab0b7dbb157499e1949e4edab21cf5d10b782bc1e945e13d7421ad8121dbc72b1d

== Hash to curve ===
Destination: QUUX-V01-CS02-with-P521_XMD:SHA-512_SSWU_RO_
Curve group: P521
Point (Element - hash to curve):
x: 0x2f89a1677b28054b50d15e1f81ed6669b5a2158211118ebdef8a6efc77f8ccaa528f698214e4340155abc1fa08f8f613ef14a043717503d57e267d57155cf784a4
y: 0x10e0be5dc8e753da8ce51091908b72396d3deed14ae166f66d8ebf0a4e7059ead169ea4bead0232e9b700dd380b316e9361cfdba55a08c73545563a80966ecbb86d

== Scalar ===
Scalar:
0x00c7db17b594df83dafa74f9d7365f57ef86bf82449e9a43673d0c648ad668a17de2315ab37de68609ab761ac3663d6155ddcecc0ff0fcb59f2cb0dbf7bc71c3c016

This has 65 bytes (520 bits) for each coordinate value.

Conclusion

Side channels are often difficult to overcome, but WPA-3 was exposed with its password to curve method. This exposed the Dragonblood vulnerability:

To overcome this, we can use the “Hashing to Elliptic Curves” proposed standard.