Hash To Curve With Cloudflare CIRCL

One of the great advancements with the Internet has been RFC (Request For Comment) documents and Internet Engineering Task Force (IETF)…

Hash To Curve With Cloudflare CIRCL

One of the great advancements with the Internet has been RFC (Request For Comment) documents and Internet Engineering Task Force (IETF) Internet-Drafts. The classics of such as RFC791 (IPv6) and RFC793 (TCP) brought a level of conformity that broke the dominance of large companies and countries in defining standards.

A new Internet-Draft [here] brings a new standardization for hashing data values into curves. This can be in the form of hashing a value to a scalar — which might then be used to multiply a point — or onto a curve:

Its importance is due to the increasing usage of elliptic curve methods and their application into zero-knowledge proofs (ZKPs) and multiparty computation (MPC).

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 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)

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)

We can use the CIRCL library developed by Cloudflare 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]
 }

Dst := "QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_NU_"

switch curvetype {
 case "P256":
  G = group.P256
  Dst = "QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_NU_"
  // QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_RO_
 case "P384":
  G = group.P384
  Dst = "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_NU_"
  //  QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_RO_

case "P521":
  G = group.P521
  Dst = "QUUX-V01-CS02-with-P521_XMD:SHA-512_SSWU_NU_"
  // QUUX-V01-CS02-with-P521_XMD:SHA-512_SSWU_RO_
 }

// hashFunc := G.HashToElement

hashFunc := G.HashToElementNonUniform

// want := G.NewElement()

myhash := hashFunc([]byte(Msg), []byte(Dst))
 //   _:= want.UnmarshalBinary(v.P.toBytes())
 fmt.Printf("Message: %s\n", Msg)
 fmt.Printf("Destination: %s\n", Dst)
 fmt.Printf("Curve group: %s\n", curvetype)
 fmt.Printf("Point:\n%v\n", myhash)

A sample run [here]:

Message: abc
Destination: QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_NU_
Curve group: P256
Point:
x: 0xfc3f5d734e8dce41ddac49f47dd2b8a57257522a865c124ed02b92b5237befa4
y: 0xfe4d197ecf5a62645b9690599e1d80e82c500b22ac705a0b421fac7b47157866

This matches the test vector at [here].

Conclusions

So, say thank you to RFCs and Internet-Drafts for the ability for systems to intercommunicate. The new hashing standard for hashing to scalars and curves is interesting, especially in their applications to privacy and resilience.

If you want to know more about the Cloudflare CIRCL library:

https://asecuritysite.com/circl