On 07/20/2018 02:27 AM, teor wrote:
A few of us discussed this proposal in the #tor-dev IRC earlier this week.
Hi teor, and thanks for writing this summary! I generally agree with what you've written.
We’re confused by 3.1 and 3.2, which seem to be duplicate sections using different notation.
On further reflection, I think sections 3.1 and 3.2 describe two different revisions of the proposal. 3.1 seems to not include the previous tweak (T' in 3.2.2) in computing a new tweak, while 3.2.2 does. It seems like if we adapt 3.1 to incorporate some chaining of the tweak, the scheme will be IND-CPA. (This is because the ciphertext that the endpoint receives will no longer be solely a function of the plaintext and the key.)
I'm going to tentatively propose some more consistent notation here:
C ciphertext
M plaintext message
S encrypted nonce
N CTR mode nonce
T nonce tweak
T' saved nonce tweak
U pre-nonce tweak
U' saved pre-nonce tweak
keys
kf, kb CTR mode key
hf, hb GHASH key
cf, cb nonce-encryption key
gf, gb pre-nonce GHASH key
bf, bb pre-nonce encryption key
(I'm happy to hear feedback on alternative designators.)
-----
single hop outbound (same direction as CREATE):
input C||S
1. T = H_hf(T'||C) -- generate tweak T by hashing saved previous tweak T' and ciphertext C
2. N = T ^ D_cf(S ^ T) -- decrypt encrypted nonce S using AES and tweak T
3. M = C ^ CTR_kf(N) -- decrypt ciphertext C using CTR and nonce N
4. T' = T -- save tweak for next cell
5. output M||N
single hop inbound (same direction as CREATED):
input M||N
1. C = M ^ CTR_kb(N) -- encrypt message M using CTR and nonce N
2. T = H_hb(T'||C) -- generate tweak T by hashing saved previous tweak T' and ciphertext C
3. S = T ^ E_cb(N ^ T) -- encrypt nonce N using AES and tweak T
4. T' = T -- save tweak for next cell
5. output C||S
receiving/decrypting a cell at the endpoint (e.g., exit):
input C||S
1. decrypt as above to obtain M and N
2. U = H_gf(U'||M) -- generate tweak U by hashing saved previous tweak U' and plaintext M
3. V = U ^ D_bf(N ^ U) -- decrypt nonce N with AES and pre-nonce tweak U for verification
4. U' = U -- save pre-nonce tweak for next cell
5. if V == 0, cell is authentic
sending/encrypting a cell from the endpoint:
input M
1. U = H_gb(U'||M) -- generate tweak U by hashing saved previous tweak U' and plaintext M
2. N = U ^ E_bb(0 ^ U) -- generate nonce N by encrypting all-zeroes block using AES and pre-nonce tweak U
3. U' = U
4. encrypt as above using M and N
-----
Open question: what do we initialize the saved tweaks T', U' to? Is it safe to use an all-zeroes block?
Generalising to Different Numbers of Hops
The proposal assumes that all circuits are 3-hop circuits, but Tor typically builds 1, 3, 4, and 5-hop circuits. Also, Tor currently generates the same number of keys for each hop. There’s no way it can just generate kf_M, kf_E, kb_M, and kb_E for the final hop, because sometimes the final hop changes. (Due to circuit cannibalisation, or failed intro extension.)
Please generalise the proposal so that:
- all references to “3-hop circuit” are changed to "N-hop circuit".
- all references to kf_1,2,3, kb_1,2,3, k_fM, k_fE, k_bM and k_bE; are changed to kf_N, kb_N, kfM_N, kfE_N, kbM_N and kbE_N.
Judging by the cited paper, the subkeys k1, k2, k3 are all used in the same hop. Given that we already use digits for hop numbers, we should choose some alphabetic subkey designators.
(In the paper: k1 = CTR key; k2 = GHASH key for computing tweak; k3 = AES key for encrypting nonce.)
Do we really need 6 keys per hop? It’s ok if we do, let’s make sure there are no redundant keys.
It looks like ten keys per hop. Every ordinary relay hop needs the endpoint authentication keys kf_M, kf_E, kb_M, kb_E to handle EXTEND/EXTENDED cells at least.
I'm not sure yet which of these are actually required to be independent to achieve the desired security properties.
Best regards, -Taylor