Hello tor-devs,

Martijn Stam and myself have previously worked on analysing the security of proposal 261. Together with Martijn's PhD student, Alessandro Melloni, we have now written a proposal for an onion encryption scheme as an alternative to Proposals 261 and 295. It builds on the GCM-RUP construction 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.

[ADL17] Tomer Ashur, Orr Dunkelman, Atul Luykx, "Boosting Authenticated Encryption Robustness with Minimal Modifications", CRYPTO 2017.