projects / openssl.git / commitdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | patch | inline | side by side (parent: e97be71)
Replace GFp ladder implementation with ladd-2002-it-4 from EFD
authorNicola Tuveri <nic.tuv@gmail.com>
Fri, 17 Aug 2018 20:00:44 +0000 (23:00 +0300)
committerMatt Caswell <matt@openssl.org>
Tue, 21 Aug 2018 08:51:18 +0000 (09:51 +0100)
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 <bbrumley@gmail.com>
Reviewed-by: Andy Polyakov <appro@openssl.org>
Reviewed-by: Tim Hudson <tjh@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/7000)

crypto/ec/ecp_smpl.c patch | blob | history
test/recipes/30-test_evp_data/evppkey_ecc.txt patch | blob | history

diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c
index 7ac519ca03efe86ac8b8056082b0f0ada9d8560f..d0c5557ff4ddaf52c2d7389d7114a0abf012377a 100644 (file)
--- 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 685af179948bd0d58e5ea8dd098e110a4acc28ec..8e95c023496386dc844a1b4d0d711104532ada8d 100644 (file)
--- 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
Unnamed repository; edit this file 'description' to name the repository.