commit 5d397a19f34212598b98fe1d4fc0ad5945cc0809 Author: Nick Mathewson nickm@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.