record encryption (#1058)

* record encryption

* move paserk impl

* implicit assertions

* move wrapped cek

* add another test

* use host

* undo stray change

* more tests and docs

* fmt

* Update atuin-client/src/record/encryption.rs

Co-authored-by: Matteo Martellini <matteo@mercxry.me>

* Update atuin-client/src/record/encryption.rs

Co-authored-by: Matteo Martellini <matteo@mercxry.me>

* typo

---------

Co-authored-by: Matteo Martellini <matteo@mercxry.me>

5 files changed, 427 insertions, 36 deletions

diff --git a/atuin-client/src/kv.rs b/atuin-client/src/kv.rs
index 1fe90b6c..c365a385 100644
--- a/atuin-client/src/kv.rs
+++ b/atuin-client/src/kv.rs
@@ -1,5 +1,7 @@
+use atuin_common::record::DecryptedData;
 use eyre::{bail, ensure, eyre, Result};
 
+use crate::record::encryption::PASETO_V4;
 use crate::record::store::Store;
 use crate::settings::Settings;
 
@@ -14,7 +16,7 @@ pub struct KvRecord {
 }
 
 impl KvRecord {
-    pub fn serialize(&self) -> Result<Vec<u8>> {
+    pub fn serialize(&self) -> Result<DecryptedData> {
         use rmp::encode;
 
         let mut output = vec![];
@@ -26,10 +28,10 @@ impl KvRecord {
         encode::write_str(&mut output, &self.key)?;
         encode::write_str(&mut output, &self.value)?;
 
-        Ok(output)
+        Ok(DecryptedData(output))
     }
 
-    pub fn deserialize(data: &[u8], version: &str) -> Result<Self> {
+    pub fn deserialize(data: &DecryptedData, version: &str) -> Result<Self> {
         use rmp::decode;
 
         fn error_report<E: std::fmt::Debug>(err: E) -> eyre::Report {
@@ -38,7 +40,7 @@ impl KvRecord {
 
         match version {
             KV_VERSION => {
-                let mut bytes = decode::Bytes::new(data);
+                let mut bytes = decode::Bytes::new(&data.0);
 
                 let nfields = decode::read_array_len(&mut bytes).map_err(error_report)?;
                 ensure!(nfields == 3, "too many entries in v0 kv record");
@@ -84,6 +86,7 @@ impl KvStore {
     pub async fn set(
         &self,
         store: &mut (impl Store + Send + Sync),
+        encryption_key: &[u8; 32],
         namespace: &str,
         key: &str,
         value: &str,
@@ -111,7 +114,9 @@ impl KvStore {
             .data(bytes)
             .build();
 
-        store.push(&record).await?;
+        store
+            .push(&record.encrypt::<PASETO_V4>(encryption_key))
+            .await?;
 
         Ok(())
     }
@@ -121,6 +126,7 @@ impl KvStore {
     pub async fn get(
         &self,
         store: &impl Store,
+        encryption_key: &[u8; 32],
         namespace: &str,
         key: &str,
     ) -> Result<Option<KvRecord>> {
@@ -137,12 +143,17 @@ impl KvStore {
         };
 
         loop {
-            let kv = KvRecord::deserialize(&record.data, &record.version)?;
+            let decrypted = match record.version.as_str() {
+                KV_VERSION => record.decrypt::<PASETO_V4>(encryption_key)?,
+                version => bail!("unknown version {version:?}"),
+            };
+
+            let kv = KvRecord::deserialize(&decrypted.data, &decrypted.version)?;
             if kv.key == key && kv.namespace == namespace {
                 return Ok(Some(kv));
             }
 
-            if let Some(parent) = record.parent {
+            if let Some(parent) = decrypted.parent {
                 record = store.get(parent.as_str()).await?;
             } else {
                 break;
@@ -172,7 +183,7 @@ mod tests {
         let encoded = kv.serialize().unwrap();
         let decoded = KvRecord::deserialize(&encoded, KV_VERSION).unwrap();
 
-        assert_eq!(encoded, &snapshot);
+        assert_eq!(encoded.0, &snapshot);
         assert_eq!(decoded, kv);
     }
 }
diff --git a/atuin-client/src/record/encryption.rs b/atuin-client/src/record/encryption.rs
new file mode 100644
index 00000000..f14bf027
--- /dev/null
+++ b/atuin-client/src/record/encryption.rs
@@ -0,0 +1,361 @@
+use atuin_common::record::{AdditionalData, DecryptedData, EncryptedData, Encryption};
+use base64::{engine::general_purpose, Engine};
+use eyre::{ensure, Context, Result};
+use rusty_paserk::{Key, KeyId, Local, PieWrappedKey};
+use rusty_paseto::core::{
+    ImplicitAssertion, Key as DataKey, Local as LocalPurpose, Paseto, PasetoNonce, Payload, V4,
+};
+use serde::{Deserialize, Serialize};
+
+/// Use PASETO V4 Local encryption using the additional data as an implicit assertion.
+#[allow(non_camel_case_types)]
+pub struct PASETO_V4;
+
+/*
+Why do we use a random content-encryption key?
+Originally I was planning on using a derived key for encryption based on additional data.
+This would be a lot more secure than using the master key directly.
+
+However, there's an established norm of using a random key. This scheme might be otherwise known as
+- client-side encryption
+- envelope encryption
+- key wrapping
+
+A HSM (Hardware Security Module) provider, eg: AWS, Azure, GCP, or even a physical device like a YubiKey
+will have some keys that they keep to themselves. These keys never leave their physical hardware.
+If they never leave the hardware, then encrypting large amounts of data means giving them the data and waiting.
+This is not a practical solution. Instead, generate a unique key for your data, encrypt that using your HSM
+and then store that with your data.
+
+See
+ - <https://docs.aws.amazon.com/wellarchitected/latest/financial-services-industry-lens/use-envelope-encryption-with-customer-master-keys.html>
+ - <https://cloud.google.com/kms/docs/envelope-encryption>
+ - <https://learn.microsoft.com/en-us/azure/storage/blobs/client-side-encryption?tabs=dotnet#encryption-and-decryption-via-the-envelope-technique>
+ - <https://www.yubico.com/gb/product/yubihsm-2-fips/>
+ - <https://cheatsheetseries.owasp.org/cheatsheets/Cryptographic_Storage_Cheat_Sheet.html#encrypting-stored-keys>
+
+Why would we care? In the past we have recieved some requests for company solutions. If in future we can configure a
+KMS service with little effort, then that would solve a lot of issues for their security team.
+
+Even for personal use, if a user is not comfortable with sharing keys between hosts,
+GCP HSM costs $1/month and $0.03 per 10,000 key operations. Assuming an active user runs
+1000 atuin records a day, that would only cost them $1 and 10 cent a month.
+
+Additionally, key rotations are much simpler using this scheme. Rotating a key is as simple as re-encrypting the CEK, and not the message contents.
+This makes it very fast to rotate a key in bulk.
+
+For future reference, with asymmetric encryption, you can encrypt the CEK without the HSM's involvement, but decrypting
+will need the HSM. This allows the encryption path to still be extremely fast (no network calls) but downloads/decryption
+that happens in the background can make the network calls to the HSM
+*/
+
+impl Encryption for PASETO_V4 {
+    fn re_encrypt(
+        mut data: EncryptedData,
+        _ad: AdditionalData,
+        old_key: &[u8; 32],
+        new_key: &[u8; 32],
+    ) -> Result<EncryptedData> {
+        let cek = Self::decrypt_cek(data.content_encryption_key, old_key)?;
+        data.content_encryption_key = Self::encrypt_cek(cek, new_key);
+        Ok(data)
+    }
+
+    fn encrypt(data: DecryptedData, ad: AdditionalData, key: &[u8; 32]) -> EncryptedData {
+        // generate a random key for this entry
+        // aka content-encryption-key (CEK)
+        let random_key = Key::<V4, Local>::new_os_random();
+
+        // encode the implicit assertions
+        let assertions = Assertions::from(ad).encode();
+
+        // build the payload and encrypt the token
+        let payload = general_purpose::URL_SAFE_NO_PAD.encode(data.0);
+        let nonce = DataKey::<32>::try_new_random().expect("could not source from random");
+        let nonce = PasetoNonce::<V4, LocalPurpose>::from(&nonce);
+
+        let token = Paseto::<V4, LocalPurpose>::builder()
+            .set_payload(Payload::from(payload.as_str()))
+            .set_implicit_assertion(ImplicitAssertion::from(assertions.as_str()))
+            .try_encrypt(&random_key.into(), &nonce)
+            .expect("error encrypting atuin data");
+
+        EncryptedData {
+            data: token,
+            content_encryption_key: Self::encrypt_cek(random_key, key),
+        }
+    }
+
+    fn decrypt(data: EncryptedData, ad: AdditionalData, key: &[u8; 32]) -> Result<DecryptedData> {
+        let token = data.data;
+        let cek = Self::decrypt_cek(data.content_encryption_key, key)?;
+
+        // encode the implicit assertions
+        let assertions = Assertions::from(ad).encode();
+
+        // decrypt the payload with the footer and implicit assertions
+        let payload = Paseto::<V4, LocalPurpose>::try_decrypt(
+            &token,
+            &cek.into(),
+            None,
+            ImplicitAssertion::from(&*assertions),
+        )
+        .context("could not decrypt entry")?;
+
+        let data = general_purpose::URL_SAFE_NO_PAD.decode(payload)?;
+        Ok(DecryptedData(data))
+    }
+}
+
+impl PASETO_V4 {
+    fn decrypt_cek(wrapped_cek: String, key: &[u8; 32]) -> Result<Key<V4, Local>> {
+        let wrapping_key = Key::<V4, Local>::from_bytes(*key);
+
+        // let wrapping_key = PasetoSymmetricKey::from(Key::from(key));
+
+        let AtuinFooter { kid, wpk } = serde_json::from_str(&wrapped_cek)
+            .context("wrapped cek did not contain the correct contents")?;
+
+        // check that the wrapping key matches the required key to decrypt.
+        // In future, we could support multiple keys and use this key to
+        // look up the key rather than only allow one key.
+        // For now though we will only support the one key and key rotation will
+        // have to be a hard reset
+        let current_kid = wrapping_key.to_id();
+        ensure!(
+            current_kid == kid,
+            "attempting to decrypt with incorrect key. currently using {current_kid}, expecting {kid}"
+        );
+
+        // decrypt the random key
+        Ok(wpk.unwrap_key(&wrapping_key)?)
+    }
+
+    fn encrypt_cek(cek: Key<V4, Local>, key: &[u8; 32]) -> String {
+        // aka key-encryption-key (KEK)
+        let wrapping_key = Key::<V4, Local>::from_bytes(*key);
+
+        // wrap the random key so we can decrypt it later
+        let wrapped_cek = AtuinFooter {
+            wpk: cek.wrap_pie(&wrapping_key),
+            kid: wrapping_key.to_id(),
+        };
+        serde_json::to_string(&wrapped_cek).expect("could not serialize wrapped cek")
+    }
+}
+
+#[derive(Serialize, Deserialize)]
+/// Well-known footer claims for decrypting. This is not encrypted but is stored in the record.
+/// <https://github.com/paseto-standard/paseto-spec/blob/master/docs/02-Implementation-Guide/04-Claims.md#optional-footer-claims>
+struct AtuinFooter {
+    /// Wrapped key
+    wpk: PieWrappedKey<V4, Local>,
+    /// ID of the key which was used to wrap
+    kid: KeyId<V4, Local>,
+}
+
+/// Used in the implicit assertions. This is not encrypted and not stored in the data blob.
+// This cannot be changed, otherwise it breaks the authenticated encryption.
+#[derive(Debug, Copy, Clone, Serialize)]
+struct Assertions<'a> {
+    id: &'a str,
+    version: &'a str,
+    tag: &'a str,
+    host: &'a str,
+}
+
+impl<'a> From<AdditionalData<'a>> for Assertions<'a> {
+    fn from(ad: AdditionalData<'a>) -> Self {
+        Self {
+            id: ad.id,
+            version: ad.version,
+            tag: ad.tag,
+            host: ad.host,
+        }
+    }
+}
+
+impl Assertions<'_> {
+    fn encode(&self) -> String {
+        serde_json::to_string(self).expect("could not serialize implicit assertions")
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use atuin_common::record::Record;
+
+    use super::*;
+
+    #[test]
+    fn round_trip() {
+        let key = Key::<V4, Local>::new_os_random();
+
+        let ad = AdditionalData {
+            id: "foo",
+            version: "v0",
+            tag: "kv",
+            host: "1234",
+        };
+
+        let data = DecryptedData(vec![1, 2, 3, 4]);
+
+        let encrypted = PASETO_V4::encrypt(data.clone(), ad, &key.to_bytes());
+        let decrypted = PASETO_V4::decrypt(encrypted, ad, &key.to_bytes()).unwrap();
+        assert_eq!(decrypted, data);
+    }
+
+    #[test]
+    fn same_entry_different_output() {
+        let key = Key::<V4, Local>::new_os_random();
+
+        let ad = AdditionalData {
+            id: "foo",
+            version: "v0",
+            tag: "kv",
+            host: "1234",
+        };
+
+        let data = DecryptedData(vec![1, 2, 3, 4]);
+
+        let encrypted = PASETO_V4::encrypt(data.clone(), ad, &key.to_bytes());
+        let encrypted2 = PASETO_V4::encrypt(data, ad, &key.to_bytes());
+
+        assert_ne!(
+            encrypted.data, encrypted2.data,
+            "re-encrypting the same contents should have different output due to key randomization"
+        );
+    }
+
+    #[test]
+    fn cannot_decrypt_different_key() {
+        let key = Key::<V4, Local>::new_os_random();
+        let fake_key = Key::<V4, Local>::new_os_random();
+
+        let ad = AdditionalData {
+            id: "foo",
+            version: "v0",
+            tag: "kv",
+            host: "1234",
+        };
+
+        let data = DecryptedData(vec![1, 2, 3, 4]);
+
+        let encrypted = PASETO_V4::encrypt(data, ad, &key.to_bytes());
+        let _ = PASETO_V4::decrypt(encrypted, ad, &fake_key.to_bytes()).unwrap_err();
+    }
+
+    #[test]
+    fn cannot_decrypt_different_id() {
+        let key = Key::<V4, Local>::new_os_random();
+
+        let ad = AdditionalData {
+            id: "foo",
+            version: "v0",
+            tag: "kv",
+            host: "1234",
+        };
+
+        let data = DecryptedData(vec![1, 2, 3, 4]);
+
+        let encrypted = PASETO_V4::encrypt(data, ad, &key.to_bytes());
+
+        let ad = AdditionalData {
+            id: "foo1",
+            version: "v0",
+            tag: "kv",
+            host: "1234",
+        };
+        let _ = PASETO_V4::decrypt(encrypted, ad, &key.to_bytes()).unwrap_err();
+    }
+
+    #[test]
+    fn re_encrypt_round_trip() {
+        let key1 = Key::<V4, Local>::new_os_random();
+        let key2 = Key::<V4, Local>::new_os_random();
+
+        let ad = AdditionalData {
+            id: "foo",
+            version: "v0",
+            tag: "kv",
+            host: "1234",
+        };
+
+        let data = DecryptedData(vec![1, 2, 3, 4]);
+
+        let encrypted1 = PASETO_V4::encrypt(data.clone(), ad, &key1.to_bytes());
+        let encrypted2 =
+            PASETO_V4::re_encrypt(encrypted1.clone(), ad, &key1.to_bytes(), &key2.to_bytes())
+                .unwrap();
+
+        // we only re-encrypt the content keys
+        assert_eq!(encrypted1.data, encrypted2.data);
+        assert_ne!(
+            encrypted1.content_encryption_key,
+            encrypted2.content_encryption_key
+        );
+
+        let decrypted = PASETO_V4::decrypt(encrypted2, ad, &key2.to_bytes()).unwrap();
+
+        assert_eq!(decrypted, data);
+    }
+
+    #[test]
+    fn full_record_round_trip() {
+        let key = [0x55; 32];
+        let record = Record::builder()
+            .id("1".to_owned())
+            .version("v0".to_owned())
+            .tag("kv".to_owned())
+            .host("host1".to_owned())
+            .timestamp(1687244806000000)
+            .data(DecryptedData(vec![1, 2, 3, 4]))
+            .build();
+
+        let encrypted = record.encrypt::<PASETO_V4>(&key);
+
+        assert!(!encrypted.data.data.is_empty());
+        assert!(!encrypted.data.content_encryption_key.is_empty());
+        assert_eq!(encrypted.id, "1");
+        assert_eq!(encrypted.host, "host1");
+        assert_eq!(encrypted.version, "v0");
+        assert_eq!(encrypted.tag, "kv");
+        assert_eq!(encrypted.timestamp, 1687244806000000);
+
+        let decrypted = encrypted.decrypt::<PASETO_V4>(&key).unwrap();
+
+        assert_eq!(decrypted.data.0, [1, 2, 3, 4]);
+        assert_eq!(decrypted.id, "1");
+        assert_eq!(decrypted.host, "host1");
+        assert_eq!(decrypted.version, "v0");
+        assert_eq!(decrypted.tag, "kv");
+        assert_eq!(decrypted.timestamp, 1687244806000000);
+    }
+
+    #[test]
+    fn full_record_round_trip_fail() {
+        let key = [0x55; 32];
+        let record = Record::builder()
+            .id("1".to_owned())
+            .version("v0".to_owned())
+            .tag("kv".to_owned())
+            .host("host1".to_owned())
+            .timestamp(1687244806000000)
+            .data(DecryptedData(vec![1, 2, 3, 4]))
+            .build();
+
+        let encrypted = record.encrypt::<PASETO_V4>(&key);
+
+        let mut enc1 = encrypted.clone();
+        enc1.host = "host2".to_owned();
+        let _ = enc1
+            .decrypt::<PASETO_V4>(&key)
+            .expect_err("tampering with the host should result in auth failure");
+
+        let mut enc2 = encrypted;
+        enc2.id = "2".to_owned();
+        let _ = enc2
+            .decrypt::<PASETO_V4>(&key)
+            .expect_err("tampering with the id should result in auth failure");
+    }
+}
diff --git a/atuin-client/src/record/mod.rs b/atuin-client/src/record/mod.rs
index 72c1f889..9ac2c541 100644
--- a/atuin-client/src/record/mod.rs
+++ b/atuin-client/src/record/mod.rs
@@ -1,2 +1,3 @@
+pub mod encryption;
 pub mod sqlite_store;
 pub mod store;
diff --git a/atuin-client/src/record/sqlite_store.rs b/atuin-client/src/record/sqlite_store.rs
index f116b6e5..f692c0c2 100644
--- a/atuin-client/src/record/sqlite_store.rs
+++ b/atuin-client/src/record/sqlite_store.rs
@@ -13,7 +13,7 @@ use sqlx::{
     Row,
 };
 
-use atuin_common::record::Record;
+use atuin_common::record::{EncryptedData, Record};
 
 use super::store::Store;
 
@@ -53,11 +53,14 @@ impl SqliteStore {
         Ok(())
     }
 
-    async fn save_raw(tx: &mut sqlx::Transaction<'_, sqlx::Sqlite>, r: &Record) -> Result<()> {
+    async fn save_raw(
+        tx: &mut sqlx::Transaction<'_, sqlx::Sqlite>,
+        r: &Record<EncryptedData>,
+    ) -> Result<()> {
         // In sqlite, we are "limited" to i64. But that is still fine, until 2262.
         sqlx::query(
-            "insert or ignore into records(id, host, tag, timestamp, parent, version, data)
-                values(?1, ?2, ?3, ?4, ?5, ?6, ?7)",
+            "insert or ignore into records(id, host, tag, timestamp, parent, version, data, cek)
+                values(?1, ?2, ?3, ?4, ?5, ?6, ?7, ?8)",
         )
         .bind(r.id.as_str())
         .bind(r.host.as_str())
@@ -65,14 +68,15 @@ impl SqliteStore {
         .bind(r.timestamp as i64)
         .bind(r.parent.as_ref())
         .bind(r.version.as_str())
-        .bind(r.data.as_slice())
+        .bind(r.data.data.as_str())
+        .bind(r.data.content_encryption_key.as_str())
         .execute(tx)
         .await?;
 
         Ok(())
     }
 
-    fn query_row(row: SqliteRow) -> Record {
+    fn query_row(row: SqliteRow) -> Record<EncryptedData> {
         let timestamp: i64 = row.get("timestamp");
 
         Record {
@@ -82,14 +86,20 @@ impl SqliteStore {
             timestamp: timestamp as u64,
             tag: row.get("tag"),
             version: row.get("version"),
-            data: row.get("data"),
+            data: EncryptedData {
+                data: row.get("data"),
+                content_encryption_key: row.get("cek"),
+            },
         }
     }
 }
 
 #[async_trait]
 impl Store for SqliteStore {
-    async fn push_batch(&self, records: impl Iterator<Item = &Record> + Send + Sync) -> Result<()> {
+    async fn push_batch(
+        &self,
+        records: impl Iterator<Item = &Record<EncryptedData>> + Send + Sync,
+    ) -> Result<()> {
         let mut tx = self.pool.begin().await?;
 
         for record in records {
@@ -101,7 +111,7 @@ impl Store for SqliteStore {
         Ok(())
     }
 
-    async fn get(&self, id: &str) -> Result<Record> {
+    async fn get(&self, id: &str) -> Result<Record<EncryptedData>> {
         let res = sqlx::query("select * from records where id = ?1")
             .bind(id)
             .map(Self::query_row)
@@ -122,7 +132,7 @@ impl Store for SqliteStore {
         Ok(res.0 as u64)
     }
 
-    async fn next(&self, record: &Record) -> Result<Option<Record>> {
+    async fn next(&self, record: &Record<EncryptedData>) -> Result<Option<Record<EncryptedData>>> {
         let res = sqlx::query("select * from records where parent = ?1")
             .bind(record.id.clone())
             .map(Self::query_row)
@@ -136,7 +146,7 @@ impl Store for SqliteStore {
         }
     }
 
-    async fn first(&self, host: &str, tag: &str) -> Result<Option<Record>> {
+    async fn first(&self, host: &str, tag: &str) -> Result<Option<Record<EncryptedData>>> {
         let res = sqlx::query(
             "select * from records where host = ?1 and tag = ?2 and parent is null limit 1",
         )
@@ -149,7 +159,7 @@ impl Store for SqliteStore {
         Ok(res)
     }
 
-    async fn last(&self, host: &str, tag: &str) -> Result<Option<Record>> {
+    async fn last(&self, host: &str, tag: &str) -> Result<Option<Record<EncryptedData>>> {
         let res = sqlx::query(
             "select * from records rp where tag=?1 and host=?2 and (select count(1) from records where parent=rp.id) = 0;",
         )
@@ -165,18 +175,21 @@ impl Store for SqliteStore {
 
 #[cfg(test)]
 mod tests {
-    use atuin_common::record::Record;
+    use atuin_common::record::{EncryptedData, Record};
 
-    use crate::record::store::Store;
+    use crate::record::{encryption::PASETO_V4, store::Store};
 
     use super::SqliteStore;
 
-    fn test_record() -> Record {
+    fn test_record() -> Record<EncryptedData> {
         Record::builder()
             .host(atuin_common::utils::uuid_v7().simple().to_string())
             .version("v1".into())
             .tag(atuin_common::utils::uuid_v7().simple().to_string())
-            .data(vec![0, 1, 2, 3])
+            .data(EncryptedData {
+                data: "1234".into(),
+                content_encryption_key: "1234".into(),
+            })
             .build()
     }
 
@@ -261,7 +274,9 @@ mod tests {
         db.push(&tail).await.expect("failed to push record");
 
         for _ in 1..100 {
-            tail = tail.new_child(vec![1, 2, 3, 4]);
+            tail = tail
+                .new_child(vec![1, 2, 3, 4])
+                .encrypt::<PASETO_V4>(&[0; 32]);
             db.push(&tail).await.unwrap();
         }
 
@@ -276,13 +291,13 @@ mod tests {
     async fn append_a_big_bunch() {
         let db = SqliteStore::new(":memory:").await.unwrap();
 
-        let mut records: Vec<Record> = Vec::with_capacity(10000);
+        let mut records: Vec<Record<EncryptedData>> = Vec::with_capacity(10000);
 
         let mut tail = test_record();
         records.push(tail.clone());
 
         for _ in 1..10000 {
-            tail = tail.new_child(vec![1, 2, 3]);
+            tail = tail.new_child(vec![1, 2, 3]).encrypt::<PASETO_V4>(&[0; 32]);
             records.push(tail.clone());
         }
 
@@ -299,13 +314,13 @@ mod tests {
     async fn test_chain() {
         let db = SqliteStore::new(":memory:").await.unwrap();
 
-        let mut records: Vec<Record> = Vec::with_capacity(1000);
+        let mut records: Vec<Record<EncryptedData>> = Vec::with_capacity(1000);
 
         let mut tail = test_record();
         records.push(tail.clone());
 
         for _ in 1..1000 {
-            tail = tail.new_child(vec![1, 2, 3]);
+            tail = tail.new_child(vec![1, 2, 3]).encrypt::<PASETO_V4>(&[0; 32]);
             records.push(tail.clone());
         }
 
diff --git a/atuin-client/src/record/store.rs b/atuin-client/src/record/store.rs
index 75d79fb5..9ea7007a 100644
--- a/atuin-client/src/record/store.rs
+++ b/atuin-client/src/record/store.rs
@@ -1,7 +1,7 @@
 use async_trait::async_trait;
 use eyre::Result;
 
-use atuin_common::record::Record;
+use atuin_common::record::{EncryptedData, Record};
 
 /// A record store stores records
 /// In more detail - we tend to need to process this into _another_ format to actually query it.
@@ -10,21 +10,24 @@ use atuin_common::record::Record;
 #[async_trait]
 pub trait Store {
     // Push a record
-    async fn push(&self, record: &Record) -> Result<()> {
+    async fn push(&self, record: &Record<EncryptedData>) -> Result<()> {
         self.push_batch(std::iter::once(record)).await
     }
 
     // Push a batch of records, all in one transaction
-    async fn push_batch(&self, records: impl Iterator<Item = &Record> + Send + Sync) -> Result<()>;
+    async fn push_batch(
+        &self,
+        records: impl Iterator<Item = &Record<EncryptedData>> + Send + Sync,
+    ) -> Result<()>;
 
-    async fn get(&self, id: &str) -> Result<Record>;
+    async fn get(&self, id: &str) -> Result<Record<EncryptedData>>;
     async fn len(&self, host: &str, tag: &str) -> Result<u64>;
 
     /// Get the record that follows this record
-    async fn next(&self, record: &Record) -> Result<Option<Record>>;
+    async fn next(&self, record: &Record<EncryptedData>) -> Result<Option<Record<EncryptedData>>>;
 
     /// Get the first record for a given host and tag
-    async fn first(&self, host: &str, tag: &str) -> Result<Option<Record>>;
+    async fn first(&self, host: &str, tag: &str) -> Result<Option<Record<EncryptedData>>>;
     /// Get the last record for a given host and tag
-    async fn last(&self, host: &str, tag: &str) -> Result<Option<Record>>;
+    async fn last(&self, host: &str, tag: &str) -> Result<Option<Record<EncryptedData>>>;
 }