X25519 KeyFactory can resolve to AndroidKeyStore, breaking curve25519 KEX on some Android devices

[GlassOnTin]

On some Android devices, every connection that negotiates curve25519-sha256 fails during key exchange with:

java.security.spec.InvalidKeySpecException: To generate a key pair in Android Keystore,
use KeyPairGenerator initialized with android.security.keystore.KeyGenParameterSpec
    at android.security.keystore2.AndroidKeyStoreKeyFactorySpi.engineGeneratePublic(AndroidKeyStoreKeyFactorySpi.java:127)
    at java.security.KeyFactory.generatePublic(KeyFactory.java:373)

Reported against Haven on Android 16 (GlassHaven/Haven#451). Not universal — I run the same version on Android 16 without hitting it — so it depends on which JCE provider wins the lookup on a given build.

Cause

PlatformX25519Provider resolves both primitives without naming a provider:

private val keyPairGenerator = KeyPairGenerator.getInstance(ALGORITHM)
private val keyFactory = KeyFactory.getInstance(ALGORITHM)

On the affected device the KeyFactory lookup lands on AndroidKeyStore, which by design only produces keys backed by the keystore. Converting a peer's ephemeral X25519 public key from an X509EncodedKeySpec is something it can never do, so createPublicKey() throws on the first shared-secret computation.

Why the availability probe does not catch it

X25519ProviderFactory decides between platform and Tink like this:

private fun isPlatformNativeAvailable(): Boolean = try {
    KeyPairGenerator.getInstance("X25519")
    Class.forName("java.security.spec.XECPrivateKeySpec")
    true
} catch (_: Exception) { false }

It probes the KeyPairGenerator and then the provider uses a separately-resolved KeyFactory. Those two lookups can resolve to different providers, and on the affected device they do: key generation succeeds — the reported failure is at generatePublic, which is reached only after generatePrivateKey() has already worked — while the KeyFactory is AndroidKeyStore. So the probe passes and the operation still fails.

Constructing the objects also proves nothing here: KeyFactory.getInstance succeeds for AndroidKeyStore; only the later generatePublic call rejects the spec.

Suggested fix

Whichever of these you prefer:

1. Name the provider. Both lookups want a software implementation of raw X25519 — on Android that is AndroidOpenSSL (Conscrypt). AndroidKeyStore is never a valid answer for raw key material, so it could also simply be excluded by name.
2. Probe with a real round-trip. Generate a key pair, encode the public key, and feed it back through keyFactory.generatePublic() inside the try. That exercises the exact call that fails and falls back to Tink correctly.

The second is the more robust shape, since it validates the primitives actually used rather than a proxy for them.

Note for the fallback path

Worth flagging because it affects how the fallback behaves in practice: consumers who exclude Tink (Haven does, to keep the JVM Tink artifact out of an Android build) have no fallback available if the platform path is rejected. That is our problem rather than yours, but it means fix (1) — making the platform path work — is materially more useful to us than fix (2) alone.

Happy to test a patch against the affected device via the reporter; I cannot reproduce it on my own hardware.

[GlassOnTin]

Follow-up with a device log, because it narrows this usefully and rules out the obvious workaround.

I shipped a downstream mitigation that moves AndroidKeyStore to the end of the JCE provider list when it wins an unpinned raw-key KeyFactory lookup. On the affected device it ran and the connection failed anyway:

W RawKeyProviderOrder: AndroidKeyStore was first for an unpinned Ed25519 KeyFactory — moved to the end of the provider list
...
INFO   Negotiated KEX: mlkem768x25519-sha256
INFO   Negotiated host key: ssh-ed25519
INFO   Received ECDH_REPLY from server
ERROR  Connection failed: TransportError(cause=java.security.spec.InvalidKeySpecException:
       To generate a key pair in Android Keystore, use KeyPairGenerator initialized with
       android.security.keystore.KeyGenParameterSpec)
  at android.security.keystore2.AndroidKeyStoreKeyFactorySpi.engineGeneratePublic(AndroidKeyStoreKeyFactorySpi.java:127)
  at java.security.KeyFactory.generatePublic(KeyFactory.java:373)

Two things worth taking from that:

Reordering providers is not a workaround. It only helps when some other provider is willing to serve the algorithm. On this ROM AndroidKeyStore appears to be the only one registering that KeyFactory, so demoting it to last place changes nothing — last is still the only choice. Anyone hitting this cannot fix it from outside the library by adjusting provider order.

It is not confined to X25519. The failure here is on the ed25519 host key, reading it out of ECDH_REPLY — a different call site from the curve25519 shared-secret path this issue was opened about. The device also negotiated mlkem768x25519-sha256 rather than plain curve25519. So the same unpinned-lookup pattern bites wherever a peer's raw key is reconstructed, which suggests the fix wants to be a general policy rather than a patch at one call site.

Naming the provider explicitly at the point of the lookup — or resolving once at startup to a provider that has been verified to accept an X509EncodedKeySpec and reusing it — would close all of these together. Happy to put a PR together if you would like it, and to say which shape you would prefer.

Reported downstream at GlassHaven/Haven#451, where the reporter's full log is attached.

[GlassOnTin]

Confirmed on the affected device, which pins the mechanism precisely and rules out the obvious workaround.

After instrumenting the downstream mitigation to report where each raw-key algorithm resolves after reordering, the reporter's device says:

X25519=AndroidOpenSSL, XDH=AndroidOpenSSL, Ed25519=BC, EC=AndroidOpenSSL

So on that ROM (RedMagic 11 Air, official firmware) AndroidKeyStore is the only provider registering an Ed25519 KeyFactory. Three of the four algorithms had a working provider all along and merely lost the ordering race; Ed25519 had none, and only resolved once a provider that implements it was registered explicitly.

Two consequences worth recording here:

Reordering providers is not a viable workaround. It only helps where an alternative exists. Where the key store is the sole registrant, moving it to the end of the list changes nothing — it is still the only candidate. A downstream mitigation that only reordered shipped, ran, logged that it ran, and the connection failed anyway.

The failing call site is host-key parsing, not just the KEX shared secret. The device negotiated mlkem768x25519-sha256 with an ssh-ed25519 host key and died immediately after ECDH_REPLY, reconstructing the peer's raw ed25519 key. This issue was opened about X25519; the same unpinned-lookup pattern applies wherever a peer's raw key is rebuilt from an encoded spec, which argues for a general policy over a per-call-site patch.

Resolving the provider once at startup — preferring one that has been verified to accept an X509EncodedKeySpec for the algorithm, and never silently accepting a key-store provider for raw key material — would cover all of these. Still happy to prepare a PR; just say which shape you would prefer.

Downstream fix shipped and confirmed by the reporter in GlassHaven/Haven#451 (now closed), including jump-host and Tailscale paths.