Question about encrypting paths

[declanvk]

Hello, I had a question about the procedure for encrypting paths from https://willowprotocol.org/specs/e2e/index.html#e2e_paths. I'm a bit confused and I thought I would ask the authors, but this isn't a true "issue". If you'd prefer inquiry via email or other, please let me know and I can resend this.

---

Using the terminology from that section:

key_0 = the input key material
kdf(key, byte string) = new key

I'm going to add a new function for my own understanding

encrypt_path(key_0, path) = encrypted path
# where paths are lists of byte strings

The first bullet point is straightforward:

Encrypting the empty Path yields the empty Path again.

encrypt_path(key_0, []) = []

The second bullet point:

Encrypt Paths with a single Component component_0 using the key kdf(key_0, component_0).

Is probably where I start to go wrong. My reading of the part "Encrypt [...] using the key [...]" implies there should be some sort of other encryption function? I was imagining a symmetric cipher like:

cipher_encrypt(key, plaintext) = ciphertext
# where plaintext and ciphertext are both byte strings

Then the encrypt_path for this bullet point would be:

encrypt_path(key_0, ["first"]) = [cipher_encrypt(kdf(key_0, "first"), "first")]

The third bullet point:

For any other (longer) Path , denote its final Component as component_i, the Path formed by its prior Components as path_i, and denote the key that is used to encrypt the final Component of path_i as key_i. You then encrypt the Path by first encrypting path_i, and then appending kdf(key_i, component_i) as the final Component.

So at this point I tried to figure out the length 2 case:

encrypt_path(key_0, ["first", "second"]) = ?

component_i = "second"
path_i = ["first"]
key_i = kdf(key_0, "first")

encrypt_path(key_0, ["first", "second"]) = encrypt_path(key_0, ["first"]) || kdf(key_i, "second")
                                         = [cipher_encrypt(kdf(key_0, "first"), "first")] || kdf(kdf(key_0, "first"), "second")
                                         = [cipher_encrypt(kdf(key_0, "first"), "first"), kdf(kdf(key_0, "first"), "second")]

But that feels weird because then the first component is encrypted with the cipher_encrypt, but the second component is not.

My main question: does the cipher_encrypt function actually exist in this procedure? Or did I imagine it into existence? Is the kdf function sufficient to provide confidentiality of the plaintext path components? Is that part of what you meant by:

As long as the kdf is non-invertable even for known Components, no other Paths can be decrypted beyond the point where they differ.

Other question(s) (less important, feel free to ignore):

• Does the key_0 input key material need to be communicated between peers outside of the willow sync protocol?

---

Thanks for working on the Willow protocol! Sorry am cryptography noob

[AljoschaMeyer]

Hey, those are good questions, and the answer is that we made a mistake in the writeup. In the inductive case, where the website says

You then encrypt the Path by first encrypting path_i, and then appending kdf(key_i, component_i) as the final Component.

it should really say

..., and then appending the result of encrypting component_i with the key kdf(key_i, component_i) as the final Component.

I'll push a fix when I'm properly awake (just past midnight in my timezone right now). I'll also mull over a formulation for making cipher_encrypt explicit. Thanks for reading this carefully!

Regarding communication of the initial keying material: this is indeed not covered by the WGPS protocol. There are several communication issues around capabilities and encryption that will benefit from standardized protocols, and we plan to tackle those eventually. It will just take a while until we get there. But we should probably put some disclaimers saying as much onto the website.

[AljoschaMeyer]

Turns out there was a bit more to fix, there was an off-by-one in which components to feed to the key derivation function. https://github.com/earthstar-project/willowprotocol.org/commit/063b7748f0f87d0d4f02ca42256f342d0c6d4c4c should fix everything

[declanvk]

Thanks so much for responding and pushing a fix! I'll mark this resolved since you got all my questions