1 /** 2 * Licensed under the Apache License, Version 2.0 (the "License"); 3 * you may not use this file except in compliance with the License. 4 * You may obtain a copy of the License at 5 * 6 * http://www.apache.org/licenses/LICENSE-2.0 7 * 8 * Unless required by applicable law or agreed to in writing, software 9 * distributed under the License is distributed on an "AS IS" BASIS, 10 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 * See the License for the specific language governing permissions and 12 * limitations under the License. 13 */ 14 package com.google.security.wycheproof; 15 16 import static org.junit.Assert.assertEquals; 17 import static org.junit.Assert.assertTrue; 18 import static org.junit.Assert.fail; 19 20 import com.google.security.wycheproof.WycheproofRunner.NoPresubmitTest; 21 import com.google.security.wycheproof.WycheproofRunner.ProviderType; 22 import com.google.security.wycheproof.WycheproofRunner.SlowTest; 23 import java.lang.management.ManagementFactory; 24 import java.lang.management.ThreadMXBean; 25 import java.math.BigInteger; 26 import java.security.GeneralSecurityException; 27 import java.security.InvalidKeyException; 28 import java.security.KeyFactory; 29 import java.security.KeyPair; 30 import java.security.KeyPairGenerator; 31 import java.security.NoSuchAlgorithmException; 32 import java.security.PrivateKey; 33 import java.security.PublicKey; 34 import java.security.SecureRandom; 35 import java.security.interfaces.ECPrivateKey; 36 import java.security.interfaces.ECPublicKey; 37 import java.security.spec.ECFieldFp; 38 import java.security.spec.ECGenParameterSpec; 39 import java.security.spec.ECParameterSpec; 40 import java.security.spec.ECPoint; 41 import java.security.spec.ECPrivateKeySpec; 42 import java.security.spec.ECPublicKeySpec; 43 import java.security.spec.EllipticCurve; 44 import java.security.spec.InvalidKeySpecException; 45 import java.security.spec.X509EncodedKeySpec; 46 import javax.crypto.KeyAgreement; 47 import org.junit.Test; 48 import org.junit.runner.RunWith; 49 import org.junit.runners.JUnit4; 50 51 /** 52 * Testing ECDH. 53 * 54 * <p><b>Defense in depth</b>: The tests for ECDH assume that a attacker has control over all 55 * aspects of the public key in an exchange. That means that the attacker can potentially send weak 56 * or invalid public keys. For example, invalid public keys can contain points not on the curve, 57 * curves that have been deliberately chosen so that DLs are easy to compute as well as orders or 58 * cofactors that are wrong. It is expected that implementations validate the inputs of a key 59 * agreement and that in no case information about the private key is leaked. 60 * 61 * <p><b>References:</b> Ingrid Biehl, Bernd Meyer, Volker Müller, "Differential Fault Attacks on 62 * Elliptic Curve Cryptosystems", Crypto '00, pp. 131-164 63 * 64 * <p>Adrian Antipa, Daniel Brown, Alfred Menezes, Rene Struik, and Scott Vanstone, "Validation of 65 * Elliptic Curve Public Keys", PKC 2003, https://www.iacr.org/archive/pkc2003/25670211/25670211.pdf 66 * 67 * <p><b>Bugs:</b> CVE-2015-7940: BouncyCastle before 1.51 does not validate a point is on the 68 * curve. BouncyCastle v.1.52 checks that the public key point is on the public key curve but does 69 * not check whether public key and private key use the same curve. BouncyCastle v.1.53 is still 70 * vulnerable to attacks with modified public keys. An attacker can change the order of the curve 71 * used by the public key. ECDHC would then reduce the private key modulo this order, which can be 72 * used to find the private key. 73 * 74 * <p>CVE-2015-6924: Utimaco HSMs vulnerable to invalid curve attacks, which made the private key 75 * extraction possible. 76 * 77 * <p>CVE-2015-7940: Issue with elliptic curve addition in mixed Jacobian-affine coordinates 78 * 79 * @author bleichen@google.com (Daniel Bleichenbacher) 80 */ 81 // TODO(bleichen): Stuff we haven't implemented: 82 // - timing attacks 83 // Stuff we are delaying because there are more important bugs: 84 // - testWrongOrder using BouncyCastle with ECDHWithSHA1Kdf throws 85 // java.lang.UnsupportedOperationException: KDF can only be used when algorithm is known 86 // Not sure if that is expected or another bug. 87 // CVEs for ECDH we haven't used anywhere. 88 // - CVE-2014-3470: OpenSSL anonymous ECDH denial of service: triggered by NULL value in 89 // certificate. 90 // - CVE-2014-3572: OpenSSL downgrades ECDHE to ECDH 91 // - CVE-2011-3210: OpenSSL was not thread safe 92 @RunWith(JUnit4.class) 93 public class EcdhTest { 94 95 static final String[] ECDH_VARIANTS = { 96 // Raw ECDH. The shared secret is the x-coordinate of the ECDH computation. 97 // The tests below assume that this variant is implemenented. 98 "ECDH", 99 // ECDHC is a variant described in P1363 7.2.2 ECSVDP-DHC. 100 // BouncyCastle implements this variant. 101 "ECDHC", 102 // A variant with an explicit key derivation function. 103 // This is implemented by BouncyCastle. 104 "ECDHWITHSHA1KDF", 105 }; 106 107 /** Test vectors */ 108 public static class EcPublicKeyTestVector { 109 final String comment; 110 final String encoded; // hexadecimal representation of the X509 encoding 111 final BigInteger p; // characteristic of the field 112 final BigInteger n; // order of the subgroup 113 final BigInteger a; // parameter a of the Weierstrass representation 114 final BigInteger b; // parameter b of the Weierstrass represnetation 115 final BigInteger gx; // x-coordinate of the generator 116 final BigInteger gy; // y-coordainat of the generator 117 final Integer h; // cofactor: may be null 118 final BigInteger pubx; // x-coordinate of the public point 119 final BigInteger puby; // y-coordinate of the public point 120 EcPublicKeyTestVector( String comment, String encoded, BigInteger p, BigInteger n, BigInteger a, BigInteger b, BigInteger gx, BigInteger gy, Integer h, BigInteger pubx, BigInteger puby)121 public EcPublicKeyTestVector( 122 String comment, 123 String encoded, 124 BigInteger p, 125 BigInteger n, 126 BigInteger a, 127 BigInteger b, 128 BigInteger gx, 129 BigInteger gy, 130 Integer h, 131 BigInteger pubx, 132 BigInteger puby) { 133 this.comment = comment; 134 this.encoded = encoded; 135 this.p = p; 136 this.n = n; 137 this.a = a; 138 this.b = b; 139 this.gx = gx; 140 this.gy = gy; 141 this.h = h; 142 this.pubx = pubx; 143 this.puby = puby; 144 } 145 146 /** 147 * Returns this key as ECPublicKeySpec or null if the key cannot be represented as 148 * ECPublicKeySpec. The later happens for example if the order of cofactor are not positive. 149 */ getSpec()150 public ECPublicKeySpec getSpec() { 151 try { 152 ECFieldFp fp = new ECFieldFp(p); 153 EllipticCurve curve = new EllipticCurve(fp, a, b); 154 ECPoint g = new ECPoint(gx, gy); 155 // ECParameterSpec requires that the cofactor h is specified. 156 if (h == null) { 157 return null; 158 } 159 ECParameterSpec params = new ECParameterSpec(curve, g, n, h); 160 ECPoint pubPoint = new ECPoint(pubx, puby); 161 ECPublicKeySpec pub = new ECPublicKeySpec(pubPoint, params); 162 return pub; 163 } catch (Exception ex) { 164 System.out.println(comment + " throws " + ex.toString()); 165 return null; 166 } 167 } 168 getX509EncodedKeySpec()169 public X509EncodedKeySpec getX509EncodedKeySpec() { 170 return new X509EncodedKeySpec(TestUtil.hexToBytes(encoded)); 171 } 172 } 173 174 public static final EcPublicKeyTestVector EC_VALID_PUBLIC_KEY = 175 new EcPublicKeyTestVector( 176 "unmodified", 177 "3059301306072a8648ce3d020106082a8648ce3d03010703420004cdeb39edd0" 178 + "3e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b84" 179 + "29598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 180 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 181 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 182 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 183 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 184 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 185 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16), 186 1, 187 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 188 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)); 189 190 public static final EcPublicKeyTestVector[] EC_MODIFIED_PUBLIC_KEYS = { 191 // Modified keys 192 new EcPublicKeyTestVector( 193 "public point not on curve", 194 "3059301306072a8648ce3d020106082a8648ce3d03010703420004cdeb39edd0" 195 + "3e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b84" 196 + "29598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebaca", 197 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 198 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 199 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 200 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 201 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 202 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16), 203 1, 204 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 205 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebaca", 16)), 206 new EcPublicKeyTestVector( 207 "public point = (0,0)", 208 "3059301306072a8648ce3d020106082a8648ce3d030107034200040000000000" 209 + "0000000000000000000000000000000000000000000000000000000000000000" 210 + "000000000000000000000000000000000000000000000000000000", 211 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 212 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 213 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 214 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 215 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 216 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16), 217 1, 218 new BigInteger("0"), 219 new BigInteger("0")), 220 new EcPublicKeyTestVector( 221 "order = 1", 222 "308201133081cc06072a8648ce3d02013081c0020101302c06072a8648ce3d01" 223 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 224 + "ffffffff30440420ffffffff00000001000000000000000000000000ffffffff" 225 + "fffffffffffffffc04205ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53" 226 + "b0f63bce3c3e27d2604b0441046b17d1f2e12c4247f8bce6e563a440f277037d" 227 + "812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33" 228 + "576b315ececbb6406837bf51f502010102010103420004cdeb39edd03e2b1a11" 229 + "a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b8429598c0b" 230 + "49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 231 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 232 new BigInteger("01", 16), 233 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 234 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 235 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 236 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16), 237 1, 238 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 239 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)), 240 new EcPublicKeyTestVector( 241 "order = 26959946660873538060741835960514744168612397095220107664918121663170", 242 "3082012f3081e806072a8648ce3d02013081dc020101302c06072a8648ce3d01" 243 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 244 + "ffffffff30440420ffffffff00000001000000000000000000000000ffffffff" 245 + "fffffffffffffffc04205ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53" 246 + "b0f63bce3c3e27d2604b0441046b17d1f2e12c4247f8bce6e563a440f277037d" 247 + "812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33" 248 + "576b315ececbb6406837bf51f5021d00ffffffff00000000ffffffffffffffff" 249 + "bce6faada7179e84f3b9cac202010103420004cdeb39edd03e2b1a11a5e134ec" 250 + "99d5f25f21673d403f3ecb47bd1fa676638958ea58493b8429598c0b49bbb85c" 251 + "3303ddb1553c3b761c2caacca71606ba9ebac8", 252 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 253 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2", 16), 254 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 255 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 256 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 257 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16), 258 1, 259 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 260 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)), 261 new EcPublicKeyTestVector( 262 "generator = (0,0)", 263 "308201333081ec06072a8648ce3d02013081e0020101302c06072a8648ce3d01" 264 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 265 + "ffffffff30440420ffffffff00000001000000000000000000000000ffffffff" 266 + "fffffffffffffffc04205ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53" 267 + "b0f63bce3c3e27d2604b04410400000000000000000000000000000000000000" 268 + "0000000000000000000000000000000000000000000000000000000000000000" 269 + "00000000000000000000000000022100ffffffff00000000ffffffffffffffff" 270 + "bce6faada7179e84f3b9cac2fc63255102010103420004cdeb39edd03e2b1a11" 271 + "a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b8429598c0b" 272 + "49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 273 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 274 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 275 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 276 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 277 new BigInteger("0"), 278 new BigInteger("0"), 279 1, 280 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 281 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)), 282 new EcPublicKeyTestVector( 283 "generator not on curve", 284 "308201333081ec06072a8648ce3d02013081e0020101302c06072a8648ce3d01" 285 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 286 + "ffffffff30440420ffffffff00000001000000000000000000000000ffffffff" 287 + "fffffffffffffffc04205ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53" 288 + "b0f63bce3c3e27d2604b0441046b17d1f2e12c4247f8bce6e563a440f277037d" 289 + "812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33" 290 + "576b315ececbb6406837bf51f7022100ffffffff00000000ffffffffffffffff" 291 + "bce6faada7179e84f3b9cac2fc63255102010103420004cdeb39edd03e2b1a11" 292 + "a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b8429598c0b" 293 + "49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 294 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 295 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 296 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 297 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 298 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 299 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f7", 16), 300 1, 301 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 302 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)), 303 new EcPublicKeyTestVector( 304 "cofactor = 2", 305 "308201333081ec06072a8648ce3d02013081e0020101302c06072a8648ce3d01" 306 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 307 + "ffffffff30440420ffffffff00000001000000000000000000000000ffffffff" 308 + "fffffffffffffffc04205ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53" 309 + "b0f63bce3c3e27d2604b0441046b17d1f2e12c4247f8bce6e563a440f277037d" 310 + "812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33" 311 + "576b315ececbb6406837bf51f5022100ffffffff00000000ffffffffffffffff" 312 + "bce6faada7179e84f3b9cac2fc63255102010203420004cdeb39edd03e2b1a11" 313 + "a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b8429598c0b" 314 + "49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 315 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 316 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 317 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 318 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 319 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 320 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16), 321 2, 322 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 323 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)), 324 new EcPublicKeyTestVector( 325 "cofactor = None", 326 "308201303081e906072a8648ce3d02013081dd020101302c06072a8648ce3d01" 327 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 328 + "ffffffff30440420ffffffff00000001000000000000000000000000ffffffff" 329 + "fffffffffffffffc04205ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53" 330 + "b0f63bce3c3e27d2604b0441046b17d1f2e12c4247f8bce6e563a440f277037d" 331 + "812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33" 332 + "576b315ececbb6406837bf51f5022100ffffffff00000000ffffffffffffffff" 333 + "bce6faada7179e84f3b9cac2fc63255103420004cdeb39edd03e2b1a11a5e134" 334 + "ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b8429598c0b49bbb8" 335 + "5c3303ddb1553c3b761c2caacca71606ba9ebac8", 336 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 337 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 338 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 339 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 340 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 341 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16), 342 null, 343 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 344 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)), 345 new EcPublicKeyTestVector( 346 "modified prime", 347 "308201333081ec06072a8648ce3d02013081e0020101302c06072a8648ce3d01" 348 + "01022100fd091059a6893635f900e9449d63f572b2aebc4cff7b4e5e33f1b200" 349 + "e8bbc1453044042002f6efa55976c9cb06ff16bb629c0a8d4d5143b40084b1a1" 350 + "cc0e4dff17443eb704205ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53" 351 + "b0f63bce3c3e27d2604b0441040000000000000000000006597fa94b1fd90000" 352 + "000000000000000000000000021b8c7dd77f9a95627922eceefea73f028f1ec9" 353 + "5ba9b8fa95a3ad24bdf9fff414022100ffffffff00000000ffffffffffffffff" 354 + "bce6faada7179e84f3b9cac2fc63255102010103420004000000000000000000" 355 + "0006597fa94b1fd90000000000000000000000000000021b8c7dd77f9a956279" 356 + "22eceefea73f028f1ec95ba9b8fa95a3ad24bdf9fff414", 357 new BigInteger("fd091059a6893635f900e9449d63f572b2aebc4cff7b4e5e33f1b200e8bbc145", 16), 358 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 359 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 360 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 361 new BigInteger("06597fa94b1fd9000000000000000000000000000002", 16), 362 new BigInteger("1b8c7dd77f9a95627922eceefea73f028f1ec95ba9b8fa95a3ad24bdf9fff414", 16), 363 1, 364 new BigInteger("06597fa94b1fd9000000000000000000000000000002", 16), 365 new BigInteger("1b8c7dd77f9a95627922eceefea73f028f1ec95ba9b8fa95a3ad24bdf9fff414", 16)), 366 new EcPublicKeyTestVector( 367 "using secp224r1", 368 "304e301006072a8648ce3d020106052b81040021033a0004074f56dc2ea648ef" 369 + "89c3b72e23bbd2da36f60243e4d2067b70604af1c2165cec2f86603d60c8a611" 370 + "d5b84ba3d91dfe1a480825bcc4af3bcf", 371 new BigInteger("ffffffffffffffffffffffffffffffff000000000000000000000001", 16), 372 new BigInteger("ffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d", 16), 373 new BigInteger("fffffffffffffffffffffffffffffffefffffffffffffffffffffffe", 16), 374 new BigInteger("b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4", 16), 375 new BigInteger("b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21", 16), 376 new BigInteger("bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34", 16), 377 1, 378 new BigInteger("074f56dc2ea648ef89c3b72e23bbd2da36f60243e4d2067b70604af1", 16), 379 new BigInteger("c2165cec2f86603d60c8a611d5b84ba3d91dfe1a480825bcc4af3bcf", 16)), 380 new EcPublicKeyTestVector( 381 "a = 0", 382 "308201143081cd06072a8648ce3d02013081c1020101302c06072a8648ce3d01" 383 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 384 + "ffffffff30250401000420f104880c3980129c7efa19b6b0cb04e547b8d0fc0b" 385 + "95f4946496dd4ac4a7c440044104cdeb39edd03e2b1a11a5e134ec99d5f25f21" 386 + "673d403f3ecb47bd1fa676638958ea58493b8429598c0b49bbb85c3303ddb155" 387 + "3c3b761c2caacca71606ba9ebac8022100ffffffff00000000ffffffffffffff" 388 + "ffbce6faada7179e84f3b9cac2fc63255102010103420004cdeb39edd03e2b1a" 389 + "11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b8429598c" 390 + "0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 391 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 392 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 393 new BigInteger("0"), 394 new BigInteger("f104880c3980129c7efa19b6b0cb04e547b8d0fc0b95f4946496dd4ac4a7c440", 16), 395 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 396 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16), 397 1, 398 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 399 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)), 400 new EcPublicKeyTestVector( 401 "new curve with generator of order 3 that is also on secp256r1", 402 "308201333081ec06072a8648ce3d02013081e0020101302c06072a8648ce3d01" 403 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 404 + "ffffffff3044042046dc879a5c2995d0e6f682468ea95791b7bbd0225cfdb251" 405 + "3fb10a737afece170420bea6c109251bfe4acf2eeda7c24c4ab70a1473335dec" 406 + "28b244d4d823d15935e2044104701c05255026aa4630b78fc6b769e388059ab1" 407 + "443cbdd1f8348bedc3be589dc34cfdab998ad27738ae382aa013986ade0f4859" 408 + "2a9a1ae37ca61d25ec5356f1bd022100ffffffff00000000ffffffffffffffff" 409 + "bce6faada7179e84f3b9cac2fc63255102010103420004701c05255026aa4630" 410 + "b78fc6b769e388059ab1443cbdd1f8348bedc3be589dc3b3025465752d88c851" 411 + "c7d55fec679521f0b7a6d665e51c8359e2da13aca90e42", 412 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 413 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 414 new BigInteger("46dc879a5c2995d0e6f682468ea95791b7bbd0225cfdb2513fb10a737afece17", 16), 415 new BigInteger("bea6c109251bfe4acf2eeda7c24c4ab70a1473335dec28b244d4d823d15935e2", 16), 416 new BigInteger("701c05255026aa4630b78fc6b769e388059ab1443cbdd1f8348bedc3be589dc3", 16), 417 new BigInteger("4cfdab998ad27738ae382aa013986ade0f48592a9a1ae37ca61d25ec5356f1bd", 16), 418 1, 419 new BigInteger("701c05255026aa4630b78fc6b769e388059ab1443cbdd1f8348bedc3be589dc3", 16), 420 new BigInteger("b3025465752d88c851c7d55fec679521f0b7a6d665e51c8359e2da13aca90e42", 16)), 421 // Invalid keys 422 new EcPublicKeyTestVector( 423 "order = -1157920892103562487626974469494075735299969552241357603" 424 + "42422259061068512044369", 425 "308201333081ec06072a8648ce3d02013081e0020101302c06072a8648ce3d01" 426 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 427 + "ffffffff30440420ffffffff00000001000000000000000000000000ffffffff" 428 + "fffffffffffffffc04205ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53" 429 + "b0f63bce3c3e27d2604b0441046b17d1f2e12c4247f8bce6e563a440f277037d" 430 + "812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33" 431 + "576b315ececbb6406837bf51f50221ff00000000ffffffff0000000000000000" 432 + "4319055258e8617b0c46353d039cdaaf02010103420004cdeb39edd03e2b1a11" 433 + "a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b8429598c0b" 434 + "49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 435 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 436 new BigInteger( 437 "-115792089210356248762697446949407573529996955224135760342422259061068512044369"), 438 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 439 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 440 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 441 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16), 442 1, 443 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 444 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)), 445 new EcPublicKeyTestVector( 446 "order = 0", 447 "308201133081cc06072a8648ce3d02013081c0020101302c06072a8648ce3d01" 448 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 449 + "ffffffff30440420ffffffff00000001000000000000000000000000ffffffff" 450 + "fffffffffffffffc04205ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53" 451 + "b0f63bce3c3e27d2604b0441046b17d1f2e12c4247f8bce6e563a440f277037d" 452 + "812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33" 453 + "576b315ececbb6406837bf51f502010002010103420004cdeb39edd03e2b1a11" 454 + "a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b8429598c0b" 455 + "49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 456 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 457 new BigInteger("0"), 458 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 459 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 460 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 461 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16), 462 1, 463 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 464 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)), 465 new EcPublicKeyTestVector( 466 "cofactor = -1", 467 "308201333081ec06072a8648ce3d02013081e0020101302c06072a8648ce3d01" 468 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 469 + "ffffffff30440420ffffffff00000001000000000000000000000000ffffffff" 470 + "fffffffffffffffc04205ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53" 471 + "b0f63bce3c3e27d2604b0441046b17d1f2e12c4247f8bce6e563a440f277037d" 472 + "812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33" 473 + "576b315ececbb6406837bf51f5022100ffffffff00000000ffffffffffffffff" 474 + "bce6faada7179e84f3b9cac2fc6325510201ff03420004cdeb39edd03e2b1a11" 475 + "a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b8429598c0b" 476 + "49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 477 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 478 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 479 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 480 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 481 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 482 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16), 483 -1, 484 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 485 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)), 486 new EcPublicKeyTestVector( 487 "cofactor = 0", 488 "308201333081ec06072a8648ce3d02013081e0020101302c06072a8648ce3d01" 489 + "01022100ffffffff00000001000000000000000000000000ffffffffffffffff" 490 + "ffffffff30440420ffffffff00000001000000000000000000000000ffffffff" 491 + "fffffffffffffffc04205ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53" 492 + "b0f63bce3c3e27d2604b0441046b17d1f2e12c4247f8bce6e563a440f277037d" 493 + "812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33" 494 + "576b315ececbb6406837bf51f5022100ffffffff00000000ffffffffffffffff" 495 + "bce6faada7179e84f3b9cac2fc63255102010003420004cdeb39edd03e2b1a11" 496 + "a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958ea58493b8429598c0b" 497 + "49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 498 new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16), 499 new BigInteger("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16), 500 new BigInteger("ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16), 501 new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16), 502 new BigInteger("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16), 503 new BigInteger("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16), 504 0, 505 new BigInteger("cdeb39edd03e2b1a11a5e134ec99d5f25f21673d403f3ecb47bd1fa676638958", 16), 506 new BigInteger("ea58493b8429598c0b49bbb85c3303ddb1553c3b761c2caacca71606ba9ebac8", 16)), 507 }; 508 509 /** Checks that key agreement using ECDH works. */ 510 @Test testBasic()511 public void testBasic() throws Exception { 512 KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); 513 ECGenParameterSpec ecSpec = new ECGenParameterSpec("secp256r1"); 514 keyGen.initialize(ecSpec); 515 KeyPair keyPairA = keyGen.generateKeyPair(); 516 KeyPair keyPairB = keyGen.generateKeyPair(); 517 518 KeyAgreement kaA = KeyAgreement.getInstance("ECDH"); 519 KeyAgreement kaB = KeyAgreement.getInstance("ECDH"); 520 kaA.init(keyPairA.getPrivate()); 521 kaB.init(keyPairB.getPrivate()); 522 kaA.doPhase(keyPairB.getPublic(), true); 523 kaB.doPhase(keyPairA.getPublic(), true); 524 byte[] kAB = kaA.generateSecret(); 525 byte[] kBA = kaB.generateSecret(); 526 assertEquals(TestUtil.bytesToHex(kAB), TestUtil.bytesToHex(kBA)); 527 } 528 529 @NoPresubmitTest( 530 providers = {ProviderType.BOUNCY_CASTLE}, 531 bugs = {"BouncyCastle uses long encoding. Is this a bug?"} 532 ) 533 @Test testEncode()534 public void testEncode() throws Exception { 535 KeyFactory kf = KeyFactory.getInstance("EC"); 536 ECPublicKey valid = (ECPublicKey) kf.generatePublic(EC_VALID_PUBLIC_KEY.getSpec()); 537 assertEquals(TestUtil.bytesToHex(valid.getEncoded()), EC_VALID_PUBLIC_KEY.encoded); 538 } 539 540 @Test testDecode()541 public void testDecode() throws Exception { 542 KeyFactory kf = KeyFactory.getInstance("EC"); 543 ECPublicKey key1 = (ECPublicKey) kf.generatePublic(EC_VALID_PUBLIC_KEY.getSpec()); 544 ECPublicKey key2 = (ECPublicKey) kf.generatePublic(EC_VALID_PUBLIC_KEY.getX509EncodedKeySpec()); 545 ECParameterSpec params1 = key1.getParams(); 546 ECParameterSpec params2 = key2.getParams(); 547 assertEquals(params1.getCofactor(), params2.getCofactor()); 548 assertEquals(params1.getCurve(), params2.getCurve()); 549 assertEquals(params1.getGenerator(), params2.getGenerator()); 550 assertEquals(params1.getOrder(), params2.getOrder()); 551 assertEquals(key1.getW(), key2.getW()); 552 } 553 554 /** 555 * This test modifies the order of group in the public key. A severe bug would be an 556 * implementation that leaks information whether the private key is larger than the order given in 557 * the public key. Also a severe bug would be to reduce the private key modulo the order given in 558 * the public key parameters. 559 */ 560 @SuppressWarnings("InsecureCryptoUsage") testModifiedPublic(String algorithm)561 public void testModifiedPublic(String algorithm) throws Exception { 562 KeyAgreement ka; 563 try { 564 ka = KeyAgreement.getInstance(algorithm); 565 } catch (NoSuchAlgorithmException ex) { 566 System.out.println("testWrongOrder: " + algorithm + " not supported"); 567 return; 568 } 569 KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); 570 keyGen.initialize(EcUtil.getNistP256Params()); 571 ECPrivateKey priv = (ECPrivateKey) keyGen.generateKeyPair().getPrivate(); 572 KeyFactory kf = KeyFactory.getInstance("EC"); 573 ECPublicKey validKey = (ECPublicKey) kf.generatePublic(EC_VALID_PUBLIC_KEY.getSpec()); 574 ka.init(priv); 575 ka.doPhase(validKey, true); 576 String expected = TestUtil.bytesToHex(ka.generateSecret()); 577 for (EcPublicKeyTestVector test : EC_MODIFIED_PUBLIC_KEYS) { 578 try { 579 X509EncodedKeySpec spec = test.getX509EncodedKeySpec(); 580 ECPublicKey modifiedKey = (ECPublicKey) kf.generatePublic(spec); 581 ka.init(priv); 582 ka.doPhase(modifiedKey, true); 583 String shared = TestUtil.bytesToHex(ka.generateSecret()); 584 // The implementation did not notice that the public key was modified. 585 // This is not nice, but at the moment we only fail the test if the 586 // modification was essential for computing the shared secret. 587 // 588 // BouncyCastle v.1.53 fails this test, for ECDHC with modified order. 589 // This implementation reduces the product s*h modulo the order given 590 // in the public key. An attacker who can modify the order of the public key 591 // and who can learn whether such a modification changes the shared secret is 592 // able to learn the private key with a simple binary search. 593 assertEquals("algorithm:" + algorithm + " test:" + test.comment, expected, shared); 594 } catch (GeneralSecurityException ex) { 595 // OK, since the public keys have been modified. 596 System.out.println("testModifiedPublic:" + test.comment + " throws " + ex.toString()); 597 } 598 } 599 } 600 601 /** 602 * This is a similar test as testModifiedPublic. However, this test uses test vectors 603 * ECPublicKeySpec 604 */ 605 @SuppressWarnings("InsecureCryptoUsage") testModifiedPublicSpec(String algorithm)606 public void testModifiedPublicSpec(String algorithm) throws Exception { 607 KeyAgreement ka; 608 try { 609 ka = KeyAgreement.getInstance(algorithm); 610 } catch (NoSuchAlgorithmException ex) { 611 System.out.println("testWrongOrder: " + algorithm + " not supported"); 612 return; 613 } 614 KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); 615 keyGen.initialize(EcUtil.getNistP256Params()); 616 ECPrivateKey priv = (ECPrivateKey) keyGen.generateKeyPair().getPrivate(); 617 KeyFactory kf = KeyFactory.getInstance("EC"); 618 ECPublicKey validKey = (ECPublicKey) kf.generatePublic(EC_VALID_PUBLIC_KEY.getSpec()); 619 ka.init(priv); 620 ka.doPhase(validKey, true); 621 String expected = TestUtil.bytesToHex(ka.generateSecret()); 622 for (EcPublicKeyTestVector test : EC_MODIFIED_PUBLIC_KEYS) { 623 ECPublicKeySpec spec = test.getSpec(); 624 if (spec == null) { 625 // The constructor of EcPublicKeySpec performs some very minor validity checks. 626 // spec == null if one of these validity checks fails. Of course such a failure is OK. 627 continue; 628 } 629 try { 630 ECPublicKey modifiedKey = (ECPublicKey) kf.generatePublic(spec); 631 ka.init(priv); 632 ka.doPhase(modifiedKey, true); 633 String shared = TestUtil.bytesToHex(ka.generateSecret()); 634 // The implementation did not notice that the public key was modified. 635 // This is not nice, but at the moment we only fail the test if the 636 // modification was essential for computing the shared secret. 637 // 638 // BouncyCastle v.1.53 fails this test, for ECDHC with modified order. 639 // This implementation reduces the product s*h modulo the order given 640 // in the public key. An attacker who can modify the order of the public key 641 // and who can learn whether such a modification changes the shared secret is 642 // able to learn the private key with a simple binary search. 643 assertEquals("algorithm:" + algorithm + " test:" + test.comment, expected, shared); 644 } catch (GeneralSecurityException ex) { 645 // OK, since the public keys have been modified. 646 System.out.println("testModifiedPublic:" + test.comment + " throws " + ex.toString()); 647 } 648 } 649 } 650 651 @Test testModifiedPublic()652 public void testModifiedPublic() throws Exception { 653 testModifiedPublic("ECDH"); 654 testModifiedPublic("ECDHC"); 655 } 656 657 @Test testModifiedPublicSpec()658 public void testModifiedPublicSpec() throws Exception { 659 testModifiedPublicSpec("ECDH"); 660 testModifiedPublicSpec("ECDHC"); 661 } 662 663 @SuppressWarnings("InsecureCryptoUsage") testDistinctCurves(String algorithm, ECPrivateKey priv, ECPublicKey pub)664 public void testDistinctCurves(String algorithm, ECPrivateKey priv, ECPublicKey pub) 665 throws Exception { 666 KeyAgreement kaA; 667 try { 668 kaA = KeyAgreement.getInstance(algorithm); 669 } catch (NoSuchAlgorithmException ex) { 670 System.out.println("Algorithm not supported: " + algorithm); 671 return; 672 } 673 byte[] shared; 674 try { 675 kaA.init(priv); 676 kaA.doPhase(pub, true); 677 shared = kaA.generateSecret(); 678 } catch (InvalidKeyException ex) { 679 // This is expected. 680 return; 681 } 682 // Printing some information to determine what might have gone wrong: 683 // E.g., if the generated secret is the same as the x-coordinate of the public key 684 // then it is likely that the ECDH computation was using a fake group with small order. 685 // Such a situation is probably exploitable. 686 // This probably is exploitable. If the curve of the private key was used for the ECDH 687 // then the generated secret and the x-coordinate of the public key are likely 688 // distinct. 689 EllipticCurve pubCurve = pub.getParams().getCurve(); 690 EllipticCurve privCurve = priv.getParams().getCurve(); 691 ECPoint pubW = pub.getW(); 692 System.out.println("testDistinctCurves: algorithm=" + algorithm); 693 System.out.println( 694 "Private key: a=" 695 + privCurve.getA() 696 + " b=" 697 + privCurve.getB() 698 + " p" 699 + EcUtil.getModulus(privCurve)); 700 System.out.println(" s =" + priv.getS()); 701 System.out.println( 702 "Public key: a=" 703 + pubCurve.getA() 704 + " b=" 705 + pubCurve.getB() 706 + " p" 707 + EcUtil.getModulus(pubCurve)); 708 System.out.println(" w = (" + pubW.getAffineX() + ", " + pubW.getAffineY() + ")"); 709 System.out.println( 710 " = (" 711 + pubW.getAffineX().toString(16) 712 + ", " 713 + pubW.getAffineY().toString(16) 714 + ")"); 715 System.out.println("generated shared secret:" + TestUtil.bytesToHex(shared)); 716 fail("Generated secret with distinct Curves using " + algorithm); 717 } 718 719 /** 720 * This test modifies the order of group in the public key. A severe bug would be an 721 * implementation that leaks information whether the private key is larger than the order given in 722 * the public key. Also a severe bug would be to reduce the private key modulo the order given in 723 * the public key parameters. 724 */ 725 // TODO(bleichen): This can be merged with testModifiedPublic once this is fixed. 726 @SuppressWarnings("InsecureCryptoUsage") testWrongOrder(String algorithm, ECParameterSpec spec)727 public void testWrongOrder(String algorithm, ECParameterSpec spec) throws Exception { 728 KeyAgreement ka; 729 try { 730 ka = KeyAgreement.getInstance(algorithm); 731 } catch (NoSuchAlgorithmException ex) { 732 System.out.println("testWrongOrder: " + algorithm + " not supported"); 733 return; 734 } 735 KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); 736 ECPrivateKey priv; 737 ECPublicKey pub; 738 try { 739 keyGen.initialize(spec); 740 priv = (ECPrivateKey) keyGen.generateKeyPair().getPrivate(); 741 pub = (ECPublicKey) keyGen.generateKeyPair().getPublic(); 742 } catch (GeneralSecurityException ex) { 743 // This is OK, since not all provider support Brainpool curves 744 System.out.println("testWrongOrder: could not generate keys for curve"); 745 return; 746 } 747 // Get the shared secret for the unmodified keys. 748 ka.init(priv); 749 ka.doPhase(pub, true); 750 byte[] shared = ka.generateSecret(); 751 // Generate a modified public key. 752 ECParameterSpec modifiedParams = 753 new ECParameterSpec( 754 spec.getCurve(), spec.getGenerator(), spec.getOrder().shiftRight(16), 1); 755 ECPublicKeySpec modifiedPubSpec = new ECPublicKeySpec(pub.getW(), modifiedParams); 756 KeyFactory kf = KeyFactory.getInstance("EC"); 757 ECPublicKey modifiedPub; 758 try { 759 modifiedPub = (ECPublicKey) kf.generatePublic(modifiedPubSpec); 760 } catch (GeneralSecurityException ex) { 761 // The provider does not support non-standard curves or did a validity check. 762 // Both would be correct. 763 System.out.println("testWrongOrder: can't modify order."); 764 return; 765 } 766 byte[] shared2; 767 try { 768 ka.init(priv); 769 ka.doPhase(modifiedPub, true); 770 shared2 = ka.generateSecret(); 771 } catch (GeneralSecurityException ex) { 772 // This is the expected behavior 773 System.out.println("testWrongOrder:" + ex.toString()); 774 return; 775 } 776 // TODO(bleichen): Getting here is already a bug and we might flag this later. 777 // At the moment we are only interested in really bad behavior of a library, that potentially 778 // leaks the secret key. This is the case when the shared secrets are different, since this 779 // suggests that the implementation reduces the multiplier modulo the given order of the curve 780 // or some other behaviour that is dependent on the private key. 781 // An attacker who can check whether a DH computation was done correctly or incorrectly because 782 // of modular reduction, can determine the private key, either by a binary search or by trying 783 // to guess the private key modulo some small "order". 784 // BouncyCastle v.1.53 fails this test, and leaks the private key. 785 System.out.println( 786 "Generated shared secret with a modified order:" 787 + algorithm 788 + "\n" 789 + "expected:" 790 + TestUtil.bytesToHex(shared) 791 + " computed:" 792 + TestUtil.bytesToHex(shared2)); 793 assertEquals( 794 "Algorithm:" + algorithm, TestUtil.bytesToHex(shared), TestUtil.bytesToHex(shared2)); 795 } 796 797 @Test testWrongOrderEcdh()798 public void testWrongOrderEcdh() throws Exception { 799 testWrongOrder("ECDH", EcUtil.getNistP256Params()); 800 testWrongOrder("ECDH", EcUtil.getBrainpoolP256r1Params()); 801 } 802 803 @Test testWrongOrderEcdhc()804 public void testWrongOrderEcdhc() throws Exception { 805 testWrongOrder("ECDHC", EcUtil.getNistP256Params()); 806 testWrongOrder("ECDHC", EcUtil.getBrainpoolP256r1Params()); 807 } 808 809 /** 810 * Tests for the problem detected by CVE-2017-10176. 811 * 812 * <p>Some libraries do not compute P + (-P) correctly and return 2 * P or throw exceptions. When 813 * the library uses addition-subtraction chains for the point multiplication then such cases can 814 * occur for example when the private key is close to the order of the curve. 815 */ testLargePrivateKey(ECParameterSpec spec)816 private void testLargePrivateKey(ECParameterSpec spec) throws Exception { 817 BigInteger order = spec.getOrder(); 818 KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); 819 ECPublicKey pub; 820 try { 821 keyGen.initialize(spec); 822 pub = (ECPublicKey) keyGen.generateKeyPair().getPublic(); 823 } catch (GeneralSecurityException ex) { 824 // curve is not supported 825 return; 826 } 827 KeyFactory kf = KeyFactory.getInstance("EC"); 828 KeyAgreement ka = KeyAgreement.getInstance("ECDH"); 829 for (int i = 1; i <= 64; i++) { 830 BigInteger p1 = BigInteger.valueOf(i); 831 ECPrivateKeySpec spec1 = new ECPrivateKeySpec(p1, spec); 832 ECPrivateKeySpec spec2 = new ECPrivateKeySpec(order.subtract(p1), spec); 833 ka.init(kf.generatePrivate(spec1)); 834 ka.doPhase(pub, true); 835 byte[] shared1 = ka.generateSecret(); 836 ka.init(kf.generatePrivate(spec2)); 837 ka.doPhase(pub, true); 838 byte[] shared2 = ka.generateSecret(); 839 // The private keys p1 and p2 are equivalent, since only the x-coordinate of the 840 // shared point is used to generate the shared secret. 841 assertEquals(TestUtil.bytesToHex(shared1), TestUtil.bytesToHex(shared2)); 842 } 843 } 844 845 @Test testLargePrivateKey()846 public void testLargePrivateKey() throws Exception { 847 testLargePrivateKey(EcUtil.getNistP224Params()); 848 testLargePrivateKey(EcUtil.getNistP256Params()); 849 testLargePrivateKey(EcUtil.getNistP384Params()); 850 // This test failed before CVE-2017-10176 was fixed. 851 testLargePrivateKey(EcUtil.getNistP521Params()); 852 testLargePrivateKey(EcUtil.getBrainpoolP256r1Params()); 853 } 854 855 /** 856 * This test tries to determine whether point multipliplication using two distinct 857 * points leads to distinguishable timings. 858 * 859 * The main goal here is to determine if the attack by Toru Akishita and Tsuyoshi Takagi 860 * in https://www-old.cdc.informatik.tu-darmstadt.de/reports/TR/TI-03-01.zvp.pdf 861 * might be applicable. I.e. one of the points contains a zero value when multiplied 862 * by mul, the other one does not. 863 * 864 * In its current form the test here is quite weak for a number of reasons: 865 * (1) The timing is often noisy, because the test is run as a unit test. 866 * (2) The test is executed with only a small number of input points. 867 * (3) The number of samples is rather low. Running this test with a larger sample 868 * size would detect more timing differences. Unfortunately 869 * (4) The test does not determine if a variable run time is exploitable. For example 870 * if the tested provider uses windowed exponentiation and the special point is 871 * in the precomputation table then timing differences are easy to spot, but more 872 * difficult to exploit and hence additional experiments would be necessary. 873 * 874 * @param spec the specification of the curve 875 * @param p0 This is a special point. I.e. multiplying this point by mul 876 * may lead to a zero value that may be observable. 877 * @param p1 a random point on the curve 878 * @param mul an integer, such that multiplying p0 with this value may lead to a timing 879 * difference 880 * @param privKeySize the size of the private key in bits 881 * @param comment describes the test case 882 */ testTiming(ECParameterSpec spec, ECPoint p0, ECPoint p1, BigInteger mul, int privKeySize, String comment)883 private void testTiming(ECParameterSpec spec, ECPoint p0, ECPoint p1, 884 BigInteger mul, int privKeySize, String comment) throws Exception { 885 ThreadMXBean bean = ManagementFactory.getThreadMXBean(); 886 if (!bean.isCurrentThreadCpuTimeSupported()) { 887 System.out.println("getCurrentThreadCpuTime is not supported. Skipping"); 888 return; 889 } 890 SecureRandom random = new SecureRandom(); 891 int fixedSize = mul.bitLength(); 892 int missingBits = privKeySize - 2 * fixedSize; 893 assertTrue(missingBits > 0); 894 // possible values for tests, minCount: 895 // 1024, 410 896 // 2048, 880 897 // 4096, 1845 898 // 10000, 4682 899 // I.e. these are values, such that doing 'tests' coin flips results in <= minCount heads or 900 // tails with a probability smaller than 2^-32. 901 // 902 // def min_count(n, b=33): 903 // res, sum, k = 1,1,0 904 // bnd = 2**(n-b) 905 // while sum < bnd: 906 // res *= n - k 907 // res //= 1 + k 908 // k += 1 909 // sum += res 910 // return k - 1 911 final int tests = 2048; 912 final int minCount = 880; 913 // the number of measurements done with each point 914 final int repetitions = 8; 915 // the number of warmup experiments that are ignored 916 final int warmup = 8; 917 final int sampleSize = warmup + tests; 918 KeyFactory kf = KeyFactory.getInstance("EC"); 919 PublicKey[] publicKeys = new PublicKey[2]; 920 try { 921 publicKeys[0] = kf.generatePublic(new ECPublicKeySpec(p0, spec)); 922 publicKeys[1] = kf.generatePublic(new ECPublicKeySpec(p1, spec)); 923 } catch (InvalidKeySpecException ex) { 924 // unsupported curve 925 return; 926 } 927 PrivateKey[] privKeys = new PrivateKey[sampleSize]; 928 for (int i = 0; i < sampleSize; i++) { 929 BigInteger m = new BigInteger(missingBits, random); 930 m = mul.shiftLeft(missingBits).add(m); 931 m = m.shiftLeft(fixedSize).add(mul); 932 ECPrivateKeySpec privSpec = new ECPrivateKeySpec(m, spec); 933 privKeys[i] = kf.generatePrivate(privSpec); 934 } 935 KeyAgreement ka = KeyAgreement.getInstance("ECDH"); 936 long[][] timings = new long[2][sampleSize]; 937 for (int i = 0; i < sampleSize; i++) { 938 for (int j = 0; j < 2 * repetitions; j++) { 939 // idx determines which key to use. 940 int idx = (j ^ i) & 1; 941 ka.init(privKeys[i]); 942 long start = bean.getCurrentThreadCpuTime(); 943 ka.doPhase(publicKeys[idx], true); 944 byte[] unused = ka.generateSecret(); 945 long time = bean.getCurrentThreadCpuTime() - start; 946 timings[idx][i] += time; 947 } 948 } 949 for (int i = 0; i < sampleSize; i++) { 950 for (int j = 0; j < 2; j++) { 951 timings[j][i] /= repetitions; 952 } 953 } 954 955 // Performs some statistics. 956 boolean noisy = false; // Set to true, if the timings have a large variance. 957 System.out.println("ECDH timing test:" + comment); 958 double[] avg = new double[2]; 959 double[] var = new double[2]; 960 for (int i = 0; i < 2; i++) { 961 double sum = 0.0; 962 double sumSqr = 0.0; 963 for (int j = warmup; j < sampleSize; j++) { 964 double val = (double) timings[i][j]; 965 sum += val; 966 sumSqr += val * val; 967 } 968 avg[i] = sum / tests; 969 var[i] = (sumSqr - avg[i] * sum) / (tests - 1); 970 double stdDev = Math.sqrt(var[i]); 971 double cv = stdDev / avg[i]; 972 System.out.println("Timing for point " + i + " avg: " + avg[i] + " std dev: " + stdDev 973 + " cv:" + cv); 974 // The ratio 0.05 below is a somewhat arbitrary value that tries to determine if the noise 975 // is too big to detect even larger timing differences. 976 if (cv > 0.05) { 977 noisy = true; 978 } 979 } 980 // Paired Z-test: 981 // The outcome of this value can be significantly influenced by extreme outliers, such 982 // as slow timings because of things like a garbage collection. 983 double sigmas = Math.abs(avg[0] - avg[1]) / Math.sqrt((var[0] + var[1]) / tests); 984 System.out.println("Sigmas: " + sigmas); 985 986 // Pairwise comparison: 987 // this comparison has the property that it compares timings done with the same 988 // private key, hence timing differences from using different addition chain sizes 989 // are ignored. Extreme outliers should not influence the result a lot, as long as the 990 // number of outliers is small. 991 int point0Faster = 0; 992 int equal = 0; 993 for (int i = 0; i < sampleSize; i++) { 994 if (timings[0][i] < timings[1][i]) { 995 point0Faster += 1; 996 } else if (timings[0][i] < timings[1][i]) { 997 equal += 1; 998 } 999 } 1000 point0Faster += equal / 2; 1001 System.out.println("Point 0 multiplication is faster: " + point0Faster); 1002 if (point0Faster < minCount || point0Faster > sampleSize - minCount) { 1003 fail("Timing differences in ECDH computation detected"); 1004 } else if (noisy) { 1005 System.out.println("Timing was too noisy to expect results."); 1006 } 1007 } 1008 1009 @SlowTest(providers = 1010 {ProviderType.BOUNCY_CASTLE, ProviderType.SPONGY_CASTLE, ProviderType.OPENJDK}) 1011 @Test testTimingSecp256r1()1012 public void testTimingSecp256r1() throws Exception { 1013 // edge case for projective coordinates 1014 BigInteger x1 = 1015 new BigInteger("81bfb55b010b1bdf08b8d9d8590087aa278e28febff3b05632eeff09011c5579", 16); 1016 BigInteger y1 = 1017 new BigInteger("732d0e65267ea28b7af8cfcb148936c2af8664cbb4f04e188148a1457400c2a7", 16); 1018 ECPoint p1 = new ECPoint(x1, y1); 1019 // random point 1020 BigInteger x2 = 1021 new BigInteger("8608e36a91f1fba12e4074972af446176b5608c9c58dc318bd0742754c3dcee7", 16); 1022 BigInteger y2 = 1023 new BigInteger("bc2c9ecd44af916ca58d9e3ef1257f698d350ef486eb86137fe69a7375bcc191", 16); 1024 ECPoint p2 = new ECPoint(x2, y2); 1025 testTiming(EcUtil.getNistP256Params(), p1, p2, new BigInteger("2"), 256, "secp256r1"); 1026 } 1027 1028 @SlowTest(providers = 1029 {ProviderType.BOUNCY_CASTLE, ProviderType.SPONGY_CASTLE, ProviderType.OPENJDK}) 1030 @Test testTimingSecp384r1()1031 public void testTimingSecp384r1() throws Exception { 1032 // edge case for projective coordinates 1033 BigInteger x1 = 1034 new BigInteger("7a6fadfee03eb09554f2a04fe08300aca88bb3a46e8f6347bace672cfe427698" 1035 + "8541cef8dc10536a84580215f5f90a3b", 16); 1036 BigInteger y1 = 1037 new BigInteger("6d243d5d9de1cdddd04cbeabdc7a0f6c244391f7cb2d5738fe13c334add4b458" 1038 + "5fef61ffd446db33b39402278713ae78", 16); 1039 ECPoint p1 = new ECPoint(x1, y1); 1040 // random point 1041 BigInteger x2 = 1042 new BigInteger("71f3c57d6a879889e582af2c7c5444b0eb6ba95d88365b21ca9549475273ecdd" 1043 + "3930aa0bebbd1cf084e4049667278602", 16); 1044 BigInteger y2 = 1045 new BigInteger("9dcbc4d843af8944eb4ba018d369b351a9ea0f7b9e3561df2ee218d54e198f7c" 1046 + "837a3abaa41dffd2d2cb771a7599ed9e", 16); 1047 ECPoint p2 = new ECPoint(x2, y2); 1048 testTiming(EcUtil.getNistP384Params(), p1, p2, new BigInteger("2"), 384, "secp384r1"); 1049 } 1050 1051 @SlowTest(providers = 1052 {ProviderType.BOUNCY_CASTLE, ProviderType.SPONGY_CASTLE, ProviderType.OPENJDK}) 1053 @Test testTimingBrainpoolP256r1()1054 public void testTimingBrainpoolP256r1() throws Exception { 1055 // edge case for Jacobian and projective coordinates 1056 BigInteger x1 = 1057 new BigInteger("79838c22d2b8dc9af2e6cf56f8826dc3dfe10fcb17b6aaaf551ee52bef12f826", 16); 1058 BigInteger y1 = 1059 new BigInteger("1e2ed3d453088c8552c6feecf898667bc1e15905002edec6b269feb7bea09d5b", 16); 1060 ECPoint p1 = new ECPoint(x1, y1); 1061 1062 // random point 1063 BigInteger x2 = 1064 new BigInteger("2720b2e821b2ac8209b573bca755a68821e1e09deb580666702570dd527dd4c1", 16); 1065 BigInteger y2 = 1066 new BigInteger("25cdd610243c7e693fad7bd69b43ae3e63e94317c4c6b717d9c8bc3be8c996fb", 16); 1067 ECPoint p2 = new ECPoint(x2, y2); 1068 testTiming(EcUtil.getBrainpoolP256r1Params(), p1, p2, new BigInteger("2"), 255, 1069 "brainpoolP256r1"); 1070 } 1071 } 1072 1073