Hello everyone, Below is our response to the main issues raised by Tomer in his previous email. We went into some detail in order to better convey the severity of the issues we raised. In summary the main points are the following: 1) The feedback in the polynomial hash is dangerous and renders the overall security of proposal 295 unclear. This is not a mere technicality as evidenced by our attack below. We show, for a reasonable choice of hash function, an attack that breaks basic IND-CPA security of the original specification of proposal 295. 2) Proposals 202 and 261 already mention forward security as a desirable feature. Proposal 295 provides no forward security at all - see the attack below. Even if the hash function in 295 is replaced with SHA3, at the expense of a substantial toll in performance, proposal 308 would still offer better forward security. 3) A main observation in 308 is that in order to protect against tagging attacks, RUP security is not needed at the uppermost layer. It is by making that deviation that 308 manages to attain forward security, in a provable way, without deteriorating the efficiency. (We actually expect it to be faster than 295 as the last node requires only 2 passes Instead of 3). Tomer makes a valid point that having RUP security at the uppermost layer would be beneficial in the event that an implementation screws up that particular IF statement. However, as we explain below, in the specific case of Tor we do not expect this to be much of an issue. A more in-depth technical discussion of these points is provided below. We start by stating our case as to why the basic security of 295 does not stand on solid ground, then discuss its forward insecurity, and finally argue why we believe RUP is largely irrelevant as an end-to-end design goal for Tor. Overall, the security of 295 is currently unclear and it most likely requires changes (from GHASH to a more costly and heavy weight primitive). As far as we can see, the only benefit that this modified 295 would have over 308 is end-to-end RUP security. On the other hand 308 offers forward security (whereas 295 does not), better performance, and it follows well-established design choices. Moreover, forward security is not easy to add on for any scheme, especially when considering leaky pipes. We advocate that a scheme should be designed and analysed as a whole and are worried that 295 would require considerable modifications to attain provable, ordinary security, let alone meaningful forward security. (1) ``SUBTLETIES'' CONCERNING THE (IN)SECURITY OF PROPOSAL 295. Proposal 295 is based on [ADL17]. In [ADL17] a proof of security is provided to obtain authenticated encryption secure against release of unverified plaintext. [ADL17] crucially relies on a wide-tweak tweakable blockcipher. In proposal 295 this wide-tweak tweakable blockcipher is instantiated with a universal hash function (GHASH) combined with AES in XEX mode, following results in [ST13], [MI15] and [LRW02]. However, the problem is that all that theory only applies to a setting where the tweakable blockcipher is called as a stateless whole. In proposal 295 the output of the universal hash function (T'_1, T'_2, T'_3, T'_4) is fed back into the input of the next invocation of this universal hash function. This mechanism, designed to prevent replay and reorder attacks, results in an unfortunate key-dependency that invalidates the idea that the universal hash together with AES in XEX modes operates as a tweakable blockcipher. We disagree that this key-dependency is just a subtlety and we don't see a straightforward way to fix it in a security proof. In general, dealing with key-dependency in security proofs is far from trivial. Our observation that feeding a key-dependent input to a polynomial hash breaks down the security proof goes beyond the proof in [ADL17]. Indeed the results in [ST13], [MI15], [LRW02] all require the hash function to be Almost-XOR-Universal (AXU) and similarly the security of GCM and GCM-SIV rests on GHASH and POLYVAL being AXU secure. Now our point is that the feedback employed in 295 is outside the model of AXU security and it invalidates the results in [ADL17], [ST13], [MI15], [LRW02]. Addressing this issue requires either major alterations to the results in [MI15] and [LRW02] to cater for this feedback or identifying a new non-standard security property for the hash function which suffices to prove the security of 295 and show that POLYVAL or GHASH satisfy that property. To see that feeding the digest of an AXU hash back into its input is dangerous and not just a theoretical curiosity, consider the following. For fixed-size inputs A = A1||..||Am (consisting of m blocks each of which represents an element in GF(2^n)) and a hash key K \in GF(2^n), the hash function defined by H(K,A) = A1.K + .. + Am.K^m is a perfectly valid AXU hash. Now we construct inputs A, B, and C as follows: A = A1||0^n||..||0^n, B = Ta||-A1||0^n||...||0^n where Ta = H(K,A), D = Tb||0^n||...||0^n where Tb = H(K,B). As you can see B contains the digest of A, and D contains the digest of B. Now, evaluating the digests of A and B we get that: H(K,A) = A1.K = Ta H(K,B) = Ta.K -A1.K^2 = A1.K^2 - A1.K^2 = 0 = Tb H(K,D) = 0 As you can see, irrespective of the value of the key K, we are able to set H(K,B) = 0 (with probability 1), and even worse we have that H(K,B) = H(K,D) = 0 for B \neq D. This should not be possible for an AXU hash, but because inputs B and D are key-dependent this is now possible. Note how this corresponds to the setting in 295 (see https://people.torproject.org/~nickm/prop295/cascade.pdf) where T' is initialised to a fixed known value -- in this case A1. Then the above choice of messages (M = -A1||0^n||...||0^n and M' = 0^n||...||0^n) would result in identical values of N_4 and consequently related layer-3 ciphertexts, where C_3 \xor C'_3 = M \xor M', thereby breaking IND-CPA security. At a more fundamental level, this attack also serves to show that the combination of AXU hash and block cipher, in this feedback configuration, does not yield a secure tweakable block cipher. Looking at the email discussion from July 11th, 295 originally specified T' to be initialised to a constant value but was later amended to be initialised to a random secret value via the KDF. Thus, because of this feedback mechanism, the original proposal would have failed to satisfy even basic IND-CPA security. Moreover, the change in the way T' is initialised seems to have been adopted only as an extra precautionary measure (proposed by Nick) rather than purposefully to stifle this attack. We hope that this convinces you that although it looks like a minor difference the feedback mechanism has significant consequences on security. We didn't find an attack on 295 in its current form and it might be possible to prove it secure. However it should be noted that it is a rather unorthodox construction which deviates significantly from the way that AXU hash functions (like GHASH and POLYVAL) are normally used and thus its security simply cannot be taken for granted. The construction appears brittle and would need a dedicated security analysis. A secondary issue is the choice of hash function. Proposal 295 specifies an Almost-XOR-Universal hash function (GHASH), though later in July 2019, Tomer suggested that, in the context of forward security one would probably need something stronger and more costly, referring detailed analysis (and see below). From the most recent email we get the impression that Proposal 295 should be understood to work with an AXU (as specified), although the statement "GHASH or POLYVAL or any other collision resistant hash function are all the same to us" confuses us. Collision resistant hash functions and AXU hash functions are really quite different beasts and GHASH and POLYVAL are expressly not preimage or collision-resistant hash functions. Clearly, the choice of primitive affects both security and efficiency. We contend that Proposal 295 should not be using an AXU, whereas our proposal can. (2) THE FORWARD (IN)SECURITY OF 295 Note that forward security was already indicated as one of the desired goals of new relay cryptography in proposals 202 and 261. "A more reasonable definition for forward secrecy would be that no message can be decrypted *after* the state (including ephemeral secrets) that was used to generate this message was replaced." In general the security goal should be independent of the internal workings of a scheme, and hence it should not depend on when the scheme updates its state. Rather it is the other way round: forward security requires that once a message has been decrypted, the state ought to be updated immediately. The literature on forward security conforms to this principle as well. "I find that the attack is not very convincing." It is true that the attack we described in our previous email recovers only the last ciphertext. However this was under the assumption that the hash function is a *random oracle*. This was meant to show that even for a stronger and less efficient choice of hash function (like SHA3) 295 would still not be able to attain full-fledged forward security. However, with a hash function like GHASH or POLYVAL, the situation is much worse as 295 provides no forward security whatsoever. Referring once again to the notation used in: https://people.torproject.org/~nickm/prop295/cascade.pdf consider the following attack. Given the current state of the exit node (Ktf3, Khf3, T'_3, T'_4) and the sequence of prior ciphertexts pairs (N3, C3), the attacker can use this information to recover previous values of T'_3 and T'_4. Let T''_3 represent the preceding value of T'_3, then T'_3 = GHASH(Khf3, T''_3 || C_3) which yields a linear equation with only one unknown: T''_3. A similar situation arises for T''_4 an it thus can also be recovered. Once T''_3 and T''_4 are recovered, the same process can be repeated to recover the previous values in an iterative fashion. Note that this recovers all key and state material thereby allowing the decryption of all prior ciphertexts. (3) AUTHENTICATION AND THE IF STATEMENT. "authentication of the last node depends solely on the proper execution of the IF statement on Line 266. As a result, if this line is skipped for some reason (e.g., because an adversary corrupted the last node, a bug, or as a result of over-optimization), modified messages may leave the network. " Both 295 and 308 have an IF statement that if bypassed authenticity would be broken. The difference is that in 308 the adversary would have control over the plaintext (a chosen forgery), whereas in 295 the plaintext would be randomised (an existential forgery). This is the only difference here. For general AEAD schemes this would normally be considered as providing robustness against misuse. However in the specific case of Tor we do not see this to be much of an issue for the reasons set out below. This choice has an effect on efficiency: the last round in 308 requires only *two passes* whereas 295 requires *three passes*. Thus the last layer decryption in 308 is more efficient than 295 thereby reducing the load on the exit nodes. Now consider the scenarios listed by Tomer in which the IF statement could be skipped: a) The last node is corrupted - If the exit node is corrupted then no authenticity is possible. Remember that authenticity is only end-to-end and if the last node is corrupted it can always output any message of its choice. b) Thus the only setting where it makes sense to consider this possibility is that of a bad implementation. However, to begin with, Tor is a relatively closed ecosystem, in that there aren't that many implementations of onion relays. More importantly however, such a flaw is unlikely to go unnoticed as it would affect correct functionality due to the leaky-pipe architecture. If a ciphertext is accepted even when the IF statement fails then that would cause an intermediate onion router to recognise the ciphertext as its own and consequently the ciphertext would not reach the intended recipient. As such the likelihood of such a bug seems rather remote. Best, Martijn, Alessandro, and Jean Paul ---------------------------------------------- [LRW02] M. Liskov, R. Rivest, D. Wagner, "Tweakable block ciphers", CRYPTO 2002. [MI15] K. Minematsu and T. Iwata, "Tweak-Length Extension for Tweakable Blockciphers", IMACC 2015. [ADL17] Tomer Ashur, Orr Dunkelman, Atul Luykx, "Boosting Authenticated Encryption Robustness with Minimal Modifications", CRYPTO 2017. [ST13] Thomas Shrimpton, R. Seth Terashima, "A Modular Framework for Building Variable-Input Length Tweakable Ciphers", ASIACRYPT 2013. On Wed, Oct 16, 2019 at 10:57 AM Tomer Ashur <tomer.ashur@esat.kuleuven.be> wrote:

Dear all,

Some time ago I sent to this mailing list a proposal for using the ADL construction to solve the crypto tagging attack and it was registered as Proposal 295. Then, about a month ago Jean Paul Degabriele sent another proposal aiming for the same, which was registered as Proposal 308. We’ve now had the chance to compare both proposals and we provide our observations below. But before we discuss the pros and cons of each proposal, I’d like to re-state our goal for Proposal 295. Our aim was to build something that:

1. does not lose any security guarantees that are already in place;

2. prevents successful crypto-tagging; and

3. does not introduce new weaknesses.

We *did not* consider advanced security goals such as forward secrecy and/or non-repudiation which was also mentioned earlier on this mailing list.

In achieving these goals, the two proposals are almost the same: for the encryption part, both use layered encryption where the nonce is tweaked with a digest of the ciphertext, and sent in encrypted form to the next node as part of the ciphertext. The only meaningful difference I could find is that instead of using the output of the universal hash function (i.e., GHASH) as a running digest as is done in Proposal 295, Proposal 308 uses the encrypted nonce. Jean Paul made the correct observation that our security proof did not account for key-dependent input, but we believe that this can be resolved by rewriting the proof. In either case, this is a subtlety and common ground can be found. On a high level, both proposals use the same mechanism to avoid crypto-tagging.

Where the proposals differ is in the authentication part. Proposal 295 makes a functional separation between the encryption part and the authentication part, cf. Lines 150-152 (authentication) and Lines 156-160 (layered encryption). Conversely, Proposal 308 does not offer such separation, and the authentication and encryption of the last node are done in a single pass (cf. Lines 227-230 and Lines 244-252). This comes with what we think are two highly unwanted side effects defeating the purpose of using the ADL construction to begin with: the authentication of the last node depends solely on the proper execution of the IF statement on Line 266. As a result, if this line is skipped for some reason (e.g., because an adversary corrupted the last node, a bug, or as a result of over-optimization), modified messages may leave the network. Moreover, the last layer is malleable which means that a difference introduced to the ciphertext entering the last node will be preserved through the final decryption (given that the IF statement on Line 266 is skipped). This is because the decryption nonce does not depend on the authentication process (in the lingo of Proposal 308 this is called a “dynamic nonce”).

Comparing this to Proposal 295 we see that the same cannot happen. Any change introduced at any point (including the ciphertext entering the last node) will completely destroy the payload in an irrecoverable way (the same happens in the “static layers” of Proposal 308; only the dynamic layer is malleable).

For the record, a corollary of all of this is that if Sf_I is leaked (e.g., via a side channel in the generation process of Nf_I that is used by the IF statement), the adversary now has the secret it needs to decrypt the ciphertext regardless of the authentication process. Not being able to do this is exactly what’s captured by the RUP property used in Proposal 295 in which the only way to obtain N_4 (the counterpart of Proposal 308’s Nf_I) is via a successful digest of an unmodified ciphertext.

The place where Proposal 308 nicely extends over Proposal 295 is in the forward secrecy domain. In an email to this mailing list we conjectured that if certain changes are made to Proposal 295 it will provide forward secrecy in addition to its crypto-tagging resistance. Jean Paul suggested an attack against this conjecture, but I find that the attack is not very convincing. Indeed, once the keys are leaked, the last message can be recovered. But I don’t think that there’s anything surprising in the fact that the set of keys that would have normally decrypted a message will also do so if leaked to an adversary. A more reasonable definition for forward secrecy would be that no message can be decrypted **after** the state (including ephemeral secrets) that was used to generate this message was replaced. Admittedly, Proposal 308 replaces this state earlier than Proposal 295 (immediately after processing the message vs. after processing the next message), which may be desirable, but is anyway not disastrous.

That being said, this discussion is theoretic in nature since of the two proposals, only Proposal 308 offers an actual mechanism. For Proposal 295 we only offer a conjecture. We also tend to somewhat agree that frequent re-keying is a better way to achieve forward secrecy.

Regardless of which is the better way, both can be built on top of the encryption mechanism we offered in Proposal 295 whose goal is to resist crypto-tagging. In the interest of moving forward we propose to implement Proposal 295 as suggested or something close to it (e.g., using POLYVAL) to counter crypto-tagging, then discuss alternatives to achieving forward secrecy and add those on top of the ADL construction via Proposal 308.

A few side notes:

1. Proposal 308 argues that POLYVAL is more suited than GHASH to our this use-case. This is an implementation issue. GHASH or POLYVAL or any other collision resistant hash function are all the same to us.

2. I'm pretty sure there's a typo on Line 250 in Proposal 308 and that the text should be Y_I = Tf_{I+1} ^ X_I. Otherwise, I can't see how the protocol decrypts on Line 285.

3. The lengths in Section 2.2 (marked for revision) are given in bytes, but then in Section 2.3 they are treated as bits.

4. Line 230 has unbalanced parenthesis.

Tomer