Element-R: very slow to open

[richvdh]

TL;DR: It takes tens of seconds to open the indexeddb database. We should do less PBKDF.

---

The rust SDK encrypts its data in indexeddb with ChaChaPoly-1305, and hashes its keys with Blake3-256.

Obviously, we need to be able to recover the keys for those algorithms on subsequent runs of the application. Currently, they are derived as follows:

1. A 256-bit AES-GCM key is created, and saved in indexeddb. (The cryptoKey property of an entry in the pickleKey store in the matrix-react-sdk database)
2. A random 32-byte (=256 bits) array is created. This becomes the pickleKey. It is encrypted with the cryptoKey, and stored in indexeddb. (The encrypted property of the entry in the pickleKey store.)
3. Two more random 32-byte arrays are created; these become the ChaChaPoly-1305 and Blake3 keys.
4. The pickleKey is passed through 200000 rounds of PBKDF2-SHA2 to produce another random 32-byte array, which is used as another ChaChaPoly-1305 key.
5. The primary ChaChaPoly-1305 and Blake3 keys are encrypted by this new ChaChaPoly-1305 key, and then stored, along with details of the PBKDF derivation, in indexeddb. (The value of an entry in the matrix-sdk-crypto store in the matrix-js-sdk::matrix-sdk-crypto-meta).

[The storage of the pickleKey is slightly different on element desktop (it is stored in the system keychain, rather than being encrypted by the AES-GCM key and stored in indexeddb), but the net result is the same: it is a crypto-random 32-byte array.]

On reload, we effectively reverse the process:

1. The encrypted pickleKey is loaded from the matrix-react-sdk/pickleKey store.
2. The encrypted pickleKey is decrypted using the cryptoKey, also loaded from the matrix-react-sdk/pickleKey store.
3. The encrypted ChaChaPoly-1305 and Blake3 keys, and details of the PBKDF derivation, are loaded from matrix-js-sdk::matrix-sdk-crypto-meta/matrix-sdk-crypto.
4. The pickleKey is passed through PBKDF to produce the intermediate ChaChaPoly-1305 key.
5. The primary ChaChaPoly-1305 and Blake3 keys are decrypted using the intermediate ChaChaPoly-1305 key.

It seems to me that this is, ahem, /baroque/. It is also very slow: the PBKDF calculation takes 10s of seconds. (That is the job of PBKDF: it is designed to resist brute-forcing of human-readable passwords by slowing down the process. However, it has little value when the input is a pseudo-random array the same size as the output).

Fundamentally, both the Javascript and Rust layers are jumping through their own hoops for "security", and the whole thing is overcomplicated.

I think an easy win would be to skip the PBKDF step and use the pickleKey directly as a ChaChaPoly-1305 key to encrypt the primary ChaChaPoly-1305 and Blake3 keys. (Or, maybe better, pass pickleKey through an HMAC-based KDF). I think this could be done without breaking existing sessions, since we already store details of the PBKDF derivation: we would simply switch to the faster derivation for new sessions.

It would be nice to get rid of the whole matrix-js-sdk::matrix-sdk-crypto-meta/matrix-sdk-crypto store, and just use an HMAC-based KDF to derive the ChaChaPoly-1305 and Blake3 keys from the pickleKey. But that's a bit harder to do without breaking existing sessions.