diff options
Diffstat (limited to 'keystore-cts/java/com/google/security/wycheproof/testcases/EcdsaTest.java')
-rw-r--r-- | keystore-cts/java/com/google/security/wycheproof/testcases/EcdsaTest.java | 417 |
1 files changed, 417 insertions, 0 deletions
diff --git a/keystore-cts/java/com/google/security/wycheproof/testcases/EcdsaTest.java b/keystore-cts/java/com/google/security/wycheproof/testcases/EcdsaTest.java new file mode 100644 index 0000000..a6ce23a --- /dev/null +++ b/keystore-cts/java/com/google/security/wycheproof/testcases/EcdsaTest.java @@ -0,0 +1,417 @@ +/** + * 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 static org.junit.Assert.assertTrue; +import static org.junit.Assert.fail; + +import com.google.security.wycheproof.WycheproofRunner.ProviderType; +import com.google.security.wycheproof.WycheproofRunner.SlowTest; +import java.lang.management.ManagementFactory; +import java.lang.management.ThreadMXBean; +import java.math.BigInteger; +import java.security.InvalidAlgorithmParameterException; +import java.security.KeyPair; +import java.security.KeyPairGenerator; +import java.security.MessageDigest; +import java.security.NoSuchAlgorithmException; +import java.security.Signature; +import java.security.interfaces.ECPrivateKey; +import java.security.interfaces.ECPublicKey; +import java.security.spec.ECGenParameterSpec; +import java.security.spec.ECParameterSpec; +import java.util.Arrays; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.JUnit4; + +/** + * Tests ECDSA signatures. + * + * <p>Tests for signature verification with test vectors are in JsonSignatureTest.java toghether + * with other signature schemes. + * + * @author bleichen@google.com (Daniel Bleichenbacher) + */ +@RunWith(JUnit4.class) +public class EcdsaTest { + + /** + * 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. + */ + private 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; + } + + /** + * Computes the bias of samples as + * + * abs(sum(e^(2 pi i s m / modulus) for s in samples) / sqrt(samples.length). + * + * If the samples are taken from a uniform distribution in the range 0 .. modulus - 1 + * and the number of samples is significantly larger than L^2 + * then the probability that the result is larger than L is approximately e^(-L^2). + * The approximation can be derived from the assumption that samples taken from + * a uniform distribution give a result that approximates a standard complex normal + * distribution Z. I.e. Z has a density f_Z(z) = exp(-abs(z)^2) / pi. + * https://en.wikipedia.org/wiki/Complex_normal_distribution + */ + double bias(BigInteger[] samples, BigInteger modulus, BigInteger m) { + double sumReal = 0.0; + double sumImag = 0.0; + for (BigInteger s : samples) { + BigInteger r = s.multiply(m).mod(modulus); + // multiplier = 2 * pi / 2^52 + double multiplier = 1.3951473992034527e-15; + // computes the quotent 2 * pi * r / modulus + double quot = r.shiftLeft(52).divide(modulus).doubleValue() * multiplier; + sumReal += Math.cos(quot); + sumImag += Math.sin(quot); + } + return Math.sqrt((sumReal * sumReal + sumImag * sumImag) / samples.length); + } + + /** + * This test checks the basic functionality of ECDSA. It simply tries to generate a key, sign and + * verify a message for a given, algorithm and curve. + * + * @param algorithm the algorithm to test (e.g. "SHA256WithECDSA") + * @param curve the curve to test (e.g. "secp256r1") + * @return whether the algorithm and curve are supported. + * @throws Exception if an unexpected error occurred. + */ + boolean testParameters(String algorithm, String curve) throws Exception { + String message = "123400"; + + KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC"); + ECGenParameterSpec ecSpec = new ECGenParameterSpec(curve); + KeyPair keyPair; + try { + keyGen.initialize(ecSpec); + keyPair = keyGen.generateKeyPair(); + } catch (InvalidAlgorithmParameterException ex) { + // The curve is not supported. + // The documentation does not specify whether the method initialize + // has to reject unsupported curves or if only generateKeyPair checks + // whether the curve is supported. + return false; + } + ECPublicKey pub = (ECPublicKey) keyPair.getPublic(); + ECPrivateKey priv = (ECPrivateKey) keyPair.getPrivate(); + + // Print the parameters. + System.out.println("Parameters for curve:" + curve); + EcUtil.printParameters(pub.getParams()); + + Signature signer; + Signature verifier; + try { + signer = Signature.getInstance(algorithm); + verifier = Signature.getInstance(algorithm); + } catch (NoSuchAlgorithmException ex) { + // The algorithm is not supported. + return false; + } + // Both algorithm and curve are supported. + // Hence, we expect that signing and verifying properly works. + byte[] messageBytes = message.getBytes("UTF-8"); + signer.initSign(priv); + signer.update(messageBytes); + byte[] signature = signer.sign(); + verifier.initVerify(pub); + verifier.update(messageBytes); + assertTrue(verifier.verify(signature)); + return true; + } + + /** + * This test checks the basic functionality of ECDSA. This mainly checks that the provider follows + * the JCA interface. + */ + @Test + public void testBasic() throws Exception { + String algorithm = "SHA256WithECDSA"; + String curve = "secp256r1"; + assertTrue(testParameters(algorithm, curve)); + } + + /** 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); + BigInteger[] kList = new BigInteger[tests]; + for (int i = 0; i < tests; i++) { + signer.update(messageBytes); + byte[] signature = signer.sign(); + kList[i] = extractK(signature, h, priv); + } + + // Checks whether the most significant bits and the least significant bits + // of the value k are unbiased. + int countMsb = 0; // count the number of k's with lsb set + int countLsb = 0; // count the number of k's with msb set + for (BigInteger k : kList) { + if (k.testBit(0)) { + countLsb++; + } + if (k.compareTo(qHalf) > 0) { + 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); + } + + // One situation where the bits above are not biased even if k itself is + // badly distributed is the case where the signer replaces s by + // min(s, q - s). Such a replacement is sometimes done to avoid signature + // malleability of ECDSA. + // Breitner and Heninger describe such cases in the paper + // "Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies", + // https://eprint.iacr.org/2019/023.pdf + // The following tests should catch the bugs described in this paper. + // The threshold below has been chosen to give false positives with probability < 2^{-32}. + double threshold = 5; + + // This test detects for example the case when either k or q-k is small. + double bias1 = bias(kList, q, BigInteger.ONE); + if (bias1 > threshold) { + fail("Bias for k detected. bias1 = " + bias1); + } + // Same as above but shifing by one bit. + double bias2 = bias(kList, q, BigInteger.valueOf(2)); + if (bias2 > threshold) { + fail("Bias for k detected. bias2 = " + bias2); + } + double bias3 = bias(kList, q, qHalf); + if (bias3 > threshold) { + fail("Bias for k detected. bias3 = " + bias3); + } + // Checks whether most significant bytes, words, dwords or qwords are strongly correlated. + for (int bits : new int[] {8, 16, 32, 64}) { + BigInteger multiplier = BigInteger.ONE.shiftLeft(bits).subtract(BigInteger.ONE); + double bias4 = bias(kList, q, multiplier); + if (bias4 > threshold) { + fail("Bias for k detected. bits = " + bits + " bias4 = " + bias4); + } + } + } + + @SlowTest( + providers = { + ProviderType.BOUNCY_CASTLE, + ProviderType.CONSCRYPT, + ProviderType.OPENJDK, + ProviderType.SPONGY_CASTLE + } + ) + @Test + 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 { + 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 = Math.abs(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"); + } + } + + @SlowTest( + providers = { + ProviderType.BOUNCY_CASTLE, + ProviderType.CONSCRYPT, + ProviderType.OPENJDK, + ProviderType.SPONGY_CASTLE + } + ) + @Test + 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()); + } +} |