switch to paseto v4 style encryptionchacha

8 files changed, 272 insertions, 187 deletions

diff --git a/Cargo.lock b/Cargo.lock
index c1151a30..83472768 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -136,7 +136,8 @@ dependencies = [
  "async-trait",
  "atuin-common",
  "base64 0.21.0",
- "chacha20poly1305",
+ "blake2",
+ "chacha20",
  "chrono",
  "clap",
  "config",
@@ -145,7 +146,6 @@ dependencies = [
  "fs-err",
  "generic-array",
  "hex",
- "hkdf",
  "interim",
  "itertools",
  "lazy_static",
@@ -364,19 +364,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "chacha20poly1305"
-version = "0.10.1"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "10cd79432192d1c0f4e1a0fef9527696cc039165d729fb41b3f4f4f354c2dc35"
-dependencies = [
- "aead",
- "chacha20",
- "cipher",
- "poly1305",
- "zeroize",
-]
-
-[[package]]
 name = "chrono"
 version = "0.4.22"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/atuin-client/Cargo.toml b/atuin-client/Cargo.toml
index 0460dbb0..123f7e00 100644
--- a/atuin-client/Cargo.toml
+++ b/atuin-client/Cargo.toml
@@ -22,8 +22,8 @@ sync = [
   "base64",
   "generic-array",
   "xsalsa20poly1305",
-  "chacha20poly1305",
-  "hkdf",
+  "blake2",
+  "chacha20",
 ]
 
 [dependencies]
@@ -64,8 +64,8 @@ base64 = { workspace = true, optional = true }
 tokio = { workspace = true }
 semver = { workspace = true }
 xsalsa20poly1305 = { version = "0.9.0", optional = true }
-chacha20poly1305 =  { version = "0.10.1", optional = true }
-hkdf = { version = "0.12.3", optional = true }
+chacha20 =  { version = "0.9.0", optional = true }
+blake2 = { version = "0.10.6", optional = true }
 generic-array = { version = "0.14", optional = true, features = ["serde"] }
 
 [dev-dependencies]
diff --git a/atuin-client/src/sync.rs b/atuin-client/src/sync.rs
index 6a391154..958b8633 100644
--- a/atuin-client/src/sync.rs
+++ b/atuin-client/src/sync.rs
@@ -10,8 +10,8 @@ use atuin_common::api::{AddHistoryRequest, EncryptionScheme};
 use crate::{api_client, database::Database, settings::Settings};
 
 pub mod key;
-mod xchacha20poly1305;
-mod xsalsa20poly1305legacy;
+mod legacy;
+mod pasetov4;
 
 pub fn hash_str(string: &str) -> String {
     use sha2::{Digest, Sha256};
@@ -70,10 +70,10 @@ async fn sync_download(
 
         for entry in encrypted_page {
             let mut history = match entry.encryption {
-                Some(EncryptionScheme::XSalsa20Poly1305Legacy) | None => {
+                Some(EncryptionScheme::Legacy) | None => {
                     crypto.salsa_legacy.decrypt(&entry.data, &entry.id)?
                 }
-                Some(EncryptionScheme::XChaCha20Poly1305) => {
+                Some(EncryptionScheme::PasetoV4) => {
                     crypto.xchacha20.decrypt(&entry.data, &entry.id)?
                 }
                 Some(EncryptionScheme::Unknown(x)) => {
@@ -165,8 +165,8 @@ async fn sync_upload(
                 hostname: hash_str(&i.hostname),
                 encryption: Some(settings.encryption_scheme.clone()),
                 data: match &settings.encryption_scheme {
-                    EncryptionScheme::XSalsa20Poly1305Legacy => crypto.salsa_legacy.encrypt(&i)?,
-                    EncryptionScheme::XChaCha20Poly1305 => crypto.xchacha20.encrypt(i)?,
+                    EncryptionScheme::Legacy => crypto.salsa_legacy.encrypt(&i)?,
+                    EncryptionScheme::PasetoV4 => crypto.xchacha20.encrypt(i)?,
                     EncryptionScheme::Unknown(x) => {
                         bail!("cannot encrypt with '{x}' encryption scheme")
                     }
@@ -214,15 +214,15 @@ pub async fn sync(settings: &Settings, force: bool, db: &mut (impl Database + Se
 }
 
 struct Crypto {
-    salsa_legacy: xsalsa20poly1305legacy::Client,
-    xchacha20: xchacha20poly1305::Client,
+    salsa_legacy: legacy::Client,
+    xchacha20: pasetov4::Client,
 }
 
 impl Crypto {
     fn new(key: &key::Key) -> Self {
         Self {
-            salsa_legacy: xsalsa20poly1305legacy::Client::new(key),
-            xchacha20: xchacha20poly1305::Client::new(key),
+            salsa_legacy: legacy::Client::new(key),
+            xchacha20: pasetov4::Client::new(key),
         }
     }
 }
diff --git a/atuin-client/src/sync/key.rs b/atuin-client/src/sync/key.rs
index 84284acf..d961dd0e 100644
--- a/atuin-client/src/sync/key.rs
+++ b/atuin-client/src/sync/key.rs
@@ -1,9 +1,9 @@
 use std::path::Path;
 
 use base64::prelude::{Engine, BASE64_STANDARD};
-use chacha20poly1305::aead::{rand_core::RngCore, OsRng};
 use eyre::{Context, Result};
 use generic_array::typenum::U32;
+use xsalsa20poly1305::aead::{rand_core::RngCore, OsRng};
 
 use crate::settings::Settings;
 
diff --git a/atuin-client/src/sync/xsalsa20poly1305legacy.rs b/atuin-client/src/sync/legacy.rs
index 570df9e5..570df9e5 100644
--- a/atuin-client/src/sync/xsalsa20poly1305legacy.rs
+++ b/atuin-client/src/sync/legacy.rs
diff --git a/atuin-client/src/sync/pasetov4.rs b/atuin-client/src/sync/pasetov4.rs
new file mode 100644
index 00000000..13c4045b
--- /dev/null
+++ b/atuin-client/src/sync/pasetov4.rs
@@ -0,0 +1,247 @@
+//! Loosely following <https://github.com/paseto-standard/paseto-spec/blob/master/docs/01-Protocol-Versions/Version4.md>.
+// DO NOT MODIFY. We can't change old encryption schemes, only add new ones.
+
+use super::key::Key;
+use base64::{prelude::BASE64_URL_SAFE, Engine};
+use blake2::{
+    digest::{FixedOutput, Mac},
+    Blake2bMac,
+};
+use chacha20::{
+    cipher::{KeyIvInit, StreamCipher},
+    XChaCha20,
+};
+use chrono::Utc;
+use eyre::{bail, Result};
+use generic_array::{
+    sequence::Split,
+    typenum::{U32, U56},
+    GenericArray,
+};
+use serde::{Deserialize, Serialize};
+use xsalsa20poly1305::aead::{rand_core::RngCore, OsRng};
+
+#[derive(Debug, Serialize, Deserialize)]
+struct HistoryPlaintext {
+    pub duration: i64,
+    pub exit: i64,
+    pub command: String,
+    pub cwd: String,
+    pub session: String,
+    pub hostname: String,
+    pub timestamp: chrono::DateTime<Utc>,
+}
+#[derive(Debug, Serialize, Deserialize)]
+struct EncryptedHistory {
+    pub ciphertext: Vec<u8>,
+    pub nonce: GenericArray<u8, U32>,
+}
+
+use crate::history::History;
+
+pub struct Client {
+    encryption_key_hasher: Blake2bMac<U56>,
+    authentication_key_hasher: Blake2bMac<U32>,
+}
+
+static HEADER: &[u8] = b"atuin.paseto.v4.local."; // not spec compliant, but we don't intend to be 100% compliant
+
+/// <https://github.com/paseto-standard/paseto-spec/blob/master/docs/01-Protocol-Versions/Common.md#authentication-padding>
+fn pae<M: Mac>(mut mac: M, pieces: &[&[u8]]) -> GenericArray<u8, M::OutputSize> {
+    mac.update(&(pieces.len() as u64).to_le_bytes());
+    for piece in pieces {
+        mac.update(&(piece.len() as u64).to_le_bytes());
+        mac.update(piece);
+    }
+    mac.finalize().into_bytes()
+}
+
+impl Client {
+    pub fn new(key: &Key) -> Self {
+        Self {
+            encryption_key_hasher: Blake2bMac::<U56>::new_from_slice(key)
+                .expect("32 byte key is less than 56 byte block size"),
+            authentication_key_hasher: Blake2bMac::<U32>::new_from_slice(key)
+                .expect("32 byte key is equal to 32 byte block size"),
+        }
+    }
+
+    /// Step 4 of encryption, Step 5 of decryption
+    ///
+    /// > Split the key into an Encryption key (Ek) and Authentication key (Ak), using keyed BLAKE2b,
+    /// > using the domain separation constants and n as the message, and the input key as the key.
+    /// > The first value will be 56 bytes, the second will be 32 bytes. The derived key will be the leftmost 32 bytes of the hash output.
+    /// > The remaining 24 bytes will be used as a counter nonce (n2):
+    /// ```ignore
+    /// tmp = crypto_generichash(
+    ///     msg = "paseto-encryption-key" || n,
+    ///     key = key,
+    ///     length = 56
+    /// );
+    /// Ek = tmp[0:32]
+    /// n2 = tmp[32:]
+    /// Ak = crypto_generichash(
+    ///     msg = "paseto-auth-key-for-aead" || n,
+    ///     key = key,
+    ///     length = 32
+    /// );
+    /// ```
+    fn keys(&self, nonce: &GenericArray<u8, U32>) -> Result<(XChaCha20, Blake2bMac<U32>)> {
+        let (ek, n2) = self
+            .encryption_key_hasher
+            .clone()
+            .chain_update(b"atuin-paseto-encryption-key")
+            .chain_update(nonce)
+            .finalize_fixed()
+            .split();
+
+        let ak = self
+            .authentication_key_hasher
+            .clone()
+            .chain_update(b"atuin-paseto-auth-key-for-aead")
+            .chain_update(nonce)
+            .finalize_fixed();
+
+        let cipher = XChaCha20::new(&ek, &n2);
+        let mac = Blake2bMac::<U32>::new_from_slice(&ak)
+            .expect("32 byte key is equal to 32 byte block size");
+
+        Ok((cipher, mac))
+    }
+
+    /// <https://github.com/paseto-standard/paseto-spec/blob/master/docs/01-Protocol-Versions/Version4.md#decrypt>
+    pub fn encrypt(&self, history: History) -> Result<String> {
+        // Step 3: Generate 32 random bytes from the OS's CSPRNG, n.
+        let mut nonce = GenericArray::default();
+        OsRng.fill_bytes(&mut nonce);
+
+        // Step 4: Key splitting
+        let (mut cipher, mac) = self.keys(&nonce)?;
+
+        // Step 5.0: encode the message
+        let mut plaintext = rmp_serde::to_vec(&HistoryPlaintext {
+            duration: history.duration,
+            exit: history.exit,
+            command: history.command,
+            cwd: history.cwd,
+            session: history.session,
+            hostname: history.hostname,
+            timestamp: history.timestamp,
+        })?;
+
+        // Step 5: Encrypt the message using XChaCha20, using n2 from step 3 as the nonce and Ek as the key.
+        cipher.apply_keystream(&mut plaintext);
+        let mut ciphertext = plaintext;
+
+        // Step 6: Pack h, n, c, f, and i together (in that order) using PAE. We'll call this preAuth.
+        // h = HEADER
+        // n = nonce
+        // c = ciphertext
+        // f = history_id
+        // i = none
+        // Step 7: Calculate BLAKE2b-MAC of the output of preAuth, using Ak as the authentication key. We'll call this t.
+        let tag = pae(mac, &[HEADER, &nonce, &ciphertext, history.id.as_bytes()]);
+
+        // Step 8: Encode the message `base64url(n || c || t)` (we store the header and footer elsewhere already)
+        ciphertext.splice(0..0, nonce);
+        ciphertext.extend(tag);
+        Ok(BASE64_URL_SAFE.encode(&ciphertext))
+    }
+
+    /// <https://github.com/paseto-standard/paseto-spec/blob/master/docs/01-Protocol-Versions/Version4.md#decrypt>
+    pub fn decrypt(&self, encrypted_history: &str, id: &str) -> Result<History> {
+        // Step 4: Decode the payload from base64url to raw binary. Set:
+        // n to the leftmost 32 bytes
+        // t to the rightmost 32 bytes
+        // c to the middle remainder of the payload, excluding n and t.
+        let mut decoded = BASE64_URL_SAFE.decode(encrypted_history)?;
+        if decoded.len() < 64 {
+            bail!("encrypted message too short");
+        }
+        let (nonce, ciphertext) = decoded.split_at_mut(32);
+        let (ciphertext, tag) = ciphertext.split_at_mut(ciphertext.len() - 32);
+
+        // Step 5: Key splitting
+        let (mut cipher, mac) = self.keys(GenericArray::from_slice(nonce))?;
+
+        // Step 6: Pack h, n, c, f, and i together (in that order) using PAE. We'll call this preAuth.
+        // h = HEADER
+        // n = nonce
+        // c = ciphertext
+        // f = history_id
+        // i = none
+        // Step 7: Re-calculate BLAKE2b-MAC of the output of preAuth, using Ak as the authentication key. We'll call this t2.
+        let tag2 = pae(mac, &[HEADER, nonce, ciphertext, id.as_bytes()]);
+
+        // Step 8: Compare t with t2 using a constant-time string compare function. If they are not identical, throw an exception.
+        if *tag != *tag2 {
+            bail!("message authentication failed");
+        }
+
+        cipher.apply_keystream(ciphertext);
+        let plaintext = ciphertext;
+
+        let history: HistoryPlaintext = rmp_serde::from_slice(plaintext)?;
+
+        Ok(History {
+            id: id.to_owned(),
+            cwd: history.cwd,
+            exit: history.exit,
+            command: history.command,
+            session: history.session,
+            duration: history.duration,
+            hostname: history.hostname,
+            timestamp: history.timestamp,
+            deleted_at: None,
+        })
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use crate::{history::History, sync::key};
+
+    use super::Client;
+
+    #[test]
+    fn test_encrypt_decrypt() {
+        let key = Client::new(&key::random());
+
+        let history1 = History::new(
+            chrono::Utc::now(),
+            "ls".to_string(),
+            "/home/ellie".to_string(),
+            0,
+            1,
+            Some("beep boop".to_string()),
+            Some("booop".to_string()),
+            None,
+        );
+        let history2 = History {
+            id: "another-id".to_owned(),
+            ..history1.clone()
+        };
+
+        // same contents, different id, different encryption key
+        let e1 = key.encrypt(history1.clone()).unwrap();
+        let e2 = key.encrypt(history2.clone()).unwrap();
+
+        assert_ne!(e1, e2);
+
+        // test decryption works
+        // this should pass
+        match key.decrypt(&e1, &history1.id) {
+            Err(e) => panic!("failed to decrypt, got {}", e),
+            Ok(h) => assert_eq!(h, history1),
+        };
+        match key.decrypt(&e2, &history2.id) {
+            Err(e) => panic!("failed to decrypt, got {}", e),
+            Ok(h) => assert_eq!(h, history2),
+        };
+
+        // this should err
+        let _ = key
+            .decrypt(&e2, &history1.id)
+            .expect_err("expected an error decrypting with invalid key");
+    }
+}
diff --git a/atuin-client/src/sync/xchacha20poly1305.rs b/atuin-client/src/sync/xchacha20poly1305.rs
deleted file mode 100644
index 4245b8e0..00000000
--- a/atuin-client/src/sync/xchacha20poly1305.rs
+++ /dev/null
@@ -1,148 +0,0 @@
-// DO NOT MODIFY. We can't change old encryption schemes, only add new ones.
-
-use super::key::Key;
-use chacha20poly1305::{
-    aead::{Nonce, OsRng},
-    AeadCore, AeadInPlace, KeyInit, XChaCha20Poly1305,
-};
-use chrono::Utc;
-use eyre::{eyre, Result};
-use hkdf::Hkdf;
-use serde::{Deserialize, Serialize};
-use sha2::Sha256;
-
-#[derive(Debug, Serialize, Deserialize)]
-struct HistoryPlaintext {
-    pub duration: i64,
-    pub exit: i64,
-    pub command: String,
-    pub cwd: String,
-    pub session: String,
-    pub hostname: String,
-    pub timestamp: chrono::DateTime<Utc>,
-}
-#[derive(Debug, Serialize, Deserialize)]
-struct EncryptedHistory {
-    pub ciphertext: Vec<u8>,
-    pub nonce: Nonce<XChaCha20Poly1305>,
-}
-
-use crate::history::History;
-
-pub struct Client {
-    inner: Hkdf<Sha256>,
-}
-
-impl Client {
-    pub fn new(key: &Key) -> Self {
-        Self {
-            // constant 'salt' is important and actually helps with security, while helping to improving performance
-            // <https://soatok.blog/2021/11/17/understanding-hkdf/>
-            inner: Hkdf::<Sha256>::new(Some(b"history"), key),
-        }
-    }
-
-    fn cipher(&self, id: &str) -> Result<XChaCha20Poly1305> {
-        let mut content_key = chacha20poly1305::Key::default();
-        self.inner
-            .expand(id.as_bytes(), &mut content_key)
-            .map_err(|_| eyre!("could not derive encryption key"))?;
-        Ok(XChaCha20Poly1305::new(&content_key))
-    }
-
-    pub fn encrypt(&self, history: History) -> Result<String> {
-        let mut plaintext = rmp_serde::to_vec(&HistoryPlaintext {
-            duration: history.duration,
-            exit: history.exit,
-            command: history.command,
-            cwd: history.cwd,
-            session: history.session,
-            hostname: history.hostname,
-            timestamp: history.timestamp,
-        })?;
-
-        let nonce = XChaCha20Poly1305::generate_nonce(&mut OsRng);
-        self.cipher(&history.id)?
-            .encrypt_in_place(&nonce, history.id.as_bytes(), &mut plaintext)
-            .map_err(|_| eyre!("could not encrypt"))?;
-
-        let record = serde_json::to_string(&EncryptedHistory {
-            ciphertext: plaintext,
-            nonce,
-        })?;
-
-        Ok(record)
-    }
-
-    pub fn decrypt(&self, encrypted_history: &str, id: &str) -> Result<History> {
-        let mut decoded: EncryptedHistory = serde_json::from_str(encrypted_history)?;
-
-        self.cipher(id)?
-            .decrypt_in_place(&decoded.nonce, id.as_bytes(), &mut decoded.ciphertext)
-            .map_err(|_| eyre!("could not decrypt"))?;
-        let plaintext = decoded.ciphertext;
-
-        let history: HistoryPlaintext = rmp_serde::from_slice(&plaintext)?;
-
-        Ok(History {
-            id: id.to_owned(),
-            cwd: history.cwd,
-            exit: history.exit,
-            command: history.command,
-            session: history.session,
-            duration: history.duration,
-            hostname: history.hostname,
-            timestamp: history.timestamp,
-            deleted_at: None,
-        })
-    }
-}
-
-#[cfg(test)]
-mod test {
-    use crate::{history::History, sync::key};
-
-    use super::Client;
-
-    #[test]
-    fn test_encrypt_decrypt() {
-        let key = Client::new(&key::random());
-
-        let history1 = History::new(
-            chrono::Utc::now(),
-            "ls".to_string(),
-            "/home/ellie".to_string(),
-            0,
-            1,
-            Some("beep boop".to_string()),
-            Some("booop".to_string()),
-            None,
-        );
-        let history2 = History {
-            id: "another-id".to_owned(),
-            ..history1.clone()
-        };
-
-        // same contents, different id, different encryption key
-        let e1 = key.encrypt(history1.clone()).unwrap();
-        let e2 = key.encrypt(history2.clone()).unwrap();
-
-        assert_ne!(e1, e2);
-
-        // test decryption works
-        // this should pass
-        match key.decrypt(&e1, &history1.id) {
-            Err(e) => panic!("failed to decrypt, got {}", e),
-            Ok(h) => assert_eq!(h, history1),
-        };
-        match key.decrypt(&e2, &history2.id) {
-            Err(e) => panic!("failed to decrypt, got {}", e),
-            Ok(h) => assert_eq!(h, history2),
-        };
-
-        // this should err
-        let _ = key
-            .decrypt(&e2, &history1.id)
-            .expect_err("expected an error decrypting with invalid key");
-    }
-}
diff --git a/atuin-common/src/api.rs b/atuin-common/src/api.rs
index afbedec4..0db1ac1c 100644
--- a/atuin-common/src/api.rs
+++ b/atuin-common/src/api.rs
@@ -46,12 +46,11 @@ pub struct AddHistoryRequest {
 pub enum EncryptionScheme {
     /// Encryption scheme using xsalsa20poly1305 (tweetnacl crypto_box) using the legacy system
     /// with no additional data and the same key for each entry with random IV
-    XSalsa20Poly1305Legacy,
+    Legacy,
 
-    /// Encryption scheme using xchacha20poly1305. Entry id is used in the additional data.
-    /// The key is derived from the original using the ID as info and "history" as the salt.
-    /// Each entry uses a random IV too.
-    XChaCha20Poly1305,
+    /// Following the PasetoV4 Specification for encryption:
+    /// <https://github.com/paseto-standard/paseto-spec/blob/master/docs/01-Protocol-Versions/Version4.md>
+    PasetoV4,
 
     Unknown(String),
 }
@@ -59,15 +58,15 @@ pub enum EncryptionScheme {
 impl EncryptionScheme {
     pub fn to_str(&self) -> &str {
         match self {
-            EncryptionScheme::XSalsa20Poly1305Legacy => "XSalsa20Poly1305Legacy",
-            EncryptionScheme::XChaCha20Poly1305 => "XChaCha20Poly1305",
+            EncryptionScheme::Legacy => "Legacy",
+            EncryptionScheme::PasetoV4 => "PasetoV4",
             EncryptionScheme::Unknown(x) => x,
         }
     }
     pub fn from_string(s: String) -> Self {
         match &*s {
-            "XSalsa20Poly1305Legacy" => EncryptionScheme::XSalsa20Poly1305Legacy,
-            "XChaCha20Poly1305" => EncryptionScheme::XChaCha20Poly1305,
+            "Legacy" => EncryptionScheme::Legacy,
+            "PasetoV4" => EncryptionScheme::PasetoV4,
             _ => EncryptionScheme::Unknown(s),
         }
     }