commit 5d397a19f34212598b98fe1d4fc0ad5945cc0809
Author: Nick Mathewson <nickm(a)torproject.org>
Date: Mon Oct 31 11:06:30 2011 -0400
Re-flow new-crypto-sketch to a 72 columns, add a TODO
---
proposals/ideas/xxx-new-crypto-sketch.txt | 617 +++++++++++++++--------------
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.
