[tor-dev] basket: More eggs in the Guard basket.

Yawning Angel yawning at schwanenlied.me
Tue Dec 16 14:53:04 UTC 2014

Hi all,

For several reasons I've been working on a bit of code that I named
"basket".  It's almost at the point where the brave members of the
general public should be aware that it exists as a potential option in
the privacy toolbox, though using it in any capacity beyond testing on
a loopback device IS CURRENTLY ACTIVELY DISCOURAGED unless users are
comfortable debugging it (This means, DO NOT USE IT.  I will likely
break backward compatibility in the future, and you will be sad.).

"basket" is my stab at designing something that significantly increases
Tor's resistance to upcoming/future attacks, by providing a link layer
cryptographic handshake that uses post-quantum cryptographic primitives
and defenses against website fingerprinting (and possibly e2e
correlation) attacks.

For the ease of development it is in the form of a pluggable transport
with the expected tradeoffs (you must absolutely trust your Bridge,
since both features only run to the Bridge).  It is worth noting that
it is anything but subtle, and it is blatantly obvious that a given
connection is speaking "basket" as no attempt was made to obfuscate the

The link layer handshake works roughly like thus:
  * Bob generates a long term SPHINCS256 keypair s,S used to sign

 The handshake:
  1. Alice generates a Curve25519 keypair x,X and a NTRUEncrypt
     EES1171EP1 keypair n,N.
  2. Alice sends X | N to Bob.
  3. Bob generates a Curve25519 keypair y,Y, and calculates
     Curve25519(y,X) as the shared secret.
  4. Bob sends NTRUEncrypt(N,Y) | S | SPHINCS256(s, ntru_ciphertext |
     S) to Alice.
  5. Alice verifies the SPHINCS256 signature (Alice's copy of S is
     saved/trusted in a Trust-On-First-Use manner), and decrypts the
     NTRU ciphertext to obtain Y.
  6. Alice calculates Curve25519(x,Y) as the shared secret.  

  NB: Some details omitted for brevity.

Passive attackers see Alice's Curve25519 public key, Alice's
NTRUEncrypt public key, Bob's SPHINCS256 public key, a NTRUEncrypt
ciphertext, and SPHINCS256 signature.  Obtaining the link's ephemeral
session key requires decrypting the NTRUEncrypt ciphertext (to obtain
Bob's Curve25519 public key), and reversing the scalar base multiply on
one of X and Y.

Active man-in-the-middle attackers need to be able to forge SPHINCS256
signatures to substitute their own NTRUEncrypt-ed payload to mount an
attack (Alice's request is also validated/protected but it's one of the
details omitted, read the code).

As NTRUEncrypt is patent encumbered, there also is a handshake mode
that removes the experimental post-quantum cryptography and uses

The fingerprinting defenses are in the form of the CS-BuFLO algorithm
in CTST (Client total, Server total) mode, without the application
level hinting based optimizations to reduce bandwidth consumption (See:
http://www3.cs.stonybrook.edu/~rob/papers/csbuflo.pdf).  As a minor
implementation refinement, "basket" uses the kernel information as
described in the KIST paper to be more responsive to changing network
conditions.  Most of the CS-BuFLO parameters were adjusted in an
attempt to compensate for the lack of said application level hinting,
but "basket"'s CS-BuFLO implementation is still a lot more expensive
than the one presented in the paper.

The code: http://github.com/yawning/basket

 * The PQ crypto primitives used are ports to Go by yours truly based
   on the reference implementations.  It is both possible and likely
   that I messed something up, so users should decide between trusting
   my implementations and using a handshake based on classical
 * The "basket" handshake consumes a non-trivial amount of CPU on the
   server side due to the SPHINCS256 implementation being relatively
 * CS-BuFLO is EXTREMELY BANDWIDTH INTENSIVE, and if adversaries can
   observe the Bridge's upstream, it likely can be broken, especially
   if the Bridge is only servicing a handful of users.  Running the
   defense end-to-end (or even to the middle relay) is *extremely*
   non-trivial, though that would be required if something more
   comprehensive is desired.
 * The KIST code is platform specific, and I only wrote the Linux
   version.  If this ends up being useful to people, support for other
   platforms is possible.
 * "basket" was never written to be a general use transport, though it
   sits somewhere between obfsproxy-wfpadtools (a pure research
   framework) and obfs4proxy (something that is intended to be
   used in production) in terms of completeness.

Thanks to Marc Juarez (KU Leuven) and Mike Perry for inspiration to
write the CS-BuFLO component of "basket".

Questions, comments, feedback appreciated as always,

Yawning Angel

ps: Seriously, unless you are a developer or researcher, you REALLY
SHOULD NOT use "basket".
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20141216/81d15e4a/attachment.sig>

More information about the tor-dev mailing list