Some draft notes on migrating Tor's ciphersuites

[Weidong Shao]

Is there any writeup on the current status of Tor crypto?  doc or issue
list.

Thanks,
Weidong

On Tue, Dec 14, 2010 at 8:31 PM, Nick Mathewson <nickm at torproject.org>wrote:

> Here's something I've worked up, with fixes from Robert Ransom.  It's
> currently in doc/spec/proposals/ideas/xxx-crypto-migration.txt.  Once
> it's more discussed and worked out, it should turn into a real
> proposal, but I'd like to kick the ball off here.
>
> Robert has also written up a couple of documents I'll be forwarding in
> my next email.
>
> =====
> Title: Initial thoughts on migrating Tor to new cryptography
> Author: Nick Mathewson
> Created: 12 December 2010
>
> 1. Introduction
>
>  Tor currently uses AES-128, RSA-1024, and SHA1.  Even though these
>  ciphers were a decent choice back in 2003, and even though attacking
>  these algorithms is by no means the best way for a well-funded
>  adversary to attack users (correlation attacks are still cheaper, even
>  with pessimistic assumptions about the security of each cipher), we
>  will want to move to better algorithms in the future.  Indeed, if
>  migrating to a new ciphersuite were simple, we would probably have
>  already moved to RSA-1024/AES-128/SHA256 or something like that.
>
>  So it's a good idea to start figuring out how we can move to better
>  ciphers.  Unfortunately, this is a bit nontrivial, so before we start
>  doing the design work here, we should start by examining the issues
>  involved.  Robert Ransom and I both decided to spend this weekend
>  writing up documents of this type so that we can see how much two
>  people working independently agree on.  I know more Tor than Robert;
>  Robert knows far more cryptography than I do.  With luck we'll
>  complement each other's work nicely.
>
>  A note on scope: This document WILL NOT attempt to pick a new cipher
>  or set of ciphers.  Instead, it's about how to migrate to new ciphers
>  in general.  Any algorithms mentioned other than those we use today
>  are just for illustration.
>
>  Also, I don't much consider the importance of updating each particular
>  usage; only the methods that you'd use to do it.
>
>  Also, this isn't a complete proposal.
>
> 2. General principles and tricks
>
>  Before I get started, let's talk about some general design issues.
>
> 2.1. Many algorithms or few?
>
>  Protocols like TLS and OpenPGP allow a wide choice of cryptographic
>  algorithms; so long as the sender and receiver (or the responder and
>  initiator) have at least one mutually acceptable algorithm, they can
>  converge upon it and send each other messages.
>
>  This isn't the best choice for anonymity designs.  If two clients
>  support a different set of algorithms, then an attacker can tell them
>  apart.  A protocol with N ciphersuites would in principle split
>  clients into 2**N-1 sets.  (In practice, nearly all users will use the
>  default, and most users who choose _not_ to use the default will do so
>  without considering the loss of anonymity.  See "Anonymity Loves
>  Company: Usability and the Network Effect".)
>
>  On the other hand, building only one ciphersuite into Tor has a flaw
>  of its own: it has proven difficult to migrate to another one.  So
>  perhaps instead of specifying only a single new ciphersuite, we should
>  specify more than one, with plans to switch over (based on a flag in
>  the consensus or some other secure signal) once the first choice of
>  algorithms start looking iffy.  This switch-based approach would seem
>  especially easy for parameterizable stuff like key sizes.
>
> 2.2. Waiting for old clients and servers to upgrade
>
>  The easiest way to implement a shift in algorithms would be to declare
>  a "flag day": once we have the new versions of the protocols
>  implemented, pick a day by which everybody must upgrade to the new
>  software.  Before this day, the software would have the old behavior;
>  after this way, it would use the improved behavior.
>
>  Tor tries to avoid flag days whenever possible; they have well-known
>  issues.  First, since a number of our users don't automatically
>  update, it can take a while for people to upgrade to new versions of
>  our software.  Second and more worryingly, it's hard to get adequate
>  testing for new behavior that is off-by-default.  Flag days in other
>  systems have been known to leave whole networks more or less
>  inoperable for months; we should not trust in our skill to avoid
>  similar problems.
>
>  So if we're avoiding flag days, what can we do?
>
>  * We can add _support_ for new behavior early, and have clients use it
>    where it's available.  (Clients know the advertised versions of the
>    Tor servers they use-- but see 2.3 below for a danger here, and 2.4
>    for a bigger danger.)
>
>  * We can remove misfeatures that _prevent_ deployment of new
>    behavior.  For instance, if a certain key length has an arbitrary
>    1024-bit limit, we can remove that arbitrary limitation.
>
>  * Once an optional new behavior is ubiquitous enough, the authorities
>    can stop accepting descriptors from servers that do not have it
>    until they upgrade.
>
>  It is far easier to remove arbitrary limitations than to make other
>  changes; such changes are generally safe to back-port to older stable
>  release series.  But in general, it's much better to avoid any plans
>  that require waiting for any version of Tor to no longer be in common
>  use: a stable release can take on the order of 2.5 years to start
>  dropping off the radar.  Thandy might fix that, but even if a perfect
>  Thandy release comes out tomorrow, we'll still have lots of older
>  clients and relays not using it.
>
>  We'll have to approach the migration problem on a case-by-case basis
>  as we consider the algorithms used by Tor and how to change them.
>
> 2.3. Early adopters and other partitioning dangers
>
>  It's pretty much unavoidable that clients running software that speak
>  the new version of any protocol will be distinguishable from those
>  that cannot speak the new version.  This is inevitable, though we
>  could try to minimize the number of such partitioning sets by having
>  features turned on in the same release rather than one-at-a-time.
>
>  Another option here is to have new protocols controlled by a
>  configuration tri-state with values "on", "off", and "auto".  The
>  "auto" value means to look at the consensus to decide wither to use
>  the feature; the other two values are self-explanatory.  We'd ship
>  clients with the feature set to "auto" by default, with people only
>  using "on" for testing.
>
>  If we're worried about early client-side implementations of a protocol
>  turning out to be broken, we can have the consensus value say _which_
>  versions should turn on the protocol.
>
> 2.4. Avoid whole-circuit switches
>
>  One risky kind of protocol migration is a feature that gets used only
>  when all the routers in a circuit support it.  If such a feature is
>  implemented by few relays, then each relay learns a lot about the rest
>  of the path by seeing it used.  On the other hand, if the feature is
>  implemented by most relays, then a relay learns a lot about the rest of
>  the path when the feature is *not* used.
>
>  It's okay to have a feature that can be only used if two consecutive
>  routers in the patch support it: each router knows the ones adjacent
>  to it, after all, so knowing what version of Tor they're running is no
>  big deal.
>
> 2.5. The Second System Effect rears its ugly head
>
>  Any attempt at improving Tor's crypto is likely to involve changes
>  throughout the Tor protocol.  We should be aware of the risks of
>  falling into what Fred Brooks called the "Second System Effect": when
>  redesigning a fielded system, it's always tempting to try to shovel in
>  every possible change that one ever wanted to make to it.
>
>  This is a fine time to make parts of our protocol that weren't
>  previously versionable into ones that are easier to upgrade in the
>  future.  This probably _isn't_ time to redesign every aspect of the
>  Tor protocol that anybody finds problematic.
>
> 2.6. Low-hanging fruit and well-lit areas
>
>  Not all parts of Tor are tightly covered.  If it's possible to upgrade
>  different parts of the system at different rates from one another, we
>  should consider doing the stuff we can do easier, earlier.
>
>  But remember the story of the policeman who finds a drunk under a
>  streetlamp, staring at the ground?  The cop asks, "What are you
>  doing?"  The drunk says, "I'm looking for my keys!"  "Oh, did you drop
>  them around here?" says the policeman.  "No," says the drunk, "But the
>  light is so much better here!"
>
>  Or less proverbially: Simply because a change is easiest, does not
>  mean it is the best use of our time.  We should avoid getting bogged
>  down solving the _easy_ aspects of our system unless they happen also
>  to be _important_.
>
> 2.7. Nice safe boring codes
>
>  Let's avoid, to the extent that we can:
>    - being the primary user of any cryptographic construction or
>      protocol.
>    - anything that hasn't gotten much attention in the literature.
>    - anything we would have to implement from scratch
>    - anything without a nice BSD-licensed C implementation
>
>  Sometimes we'll have the choice of a more efficient algorithm or a
>  more boring & well-analyzed one.  We should not even consider trading
>  conservative design for efficiency unless we are firmly in the
>  critical path.
>
> 2.8. Key restrictions
>
>  Our spec says that RSA exponents should be 65537, but our code never
>  checks for that.  If we want to bolster resistance against collision
>  attacks, we could check this requirement.  To the best of my
>  knowledge, nothing violates it except for tools like "shallot" that
>  generate cute memorable .onion names.  If we want to be nice to
>  shallot users, we could check the requirement for everything *except*
>  hidden service identity keys.
>
> 3. Aspects of Tor's cryptography, and thoughts on how to upgrade them all
>
> 3.1. Link cryptography
>
>  Tor uses TLS for its link cryptography; it is easy to add more
>  ciphersuites to the acceptable list, or increase the length of
>  link-crypto public keys, or increase the length of the DH parameter,
>  or sign the X509 certificates with any digest algorithm that OpenSSL
>  clients will support.  Current Tor versions do not check any of these
>  against expected values.
>
>  The identity key used to sign the second certificate in the current
>  handshake protocol, however, is harder to change, since it needs to
>  match up with what we see in the router descriptor for the router
>  we're connecting to.  See notes on router identity below.  So long as
>  the certificate chain is ultimately authenticated by a RSA-1024 key,
>  it's not clear whether making the link RSA key longer on its own
>  really improves matters or not.
>
>  Recall also that for anti-fingerprinting reasons, we're thinking of
>  revising the protocol handshake sometime in the 0.2.3.x timeframe.
>  If we do that, that might be a good time to make sure that we aren't
>  limited by the old identity key size.
>
> 3.2. Circuit-extend crypto
>
>  Currently, our code requires RSA onion keys to be 1024 bits long.
>  Additionally, current nodes will not deliver an EXTEND cell unless it
>  is the right length.
>
>  For this, we might add a second, longer onion-key to router
>  descriptors, and a second CREATE2 cell to open new circuits
>  using this key type.  It should contain not only the onionskin, but
>  also information on onionskin version and ciphersuite.  Onionskins
>  generated for CREATE2 cells should use a larger DH group as well, and
>  keys should be derived from DH results using a better digest algorithm.
>
>  We should remove the length limit on EXTEND cells, backported to all
>  supported stable versions; call these "EXTEND2" cells.  Call these
>  "lightly patched".  Clients could use the new EXTEND2/CREATE2 format
>  whenever using a lightly patched or new server to extend to a new
>  server, and the old EXTEND/CREATE format otherwise.
>
>  The new onion skin format should try to avoid the design oddities of
>  our old one.  Instead of its current iffy hybrid encryption scheme, it
>  should probably do something more like a BEAR/LIONESS operation with a
>  fixed key on the g^x value, followed by a public key encryption on the
>  start of the encrypted data.  (Robert reminded me about this
>  construction.)
>
>  The current EXTEND cell format ends with a router identity
>  fingerprint, which is used by the extended-from router to authenticate
>  the extended-to router when it connects.  Changes to this will
>  interact with changes to how long an identity key can be and to the
>  link protocol; see notes on the link protocol above and about router
>  identity below.
>
> 3.2.1. Circuit-extend crypto: fast case
>
>  When we do unauthenticated circuit extends with CREATE/CREATED_FAST,
>  the two input values are combined with SHA1.  I believe that's okay;
>  using any entropy here at all is overkill.
>
> 3.3. Relay crypto
>
>  Upon receiving relay cells, a router transforms the payload portion of
>  the cell with the appropriate key appropriate key, sees if it
>  recognizes the cell (the recognized field is zero, the digest field is
>  correct, the cell is outbound), and passes them on if not.  It is
>  possible for each hop in the circuit to handle the relay crypto
>  differently; nobody but the client and the hop in question need to
>  coordinate their operations.
>
>  It's not clear, though, whether updating the relay crypto algorithms
>  would help anything, unless we changed the whole relay cell processing
>  format too.  The stream cipher is good enough, and the use of 4 bytes
>  of digest does not have enough bits to provide cryptographic strength,
>  no matter what cipher we use.
>
>  This is the likeliest area for the second-system effect to strike;
>  there are lots of opportunities to try to be more clever than we are
>  now.
>
> 3.4. Router identity
>
>  This is one of the hardest things to change.  Right now, routers are
>  identified by a "fingerprint" equal to the SHA1 hash of their 1024-bit
>  identity key as given in their router descriptor.  No existing Tor
>  will accept any other size of identity key, or any other hash
>  algorithm.  The identity key itself is used:
>    - To sign the router descriptors
>    - To sign link-key certificates
>    - To determine the least significant bits of circuit IDs used on a
>      Tor instance's links (see tor-spec §5.1)
>
>  The fingerprint is used:
>    - To identify a router identity key in EXTEND cells
>    - To identify a router identity key in bridge lines
>    - Throughout the controller interface
>    - To fetch bridge descriptors for a bridge
>    - To identify a particular router throughout the codebase
>    - In the .exit notation.
>    - By the controller to identify nodes
>    - To identify servers in the logs
>    - Probably other places too
>
>  To begin to allow other key types, key lengths, and hash functions, we
>  would either need to wait till all current Tors are obsolete, or allow
>  routers to have more than one identity for a while.
>
>  To allow routers to have more than one identity, we need to
>  cross-certify identity keys.  We can do this trivially, in theory, by
>  listing both keys in the router descriptor and having both identities
>  sign the descriptor.  In practice, we will need to analyze this pretty
>  carefully to avoid attacks where one key is completely fake aimed to
>  trick old clients somehow.
>
>  Upgrading the hash algorithm once would be easy: just say that all
>  new-type keys get hashed using the new hash algorithm.  Remaining
>  future-proof could be tricky.
>
>  This is one of the hardest areas to update; "SHA1 of identity key" is
>  assumed in so many places throughout Tor that we'll probably need a
>  lot of design work to work with something else.
>
> 3.5. Directory objects
>
>  Fortunately, the problem is not so bad for consensuses themselves,
>  because:
>    - Authority identity keys are allowed to be RSA keys of any length;
>      in practice I think they are all 3072 bits.
>    - Authority signing keys are also allowed to be of any length.
>      AFAIK the code works with longer signing keys just fine.
>    - Currently, votes are hashed with both sha1 and sha256; adding
>      more hash algorithms isn't so hard.
>    - Microdescriptor consensuses are all signed using sha256.  While
>      regular consensuses are signed using sha1, exploitable collisions
>      are hard to come up with, since once you had a collision, you
>      would need to get a majority of other authorities to agree to
>      generate it.
>
>  Router descriptors are currently identified by SHA1 digests of their
>  identity keys and descriptor digests in regular consensuses, and by
>  SHA1 digests of identity keys and SHA256 digests of microdescriptors
>  in microdesc consensuses.  The consensus-flavors design allows us to
>  generate new flavors of consensus that identity routers by new hashes
>  of their identity keys.  Alternatively, existing consensuses could be
>  expanded to contain more hashes, though that would have some space
>  concerns.
>
>  Router descriptors themselves are signed using RSA-1024 identity keys
>  and SHA1.  For information on updating identity keys, see above.
>
>  Router descriptors and extra-info documents cross-certify one another
>  using SHA1.
>
>  Microdescriptors are currently specified to contain exactly one
>  onion key, of length 1024 bits.
>
> 3.6. The directory protocol
>
>  Most objects are indexed by SHA1 hash of an identity key or a
>  descriptor object.  Adding more hash types wouldn't be a huge problem
>  at the directory cache level.
>
> 3.7. The hidden service protocol
>
>  Hidden services self-identify by a 1024-bit RSA key.  Other key
>  lengths are not supported.  This key is turned into an 80 bit half
>  SHA-1 hash for hidden service names.
>
>  The most simple change here would be to set an interface for putting
>  the whole ugly SHA1 hash in the hidden service name.  Remember that
>  this needs to coexist with the authentication system which also uses
>  .onion hostnames; that hostnames top out around 255 characters and and
>  their components top out at 63.
>
>  Currently, ESTABLISH_INTRO cells take a key length parameter, so in
>  theory they allow longer keys.  The rest of the protocol assumes that
>  this will be hashed into a 20-byte SHA1 identifier.  Changing that
>  would require changes at the introduction point as well as the hidden
>  service.
>
>  The parsing code for hidden service descriptors currently enforce a
>  1024-bit identity key, though this does not seem to be described in
>  the specification.  Changing that would be at least as hard as doing
>  it for regular identity keys.
>
>  Fortunately, hidden services are nearly completely orthogonal to
>  everything else.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20101217/a7d75e6d/attachment.htm>