)]}' { "commit": "a838f9dc7e6cc091237f0acbbe4953104104e815", "tree": "7102783a8ebb8963fb9938a18567f631ca11901f", "parents": [ "66801feb175599a6d1eb3845eb7ce0ca84551fb5" ], "author": { "name": "David Benjamin", "email": "davidben@google.com", "time": "Mon Nov 13 11:58:00 2017 +0800" }, "committer": { "name": "Adam Langley", "email": "agl@google.com", "time": "Wed Nov 22 22:51:40 2017 +0000" }, "message": "Make ECDSA signing 10% faster and plug some timing leaks.\n\nNone of the asymmetric crypto we inherented from OpenSSL is\nconstant-time because of BIGNUM. BIGNUM chops leading zeros off the\nfront of everything, so we end up leaking information about the first\nword, in theory. BIGNUM functions additionally tend to take the full\nrange of inputs and then call into BN_nnmod at various points.\n\nAll our secret values should be acted on in constant-time, but k in\nECDSA is a particularly sensitive value. So, ecdsa_sign_setup, in an\nattempt to mitigate the BIGNUM leaks, would add a couple copies of the\norder.\n\nThis does not work at all. k is used to compute two values: k^-1 and kG.\nThe first operation when computing k^-1 is to call BN_nnmod if k is out\nof range. The entry point to our tuned constant-time curve\nimplementations is to call BN_nnmod if the scalar has too many bits,\nwhich this causes. The result is both corrections are immediately undone\nbut cause us to do more variable-time work in the meantime.\n\nReplace all these computations around k with the word-based functions\nadded in the various preceding CLs. In doing so, replace the BN_mod_mul\ncalls (which internally call BN_nnmod) with Montgomery reduction. We can\navoid taking k^-1 out of Montgomery form, which combines nicely with\nBrian Smith\u0027s trick in 3426d1011946b26ff1bb2fd98a081ba4753c9cc8. Along\nthe way, we avoid some unnecessary mallocs.\n\nBIGNUM still affects the private key itself, as well as the EC_POINTs.\nBut this should hopefully be much better now. Also it\u0027s 10% faster:\n\nBefore:\nDid 15000 ECDSA P-224 signing operations in 1069117us (14030.3 ops/sec)\nDid 18000 ECDSA P-256 signing operations in 1053908us (17079.3 ops/sec)\nDid 1078 ECDSA P-384 signing operations in 1087853us (990.9 ops/sec)\nDid 473 ECDSA P-521 signing operations in 1069835us (442.1 ops/sec)\n\nAfter:\nDid 16000 ECDSA P-224 signing operations in 1064799us (15026.3 ops/sec)\nDid 19000 ECDSA P-256 signing operations in 1007839us (18852.2 ops/sec)\nDid 1078 ECDSA P-384 signing operations in 1079413us (998.7 ops/sec)\nDid 484 ECDSA P-521 signing operations in 1083616us (446.7 ops/sec)\n\nChange-Id: I2a25e90fc99dac13c0616d0ea45e125a4bd8cca1\nReviewed-on: https://boringssl-review.googlesource.com/23075\nReviewed-by: Adam Langley \u003cagl@google.com\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "fae9480885010de8dd667ac4c8cc4e0d546de4bb", "old_mode": 33188, "old_path": "crypto/err/ec.errordata", "new_id": "de8ee6c116ae0cead366edcfe546ec63cdf63f33", "new_mode": 33188, "new_path": "crypto/err/ec.errordata" }, { "type": "modify", "old_id": "8fa8ed240efbd941bf1ecdcad7f33c21328c6ffc", "old_mode": 33188, "old_path": "crypto/fipsmodule/bn/internal.h", "new_id": "75efbfab9cad8b7e299e2368416de8d19c72132d", "new_mode": 33188, "new_path": "crypto/fipsmodule/bn/internal.h" }, { "type": "modify", "old_id": "e081a1194d31837322559633adbd00e366d7abd8", "old_mode": 33188, "old_path": "crypto/fipsmodule/bn/random.c", "new_id": "61499af47c4c117f5243a8145ff4b5316885d96a", "new_mode": 33188, "new_path": "crypto/fipsmodule/bn/random.c" }, { "type": "modify", "old_id": "14c7450753bc25030172a0b0d41881514f4daa6f", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/ec.c", "new_id": "bcf5afc56e142d6be10e5901457b4da7413e1e69", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/ec.c" }, { "type": "modify", "old_id": "8a784977aeb83a2bc67ae73fc9134c89f7c83ee0", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/internal.h", "new_id": "7374e8b57a696363970b12e22fef0bca14f09a3e", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/internal.h" }, { "type": "modify", "old_id": "26a94b9ed668061b2ea2d85dfcdc9e40c35d57b3", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/p224-64.c", "new_id": "ba25d22a782ca01ada2c7d1f475faeb6fbe25826", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/p224-64.c" }, { "type": "modify", "old_id": "04ae56baf7c755b44a62777380cb381d83542071", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/p256-64.c", "new_id": "d4a8ff6815d996b0aa6d3b445667b0f4158cc144", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/p256-64.c" }, { "type": "modify", "old_id": "0004add8871b51f3f9fb1dd682b6e99aad317875", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/p256-x86_64.c", "new_id": "a9b603aebb039685f510c68c821965196b31d664", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/p256-x86_64.c" }, { "type": "modify", "old_id": "842a8fb6631f5888a795ee71467a24257bd96001", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/wnaf.c", "new_id": "e3b6437b6b259a87a25b1dd39882f6b769bbf8fc", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/wnaf.c" }, { "type": "modify", "old_id": "7af35f7c625fae8542eced1be759b5b138773a35", "old_mode": 33188, "old_path": "crypto/fipsmodule/ecdsa/ecdsa.c", "new_id": "90393f33b3702616fe90fea579e4a22eefa719b1", "new_mode": 33188, "new_path": "crypto/fipsmodule/ecdsa/ecdsa.c" }, { "type": "modify", "old_id": "85fdae461d7ff9c5198e0312d99ad728a11aebd6", "old_mode": 33188, "old_path": "include/openssl/bn.h", "new_id": "bb32c2f56516966e136bee029bd9e91706a7d7ac", "new_mode": 33188, "new_path": "include/openssl/bn.h" }, { "type": "modify", "old_id": "dee41b7afec16f8d91adbaf702c623f49a90d149", "old_mode": 33188, "old_path": "include/openssl/ec.h", "new_id": "b34605fd11c0f59f5e975497811b583c2155b682", "new_mode": 33188, "new_path": "include/openssl/ec.h" } ] }