[tor-dev] Proposal 216 (ntor) redux

[Nick Mathewson]

Here's a slightly updated version of the ntor proposal, as changed
while I was doing the implementation (see [A]  for more information on
that).  For a diff between the old version and the new one, see [B].

The interesting changes were:
  * To specify that the key expansion uses HKDF from RFC5869. (This is
the standardized version of originally recommended key expansion
approach.)
  * To specify that the length of a node ID is ID_LENGTH bytes, not H_LENGTH.
  * To make the t_key tweak value not be a prefix of the m_expand
value.  This is probably cosmetic.
  * To specify a way for embedding these handshakes in
EXTEND/EXTENDED/CREATE/CREATED cells so that they can be used to
extend from a server that doesn't know about proposal 200.
  * To specify checking EXP() outputs for the point at infinity rather
than checking inputs for group membership.  I am not convinced this is
necessary [C], but Ian Goldberg thought it was a good idea.

The ntor branch has a reference implementation of the handshake in
src/test/ntor_ref.py [D] which has been verified to interoperate with
the C implementation.


[A] https://trac.torproject.org/projects/tor/ticket/7202
[B] https://gitweb.torproject.org/torspec.git/blobdiff/08b4c89058e7704f9cdb1e11407c7d1c8186c0cd..HEAD:/proposals/216-ntor-handshake.txt
[C] If a client generates a bad public key, it will at worst get no
security.  If a server generates a bad public key, it will at worst
provide no security--but a server that wants to provide no security
can already leak its outputs.  The case to worry about would be if an
MITM attacker replaced the X value or the Y value when communicating
between the server and the client.  But I believe that the inclusion
of X and Y in the auth_input and secret_input steps prevents such an
MITM attacker from successfully convincing the client that the
handshake was successful.  Still, "belt and suspenders."
[D] https://gitweb.torproject.org/nickm/tor.git/blob_plain/ntor:/src/test/ntor_ref.py

====
Filename: 216-ntor-handshake.txt
Title: Improved circuit-creation key exchange
Author:  Nick Mathewson
Created: 11-May-2011
Status: Open

Summary:

  This is an attempt to translate the proposed circuit handshake from
  "Anonymity and one-way authentication in key-exchange protocols" by
  Goldberg, Stebila, and Ustaoglu, into a Tor proposal format.

  It assumes that proposal 200 is implemented, to provide an extended CREATE
  cell format that can indicate what type of handshake is in use.

Notation:

  Let a|b be the concatenation of a with b.

  Let H(x,t) be a tweakable hash function of output width H_LENGTH bytes.

  Let t_mac, t_key, and t_verify be a set of arbitrarily-chosen tweaks
  for the hash function.

  Let EXP(a,b) be a^b in some appropriate group G where the appropriate DH
  parameters hold.  Let's say elements of this group, when represented as
  byte strings, are all G_LENGTH bytes long.  Let's say we are using a
  generator g for this group.

  Let a,A=KEYGEN() yield a new private-public keypair in G, where a is the
  secret key and A = EXP(g,a).  If additional checks are needed to insure
  a valid keypair, they should be performed.

  Let PROTOID be a string designating this variant of the protocol.

  Let KEYID be a collision-resistant (but not necessarily preimage-resistant)
     hash function on members of G, of output length H_LENGTH bytes.

  Let each node have a unique identifier, ID_LENGTH bytes in length.

Instantiation:

  Let's call this PROTOID "ntor-curve25519-sha256-1"  (We might want to make
  this shorter if it turns out to save us a block of hashing somewhere.)

  Set H(x,t) == HMAC_SHA256 with message x and key t. So H_LENGTH == 32.
  Set t_mac   == PROTOID | ":mac"
      t_key  == PROTOID | ":key_extract"
      t_verify  == PROTOID | ":verify"

  Set EXP(a,b) == curve25519(.,b,a), and g == 9 .  Let KEYGEN() do the
  appropriate manipulations when generating the secret key (clearing the
  low bits, twiddling the high bits).

  Set KEYID(B) == B.  (We don't need to use a hash function here, since our
     keys are already very short.  It is trivially collision-resistant, since
     KEYID(A)==KEYID(B) iff A==B.)

Protocol:

  Take a router with identity key digest ID.

  As setup, the router generates a secret key b, and a public onion key
  B with b, B = KEYGEN().  The router publishes B in its server descriptor.

  To send a create cell, the client generates a keypair x,X = KEYGEN(), and
  sends a CREATE cell with contents:

    NODEID:     ID             -- ID_LENGTH bytes
    KEYID:      KEYID(B)       -- H_LENGTH bytes
    CLIENT_PK:  X              -- G_LENGTH bytes

  The server generates a keypair of y,Y = KEYGEN(), and computes

    secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID
    KEY_SEED = H(secret_input, t_key)
    verify = H(secret_input, t_verify)
    auth_input = verify | ID | B | Y | X | PROTOID | "Server"

  The server sends a CREATED cell containing:

    SERVER_PK:  Y                     -- G_LENGTH bytes
    AUTH:       H(auth_input, t_mac)  -- H_LENGTH byets

  The client then checks Y is in G^* [see NOTE below], and computes

    secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID
    KEY_SEED = H(secret_input, t_key)
    verify = H(secret_input, t_verify)
    auth_input = verify | ID | B | Y | X | PROTOID | "Server"

    The client verifies that AUTH == H(auth_input, t_mac).

  Both parties check that none of the EXP() operations produced the point at
  infinity. [NOTE: This is an adequate replacement for checking Y for group
  membership, if the group is curve25519.]

  Both parties now have a shared value for KEY_SEED.  They expand this into
  the keys needed for the Tor relay protocol.

Key expansion:

  Currently, the key expansion formula used by Tor here is

       K = SHA(K0 | [00]) | SHA(K0 | [01]) | SHA(K0 | [02]) | ...

       where K0==g^xy, and K is divvied up into Df, Db, Kf, and Kb portions.

  Instead, let's have it be HKDF-SHA256 as defined in RFC5869:

       K = K_1 | K_2 | K_3 | ...

       Where K_1     = H(m_expand | INT8(1) , KEY_SEED )
         and K_(i+1) = H(K_i | m_expand | INT8(i) , KEY_SEED )
         and m_expand is an arbitrarily chosen value,
         and INT8(i) is a octet with the value "i".

  Ian says this is due to a construction from Krawczyk at
  http://eprint.iacr.org/2010/264 .

  Let m_expand be PROTOID | ":key_expand"

  In RFC5869's vocabulary, this is HKDF-SHA256 with info == m_expand,
  salt == t_key, and IKM == secret_input.

Performance notes:

  In Tor's current circuit creation handshake, the client does:
     One RSA public-key encryption
     A full DH handshake in Z_p
     A short AES encryption
     Five SHA1s for key expansion
  And the server does:
     One RSA private-key decryption
     A full DH handshake in Z_p
     A short AES decryption
     Five SHA1s for key expansion

  While in the revised handshake, the client does:
     A full DH handshake
     A public-half of a DH handshake
     3 H operations for the handshake
     3 H operations for the key expansion
  and the server does:
     A full DH handshake
     A private-half of a DH handshake
     3 H operations for the handshake
     3 H operations for the key expansion

Integrating with the rest of Tor:

  Add a new optional entry to router descriptors and microdescriptors:

     "ntor-onion-key" SP Base64Key NL

  where Base64Key is a base-64 encoded 32-byte value, with padding
  omitted.

  Add a new consensus method to tell servers to copy "ntor-onion-key"
  entries to from router descriptors to microdescriptors.

  In microdescriptors, "ntor-onion-key" can go right after the "onion-key"
  line.

  Add a "UseNTorHandshake" configuration option and a corresponding
  consensus parameter to control whether clients use the ntor
  handshake.  If the configuration option is "auto", clients should
  obey the consensus parameter.  Have the configuration default be
  "auto" and the consensus value initially be "0".

  Reserve the handshake type [00 02] for this handshake in CREATE2 and
  EXTEND2 cells.

  Specify that this handshake type can be used in EXTEND/EXTENDED/
  CREATE/CREATED cells as follows: instead of a 190-byte TAP onionskin, send
  the 16-byte string "ntorNTORntorNTOR", followed by the client's ntor
  message.  Instead of a 148-byte TAP response, send the server's ntor
  response.  (We need this so that a client can extend from an 0.2.3 server,
  which doesn't know about CREATE2/CREATED2/EXTEND/EXTENDED2.)

Test vectors for HKDF-SHA256:

 These are some test vectors for HKDF-SHA256 using the values for M_EXPAND
 and T_KEY above, taking 100 bytes of key material.

  INPUT: "" (The empty string)
  OUTPUT: d3490ed48b12a48f9547861583573fe3f19aafe3
          f81dc7fc75eeed96d741b3290f941576c1f9f0b2
          d463d1ec7ab2c6bf71cdd7f826c6298c00dbfe67
          11635d7005f0269493edf6046cc7e7dcf6abe0d2
          0c77cf363e8ffe358927817a3d3e73712cee28d8

  INPUT: "Tor" (546f72)
  OUTPUT: 5521492a85139a8d9107a2d5c0d9c91610d0f959
          89975ebee6c02a4f8d622a6cfdf9b7c7edd3832e
          2760ded1eac309b76f8d66c4a3c4d6225429b3a0
          16e3c3d45911152fc87bc2de9630c3961be9fdb9
          f93197ea8e5977180801926d3321fa21513e59ac

  INPUT: "AN ALARMING ITEM TO FIND ON YOUR CREDIT-RATING STATEMENT"
         (414e20414c41524d494e47204954454d20544f2046494e44204f4e20
          594f5552204352454449542d524154494e472053544154454d454e54)
  OUTPUT: a2aa9b50da7e481d30463adb8f233ff06e9571a0
          ca6ab6df0fb206fa34e5bc78d063fc291501beec
          53b36e5a0e434561200c5f8bd13e0f88b3459600
          b4dc21d69363e2895321c06184879d94b18f0784
          11be70b767c7fc40679a9440a0c95ea83a23efbf