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