from [ADL17] but it offers a number of improvements over proposal 295. In

addition to addressing the issues described below we expect it to offer better

performance. We are currently working on a security proof and potential

efficiency optimisations for this scheme. In the meantime, we would be very

happy to hear what you think and any feedback you may have. If something

is unclear, please let us know.

Best,

Martijn, Alessandro, and Jean Paul

---------------------

In our assessment of proposal 295 we identified the following issues:

a) Improper use of the universal hash function. The proposal suggested
using GHASH, a universal hash function, to compute the digest.
Universal hash functions require their input to be independent of the
hash key for security to hold. This is also a basic requirement in the
tweakable block cipher construction, underlying the PIV and RUP
constructions. However, the construction requires feeding back the
digest (which is key-dependent) back into the input of the hash. Note
that such feedback was not present in [ADL17] and the security proof
breaks down with this modification.

b) Lack of Forward Security for any type of hash function that is
used. If instantiated with GHASH, proposal 295 does not provide forward
security (as it is easy to invert given the hash key). The designers
suggested (on the Tor dev mailing list) that forward security could be
achieved by instantiating the hash function with SHA2 or SHAKE instead.
Clearly this degrades the efficiency of the scheme but, as we argue
below, it still does not suffice to achieve forward security
Specifically, even if the hash function is instantiated with an ideal
hash function (a random oracle), the construction succumbs to the
following attack.

Assume that the last OR in a circuit of length n has already processed
some cells and that its current state is (Kf_n, Kb_n, Ktf_n, Ktb_n, Khf_n,

Khb_n, Tf'_n, Tf'_{n+1}, Tb'_n, Tb'_{n+1}). An adversary, who has collected
previous ciphertexts and nonces (C, N), then corrupts it. The adversary has

enough information to recover the last message received by OR_n, which

it computes as follows:

N_{n+1} = Tf'_n ^ D(Ktf_n, Tf'_n ^ N_n)
M = Decrypt(Kf_n, N_{n+1}, C_n).

Clearly this breaks forward security, and it is enabled by the fact that the

current digest needs to be saved for computing the next digest for when

another ciphertext is received.