[tor-dev] Proposal 295: Using the ATL construction for relay cryptography (solving the crypto-tagging attack)

[Taylor Yu]

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