1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 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 android.keystore.cts; 18 19 import static org.junit.Assert.assertFalse; 20 import static org.junit.Assert.assertSame; 21 import static org.junit.Assert.assertTrue; 22 import static org.junit.Assert.fail; 23 24 import android.content.Context; 25 import android.keystore.cts.util.ImportedKey; 26 import android.keystore.cts.util.TestUtils; 27 import android.security.keystore.KeyGenParameterSpec; 28 import android.security.keystore.KeyProperties; 29 import android.security.keystore.KeyProtection; 30 import android.util.Log; 31 32 import androidx.test.InstrumentationRegistry; 33 import androidx.test.runner.AndroidJUnit4; 34 35 import com.android.internal.util.HexDump; 36 37 import org.bouncycastle.asn1.ASN1Primitive; 38 import org.bouncycastle.asn1.ASN1Sequence; 39 import org.junit.Test; 40 import org.junit.runner.RunWith; 41 42 import java.io.IOException; 43 import java.security.InvalidAlgorithmParameterException; 44 import java.security.InvalidKeyException; 45 import java.security.KeyPair; 46 import java.security.KeyPairGenerator; 47 import java.security.NoSuchAlgorithmException; 48 import java.security.NoSuchProviderException; 49 import java.security.Security; 50 import java.security.Signature; 51 import java.security.SignatureException; 52 import java.security.spec.ECGenParameterSpec; 53 import java.util.Arrays; 54 import java.util.Collection; 55 import java.util.Enumeration; 56 import java.util.HashMap; 57 import java.util.Map; 58 59 @RunWith(AndroidJUnit4.class) 60 public class ECDSASignatureTest { 61 62 private static final String TAG = "ECDSASignatureTest"; 63 getContext()64 private Context getContext() { 65 return InstrumentationRegistry.getInstrumentation().getTargetContext(); 66 } 67 68 @Test testNONEwithECDSATruncatesInputToFieldSize()69 public void testNONEwithECDSATruncatesInputToFieldSize() throws Exception { 70 for (ImportedKey key : importKatKeyPairs("NONEwithECDSA")) { 71 try { 72 assertNONEwithECDSATruncatesInputToFieldSize(key.getKeystoreBackedKeyPair()); 73 } catch (Throwable e) { 74 throw new RuntimeException("Failed for " + key.getAlias(), e); 75 } 76 } 77 } 78 assertNONEwithECDSATruncatesInputToFieldSize(KeyPair keyPair)79 private void assertNONEwithECDSATruncatesInputToFieldSize(KeyPair keyPair) 80 throws Exception { 81 int keySizeBits = TestUtils.getKeySizeBits(keyPair.getPublic()); 82 byte[] message = new byte[(keySizeBits * 3) / 8]; 83 for (int i = 0; i < message.length; i++) { 84 message[i] = (byte) (i + 1); 85 } 86 87 Signature signature = Signature.getInstance("NONEwithECDSA"); 88 signature.initSign(keyPair.getPrivate()); 89 assertSame(Security.getProvider(SignatureTest.EXPECTED_PROVIDER_NAME), 90 signature.getProvider()); 91 signature.update(message); 92 byte[] sigBytes = signature.sign(); 93 94 signature = Signature.getInstance(signature.getAlgorithm(), signature.getProvider()); 95 signature.initVerify(keyPair.getPublic()); 96 97 // Verify the full-length message 98 signature.update(message); 99 assertTrue(signature.verify(sigBytes)); 100 101 // Verify the message truncated to field size 102 signature.update(message, 0, (keySizeBits + 7) / 8); 103 assertTrue(signature.verify(sigBytes)); 104 105 // Verify message truncated to one byte shorter than field size -- this should fail 106 signature.update(message, 0, (keySizeBits / 8) - 1); 107 assertFalse(signature.verify(sigBytes)); 108 } 109 110 @Test testNONEwithECDSASupportsMessagesShorterThanFieldSize()111 public void testNONEwithECDSASupportsMessagesShorterThanFieldSize() throws Exception { 112 for (ImportedKey key : importKatKeyPairs("NONEwithECDSA")) { 113 try { 114 assertNONEwithECDSASupportsMessagesShorterThanFieldSize( 115 key.getKeystoreBackedKeyPair()); 116 } catch (Throwable e) { 117 throw new RuntimeException("Failed for " + key.getAlias(), e); 118 } 119 } 120 } 121 122 /* Duplicate nonces can leak the ECDSA private key, even if each nonce is only used once per 123 * keypair. See Brengel & Rossow 2018 ( https://doi.org/10.1007/978-3-030-00470-5_29 ). 124 */ 125 @Test testECDSANonceReuse()126 public void testECDSANonceReuse() throws Exception { 127 testECDSANonceReuse_Helper(false /* useStrongbox */, "secp224r1"); 128 testECDSANonceReuse_Helper(false /* useStrongbox */, "secp256r1"); 129 testECDSANonceReuse_Helper(false /* useStrongbox */, "secp384r1"); 130 testECDSANonceReuse_Helper(false /* useStrongbox */, "secp521r1"); 131 132 if (TestUtils.hasStrongBox(getContext())) { 133 testECDSANonceReuse_Helper(true /* useStrongbox */, "secp256r1"); 134 } 135 } 136 testECDSANonceReuse_Helper(boolean useStrongbox, String curve)137 private void testECDSANonceReuse_Helper(boolean useStrongbox, String curve) 138 throws NoSuchAlgorithmException, NoSuchProviderException, 139 InvalidAlgorithmParameterException, InvalidKeyException, SignatureException, 140 IOException { 141 KeyPair kp = generateKeyPairForNonceReuse_Helper(useStrongbox, curve); 142 /* An ECDSA signature is a pair of integers (r,s). 143 * 144 * Let G be the curve base point, let n be the order of G, and let k be a random 145 * per-signature nonce. 146 * 147 * ECDSA defines: 148 * r := x_coordinate( k x G) mod n 149 * 150 * It follows that if r_1 == r_2 mod n, then k_1 == k_2 mod n. That is, congruent r 151 * values mod n imply a compromised private key. 152 */ 153 Map<String, byte[]> rValueStrToSigMap = new HashMap<String, byte[]>(); 154 for (byte i = 1; i <= 100; i++) { 155 byte[] message = new byte[] {i}; 156 byte[] signature = computeSignatureForNonceReuse_Helper(message, kp); 157 byte[] rValue = extractRValueFromEcdsaSignature_Helper(signature); 158 String rValueStr = HexDump.toHexString(rValue); 159 if (!rValueStrToSigMap.containsKey(rValueStr)) { 160 rValueStrToSigMap.put(rValueStr, signature); 161 continue; 162 } 163 // Duplicate nonces. 164 Log.i( 165 TAG, 166 "Found duplicate nonce after " 167 + Integer.toString(rValueStrToSigMap.size()) 168 + " ECDSA signatures."); 169 170 byte[] otherSig = rValueStrToSigMap.get(rValueStr); 171 String otherSigStr = HexDump.toHexString(otherSig); 172 String currentSigStr = HexDump.toHexString(signature); 173 fail( 174 "Duplicate ECDSA nonce detected." 175 + " Curve: " + curve 176 + " Strongbox: " + Boolean.toString(useStrongbox) 177 + " Signature 1: " 178 + otherSigStr 179 + " Signature 2: " 180 + currentSigStr); 181 } 182 } 183 generateKeyPairForNonceReuse_Helper(boolean useStrongbox, String curve)184 private KeyPair generateKeyPairForNonceReuse_Helper(boolean useStrongbox, 185 String curve) 186 throws NoSuchAlgorithmException, NoSuchProviderException, 187 InvalidAlgorithmParameterException { 188 // We use a generated key instead of an imported key since key generation drains the entropy 189 // pool and thus increase the chance of duplicate nonces. 190 KeyPairGenerator generator = KeyPairGenerator.getInstance("EC", "AndroidKeyStore"); 191 generator.initialize( 192 new KeyGenParameterSpec.Builder("test1", KeyProperties.PURPOSE_SIGN) 193 .setAlgorithmParameterSpec(new ECGenParameterSpec(curve)) 194 .setDigests(KeyProperties.DIGEST_NONE, KeyProperties.DIGEST_SHA256) 195 .setIsStrongBoxBacked(useStrongbox) 196 .build()); 197 KeyPair kp = generator.generateKeyPair(); 198 return kp; 199 } 200 201 /** 202 * Extract the R value from the ECDSA signature. 203 * 204 * @param sigBytes ASN.1 encoded ECDSA signature. 205 * @return The r value extracted from the signature. 206 * @throws IOException 207 */ extractRValueFromEcdsaSignature_Helper(byte[] sigBytes)208 private byte[] extractRValueFromEcdsaSignature_Helper(byte[] sigBytes) throws IOException { 209 /* ECDSA Signature format (X9.62 Section 6.5): 210 * ECDSA-Sig-Value ::= SEQUENCE { 211 * r INTEGER, 212 * s INTEGER 213 * } 214 */ 215 ASN1Primitive sig1prim = ASN1Primitive.fromByteArray(sigBytes); 216 Enumeration secEnum = ((ASN1Sequence) sig1prim).getObjects(); 217 ASN1Primitive seqObj = (ASN1Primitive) secEnum.nextElement(); 218 // The first ASN1 object is the r value. 219 byte[] r = seqObj.getEncoded(); 220 return r; 221 } 222 computeSignatureForNonceReuse_Helper(byte[] message, KeyPair keyPair)223 private byte[] computeSignatureForNonceReuse_Helper(byte[] message, KeyPair keyPair) 224 throws NoSuchAlgorithmException, InvalidKeyException, SignatureException { 225 Signature signature = Signature.getInstance("NONEwithECDSA"); 226 signature.initSign(keyPair.getPrivate()); 227 signature.update(message); 228 byte[] sigBytes = signature.sign(); 229 return sigBytes; 230 } 231 assertNONEwithECDSASupportsMessagesShorterThanFieldSize(KeyPair keyPair)232 private void assertNONEwithECDSASupportsMessagesShorterThanFieldSize(KeyPair keyPair) 233 throws Exception { 234 int keySizeBits = TestUtils.getKeySizeBits(keyPair.getPublic()); 235 byte[] message = new byte[(keySizeBits * 3 / 4) / 8]; 236 for (int i = 0; i < message.length; i++) { 237 message[i] = (byte) (i + 1); 238 } 239 240 Signature signature = Signature.getInstance("NONEwithECDSA"); 241 signature.initSign(keyPair.getPrivate()); 242 assertSame(Security.getProvider(SignatureTest.EXPECTED_PROVIDER_NAME), 243 signature.getProvider()); 244 signature.update(message); 245 byte[] sigBytes = signature.sign(); 246 247 signature = Signature.getInstance(signature.getAlgorithm(), signature.getProvider()); 248 signature.initVerify(keyPair.getPublic()); 249 250 // Verify the message 251 signature.update(message); 252 assertTrue(signature.verify(sigBytes)); 253 254 // Assert that the message is left-padded with zero bits 255 byte[] fullLengthMessage = TestUtils.leftPadWithZeroBytes(message, keySizeBits / 8); 256 signature.update(fullLengthMessage); 257 assertTrue(signature.verify(sigBytes)); 258 } 259 importKatKeyPairs(String signatureAlgorithm)260 private Collection<ImportedKey> importKatKeyPairs(String signatureAlgorithm) 261 throws Exception { 262 KeyProtection params = 263 TestUtils.getMinimalWorkingImportParametersForSigningingWith(signatureAlgorithm); 264 return importKatKeyPairs(getContext(), params); 265 } 266 importKatKeyPairs( Context context, KeyProtection importParams)267 static Collection<ImportedKey> importKatKeyPairs( 268 Context context, KeyProtection importParams) throws Exception { 269 return Arrays.asList(new ImportedKey[] { 270 TestUtils.importIntoAndroidKeyStore("testECsecp224r1", context, 271 R.raw.ec_key3_secp224r1_pkcs8, R.raw.ec_key3_secp224r1_cert, importParams), 272 TestUtils.importIntoAndroidKeyStore("testECsecp256r1", context, 273 R.raw.ec_key4_secp256r1_pkcs8, R.raw.ec_key4_secp256r1_cert, importParams), 274 TestUtils.importIntoAndroidKeyStore("testECsecp384r1", context, 275 R.raw.ec_key5_secp384r1_pkcs8, R.raw.ec_key5_secp384r1_cert, importParams), 276 TestUtils.importIntoAndroidKeyStore("testECsecp521r1", context, 277 R.raw.ec_key6_secp521r1_pkcs8, R.raw.ec_key6_secp521r1_cert, importParams), 278 }); 279 } 280 } 281