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>

11 files changed, 976 insertions, 89 deletions

diff --git a/Cargo.lock b/Cargo.lock
index d019fd45..ecec2940 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -18,7 +18,7 @@ version = "0.7.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "fcb51a0695d8f838b1ee009b3fbf66bda078cd64590202a864a8f3e8c4315c47"
 dependencies = [
- "getrandom",
+ "getrandom 0.2.7",
  "once_cell",
  "version_check",
 ]
@@ -54,7 +54,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "95c2fcf79ad1932ac6269a738109997a83c227c09b75842ae564dc8ede6a861c"
 dependencies = [
  "base64ct",
- "blake2",
+ "blake2 0.10.6",
  "password-hash",
 ]
 
@@ -151,15 +151,17 @@ dependencies = [
  "memchr",
  "minspan",
  "parse_duration",
- "rand",
+ "rand 0.8.5",
  "regex",
  "reqwest",
  "rmp",
+ "rusty_paserk",
+ "rusty_paseto",
  "semver",
  "serde",
  "serde_json",
  "serde_regex",
- "sha2",
+ "sha2 0.10.6",
  "shellexpand",
  "sql-builder",
  "sqlx",
@@ -176,8 +178,9 @@ name = "atuin-common"
 version = "15.0.0"
 dependencies = [
  "chrono",
+ "eyre",
  "pretty_assertions",
- "rand",
+ "rand 0.8.5",
  "serde",
  "typed-builder",
  "uuid",
@@ -199,7 +202,7 @@ dependencies = [
  "eyre",
  "fs-err",
  "http",
- "rand",
+ "rand 0.8.5",
  "reqwest",
  "semver",
  "serde",
@@ -327,11 +330,31 @@ checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a"
 
 [[package]]
 name = "blake2"
+version = "0.9.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0a4e37d16930f5459780f5621038b6382b9bb37c19016f39fb6b5808d831f174"
+dependencies = [
+ "crypto-mac",
+ "digest 0.9.0",
+ "opaque-debug",
+]
+
+[[package]]
+name = "blake2"
 version = "0.10.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "46502ad458c9a52b69d4d4d32775c788b7a1b85e8bc9d482d92250fc0e3f8efe"
 dependencies = [
- "digest",
+ "digest 0.10.7",
+]
+
+[[package]]
+name = "block-buffer"
+version = "0.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "4152116fd6e9dadb291ae18fc1ec3575ed6d84c29642d97890f4b4a3417297e4"
+dependencies = [
+ "generic-array",
 ]
 
 [[package]]
@@ -380,6 +403,28 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
 
 [[package]]
+name = "chacha20"
+version = "0.8.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5c80e5460aa66fe3b91d40bcbdab953a597b60053e34d684ac6903f863b680a6"
+dependencies = [
+ "cfg-if",
+ "cipher 0.3.0",
+ "cpufeatures",
+]
+
+[[package]]
+name = "chacha20"
+version = "0.9.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c3613f74bd2eac03dad61bd53dbe620703d4371614fe0bc3b9f04dd36fe4e818"
+dependencies = [
+ "cfg-if",
+ "cipher 0.4.4",
+ "cpufeatures",
+]
+
+[[package]]
 name = "chrono"
 version = "0.4.22"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -390,7 +435,7 @@ dependencies = [
  "num-integer",
  "num-traits",
  "serde",
- "time",
+ "time 0.1.44",
  "wasm-bindgen",
  "winapi",
 ]
@@ -406,6 +451,15 @@ dependencies = [
 
 [[package]]
 name = "cipher"
+version = "0.3.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7ee52072ec15386f770805afd189a01c8841be8696bed250fa2f13c4c0d6dfb7"
+dependencies = [
+ "generic-array",
+]
+
+[[package]]
+name = "cipher"
 version = "0.4.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "773f3b9af64447d2ce9850330c473515014aa235e6a783b02db81ff39e4a3dad"
@@ -505,6 +559,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "const-oid"
+version = "0.9.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "520fbf3c07483f94e3e3ca9d0cfd913d7718ef2483d2cfd91c0d9e91474ab913"
+
+[[package]]
 name = "core-foundation"
 version = "0.9.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -597,11 +657,21 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "1bfb12502f3fc46cca1bb51ac28df9d618d813cdc3d2f25b9fe775a34af26bb3"
 dependencies = [
  "generic-array",
- "rand_core",
+ "rand_core 0.6.4",
  "typenum",
 ]
 
 [[package]]
+name = "crypto-mac"
+version = "0.8.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b584a330336237c1eecd3e94266efb216c56ed91225d634cb2991c5f3fd1aeab"
+dependencies = [
+ "generic-array",
+ "subtle",
+]
+
+[[package]]
 name = "ctor"
 version = "0.1.26"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -612,6 +682,44 @@ dependencies = [
 ]
 
 [[package]]
+name = "curve25519-dalek"
+version = "3.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0b9fdf9972b2bd6af2d913799d9ebc165ea4d2e65878e329d9c6b372c4491b61"
+dependencies = [
+ "byteorder",
+ "digest 0.9.0",
+ "rand_core 0.5.1",
+ "subtle",
+ "zeroize",
+]
+
+[[package]]
+name = "curve25519-dalek"
+version = "4.0.0-rc.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "03d928d978dbec61a1167414f5ec534f24bea0d7a0d24dd9b6233d3d8223e585"
+dependencies = [
+ "cfg-if",
+ "digest 0.10.7",
+ "fiat-crypto",
+ "packed_simd_2",
+ "platforms",
+ "subtle",
+ "zeroize",
+]
+
+[[package]]
+name = "der"
+version = "0.7.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "56acb310e15652100da43d130af8d97b509e95af61aab1c5a7939ef24337ee17"
+dependencies = [
+ "const-oid",
+ "zeroize",
+]
+
+[[package]]
 name = "diff"
 version = "0.1.13"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -619,11 +727,20 @@ checksum = "56254986775e3233ffa9c4d7d3faaf6d36a2c09d30b20687e9f88bc8bafc16c8"
 
 [[package]]
 name = "digest"
-version = "0.10.5"
+version = "0.9.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "adfbc57365a37acbd2ebf2b64d7e69bb766e2fea813521ed536f5d0520dcf86c"
+checksum = "d3dd60d1080a57a05ab032377049e0591415d2b31afd7028356dbf3cc6dcb066"
 dependencies = [
- "block-buffer",
+ "generic-array",
+]
+
+[[package]]
+name = "digest"
+version = "0.10.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9ed9a281f7bc9b7576e61468ba615a66a5c8cfdff42420a70aa82701a3b1e292"
+dependencies = [
+ "block-buffer 0.10.3",
  "crypto-common",
  "subtle",
 ]
@@ -667,6 +784,52 @@ dependencies = [
 ]
 
 [[package]]
+name = "ed25519"
+version = "1.5.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "91cff35c70bba8a626e3185d8cd48cc11b5437e1a5bcd15b9b5fa3c64b6dfee7"
+dependencies = [
+ "signature 1.6.4",
+]
+
+[[package]]
+name = "ed25519"
+version = "2.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5fb04eee5d9d907f29e80ee6b0e78f7e2c82342c63e3580d8c4f69d9d5aad963"
+dependencies = [
+ "pkcs8",
+ "signature 2.1.0",
+]
+
+[[package]]
+name = "ed25519-dalek"
+version = "1.0.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c762bae6dcaf24c4c84667b8579785430908723d5c889f469d76a41d59cc7a9d"
+dependencies = [
+ "curve25519-dalek 3.2.0",
+ "ed25519 1.5.3",
+ "rand 0.7.3",
+ "serde",
+ "sha2 0.9.9",
+ "zeroize",
+]
+
+[[package]]
+name = "ed25519-dalek"
+version = "2.0.0-rc.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "798f704d128510932661a3489b08e3f4c934a01d61c5def59ae7b8e48f19665a"
+dependencies = [
+ "curve25519-dalek 4.0.0-rc.2",
+ "ed25519 2.2.1",
+ "serde",
+ "sha2 0.10.6",
+ "zeroize",
+]
+
+[[package]]
 name = "either"
 version = "1.8.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -738,6 +901,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "fiat-crypto"
+version = "0.1.20"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e825f6987101665dea6ec934c09ec6d721de7bc1bf92248e1d5810c8cd636b77"
+
+[[package]]
 name = "filedescriptor"
 version = "0.8.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -879,6 +1048,17 @@ dependencies = [
 
 [[package]]
 name = "getrandom"
+version = "0.1.16"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8fc3cb4d91f53b50155bdcfd23f6a4c39ae1969c2ae85982b135750cccaf5fce"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "wasi 0.9.0+wasi-snapshot-preview1",
+]
+
+[[package]]
+name = "getrandom"
 version = "0.2.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "4eb1a864a501629691edf6c15a593b7a51eebaa1e8468e9ddc623de7c9b58ec6"
@@ -970,7 +1150,7 @@ version = "0.12.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "6c49c37c09c17a53d937dfbb742eb3a961d65a994e6bcdcf37e7399d0cc8ab5e"
 dependencies = [
- "digest",
+ "digest 0.10.7",
 ]
 
 [[package]]
@@ -1166,6 +1346,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "iso8601"
+version = "0.4.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e5b94fbeb759754d87e1daea745bc8efd3037cd16980331fe1d1524c9a79ce96"
+dependencies = [
+ "nom",
+]
+
+[[package]]
 name = "itertools"
 version = "0.10.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1202,6 +1391,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "3304a64d199bb964be99741b7a14d26972741915b3649639149b2479bb46f4b5"
 
 [[package]]
+name = "libm"
+version = "0.1.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7fc7aa29613bd6a620df431842069224d8bc9011086b1db4c0e0cd47fa03ec9a"
+
+[[package]]
 name = "libsqlite3-sys"
 version = "0.24.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1281,7 +1476,7 @@ version = "0.10.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "66b48670c893079d3c2ed79114e3644b7004df1c361a4e0ad52e2e6940d07c3d"
 dependencies = [
- "digest",
+ "digest 0.10.7",
 ]
 
 [[package]]
@@ -1467,6 +1662,16 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "b15813163c1d831bf4a13c3610c05c0d03b39feb07f7e09fa234dac9b15aaf39"
 
 [[package]]
+name = "packed_simd_2"
+version = "0.3.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a1914cd452d8fccd6f9db48147b29fd4ae05bea9dc5d9ad578509f72415de282"
+dependencies = [
+ "cfg-if",
+ "libm",
+]
+
+[[package]]
 name = "parking_lot"
 version = "0.11.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1532,7 +1737,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "346f04948ba92c43e8469c1ee6736c7563d71012b17d40745260fe106aac2166"
 dependencies = [
  "base64ct",
- "rand_core",
+ "rand_core 0.6.4",
  "subtle",
 ]
 
@@ -1554,7 +1759,7 @@ version = "0.11.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "83a0692ec44e4cf1ef28ca317f14f8f07da2d95ec3fa01f86e4467b725e60917"
 dependencies = [
- "digest",
+ "digest 0.10.7",
 ]
 
 [[package]]
@@ -1596,12 +1801,28 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "8b870d8c151b6f2fb93e84a13146138f05d02ed11c7e7c54f8826aaaf7c9f184"
 
 [[package]]
+name = "pkcs8"
+version = "0.10.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f950b2377845cebe5cf8b5165cb3cc1a5e0fa5cfa3e1f7f55707d8fd82e0a7b7"
+dependencies = [
+ "der",
+ "spki",
+]
+
+[[package]]
 name = "pkg-config"
 version = "0.3.25"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "1df8c4ec4b0627e53bdf214615ad287367e482558cf84b109250b37464dc03ae"
 
 [[package]]
+name = "platforms"
+version = "3.0.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e3d7ddaed09e0eb771a79ab0fd64609ba0afb0a8366421957936ad14cbd13630"
+
+[[package]]
 name = "poly1305"
 version = "0.8.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1656,13 +1877,36 @@ dependencies = [
 
 [[package]]
 name = "rand"
+version = "0.7.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6a6b1679d49b24bbfe0c803429aa1874472f50d9b363131f0e89fc356b544d03"
+dependencies = [
+ "getrandom 0.1.16",
+ "libc",
+ "rand_chacha 0.2.2",
+ "rand_core 0.5.1",
+ "rand_hc",
+]
+
+[[package]]
+name = "rand"
 version = "0.8.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404"
 dependencies = [
  "libc",
- "rand_chacha",
- "rand_core",
+ "rand_chacha 0.3.1",
+ "rand_core 0.6.4",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.2.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f4c8ed856279c9737206bf725bf36935d8666ead7aa69b52be55af369d193402"
+dependencies = [
+ "ppv-lite86",
+ "rand_core 0.5.1",
 ]
 
 [[package]]
@@ -1672,7 +1916,16 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88"
 dependencies = [
  "ppv-lite86",
- "rand_core",
+ "rand_core 0.6.4",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "90bde5296fc891b0cef12a6d03ddccc162ce7b2aff54160af9338f8d40df6d19"
+dependencies = [
+ "getrandom 0.1.16",
 ]
 
 [[package]]
@@ -1681,7 +1934,16 @@ version = "0.6.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c"
 dependencies = [
- "getrandom",
+ "getrandom 0.2.7",
+]
+
+[[package]]
+name = "rand_hc"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ca3129af7b92a17112d59ad498c6f81eaf463253766b90396d39ea7a39d6613c"
+dependencies = [
+ "rand_core 0.5.1",
 ]
 
 [[package]]
@@ -1699,7 +1961,7 @@ version = "0.4.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "b033d837a7cf162d7993aded9304e30a83213c648b6e389db233191f891e5c2b"
 dependencies = [
- "getrandom",
+ "getrandom 0.2.7",
  "redox_syscall",
  "thiserror",
 ]
@@ -1885,6 +2147,48 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "5583e89e108996506031660fe09baa5011b9dd0341b89029313006d1fb508d70"
 
 [[package]]
+name = "rusty_paserk"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "db0fa9527e508b8e466bbced04aae220b1d87b03a080868931ae7020c87d3902"
+dependencies = [
+ "argon2",
+ "base64 0.13.1",
+ "base64ct",
+ "blake2 0.10.6",
+ "chacha20 0.9.1",
+ "cipher 0.4.4",
+ "curve25519-dalek 4.0.0-rc.2",
+ "digest 0.10.7",
+ "ed25519-dalek 2.0.0-rc.2",
+ "generic-array",
+ "rand 0.8.5",
+ "rusty_paseto",
+ "serde",
+ "sha2 0.10.6",
+ "subtle",
+ "x25519-dalek",
+]
+
+[[package]]
+name = "rusty_paseto"
+version = "0.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "76c81107ec38df7977a58555d21eef19584878a6ce4d0005efbb16438bce19f4"
+dependencies = [
+ "base64 0.13.1",
+ "blake2 0.9.2",
+ "chacha20 0.8.2",
+ "ed25519-dalek 1.0.1",
+ "hex",
+ "iso8601",
+ "ring",
+ "thiserror",
+ "time 0.3.22",
+ "zeroize",
+]
+
+[[package]]
 name = "ryu"
 version = "1.0.11"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1896,7 +2200,7 @@ version = "0.10.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "97a22f5af31f73a954c10289c93e8a50cc23d971e80ee446f1f6f7137a088213"
 dependencies = [
- "cipher",
+ "cipher 0.4.4",
 ]
 
 [[package]]
@@ -2024,7 +2328,20 @@ checksum = "006769ba83e921b3085caa8334186b00cf92b4cb1a6cf4632fbccc8eff5c7549"
 dependencies = [
  "cfg-if",
  "cpufeatures",
- "digest",
+ "digest 0.10.7",
+]
+
+[[package]]
+name = "sha2"
+version = "0.9.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "4d58a1e1bf39749807d89cf2d98ac2dfa0ff1cb3faa38fbb64dd88ac8013d800"
+dependencies = [
+ "block-buffer 0.9.0",
+ "cfg-if",
+ "cpufeatures",
+ "digest 0.9.0",
+ "opaque-debug",
 ]
 
 [[package]]
@@ -2035,7 +2352,7 @@ checksum = "82e6b795fe2e3b1e845bafcb27aa35405c4d47cdfc92af5fc8d3002f76cebdc0"
 dependencies = [
  "cfg-if",
  "cpufeatures",
- "digest",
+ "digest 0.10.7",
 ]
 
 [[package]]
@@ -2087,6 +2404,18 @@ dependencies = [
 ]
 
 [[package]]
+name = "signature"
+version = "1.6.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "74233d3b3b2f6d4b006dc19dee745e73e2a6bfb6f93607cd3b02bd5b00797d7c"
+
+[[package]]
+name = "signature"
+version = "2.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5e1788eed21689f9cf370582dfc467ef36ed9c707f073528ddafa8d83e3b8500"
+
+[[package]]
 name = "slab"
 version = "0.4.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2127,6 +2456,16 @@ dependencies = [
 ]
 
 [[package]]
+name = "spki"
+version = "0.7.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9d1e996ef02c474957d681f1b05213dfb0abab947b446a62d37770b23500184a"
+dependencies = [
+ "base64ct",
+ "der",
+]
+
+[[package]]
 name = "sql-builder"
 version = "3.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2196,13 +2535,13 @@ dependencies = [
  "once_cell",
  "paste",
  "percent-encoding",
- "rand",
+ "rand 0.8.5",
  "rustls",
  "rustls-pemfile",
  "serde",
  "serde_json",
  "sha1",
- "sha2",
+ "sha2 0.10.6",
  "smallvec",
  "sqlformat",
  "sqlx-rt",
@@ -2226,7 +2565,7 @@ dependencies = [
  "once_cell",
  "proc-macro2",
  "quote",
- "sha2",
+ "sha2 0.10.6",
  "sqlx-core",
  "sqlx-rt",
  "syn 1.0.99",
@@ -2262,9 +2601,9 @@ checksum = "73473c0e59e6d5812c5dfe2a064a6444949f089e20eec9a2e5506596494e4623"
 
 [[package]]
 name = "subtle"
-version = "2.4.1"
+version = "2.5.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "6bdef32e8150c2a081110b42772ffe7d7c9032b606bc226c8260fd97e0976601"
+checksum = "81cdd64d312baedb58e21336b31bc043b77e01cc99033ce76ef539f78e965ebc"
 
 [[package]]
 name = "syn"
@@ -2345,6 +2684,33 @@ dependencies = [
 ]
 
 [[package]]
+name = "time"
+version = "0.3.22"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ea9e1b3cf1243ae005d9e74085d4d542f3125458f3a81af210d901dcd7411efd"
+dependencies = [
+ "itoa",
+ "serde",
+ "time-core",
+ "time-macros",
+]
+
+[[package]]
+name = "time-core"
+version = "0.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7300fbefb4dadc1af235a9cef3737cea692a9d97e1b9cbcd4ebdae6f8868e6fb"
+
+[[package]]
+name = "time-macros"
+version = "0.2.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "372950940a5f07bf38dbe211d7283c9e6d7327df53794992d293e534c733d09b"
+dependencies = [
+ "time-core",
+]
+
+[[package]]
 name = "tiny-bip39"
 version = "1.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2354,9 +2720,9 @@ dependencies = [
  "hmac",
  "once_cell",
  "pbkdf2",
- "rand",
+ "rand 0.8.5",
  "rustc-hash",
- "sha2",
+ "sha2 0.10.6",
  "thiserror",
  "unicode-normalization",
  "wasm-bindgen",
@@ -2615,9 +2981,9 @@ checksum = "39ec24b3121d976906ece63c9daad25b85969647682eee313cb5779fdd69e14e"
 
 [[package]]
 name = "universal-hash"
-version = "0.5.0"
+version = "0.5.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "7d3160b73c9a19f7e2939a2fdad446c57c1bbbbf4d919d3213ff1267a580d8b5"
+checksum = "fc1de2c688dc15305988b563c3854064043356019f97a4b46276fe734c4f07ea"
 dependencies = [
  "crypto-common",
  "subtle",
@@ -2652,7 +3018,7 @@ version = "1.3.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "0fa2982af2eec27de306107c027578ff7f423d65f7250e40ce0fea8f45248b81"
 dependencies = [
- "getrandom",
+ "getrandom 0.2.7",
 ]
 
 [[package]]
@@ -2679,6 +3045,12 @@ dependencies = [
 
 [[package]]
 name = "wasi"
+version = "0.9.0+wasi-snapshot-preview1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "cccddf32554fecc6acb585f82a32a72e28b48f8c4c1883ddfeeeaa96f7d8e519"
+
+[[package]]
+name = "wasi"
 version = "0.10.0+wasi-snapshot-preview1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "1a143597ca7c7793eff794def352d41792a93c481eb1042423ff7ff72ba2c31f"
@@ -3002,6 +3374,18 @@ dependencies = [
 ]
 
 [[package]]
+name = "x25519-dalek"
+version = "2.0.0-rc.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "fabd6e16dd08033932fc3265ad4510cc2eab24656058a6dcb107ffe274abcc95"
+dependencies = [
+ "curve25519-dalek 4.0.0-rc.2",
+ "rand_core 0.6.4",
+ "serde",
+ "zeroize",
+]
+
+[[package]]
 name = "xsalsa20poly1305"
 version = "0.9.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/atuin-client/Cargo.toml b/atuin-client/Cargo.toml
index 8147ddca..6492bd15 100644
--- a/atuin-client/Cargo.toml
+++ b/atuin-client/Cargo.toml
@@ -18,7 +18,6 @@ sync = [
   "reqwest",
   "sha2",
   "hex",
-  "base64",
   "generic-array",
   "xsalsa20poly1305",
 ]
@@ -27,6 +26,7 @@ sync = [
 atuin-common = { path = "../atuin-common", version = "15.0.0" }
 
 log = { workspace = true }
+base64 = { workspace = true }
 chrono = { workspace = true }
 clap = { workspace = true }
 eyre = { workspace = true }
@@ -52,15 +52,18 @@ lazy_static = "1"
 memchr = "2.5"
 rmp = { version = "0.8.11" }
 typed-builder = "0.14.0"
+tokio = { workspace = true }
+semver = { workspace = true }
+
+# encryption
+rusty_paseto = { version = "0.5.0", default-features = false }
+rusty_paserk = { version = "0.2.0", default-features = false, features = ["v4", "serde"] }
 
 # sync
 urlencoding = { version = "2.1.0", optional = true }
 reqwest = { workspace = true, optional = true }
 hex = { version = "0.4", optional = true }
 sha2 = { version = "0.10", optional = true }
-base64 = { workspace = true, optional = true }
-tokio = { workspace = true }
-semver = { workspace = true }
 xsalsa20poly1305 = { version = "0.9.0", optional = true }
 generic-array = { version = "0.14", optional = true, features = ["serde"] }
 
diff --git a/atuin-client/record-migrations/20230619235421_add_content_encrytion_key.sql b/atuin-client/record-migrations/20230619235421_add_content_encrytion_key.sql
new file mode 100644
index 00000000..86bf6844
--- /dev/null
+++ b/atuin-client/record-migrations/20230619235421_add_content_encrytion_key.sql
@@ -0,0 +1,3 @@
+-- store content encryption keys in the record
+alter table records
+  add column cek text;
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>>>;
 }
diff --git a/atuin-common/Cargo.toml b/atuin-common/Cargo.toml
index b693a464..ead3df84 100644
--- a/atuin-common/Cargo.toml
+++ b/atuin-common/Cargo.toml
@@ -17,4 +17,7 @@ serde = { workspace = true }
 uuid = { workspace = true }
 rand = { workspace = true }
 typed-builder = { workspace = true }
+eyre = { workspace = true }
+
+[dev-dependencies]
 pretty_assertions = "1.3.0"
diff --git a/atuin-common/src/record.rs b/atuin-common/src/record.rs
index a9c177c0..b46647c3 100644
--- a/atuin-common/src/record.rs
+++ b/atuin-common/src/record.rs
@@ -1,11 +1,21 @@
 use std::collections::HashMap;
 
+use eyre::Result;
 use serde::{Deserialize, Serialize};
 use typed_builder::TypedBuilder;
 
+#[derive(Clone, Debug, PartialEq)]
+pub struct DecryptedData(pub Vec<u8>);
+
+#[derive(Debug, Clone, PartialEq)]
+pub struct EncryptedData {
+    pub data: String,
+    pub content_encryption_key: String,
+}
+
 /// A single record stored inside of our local database
 #[derive(Debug, Clone, PartialEq, Serialize, Deserialize, TypedBuilder)]
-pub struct Record {
+pub struct Record<Data> {
     /// a unique ID
     #[builder(default = crate::utils::uuid_v7().as_simple().to_string())]
     pub id: String,
@@ -35,17 +45,26 @@ pub struct Record {
     pub tag: String,
 
     /// Some data. This can be anything you wish to store. Use the tag field to know how to handle it.
-    pub data: Vec<u8>,
+    pub data: Data,
+}
+
+/// Extra data from the record that should be encoded in the data
+#[derive(Debug, Copy, Clone)]
+pub struct AdditionalData<'a> {
+    pub id: &'a str,
+    pub version: &'a str,
+    pub tag: &'a str,
+    pub host: &'a str,
 }
 
-impl Record {
-    pub fn new_child(&self, data: Vec<u8>) -> Record {
+impl<Data> Record<Data> {
+    pub fn new_child(&self, data: Vec<u8>) -> Record<DecryptedData> {
         Record::builder()
             .host(self.host.clone())
             .version(self.version.clone())
             .parent(Some(self.id.clone()))
             .tag(self.tag.clone())
-            .data(data)
+            .data(DecryptedData(data))
             .build()
     }
 }
@@ -71,7 +90,7 @@ impl RecordIndex {
     }
 
     /// Insert a new tail record into the store
-    pub fn set(&mut self, tail: Record) {
+    pub fn set(&mut self, tail: Record<DecryptedData>) {
         self.hosts
             .entry(tail.host)
             .or_default()
@@ -128,17 +147,93 @@ impl RecordIndex {
     }
 }
 
+pub trait Encryption {
+    fn re_encrypt(
+        data: EncryptedData,
+        ad: AdditionalData,
+        old_key: &[u8; 32],
+        new_key: &[u8; 32],
+    ) -> 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>;
+}
+
+impl Record<DecryptedData> {
+    pub fn encrypt<E: Encryption>(self, key: &[u8; 32]) -> Record<EncryptedData> {
+        let ad = AdditionalData {
+            id: &self.id,
+            version: &self.version,
+            tag: &self.tag,
+            host: &self.host,
+        };
+        Record {
+            data: E::encrypt(self.data, ad, key),
+            id: self.id,
+            host: self.host,
+            parent: self.parent,
+            timestamp: self.timestamp,
+            version: self.version,
+            tag: self.tag,
+        }
+    }
+}
+
+impl Record<EncryptedData> {
+    pub fn decrypt<E: Encryption>(self, key: &[u8; 32]) -> Result<Record<DecryptedData>> {
+        let ad = AdditionalData {
+            id: &self.id,
+            version: &self.version,
+            tag: &self.tag,
+            host: &self.host,
+        };
+        Ok(Record {
+            data: E::decrypt(self.data, ad, key)?,
+            id: self.id,
+            host: self.host,
+            parent: self.parent,
+            timestamp: self.timestamp,
+            version: self.version,
+            tag: self.tag,
+        })
+    }
+
+    pub fn re_encrypt<E: Encryption>(
+        self,
+        old_key: &[u8; 32],
+        new_key: &[u8; 32],
+    ) -> Result<Record<EncryptedData>> {
+        let ad = AdditionalData {
+            id: &self.id,
+            version: &self.version,
+            tag: &self.tag,
+            host: &self.host,
+        };
+        Ok(Record {
+            data: E::re_encrypt(self.data, ad, old_key, new_key)?,
+            id: self.id,
+            host: self.host,
+            parent: self.parent,
+            timestamp: self.timestamp,
+            version: self.version,
+            tag: self.tag,
+        })
+    }
+}
+
 #[cfg(test)]
 mod tests {
-    use super::{Record, RecordIndex};
-    use pretty_assertions::{assert_eq, assert_ne};
+    use super::{DecryptedData, Record, RecordIndex};
+    use pretty_assertions::assert_eq;
 
-    fn test_record() -> Record {
+    fn test_record() -> Record<DecryptedData> {
         Record::builder()
             .host(crate::utils::uuid_v7().simple().to_string())
             .version("v1".into())
             .tag(crate::utils::uuid_v7().simple().to_string())
-            .data(vec![0, 1, 2, 3])
+            .data(DecryptedData(vec![0, 1, 2, 3]))
             .build()
     }
 
diff --git a/atuin/src/command/client/kv.rs b/atuin/src/command/client/kv.rs
index a3f642df..694ee67e 100644
--- a/atuin/src/command/client/kv.rs
+++ b/atuin/src/command/client/kv.rs
@@ -1,7 +1,7 @@
 use clap::Subcommand;
-use eyre::Result;
+use eyre::{Context, Result};
 
-use atuin_client::{kv::KvStore, record::store::Store, settings::Settings};
+use atuin_client::{encryption, kv::KvStore, record::store::Store, settings::Settings};
 
 #[derive(Subcommand)]
 #[command(infer_subcommands = true)]
@@ -29,20 +29,28 @@ pub enum Cmd {
 impl Cmd {
     pub async fn run(
         &self,
-        _settings: &Settings,
+        settings: &Settings,
         store: &mut (impl Store + Send + Sync),
     ) -> Result<()> {
         let kv_store = KvStore::new();
 
+        let encryption_key: [u8; 32] = encryption::load_key(settings)
+            .context("could not load encryption key")?
+            .into();
+
         match self {
             Self::Set {
                 key,
                 value,
                 namespace,
-            } => kv_store.set(store, namespace, key, value).await,
+            } => {
+                kv_store
+                    .set(store, &encryption_key, namespace, key, value)
+                    .await
+            }
 
             Self::Get { key, namespace } => {
-                let val = kv_store.get(store, namespace, key).await?;
+                let val = kv_store.get(store, &encryption_key, namespace, key).await?;
 
                 if let Some(kv) = val {
                     println!("{}", kv.value);