From 1874deb647df9ece06573fe7f79fd50f2ca6eb20 Mon Sep 17 00:00:00 2001 From: Loup Vaillant Date: Wed, 18 Mar 2020 15:40:04 +0100 Subject: [PATCH] Elligator: take cofactor from secret key instead of tweak This allows the simplification of the implementation of higher level interfaces. The idea is, only the scalar and cofactor have any influence over whether the inverse map succeeds or fail. This means that when it fails, the padding & sign have not be used at all, and can be "reused" to generate another random seed. In practice, this means we can use Chacha20 or Blake2, or any hash that outputs 64 random bytes from 32 random bytes, use 32 bytes to make an attempt, then use the *other* 32 bytes to either generate more random bytes (if we failed), or to use the tweak (if we succeed). The tweak has also been modified to simplify the implementation. The sign bit is now the least significant bit, and the padding bits are the most significant bits. The computational savings are negligible, but this allows neat micro-simplifications. --- src/monocypher.c | 32 +++++++++++++++++++----------- tests/gen/elligator-inverse.py | 36 +++++++++++++++++++--------------- 2 files changed, 41 insertions(+), 27 deletions(-) diff --git a/src/monocypher.c b/src/monocypher.c index f029d03..8b57f26 100644 --- a/src/monocypher.c +++ b/src/monocypher.c @@ -2301,12 +2301,15 @@ void crypto_elligator2_direct(uint8_t curve[32], const uint8_t hash[32]) } // Compute the representative of a point (defined by the secret key and -// tweak), if possible. If not it does nothing and returns -1 -// The tweak comprises 3 parts: -// - Bits 4-5: random padding -// - Bit 3 : sign of the v coordinate (0 if positive, 1 if negative) -// - Bits 0-2: cofactor -// The bits 6-7 are ignored. +// tweak), if possible. If not it does nothing and returns -1. Note +// that the success of the operation depends only on the value of +// secret_key. The tweak parameter is used only when we succeed. +// +// The tweak should be a random byte. Beyond that, its contents are an +// implementation detail. Currently, the tweak comprises 2 parts: +// - Bit 1 : sign of the v coordinate (0 if positive, 1 if negative) +// - Bit 2-5: not used +// - Bits 6-7: random padding // // Note that to ensure the representative is fully random, we do *not* // clear the cofactor. It is otherwise compatible with X25519 (once @@ -2368,9 +2371,10 @@ int crypto_elligator2_inverse(u8 hash[32], const u8 secret_key[32], u8 tweak) // - A (single) Montgomery ladder would be twice as slow. // - An actual scalar multiplication would hurt performance. // - A full table lookup would take more code. - int a = (tweak >> 2) & 1; - int b = (tweak >> 1) & 1; - int c = (tweak >> 0) & 1; + u8 cofactor = secret_key[0] & 7; + int a = (cofactor >> 2) & 1; + int b = (cofactor >> 1) & 1; + int c = (cofactor >> 0) & 1; fe t1, t2, t3; fe_0(t1); fe_ccopy(t1, sqrtm1, b); @@ -2437,7 +2441,7 @@ int crypto_elligator2_inverse(u8 hash[32], const u8 secret_key[32], u8 tweak) WIPE_BUFFER(t3); WIPE_CTX(&low_order_point); return -1; } - fe_ccopy(t1, t2, (tweak >> 3) & 1); + fe_ccopy(t1, t2, tweak & 1); fe_mul (t3, t1, t3); fe_add (t1, t3, t3); fe_neg (t2, t3); @@ -2445,7 +2449,7 @@ int crypto_elligator2_inverse(u8 hash[32], const u8 secret_key[32], u8 tweak) fe_tobytes(hash, t3); // Pad with two random bits - hash[31] |= (tweak << 2) & 0xc0; + hash[31] |= tweak & 0xc0; WIPE_BUFFER(t1); WIPE_BUFFER(scalar); WIPE_BUFFER(t2); WIPE_CTX(&pk); @@ -2462,6 +2466,12 @@ void crypto_elligator2_key_pair(u8 hash[32], u8 secret_key[32], u8 seed[32]) do { crypto_chacha20(buf, 0, 64, buf+32, zero); } while(crypto_elligator2_inverse(buf+32, buf, buf[32])); + // Note that buf[32] is not actually reused. Either we loop one + // more time and buf[32] is used for the new seed, or we succeeded, + // and buf[32] is used as a tweak parameter. + // + // This is because the return value of crypto_elligator2_inverse() + // is independent from its tweak parameter. crypto_wipe(seed, 32); FOR (i, 0, 32) { hash [i] = buf[i+32]; } diff --git a/tests/gen/elligator-inverse.py b/tests/gen/elligator-inverse.py index 18f8118..e6d1517 100755 --- a/tests/gen/elligator-inverse.py +++ b/tests/gen/elligator-inverse.py @@ -62,9 +62,9 @@ from elligator_scalarmult import print_scalar from random import randrange def private_to_hash(scalar, tweak): - cofactor = tweak % 8 ; tweak = tweak // 8 - v_is_negative = tweak % 2 == 1; tweak = tweak // 2 - msb = tweak * 2**254 + cofactor = scalar % 8 + v_is_negative = tweak % 2 == 1; + msb = (tweak // 2**6) * 2**254 u = scalarmult(scalar, cofactor) r1 = None if can_curve_to_hash(u): @@ -79,9 +79,10 @@ def private_to_hash(scalar, tweak): return r1.val + msb # All possible failures -for tweak in range(2**4): +for cofactor in range(8): + tweak = randrange(0, 256) while True: - scalar = randrange(0, 2**256) + scalar = randrange(0, 2**253) * 8 + cofactor r = private_to_hash(scalar, tweak) if r is None: print_scalar(scalar) @@ -92,14 +93,17 @@ for tweak in range(2**4): break # All possible successes -for tweak in range(2**6): - while True: - scalar = randrange(0, 2**256) - r = private_to_hash(scalar, tweak) - if r is not None: - print_scalar(scalar) - print(format(tweak, '02x') + ":") - print('00:') # Success - print_scalar(r) - print() - break +for cofactor in range(8): + for sign in range(2): + for msb in range(4): + tweak = sign + randrange(0, 32) * 2 + msb * 64 + while True: + scalar = randrange(0, 2**253) * 8 + cofactor + r = private_to_hash(scalar, tweak) + if r is not None: + print_scalar(scalar) + print(format(tweak, '02x') + ":") + print('00:') # Success + print_scalar(r) + print() + break -- 2.47.3