From 5d92b853f6b875ba8d1a1b51b305f14df5adb8aa Mon Sep 17 00:00:00 2001 From: Nicola Tuveri Date: Fri, 17 Aug 2018 23:00:44 +0300 Subject: [PATCH] Replace GFp ladder implementation with ladd-2002-it-4 from EFD The EFD database does not state that the "ladd-2002-it-3" algorithm assumes X1 != 0. Consequently the current implementation, based on it, fails to compute correctly if the affine x coordinate of the scalar multiplication input point is 0. We replace this implementation using the alternative algorithm based on Eq. (9) and (10) from the same paper, which being derived from the additive relation of (6) does not incur in this problem, but costs one extra field multiplication. The EFD entry for this algorithm is at https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#ladder-ladd-2002-it-4 and the code to implement it was generated with tooling. Regression tests add one positive test for each named curve that has such a point. The `SharedSecret` was generated independently from the OpenSSL codebase with sage. This bug was originally reported by Dmitry Belyavsky on the openssl-users maling list: https://mta.openssl.org/pipermail/openssl-users/2018-August/008540.html Co-authored-by: Billy Brumley Reviewed-by: Andy Polyakov Reviewed-by: Tim Hudson (Merged from https://github.com/openssl/openssl/pull/7000) --- crypto/ec/ecp_smpl.c | 63 ++--- test/recipes/30-test_evp_data/evppkey_ecc.txt | 237 ++++++++++++++++++ 2 files changed, 270 insertions(+), 30 deletions(-) diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c index 7ac519ca03..d0c5557ff4 100644 --- a/crypto/ec/ecp_smpl.c +++ b/crypto/ec/ecp_smpl.c @@ -1483,10 +1483,10 @@ int ec_GFp_simple_ladder_pre(const EC_GROUP *group, } /*- - * Differential addition-and-doubling using Eq. (8) and (10) from Izu-Takagi + * Differential addition-and-doubling using Eq. (9) and (10) from Izu-Takagi * "A fast parallel elliptic curve multiplication resistant against side channel * attacks", as described at - * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#ladder-ladd-2002-it-3 + * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#ladder-ladd-2002-it-4 */ int ec_GFp_simple_ladder_step(const EC_GROUP *group, EC_POINT *r, EC_POINT *s, @@ -1511,39 +1511,42 @@ int ec_GFp_simple_ladder_step(const EC_GROUP *group, || !group->meth->field_mul(group, t2, r->X, s->Z, ctx) || !group->meth->field_mul(group, t3, r->Z, s->X, ctx) || !group->meth->field_mul(group, t4, group->a, t1, ctx) - || !BN_mod_sub_quick(t4, t0, t4, group->field) - || !BN_mod_add_quick(t5, t3, t2, group->field) - || !group->meth->field_sqr(group, t4, t4, ctx) - || !group->meth->field_mul(group, t5, t1, t5, ctx) - || !BN_mod_lshift_quick(t0, group->b, 2, group->field) - || !group->meth->field_mul(group, t5, t0, t5, ctx) - || !BN_mod_sub_quick(t5, t4, t5, group->field) + || !BN_mod_add_quick(t0, t0, t4, group->field) + || !BN_mod_add_quick(t4, t3, t2, group->field) + || !group->meth->field_mul(group, t0, t4, t0, ctx) + || !group->meth->field_sqr(group, t1, t1, ctx) + || !BN_mod_lshift_quick(t7, group->b, 2, group->field) + || !group->meth->field_mul(group, t1, t7, t1, ctx) + || !BN_mod_lshift1_quick(t0, t0, group->field) + || !BN_mod_add_quick(t0, t1, t0, group->field) + || !BN_mod_sub_quick(t1, t2, t3, group->field) + || !group->meth->field_sqr(group, t1, t1, ctx) + || !group->meth->field_mul(group, t3, t1, p->X, ctx) + || !group->meth->field_mul(group, t0, p->Z, t0, ctx) /* s->X coord output */ - || !group->meth->field_mul(group, s->X, t5, p->Z, ctx) - || !BN_mod_sub_quick(t3, t2, t3, group->field) - || !group->meth->field_sqr(group, t3, t3, ctx) + || !BN_mod_sub_quick(s->X, t0, t3, group->field) /* s->Z coord output */ - || !group->meth->field_mul(group, s->Z, t3, p->X, ctx) - || !group->meth->field_sqr(group, t2, r->X, ctx) - || !group->meth->field_sqr(group, t4, r->Z, ctx) - || !group->meth->field_mul(group, t1, t4, group->a, ctx) - || !BN_mod_add_quick(t6, r->X, r->Z, group->field) + || !group->meth->field_mul(group, s->Z, p->Z, t1, ctx) + || !group->meth->field_sqr(group, t3, r->X, ctx) + || !group->meth->field_sqr(group, t2, r->Z, ctx) + || !group->meth->field_mul(group, t4, t2, group->a, ctx) + || !BN_mod_add_quick(t5, r->X, r->Z, group->field) + || !group->meth->field_sqr(group, t5, t5, ctx) + || !BN_mod_sub_quick(t5, t5, t3, group->field) + || !BN_mod_sub_quick(t5, t5, t2, group->field) + || !BN_mod_sub_quick(t6, t3, t4, group->field) || !group->meth->field_sqr(group, t6, t6, ctx) - || !BN_mod_sub_quick(t6, t6, t2, group->field) - || !BN_mod_sub_quick(t6, t6, t4, group->field) - || !BN_mod_sub_quick(t7, t2, t1, group->field) - || !group->meth->field_sqr(group, t7, t7, ctx) - || !group->meth->field_mul(group, t5, t4, t6, ctx) - || !group->meth->field_mul(group, t5, t0, t5, ctx) + || !group->meth->field_mul(group, t0, t2, t5, ctx) + || !group->meth->field_mul(group, t0, t7, t0, ctx) /* r->X coord output */ - || !BN_mod_sub_quick(r->X, t7, t5, group->field) - || !BN_mod_add_quick(t2, t2, t1, group->field) - || !group->meth->field_sqr(group, t5, t4, ctx) - || !group->meth->field_mul(group, t5, t5, t0, ctx) - || !group->meth->field_mul(group, t6, t6, t2, ctx) - || !BN_mod_lshift1_quick(t6, t6, group->field) + || !BN_mod_sub_quick(r->X, t6, t0, group->field) + || !BN_mod_add_quick(t6, t3, t4, group->field) + || !group->meth->field_sqr(group, t3, t2, ctx) + || !group->meth->field_mul(group, t7, t3, t7, ctx) + || !group->meth->field_mul(group, t5, t5, t6, ctx) + || !BN_mod_lshift1_quick(t5, t5, group->field) /* r->Z coord output */ - || !BN_mod_add_quick(r->Z, t5, t6, group->field)) + || !BN_mod_add_quick(r->Z, t7, t5, group->field)) goto err; ret = 1; diff --git a/test/recipes/30-test_evp_data/evppkey_ecc.txt b/test/recipes/30-test_evp_data/evppkey_ecc.txt index 685af17994..8e95c02349 100644 --- a/test/recipes/30-test_evp_data/evppkey_ecc.txt +++ b/test/recipes/30-test_evp_data/evppkey_ecc.txt @@ -4364,3 +4364,240 @@ PeerKey=ALICE_cf_wap-wsg-idm-ecid-wtls9_PUB SharedSecret=948d3030e95cead39a1bb3d8a01c2be178517ba7 # tests: 484 + +Title=zero x-coord regression tests + +PrivateKey=ALICE_zero_prime192v1 +-----BEGIN PRIVATE KEY----- +MDkCAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQEEHzAdAgEBBBhaPNk8jG5hSG6y8tUqUoOaNNsZ3APU +pps= +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_prime192v1_PUB +-----BEGIN PUBLIC KEY----- +MEkwEwYHKoZIzj0CAQYIKoZIzj0DAQEDMgAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAe2hWBe5g +DLNj216pEvK7XjoKLg5gNg8S +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_prime192v1 +PeerKey=BOB_zero_prime192v1_PUB +SharedSecret=baaffd49a8399d2ad52cbbe24d47b67afb4b3cf436f1cd65 + +PrivateKey=ALICE_zero_prime192v2 +-----BEGIN PRIVATE KEY----- +MDkCAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQIEHzAdAgEBBBj1AIQMJ7jqYIKCvxYAS+qKMmKmH0to +41k= +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_prime192v2_PUB +-----BEGIN PUBLIC KEY----- +MEkwEwYHKoZIzj0CAQYIKoZIzj0DAQIDMgAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB4Gj7Qqt +2wx/jwFlKgvE4rnd50LspdMk +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_prime192v2 +PeerKey=BOB_zero_prime192v2_PUB +SharedSecret=b8f200a4b87064f2e8600685ca3e69b8e661a117aabc770b + +PrivateKey=ALICE_zero_prime192v3 +-----BEGIN PRIVATE KEY----- +MDkCAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQMEHzAdAgEBBBh/maLQMSlea9BfLqGy5NPuK0YAH/cz +GqI= +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_prime192v3_PUB +-----BEGIN PUBLIC KEY----- +MEkwEwYHKoZIzj0CAQYIKoZIzj0DAQMDMgAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZEzb63e2 +3MKatRLR9Y1M5JEdI9jwMocI +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_prime192v3 +PeerKey=BOB_zero_prime192v3_PUB +SharedSecret=b5de857d355bc5b9e270a4c290ea9728d764d8b243ff5d8d + +PrivateKey=ALICE_zero_prime239v1 +-----BEGIN PRIVATE KEY----- +MD8CAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQQEJTAjAgEBBB5pYWzRYI+c6O7NXCt0H2kw8XRL3rhe +4MrJT8j++CI= +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_prime239v1_PUB +-----BEGIN PUBLIC KEY----- +MFUwEwYHKoZIzj0CAQYIKoZIzj0DAQQDPgAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA +Ox02uwNNLFuvDRn5ip8TxvW0W22R7UzJa9Av6/nh +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_prime239v1 +PeerKey=BOB_zero_prime239v1_PUB +SharedSecret=6b6206408bd05d42daa2cd224c401a1230b44e184f17b82f385f22dac215 + +PrivateKey=ALICE_zero_prime239v2 +-----BEGIN PRIVATE KEY----- +MD8CAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQUEJTAjAgEBBB5l8bB7Cpmr7vyx9FiOT2wEF3YOFbDG +bmRr3Vi/xr4= +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_prime239v2_PUB +-----BEGIN PUBLIC KEY----- +MFUwEwYHKoZIzj0CAQYIKoZIzj0DAQUDPgAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA +IOg3VJGQ89d1GWg4Igxcj5xpDmJiP8tv+e4mxt5U +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_prime239v2 +PeerKey=BOB_zero_prime239v2_PUB +SharedSecret=772c2819c960c78f28f21f6542b7409294fad1f84567c44c4b7678dc0e42 + +PrivateKey=ALICE_zero_prime239v3 +-----BEGIN PRIVATE KEY----- +MD8CAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQYEJTAjAgEBBB5HF5FABzUOTYMZg9UdZTx/oRERm/fU +M/+otKzpLjA= +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_prime239v3_PUB +-----BEGIN PUBLIC KEY----- +MFUwEwYHKoZIzj0CAQYIKoZIzj0DAQYDPgAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA +AsZ4u6r3qQI78EYBpiSgWjqNpoeShjr5piecMBWj +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_prime239v3 +PeerKey=BOB_zero_prime239v3_PUB +SharedSecret=56a71f5dd1611e8032c3e2d8224d86e5e8c2fc6480d74c0e282282decd43 + +PrivateKey=ALICE_zero_prime256v1 +-----BEGIN PRIVATE KEY----- +MEECAQAwEwYHKoZIzj0CAQYIKoZIzj0DAQcEJzAlAgEBBCDXhMb6aR4JR2+l2tmgYqP0r8S4jtym +yH++awvF2nGhhg== +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_prime256v1_PUB +-----BEGIN PUBLIC KEY----- +MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA +AABmSFx4Di+D1yQzvV2EoGu2VBwq8x2uhxcov4VqF0+T9A== +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_prime256v1 +PeerKey=BOB_zero_prime256v1_PUB +SharedSecret=c4f5607deb8501f1a4ba23fce4122a4343a17ada2c86a9c8e0d03d92d4a4c84c + +PrivateKey=ALICE_zero_secp112r2 +-----BEGIN PRIVATE KEY----- +MCwCAQAwEAYHKoZIzj0CAQYFK4EEAAcEFTATAgEBBA4hh3tRkG3tnA0496ffMw== +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_secp112r2_PUB +-----BEGIN PUBLIC KEY----- +MDIwEAYHKoZIzj0CAQYFK4EEAAcDHgAEAAAAAAAAAAAAAAAAAAAS5eEOWDV/Wk7w4djyDQ== +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_secp112r2 +PeerKey=BOB_zero_secp112r2_PUB +SharedSecret=958cc1cb425713678830a4d7d95e + +PrivateKey=ALICE_zero_secp128r1 +-----BEGIN PRIVATE KEY----- +MC4CAQAwEAYHKoZIzj0CAQYFK4EEABwEFzAVAgEBBBCykSzic/h3T2K6SkSP1SGt +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_secp128r1_PUB +-----BEGIN PUBLIC KEY----- +MDYwEAYHKoZIzj0CAQYFK4EEABwDIgAEAAAAAAAAAAAAAAAAAAAAAABya8M5aeOpNG3z799IdHc= +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_secp128r1 +PeerKey=BOB_zero_secp128r1_PUB +SharedSecret=5235d452066f126cd7e99eea00fd3068 + +PrivateKey=ALICE_zero_secp160r1 +-----BEGIN PRIVATE KEY----- +MDMCAQAwEAYHKoZIzj0CAQYFK4EEAAgEHDAaAgEBBBUACoRnbig69XLlh5VcRexpbbn5zwA= +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_secp160r1_PUB +-----BEGIN PUBLIC KEY----- +MD4wEAYHKoZIzj0CAQYFK4EEAAgDKgAEAAAAAAAAAAAAAAAAAAAAAAAAAAAG/w1po29wYlxlygXs +MGfbiGg5ng== +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_secp160r1 +PeerKey=BOB_zero_secp160r1_PUB +SharedSecret=9ccd0ab8d093b6acdb3fe14c3736a0dfe61a4666 + +PrivateKey=ALICE_zero_secp160r2 +-----BEGIN PRIVATE KEY----- +MDMCAQAwEAYHKoZIzj0CAQYFK4EEAB4EHDAaAgEBBBUAQFGxInSw1eAvd45E9TUdbXtJGnA= +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_secp160r2_PUB +-----BEGIN PUBLIC KEY----- +MD4wEAYHKoZIzj0CAQYFK4EEAB4DKgAEAAAAAAAAAAAAAAAAAAAAAAAAAAAZtSBSZqfmXp47v5z2 +ZZZl2JFxDg== +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_secp160r2 +PeerKey=BOB_zero_secp160r2_PUB +SharedSecret=303e0a282ac86f463fe834cb51b0057be42ed5ab + +PrivateKey=ALICE_zero_secp384r1 +-----BEGIN PRIVATE KEY----- +ME4CAQAwEAYHKoZIzj0CAQYFK4EEACIENzA1AgEBBDD6kgzKbg28zbQyVTdC0IdHbm0UCQt2Rdbi +VVHJeYRSnNpFOiFLaOsGOmwoeZzj6jc= +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_secp384r1_PUB +-----BEGIN PUBLIC KEY----- +MHYwEAYHKoZIzj0CAQYFK4EEACIDYgAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA +AAAAAAAAAAAAAAAAAAAAPPme8E9RpepjC6P5+WDdWToUyb45/SvSFdO0sIqq+Gu/kn8sRuUqsG+3 +QriFDlIe +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_secp384r1 +PeerKey=BOB_zero_secp384r1_PUB +SharedSecret=b1cfeaeef51dfd487d3a8b2849f1592e04d63f2d2c88b310a6290ebfe5399f5ffe954eabd0619231393e56c35b242986 + +PrivateKey=ALICE_zero_secp521r1 +-----BEGIN PRIVATE KEY----- +MGACAQAwEAYHKoZIzj0CAQYFK4EEACMESTBHAgEBBEIAbddDLMUWbAsY7l3vbNDmntXuAUcDYPg5 +w/cgUwSCIvrV9MBeSG8AWqT16riHmHlsn+XI5PAJM6eij3JDahnu9Mo= +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_secp521r1_PUB +-----BEGIN PUBLIC KEY----- +MIGbMBAGByqGSM49AgEGBSuBBAAjA4GGAAQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA +AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA0g7J/qa1d8ENJsobtEb0CymeZIsa +1Qiq0GiJb+4/jmFLxjBU1Xcr8Bpl1BLgvKqOll0vXTMtfzn4RtRArgAfT4c= +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_secp521r1 +PeerKey=BOB_zero_secp521r1_PUB +SharedSecret=003fc3028f61db94b20c7cd177923b6e73f12f0ab067c9ce8866755e3c82abb39c9863cde74fa80b32520bd7dd0eb156c30c08911503b67b2661f1264d09bb231423 + +PrivateKey=ALICE_zero_wap-wsg-idm-ecid-wtls7 +-----BEGIN PRIVATE KEY----- +MDMCAQAwEAYHKoZIzj0CAQYFZysBBAcEHDAaAgEBBBUAoGng7WzYr4P9vtdc3BS/UiNWmc0= +-----END PRIVATE KEY----- + +PublicKey=BOB_zero_wap-wsg-idm-ecid-wtls7_PUB +-----BEGIN PUBLIC KEY----- +MD4wEAYHKoZIzj0CAQYFZysBBAcDKgAEAAAAAAAAAAAAAAAAAAAAAAAAAAAZtSBSZqfmXp47v5z2 +ZZZl2JFxDg== +-----END PUBLIC KEY----- + +# ECDH Alice with Bob peer +Derive=ALICE_zero_wap-wsg-idm-ecid-wtls7 +PeerKey=BOB_zero_wap-wsg-idm-ecid-wtls7_PUB +SharedSecret=6582fc03bbb340fcf24a5fe8fcdf722655efa8b9 + +# tests: 14 -- 2.25.1