[tor-dev] New revision: Proposal 295: Using ADL for relay cryptography (solving the crypto-tagging attack)

[Tomer Ashur]

Hi Nick,
Atul and I finally got together and have some answers for you:

Python code - I've reviewed it and it seems fine to me. The only changes required are to make the authentication part stateless (see below) and reduce the number of states accordingly. 

Updated proposal - attached. 

> I'm planning to replace HKDF-SHA256 with SHAKE, and AES128 with AES256.
That's fine with us. I've updated the AES128 to AES256 part of the proposal, but didn't want to touch the HKDF-SHA256 to SHAKE part. 

> To clarify, I believe there need to be two separate T'_I values for each
  hop: T'_I for outbound cells, and T'_I for inbound cells.  I suggest
  calling them Tf'_I and Tb'_I.

Yes there should. This is updated in the proposal now. 

> Since Tor allows a relay cell to be addressed to any hop in the circuit, I
  believe that every relay needs to have a separate value for authentication
  state that is currently called T'_{n+1}.  I'm calling this value Ta'_I,
  where the a stands for 'authentication'.

You are right on this. However, in the course of our discussion we've realized that the authentication part can be done in a stateless manner, i.e., T'_{N+1} is not necessary (and therefore neither does Ta'_I). This also obviates your next comment about a conditional update to the running digest. All of this is now reflected in the proposal. 

> Is it really safe to use the same key (Khf_n) for authentication as well
  as for encryption?
Yes. See Figure 1 in https://eprint.iacr.org/2013/835. 

> Is there any reason _not_ to initialize the T' values based on the
  KDF?  It seems to me that setting them to zero might give the attacker
  some information they didn't have before.
There isn't. This is now updated in the proposal (I've used the old DF and DB which were previously marked for deletion). See also my next answer.  

> What forward secrecy, if any, are we getting here?
Short answer: we don't know. 

Longer answer: after discussing this, we conjecture that if the hash function being used to generate T'_I is preimage-resistant and the initial value for T'_I is random (as you suggested above), then you get full forward secrecy. We also conjecture that GHash does not satisfy this condition, i.e., that in the case of a key exposure, it is possible to find preimages, meaning that no forward secrecy is offered by the scheme the way it is right now. Things are likely different if you use something proper like HMAC (our construction works just the same with any secure MAC instead of GHash) or possibly even with just an unkeyed hash function like SHA2 or SHAKE. 

The rationale is as follows: To decrypt a ciphertext from round R you would need to know the respective T'_I. At the end of round R, T'_I is replaced (in an irrecoverable way; this is important) by a new value. Now, to reobtain the old T'_I from the new T'_I you'd need to find a preimage. This is also the reason we need the initial T'_I to be random. Otherwise, an adversary that has access to all previous ciphertexts can compute any T'_I forward by starting from the known initial value for T'_I. 

However, note that neither of us have the time to further investigate and prove this at the moment (and therefore, this isn't reflected in the updated proposal). We're leaving this as an open question and will try to address it at some unknown point in the future, but of course we'd be happy for anyone else to scoop us in doing so. 

Tomer

-----Original Message-----
From: tor-dev <tor-dev-bounces at lists.torproject.org> On Behalf Of Nick Mathewson
Sent: Monday, May 6, 2019 10:09 PM
To: tor-dev at lists.torproject.org
Subject: Re: [tor-dev] New revision: Proposal 295: Using ADL for relay cryptography (solving the crypto-tagging attack)

Hi!

Here are my notes on the latest prop295 that I came up with while doing a reference implementation in Python.  If you're curious, you can see the candidate reference implementation at https://github.com/nmathewson/prop295ref . I'd love to know whether or not the implementation matches the intention of the proposal.

Minor notes:

* I'm planning to replace HKDF-SHA256 with SHAKE, and AES128 with AES256.

* I agree with dropping the 'recognized' field.  I didn't implement it here.

More important issues:

* To clarify, I believe there need to be two separate T'_I values for each
  hop: T'_I for outbound cells, and T'_I for inbound cells.  I suggest
  calling them Tf'_I and Tb'_I.

* Since Tor allows a relay cell to be addressed to any hop in the circuit, I
  believe that every relay needs to have a separate value for authentication
  state that is currently called T'_{n+1}.  I'm calling this value Ta'_I,
  where the a stands for 'authentication'.

* I believe that the authentication algorithm in section 4.1 does not if
  cells may be addressed to hops other than the last hop.  It needs to change
  as follows:

             T_{n+1} = Digest(Khf_n,T'_{n+1}||C_{n+1})
             Tag = T_{n+1} ^ D(Ktf_n,T_{n+1} ^ N_{n+1})

             If Tag = 0:
                  T'_{n+1} = T_{n+1}
                  The message is authenticated.
             Otherwise:
                  T'_{n+1} remains unchanged.
                  The message is not authenticated.

  The change here is that I think T'_{n+1} (which I'd like to call Ta'_I)
  should only change when the message is authenticated.

Some questions about issues I don't understand:

* Is it really safe to use the same key (Khf_n) for authentication as well
  as for encryption?

* Is there any reason _not_ to initialize the T' values based on the
  KDF?  It seems to me that setting them to zero might give the attacker
  some information they didn't have before.

* What forward secrecy, if any, are we getting here?

many thanks,
--
Nick
_______________________________________________
tor-dev mailing list
tor-dev at lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: 295-relay-crypto-with-adl.txt
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20190711/c0bf485f/attachment-0001.txt>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Proposal_295.diff
Type: application/octet-stream
Size: 10397 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20190711/c0bf485f/attachment-0001.obj>