Let token key IDs be UTF-8 byte strings instead of just an integer

This makes key IDs vastly more expressive. Max size is 255 bytes,
and UTF-8 form is enforced by checking that the byte sequence can be
identity-transformed to and from a string with UTF-8 encoding.

In addition, we now protect the integrity of the key ID by supplying
it as the AAD parameter to the key sealing and opening operations.

Reduce v1 token max length of `enc` part to 255, since this is always
an X25519 public key, which is never bigger than 32 bytes (but may
be _less_ if the random `BigInteger` is small enough, so we still have
to encode the length).

3 files changed, 119 insertions, 37 deletions

diff --git a/security-utils/src/main/java/com/yahoo/security/SealedSharedKey.java b/security-utils/src/main/java/com/yahoo/security/SealedSharedKey.java
index 9c379b67a23..fe1be85539c 100644
--- a/security-utils/src/main/java/com/yahoo/security/SealedSharedKey.java
+++ b/security-utils/src/main/java/com/yahoo/security/SealedSharedKey.java
@@ -2,8 +2,12 @@
 package com.yahoo.security;
 
 import java.nio.ByteBuffer;
+import java.util.Arrays;
 import java.util.Base64;
 
+import static com.yahoo.security.ArrayUtils.fromUtf8Bytes;
+import static com.yahoo.security.ArrayUtils.toUtf8Bytes;
+
 /**
  * A SealedSharedKey represents the public part of a secure one-way ephemeral key exchange.
  *
@@ -15,29 +19,37 @@ import java.util.Base64;
  * This token representation is expected to be used as a convenient serialization
  * form when communicating shared keys.
  */
-public record SealedSharedKey(int keyId, byte[] enc, byte[] ciphertext) {
+public record SealedSharedKey(byte[] keyId, byte[] enc, byte[] ciphertext) {
 
     /** Current encoding version of opaque sealed key tokens. Must be less than 256. */
     public static final int CURRENT_TOKEN_VERSION = 1;
+    public static final int MAX_KEY_ID_UTF8_LENGTH = 255;
+    /** Encryption context for v1 tokens is always a 32-byte X25519 public key */
+    public static final int MAX_ENC_CONTEXT_LENGTH = 255;
 
-    private static final int MAX_ENC_CONTEXT_LENGTH = Short.MAX_VALUE;
+    public SealedSharedKey {
+        if (keyId.length > MAX_KEY_ID_UTF8_LENGTH) {
+            throw new IllegalArgumentException("Key ID is too large to be encoded (max is %d, got %d)"
+                    .formatted(MAX_KEY_ID_UTF8_LENGTH, keyId.length));
+        }
+        verifyByteStringRoundtripsAsValidUtf8(keyId);
+        if (enc.length > MAX_ENC_CONTEXT_LENGTH) {
+            throw new IllegalArgumentException("Encryption context is too large to be encoded (max is %d, got %d)"
+                    .formatted(MAX_ENC_CONTEXT_LENGTH, enc.length));
+        }
+    }
 
     /**
      * Creates an opaque URL-safe string token that contains enough information to losslessly
      * reconstruct the SealedSharedKey instance when passed verbatim to fromTokenString().
      */
     public String toTokenString() {
-        if (keyId >= (1 << 24)) {
-            throw new IllegalArgumentException("Key id is too large to be encoded");
-        }
-        if (enc.length > MAX_ENC_CONTEXT_LENGTH) {
-            throw new IllegalArgumentException("Encryption context is too large to be encoded");
-        }
-
-        // i32 header || i16 length(enc) || enc || ciphertext
-        ByteBuffer encoded = ByteBuffer.allocate(4 + 2 + enc.length + ciphertext.length);
-        encoded.putInt((CURRENT_TOKEN_VERSION << 24) | keyId);
-        encoded.putShort((short)enc.length);
+        // u8 token version || u8 length(key id) || key id || u8 length(enc) || enc || ciphertext
+        ByteBuffer encoded = ByteBuffer.allocate(1 + 1 + keyId.length + 1 + enc.length + ciphertext.length);
+        encoded.put((byte)CURRENT_TOKEN_VERSION);
+        encoded.put((byte)keyId.length);
+        encoded.put(keyId);
+        encoded.put((byte)enc.length);
         encoded.put(enc);
         encoded.put(ciphertext);
         encoded.flip();
@@ -53,27 +65,37 @@ public record SealedSharedKey(int keyId, byte[] enc, byte[] ciphertext) {
      */
     public static SealedSharedKey fromTokenString(String tokenString) {
         byte[] rawTokenBytes = Base64.getUrlDecoder().decode(tokenString);
-        if (rawTokenBytes.length < 4) {
-            throw new IllegalArgumentException("Decoded token too small to contain a header");
+        if (rawTokenBytes.length < 1) {
+            throw new IllegalArgumentException("Decoded token too small to contain a version");
         }
         ByteBuffer decoded = ByteBuffer.wrap(rawTokenBytes);
-        int versionAndKeyId = decoded.getInt();
-        int version = versionAndKeyId >>> 24;
+        // u8 token version || u8 length(key id) || key id || u8 length(enc) || enc || ciphertext
+        int version = Byte.toUnsignedInt(decoded.get());
         if (version != CURRENT_TOKEN_VERSION) {
             throw new IllegalArgumentException("Token had unexpected version. Expected %d, was %d"
                                                .formatted(CURRENT_TOKEN_VERSION, version));
         }
-        short encLen = decoded.getShort();
-        if (encLen <= 0) {
-            throw new IllegalArgumentException("Token encryption context does not have a valid length");
-        }
+        int keyIdLen = Byte.toUnsignedInt(decoded.get());
+        byte[] keyId = new byte[keyIdLen];
+        decoded.get(keyId);
+        verifyByteStringRoundtripsAsValidUtf8(keyId);
+        int encLen = Byte.toUnsignedInt(decoded.get());
         byte[] enc = new byte[encLen];
         decoded.get(enc);
         byte[] ciphertext = new byte[decoded.remaining()];
         decoded.get(ciphertext);
 
-        int keyId = versionAndKeyId & 0xffffff;
         return new SealedSharedKey(keyId, enc, ciphertext);
     }
 
+    private static void verifyByteStringRoundtripsAsValidUtf8(byte[] byteStr) {
+        String asStr   = fromUtf8Bytes(byteStr); // Replaces bad chars with a placeholder
+        byte[] asBytes = toUtf8Bytes(asStr);
+        if (!Arrays.equals(byteStr, asBytes)) {
+            throw new IllegalArgumentException("Key ID is not valid normalized UTF-8");
+        }
+    }
+
+    public int tokenVersion() { return CURRENT_TOKEN_VERSION; }
+
 }
diff --git a/security-utils/src/main/java/com/yahoo/security/SharedKeyGenerator.java b/security-utils/src/main/java/com/yahoo/security/SharedKeyGenerator.java
index f9a16a78013..47936dab114 100644
--- a/security-utils/src/main/java/com/yahoo/security/SharedKeyGenerator.java
+++ b/security-utils/src/main/java/com/yahoo/security/SharedKeyGenerator.java
@@ -60,18 +60,17 @@ public class SharedKeyGenerator {
         }
     }
 
-    public static SecretSharedKey generateForReceiverPublicKey(PublicKey receiverPublicKey, int keyId) {
+    public static SecretSharedKey generateForReceiverPublicKey(PublicKey receiverPublicKey, byte[] keyId) {
         var secretKey = generateRandomSecretAesKey();
-        // TODO do we want to tie the key ID to the sealing via AAD?
-        var sealed = HPKE.sealBase((XECPublicKey) receiverPublicKey, EMPTY_BYTES, EMPTY_BYTES, secretKey.getEncoded());
+        // We protect the integrity of the key ID by passing it as AAD.
+        var sealed = HPKE.sealBase((XECPublicKey) receiverPublicKey, EMPTY_BYTES, keyId, secretKey.getEncoded());
         var sealedSharedKey = new SealedSharedKey(keyId, sealed.enc(), sealed.ciphertext());
         return new SecretSharedKey(secretKey, sealedSharedKey);
     }
 
     public static SecretSharedKey fromSealedKey(SealedSharedKey sealedKey, PrivateKey receiverPrivateKey) {
-        // TODO do we want to tie the key ID to the opening via AAD?
         byte[] secretKeyBytes = HPKE.openBase(sealedKey.enc(), (XECPrivateKey) receiverPrivateKey,
-                                              EMPTY_BYTES, EMPTY_BYTES, sealedKey.ciphertext());
+                                              EMPTY_BYTES, sealedKey.keyId(), sealedKey.ciphertext());
         return new SecretSharedKey(new SecretKeySpec(secretKeyBytes, "AES"), sealedKey);
     }
 
diff --git a/security-utils/src/test/java/com/yahoo/security/SharedKeyTest.java b/security-utils/src/test/java/com/yahoo/security/SharedKeyTest.java
index 3a1952da49d..f635121eda0 100644
--- a/security-utils/src/test/java/com/yahoo/security/SharedKeyTest.java
+++ b/security-utils/src/test/java/com/yahoo/security/SharedKeyTest.java
@@ -10,18 +10,23 @@ import java.io.ByteArrayOutputStream;
 import java.io.IOException;
 import java.nio.ByteBuffer;
 import java.nio.charset.StandardCharsets;
+import java.util.Arrays;
+import java.util.Base64;
 
 import static com.yahoo.security.ArrayUtils.hex;
+import static com.yahoo.security.ArrayUtils.toUtf8Bytes;
 import static org.junit.jupiter.api.Assertions.assertArrayEquals;
 import static org.junit.jupiter.api.Assertions.assertEquals;
 import static org.junit.jupiter.api.Assertions.assertThrows;
 
 public class SharedKeyTest {
 
+    private static final byte[] KEY_ID_1 = new byte[] {1};
+
     @Test
     void generated_secret_key_is_128_bit_aes() {
         var receiverKeyPair = KeyUtils.generateX25519KeyPair();
-        var shared = SharedKeyGenerator.generateForReceiverPublicKey(receiverKeyPair.getPublic(), 1);
+        var shared = SharedKeyGenerator.generateForReceiverPublicKey(receiverKeyPair.getPublic(), KEY_ID_1);
         var secret = shared.secretKey();
         assertEquals(secret.getAlgorithm(), "AES");
         assertEquals(secret.getEncoded().length, 16);
@@ -31,7 +36,7 @@ public class SharedKeyTest {
     void sealed_shared_key_can_be_exchanged_via_token_and_computes_identical_secret_key_at_receiver() {
         var receiverKeyPair = KeyUtils.generateX25519KeyPair();
 
-        var myShared    = SharedKeyGenerator.generateForReceiverPublicKey(receiverKeyPair.getPublic(), 1);
+        var myShared    = SharedKeyGenerator.generateForReceiverPublicKey(receiverKeyPair.getPublic(), KEY_ID_1);
         var publicToken = myShared.sealedSharedKey().toTokenString();
 
         var theirSealed = SealedSharedKey.fromTokenString(publicToken);
@@ -44,15 +49,16 @@ public class SharedKeyTest {
     void token_v1_representation_is_stable() {
         var receiverPrivate = KeyUtils.fromBase64EncodedX25519PrivateKey("4qGcntygFn_a3uqeBa1PbDlygQ-cpOuNznTPIz9ftWE");
         var receiverPublic  = KeyUtils.fromBase64EncodedX25519PublicKey( "ROAH_S862tNMpbJ49lu1dPXFCPHFIXZK30pSrMZEmEg");
+        byte[] keyId        = toUtf8Bytes("my key ID");
 
         // Token generated for the above receiver public key, with the below expected shared secret (in hex)
-        var publicToken = "AQAAAQAgwyxd7bFNQB_2LdL3bw-xFlvrxXhs7WWNVCKZ4EFeNVtu42JMwM74bMN4E46v6mYcfQNPzcMGaP22Wl2cTnji0A";
-        var expectedSharedSecret = "85ac3c7c3a930a19334cb73e02779733";
+        var publicToken = "AQlteSBrZXkgSUQgAtTxJJdmv3eUoW5Z3NJSdZ3poKPEkW0SJOGQXP6CaC5XfyAVoUlK_NyYIMsJKyNYKU6WmagZpVG2zQGFJoqiFA";
+        var expectedSharedSecret = "1b33b4dcd6a94e5a4a1ee6d208197d01";
 
         var theirSealed = SealedSharedKey.fromTokenString(publicToken);
         var theirShared = SharedKeyGenerator.fromSealedKey(theirSealed, receiverPrivate);
 
-        assertEquals(1, theirSealed.keyId());
+        assertArrayEquals(keyId, theirSealed.keyId());
         assertEquals(expectedSharedSecret, hex(theirShared.secretKey().getEncoded()));
     }
 
@@ -60,19 +66,74 @@ public class SharedKeyTest {
     void unrelated_private_key_cannot_decrypt_shared_secret_key() {
         var aliceKeyPair = KeyUtils.generateX25519KeyPair();
         var eveKeyPair   = KeyUtils.generateX25519KeyPair();
-        var bobShared    = SharedKeyGenerator.generateForReceiverPublicKey(aliceKeyPair.getPublic(), 1);
+        var bobShared    = SharedKeyGenerator.generateForReceiverPublicKey(aliceKeyPair.getPublic(), KEY_ID_1);
         assertThrows(RuntimeException.class, // TODO consider distinct exception class
                      () -> SharedKeyGenerator.fromSealedKey(bobShared.sealedSharedKey(), eveKeyPair.getPrivate()));
     }
 
     @Test
-    void token_carries_key_id_as_metadata() {
-        int keyId       = 12345;
+    void token_carries_opaque_key_id_bytes_as_metadata() {
+        byte[] keyId    = toUtf8Bytes("hello key id world");
         var keyPair     = KeyUtils.generateX25519KeyPair();
         var myShared    = SharedKeyGenerator.generateForReceiverPublicKey(keyPair.getPublic(), keyId);
         var publicToken = myShared.sealedSharedKey().toTokenString();
         var theirShared = SealedSharedKey.fromTokenString(publicToken);
-        assertEquals(theirShared.keyId(), keyId);
+        assertArrayEquals(theirShared.keyId(), keyId);
+    }
+
+    @Test
+    void key_id_integrity_is_protected_by_aad() {
+        byte[] goodId = toUtf8Bytes("my key 1");
+        var keyPair   = KeyUtils.generateX25519KeyPair();
+        var myShared  = SharedKeyGenerator.generateForReceiverPublicKey(keyPair.getPublic(), goodId);
+        var mySealed  = myShared.sealedSharedKey();
+        byte[] badId  = toUtf8Bytes("my key 2");
+
+        var tamperedShared = new SealedSharedKey(badId, mySealed.enc(), mySealed.ciphertext());
+        // Should not be able to unseal the token since the AAD auth tag won't be correct
+        assertThrows(RuntimeException.class, // TODO consider distinct exception class
+                     () -> SharedKeyGenerator.fromSealedKey(tamperedShared, keyPair.getPrivate()));
+    }
+
+    @Test
+    void key_id_encoding_size_is_bounded() {
+        byte[] okId = new byte[SealedSharedKey.MAX_KEY_ID_UTF8_LENGTH];
+        Arrays.fill(okId, (byte)'A');
+        var keyPair  = KeyUtils.generateX25519KeyPair();
+        var myShared = SharedKeyGenerator.generateForReceiverPublicKey(keyPair.getPublic(), okId);
+        assertArrayEquals(okId, myShared.sealedSharedKey().keyId());
+
+        var asToken = myShared.sealedSharedKey().toTokenString();
+        var decoded = SealedSharedKey.fromTokenString(asToken);
+        assertArrayEquals(okId, decoded.keyId());
+
+        byte[] tooBigId = new byte[SealedSharedKey.MAX_KEY_ID_UTF8_LENGTH + 1];
+        Arrays.fill(tooBigId, (byte)'A');
+        assertThrows(IllegalArgumentException.class,
+                     () -> SharedKeyGenerator.generateForReceiverPublicKey(keyPair.getPublic(), tooBigId));
+    }
+
+    @Test
+    void malformed_utf8_key_id_is_rejected_on_construction() {
+        byte[] malformedId = new byte[]{ (byte)0xC0 }; // First part of a 2-byte continuation without trailing byte
+        var keyPair = KeyUtils.generateX25519KeyPair();
+        assertThrows(IllegalArgumentException.class,
+                     () -> SharedKeyGenerator.generateForReceiverPublicKey(keyPair.getPublic(), malformedId));
+    }
+
+    // TODO make this test less implementation specific if possible...
+    @Test
+    void malformed_utf8_key_id_is_rejected_on_parsing() {
+        byte[] goodId = new byte[] { (byte)'A' };
+        var keyPair   = KeyUtils.generateX25519KeyPair();
+        var myShared  = SharedKeyGenerator.generateForReceiverPublicKey(keyPair.getPublic(), goodId);
+
+        // token header is u8 version || u8 key id length || key id bytes ...
+        // Since the key ID is only 1 bytes long, patch it with a bad UTF-8 value (see above test)
+        byte[] tokenBytes = Base64.getUrlDecoder().decode(myShared.sealedSharedKey().toTokenString());
+        tokenBytes[2] = (byte)0xC0;
+        var tokenStr = Base64.getUrlEncoder().encodeToString(tokenBytes);
+        assertThrows(IllegalArgumentException.class, () -> SealedSharedKey.fromTokenString(tokenStr));
     }
 
     static byte[] streamEncryptString(String data, SecretSharedKey secretSharedKey) throws IOException {
@@ -108,7 +169,7 @@ public class SharedKeyTest {
     @Test
     void can_create_symmetric_ciphers_from_shared_secret_key_and_public_keys() throws Exception {
         var receiverKeyPair = KeyUtils.generateX25519KeyPair();
-        var myShared        = SharedKeyGenerator.generateForReceiverPublicKey(receiverKeyPair.getPublic(), 1);
+        var myShared        = SharedKeyGenerator.generateForReceiverPublicKey(receiverKeyPair.getPublic(), KEY_ID_1);
 
         String terrifyingSecret = "birds are not real D:";
         byte[] encrypted = streamEncryptString(terrifyingSecret, myShared);