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