key management overhaulkey-mgmt-overhaul

use public key sealing of content encryption keys

no secret keys are needed to encrypt records

master keys are needed to decrypt the secret key which is used to decrypt the records

9 files changed, 696 insertions, 32 deletions

diff --git a/atuin-client/src/kv.rs b/atuin-client/src/kv.rs
index 1ca6b5e8..74db2707 100644
--- a/atuin-client/src/kv.rs
+++ b/atuin-client/src/kv.rs
@@ -1,13 +1,17 @@
-use std::collections::BTreeMap;
+use std::collections::{BTreeMap, HashMap};
+use std::sync::{Mutex, OnceLock};
 
 use atuin_common::record::{DecryptedData, HostId};
-use eyre::{bail, ensure, eyre, Result};
-use serde::Deserialize;
+use eyre::{bail, ensure, eyre, ContextCompat, Result};
+use rusty_paserk::{Key, KeyId, Public, Secret, V4};
 
 use crate::record::encryption::PASETO_V4;
+use crate::record::key_mgmt;
+use crate::record::key_mgmt::key::KeyStore;
+use crate::record::key_mgmt::paseto_seal::PASETO_V4_SEAL;
 use crate::record::store::Store;
 
-const KV_VERSION: &str = "v0";
+const KV_VERSION: &str = "v1";
 const KV_TAG: &str = "kv";
 const KV_VAL_MAX_LEN: usize = 100 * 1024;
 
@@ -42,7 +46,7 @@ impl KvRecord {
         }
 
         match version {
-            KV_VERSION => {
+            "v0" | "v1" => {
                 let mut bytes = decode::Bytes::new(&data.0);
 
                 let nfields = decode::read_array_len(&mut bytes).map_err(error_report)?;
@@ -72,8 +76,11 @@ impl KvRecord {
     }
 }
 
-#[derive(Debug, Clone, Deserialize)]
-pub struct KvStore;
+pub struct KvStore {
+    key_store: KeyStore,
+    v1_public_key: OnceLock<Key<V4, Public>>,
+    v1_secret_keys: Mutex<HashMap<KeyId<V4, Public>, Key<V4, Secret>>>,
+}
 
 impl Default for KvStore {
     fn default() -> Self {
@@ -84,7 +91,12 @@ impl Default for KvStore {
 impl KvStore {
     // will want to init the actual kv store when that is done
     pub fn new() -> KvStore {
-        KvStore {}
+        let key_store = KeyStore::new("atuin-kv");
+        KvStore {
+            key_store,
+            v1_public_key: OnceLock::new(),
+            v1_secret_keys: Mutex::new(HashMap::new()),
+        }
     }
 
     pub async fn set(
@@ -121,13 +133,27 @@ impl KvStore {
             .data(bytes)
             .build();
 
-        store
-            .push(&record.encrypt::<PASETO_V4>(encryption_key))
-            .await?;
+        let key = self
+            .key_store
+            .get_encryption_key(store)
+            .await?
+            .context("no key")?;
+
+        store.push(&record.encrypt::<PASETO_V4_SEAL>(&key)).await?;
 
         Ok(())
     }
 
+    fn get_v1_decryption_key(
+        &self,
+        store: &impl Store,
+        id: KeyId<V4, Public>,
+    ) -> Result<Option<Key<V4, Secret>>> {
+        // self.v1_secret_keys.lock().unwrap().get()
+
+        todo!()
+    }
+
     // TODO: setup an actual kv store, rebuild func, and do not pass the main store in here as
     // well.
     pub async fn get(
@@ -156,7 +182,17 @@ impl KvStore {
 
         loop {
             let decrypted = match record.version.as_str() {
-                KV_VERSION => record.decrypt::<PASETO_V4>(encryption_key)?,
+                "v0" => record.decrypt::<PASETO_V4>(encryption_key)?,
+                "v1" => {
+                    let id = serde_json::from_str::<key_mgmt::paseto_seal::AtuinFooter>(
+                        &record.data.content_encryption_key,
+                    )?
+                    .kid;
+                    let key = self
+                        .get_v1_decryption_key(store, id)?
+                        .context("missing key")?;
+                    record.decrypt::<PASETO_V4_SEAL>(&key)?
+                }
                 version => bail!("unknown version {version:?}"),
             };
 
diff --git a/atuin-client/src/record/encryption.rs b/atuin-client/src/record/encryption.rs
index 3074a9c2..9d5378d6 100644
--- a/atuin-client/src/record/encryption.rs
+++ b/atuin-client/src/record/encryption.rs
@@ -1,3 +1,5 @@
+use std::marker::PhantomData;
+
 use atuin_common::record::{
     AdditionalData, DecryptedData, EncryptedData, Encryption, HostId, RecordId,
 };
@@ -11,7 +13,11 @@ 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;
+pub struct PASETO_V4_ENVELOPE<KE>(PhantomData<KE>);
+
+/// Use PASETO V4 Local encryption using the additional data as an implicit assertion.
+#[allow(non_camel_case_types)]
+pub type PASETO_V4 = PASETO_V4_ENVELOPE<Wrap>;
 
 /*
 Why do we use a random content-encryption key?
@@ -51,19 +57,22 @@ will need the HSM. This allows the encryption path to still be extremely fast (n
 that happens in the background can make the network calls to the HSM
 */
 
-impl Encryption for PASETO_V4 {
+impl<KE: KeyEncapsulation> Encryption for PASETO_V4_ENVELOPE<KE> {
+    type DecryptionKey = KE::DecryptionKey;
+    type EncryptionKey = KE::EncryptionKey;
+
     fn re_encrypt(
         mut data: EncryptedData,
         _ad: AdditionalData,
-        old_key: &[u8; 32],
-        new_key: &[u8; 32],
+        old_key: &KE::DecryptionKey,
+        new_key: &KE::EncryptionKey,
     ) -> Result<EncryptedData> {
-        let cek = Self::decrypt_cek(data.content_encryption_key, old_key)?;
-        data.content_encryption_key = Self::encrypt_cek(cek, new_key);
+        let cek = KE::decrypt_cek(data.content_encryption_key, old_key)?;
+        data.content_encryption_key = KE::encrypt_cek(cek, new_key);
         Ok(data)
     }
 
-    fn encrypt(data: DecryptedData, ad: AdditionalData, key: &[u8; 32]) -> EncryptedData {
+    fn encrypt(data: DecryptedData, ad: AdditionalData, key: &KE::EncryptionKey) -> EncryptedData {
         // generate a random key for this entry
         // aka content-encryption-key (CEK)
         let random_key = Key::<V4, Local>::new_os_random();
@@ -87,13 +96,17 @@ impl Encryption for PASETO_V4 {
 
         EncryptedData {
             data: token,
-            content_encryption_key: Self::encrypt_cek(random_key, key),
+            content_encryption_key: KE::encrypt_cek(random_key, key),
         }
     }
 
-    fn decrypt(data: EncryptedData, ad: AdditionalData, key: &[u8; 32]) -> Result<DecryptedData> {
+    fn decrypt(
+        data: EncryptedData,
+        ad: AdditionalData,
+        key: &KE::DecryptionKey,
+    ) -> Result<DecryptedData> {
         let token = data.data;
-        let cek = Self::decrypt_cek(data.content_encryption_key, key)?;
+        let cek = KE::decrypt_cek(data.content_encryption_key, key)?;
 
         // encode the implicit assertions
         let assertions = Assertions::from(ad).encode();
@@ -113,7 +126,20 @@ impl Encryption for PASETO_V4 {
     }
 }
 
-impl PASETO_V4 {
+pub trait KeyEncapsulation {
+    type DecryptionKey;
+    type EncryptionKey;
+
+    fn decrypt_cek(wrapped_cek: String, key: &Self::DecryptionKey) -> Result<Key<V4, Local>>;
+    fn encrypt_cek(cek: Key<V4, Local>, key: &Self::EncryptionKey) -> String;
+}
+
+pub struct Wrap;
+
+impl KeyEncapsulation for Wrap {
+    type DecryptionKey = [u8; 32];
+    type EncryptionKey = [u8; 32];
+
     fn decrypt_cek(wrapped_cek: String, key: &[u8; 32]) -> Result<Key<V4, Local>> {
         let wrapping_key = Key::<V4, Local>::from_bytes(*key);
 
diff --git a/atuin-client/src/record/key_mgmt/key.rs b/atuin-client/src/record/key_mgmt/key.rs
new file mode 100644
index 00000000..78ddca53
--- /dev/null
+++ b/atuin-client/src/record/key_mgmt/key.rs
@@ -0,0 +1,269 @@
+//! An encryption key store
+//!
+//! * `tag` = "key;<KEY PURPOSE>"
+//! * `version`s:
+//!   - "v0"
+//!
+//! ## Encryption schemes
+//!
+//! ### v0
+//!
+//! [`UnsafeNoEncryption`]
+//!
+//! ## Encoding schemes
+//!
+//! ### v0
+//!
+//! JSON encoding of the KeyRecord.
+//!
+//! KeyRecord {
+//!     id: k4.pid.<public key id>,
+//!     public_key: k4.public.<public key>,
+//!     wrapped_secret_key: k4.secret-wrap.<encrypted secret key>,
+//! }
+
+use std::io::Write;
+use std::path::PathBuf;
+
+use atuin_common::record::{DecryptedData, HostId};
+use base64::prelude::BASE64_STANDARD;
+use base64::Engine;
+use eyre::{bail, ensure, eyre, Context, Result};
+use rand::rngs::OsRng;
+use rand::RngCore;
+use rusty_paserk::{
+    Key, KeyId, Local, PieWrappedKey, PlaintextKey, Public, SafeForFooter, Secret, V4,
+};
+
+use crate::record::store::Store;
+use crate::settings::Settings;
+
+use super::unsafe_encryption::UnsafeNoEncryption;
+
+const KEY_VERSION: &str = "v0";
+const KEY_TAG_PREFIX: &str = "key;";
+
+#[derive(serde::Deserialize, serde::Serialize)]
+struct KeyRecord {
+    /// Key ID used to encrypt messages
+    id: KeyId<V4, Public>,
+    /// Key used to encrypt messages
+    public_key: PlaintextKey<V4, Public>,
+    /// Wrapped decryption key
+    wrapped_secret_key: PieWrappedKey<V4, Secret>,
+}
+
+/// Verify that the fields in the KeyRecord are safe to be unencrypted
+const _SAFE_UNENCRYPTED: () = {
+    const fn safe_for_footer<T: SafeForFooter>() {}
+
+    safe_for_footer::<PieWrappedKey<V4, Secret>>();
+    safe_for_footer::<KeyId<V4, Public>>();
+
+    // Public keys are always safe to share - but they should not be in footers of a PASETO.
+    // This is because for a PASETO they might be the verification key. Including the verification key
+    // with a token is an attack vector and thus you should only include the identifier of the verification key.
+    // This is not a problem for us. We don't these public keys for verification, only encryption.
+    // safe_for_footer::<PlaintextKey<V4, Public>>();
+};
+
+impl KeyRecord {
+    pub fn serialize(&self) -> Result<DecryptedData> {
+        Ok(DecryptedData(self.id.to_string().into_bytes()))
+    }
+
+    pub fn deserialize(data: &DecryptedData, version: &str) -> Result<Self> {
+        match version {
+            KEY_VERSION => serde_json::from_slice(&data.0).context("not a valid key record"),
+            _ => {
+                bail!("unknown version {version:?}")
+            }
+        }
+    }
+}
+
+pub struct KeyStore {
+    purpose: String,
+}
+
+impl KeyStore {
+    /// Create a new key store for your application.
+    ///
+    /// Purpose should be unique for your application.
+    /// Eg for atuin history this might be "atuin-history".
+    /// For atuin kv this might be "atuin-kv".
+    /// For mcfly history this might be "mcfly".
+    /// etc...
+    pub fn new(purpose: &str) -> KeyStore {
+        KeyStore {
+            purpose: format!("{KEY_TAG_PREFIX}{purpose}"),
+        }
+    }
+
+    pub async fn get_encryption_key(
+        &self,
+        store: &mut impl Store,
+    ) -> Result<Option<Key<V4, Public>>> {
+        // iterate records to find the value we want
+        // start at the end, so we get the most recent version
+        let tails = store.tag_tails(&self.purpose).await?;
+
+        if tails.is_empty() {
+            return Ok(None);
+        }
+
+        // first, decide on a record. see kv store for details
+        let record = tails.iter().max_by_key(|r| r.timestamp).unwrap().clone();
+
+        let decrypted = match record.version.as_str() {
+            KEY_VERSION => record.decrypt::<UnsafeNoEncryption>(&())?,
+            version => bail!("unknown version {version:?}"),
+        };
+
+        let kv = KeyRecord::deserialize(&decrypted.data, &decrypted.version)?;
+        Ok(Some(kv.public_key.0))
+    }
+
+    pub async fn get_wrapped_decryption_key(
+        &self,
+        store: &mut impl Store,
+        id: KeyId<V4, Public>,
+    ) -> Result<Option<PieWrappedKey<V4, Secret>>> {
+        // iterate records to find the value we want
+        // start at the end, so we get the most recent version
+        let tails = store.tag_tails(&self.purpose).await?;
+
+        if tails.is_empty() {
+            return Ok(None);
+        }
+
+        // first, decide on a record. see kv store for details
+        let mut record = tails.iter().max_by_key(|r| r.timestamp).unwrap().clone();
+
+        loop {
+            let decrypted = match record.version.as_str() {
+                KEY_VERSION => record.decrypt::<UnsafeNoEncryption>(&())?,
+                version => bail!("unknown version {version:?}"),
+            };
+
+            let kv = KeyRecord::deserialize(&decrypted.data, &decrypted.version)?;
+            if kv.id == id {
+                return Ok(Some(kv.wrapped_secret_key));
+            }
+
+            if let Some(parent) = decrypted.parent {
+                record = store.get(parent).await?;
+            } else {
+                break;
+            }
+        }
+
+        // if we get here, then... we didn't find the record with that key id :(
+        Ok(None)
+    }
+
+    pub async fn set(
+        &self,
+        store: &mut impl Store,
+        host_id: HostId,
+        public_key: Key<V4, Public>,
+        wrapped_secret_key: PieWrappedKey<V4, Secret>,
+    ) -> Result<()> {
+        let id = public_key.to_id();
+        let record = KeyRecord {
+            id,
+            public_key: PlaintextKey(public_key),
+            wrapped_secret_key,
+        };
+
+        let bytes = record.serialize()?;
+
+        let parent = store
+            .tail(host_id, &self.purpose)
+            .await?
+            .map(|entry| entry.id);
+
+        let record = atuin_common::record::Record::builder()
+            .host(host_id)
+            .version(KEY_VERSION.to_string())
+            .tag(self.purpose.to_string())
+            .parent(parent)
+            .data(bytes)
+            .build();
+
+        store
+            .push(&record.encrypt::<UnsafeNoEncryption>(&()))
+            .await?;
+
+        Ok(())
+    }
+}
+
+pub enum EncryptionKey {
+    /// The current key is invalid
+    Invalid {
+        /// the id of the key
+        kid: KeyId<V4, Local>,
+        /// the id of the host that registered the key
+        host_id: String,
+    },
+    Valid {
+        encryption_key: AtuinKey,
+    },
+}
+pub type AtuinKey = [u8; 32];
+
+pub fn new_key(settings: &Settings) -> Result<AtuinKey> {
+    let path = settings.key_path.as_str();
+
+    let mut key = [0; 32];
+    OsRng.fill_bytes(&mut key);
+    let encoded = encode_key(&key)?;
+
+    let mut file = fs_err::File::create(path)?;
+    file.write_all(encoded.as_bytes())?;
+
+    Ok(key)
+}
+
+// Loads the secret key, will create + save if it doesn't exist
+pub fn load_key(settings: &Settings) -> Result<AtuinKey> {
+    let path = settings.key_path.as_str();
+
+    let key = if PathBuf::from(path).exists() {
+        let key = fs_err::read_to_string(path)?;
+        decode_key(key)?
+    } else {
+        new_key(settings)?
+    };
+
+    Ok(key)
+}
+
+pub fn encode_key(key: &AtuinKey) -> Result<String> {
+    let mut buf = vec![];
+    rmp::encode::write_bin(&mut buf, key.as_slice())
+        .wrap_err("could not encode key to message pack")?;
+    let buf = BASE64_STANDARD.encode(buf);
+
+    Ok(buf)
+}
+
+pub fn decode_key(key: String) -> Result<AtuinKey> {
+    let buf = BASE64_STANDARD
+        .decode(key.trim_end())
+        .wrap_err("encryption key is not a valid base64 encoding")?;
+
+    // old code wrote the key as a fixed length array of 32 bytes
+    // new code writes the key with a length prefix
+    match <[u8; 32]>::try_from(&*buf) {
+        Ok(key) => Ok(key),
+        Err(_) => {
+            let mut bytes = rmp::decode::Bytes::new(&buf);
+            let key_len = rmp::decode::read_bin_len(&mut bytes).map_err(|err| eyre!("{err:?}"))?;
+            ensure!(key_len == 32, "encryption key is not the correct size");
+            <[u8; 32]>::try_from(bytes.remaining_slice())
+                .context("encryption key is not the correct size")
+        }
+    }
+}
diff --git a/atuin-client/src/record/key_mgmt/mod.rs b/atuin-client/src/record/key_mgmt/mod.rs
new file mode 100644
index 00000000..4a8a0dc6
--- /dev/null
+++ b/atuin-client/src/record/key_mgmt/mod.rs
@@ -0,0 +1,5 @@
+#![forbid(unsafe_code)]
+
+pub mod paseto_seal;
+pub mod key;
+pub mod unsafe_encryption;
diff --git a/atuin-client/src/record/key_mgmt/paseto_seal.rs b/atuin-client/src/record/key_mgmt/paseto_seal.rs
new file mode 100644
index 00000000..f012062c
--- /dev/null
+++ b/atuin-client/src/record/key_mgmt/paseto_seal.rs
@@ -0,0 +1,239 @@
+use crate::record::encryption::{KeyEncapsulation, PASETO_V4_ENVELOPE};
+use eyre::{ensure, Context, Result};
+use rusty_paserk::{Key, KeyId, Local, Public, SealedKey, Secret};
+use rusty_paseto::core::V4;
+use serde::{Deserialize, Serialize};
+
+/// Use PASETO V4 Local encryption with PASERK key sealing using the additional data as an implicit assertion.
+#[allow(non_camel_case_types)]
+pub type PASETO_V4_SEAL = PASETO_V4_ENVELOPE<Seal>;
+
+/// Key sealing
+pub struct Seal;
+
+impl KeyEncapsulation for Seal {
+    type DecryptionKey = rusty_paserk::Key<V4, Secret>;
+    type EncryptionKey = rusty_paserk::Key<V4, Public>;
+
+    fn decrypt_cek(
+        wrapped_cek: String,
+        key: &rusty_paserk::Key<V4, Secret>,
+    ) -> Result<Key<V4, Local>> {
+        // 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 = key.public_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.unseal(key)?)
+    }
+
+    fn encrypt_cek(cek: Key<V4, Local>, key: &rusty_paserk::Key<V4, Public>) -> String {
+        // wrap the random key so we can decrypt it later
+        let wrapped_cek = AtuinFooter {
+            wpk: cek.seal(key),
+            kid: key.to_id(),
+        };
+        serde_json::to_string(&wrapped_cek).expect("could not serialize wrapped cek")
+    }
+}
+
+#[derive(Serialize, Deserialize)]
+struct AtuinPayload {
+    data: String,
+}
+
+#[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>
+pub struct AtuinFooter {
+    /// Wrapped key
+    wpk: SealedKey<V4>,
+    /// ID of the key which was used to wrap
+    pub kid: KeyId<V4, Public>,
+}
+
+#[cfg(test)]
+mod tests {
+    use atuin_common::{
+        record::{AdditionalData, DecryptedData, Encryption, HostId, Record, RecordId},
+        utils::uuid_v7,
+    };
+
+    use super::*;
+
+    #[test]
+    fn round_trip() {
+        let key = Key::<V4, Secret>::new_os_random();
+
+        let ad = AdditionalData {
+            id: &RecordId(uuid_v7()),
+            version: "v0",
+            tag: "kv",
+            host: &HostId(uuid_v7()),
+            parent: None,
+        };
+
+        let data = DecryptedData(vec![1, 2, 3, 4]);
+
+        let encrypted = PASETO_V4_SEAL::encrypt(data.clone(), ad, &key.public_key());
+        let decrypted = PASETO_V4_SEAL::decrypt(encrypted, ad, &key).unwrap();
+        assert_eq!(decrypted, data);
+    }
+
+    #[test]
+    fn same_entry_different_output() {
+        let key = Key::<V4, Secret>::new_os_random();
+
+        let ad = AdditionalData {
+            id: &RecordId(uuid_v7()),
+            version: "v0",
+            tag: "kv",
+            host: &HostId(uuid_v7()),
+            parent: None,
+        };
+
+        let data = DecryptedData(vec![1, 2, 3, 4]);
+
+        let encrypted = PASETO_V4_SEAL::encrypt(data.clone(), ad, &key.public_key());
+        let encrypted2 = PASETO_V4_SEAL::encrypt(data, ad, &key.public_key());
+
+        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, Secret>::new_os_random();
+        let fake_key = Key::<V4, Secret>::new_os_random();
+
+        let ad = AdditionalData {
+            id: &RecordId(uuid_v7()),
+            version: "v0",
+            tag: "kv",
+            host: &HostId(uuid_v7()),
+            parent: None,
+        };
+
+        let data = DecryptedData(vec![1, 2, 3, 4]);
+
+        let encrypted = PASETO_V4_SEAL::encrypt(data, ad, &key.public_key());
+        let _ = PASETO_V4_SEAL::decrypt(encrypted, ad, &fake_key).unwrap_err();
+    }
+
+    #[test]
+    fn cannot_decrypt_different_id() {
+        let key = Key::<V4, Secret>::new_os_random();
+
+        let ad = AdditionalData {
+            id: &RecordId(uuid_v7()),
+            version: "v0",
+            tag: "kv",
+            host: &HostId(uuid_v7()),
+            parent: None,
+        };
+
+        let data = DecryptedData(vec![1, 2, 3, 4]);
+
+        let encrypted = PASETO_V4_SEAL::encrypt(data, ad, &key.public_key());
+
+        let ad = AdditionalData {
+            id: &RecordId(uuid_v7()),
+            ..ad
+        };
+        let _ = PASETO_V4_SEAL::decrypt(encrypted, ad, &key).unwrap_err();
+    }
+
+    #[test]
+    fn re_encrypt_round_trip() {
+        let key1 = Key::<V4, Secret>::new_os_random();
+        let key2 = Key::<V4, Secret>::new_os_random();
+
+        let ad = AdditionalData {
+            id: &RecordId(uuid_v7()),
+            version: "v0",
+            tag: "kv",
+            host: &HostId(uuid_v7()),
+            parent: None,
+        };
+
+        let data = DecryptedData(vec![1, 2, 3, 4]);
+
+        let encrypted1 = PASETO_V4_SEAL::encrypt(data.clone(), ad, &key1.public_key());
+        let encrypted2 =
+            PASETO_V4_SEAL::re_encrypt(encrypted1.clone(), ad, &key1, &key2.public_key()).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_SEAL::decrypt(encrypted2, ad, &key2).unwrap();
+
+        assert_eq!(decrypted, data);
+    }
+
+    #[test]
+    fn full_record_round_trip() {
+        let key = Key::from_secret_key([0x55; 32]);
+        let record = Record::builder()
+            .id(RecordId(uuid_v7()))
+            .version("v0".to_owned())
+            .tag("kv".to_owned())
+            .host(HostId(uuid_v7()))
+            .timestamp(1687244806000000)
+            .data(DecryptedData(vec![1, 2, 3, 4]))
+            .build();
+
+        let encrypted = record.encrypt::<PASETO_V4_SEAL>(&key.public_key());
+
+        assert!(!encrypted.data.data.is_empty());
+        assert!(!encrypted.data.content_encryption_key.is_empty());
+
+        let decrypted = encrypted.decrypt::<PASETO_V4_SEAL>(&key).unwrap();
+
+        assert_eq!(decrypted.data.0, [1, 2, 3, 4]);
+    }
+
+    #[test]
+    fn full_record_round_trip_fail() {
+        let key = Key::from_secret_key([0x55; 32]);
+        let record = Record::builder()
+            .id(RecordId(uuid_v7()))
+            .version("v0".to_owned())
+            .tag("kv".to_owned())
+            .host(HostId(uuid_v7()))
+            .timestamp(1687244806000000)
+            .data(DecryptedData(vec![1, 2, 3, 4]))
+            .build();
+
+        let encrypted = record.encrypt::<PASETO_V4_SEAL>(&key.public_key());
+
+        let mut enc1 = encrypted.clone();
+        enc1.host = HostId(uuid_v7());
+        let _ = enc1
+            .decrypt::<PASETO_V4_SEAL>(&key)
+            .expect_err("tampering with the host should result in auth failure");
+
+        let mut enc2 = encrypted;
+        enc2.id = RecordId(uuid_v7());
+        let _ = enc2
+            .decrypt::<PASETO_V4_SEAL>(&key)
+            .expect_err("tampering with the id should result in auth failure");
+    }
+}
diff --git a/atuin-client/src/record/key_mgmt/unsafe_encryption.rs b/atuin-client/src/record/key_mgmt/unsafe_encryption.rs
new file mode 100644
index 00000000..ceab1c7a
--- /dev/null
+++ b/atuin-client/src/record/key_mgmt/unsafe_encryption.rs
@@ -0,0 +1,80 @@
+use std::io::Write;
+
+use atuin_common::record::{AdditionalData, DecryptedData, EncryptedData, Encryption};
+use base64::{engine::general_purpose, write::EncoderStringWriter, Engine};
+use eyre::{ensure, Context, ContextCompat, Result};
+
+/// Store record data unencrypted. Only for very specific use cases of record data not being sensitive.
+/// If in doubt, use [`super::paseto_v4::PASETO_V4`].
+pub struct UnsafeNoEncryption;
+
+static CONTENT_HEADER: &str = "v0.none.";
+static CEK_HEADER: &str = "k0.none.";
+
+impl Encryption for UnsafeNoEncryption {
+    type DecryptionKey = ();
+    type EncryptionKey = ();
+
+    fn re_encrypt(
+        data: EncryptedData,
+        _ad: AdditionalData,
+        _old_key: &(),
+        _new_key: &(),
+    ) -> Result<EncryptedData> {
+        Ok(data)
+    }
+
+    fn encrypt(data: DecryptedData, _ad: AdditionalData, _key: &()) -> EncryptedData {
+        let mut token = EncoderStringWriter::from_consumer(
+            CONTENT_HEADER.to_owned(),
+            &general_purpose::URL_SAFE_NO_PAD,
+        );
+        token
+            .write_all(&data.0)
+            .expect("base64 encoding should always succeed");
+        EncryptedData {
+            data: token.into_inner(),
+            content_encryption_key: CEK_HEADER.to_owned(),
+        }
+    }
+
+    fn decrypt(data: EncryptedData, _ad: AdditionalData, _key: &()) -> Result<DecryptedData> {
+        ensure!(
+            data.content_encryption_key == CEK_HEADER,
+            "exected unencrypted data, found a content encryption key"
+        );
+        let content = data
+            .data
+            .strip_prefix(CONTENT_HEADER)
+            .context("exected unencrypted data, found an encrypted token")?;
+        let data = general_purpose::URL_SAFE_NO_PAD
+            .decode(content)
+            .context("could not decode data")?;
+        Ok(DecryptedData(data))
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use atuin_common::record::{HostId, RecordId};
+    use uuid::Uuid;
+
+    use super::*;
+
+    #[test]
+    fn round_trip() {
+        let ad = AdditionalData {
+            id: &RecordId(Uuid::new_v4()),
+            version: "v0",
+            tag: "kv",
+            host: &HostId(Uuid::new_v4()),
+            parent: None,
+        };
+
+        let data = DecryptedData(vec![1, 2, 3, 4]);
+
+        let encrypted = UnsafeNoEncryption::encrypt(data.clone(), ad, &());
+        let decrypted = UnsafeNoEncryption::decrypt(encrypted, ad, &()).unwrap();
+        assert_eq!(decrypted, data);
+    }
+}
diff --git a/atuin-client/src/record/mod.rs b/atuin-client/src/record/mod.rs
index 8bc816ae..0790f82c 100644
--- a/atuin-client/src/record/mod.rs
+++ b/atuin-client/src/record/mod.rs
@@ -1,4 +1,5 @@
 pub mod encryption;
+pub mod key_mgmt;
 pub mod sqlite_store;
 pub mod store;
 #[cfg(feature = "sync")]
diff --git a/atuin-client/src/record/store.rs b/atuin-client/src/record/store.rs
index 45d554ef..dcdafdc5 100644
--- a/atuin-client/src/record/store.rs
+++ b/atuin-client/src/record/store.rs
@@ -8,7 +8,7 @@ use atuin_common::record::{EncryptedData, HostId, Record, RecordId, RecordIndex}
 /// As is, the record store is intended as the source of truth for arbitratry data, which could
 /// be shell history, kvs, etc.
 #[async_trait]
-pub trait Store {
+pub trait Store: Send + Sync {
     // Push a record
     async fn push(&self, record: &Record<EncryptedData>) -> Result<()> {
         self.push_batch(std::iter::once(record)).await
diff --git a/atuin-common/src/record.rs b/atuin-common/src/record.rs
index cba0917a..401e0514 100644
--- a/atuin-common/src/record.rs
+++ b/atuin-common/src/record.rs
@@ -182,21 +182,29 @@ impl RecordIndex {
 }
 
 pub trait Encryption {
+    type EncryptionKey;
+    type DecryptionKey;
+
     fn re_encrypt(
         data: EncryptedData,
         ad: AdditionalData,
-        old_key: &[u8; 32],
-        new_key: &[u8; 32],
+        old_key: &Self::DecryptionKey,
+        new_key: &Self::EncryptionKey,
     ) -> Result<EncryptedData> {
         let data = Self::decrypt(data, ad, old_key)?;
         Ok(Self::encrypt(data, ad, new_key))
     }
-    fn encrypt(data: DecryptedData, ad: AdditionalData, key: &[u8; 32]) -> EncryptedData;
-    fn decrypt(data: EncryptedData, ad: AdditionalData, key: &[u8; 32]) -> Result<DecryptedData>;
+    fn encrypt(data: DecryptedData, ad: AdditionalData, key: &Self::EncryptionKey)
+        -> EncryptedData;
+    fn decrypt(
+        data: EncryptedData,
+        ad: AdditionalData,
+        key: &Self::DecryptionKey,
+    ) -> Result<DecryptedData>;
 }
 
 impl Record<DecryptedData> {
-    pub fn encrypt<E: Encryption>(self, key: &[u8; 32]) -> Record<EncryptedData> {
+    pub fn encrypt<E: Encryption>(self, key: &E::EncryptionKey) -> Record<EncryptedData> {
         let ad = AdditionalData {
             id: &self.id,
             version: &self.version,
@@ -217,7 +225,7 @@ impl Record<DecryptedData> {
 }
 
 impl Record<EncryptedData> {
-    pub fn decrypt<E: Encryption>(self, key: &[u8; 32]) -> Result<Record<DecryptedData>> {
+    pub fn decrypt<E: Encryption>(self, key: &E::DecryptionKey) -> Result<Record<DecryptedData>> {
         let ad = AdditionalData {
             id: &self.id,
             version: &self.version,
@@ -238,8 +246,8 @@ impl Record<EncryptedData> {
 
     pub fn re_encrypt<E: Encryption>(
         self,
-        old_key: &[u8; 32],
-        new_key: &[u8; 32],
+        old_key: &E::DecryptionKey,
+        new_key: &E::EncryptionKey,
     ) -> Result<Record<EncryptedData>> {
         let ad = AdditionalData {
             id: &self.id,