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