Storing End-to-End Encryption Keys on the Device: Keychain, Keystore, and the New-Phone Problem

The Bug Report That Said "All My Messages Are Gone"

We added end to end encryption to Sync because a realtime super app that carries private messages has no business reading them. The cryptography was the calm part: libraries exist, the protocol is well understood, and if you don't invent your own crypto you mostly stay out of trouble.

What ate my time was where the private keys live on the device, and what happens to them on reinstalls, biometric changes, background wakeups, and the user buying a new phone. Every one turned into a support ticket. The worst said: "I reinstalled the app and now all my messages are gibberish."

This is the mobile side of E2EE, since the device is where it went wrong.

Where Keys Actually Live

Each device has an identity key pair. The private key never leaves the device. Everything is encrypted to public keys, so only the recipient's device, holding the matching private key, can decrypt it. The server relays ciphertext and never sees a private key. So the security of the system comes down to one question: how safe is that private key on the phone, and can I get to it when I need it?

On iOS, private keys go in the Keychain, and where possible we back them with the Secure Enclave: a separate hardware coprocessor that generates and holds keys so the raw private key never enters the app's memory. You ask the Enclave to sign or decrypt; you never see the key material. On Android the equivalent is the Android Keystore, backed on modern devices by a hardware security module or Trusted Execution Environment. Same property: the key lives behind a wall and you get operations, not bytes.

That hardware backing is great for security and it is exactly what creates the operational problems. When the key lives somewhere your app can't see or control, the platform decides its availability and lifetime, and not always the way your app expects.

The After First Unlock Trap

The first problem was Keychain accessibility, and it cost me a confusing week.

A Keychain item's accessibility class controls when it can be read. The strictest useful one, roughly "when unlocked," means readable only while the device is unlocked. "After first unlock" keeps the item readable from the first unlock after a boot until the next reboot, even if the screen locks again.

I had picked the strictest option because stricter sounds safer. Then background sync started failing silently for some users, always in the morning, always right after they picked up their phone. The timeline explained it: the phone had rebooted overnight, the user hadn't unlocked it yet, and a push woke the app for a background sync while the device was still locked. Our sync code went to read the identity key to decrypt incoming data, and the Keychain refused because the device had never been unlocked since boot. The key was there. It just wasn't readable yet.

The fix was to work out which keys a background task actually needs and store those with "after first unlock," so they survive a screen lock but still require one unlock since boot. Keys used only while the user is in the app can stay stricter. Accessibility is not a "more is better" dial; you match the key to when you need it, and background execution is the case people forget.

The Uninstall That Wasn't Clean

Then came the reinstall ticket, which broke an assumption I didn't know I was making.

I assumed uninstalling an app wipes everything it stored. On Android that is basically true. On iOS it is not: Keychain items can outlive the app that created them. Delete the app, reinstall it, and the old Keychain entries, including your E2EE identity key, can still be there under the same access group, ready for the reinstalled app to read.

The app's regular storage, our local database of message history and session state, does get wiped. So a reinstall left the private key intact but the encrypted database it was meant to unlock gone and pulled down fresh from the server. New session state, old key, and the two no longer agreed. The user saw decryption failures: gibberish.

We fixed it by making the key lifecycle explicit instead of trusting the platform's cleanup. On a fresh install we check whether we are truly fresh, using a flag in the database because we know that gets wiped, or whether stale Keychain material is hanging around. Then either reuse the surviving key and set up sessions against it, or clear it and register a new device identity. The bug was never the crypto. It was assuming two storage layers with different lifetimes would stay in sync on their own.

When Android Throws Your Keys Away

Android had the opposite problem. Instead of keys surviving too long, they vanished.

Android Keystore lets you bind a key to the device's biometric or lock screen state, so the key is only usable when the user authenticates. The fine print: if the user changes their biometric enrollment or their lock screen credential, the system can permanently invalidate keys bound to that state. Add a new fingerprint, change the PIN, and keys tied to current biometrics are gone. Not locked out temporarily; invalidated.

We hit this when users who updated their fingerprints couldn't decrypt anything. The Keystore operation throws a specific invalidation error and there is no recovering the key. The only response is to treat it as dead, generate a fresh device identity, register the new public key with the server, and tell the user what happened instead of failing silently. Keys on the device are not permanent records. They are capabilities the platform can pull at any time, so the app has to be able to build a new identity.

One Identity Per Device

A decision that saved us a lot of pain: each device is its own cryptographic identity with its own key pair, and we never sync a private key between devices. Your phone and your tablet are two separate members of your account, each publishing its own public key. A message to you is encrypted separately to every one of your devices.

That is more work, because sessions exist per device and adding a device means the sender's app fetches the new public key and starts a fresh session. But no private key ever crosses the network or leaves a Secure Enclave built specifically to never let it out. Revocation is clean too: lose a device, revoke that identity, and the others are unaffected. The cost is that "your account" is really "the set of your devices," which is what makes the next problem hard.

The New Phone Problem

This is where security and user experience pull against each other.

If the private key never leaves the device, and each device is its own identity, a new phone starts with nothing. It cannot read a single old message, because the key that could decrypt your history sits in the Secure Enclave of a phone now in a drawer or wiped and traded in. Your entire history is unreadable to the new device, by design. The first time a beta tester upgraded phones and watched years of conversations render as encrypted noise, the reaction was not "strong security." It was "your app lost my messages."

They're not wrong to be upset. This is the cost of real E2EE: if the server can't read your data, it can't restore it either. There is no "reset my password and get my history back," because there's no key on the server to hand over.

The Recovery Phrase

We squared this without giving the server the ability to read messages: an optional encrypted backup protected by a recovery phrase.

If the user turns it on, we generate a high entropy recovery phrase on the device, a sequence of random words, and derive a backup key from it. We encrypt a bundle of the user's key material and message history with that key and store the encrypted blob on the server. The server holds ciphertext and nothing else; it never sees the phrase and can't derive the key. The phrase lives only in the user's head or their password manager. We made that their responsibility with a blunt warning screen: lose the phrase and the backup is gone, and we cannot help.

On the new phone, restore is the reverse: the user enters the recovery phrase, the device derives the backup key again, pulls the encrypted blob from the server, decrypts it locally, and restores the device's identity and history. The plaintext only ever exists on the device. It turns "I lost everything" into "I typed twelve words and I'm back," while keeping the server blind.

The math is the easy 10%. The other 90% is storage lifetimes, platform quirks, and the person with a new phone expecting their stuff to be there when you made the keys impossible to copy.

Key Takeaways

• Match Keychain accessibility to usage: Strictest isn't safest; keys a background task needs before first unlock must use "after first unlock" or they'll be unreadable when you need them.

• Keys and data have different lifetimes: iOS Keychain items can survive an uninstall while your database doesn't, so reconcile key and data state explicitly on every fresh install.

• Treat keys on the device as revocable: Android Keystore invalidates keys on biometric or PIN changes; detect the failure, build a new device identity, and tell the user what happened.

• One identity per device: Never sync private keys between devices; give each device its own key pair and encrypt separately to every recipient device so no private key crosses the network.

• Plan for the new phone up front: Real E2EE means the server can't restore history, so ship an optional encrypted backup protected by a recovery phrase and be honest that losing the phrase means losing the data.