Keystore: Support Ed25519 keys

Implement support for Ed25519 signing keys in Android Keystore.
Because Conscrypt does not yet handle those keys, the Keystore classes
implement EdECPublicKey directly and parse the keys.

Specifically, AndroidKeyStoreEdECPublicKey can take an encoded X.509 key
specification, validate the encoding is of an Ed25519 key, then parse
the oddity and Y point on the curve.
RFC8032 describes EdDSA signature scheme, particularly Ed25519.
RFC8410, Section 3, defines the OID for Ed25519 keys (1.3.101.112).
RFC8410, Section 4, describes the encoding of the public key.

Bug: 195309719
Bug: 194359292
Bug: 214203951
Test: atest android.security.keystore2.AndroidKeyStoreEdECPublicKeyTest
Change-Id: I07b793cbd5029630768368ad4a863bbc1c828ced

3 files changed, 194 insertions, 3 deletions

diff --git a/keystore/java/android/security/keystore2/AndroidKeyStoreEdECPrivateKey.java b/keystore/java/android/security/keystore2/AndroidKeyStoreEdECPrivateKey.java
new file mode 100644
index 000000000000..4855ad0f7293
--- /dev/null
+++ b/keystore/java/android/security/keystore2/AndroidKeyStoreEdECPrivateKey.java
@@ -0,0 +1,46 @@
+/*
+ * Copyright (C) 2022 The Android Open Source Project
+ *
+ * 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 android.security.keystore2;
+
+import android.annotation.NonNull;
+import android.security.KeyStoreSecurityLevel;
+import android.system.keystore2.Authorization;
+import android.system.keystore2.KeyDescriptor;
+
+import java.security.PrivateKey;
+import java.security.interfaces.EdECKey;
+import java.security.spec.NamedParameterSpec;
+
+/**
+ * EdEC private key (instance of {@link PrivateKey} and {@link EdECKey}) backed by keystore.
+ *
+ * @hide
+ */
+public class AndroidKeyStoreEdECPrivateKey extends AndroidKeyStorePrivateKey implements EdECKey {
+    public AndroidKeyStoreEdECPrivateKey(
+            @NonNull KeyDescriptor descriptor, long keyId,
+            @NonNull Authorization[] authorizations,
+            @NonNull String algorithm,
+            @NonNull KeyStoreSecurityLevel securityLevel) {
+        super(descriptor, keyId, authorizations, algorithm, securityLevel);
+    }
+
+    @Override
+    public NamedParameterSpec getParams() {
+        return NamedParameterSpec.ED25519;
+    }
+}
diff --git a/keystore/java/android/security/keystore2/AndroidKeyStoreEdECPublicKey.java b/keystore/java/android/security/keystore2/AndroidKeyStoreEdECPublicKey.java
new file mode 100644
index 000000000000..642e08813291
--- /dev/null
+++ b/keystore/java/android/security/keystore2/AndroidKeyStoreEdECPublicKey.java
@@ -0,0 +1,145 @@
+/*
+ * Copyright (C) 2022 The Android Open Source Project
+ *
+ * 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 android.security.keystore2;
+
+import android.annotation.NonNull;
+import android.security.KeyStoreSecurityLevel;
+import android.system.keystore2.KeyDescriptor;
+import android.system.keystore2.KeyMetadata;
+
+import java.math.BigInteger;
+import java.security.interfaces.EdECPublicKey;
+import java.security.spec.EdECPoint;
+import java.security.spec.NamedParameterSpec;
+import java.util.Arrays;
+import java.util.Objects;
+
+/**
+ * {@link EdECPublicKey} backed by keystore.
+ *
+ * @hide
+ */
+public class AndroidKeyStoreEdECPublicKey extends AndroidKeyStorePublicKey
+        implements EdECPublicKey {
+    /**
+     * DER sequence, as defined in https://datatracker.ietf.org/doc/html/rfc8410#section-4 and
+     * https://datatracker.ietf.org/doc/html/rfc5280#section-4.1.
+     * SEQUENCE (2 elem)
+     *  SEQUENCE (1 elem)
+     *    OBJECT IDENTIFIER 1.3.101.112 curveEd25519 (EdDSA 25519 signature algorithm)
+     *    as defined in https://datatracker.ietf.org/doc/html/rfc8410#section-3
+     *  BIT STRING (256 bit) as defined in
+     *  https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.2
+     */
+    private static final byte[] DER_KEY_PREFIX = new byte[] {
+            0x30,
+            0x2a,
+            0x30,
+            0x05,
+            0x06,
+            0x03,
+            0x2b,
+            0x65,
+            0x70,
+            0x03,
+            0x21,
+            0x00,
+    };
+    private static final int ED25519_KEY_SIZE_BYTES = 32;
+
+    private byte[] mEncodedKey;
+    private EdECPoint mPoint;
+
+    public AndroidKeyStoreEdECPublicKey(
+            @NonNull KeyDescriptor descriptor,
+            @NonNull KeyMetadata metadata,
+            @NonNull String algorithm,
+            @NonNull KeyStoreSecurityLevel iSecurityLevel,
+            @NonNull byte[] encodedKey) {
+        super(descriptor, metadata, encodedKey, algorithm, iSecurityLevel);
+        mEncodedKey = encodedKey;
+
+        int preambleLength = matchesPreamble(DER_KEY_PREFIX, encodedKey);
+        if (preambleLength == 0) {
+            throw new IllegalArgumentException("Key size is not correct size");
+        }
+
+        mPoint = pointFromKeyByteArray(
+                Arrays.copyOfRange(encodedKey, preambleLength, encodedKey.length));
+    }
+
+    @Override
+    AndroidKeyStorePrivateKey getPrivateKey() {
+        return new AndroidKeyStoreEdECPrivateKey(
+                getUserKeyDescriptor(),
+                getKeyIdDescriptor().nspace,
+                getAuthorizations(),
+                "EdDSA",
+                getSecurityLevel());
+    }
+
+    @Override
+    public NamedParameterSpec getParams() {
+        return NamedParameterSpec.ED25519;
+    }
+
+    @Override
+    public EdECPoint getPoint() {
+        return mPoint;
+    }
+
+    private static int matchesPreamble(byte[] preamble, byte[] encoded) {
+        if (encoded.length != (preamble.length + ED25519_KEY_SIZE_BYTES)) {
+            return 0;
+        }
+        if (Arrays.compare(preamble, Arrays.copyOf(encoded, preamble.length)) != 0) {
+            return 0;
+        }
+        return preamble.length;
+    }
+
+    private static EdECPoint pointFromKeyByteArray(byte[] coordinates) {
+        Objects.requireNonNull(coordinates);
+
+        // Oddity of the key is the most-significant bit of the last byte.
+        boolean isOdd = (0x80 & coordinates[coordinates.length - 1]) != 0;
+        // Zero out the oddity bit.
+        coordinates[coordinates.length - 1] &= (byte) 0x7f;
+        // Representation of Y is in little-endian, according to rfc8032 section-3.1.
+        reverse(coordinates);
+        // The integer representing Y starts from the first bit in the coordinates array.
+        BigInteger y = new BigInteger(1, coordinates);
+        return new EdECPoint(isOdd, y);
+    }
+
+    private static void reverse(byte[] coordinateArray) {
+        int start = 0;
+        int end = coordinateArray.length - 1;
+        while (start < end) {
+            byte tmp = coordinateArray[start];
+            coordinateArray[start] = coordinateArray[end];
+            coordinateArray[end] = tmp;
+            start++;
+            end--;
+        }
+    }
+
+    @Override
+    public byte[] getEncoded() {
+        return mEncodedKey.clone();
+    }
+}
diff --git a/keystore/java/android/security/keystore2/AndroidKeyStoreProvider.java b/keystore/java/android/security/keystore2/AndroidKeyStoreProvider.java
index d31499e8b36d..0355628b8135 100644
--- a/keystore/java/android/security/keystore2/AndroidKeyStoreProvider.java
+++ b/keystore/java/android/security/keystore2/AndroidKeyStoreProvider.java
@@ -224,7 +224,6 @@ public class AndroidKeyStoreProvider extends Provider {
 
         String jcaKeyAlgorithm = publicKey.getAlgorithm();
 
-        KeyStoreSecurityLevel securityLevel = iSecurityLevel;
         if (KeyProperties.KEY_ALGORITHM_EC.equalsIgnoreCase(jcaKeyAlgorithm)) {
             return new AndroidKeyStoreECPublicKey(descriptor, metadata,
                     iSecurityLevel, (ECPublicKey) publicKey);
@@ -232,8 +231,9 @@ public class AndroidKeyStoreProvider extends Provider {
             return new AndroidKeyStoreRSAPublicKey(descriptor, metadata,
                     iSecurityLevel, (RSAPublicKey) publicKey);
         } else if (ED25519_OID.equalsIgnoreCase(jcaKeyAlgorithm)) {
-            //TODO(b/214203951) missing classes in conscrypt
-            throw new ProviderException("Curve " + ED25519_OID + " not supported yet");
+            final byte[] publicKeyEncoded = publicKey.getEncoded();
+            return new AndroidKeyStoreEdECPublicKey(descriptor, metadata, ED25519_OID,
+                    iSecurityLevel, publicKeyEncoded);
         } else if (X25519_ALIAS.equalsIgnoreCase(jcaKeyAlgorithm)) {
             //TODO(b/214203951) missing classes in conscrypt
             throw new ProviderException("Curve " + X25519_ALIAS + " not supported yet");