Use Base62 for tokens and Base58 for keys

 * Base62 minimizes extra size overhead relative to Base64.
 * Base58 removes ambiguous characters from key encodings.

Common for both bases is that they do not emit any characters that
interfer with easily selecting them on web pages or in the CLI.

4 files changed, 55 insertions, 11 deletions

diff --git a/security-utils/src/main/java/com/yahoo/security/KeyUtils.java b/security-utils/src/main/java/com/yahoo/security/KeyUtils.java
index cef0dd9a62e..47055a65618 100644
--- a/security-utils/src/main/java/com/yahoo/security/KeyUtils.java
+++ b/security-utils/src/main/java/com/yahoo/security/KeyUtils.java
@@ -280,6 +280,25 @@ public class KeyUtils {
         return Base64.getUrlEncoder().withoutPadding().encodeToString(toRawX25519PublicKeyBytes(publicKey));
     }
 
+    // This sanity check is to avoid any DoS potential caused by passing in a very large key
+    // to a quadratic Base58 decoding routing. We don't do this for the encoding since we
+    // always control the input size for that case.
+    private static void verifyB58InputSmallEnoughToBeX25519Key(String key) {
+        if (key.length() > 64) { // a very wide margin...
+            throw new IllegalArgumentException("Input Base58 is too large to represent an X25519 key");
+        }
+    }
+
+    public static XECPublicKey fromBase58EncodedX25519PublicKey(String base58pk) {
+        verifyB58InputSmallEnoughToBeX25519Key(base58pk);
+        byte[] rawKeyBytes = Base58.codec().decode(base58pk);
+        return fromRawX25519PublicKey(rawKeyBytes);
+    }
+
+    public static String toBase58EncodedX25519PublicKey(XECPublicKey publicKey) {
+        return Base58.codec().encode(toRawX25519PublicKeyBytes(publicKey));
+    }
+
     public static XECPrivateKey fromRawX25519PrivateKey(byte[] rawScalarBytes) {
         try {
             NamedParameterSpec paramSpec = new NamedParameterSpec("X25519");
@@ -309,6 +328,16 @@ public class KeyUtils {
         return Base64.getUrlEncoder().withoutPadding().encodeToString(toRawX25519PrivateKeyBytes(privateKey));
     }
 
+    public static XECPrivateKey fromBase58EncodedX25519PrivateKey(String base58pk) {
+        verifyB58InputSmallEnoughToBeX25519Key(base58pk);
+        byte[] rawKeyBytes = Base58.codec().decode(base58pk);
+        return fromRawX25519PrivateKey(rawKeyBytes);
+    }
+
+    public static String toBase58EncodedX25519PrivateKey(XECPrivateKey privateKey) {
+        return Base58.codec().encode(toRawX25519PrivateKeyBytes(privateKey));
+    }
+
     // TODO unify with generateKeypair()?
     public static KeyPair generateX25519KeyPair() {
         try {
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 a921b3baf87..65f149579f4 100644
--- a/security-utils/src/main/java/com/yahoo/security/SealedSharedKey.java
+++ b/security-utils/src/main/java/com/yahoo/security/SealedSharedKey.java
@@ -2,11 +2,6 @@
 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.
@@ -51,7 +46,7 @@ public record SealedSharedKey(KeyId keyId, byte[] enc, byte[] ciphertext) {
 
         byte[] encBytes = new byte[encoded.remaining()];
         encoded.get(encBytes);
-        return Base64.getUrlEncoder().withoutPadding().encodeToString(encBytes);
+        return Base62.codec().encode(encBytes);
     }
 
     /**
@@ -59,7 +54,8 @@ public record SealedSharedKey(KeyId keyId, byte[] enc, byte[] ciphertext) {
      * created by a call to toTokenString().
      */
     public static SealedSharedKey fromTokenString(String tokenString) {
-        byte[] rawTokenBytes = Base64.getUrlDecoder().decode(tokenString);
+        verifyInputTokenStringNotTooLarge(tokenString);
+        byte[] rawTokenBytes = Base62.codec().decode(tokenString);
         if (rawTokenBytes.length < 1) {
             throw new IllegalArgumentException("Decoded token too small to contain a version");
         }
@@ -84,4 +80,12 @@ public record SealedSharedKey(KeyId keyId, byte[] enc, byte[] ciphertext) {
 
     public int tokenVersion() { return CURRENT_TOKEN_VERSION; }
 
+    private static void verifyInputTokenStringNotTooLarge(String tokenString) {
+        // Expected max decoded size for v1 is 3 + 255 + 32 + 32 = 322. For simplicity, round this
+        // up to 512 to effectively not have to care about the overhead of any reasonably chosen encoding.
+        if (tokenString.length() > 512) {
+            throw new IllegalArgumentException("Token string is too long to possibly be a valid token");
+        }
+    }
+
 }
diff --git a/security-utils/src/test/java/com/yahoo/security/KeyUtilsTest.java b/security-utils/src/test/java/com/yahoo/security/KeyUtilsTest.java
index dc6078c58b7..f44eadc59d4 100644
--- a/security-utils/src/test/java/com/yahoo/security/KeyUtilsTest.java
+++ b/security-utils/src/test/java/com/yahoo/security/KeyUtilsTest.java
@@ -155,9 +155,15 @@ public class KeyUtilsTest {
         var priv = xecPrivFromHex(privHex);
         assertEquals(privHex, xecHexFromPriv(priv));
 
+        // Base 64
         var privB64 = KeyUtils.toBase64EncodedX25519PrivateKey(priv);
         var priv2 = KeyUtils.fromBase64EncodedX25519PrivateKey(privB64);
         assertEquals(privHex, xecHexFromPriv(priv2));
+
+        // Base 58
+        var privB58 = KeyUtils.toBase58EncodedX25519PrivateKey(priv);
+        var priv3 = KeyUtils.fromBase58EncodedX25519PrivateKey(privB58);
+        assertEquals(privHex, xecHexFromPriv(priv3));
     }
 
     @Test
@@ -166,9 +172,15 @@ public class KeyUtilsTest {
         var pub = xecPubFromHex(pubHex);
         assertEquals(pubHex, xecHexFromPub(pub));
 
+        // Base 64
         var pubB64 = KeyUtils.toBase64EncodedX25519PublicKey(pub);
         var pub2 = KeyUtils.fromBase64EncodedX25519PublicKey(pubB64);
         assertEquals(pubHex, xecHexFromPub(pub2));
+
+        // Base 58
+        var pubB58 = KeyUtils.toBase58EncodedX25519PublicKey(pub);
+        var pub3 = KeyUtils.fromBase58EncodedX25519PublicKey(pubB58);
+        assertEquals(pubHex, xecHexFromPub(pub3));
     }
 
     @Test
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 74b4ca0854b..4e64bc3e9aa 100644
--- a/security-utils/src/test/java/com/yahoo/security/SharedKeyTest.java
+++ b/security-utils/src/test/java/com/yahoo/security/SharedKeyTest.java
@@ -14,7 +14,6 @@ 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;
@@ -47,12 +46,12 @@ public class SharedKeyTest {
 
     @Test
     void token_v1_representation_is_stable() {
-        var receiverPrivate = KeyUtils.fromBase64EncodedX25519PrivateKey("4qGcntygFn_a3uqeBa1PbDlygQ-cpOuNznTPIz9ftWE");
-        var receiverPublic  = KeyUtils.fromBase64EncodedX25519PublicKey( "ROAH_S862tNMpbJ49lu1dPXFCPHFIXZK30pSrMZEmEg");
+        var receiverPrivate = KeyUtils.fromBase58EncodedX25519PrivateKey("GFg54SaGNCmcSGufZCx68SKLGuAFrASoDeMk3t5AjU6L");
+        var receiverPublic  = KeyUtils.fromBase58EncodedX25519PublicKey( "5drrkakYLjYSBpr5Haknh13EiCYL36ndMzK4gTJo6pwh");
         var keyId           = KeyId.ofString("my key ID");
 
         // Token generated for the above receiver public key, with the below expected shared secret (in hex)
-        var publicToken = "AQlteSBrZXkgSUQgAtTxJJdmv3eUoW5Z3NJSdZ3poKPEkW0SJOGQXP6CaC5XfyAVoUlK_NyYIMsJKyNYKU6WmagZpVG2zQGFJoqiFA";
+        var publicToken = "OntP9gRVAjXeZIr4zkYqRJFcnA993v7ZEE7VbcNs1NcR3HdE7Mpwlwi3r3anF1kVa5fn7O1CyeHQpBWpdayUTKkrtyFepG6WJrZdE";
         var expectedSharedSecret = "1b33b4dcd6a94e5a4a1ee6d208197d01";
 
         var theirSealed = SealedSharedKey.fromTokenString(publicToken);