Re: [tor-dev] Comparing Proposals 295 and 308

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@xxxxxxxxxxxxxxxx> 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