Re-flow new-crypto-sketch to a 72 columns, add a TODO

1 files changed, 326 insertions, 291 deletions

diff --git a/proposals/ideas/xxx-new-crypto-sketch.txt b/proposals/ideas/xxx-new-crypto-sketch.txt
index a4893e1..504e658 100644
--- a/proposals/ideas/xxx-new-crypto-sketch.txt
+++ b/proposals/ideas/xxx-new-crypto-sketch.txt
@@ -2,6 +2,18 @@ Title: Design sketch for new crypto ops
 Date: 19 Oct 2011
 Author: Nick Mathewson
 
+TODO:
+   - Write missing sections
+   - Fix XXXXs
+   - Write performance notes
+   - Find rransom's extend proposal
+   - Proofread
+   - Change relay-cipher section:
+     - Pad with zeros.
+     - Encrypt-then-mac.
+     - Revise analysis.
+   - Try to be a little less monlogue-ish, a little more
+
 0. Overview
 
   The point of this document is to discuss what crypto we ought to be using.
@@ -26,96 +38,100 @@ Author: Nick Mathewson
 
 1. Base algorithm choice
 
-  There seem to be two main candidate algorithms for signatures: RSA with big
-  keys (hereinafter "RSA>1024"); and Ed25519, which is DSA with the sharp
-  edges filed off on an Edwards curve related to DJB's Curve25519.  We can
-  look at other ECC groups too.  {But see ECC Notes.}
-
-  For Diffie Hellman: Curve25519 seems like a decent choice; failing that,
-  another .  DH
-  on Z_p with big groups (hereinafter "DH>1024").  {But see ECC notes.}
-
-  For a hash function: SHA256, switching to SHA3 in 2012 when it comes out.
-  It might be worthwhile waiting for SHA3 in most places, and skipping over
-  the sha256 stage entirely.
-
-  For a stream cipher: AES-CTR is in one sense a conservative choice inasmuch
-  as AES is well-analyzed, but AES's well-known issues with cache-based
-  timing attacks are pretty worrisome.  We can mitigate that some by using
-  random secret IVs for AES-CTR, so that we will be encrypting neither
-  attacker-chosen nor attacker-known plaintext with out AES cipher, but
-  that's a bit kludgy.  Salsa20 is what rransom likes these days, but IMO we
-  aren't competent to tell whether it looks good or not; the existing attacks
-  against it don't look like very bad news to me, but who knows whether it's
-  getting enough attention that we can read.  See also ChaCha; see also the
-  other EuroCrypt {XXXX} winners/finalists; see also SHA3 if the SHA3 winner
-  specifies a way to use it as a stream cipher, or specifies an underlying
-  stream/block cipher.
+  There seem to be two main candidate algorithms for signatures: RSA
+  with big keys (hereinafter "RSA>1024"); and Ed25519, which is DSA with
+  the sharp edges filed off on an Edwards curve related to DJB's
+  Curve25519.  We can look at other ECC groups too.  {But see ECC
+  Notes.}
+
+  For Diffie Hellman: Curve25519 seems like a decent choice; failing
+  that, another XXXX.  DH on Z_p with big groups (hereinafter "DH>1024").
+  {But see ECC notes.}
+
+  For a hash function: SHA256, switching to SHA3 in 2012 when it comes
+  out.  It might be worthwhile waiting for SHA3 in most places, and
+  skipping over the sha256 stage entirely.
+
+  For a stream cipher: AES-CTR is in one sense a conservative choice
+  inasmuch as AES is well-analyzed, but AES's well-known issues with
+  cache-based timing attacks are pretty worrisome.  We can mitigate that
+  some by using random secret IVs for AES-CTR, so that we will be
+  encrypting neither attacker-chosen nor attacker-known plaintext with
+  out AES cipher, but that's a bit kludgy.  Salsa20 is what rransom
+  likes these days, but IMO we aren't competent to tell whether it looks
+  good or not; the existing attacks against it don't look like very bad
+  news to me, but who knows whether it's getting enough attention that
+  we can read.  See also ChaCha; see also the other EuroCrypt {XXXX}
+  winners/finalists; see also SHA3 if the SHA3 winner specifies a way to
+  use it as a stream cipher, or specifies an underlying stream/block
+  cipher.
 
   For a random number generator: We currently use OpenSSL seeded with
-  RAND_poll and with platform entropy.  OpenSSL uses RC4 (XXX check).  The
-  platform entropy management can be messy, obscure, or both.  I suggest
-  that:
-    * we should seed our PRNG with more entropy sources if we can find some
-      promising code with an appropriate license
+  RAND_poll and with platform entropy.  OpenSSL uses RC4 (XXX check).
+  The platform entropy management can be messy, obscure, or both.  I
+  suggest that:
+
+    * we should seed our PRNG with more entropy sources if we can find
+      some promising code with an appropriate license
     * instead of just using OpenSSL's PRNG, we should use OpenSSL's PRNG
-      xor'd with some other good PRNG.  (Is Yarrow still cool?  And is there
-      a combine operation better than xor?)
-    * We should re-seed the RNG before and after very sensitive operations,
-      like private key generation.
+      xor'd with some other good PRNG.  (Is Yarrow still cool?  And is
+      there a combine operation better than xor?)
+    * We should re-seed the RNG before and after very sensitive
+      operations, like private key generation.
 
 
 1.1. ECC notes
 
-  ECC is the brave new[*] crypto of the future!  It's faster[**] than doing
-  crypto in Z_n (as we do for RSA and DH now) for equivalent levels of
-  security, and the resulting outputs are much shorter.
-
-  As near as I can tell as a layman, Certicom is muddying the waters as much
-  as possible wrt claiming that it's nigh impractical to deploy ECC without
-  licensing their patents.  This is rather like the silliness that PKP used
-  to pull back in the day, where they claimed that their patents covered not
-  only the existing public key cryptography algorithms, but also the very
-  idea of public key cryptography itself.
-
-  DJB claims that for every patent he's aware of, either that patent doesn't
-  cover his code, or that patent is invalid because of prior art.  I'm not
-  going to try to evaluate these claims, since I'm not supposed to be reading
-  patents for typical "let's avoid the appearance of knowing infringement"
-  reasons.  But before we dive into the world of ECC, we should see if we can
-  ask any friendly patent attorneys and ECC experts for a second or third
-  opinion here.
-
-  I note in passing that nearly all of the patents that DJB mentions in his
-  list would appear to expire over the next 12 months or so.
-
-  Additionally, there are ECC groups out there less fast than DJB's, but more
-  widely available and analyzed.  We should consider some of those too.
-
-  One final issue to investigate is whether using these algorithms will make
-  any major free software distribution decide not to include us.  I seem to
-  recall seeing that one or two of the big ones had at one point decided to
-  ship OpenSSL only with ECC disabled, either because of real patent
-  concerns, or because of an opinion that the certicom license for ECC use in
-  TLS was problematic for free software, or something like that.  We should
-  check that out.
-
-  [*] Actually, it's older than onion routing, and older than some members of
-  the Tor project.
-
-  [**] Actually, because of the common practice of choosing a small-ish prime
-  value (65537) for e in RSA, RSA public key operations can be a little
-  faster than equivalent-security ECDH or ECDSA operations.  The private key
-  operations in RSA are still much much slower.
+  ECC is the brave new[*] crypto of the future!  It's faster[**] than
+  doing crypto in Z_n (as we do for RSA and DH now) for equivalent
+  levels of security, and the resulting outputs are much shorter.
+
+  As near as I can tell as a layman, Certicom is muddying the waters as
+  much as possible wrt claiming that it's nigh impractical to deploy ECC
+  without licensing their patents.  This is rather like the silliness
+  that PKP used to pull back in the day, where they claimed that their
+  patents covered not only the existing public key cryptography
+  algorithms, but also the very idea of public key cryptography itself.
+
+  DJB claims that for every patent he's aware of, either that patent
+  doesn't cover his code, or that patent is invalid because of prior
+  art.  I'm not going to try to evaluate these claims, since I'm not
+  supposed to be reading patents for typical "let's avoid the appearance
+  of knowing infringement" reasons.  But before we dive into the world
+  of ECC, we should see if we can ask any friendly patent attorneys and
+  ECC experts for a second or third opinion here.
+
+  I note in passing that nearly all of the patents that DJB mentions in
+  his list would appear to expire over the next 12 months or so.
+
+  Additionally, there are ECC groups out there less fast than DJB's, but
+  more widely available and analyzed.  We should consider some of those
+  too.
+
+  One final issue to investigate is whether using these algorithms will
+  make any major free software distribution decide not to include us.  I
+  seem to recall seeing that one or two of the big ones had at one point
+  decided to ship OpenSSL only with ECC disabled, either because of real
+  patent concerns, or because of an opinion that the certicom license
+  for ECC use in TLS was problematic for free software, or something
+  like that.  We should check that out.
+
+  [*] Actually, it's older than onion routing, and older than some
+  members of the Tor project.
+
+  [**] Actually, because of the common practice of choosing a small-ish
+  prime value (65537) for e in RSA, RSA public key operations can be a
+  little faster than equivalent-security ECDH or ECDSA operations.  The
+  private key operations in RSA are still much much slower.
 
 2. New identities
 
   Identity keys and their fingerprints are used:
-    - To sign router descriptors
+    - To sign router descriptors.
     - To identify nodes in consensus directories
     - To make sure we're talking to the right node in the link handshake
-    - To make sure that the extending node is talking to the right next node
-      when sending an extend cell
+    - To make sure that the extending node is talking to the right next
+      node when sending an extend cell
     - To identify particular nodes in the hidden service subsystem
     - To identify nodes in the UI in various places
     - Internally, to identify a node uniquely in the codebase.
@@ -124,35 +140,36 @@ Author: Nick Mathewson
 
 2.1. New identities, option 1: RSA>1024, slow migration.
 
-  We use RSA for identity keys indefinitely.  Nearly all operations done with
-  an identity key are signature checking; signing happens only a few times an
-  hour per node even with pathological cases.  Since signature checking is
-  really cheap with RSA, there's no speed advantage for ECC here.  (There is
-  a space advantage, since the keys are much smaller.)
-
-  The easiest way to migrate to longer identity keys is to tell all Tors to
-  begin accepting longer identity keys now, and to tweak all our protocols so
-  that longer RSA identity keys are understood.  We should then have a pair
-  of parameters in the consensus that determines the largest and smallest
-  acceptable identity key size in the network.  Clients and servers should
-  reject any keys longer or shorter than specified.  Once all versions of Tor
-  can accept long identity keys, we raise the maximum size from 1024 to
-  somewhere in the 2048-4096 range.
+  We use RSA for identity keys indefinitely.  Nearly all operations done
+  with an identity key are signature checking; signing happens only a
+  few times an hour per node even with pathological cases.  Since
+  signature checking is really cheap with RSA, there's no speed
+  advantage for ECC here.  (There is a space advantage, since the keys
+  are much smaller.)
+
+  The easiest way to migrate to longer identity keys is to tell all Tors
+  to begin accepting longer identity keys now, and to tweak all our
+  protocols so that longer RSA identity keys are understood.  We should
+  then have a pair of parameters in the consensus that determines the
+  largest and smallest acceptable identity key size in the network.
+  Clients and servers should reject any keys longer or shorter than
+  specified.  Once all versions of Tor can accept long identity keys, we
+  raise the maximum size from 1024 to somewhere in the 2048-4096 range.
 
 2.2. New identities option 2: RSA>1024, faster migration.
 
-  We use RSA for identity keys indefinitely as above.  But we allow nodes to
-  begin having longer identities now, even though older Tors won't understand
-  them.  This implies, of course, that every such node needs to have at least
-  2 identities: one RSA1024 identity for backward compatibility, one RSA>1024
-  identity for more secure identification.
+  We use RSA for identity keys indefinitely as above.  But we allow
+  nodes to begin having longer identities now, even though older Tors
+  won't understand them.  This implies, of course, that every such node
+  needs to have at least 2 identities: one RSA1024 identity for backward
+  compatibility, one RSA>1024 identity for more secure identification.
 
-  We would have these identities cross-certify as follows: All keys would be
-  listed in the router descriptor.  RSA>1024 keys would be called something
-  other than identity-key, so as not to confuse older clients.  A signature
-  with the RSA>1024 key would appear right before the current RSA1024
-  signature.  This way, signed material would include both keys, and would be
-  signed by both keys.
+  We would have these identities cross-certify as follows: All keys
+  would be listed in the router descriptor.  RSA>1024 keys would be
+  called something other than identity-key, so as not to confuse older
+  clients.  A signature with the RSA>1024 key would appear right before
+  the current RSA1024 signature.  This way, signed material would
+  include both keys, and would be signed by both keys.
 
      [In other words, descriptors would look something like:
 
@@ -169,11 +186,13 @@ Author: Nick Mathewson
       ...
       ext-signature
       -----BEGIN SIGNATURE-----
-      signature of everything through "ext-signature\n", using the long key
+      signature of everything through "ext-signature\n",
+      using the long key
       -----END SIGNATURE-----
       router-signature
       -----BEGIN SIGNATURE-----
-      signature of everything through "router-signature\n", using the short key
+      signature of everything through "router-signature\n",
+      using the short key
       -----END SIGNATURE-----
 
      ]
@@ -181,15 +200,15 @@ Author: Nick Mathewson
   See "UI notes" in the "new fingerprints" section below for some of the
   implications of letting nodes have multiple identity keys.
 
-  We'll need to advertise these new identities in consensus directories too;
-  see XXXX below for more info there.
+  We'll need to advertise these new identities in consensus directories
+  too; see XXXX below for more info there.
 
 2.3. New identities option 3: RSA>1024 and/or Ed25519, faster migration
 
-  As in option 2 above, but new keys can also be Ed25519.  If we expect that
-  not all installations will allow Ed25519 (see "ECC Notes", section 1.1),
-  we'll need to say that every server with an Ed25519 key must also have an
-  RSA>1024 key.
+  As in option 2 above, but new keys can also be Ed25519.  If we expect
+  that not all installations will allow Ed25519 (see "ECC Notes",
+  section 1.1), we'll need to say that every server with an Ed25519 key
+  must also have an RSA>1024 key.
 
 2.4. Implications for current use of identity keys
 
@@ -204,27 +223,29 @@ Author: Nick Mathewson
 
   The current v3 link handshake can handle presenting multiple identity
   certificates in the CERT cell.  We should consider ourselves to be
-  connected to a node with identity X if _any_ of the identity certificates
-  that it presents in its authenticated CERT cell has identity X.  To handle
-  EXTEND cells correctly, we should verify every identity we can.
+  connected to a node with identity X if _any_ of the identity
+  certificates that it presents in its authenticated CERT cell has
+  identity X.  To handle EXTEND cells correctly, we should verify every
+  identity we can.
 
     - To make sure that the extending node is talking to the right next node
       when sending an extend cell
 
-  The new extend cell format needs to allow the client to tell the extending
-  node about some identity for the destination node that the extending node
-  will be able to understand.  This is a capability of the extending node
-  that the client needs to be able to check. (Also, the extend cell needs to
-  hash that identity in a form the extending node can understand; but that's
-  a fingerprint issue.)
+  The new extend cell format needs to allow the client to tell the
+  extending node about some identity for the destination node that the
+  extending node will be able to understand.  This is a capability of
+  the extending node that the client needs to be able to check. (Also,
+  the extend cell needs to hash that identity in a form the extending
+  node can understand; but that's a fingerprint issue.)
 
     - To determine which part of the circuit ID space to use on a Tor
       instance's links.
 
-  We can continue to use RSA1024 identity key comparison here by default.  We
-  can also use some other parameter of the v3 handshake, or introduce a new
-  link protocol where if the initiator authenticates, the initiator always
-  gets the low circIDs and the responder always gets the high ones.
+  We can continue to use RSA1024 identity key comparison here by
+  default.  We can also use some other parameter of the v3 handshake, or
+  introduce a new link protocol where if the initiator authenticates,
+  the initiator always gets the low circIDs and the responder always
+  gets the high ones.
 
     - To identity nodes in consensus directories
     - To identify nodes in the UI in various places
@@ -239,20 +260,20 @@ Author: Nick Mathewson
 2.5. Migrating away from short ID keys entirely
 
   Eventually no version of Tor that requires 1024-bit identity keys will
-  remain.  When that happens, we should stop using them entirely.  That means
-  that if we take any path other than the "slow migration" path of 2.1, we'll
-  need to make everything that looks at a node's identity also accept nodes
-  with _only_ a RSA>1024/Ed25519 identity.
+  remain.  When that happens, we should stop using them entirely.  That
+  means that if we take any path other than the "slow migration" path of
+  2.1, we'll need to make everything that looks at a node's identity
+  also accept nodes with _only_ a RSA>1024/Ed25519 identity.
 
-  At the directory service level, we should have an option to allow nodes
-  without RSA1024 identity keys (off until all clients and nodes accept new
-  identity keys).
+  At the directory service level, we should have an option to allow
+  nodes without RSA1024 identity keys (off until all clients and nodes
+  accept new identity keys).
 
 2.6. Implications for directory information
 
-  Clients must know a hash for each node's identity key, or else they can't
-  make an authenticated connection to the node or tell ORs how to extend to
-  the node.
+  Clients must know a hash for each node's identity key, or else they
+  can't make an authenticated connection to the node or tell ORs how to
+  extend to the node.
 
 
 3. New fingerprints
@@ -261,43 +282,46 @@ Author: Nick Mathewson
   encoding of the RSA1024 identity key.  We encode this in hex almost
   everywhere, and prefix it with a $.
 
-  I propose that fingerprints of the future be determined by taking a digest
-  using SHA256 or SHA3 of:
+  I propose that fingerprints of the future be determined by taking a
+  digest using SHA256 or SHA3 of:
 
       "Hash Algorithm Name", "Key Type Name", encoded key
 
-  When representing these internally, we should include the hash algorithm
-  that was used.  When representing them in the UI, we should use the
-  notation %b64, where b64 is a base-64 encoding, omitting the trailing =s.
+  When representing these internally, we should include the hash
+  algorithm that was used.  When representing them in the UI, we should
+  use the notation %b64, where b64 is a base-64 encoding, omitting the
+  trailing =s.
 
-  (Other plausible characters to use are @, ?, +, ~, =, etc.  I like %, but
-  can be persuaded.  Bikeshed bikeshed bikeshed.)
+  (Other plausible characters to use are @, ?, +, ~, =, etc.  I like %,
+  but can be persuaded.  Bikeshed bikeshed bikeshed.)
 
-  Since 43 base-64 characters is enough to represent a 256-bit digest, with 2
-  bits left over, I propose that the b64 value encode
+  Since 43 base-64 characters is enough to represent a 256-bit digest,
+  with 2 bits left over, I propose that the b64 value encode
       hh | D(hash algorithm name, key type, encoded key),
+
   where hh is a 2-bit value, with one of the values:
       00 -- sha256
       01 -- sha3
       10 -- to be determined
       11 -- reserved.
 
-  We should investigate in the interface whether it's plausible to allow a
-  prefix of a node ID where the full ID would otherwise be required.  That
-  seems risky for short prefixes, though.
+  We should investigate in the interface whether it's plausible to allow
+  a prefix of a node ID where the full ID would otherwise be required.
+  That seems risky for short prefixes, though.
 
 3.1. How many fingerprints is that anyway?!
 
-  Suppose that we allow sha256 and sha3 as hash algorithms, and we allow each
-  node to have 3 identity keys: one RSA1024, one RSA>1024, and one ECC.  Then
-  we would have 7 fingerprints (6 plus the legacy SHA1(RSA1024) fingerprint),
-  for a total of 20+6*32==212 bytes per node.
+  Suppose that we allow sha256 and sha3 as hash algorithms, and we allow
+  each node to have 3 identity keys: one RSA1024, one RSA>1024, and one
+  ECC.  Then we would have 7 fingerprints (6 plus the legacy
+  SHA1(RSA1024) fingerprint), for a total of 20+6*32==212 bytes per
+  node.
 
-  It's not a horrible problem to accept them all in the UI, but the UI isn't
-  the only place that needs to know fingerprints.  Instead, let's say that
-  RSA1024 identities are only identified with SHA1 hashes.  This limits our
-  fingerprint load to a more manageable 20+32*2 == 84 bytes per node.  Still
-  not great, though.
+  It's not a horrible problem to accept them all in the UI, but the UI
+  isn't the only place that needs to know fingerprints.  Instead, let's
+  say that RSA1024 identities are only identified with SHA1 hashes.
+  This limits our fingerprint load to a more manageable 20+32*2 == 84
+  bytes per node.  Still not great, though.
 
 3.2. What does this imply for the UI?
 
@@ -317,20 +341,21 @@ Author: Nick Mathewson
 4.2. More fingerprints
 
   Because extending from node A to node B requires that we have node B's
-  fingerprint in a way that node A will understand, it is not enough to get a
-  set of identity fingerprints for each node in the format _we_ like best.
-  Instead, we must .
+  fingerprint in a way that node A will understand, it is not enough to
+  get a set of identity fingerprints for each node in the format _we_
+  like best.  Instead, we must .
 
 
 4.x. An option: compound signatures on directory objects
 
-   In Tor 0.2.2.x and later, when we check a signature on a directory object
-   (not including hidden service descriptors), we only look at the first
-   DIGEST_LEN bytes of the RSA-signed data.  Once 0.2.1.x is obsolete, or on
-   any types of signatures not checked in 0.2.1.x, we can use the rest of the
-   space.  (We're using PKCS1 padding on our signatures, which has an
-   overhead of 11 bytes.  Signing a SHA1 hash with a 1024-bit key therefore
-   leaves 128-11-20==97 more bytes we could use for a SHA2 or a SHA3 hash.)
+   In Tor 0.2.2.x and later, when we check a signature on a directory
+   object (not including hidden service descriptors), we only look at
+   the first DIGEST_LEN bytes of the RSA-signed data.  Once 0.2.1.x is
+   obsolete, or on any types of signatures not checked in 0.2.1.x, we
+   can use the rest of the space.  (We're using PKCS1 padding on our
+   signatures, which has an overhead of 11 bytes.  Signing a SHA1 hash
+   with a 1024-bit key therefore leaves 128-11-20==97 more bytes we
+   could use for a SHA2 or a SHA3 hash.)
 
 4.x.
 
@@ -342,121 +367,127 @@ Author: Nick Mathewson
 
 6. Relay crypto changes
 
-There are a few things we might want out of improved relay crypto.  They
-include:
+  There are a few things we might want out of improved relay crypto.
+  They include:
    - Resistance to end-to-end bitwise tagging attacks.
    - Better resistance to malleability.
-   - If using counter mode, no block-cipher operations on any value known
-     to the attacker.
+   - If using counter mode, no block-cipher operations on any value
+     known to the attacker.
 
-I'll try to provide these in increasing order of difficulty.  None of these
-is necessarily correct; I should look for a security proof or a better
-construction for any that we seem likely to use.
+  I'll try to provide these in increasing order of difficulty.  None of
+  these is necessarily correct; I should look for a security proof or a
+  better construction for any that we seem likely to use.
 
-Rationales: Our existing malleability resistance is a kludge.  Doing no
-block-cipher ops on attacker-known values increases our security margins a
-little.  Our arguments about tagging attacks hold that an attacker who
-controls both ends has plenty of ways to win even if tagging attacks are
-foiled; nonetheless, most of these ways are technically slightly more
-difficult than xor-based tagging, and it could be useful to boost our
-defense-in-depth a little bit, just in case other active end-to-end attacks
-turn out to be harder than we'd though.)
+  Rationales: Our existing malleability resistance is a kludge.  Doing
+  no block-cipher ops on attacker-known values increases our security
+  margins a little.  Our arguments about tagging attacks hold that an
+  attacker who controls both ends has plenty of ways to win even if
+  tagging attacks are foiled; nonetheless, most of these ways are
+  technically slightly more difficult than xor-based tagging, and it
+  could be useful to boost our defense-in-depth a little bit, just in
+  case other active end-to-end attacks turn out to be harder than we'd
+  though.)
 
-Option 1: Use AES-CTR in a less scary mode
+6.1. Option 1: Use AES-CTR in a less scary mode
 
-   When doing key expansion, in addition to establishing Kf, Kb, Df, and Db,
-   also establish IVf and IVb.  Use the current relay crypto, except instead
-   of starting the counters at 0, start them at IVf and IVb.  This way, an
-   attacker doesn't have any known plaintexts to work with, which makes AES a
-   little more robust.
+  When doing key expansion, in addition to establishing Kf, Kb, Df, and
+   Db, also establish IVf and IVb.  Use the current relay crypto, except
+   instead of starting the counters at 0, start them at IVf and IVb.
+   This way, an attacker doesn't have any known plaintexts to work with,
+   which makes AES a little more robust.
 
-Option 2: As 1, but tagging attacks garble the circuit after one block.
+6.2. Option 2: As 1, but tagging attacks garble the circuit after one block.
 
    Keep an HMAC of all previously received encrypted cells on a circuit.
-   When decrypting a cell, use this HMAC value to determine the first 64 bits
-   of the counter; increment the low 64 bits of the counter as usual.
+   When decrypting a cell, use this HMAC value to determine the first 64
+   bits of the counter; increment the low 64 bits of the counter as
+   usual.
 
-   This way, if an adversary flips any bits before passing the stream through
-   an honest node, no _subsequent_ block will be recoverable.
+   This way, if an adversary flips any bits before passing the stream
+   through an honest node, no _subsequent_ block will be recoverable.
 
-   To prevent any part of the stream from being re-used, close any circuit if
-   the low 64 bits of the counter would ever wrap (that is, around 295
-   million terabytes).
+   To prevent any part of the stream from being re-used, close any
+   circuit if the low 64 bits of the counter would ever wrap (that is,
+   around 295 million terabytes).
 
-   (If we're using a stream cipher with fast re-key, then we can just have
-   the key used for each block be an HMAC of all previously received
-   ciphertext.)
+   (If we're using a stream cipher with fast re-key, then we can just
+   have the key used for each block be an HMAC of all previously
+   received ciphertext.)
 
 Option 3: As 1, but tagging attacks garble the circuit in the same block.
 
    Use a large-block cipher mode, such as BEAR or LIONESS (depending on
-   whether we need a PRP or SPRP).  Base the key material for each block on
-   an HMAC of all previous blocks' ciphertexts.
+   whether we need a PRP or SPRP).  Base the key material for each block
+   on an HMAC of all previous blocks' ciphertexts.
 
-   This way, if an adversary makes any alteration in a block, that block and
-   all subsequent blocks will be garbled.  It's more expensive than 2,
-   though, especially if we need to use a LIONESS construction.
+   This way, if an adversary makes any alteration in a block, that block
+   and all subsequent blocks will be garbled.  It's more expensive than
+   2, though, especially if we need to use a LIONESS construction.
 
-   {I considered IGE here, with a trick where odd-numbered nodes on a circuit
-   start from the front of the block and even-numbered nodes start from the
-   end, but it didn't seem much better.  We should investigate relative
-   performance, though.}
+   {I considered IGE here, with a trick where odd-numbered nodes on a
+   circuit start from the front of the block and even-numbered nodes
+   start from the end, but it didn't seem much better.  We should
+   investigate relative performance, though.}
 
 Option 4: Shall we have middle nodes be able to fast-stop bad data?
 
-   In all the above options, if a cell is altered, the middle node can at
-   best turn that cell and the rest of the cells on the circuit into garbage,
-   which the last node won't deliver (if honest) or can't deliver (if dishonest).
-
-   Might we prefer to do as in mixnets, and have nodes kill circuits upon
-   receiving altered cells?
-
-   I'm not so sure.  It's relatively expensive in per-cell overhead, and the
-   next-best attack to the one it prevents isn't so great.
-
-   Consider that if option 3 is in place, an end-to-end attacker who wants to
-   do a tagging attack at one node can garble the rest of the circuit, and
-   see if the output is garbled at the exit node.  But such an attacker could
-   just as easily close the circuit at one of those nodes and watch for a
-   corresponding close event, or even better -- simply pause traffic on that
-   circuit for a while and watch for a corresponding gap at the exit.  The
-   only advantage of the garbling attack would be that garbled cells are
-   presumably rarer than circuit closes or traffic pauses, and thus easier to
-   use to distinguish target circuits.  But that's still bunk; the other
-   attacks win fine, and the pause attack doesn't risk detection so much.
-
-   Still, to do this one, we'd want to have outgoing and incoming circuits
-   treated differently.  Incoming cells could work as in 1 or 2 or 3 above;
-   outgoing cells would want to have a header portion as in mixmaster, where
-   each node checks that the first N bits of the header match a MAC of all
-   data seen so far, *including the rest of the cell*.  They'd then decrypt
-   the rest of the cell, remove the first N bits of the header, and re-pad
-   the header with N bits at the end, taken from a PRNG whose seed is shared
-   with the client.  (This is basically how mixmaster works, and how
-   mixminion works in the common case.)
-
-   The space overhead here is kind of large: N bits per cell per node.  In
-   the most paranoid case, if we used 256-byte HMACs on 3-node paths, that's
-   96 bytes per cell, which is more than 20% of the total length.  But we can
-   probably do better if we let the CREATE operation also tell the node some
-   N to check.  For example, the first node doesn't need to check any bits.
-   The second and third nodes could check 64 bits apiece; that only has 16
-   bytes overhead, and high probability of catching any changes. (Birthday
-   attacks don't matter here, and an attacker who mounts this attack for long
-   enough to accidentally find a 64-bit mac will break so many circuits in
-   the process as to become totally unreliable.
-
-   But all of this leaks the path lengths and position on the path to various
-   nodes.  We might open ourselves up to partitioning attacks if different
-   clients choose different numbers of bits.  What's more, we might leak the
-   length of the path to the last node by how much junk there is at the end
-   of the cell.
+   In all the above options, if a cell is altered, the middle node can
+   at best turn that cell and the rest of the cells on the circuit into
+   garbage, which the last node won't deliver (if honest) or can't
+   deliver (if dishonest).
+
+   Might we prefer to do as in mixnets, and have nodes kill circuits
+   upon receiving altered cells?
+
+   I'm not so sure.  It's relatively expensive in per-cell overhead, and
+   the next-best attack to the one it prevents isn't so great.
+
+   Consider that if option 3 is in place, an end-to-end attacker who
+   wants to do a tagging attack at one node can garble the rest of the
+   circuit, and see if the output is garbled at the exit node.  But such
+   an attacker could just as easily close the circuit at one of those
+   nodes and watch for a corresponding close event, or even better --
+   simply pause traffic on that circuit for a while and watch for a
+   corresponding gap at the exit.  The only advantage of the garbling
+   attack would be that garbled cells are presumably rarer than circuit
+   closes or traffic pauses, and thus easier to use to distinguish
+   target circuits.  But that's still bunk; the other attacks win fine,
+   and the pause attack doesn't risk detection so much.
+
+   Still, to do this one, we'd want to have outgoing and incoming
+   circuits treated differently.  Incoming cells could work as in 1 or 2
+   or 3 above; outgoing cells would want to have a header portion as in
+   mixmaster, where each node checks that the first N bits of the header
+   match a MAC of all data seen so far, *including the rest of the
+   cell*.  They'd then decrypt the rest of the cell, remove the first N
+   bits of the header, and re-pad the header with N bits at the end,
+   taken from a PRNG whose seed is shared with the client.  (This is
+   basically how mixmaster works, and how mixminion works in the common
+   case.)
+
+   The space overhead here is kind of large: N bits per cell per node.
+   In the most paranoid case, if we used 256-byte HMACs on 3-node paths,
+   that's 96 bytes per cell, which is more than 20% of the total length.
+   But we can probably do better if we let the CREATE operation also
+   tell the node some N to check.  For example, the first node doesn't
+   need to check any bits.  The second and third nodes could check 64
+   bits apiece; that only has 16 bytes overhead, and high probability of
+   catching any changes. (Birthday attacks don't matter here, and an
+   attacker who mounts this attack for long enough to accidentally find
+   a 64-bit mac will break so many circuits in the process as to become
+   totally unreliable.
+
+   But all of this leaks the path lengths and position on the path to
+   various nodes.  We might open ourselves up to partitioning attacks if
+   different clients choose different numbers of bits.  What's more, we
+   might leak the length of the path to the last node by how much junk
+   there is at the end of the cell.
 
    Here's a simple construction for this format, to be concrete:
 
      The CREATE operation's KDF produces the following outputs:
-           Kf, IVf  (stream cipher key, and possibly IV, for forward direction)
-           Kb, IVb  (stream cipher key, and possibly IV, for reverse direction)
+           Kf, IVf  (stream cipher key and IV for forward direction)
+           Kb, IVb  (stream cipher key and IV for reverse direction)
            Mf       (MAC key for forward direction)
            Mb       (MAC key for reverse direction)
            SEEDf    (PRNG key for forward direction)
@@ -465,27 +496,28 @@ Option 4: Shall we have middle nodes be able to fast-stop bad data?
            MACBYTESb (an integer between 0 and 32 inclusive)
            CANEXIT   (boolean: can we exit from this hop?)
 
-     Let Kf[i], Mf[i], etc denote the parameter Kf, Mf, etc as shared between
-     the client and the i'th node in its circuit.
-
-     Relay cells sent towards the client have the following plaintext format:
+     Let Kf[i], Mf[i], etc denote the parameter Kf, Mf, etc as shared
+     between the client and the i'th node in its circuit.
 
+     Relay cells sent towards the client have the following plaintext
+     format:
          Body:
            Content:
              Relay Command [1 byte]
              StreamID      [2 bytes]
              Length        [2 bytes]
              Data          [Up to CELL_DATA_LEN-5-MACBYTESb bytes]
-             Padding       [randomly generated as needed to fill the cell]
+             Padding       [randomly generated as needed to fill the
+                            cell]
            MAC(All previous encrypted content + encrypted content,
                                   Mb)[:MACBYTESb]   [MACBYTESb bytes]
 
-     The originator of the client-bound cell encrypts the content with the
-     next part of its Kb,IVb stream, then appends the MAC.
+     The originator of the client-bound cell encrypts the content with
+     the next part of its Kb,IVb stream, then appends the MAC.
 
-     Non-clients receiving a client-bound relay cell encrypt the entire cell
-     body, MAC included, with the next part of the stream cipher that was
-     keyed with Kb,IVb.
+     Non-clients receiving a client-bound relay cell encrypt the entire
+     cell body, MAC included, with the next part of the stream cipher
+     that was keyed with Kb,IVb.
 
      When the client receives a relay cell body, it iteratively does:
 
@@ -497,15 +529,15 @@ Option 4: Shall we have middle nodes be able to fast-stop bad data?
             passed by every node on the circuit.}
 
            If MACBYTESb[i]>0, check whether MAC(cells_i | cellbody,
-           Mb[i])[:MACBYTESb[i]] the last MACBYTESb[i] bytes of the cell.  If
-           so, this cell is from node i.
+           Mb[i])[:MACBYTESb[i]] the last MACBYTESb[i] bytes of the
+           cell.  If so, this cell is from node i.
 
            If this cell is from node i, decrypt the first
            CELL_DATA_LEN-MACBYTESb[i] bytes of the cell using the stream
            keyed with Kb[i],IVb[i].  Act on it as a relay cell.
 
-           Otherwise decrypt the entire cell, MAC included, with the stream
-           keyed with Kb[i], IVb[i].
+           Otherwise decrypt the entire cell, MAC included, with the
+           stream keyed with Kb[i], IVb[i].
 
       If no node sent this cell: it's junk and somebody is probably
       messing with us!  Destroy the circuit.
@@ -535,7 +567,8 @@ Option 4: Shall we have middle nodes be able to fast-stop bad data?
 
          For i in 2...N:
              Let L = len(PADSEEN[i-1])
-             Let PADSEEN[i] = (PADSEEN[i-1] xor STREAM[i-1][CELL_DATA_LEN-L:]) | PAD[i-1]
+             Let PADSEEN[i] = (PADSEEN[i-1] xor
+                              STREAM[i-1][CELL_DATA_LEN-L:]) | PAD[i-1]
 
          For i in N down to 1:
 
@@ -549,15 +582,15 @@ Option 4: Shall we have middle nodes be able to fast-stop bad data?
 
      To receive an outbound cell:
 
-         Let M be the first MACBYTESf bytes of the cell, let REST be the rest
-         of the cell, and let "cells" be all previous cells on this circuit.
-         If CANEXIT, and M = MAC(cells|rest|"RECOGNIZED", Mb)[:MACBYTESf],
-         and MACBYTESf > 0, this cell is for us.  If M = MAC(cells|rest|"OK",
-         Mb)[:MACBYTESf], this cell is not for us, but is valid.  Otherwise,
-         destroy the circuit.
+         Let M be the first MACBYTESf bytes of the cell, let REST be the
+         rest of the cell, and let "cells" be all previous cells on this
+         circuit.  If CANEXIT, and M = MAC(cells|rest|"RECOGNIZED",
+         Mb)[:MACBYTESf], and MACBYTESf > 0, this cell is for us.  If M
+         = MAC(cells|rest|"OK", Mb)[:MACBYTESf], this cell is not for
+         us, but is valid.  Otherwise, destroy the circuit.
 
-         Decrypt REST using the stream cipher keyed with Kf,IVf.  If this
-         cell is for us, act on it as a relay cell.  Otherwise, let
+         Decrypt REST using the stream cipher keyed with Kf,IVf.  If
+         this cell is for us, act on it as a relay cell.  Otherwise, let
          PAD = the next MACBYTESf[i] bytes of the PRNG keyed with SEEDf,
          and relay REST | PAD.
 
@@ -572,28 +605,30 @@ Option 4: Shall we have middle nodes be able to fast-stop bad data?
      PICKING MACBYTESf,MACBYTESb.
 
          We don't need to worry about birthday attacks:
-            Because we're using a MAC, only the parties who are making the
-            MACs could try to do a brute-force search for a collision, but
-            they have no reason to do so.
 
-            If a collision occurs accidentally, an adversary can't substitute
-            an earlier-seen cell for a later one with the same MAC, since the
-            MAC covers not only the cell, but all previous cells on the
-            circuit.
-         So 16 bytes is about the most we should ever do, given our usual
-         security parameters.  Let me moot the number 8 for MACBYTESb.
+            Because we're using a MAC, only the parties who are making
+            the MACs could try to do a brute-force search for a
+            collision, but they have no reason to do so.
+
+            If a collision occurs accidentally, an adversary can't
+            substitute an earlier-seen cell for a later one with the
+            same MAC, since the MAC covers not only the cell, but all
+            previous cells on the circuit.
+
+         So 16 bytes is about the most we should ever do, given our
+         usual security parameters.  Let me moot the number 8 for
+         MACBYTESb.
 
          For outbound cells, for any hop we can exit from, choosing
-         MACBYTESf=6 gets us the current security level.  For the first hop,
-         assuming we don't exit from it, choosing MACBYTESf=0 is totally
-         safe, since the link crypto guarantees that nothing was corrupted on
-         the way.
+         MACBYTESf=6 gets us the current security level.  For the first
+         hop, assuming we don't exit from it, choosing MACBYTESf=0 is
+         totally safe, since the link crypto guarantees that nothing was
+         corrupted on the way.
 
          In general, to prevent an end-to-end tagging attack, it seems
          sufficient to do something like setting MACBYTES=8 for the last
          hop, and MACBYTES=8 for one hop in the middle.
 
-
 ACKS
 
    Lots of the good ideas and concerns here are due to Robert Ransom.