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
_______________________________________________
tor-dev mailing list
[email protected]
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
