<div dir="ltr">Hello tor-devs,<br><br>Martijn Stam and myself have previously worked on analysing the security<div>of proposal 261. Together with Martijn's PhD student, Alessandro Melloni, </div><div>we have now written a proposal for an onion encryption scheme as an</div><div>alternative to Proposals 261 and 295. It builds on the GCM-RUP construction<div>from [ADL17] but it offers a number of improvements over proposal 295. In</div><div>addition to addressing the issues described below we expect it to offer better</div><div>performance. We are currently working on a security proof and potential</div><div>efficiency optimisations for this scheme. In the meantime, we would be very</div><div>happy to hear what you think and any feedback you may have. If something</div><div>is unclear, please let us know.<br><br>Best,<br><br>Martijn, Alessandro, and Jean Paul<br><br>---------------------<br><br>In our assessment of proposal 295 we identified the following issues:<br><br>a) Improper use of the universal hash function. The proposal suggested<br>using GHASH, a universal hash function, to compute the digest.<br>Universal hash functions require their input to be independent of the<br>hash key for security to hold. This is also a basic requirement in the<br>tweakable block cipher construction, underlying the PIV and RUP<br>constructions. However, the construction requires feeding back the<br>digest (which is key-dependent) back into the input of the hash. Note<br>that such feedback was not present in [ADL17] and the security proof<br>breaks down with this modification.<br><br>b) Lack of Forward Security for any type of hash function that is<br>used. If instantiated with GHASH, proposal 295 does not provide forward<br>security (as it is easy to invert given the hash key). The designers<br>suggested (on the Tor dev mailing list) that forward security could be<br>achieved by instantiating the hash function with SHA2 or SHAKE instead.<br>Clearly this degrades the efficiency of the scheme but, as we argue<br>below, it still does not suffice to achieve forward security<br>Specifically, even if the hash function is instantiated with an ideal<br>hash function (a random oracle), the construction succumbs to the<br>following attack.<br><br>Assume that the last OR in a circuit of length n has already processed<br>some cells and that its current state is (Kf_n, Kb_n, Ktf_n, Ktb_n, Khf_n,</div><div>Khb_n, Tf'_n, Tf'_{n+1}, Tb'_n, Tb'_{n+1}). An adversary, who has collected<br>previous ciphertexts and nonces (C, N), then corrupts it. The adversary has</div><div>enough information to recover the last message received by OR_n, which</div><div>it computes as follows:<br><br>N_{n+1} = Tf'_n ^ D(Ktf_n, Tf'_n ^ N_n)<br>M = Decrypt(Kf_n, N_{n+1}, C_n).<br><br>Clearly this breaks forward security, and it is enabled by the fact that the</div><div>current digest needs to be saved for computing the next digest for when</div><div>another ciphertext is received.<br></div></div><div><br></div><div><br></div><div>[ADL17] Tomer Ashur, Orr Dunkelman, Atul Luykx, "Boosting Authenticated<br>Encryption Robustness with Minimal Modifications", CRYPTO 2017.<br></div></div>