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, tese do not have a constant time implementation, and could be open to side-channel analysis. The method defined here is proposed an 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 use are SHA-256, SHA-384 and SHA-512, and these match to the curves of P-256, P384 and P521, respectively.
Hash to Curve using CIRCL |
Outline
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)
Coding
We can use the Kryptology library developed by Coinbase to implement the matching:
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:
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:
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 co-ordinate. For P-521:
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 co-ordinate value.