/** * @license * Copyright 2016 Google Inc. All rights reserved. * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package com.google.security.wycheproof; import com.google.security.wycheproof.WycheproofRunner.ProviderType; import com.google.security.wycheproof.WycheproofRunner.SlowTest; // Android-removed: Android doesn't support JMX // import java.lang.management.ManagementFactory; // import java.lang.management.ThreadMXBean; import java.math.BigInteger; import java.security.InvalidAlgorithmParameterException; import java.security.KeyFactory; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.MessageDigest; import java.security.Signature; import java.security.SignatureException; import java.security.interfaces.ECPrivateKey; import java.security.interfaces.ECPublicKey; import java.security.spec.ECGenParameterSpec; import java.security.spec.ECParameterSpec; import java.security.spec.ECPoint; import java.security.spec.ECPublicKeySpec; import java.util.Arrays; import junit.framework.TestCase; /** * Tests ECDSA against invalid signatures. * * @author bleichen@google.com (Daniel Bleichenbacher) */ // Tested providers: // SunEC: accepts a few alternative encodings and throws run time exceptions. // The implementation does not protect against timing attacks. // BC: accepts alternative encoding, and additional arguments // AndroidOpenSSL: OK // TODO(bleichen): // - CVE-2015-2730: Firefox failed to handle some signatures correctly because of incorrect // point multiplication. (I don't have enough information here.) public class EcdsaTest extends TestCase { // ECDSA-Key1 static final String MESSAGE = "Hello"; static final String CURVE = "secp256r1"; static final BigInteger PubX = new BigInteger( "33903964965861532023650245008903090201819051686264021958530366090984128098564"); static final BigInteger PubY = new BigInteger( "113542129898393725739068316260085522189065290079050903091108740065052129055287"); // Valid signatures for MESSAGE static final String[] VALID_SIGNATURES = { "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", }; /** * The following test vectors contain a valid signature that use alternative BER encoding. * Whether such signatures are accepted as valid or rejected depends on the implementation. * Allowing alternative BER encodings is in many cases benign. However, there are cases where this * kind of signature malleability was a problem. See for example * https://en.bitcoin.it/wiki/Transaction_Malleability */ // NOTE(bleichen): The following test vectors were generated with some python code. // New test vectors should best be done by extending this code. Some of the signatures // can be moved to INVALID_SIGNATURES, when b/31572415 is fixed. static final String[] MODIFIED_SIGNATURES = { // BER:long form encoding of length "308145022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d" + "491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e762" + "85cd59f43260ecce", "304602812100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d" + "491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e762" + "85cd59f43260ecce", "3046022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f028120747291dd2f3f44af7ace68ea33431d6f94e418c106a6e762" + "85cd59f43260ecce", // BER:length contains leading 0 "30820045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", "30470282002100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f02820020747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", // BER:prepending 0's to integer "30470223000000b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f02220000747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", // NOTE (bleichen): belongs into INVALID_SIGNATURES. We only keep these // sigantures here because of b/31572415. // length = 2**31 - 1 "30847fffffff022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "304902847fffffff00b7babae9332b54b8a3a05b7004579821a887a1b21465f7" + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "3049022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f02847fffffff747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", }; /** * Test vectors with invalid signatures. * The motivation for these test vectors are previously broken implementations. E.g. * *

{@link java.security.Signature#verify(byte[])} should either return false or throw a * SignatureException. Other behaviour such as throwing a RuntimeException might allow a denial * of service attack: *

* Some of the test vectors were derived from a valid signature by corrupting the DER encoding. * If providers accepts such modified signatures for legacy purpose, then these signatures * should be moved to MODIFIED_SIGNATURES. */ // NOTE(bleichen): The following test vectors were generated with some python code. New test // vectors should best be done by extending the python code. static final String[] INVALID_SIGNATURES = { // wrong length "3046022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3044022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045022200b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045022000b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0221747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f021f747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", // uint32 overflow in length "30850100000045022100b7babae9332b54b8a3a05b7004579821a887a1b21465" + "f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c1" + "06a6e76285cd59f43260ecce", "304a0285010000002100b7babae9332b54b8a3a05b7004579821a887a1b21465" + "f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c1" + "06a6e76285cd59f43260ecce", "304a022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f02850100000020747291dd2f3f44af7ace68ea33431d6f94e418c1" + "06a6e76285cd59f43260ecce", // uint64 overflow in length "3089010000000000000045022100b7babae9332b54b8a3a05b7004579821a887" + "a1b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f" + "94e418c106a6e76285cd59f43260ecce", "304e028901000000000000002100b7babae9332b54b8a3a05b7004579821a887" + "a1b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f" + "94e418c106a6e76285cd59f43260ecce", "304e022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0289010000000000000020747291dd2f3f44af7ace68ea33431d6f" + "94e418c106a6e76285cd59f43260ecce", // length = 2**32 - 1 "3084ffffffff022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "30490284ffffffff00b7babae9332b54b8a3a05b7004579821a887a1b21465f7" + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "3049022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0284ffffffff747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", // length = 2**64 - 1 "3088ffffffffffffffff022100b7babae9332b54b8a3a05b7004579821a887a1" + "b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94" + "e418c106a6e76285cd59f43260ecce", "304d0288ffffffffffffffff00b7babae9332b54b8a3a05b7004579821a887a1" + "b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94" + "e418c106a6e76285cd59f43260ecce", "304d022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0288ffffffffffffffff747291dd2f3f44af7ace68ea33431d6f94" + "e418c106a6e76285cd59f43260ecce", // removing sequence "", // appending 0's to sequence "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce0000", // prepending 0's to sequence "30470000022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", // appending unused 0's "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce0000", "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f00000220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", // appending null value "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce0500", "3047022300b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f05000220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0222747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce0500", // including garbage "304949803045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "304925003045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "30473045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce0004deadbeef", "304922254980022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "304922252500022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "304d2223022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" + "3d491b39fd2c3f0004deadbeef0220747291dd2f3f44af7ace68ea33431d6f94" + "e418c106a6e76285cd59f43260ecce", "3049022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f222449800220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "3049022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f222425000220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "304d022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f22220220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce0004deadbeef", // including undefined tags "304daa00bb00cd003045022100b7babae9332b54b8a3a05b7004579821a887a1" + "b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94" + "e418c106a6e76285cd59f43260ecce", "304baa02aabb3045022100b7babae9332b54b8a3a05b7004579821a887a1b214" + "65f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418" + "c106a6e76285cd59f43260ecce", "304d2229aa00bb00cd00022100b7babae9332b54b8a3a05b7004579821a887a1" + "b21465f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94" + "e418c106a6e76285cd59f43260ecce", "304b2227aa02aabb022100b7babae9332b54b8a3a05b7004579821a887a1b214" + "65f7db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418" + "c106a6e76285cd59f43260ecce", "304d022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f2228aa00bb00cd000220747291dd2f3f44af7ace68ea33431d6f94" + "e418c106a6e76285cd59f43260ecce", "304b022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f2226aa02aabb0220747291dd2f3f44af7ace68ea33431d6f94e418" + "c106a6e76285cd59f43260ecce", // changing tag value "2e45022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3245022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "ff45022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045002100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045042100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045ff2100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0020747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0420747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3fff20747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", // dropping value of sequence "3000", // using composition "304930010230442100b7babae9332b54b8a3a05b7004579821a887a1b21465f7" + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "304922250201000220b7babae9332b54b8a3a05b7004579821a887a1b21465f7" + "db8a3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", "3049022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f2224020174021f7291dd2f3f44af7ace68ea33431d6f94e418c106" + "a6e76285cd59f43260ecce", // truncate sequence "3044022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ec", "30442100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d491b" + "39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd" + "59f43260ecce", // prepend empty sequence "30473000022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", // append empty sequence "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce3000", // sequence of sequence "30473045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a" + "3d491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", // truncated sequence "3023022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d491b39fd2c3f", // repeat element in sequence "3067022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", // removing integer "30220220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd59f43260ecce", // appending 0's to integer "3047022300b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f00000220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e7" + "6285cd59f43260ecce", "3047022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0222747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce0000", // dropping value of integer "302402000220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd59f43260ecce", "3025022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d491b39fd2c3f0200", // modify first byte of integer "3045022101b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220757291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", // modify last byte of integer "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3e0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260eccf", // truncate integer "3044022000b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd" + "59f43260ecce", "30440220b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d491b" + "39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd" + "59f43260ecce", "3044022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f021f747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ec", "3044022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f021f7291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd" + "59f43260ecce", // leading ff in integer "30460222ff00b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d" + "491b39fd2c3f0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e762" + "85cd59f43260ecce", "3046022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f0221ff747291dd2f3f44af7ace68ea33431d6f94e418c106a6e762" + "85cd59f43260ecce", // infinity "30250901800220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd59f43260ecce", "3026022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d491b39fd2c3f090180", // Vectors where r or s have been modified e.g. by adding or subtracting the order of the // group or field and hence violate the range check for r and s required by ECDSA. "30450221ff48454516ccd4ab475c5fa48ffba867de57785e4deb9a082475c2b6" + "e4c602d3c10220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045022101b7babae8332b54b9a3a05b7004579821656e9c5fbb7d96607df713" + "de366051900220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3044022048454515ccd4ab485c5fa48ffba867de145f58fb92b1a6a9697c81a7" + "c265f9120220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285cd" + "59f43260ecce", "3045022101b7babae8332b54b9a3a05b7004579821a887a1b31465f7db8a3d49" + "1b39fd2c3e0220747291dd2f3f44af7ace68ea33431d6f94e418c106a6e76285" + "cd59f43260ecce", "3045022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f02208b8d6e22d0c0bb5085319715ccbce2906b1be73ef959189d7a" + "32a60bcd9f1332", "3046022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f022101747291dc2f3f44b07ace68ea33431d6f51cb136eadbe85e7" + "798724b72ec4121f", "3046022100b7babae9332b54b8a3a05b7004579821a887a1b21465f7db8a3d49" + "1b39fd2c3f022101747291dc2f3f44b07ace68ea33431d6f94e418c206a6e762" + "85cd59f43260eccd", // Signatures with special case values for r and s (such as 0 and 1). Such values often // uncover implementation errors. "3006020100020100", "3006020100020101", "30060201000201ff", "3026020100022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", "3026020100022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632550", "3026020100022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632552", "3026020100022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", "3026020100022100ffffffff00000001000000000000000000000001000000000000000000000000", "3008020100090380fe01", "3006020101020100", "3006020101020101", "30060201010201ff", "3026020101022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", "3026020101022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632550", "3026020101022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632552", "3026020101022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", "3026020101022100ffffffff00000001000000000000000000000001000000000000000000000000", "3008020101090380fe01", "30060201ff020100", "30060201ff020101", "30060201ff0201ff", "30260201ff022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", "30260201ff022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632550", "30260201ff022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632552", "30260201ff022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", "30260201ff022100ffffffff00000001000000000000000000000001000000000000000000000000", "30080201ff090380fe01", "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551020100", "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551020101", "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc6325510201ff", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632551022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632551", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632551022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632550", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632551022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632552", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632551022100ffffffff00000001000000000000000000000000ffffffff" + "ffffffffffffffff", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632551022100ffffffff0000000100000000000000000000000100000000" + "0000000000000000", "3028022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632551090380fe01", "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632550020100", "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632550020101", "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc6325500201ff", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632550022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632551", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632550022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632550", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632550022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632552", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632550022100ffffffff00000001000000000000000000000000ffffffff" + "ffffffffffffffff", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632550022100ffffffff0000000100000000000000000000000100000000" + "0000000000000000", "3028022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632550090380fe01", "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632552020100", "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632552020101", "3026022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc6325520201ff", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632552022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632551", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632552022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632550", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632552022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632552", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632552022100ffffffff00000001000000000000000000000000ffffffff" + "ffffffffffffffff", "3046022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632552022100ffffffff0000000100000000000000000000000100000000" + "0000000000000000", "3028022100ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9ca" + "c2fc632552090380fe01", "3026022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff020100", "3026022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff020101", "3026022100ffffffff00000001000000000000000000000000ffffffffffffffffffffffff0201ff", "3046022100ffffffff00000001000000000000000000000000ffffffffffffff" + "ffffffffff022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632551", "3046022100ffffffff00000001000000000000000000000000ffffffffffffff" + "ffffffffff022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632550", "3046022100ffffffff00000001000000000000000000000000ffffffffffffff" + "ffffffffff022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632552", "3046022100ffffffff00000001000000000000000000000000ffffffffffffff" + "ffffffffff022100ffffffff00000001000000000000000000000000ffffffff" + "ffffffffffffffff", "3046022100ffffffff00000001000000000000000000000000ffffffffffffff" + "ffffffffff022100ffffffff0000000100000000000000000000000100000000" + "0000000000000000", "3028022100ffffffff00000001000000000000000000000000ffffffffffffff" + "ffffffffff090380fe01", "3026022100ffffffff00000001000000000000000000000001000000000000000000000000020100", "3026022100ffffffff00000001000000000000000000000001000000000000000000000000020101", "3026022100ffffffff000000010000000000000000000000010000000000000000000000000201ff", "3046022100ffffffff0000000100000000000000000000000100000000000000" + "0000000000022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632551", "3046022100ffffffff0000000100000000000000000000000100000000000000" + "0000000000022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632550", "3046022100ffffffff0000000100000000000000000000000100000000000000" + "0000000000022100ffffffff00000000ffffffffffffffffbce6faada7179e84" + "f3b9cac2fc632552", "3046022100ffffffff0000000100000000000000000000000100000000000000" + "0000000000022100ffffffff00000001000000000000000000000000ffffffff" + "ffffffffffffffff", "3046022100ffffffff0000000100000000000000000000000100000000000000" + "0000000000022100ffffffff0000000100000000000000000000000100000000" + "0000000000000000", "3028022100ffffffff0000000100000000000000000000000100000000000000" + "0000000000090380fe01", }; /** * Determines the Hash name from the ECDSA algorithm. There is a small inconsistency in the naming * of algorithms. The Oracle standard use no hyphen in SHA256WithECDSA but uses a hyphen in the * message digest, i.e., SHA-256. */ public String getHashAlgorithm(String ecdsaAlgorithm) { ecdsaAlgorithm = ecdsaAlgorithm.toUpperCase(); int idx = ecdsaAlgorithm.indexOf("WITH"); if (idx > 0) { if (ecdsaAlgorithm.startsWith("SHA")) { return "SHA-" + ecdsaAlgorithm.substring(3, idx); } else { return ecdsaAlgorithm.substring(0, idx); } } return ""; } /** * Extract the integer r from an ECDSA signature. This method implicitely assumes that the ECDSA * signature is DER encoded. and that the order of the curve is smaller than 2^1024. */ BigInteger extractR(byte[] signature) throws Exception { int startR = (signature[1] & 0x80) != 0 ? 3 : 2; int lengthR = signature[startR + 1]; return new BigInteger(Arrays.copyOfRange(signature, startR + 2, startR + 2 + lengthR)); } BigInteger extractS(byte[] signature) throws Exception { int startR = (signature[1] & 0x80) != 0 ? 3 : 2; int lengthR = signature[startR + 1]; int startS = startR + 2 + lengthR; int lengthS = signature[startS + 1]; return new BigInteger(Arrays.copyOfRange(signature, startS + 2, startS + 2 + lengthS)); } /** Extract the k that was used to sign the signature. */ BigInteger extractK(byte[] signature, BigInteger h, ECPrivateKey priv) throws Exception { BigInteger x = priv.getS(); BigInteger n = priv.getParams().getOrder(); BigInteger r = extractR(signature); BigInteger s = extractS(signature); BigInteger k = x.multiply(r).add(h).multiply(s.modInverse(n)).mod(n); return k; } public ECPublicKeySpec publicKey1() throws Exception { ECParameterSpec params = EcUtil.getNistP256Params(); ECPoint w = new ECPoint(PubX, PubY); return new ECPublicKeySpec(w, params); } public void testVectors( String[] signatures, ECPublicKeySpec pubSpec, String message, String algorithm, String signatureType, boolean isValidDER, boolean isValidBER) throws Exception { byte[] messageBytes = message.getBytes("UTF-8"); Signature verifier = Signature.getInstance(algorithm); KeyFactory kf = KeyFactory.getInstance("EC"); ECPublicKey pub = (ECPublicKey) kf.generatePublic(pubSpec); int errors = 0; for (String signature : signatures) { byte[] signatureBytes = TestUtil.hexToBytes(signature); verifier.initVerify(pub); verifier.update(messageBytes); boolean verified = false; try { verified = verifier.verify(signatureBytes); } catch (SignatureException ex) { // verify can throw SignatureExceptions if the signature is malformed. // We don't flag these cases and simply consider the signature as invalid. verified = false; } if (!verified && isValidDER) { System.out.println(signatureType + " was not verified:" + signature); errors++; } if (verified && !isValidBER) { System.out.println(signatureType + " was verified:" + signature); errors++; } } assertEquals(0, errors); } public void testValidSignatures() throws Exception { testVectors( VALID_SIGNATURES, publicKey1(), "Hello", "SHA256WithECDSA", "Valid ECDSA signature", true, true); } public void testModifiedSignatures() throws Exception { testVectors( MODIFIED_SIGNATURES, publicKey1(), "Hello", "SHA256WithECDSA", "Modified ECDSA signature", false, true); } public void testInvalidSignatures() throws Exception { testVectors( INVALID_SIGNATURES, publicKey1(), "Hello", "SHA256WithECDSA", "Invalid ECDSA signature", false, false); } /** * This test checks the basic functionality of ECDSA. It can also be used to generate simple test * vectors. */ public void testBasic() throws Exception { String algorithm = "SHA256WithECDSA"; String hashAlgorithm = "SHA-256"; String message = "Hello"; String curve = "secp256r1"; KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); ECGenParameterSpec ecSpec = new ECGenParameterSpec("secp256r1"); keyGen.initialize(ecSpec); KeyPair keyPair = keyGen.generateKeyPair(); ECPublicKey pub = (ECPublicKey) keyPair.getPublic(); ECPrivateKey priv = (ECPrivateKey) keyPair.getPrivate(); byte[] messageBytes = message.getBytes("UTF-8"); Signature signer = Signature.getInstance(algorithm); Signature verifier = Signature.getInstance(algorithm); signer.initSign(priv); signer.update(messageBytes); byte[] signature = signer.sign(); verifier.initVerify(pub); verifier.update(messageBytes); assertTrue(verifier.verify(signature)); // Extract some parameters. byte[] rawHash = MessageDigest.getInstance(hashAlgorithm).digest(messageBytes); ECParameterSpec params = priv.getParams(); // Print keys and signature, so that it can be used to generate new test vectors. System.out.println("Message:" + message); System.out.println("Hash:" + TestUtil.bytesToHex(rawHash)); System.out.println("Curve:" + curve); System.out.println("Order:" + params.getOrder().toString()); System.out.println("Private key:"); System.out.println("S:" + priv.getS().toString()); System.out.println("encoded:" + TestUtil.bytesToHex(priv.getEncoded())); System.out.println("Public key:"); ECPoint w = pub.getW(); System.out.println("X:" + w.getAffineX().toString()); System.out.println("Y:" + w.getAffineY().toString()); System.out.println("encoded:" + TestUtil.bytesToHex(pub.getEncoded())); System.out.println("Signature:" + TestUtil.bytesToHex(signature)); System.out.println("r:" + extractR(signature).toString()); System.out.println("s:" + extractS(signature).toString()); } /** Checks whether the one time key k in ECDSA is biased. */ public void testBias(String algorithm, String curve, ECParameterSpec ecParams) throws Exception { KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); try { keyGen.initialize(ecParams); } catch (InvalidAlgorithmParameterException ex) { System.out.println("This provider does not support curve:" + curve); return; } KeyPair keyPair = keyGen.generateKeyPair(); ECPrivateKey priv = (ECPrivateKey) keyPair.getPrivate(); // If we throw a fair coin tests times then the probability that // either heads or tails appears less than mincount is less than 2^{-32}. // Therefore the test below is not expected to fail unless the generation // of the one time keys is indeed biased. final int tests = 1024; final int mincount = 410; String hashAlgorithm = getHashAlgorithm(algorithm); String message = "Hello"; byte[] messageBytes = message.getBytes("UTF-8"); byte[] digest = MessageDigest.getInstance(hashAlgorithm).digest(messageBytes); // TODO(bleichen): Truncate the digest if the digest size is larger than the // curve size. BigInteger h = new BigInteger(1, digest); BigInteger q = priv.getParams().getOrder(); BigInteger qHalf = q.shiftRight(1); Signature signer = Signature.getInstance(algorithm); signer.initSign(priv); int countLsb = 0; // count the number of k's with msb set int countMsb = 0; // count the number of k's with lsb set for (int i = 0; i < tests; i++) { signer.update(messageBytes); byte[] signature = signer.sign(); BigInteger k = extractK(signature, h, priv); if (k.testBit(0)) { countLsb++; } if (k.compareTo(qHalf) == 1) { countMsb++; } } System.out.println( signer.getProvider().getName() + " curve:" + curve + " countLsb:" + countLsb + " countMsb:" + countMsb); if (countLsb < mincount || countLsb > tests - mincount) { fail("Bias detected in the least significant bit of k:" + countLsb); } if (countMsb < mincount || countMsb > tests - mincount) { fail("Bias detected in the most significant bit of k:" + countMsb); } } @SlowTest(providers = {ProviderType.BOUNCY_CASTLE, ProviderType.CONSCRYPT, ProviderType.OPENJDK, ProviderType.SPONGY_CASTLE}) public void testBiasAll() throws Exception { testBias("SHA256WithECDSA", "secp256r1", EcUtil.getNistP256Params()); testBias("SHA224WithECDSA", "secp224r1", EcUtil.getNistP224Params()); testBias("SHA384WithECDSA", "secp384r1", EcUtil.getNistP384Params()); testBias("SHA512WithECDSA", "secp521r1", EcUtil.getNistP521Params()); testBias("SHA256WithECDSA", "brainpoolP256r1", EcUtil.getBrainpoolP256r1Params()); } /** * Tests for a potential timing attack. This test checks if there is a correlation between the * timing of signature generation and the size of the one-time key k. This is for example the case * if a double and add method is used for the point multiplication. The test fails if such a * correlation can be shown with high confidence. Further analysis will be necessary to determine * how easy it is to exploit the bias in a timing attack. */ // TODO(bleichen): Determine if there are exploitable providers. // // SunEC currently fails this test. Since ECDSA typically is used with EC groups whose order // is 224 bits or larger, it is unclear whether the same attacks that apply to DSA are practical. // // The ECDSA implementation in BouncyCastle leaks information about k through timing too. // The test has not been optimized to detect this bias. It would require about 5'000'000 samples, // which is too much for a simple unit test. // // BouncyCastle uses FixedPointCombMultiplier for ECDSA. This is a method using // precomputation. The implementation is not constant time, since the precomputation table // contains the point at infinity and adding this point is faster than ordinary point additions. // The timing leak only has a small correlation to the size of k and at the moment it is is very // unclear if the can be exploited. (Randomizing the precomputation table by adding the same // random point to each element in the table and precomputing the necessary offset to undo the // precomputation seems much easier than analyzing this.) public void testTiming(String algorithm, String curve, ECParameterSpec ecParams) throws Exception { // BEGIN Android-removed: Android doesn't support JMX /* ThreadMXBean bean = ManagementFactory.getThreadMXBean(); if (!bean.isCurrentThreadCpuTimeSupported()) { System.out.println("getCurrentThreadCpuTime is not supported. Skipping"); return; } KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); try { keyGen.initialize(ecParams); } catch (InvalidAlgorithmParameterException ex) { System.out.println("This provider does not support curve:" + curve); return; } KeyPair keyPair = keyGen.generateKeyPair(); ECPrivateKey priv = (ECPrivateKey) keyPair.getPrivate(); String message = "Hello"; String hashAlgorithm = getHashAlgorithm(algorithm); byte[] messageBytes = message.getBytes("UTF-8"); byte[] digest = MessageDigest.getInstance(hashAlgorithm).digest(messageBytes); BigInteger h = new BigInteger(1, digest); Signature signer = Signature.getInstance(algorithm); signer.initSign(priv); // The number of samples used for the test. This number is a bit low. // I.e. it just barely detects that SunEC leaks information about the size of k. int samples = 50000; long[] timing = new long[samples]; BigInteger[] k = new BigInteger[samples]; for (int i = 0; i < samples; i++) { long start = bean.getCurrentThreadCpuTime(); signer.update(messageBytes); byte[] signature = signer.sign(); timing[i] = bean.getCurrentThreadCpuTime() - start; k[i] = extractK(signature, h, priv); } long[] sorted = Arrays.copyOf(timing, timing.length); Arrays.sort(sorted); double n = priv.getParams().getOrder().doubleValue(); double expectedAverage = n / 2; double maxSigma = 0; System.out.println("testTiming algorithm:" + algorithm); for (int idx = samples - 1; idx > 10; idx /= 2) { long cutoff = sorted[idx]; int count = 0; BigInteger total = BigInteger.ZERO; for (int i = 0; i < samples; i++) { if (timing[i] <= cutoff) { total = total.add(k[i]); count += 1; } } double expectedStdDev = n / Math.sqrt(12 * count); double average = total.doubleValue() / count; // Number of standard deviations that the average is away from // the expected value: double sigmas = (expectedAverage - average) / expectedStdDev; if (sigmas > maxSigma) { maxSigma = sigmas; } System.out.println( "count:" + count + " cutoff:" + cutoff + " relative average:" + (average / expectedAverage) + " sigmas:" + sigmas); } // Checks if the signatures with a small timing have a biased k. // We use 7 standard deviations, so that the probability of a false positive is smaller // than 10^{-10}. if (maxSigma >= 7) { fail("Signatures with short timing have a biased k"); } */ // END Android-removed: Android doesn't support JMX } @SlowTest(providers = {ProviderType.BOUNCY_CASTLE, ProviderType.CONSCRYPT, ProviderType.OPENJDK, ProviderType.SPONGY_CASTLE}) public void testTimingAll() throws Exception { testTiming("SHA256WithECDSA", "secp256r1", EcUtil.getNistP256Params()); // TODO(bleichen): crypto libraries sometimes use optimized code for curves that are frequently // used. Hence it would make sense to test distinct curves. But at the moment testing many // curves is not practical since one test alone is already quite time consuming. // testTiming("SHA224WithECDSA", "secp224r1", EcUtil.getNistP224Params()); // testTiming("SHA384WithECDSA", "secp384r1", EcUtil.getNistP384Params()); // testTiming("SHA512WithECDSA", "secp521r1", EcUtil.getNistP521Params()); // testTiming("SHA256WithECDSA", "brainpoolP256r1", EcUtil.getBrainpoolP256r1Params()); } }