1 /** 2 * @license 3 * Copyright 2016 Google Inc. All rights reserved. 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.security.wycheproof; 18 19 import com.google.security.wycheproof.WycheproofRunner.ProviderType; 20 import com.google.security.wycheproof.WycheproofRunner.SlowTest; 21 // Android-removed: Android doesn't support JMX 22 // import java.lang.management.ManagementFactory; 23 // import java.lang.management.ThreadMXBean; 24 import java.math.BigInteger; 25 import java.security.InvalidAlgorithmParameterException; 26 import java.security.KeyFactory; 27 import java.security.KeyPair; 28 import java.security.KeyPairGenerator; 29 import java.security.MessageDigest; 30 import java.security.Signature; 31 import java.security.SignatureException; 32 import java.security.interfaces.ECPrivateKey; 33 import java.security.interfaces.ECPublicKey; 34 import java.security.spec.ECGenParameterSpec; 35 import java.security.spec.ECParameterSpec; 36 import java.security.spec.ECPoint; 37 import java.security.spec.ECPublicKeySpec; 38 import java.util.Arrays; 39 import junit.framework.TestCase; 40 41 /** 42 * Tests ECDSA against invalid signatures. 43 * 44 * @author bleichen@google.com (Daniel Bleichenbacher) 45 */ 46 // Tested providers: 47 // SunEC: accepts a few alternative encodings and throws run time exceptions. 48 // The implementation does not protect against timing attacks. 49 // BC: accepts alternative encoding, and additional arguments 50 // AndroidOpenSSL: OK 51 // TODO(bleichen): 52 // - CVE-2015-2730: Firefox failed to handle some signatures correctly because of incorrect 53 // point multiplication. (I don't have enough information here.) 54 public class EcdsaTest extends TestCase { 55 // ECDSA-Key1 56 static final String MESSAGE = "Hello"; 57 static final String CURVE = "secp256r1"; 58 static final BigInteger PubX = 59 new BigInteger( 60 "33903964965861532023650245008903090201819051686264021958530366090984128098564"); 61 static final BigInteger PubY = 62 new BigInteger( 63 "113542129898393725739068316260085522189065290079050903091108740065052129055287"); 64 65 // Valid signatures for MESSAGE 66 static final String[] VALID_SIGNATURES = { 67 "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 68 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 69 + "cd59f43260ecce", 70 }; 71 72 /** 73 * The following test vectors contain a valid signature that use alternative BER encoding. 74 * Whether such signatures are accepted as valid or rejected depends on the implementation. 75 * Allowing alternative BER encodings is in many cases benign. However, there are cases where this 76 * kind of signature malleability was a problem. See for example 77 * https://en.bitcoin.it/wiki/Transaction_Malleability 78 */ 79 // NOTE(bleichen): The following test vectors were generated with some python code. 80 // New test vectors should best be done by extending this code. Some of the signatures 81 // can be moved to INVALID_SIGNATURES, when b/31572415 is fixed. 82 static final String[] MODIFIED_SIGNATURES = { 83 // BER:long form encoding of length 84 "308145022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d" 85 + "491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e762" 86 + "85cd59f43260ecce", 87 "304602812100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d" 88 + "491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e762" 89 + "85cd59f43260ecce", 90 "3046022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 91 + "1b39fd2c3f028120747291dd2f3f44af7ace68ea33431d6f94e418c106a6e762" 92 + "85cd59f43260ecce", 93 // BER:length contains leading 0 94 "30820045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" 95 + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 96 + "6285cd59f43260ecce", 97 "30470282002100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" 98 + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 99 + "6285cd59f43260ecce", 100 "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 101 + "1b39fd2c3f02820020747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 102 + "6285cd59f43260ecce", 103 // BER:prepending 0's to integer 104 "30470223000000b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" 105 + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 106 + "6285cd59f43260ecce", 107 "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 108 + "1b39fd2c3f02220000747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 109 + "6285cd59f43260ecce", 110 // NOTE (bleichen): belongs into INVALID_SIGNATURES. We only keep these 111 // sigantures here because of b/31572415. 112 // length = 2**31 - 1 113 "30847fffffff022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" 114 + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" 115 + "a6e76285cd59f43260ecce", 116 "304902847fffffff00b7babae9332b54b8a3a05b7004579821a887a1b21465f7" 117 + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" 118 + "a6e76285cd59f43260ecce", 119 "3049022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 120 + "1b39fd2c3f02847fffffff747291dd2f3f44af7ace68ea33431d6f94e418c106" 121 + "a6e76285cd59f43260ecce", 122 }; 123 124 /** 125 * Test vectors with invalid signatures. 126 * The motivation for these test vectors are previously broken implementations. E.g. 127 * <ul> 128 * <li> The implementation of DSA in gpg4browsers accepted signatures with r=1 and s=q as valid. 129 * Similar bugs in ECDSA are thinkable, hence the test vectors contain a number of tests with 130 * edge case integers. 131 * <li> CVE-2013-2944: strongSwan 5.0.4 accepts invalid ECDSA signatures when openssl is used. 132 * (Not sure if the following interpretation is correct, because of missing details). 133 * OpenSSLs error codes are easy to misinterpret. For many functions 134 * the result can be 0 (verification failed), 1 (verification succeded) 135 * or -1 (invalid format). A simple <code>if (result) { ... }</code> will be incorrect in 136 * such situations. The test vectors below contain incorrectly encoded signatures. 137 * </ul> 138 * <p> {@link java.security.Signature#verify(byte[])} should either return false or throw a 139 * SignatureException. Other behaviour such as throwing a RuntimeException might allow a denial 140 * of service attack: 141 * <ul> 142 * <li> CVE-2016-5546: OpenJDK8 throwed an OutOfmemoryError on some signatures. 143 * </ul> 144 * Some of the test vectors were derived from a valid signature by corrupting the DER encoding. 145 * If providers accepts such modified signatures for legacy purpose, then these signatures 146 * should be moved to MODIFIED_SIGNATURES. 147 */ 148 // NOTE(bleichen): The following test vectors were generated with some python code. New test 149 // vectors should best be done by extending the python code. 150 static final String[] INVALID_SIGNATURES = { 151 // wrong length 152 "3046022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 153 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 154 + "cd59f43260ecce", 155 "3044022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 156 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 157 + "cd59f43260ecce", 158 "3045022200b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 159 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 160 + "cd59f43260ecce", 161 "3045022000b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 162 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 163 + "cd59f43260ecce", 164 "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 165 + "1b39fd2c3f0221747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 166 + "cd59f43260ecce", 167 "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 168 + "1b39fd2c3f021f747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 169 + "cd59f43260ecce", 170 // uint32 overflow in length 171 "30850100000045022100b7babae9332b54b8a3a05b7004579821a887a1b21465" 172 + "f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c1" 173 + "06a6e76285cd59f43260ecce", 174 "304a0285010000002100b7babae9332b54b8a3a05b7004579821a887a1b21465" 175 + "f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c1" 176 + "06a6e76285cd59f43260ecce", 177 "304a022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 178 + "1b39fd2c3f02850100000020747291dd2f3f44af7ace68ea33431d6f94e418c1" 179 + "06a6e76285cd59f43260ecce", 180 // uint64 overflow in length 181 "3089010000000000000045022100b7babae9332b54b8a3a05b7004579821a887" 182 + "a1b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f" 183 + "94e418c106a6e76285cd59f43260ecce", 184 "304e028901000000000000002100b7babae9332b54b8a3a05b7004579821a887" 185 + "a1b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f" 186 + "94e418c106a6e76285cd59f43260ecce", 187 "304e022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 188 + "1b39fd2c3f0289010000000000000020747291dd2f3f44af7ace68ea33431d6f" 189 + "94e418c106a6e76285cd59f43260ecce", 190 // length = 2**32 - 1 191 "3084ffffffff022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" 192 + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" 193 + "a6e76285cd59f43260ecce", 194 "30490284ffffffff00b7babae9332b54b8a3a05b7004579821a887a1b21465f7" 195 + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" 196 + "a6e76285cd59f43260ecce", 197 "3049022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 198 + "1b39fd2c3f0284ffffffff747291dd2f3f44af7ace68ea33431d6f94e418c106" 199 + "a6e76285cd59f43260ecce", 200 // length = 2**64 - 1 201 "3088ffffffffffffffff022100b7babae9332b54b8a3a05b7004579821a887a1" 202 + "b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94" 203 + "e418c106a6e76285cd59f43260ecce", 204 "304d0288ffffffffffffffff00b7babae9332b54b8a3a05b7004579821a887a1" 205 + "b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94" 206 + "e418c106a6e76285cd59f43260ecce", 207 "304d022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 208 + "1b39fd2c3f0288ffffffffffffffff747291dd2f3f44af7ace68ea33431d6f94" 209 + "e418c106a6e76285cd59f43260ecce", 210 // removing sequence 211 "", 212 // appending 0's to sequence 213 "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 214 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 215 + "cd59f43260ecce0000", 216 // prepending 0's to sequence 217 "30470000022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" 218 + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 219 + "6285cd59f43260ecce", 220 // appending unused 0's 221 "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 222 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 223 + "cd59f43260ecce0000", 224 "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 225 + "1b39fd2c3f00000220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 226 + "6285cd59f43260ecce", 227 // appending null value 228 "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 229 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 230 + "cd59f43260ecce0500", 231 "3047022300b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 232 + "1b39fd2c3f05000220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 233 + "6285cd59f43260ecce", 234 "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 235 + "1b39fd2c3f0222747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 236 + "cd59f43260ecce0500", 237 // including garbage 238 "304949803045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" 239 + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" 240 + "a6e76285cd59f43260ecce", 241 "304925003045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" 242 + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" 243 + "a6e76285cd59f43260ecce", 244 "30473045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" 245 + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 246 + "6285cd59f43260ecce0004deadbeef", 247 "304922254980022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" 248 + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" 249 + "a6e76285cd59f43260ecce", 250 "304922252500022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" 251 + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" 252 + "a6e76285cd59f43260ecce", 253 "304d2223022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" 254 + "3d491b39fd2c3f0004deadbeef0220747291dd2f3f44af7ace68ea33431d6f94" 255 + "e418c106a6e76285cd59f43260ecce", 256 "3049022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 257 + "1b39fd2c3f222449800220747291dd2f3f44af7ace68ea33431d6f94e418c106" 258 + "a6e76285cd59f43260ecce", 259 "3049022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 260 + "1b39fd2c3f222425000220747291dd2f3f44af7ace68ea33431d6f94e418c106" 261 + "a6e76285cd59f43260ecce", 262 "304d022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 263 + "1b39fd2c3f22220220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 264 + "6285cd59f43260ecce0004deadbeef", 265 // including undefined tags 266 "304daa00bb00cd003045022100b7babae9332b54b8a3a05b7004579821a887a1" 267 + "b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94" 268 + "e418c106a6e76285cd59f43260ecce", 269 "304baa02aabb3045022100b7babae9332b54b8a3a05b7004579821a887a1b214" 270 + "65f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418" 271 + "c106a6e76285cd59f43260ecce", 272 "304d2229aa00bb00cd00022100b7babae9332b54b8a3a05b7004579821a887a1" 273 + "b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94" 274 + "e418c106a6e76285cd59f43260ecce", 275 "304b2227aa02aabb022100b7babae9332b54b8a3a05b7004579821a887a1b214" 276 + "65f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418" 277 + "c106a6e76285cd59f43260ecce", 278 "304d022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 279 + "1b39fd2c3f2228aa00bb00cd000220747291dd2f3f44af7ace68ea33431d6f94" 280 + "e418c106a6e76285cd59f43260ecce", 281 "304b022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 282 + "1b39fd2c3f2226aa02aabb0220747291dd2f3f44af7ace68ea33431d6f94e418" 283 + "c106a6e76285cd59f43260ecce", 284 // changing tag value 285 "2e45022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 286 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 287 + "cd59f43260ecce", 288 "3245022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 289 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 290 + "cd59f43260ecce", 291 "ff45022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 292 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 293 + "cd59f43260ecce", 294 "3045002100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 295 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 296 + "cd59f43260ecce", 297 "3045042100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 298 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 299 + "cd59f43260ecce", 300 "3045ff2100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 301 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 302 + "cd59f43260ecce", 303 "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 304 + "1b39fd2c3f0020747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 305 + "cd59f43260ecce", 306 "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 307 + "1b39fd2c3f0420747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 308 + "cd59f43260ecce", 309 "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 310 + "1b39fd2c3fff20747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 311 + "cd59f43260ecce", 312 // dropping value of sequence 313 "3000", 314 // using composition 315 "304930010230442100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" 316 + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" 317 + "a6e76285cd59f43260ecce", 318 "304922250201000220b7babae9332b54b8a3a05b7004579821a887a1b21465f7" 319 + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" 320 + "a6e76285cd59f43260ecce", 321 "3049022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 322 + "1b39fd2c3f2224020174021f7291dd2f3f44af7ace68ea33431d6f94e418c106" 323 + "a6e76285cd59f43260ecce", 324 // truncate sequence 325 "3044022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 326 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 327 + "cd59f43260ec", 328 "30442100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d491b" 329 + "39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd" 330 + "59f43260ecce", 331 // prepend empty sequence 332 "30473000022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" 333 + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 334 + "6285cd59f43260ecce", 335 // append empty sequence 336 "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 337 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 338 + "cd59f43260ecce3000", 339 // sequence of sequence 340 "30473045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" 341 + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 342 + "6285cd59f43260ecce", 343 // truncated sequence 344 "3023022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d491b39fd2c3f", 345 // repeat element in sequence 346 "3067022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 347 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 348 + "cd59f43260ecce0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 349 + "6285cd59f43260ecce", 350 // removing integer 351 "30220220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd59f43260ecce", 352 // appending 0's to integer 353 "3047022300b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 354 + "1b39fd2c3f00000220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" 355 + "6285cd59f43260ecce", 356 "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 357 + "1b39fd2c3f0222747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 358 + "cd59f43260ecce0000", 359 // dropping value of integer 360 "302402000220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd59f43260ecce", 361 "3025022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d491b39fd2c3f0200", 362 // modify first byte of integer 363 "3045022101b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 364 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 365 + "cd59f43260ecce", 366 "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 367 + "1b39fd2c3f0220757291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 368 + "cd59f43260ecce", 369 // modify last byte of integer 370 "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 371 + "1b39fd2c3e0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 372 + "cd59f43260ecce", 373 "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 374 + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 375 + "cd59f43260eccf", 376 // truncate integer 377 "3044022000b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 378 + "1b39fd2c0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd" 379 + "59f43260ecce", 380 "30440220b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d491b" 381 + "39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd" 382 + "59f43260ecce", 383 "3044022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 384 + "1b39fd2c3f021f747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 385 + "cd59f43260ec", 386 "3044022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 387 + "1b39fd2c3f021f7291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd" 388 + "59f43260ecce", 389 // leading ff in integer 390 "30460222ff00b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d" 391 + "491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e762" 392 + "85cd59f43260ecce", 393 "3046022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 394 + "1b39fd2c3f0221ff747291dd2f3f44af7ace68ea33431d6f94e418c106a6e762" 395 + "85cd59f43260ecce", 396 // infinity 397 "30250901800220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd59f43260ecce", 398 "3026022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d491b39fd2c3f090180", 399 // Vectors where r or s have been modified e.g. by adding or subtracting the order of the 400 // group or field and hence violate the range check for r and s required by ECDSA. 401 "30450221ff48454516ccd4ab475c5fa48ffba867de57785e4deb9a082475c2b6" 402 + "e4c602d3c10220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 403 + "cd59f43260ecce", 404 "3045022101b7babae8332b54b9a3a05b7004579821656e9c5fbb7d96607df713" 405 + "de366051900220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 406 + "cd59f43260ecce", 407 "3044022048454515ccd4ab485c5fa48ffba867de145f58fb92b1a6a9697c81a7" 408 + "c265f9120220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd" 409 + "59f43260ecce", 410 "3045022101b7babae8332b54b9a3a05b7004579821a887a1b31465f7db8a3d49" 411 + "1b39fd2c3e0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" 412 + "cd59f43260ecce", 413 "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 414 + "1b39fd2c3f02208b8d6e22d0c0bb5085319715ccbce2906b1be73ef959189d7a" 415 + "32a60bcd9f1332", 416 "3046022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 417 + "1b39fd2c3f022101747291dc2f3f44b07ace68ea33431d6f51cb136eadbe85e7" 418 + "798724b72ec4121f", 419 "3046022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" 420 + "1b39fd2c3f022101747291dc2f3f44b07ace68ea33431d6f94e418c206a6e762" 421 + "85cd59f43260eccd", 422 // Signatures with special case values for r and s (such as 0 and 1). Such values often 423 // uncover implementation errors. 424 "3006020100020100", 425 "3006020100020101", 426 "30060201000201ff", 427 "3026020100022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 428 "3026020100022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632550", 429 "3026020100022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632552", 430 "3026020100022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 431 "3026020100022100ffffffff00000001000000000000000000000001000000000000000000000000", 432 "3008020100090380fe01", 433 "3006020101020100", 434 "3006020101020101", 435 "30060201010201ff", 436 "3026020101022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 437 "3026020101022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632550", 438 "3026020101022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632552", 439 "3026020101022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 440 "3026020101022100ffffffff00000001000000000000000000000001000000000000000000000000", 441 "3008020101090380fe01", 442 "30060201ff020100", 443 "30060201ff020101", 444 "30060201ff0201ff", 445 "30260201ff022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 446 "30260201ff022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632550", 447 "30260201ff022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632552", 448 "30260201ff022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 449 "30260201ff022100ffffffff00000001000000000000000000000001000000000000000000000000", 450 "30080201ff090380fe01", 451 "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551020100", 452 "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551020101", 453 "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc6325510201ff", 454 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 455 + "c2fc632551022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 456 + "f3b9cac2fc632551", 457 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 458 + "c2fc632551022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 459 + "f3b9cac2fc632550", 460 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 461 + "c2fc632551022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 462 + "f3b9cac2fc632552", 463 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 464 + "c2fc632551022100ffffffff00000001000000000000000000000000ffffffff" 465 + "ffffffffffffffff", 466 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 467 + "c2fc632551022100ffffffff0000000100000000000000000000000100000000" 468 + "0000000000000000", 469 "3028022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 470 + "c2fc632551090380fe01", 471 "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632550020100", 472 "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632550020101", 473 "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc6325500201ff", 474 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 475 + "c2fc632550022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 476 + "f3b9cac2fc632551", 477 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 478 + "c2fc632550022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 479 + "f3b9cac2fc632550", 480 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 481 + "c2fc632550022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 482 + "f3b9cac2fc632552", 483 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 484 + "c2fc632550022100ffffffff00000001000000000000000000000000ffffffff" 485 + "ffffffffffffffff", 486 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 487 + "c2fc632550022100ffffffff0000000100000000000000000000000100000000" 488 + "0000000000000000", 489 "3028022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 490 + "c2fc632550090380fe01", 491 "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632552020100", 492 "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632552020101", 493 "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc6325520201ff", 494 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 495 + "c2fc632552022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 496 + "f3b9cac2fc632551", 497 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 498 + "c2fc632552022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 499 + "f3b9cac2fc632550", 500 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 501 + "c2fc632552022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 502 + "f3b9cac2fc632552", 503 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 504 + "c2fc632552022100ffffffff00000001000000000000000000000000ffffffff" 505 + "ffffffffffffffff", 506 "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 507 + "c2fc632552022100ffffffff0000000100000000000000000000000100000000" 508 + "0000000000000000", 509 "3028022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" 510 + "c2fc632552090380fe01", 511 "3026022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff020100", 512 "3026022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff020101", 513 "3026022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff0201ff", 514 "3046022100ffffffff00000001000000000000000000000000ffffffffffffff" 515 + "ffffffffff022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 516 + "f3b9cac2fc632551", 517 "3046022100ffffffff00000001000000000000000000000000ffffffffffffff" 518 + "ffffffffff022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 519 + "f3b9cac2fc632550", 520 "3046022100ffffffff00000001000000000000000000000000ffffffffffffff" 521 + "ffffffffff022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 522 + "f3b9cac2fc632552", 523 "3046022100ffffffff00000001000000000000000000000000ffffffffffffff" 524 + "ffffffffff022100ffffffff00000001000000000000000000000000ffffffff" 525 + "ffffffffffffffff", 526 "3046022100ffffffff00000001000000000000000000000000ffffffffffffff" 527 + "ffffffffff022100ffffffff0000000100000000000000000000000100000000" 528 + "0000000000000000", 529 "3028022100ffffffff00000001000000000000000000000000ffffffffffffff" 530 + "ffffffffff090380fe01", 531 "3026022100ffffffff00000001000000000000000000000001000000000000000000000000020100", 532 "3026022100ffffffff00000001000000000000000000000001000000000000000000000000020101", 533 "3026022100ffffffff000000010000000000000000000000010000000000000000000000000201ff", 534 "3046022100ffffffff0000000100000000000000000000000100000000000000" 535 + "0000000000022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 536 + "f3b9cac2fc632551", 537 "3046022100ffffffff0000000100000000000000000000000100000000000000" 538 + "0000000000022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 539 + "f3b9cac2fc632550", 540 "3046022100ffffffff0000000100000000000000000000000100000000000000" 541 + "0000000000022100ffffffff00000000ffffffffffffffffbce6faada7179e84" 542 + "f3b9cac2fc632552", 543 "3046022100ffffffff0000000100000000000000000000000100000000000000" 544 + "0000000000022100ffffffff00000001000000000000000000000000ffffffff" 545 + "ffffffffffffffff", 546 "3046022100ffffffff0000000100000000000000000000000100000000000000" 547 + "0000000000022100ffffffff0000000100000000000000000000000100000000" 548 + "0000000000000000", 549 "3028022100ffffffff0000000100000000000000000000000100000000000000" 550 + "0000000000090380fe01", 551 }; 552 553 /** 554 * Determines the Hash name from the ECDSA algorithm. There is a small inconsistency in the naming 555 * of algorithms. The Oracle standard use no hyphen in SHA256WithECDSA but uses a hyphen in the 556 * message digest, i.e., SHA-256. 557 */ getHashAlgorithm(String ecdsaAlgorithm)558 public String getHashAlgorithm(String ecdsaAlgorithm) { 559 ecdsaAlgorithm = ecdsaAlgorithm.toUpperCase(); 560 int idx = ecdsaAlgorithm.indexOf("WITH"); 561 if (idx > 0) { 562 if (ecdsaAlgorithm.startsWith("SHA")) { 563 return "SHA-" + ecdsaAlgorithm.substring(3, idx); 564 } else { 565 return ecdsaAlgorithm.substring(0, idx); 566 } 567 } 568 return ""; 569 } 570 571 /** 572 * Extract the integer r from an ECDSA signature. This method implicitely assumes that the ECDSA 573 * signature is DER encoded. and that the order of the curve is smaller than 2^1024. 574 */ extractR(byte[] signature)575 BigInteger extractR(byte[] signature) throws Exception { 576 int startR = (signature[1] & 0x80) != 0 ? 3 : 2; 577 int lengthR = signature[startR + 1]; 578 return new BigInteger(Arrays.copyOfRange(signature, startR + 2, startR + 2 + lengthR)); 579 } 580 extractS(byte[] signature)581 BigInteger extractS(byte[] signature) throws Exception { 582 int startR = (signature[1] & 0x80) != 0 ? 3 : 2; 583 int lengthR = signature[startR + 1]; 584 int startS = startR + 2 + lengthR; 585 int lengthS = signature[startS + 1]; 586 return new BigInteger(Arrays.copyOfRange(signature, startS + 2, startS + 2 + lengthS)); 587 } 588 589 /** Extract the k that was used to sign the signature. */ extractK(byte[] signature, BigInteger h, ECPrivateKey priv)590 BigInteger extractK(byte[] signature, BigInteger h, ECPrivateKey priv) throws Exception { 591 BigInteger x = priv.getS(); 592 BigInteger n = priv.getParams().getOrder(); 593 BigInteger r = extractR(signature); 594 BigInteger s = extractS(signature); 595 BigInteger k = x.multiply(r).add(h).multiply(s.modInverse(n)).mod(n); 596 return k; 597 } 598 publicKey1()599 public ECPublicKeySpec publicKey1() throws Exception { 600 ECParameterSpec params = EcUtil.getNistP256Params(); 601 ECPoint w = new ECPoint(PubX, PubY); 602 return new ECPublicKeySpec(w, params); 603 } 604 testVectors( String[] signatures, ECPublicKeySpec pubSpec, String message, String algorithm, String signatureType, boolean isValidDER, boolean isValidBER)605 public void testVectors( 606 String[] signatures, 607 ECPublicKeySpec pubSpec, 608 String message, 609 String algorithm, 610 String signatureType, 611 boolean isValidDER, 612 boolean isValidBER) 613 throws Exception { 614 byte[] messageBytes = message.getBytes("UTF-8"); 615 Signature verifier = Signature.getInstance(algorithm); 616 KeyFactory kf = KeyFactory.getInstance("EC"); 617 ECPublicKey pub = (ECPublicKey) kf.generatePublic(pubSpec); 618 int errors = 0; 619 for (String signature : signatures) { 620 byte[] signatureBytes = TestUtil.hexToBytes(signature); 621 verifier.initVerify(pub); 622 verifier.update(messageBytes); 623 boolean verified = false; 624 try { 625 verified = verifier.verify(signatureBytes); 626 } catch (SignatureException ex) { 627 // verify can throw SignatureExceptions if the signature is malformed. 628 // We don't flag these cases and simply consider the signature as invalid. 629 verified = false; 630 } 631 if (!verified && isValidDER) { 632 System.out.println(signatureType + " was not verified:" + signature); 633 errors++; 634 } 635 if (verified && !isValidBER) { 636 System.out.println(signatureType + " was verified:" + signature); 637 errors++; 638 } 639 } 640 assertEquals(0, errors); 641 } 642 testValidSignatures()643 public void testValidSignatures() throws Exception { 644 testVectors( 645 VALID_SIGNATURES, publicKey1(), "Hello", "SHA256WithECDSA", "Valid ECDSA signature", 646 true, true); 647 } 648 testModifiedSignatures()649 public void testModifiedSignatures() throws Exception { 650 testVectors( 651 MODIFIED_SIGNATURES, 652 publicKey1(), 653 "Hello", 654 "SHA256WithECDSA", 655 "Modified ECDSA signature", 656 false, 657 true); 658 } 659 testInvalidSignatures()660 public void testInvalidSignatures() throws Exception { 661 testVectors( 662 INVALID_SIGNATURES, 663 publicKey1(), 664 "Hello", 665 "SHA256WithECDSA", 666 "Invalid ECDSA signature", 667 false, 668 false); 669 } 670 671 /** 672 * This test checks the basic functionality of ECDSA. It can also be used to generate simple test 673 * vectors. 674 */ testBasic()675 public void testBasic() throws Exception { 676 String algorithm = "SHA256WithECDSA"; 677 String hashAlgorithm = "SHA-256"; 678 String message = "Hello"; 679 String curve = "secp256r1"; 680 681 KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); 682 ECGenParameterSpec ecSpec = new ECGenParameterSpec("secp256r1"); 683 keyGen.initialize(ecSpec); 684 KeyPair keyPair = keyGen.generateKeyPair(); 685 ECPublicKey pub = (ECPublicKey) keyPair.getPublic(); 686 ECPrivateKey priv = (ECPrivateKey) keyPair.getPrivate(); 687 688 byte[] messageBytes = message.getBytes("UTF-8"); 689 Signature signer = Signature.getInstance(algorithm); 690 Signature verifier = Signature.getInstance(algorithm); 691 signer.initSign(priv); 692 signer.update(messageBytes); 693 byte[] signature = signer.sign(); 694 verifier.initVerify(pub); 695 verifier.update(messageBytes); 696 assertTrue(verifier.verify(signature)); 697 698 // Extract some parameters. 699 byte[] rawHash = MessageDigest.getInstance(hashAlgorithm).digest(messageBytes); 700 ECParameterSpec params = priv.getParams(); 701 702 // Print keys and signature, so that it can be used to generate new test vectors. 703 System.out.println("Message:" + message); 704 System.out.println("Hash:" + TestUtil.bytesToHex(rawHash)); 705 System.out.println("Curve:" + curve); 706 System.out.println("Order:" + params.getOrder().toString()); 707 System.out.println("Private key:"); 708 System.out.println("S:" + priv.getS().toString()); 709 System.out.println("encoded:" + TestUtil.bytesToHex(priv.getEncoded())); 710 System.out.println("Public key:"); 711 ECPoint w = pub.getW(); 712 System.out.println("X:" + w.getAffineX().toString()); 713 System.out.println("Y:" + w.getAffineY().toString()); 714 System.out.println("encoded:" + TestUtil.bytesToHex(pub.getEncoded())); 715 System.out.println("Signature:" + TestUtil.bytesToHex(signature)); 716 System.out.println("r:" + extractR(signature).toString()); 717 System.out.println("s:" + extractS(signature).toString()); 718 } 719 720 /** Checks whether the one time key k in ECDSA is biased. */ testBias(String algorithm, String curve, ECParameterSpec ecParams)721 public void testBias(String algorithm, String curve, ECParameterSpec ecParams) throws Exception { 722 KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); 723 try { 724 keyGen.initialize(ecParams); 725 } catch (InvalidAlgorithmParameterException ex) { 726 System.out.println("This provider does not support curve:" + curve); 727 return; 728 } 729 KeyPair keyPair = keyGen.generateKeyPair(); 730 ECPrivateKey priv = (ECPrivateKey) keyPair.getPrivate(); 731 // If we throw a fair coin tests times then the probability that 732 // either heads or tails appears less than mincount is less than 2^{-32}. 733 // Therefore the test below is not expected to fail unless the generation 734 // of the one time keys is indeed biased. 735 final int tests = 1024; 736 final int mincount = 410; 737 738 String hashAlgorithm = getHashAlgorithm(algorithm); 739 String message = "Hello"; 740 byte[] messageBytes = message.getBytes("UTF-8"); 741 byte[] digest = MessageDigest.getInstance(hashAlgorithm).digest(messageBytes); 742 743 // TODO(bleichen): Truncate the digest if the digest size is larger than the 744 // curve size. 745 BigInteger h = new BigInteger(1, digest); 746 BigInteger q = priv.getParams().getOrder(); 747 BigInteger qHalf = q.shiftRight(1); 748 749 Signature signer = Signature.getInstance(algorithm); 750 signer.initSign(priv); 751 int countLsb = 0; // count the number of k's with msb set 752 int countMsb = 0; // count the number of k's with lsb set 753 for (int i = 0; i < tests; i++) { 754 signer.update(messageBytes); 755 byte[] signature = signer.sign(); 756 BigInteger k = extractK(signature, h, priv); 757 if (k.testBit(0)) { 758 countLsb++; 759 } 760 if (k.compareTo(qHalf) == 1) { 761 countMsb++; 762 } 763 } 764 System.out.println( 765 signer.getProvider().getName() 766 + " curve:" 767 + curve 768 + " countLsb:" 769 + countLsb 770 + " countMsb:" 771 + countMsb); 772 if (countLsb < mincount || countLsb > tests - mincount) { 773 fail("Bias detected in the least significant bit of k:" + countLsb); 774 } 775 if (countMsb < mincount || countMsb > tests - mincount) { 776 fail("Bias detected in the most significant bit of k:" + countMsb); 777 } 778 } 779 780 @SlowTest(providers = {ProviderType.BOUNCY_CASTLE, ProviderType.CONSCRYPT, ProviderType.OPENJDK, 781 ProviderType.SPONGY_CASTLE}) testBiasAll()782 public void testBiasAll() throws Exception { 783 testBias("SHA256WithECDSA", "secp256r1", EcUtil.getNistP256Params()); 784 testBias("SHA224WithECDSA", "secp224r1", EcUtil.getNistP224Params()); 785 testBias("SHA384WithECDSA", "secp384r1", EcUtil.getNistP384Params()); 786 testBias("SHA512WithECDSA", "secp521r1", EcUtil.getNistP521Params()); 787 testBias("SHA256WithECDSA", "brainpoolP256r1", EcUtil.getBrainpoolP256r1Params()); 788 } 789 790 /** 791 * Tests for a potential timing attack. This test checks if there is a correlation between the 792 * timing of signature generation and the size of the one-time key k. This is for example the case 793 * if a double and add method is used for the point multiplication. The test fails if such a 794 * correlation can be shown with high confidence. Further analysis will be necessary to determine 795 * how easy it is to exploit the bias in a timing attack. 796 */ 797 // TODO(bleichen): Determine if there are exploitable providers. 798 // 799 // SunEC currently fails this test. Since ECDSA typically is used with EC groups whose order 800 // is 224 bits or larger, it is unclear whether the same attacks that apply to DSA are practical. 801 // 802 // The ECDSA implementation in BouncyCastle leaks information about k through timing too. 803 // The test has not been optimized to detect this bias. It would require about 5'000'000 samples, 804 // which is too much for a simple unit test. 805 // 806 // BouncyCastle uses FixedPointCombMultiplier for ECDSA. This is a method using 807 // precomputation. The implementation is not constant time, since the precomputation table 808 // contains the point at infinity and adding this point is faster than ordinary point additions. 809 // The timing leak only has a small correlation to the size of k and at the moment it is is very 810 // unclear if the can be exploited. (Randomizing the precomputation table by adding the same 811 // random point to each element in the table and precomputing the necessary offset to undo the 812 // precomputation seems much easier than analyzing this.) testTiming(String algorithm, String curve, ECParameterSpec ecParams)813 public void testTiming(String algorithm, String curve, ECParameterSpec ecParams) 814 throws Exception { 815 // BEGIN Android-removed: Android doesn't support JMX 816 /* 817 ThreadMXBean bean = ManagementFactory.getThreadMXBean(); 818 if (!bean.isCurrentThreadCpuTimeSupported()) { 819 System.out.println("getCurrentThreadCpuTime is not supported. Skipping"); 820 return; 821 } 822 KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); 823 try { 824 keyGen.initialize(ecParams); 825 } catch (InvalidAlgorithmParameterException ex) { 826 System.out.println("This provider does not support curve:" + curve); 827 return; 828 } 829 KeyPair keyPair = keyGen.generateKeyPair(); 830 ECPrivateKey priv = (ECPrivateKey) keyPair.getPrivate(); 831 832 String message = "Hello"; 833 String hashAlgorithm = getHashAlgorithm(algorithm); 834 byte[] messageBytes = message.getBytes("UTF-8"); 835 byte[] digest = MessageDigest.getInstance(hashAlgorithm).digest(messageBytes); 836 BigInteger h = new BigInteger(1, digest); 837 Signature signer = Signature.getInstance(algorithm); 838 signer.initSign(priv); 839 // The number of samples used for the test. This number is a bit low. 840 // I.e. it just barely detects that SunEC leaks information about the size of k. 841 int samples = 50000; 842 long[] timing = new long[samples]; 843 BigInteger[] k = new BigInteger[samples]; 844 for (int i = 0; i < samples; i++) { 845 long start = bean.getCurrentThreadCpuTime(); 846 signer.update(messageBytes); 847 byte[] signature = signer.sign(); 848 timing[i] = bean.getCurrentThreadCpuTime() - start; 849 k[i] = extractK(signature, h, priv); 850 } 851 long[] sorted = Arrays.copyOf(timing, timing.length); 852 Arrays.sort(sorted); 853 double n = priv.getParams().getOrder().doubleValue(); 854 double expectedAverage = n / 2; 855 double maxSigma = 0; 856 System.out.println("testTiming algorithm:" + algorithm); 857 for (int idx = samples - 1; idx > 10; idx /= 2) { 858 long cutoff = sorted[idx]; 859 int count = 0; 860 BigInteger total = BigInteger.ZERO; 861 for (int i = 0; i < samples; i++) { 862 if (timing[i] <= cutoff) { 863 total = total.add(k[i]); 864 count += 1; 865 } 866 } 867 double expectedStdDev = n / Math.sqrt(12 * count); 868 double average = total.doubleValue() / count; 869 // Number of standard deviations that the average is away from 870 // the expected value: 871 double sigmas = (expectedAverage - average) / expectedStdDev; 872 if (sigmas > maxSigma) { 873 maxSigma = sigmas; 874 } 875 System.out.println( 876 "count:" 877 + count 878 + " cutoff:" 879 + cutoff 880 + " relative average:" 881 + (average / expectedAverage) 882 + " sigmas:" 883 + sigmas); 884 } 885 // Checks if the signatures with a small timing have a biased k. 886 // We use 7 standard deviations, so that the probability of a false positive is smaller 887 // than 10^{-10}. 888 if (maxSigma >= 7) { 889 fail("Signatures with short timing have a biased k"); 890 } 891 */ 892 // END Android-removed: Android doesn't support JMX 893 } 894 895 @SlowTest(providers = {ProviderType.BOUNCY_CASTLE, ProviderType.CONSCRYPT, ProviderType.OPENJDK, 896 ProviderType.SPONGY_CASTLE}) testTimingAll()897 public void testTimingAll() throws Exception { 898 testTiming("SHA256WithECDSA", "secp256r1", EcUtil.getNistP256Params()); 899 // TODO(bleichen): crypto libraries sometimes use optimized code for curves that are frequently 900 // used. Hence it would make sense to test distinct curves. But at the moment testing many 901 // curves is not practical since one test alone is already quite time consuming. 902 // testTiming("SHA224WithECDSA", "secp224r1", EcUtil.getNistP224Params()); 903 // testTiming("SHA384WithECDSA", "secp384r1", EcUtil.getNistP384Params()); 904 // testTiming("SHA512WithECDSA", "secp521r1", EcUtil.getNistP521Params()); 905 // testTiming("SHA256WithECDSA", "brainpoolP256r1", EcUtil.getBrainpoolP256r1Params()); 906 } 907 } 908