[tor-dev] Comparing Proposals 295 and 308

Jean Paul Degabriele jpdega at gmail.com
Wed Oct 23 15:39:44 UTC 2019

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
   layer would be beneficial in the event that an implementation screws up
   that particular IF statement. However, as we explain below, in the
   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
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
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
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.

    Proposal 295 is based on [ADL17]. In [ADL17] a proof of security is
provided to
    obtain authenticated encryption secure against release of unverified
    [ADL17] crucially relies on a wide-tweak tweakable blockcipher. In
    295 this wide-tweak tweakable blockcipher is instantiated with a
    hash function (GHASH) combined with AES in XEX mode, following results
    [ST13], [MI15] and [LRW02].

    However, the problem is that all that theory only applies to a setting
    the tweakable blockcipher is called as a stateless whole. In proposal
    the output of the universal hash function (T'_1, T'_2, T'_3, T'_4) is
    back into the input of the next invocation of this universal hash
    This mechanism, designed to prevent replay and reorder attacks, results
    an unfortunate key-dependency that invalidates the idea that the
    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
    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
    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
    issue requires either major alterations to the results in [MI15] and
    to cater for this feedback or identifying a new non-standard security
    property for the hash function which suffices to prove the security of
    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.
    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
    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
    H(K,B) = 0 (with probability 1), and even worse we have that H(K,B) =
    = 0 for B \neq D. This should not be possible for an AXU hash, but
    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
    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,
    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
    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
    basic IND-CPA security. Moreover, the change in the way T' is
    seems to have been adopted only as an extra precautionary measure
    by Nick) rather than purposefully to stifle this attack. We hope that
    convinces you that although it looks like a minor difference the
    mechanism has significant consequences on security. We didn't find an
    on 295 in its current form and it might be possible to prove it secure.
    it should be noted that it is a rather unorthodox construction which
    significantly from the way that AXU hash functions (like GHASH and
    are normally used and thus its security simply cannot be taken for
    The construction appears brittle and would need a dedicated security

    A secondary issue is the choice of hash function. Proposal 295
specifies an
    Almost-XOR-Universal hash function (GHASH), though later in July 2019,
    suggested that, in the context of forward security one would probably
    something stronger and more costly, referring detailed analysis (and see
    below). From the most recent email we get the impression that Proposal
    should be understood to work with an AXU (as specified), although the
    statement "GHASH or POLYVAL or any other collision resistant hash
    are all the same to us" confuses us. Collision resistant hash functions
    AXU hash functions are really quite different beasts and GHASH and
    are expressly not preimage or collision-resistant hash functions.

    Clearly, the choice of primitive affects both security and efficiency.
    contend that Proposal 295 should not be using an AXU, whereas our


    Note that forward security was already indicated as one of the desired
    of new relay cryptography in proposals 202 and 261.

      "A more reasonable definition for forward secrecy would be that no
      can be decrypted *after* the state (including ephemeral secrets) that
      used to generate this message was replaced."

    In general the security goal should be independent of the internal
    of a scheme, and hence it should not depend on when the scheme updates
    state. Rather it is the other way round: forward security requires that
    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
    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
    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:
    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
    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
    this recovers all key and state material thereby allowing the
decryption of
    all prior ciphertexts.


      "authentication of the last node depends solely on the proper
      of the IF statement on Line 266. As a result, if this line is skipped
      some reason (e.g., because an adversary corrupted the last node, a
      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
    the plaintext (a chosen forgery), whereas in 295 the plaintext would be
    randomised (an existential forgery). This is the only difference here.
    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
    an effect on efficiency: the last round in 308 requires only *two
    whereas 295 requires *three passes*. Thus the last layer decryption in
    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
    be skipped:

    a) The last node is corrupted - If the exit node is corrupted then no
       authenticity is possible. Remember that authenticity is only
       and if the last node is corrupted it can always output any message
of its

    b) Thus the only setting where it makes sense to consider this
       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
       not reach the intended recipient. As such the likelihood of such a
       seems rather remote.


Martijn, Alessandro, and Jean Paul


[LRW02] M. Liskov, R. Rivest, D. Wagner, "Tweakable block ciphers", CRYPTO

[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
Variable-Input Length Tweakable Ciphers", ASIACRYPT 2013.

On Wed, Oct 16, 2019 at 10:57 AM Tomer Ashur <tomer.ashur at esat.kuleuven.be>

> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20191023/e9f4fc09/attachment-0001.html>

More information about the tor-dev mailing list