From 10972a809399909575a6fcc2865042bf4a00841c Mon Sep 17 00:00:00 2001 From: Loup Vaillant Date: Mon, 9 Mar 2020 16:47:37 +0100 Subject: [PATCH] Added tests for Elligator direct mappings --- tests/gen/elligator-direct.py | 77 +++++++++++++++++++++++ tests/gen/elligator-inverse.py | 111 +++++++++++++++++++++++++++++++++ tests/gen/elligator.py | 56 ----------------- tests/gen/makefile | 9 ++- tests/test.c | 31 +++++++++ 5 files changed, 225 insertions(+), 59 deletions(-) create mode 100755 tests/gen/elligator-direct.py create mode 100755 tests/gen/elligator-inverse.py diff --git a/tests/gen/elligator-direct.py b/tests/gen/elligator-direct.py new file mode 100755 index 0000000..bdc9ca0 --- /dev/null +++ b/tests/gen/elligator-direct.py @@ -0,0 +1,77 @@ +#! /usr/bin/env python3 + +# This file is dual-licensed. Choose whichever licence you want from +# the two licences listed below. +# +# The first licence is a regular 2-clause BSD licence. The second licence +# is the CC-0 from Creative Commons. It is intended to release Monocypher +# to the public domain. The BSD licence serves as a fallback option. +# +# SPDX-License-Identifier: BSD-2-Clause OR CC0-1.0 +# +# ------------------------------------------------------------------------ +# +# Copyright (c) 2020, Loup Vaillant +# All rights reserved. +# +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions are +# met: +# +# 1. Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# +# 2. Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the +# distribution. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +# HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +# +# ------------------------------------------------------------------------ +# +# Written in 2020 by Loup Vaillant +# +# To the extent possible under law, the author(s) have dedicated all copyright +# and related neighboring rights to this software to the public domain +# worldwide. This software is distributed without any warranty. +# +# You should have received a copy of the CC0 Public Domain Dedication along +# with this software. If not, see +# + +from elligator import fe +from elligator import x25519_public_key +from elligator import can_curve_to_hash +from elligator import curve_to_hash +from elligator import fast_curve_to_hash +from elligator import hash_to_curve +from elligator import fast_hash_to_curve +from elligator import p +from sys import stdin +from random import randrange + +def direct(r1): + q1 = hash_to_curve(r1) + q2 = fast_hash_to_curve(r1) + r2 = curve_to_hash(q1) + if q1 != q2: raise ValueError('Incorrect fast_hash_to_curve') + if r1 != r2: raise ValueError('Round trip failure') + r1 .print() + q1[0].print() # u coordinate only + print() + +direct(fe(0)) # representative 0 maps to point (0, 0) +for i in range(50): + direct(fe(randrange(0, (p-1)/2))) diff --git a/tests/gen/elligator-inverse.py b/tests/gen/elligator-inverse.py new file mode 100755 index 0000000..a9306ba --- /dev/null +++ b/tests/gen/elligator-inverse.py @@ -0,0 +1,111 @@ +#! /usr/bin/env python3 + +# This file is dual-licensed. Choose whichever licence you want from +# the two licences listed below. +# +# The first licence is a regular 2-clause BSD licence. The second licence +# is the CC-0 from Creative Commons. It is intended to release Monocypher +# to the public domain. The BSD licence serves as a fallback option. +# +# SPDX-License-Identifier: BSD-2-Clause OR CC0-1.0 +# +# ------------------------------------------------------------------------ +# +# Copyright (c) 2020, Loup Vaillant +# All rights reserved. +# +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions are +# met: +# +# 1. Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# +# 2. Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the +# distribution. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +# HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +# +# ------------------------------------------------------------------------ +# +# Written in 2020 by Loup Vaillant +# +# To the extent possible under law, the author(s) have dedicated all copyright +# and related neighboring rights to this software to the public domain +# worldwide. This software is distributed without any warranty. +# +# You should have received a copy of the CC0 Public Domain Dedication along +# with this software. If not, see +# + +from elligator import fe +from elligator import x25519_public_key +from elligator import can_curve_to_hash +from elligator import curve_to_hash +from elligator import fast_curve_to_hash +from elligator import hash_to_curve +from elligator import fast_hash_to_curve +from sys import stdin + +# Test a full round trip, and print the relevant test vectors +def full_cycle_check(private_key, u): + fe(private_key).print() + uv = x25519_public_key(private_key) + if uv [0] != u: raise ValueError('Test vector failure') + uv[0].print() + uv[1].print() + if can_curve_to_hash(uv): + h = curve_to_hash(uv) + if h.is_negative(): raise ValueError('Non Canonical representative') + fh = fast_curve_to_hash(uv) + if fh != h: raise ValueError('Incorrect fast_curve_to_hash()') + print('01:') # Success + h.print() # actual value for the hash + c = hash_to_curve(h) + f = fast_hash_to_curve(h) + if f != c : raise ValueError('Incorrect fast_hash_to_curve()') + if c != uv : raise ValueError('Round trip failure') + else: + fh = fast_curve_to_hash(uv) + if not (fh is None): raise ValueError('Fast Curve to Hash did not fail') + print('00:') # Failure + print('00:') # dummy value for the hash + +# read test vectors: +def read_vector(vector): # vector: little endian hex number + cut = vector[:64] # remove final ':' character + acc = 0 # final sum + pos = 1 # power of 256 + for b in bytes.fromhex(cut): + acc += b * pos + pos *= 256 + return acc + +def read_test_vectors(): + vectors = [] + lines = [x.strip() for x in stdin.readlines() if x.strip()] + for i in range(len(lines) // 2): + private = read_vector(lines[i*2 ]) + public = read_vector(lines[i*2 + 1]) + vectors.append((private, fe(public))) + return vectors + +vectors = read_test_vectors() +for v in vectors: + private = v[0] + public = v[1] + full_cycle_check(private, public) + print('') diff --git a/tests/gen/elligator.py b/tests/gen/elligator.py index 2794588..4fef6bf 100755 --- a/tests/gen/elligator.py +++ b/tests/gen/elligator.py @@ -51,8 +51,6 @@ # with this software. If not, see # -import sys # stdin - #################### # Field arithmetic # #################### @@ -447,57 +445,3 @@ def fast_curve_to_hash(point): r = t * isr r = r.abs() return r - -############## -# Test suite # -############## -# Test a full round trip, and print the relevant test vectors -def full_cycle_check(private_key, u): - fe(private_key).print() - uv = x25519_public_key(private_key) - if uv [0] != u: raise ValueError('Test vector failure') - uv[0].print() - uv[1].print() - if can_curve_to_hash(uv): - h = curve_to_hash(uv) - if h.is_negative(): raise ValueError('Non Canonical representative') - fh = fast_curve_to_hash(uv) - if fh != h: raise ValueError('Incorrect fast_curve_to_hash()') - print('01:') # Success - h.print() # actual value for the hash - c = hash_to_curve(h) - f = fast_hash_to_curve(h) - if f != c : raise ValueError('Incorrect fast_hash_to_curve()') - if c != uv : raise ValueError('Round trip failure') - else: - fh = fast_curve_to_hash(uv) - if not (fh is None): raise ValueError('Fast Curve to Hash did not fail') - print('00:') # Failure - print('00:') # dummy value for the hash - -# read test vectors: -def read_vector(vector): # vector: little endian hex number - cut = vector[:64] # remove final ':' character - acc = 0 # final sum - pos = 1 # power of 256 - for b in bytes.fromhex(cut): - acc += b * pos - pos *= 256 - return acc - -def read_test_vectors(): - vectors = [] - lines = [x.strip() for x in sys.stdin.readlines() if x.strip()] - for i in range(len(lines) // 2): - private = read_vector(lines[i*2 ]) - public = read_vector(lines[i*2 + 1]) - vectors.append((private, fe(public))) - return vectors - -vectors = read_test_vectors() -for v in vectors: - private = v[0] - public = v[1] - full_cycle_check(private, public) - print('') - diff --git a/tests/gen/makefile b/tests/gen/makefile index ed3fa26..07179e8 100644 --- a/tests/gen/makefile +++ b/tests/gen/makefile @@ -57,7 +57,7 @@ CFLAGS = -pedantic -Wall -Wextra VEC = chacha20 hchacha20 xchacha20 ietf_chacha20 aead_ietf \ poly1305 blake2b sha512 hmac_sha512 argon2i \ edDSA edDSA_pk ed_25519 ed_25519_pk ed_25519_check \ - x25519 x25519_pk key_exchange elligator + x25519 x25519_pk key_exchange elligator_inv elligator_dir VEC2 = $(patsubst %, %.all.vec, $(VEC)) HEADERS = $(patsubst %, %.h.vec , $(VEC)) VECTORS = ../vectors.h @@ -68,8 +68,10 @@ clean: rm -f *.out *.vec *.o rm -f $(VECTORS) -elligator.vec: elligator.py x25519_pk.all.vec +elligator_inv.vec: elligator-inverse.py elligator.py x25519_pk.all.vec ./$< $@ +elligator_dir.vec: elligator-direct.py elligator.py + ./$< >$@ %.vec: %.out ./$< > $@ @@ -121,7 +123,8 @@ ed_25519.all.vec : ed_25519.vec ed_25519_pk.all.vec : ed_25519_pk.vec ed_25519_check.all.vec: vectors/ed_25519_check key_exchange.all.vec : vectors/key_exchange -elligator.all.vec : elligator.vec +elligator_dir.all.vec : elligator_dir.vec +elligator_inv.all.vec : elligator_inv.vec $(VEC2): mkdir -p $(@D) cat $^ > $@ diff --git a/tests/test.c b/tests/test.c index 5b8d0f2..c2be3cf 100644 --- a/tests/test.c +++ b/tests/test.c @@ -287,6 +287,11 @@ static int test_x25519() return status; } +static void elligator_dir(const vector in[], vector *out) +{ + crypto_elligator2_direct(out->buf, in->buf); +} + ////////////////////////////// /// Self consistency tests /// ////////////////////////////// @@ -835,6 +840,30 @@ static int p_aead() return status; } +// Elligator direct mapping must ignore the most significant bits +static int p_elligator_direct_msb() +{ + int status = 0; + FOR (i, 0, 20) { + RANDOM_INPUT(r, 32); + u8 r1[32]; memcpy(r1, r, 32); r1[31] = (r[31] & 0x3f) | 0x00; + u8 r2[32]; memcpy(r2, r, 32); r2[31] = (r[31] & 0x3f) | 0x40; + u8 r3[32]; memcpy(r3, r, 32); r3[31] = (r[31] & 0x3f) | 0x80; + u8 r4[32]; memcpy(r4, r, 32); r4[31] = (r[31] & 0x3f) | 0xc0; + u8 u [32]; crypto_elligator2_direct(u , r ); + u8 u1[32]; crypto_elligator2_direct(u1, r1); + u8 u2[32]; crypto_elligator2_direct(u2, r2); + u8 u3[32]; crypto_elligator2_direct(u3, r3); + u8 u4[32]; crypto_elligator2_direct(u4, r4); + status |= memcmp(u, u1, 32); + status |= memcmp(u, u2, 32); + status |= memcmp(u, u3, 32); + status |= memcmp(u, u4, 32); + } + printf("%s: elligator direct (msb)\n", status != 0 ? "FAILED" : "OK"); + return status; +} + #define TEST(name, nb_inputs) vector_test(name, #name, nb_inputs, \ nb_##name##_vectors, \ name##_vectors, \ @@ -869,6 +898,7 @@ int main(int argc, char *argv[]) status |= TEST(ed_25519_pk , 1); status |= TEST(ed_25519_check, 3); status |= test_x25519(); + status |= TEST(elligator_dir , 1); printf("\nProperty based tests"); printf("\n--------------------\n"); @@ -896,6 +926,7 @@ int main(int argc, char *argv[]) status |= p_eddsa_overlap(); status |= p_eddsa_incremental(); status |= p_aead(); + status |= p_elligator_direct_msb(); printf("\n%s\n\n", status != 0 ? "SOME TESTS FAILED" : "All tests OK!"); return status; } -- 2.47.3