[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-commits] [torspec/master] start a draft for "new crypto ops"
commit d55883abf351b0df0a46ee6f5adc17dad61da9de
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
Date: Tue Oct 18 21:43:36 2011 -0400
start a draft for "new crypto ops"
---
proposals/ideas/xxx-new-crypto-sketch.txt | 601 +++++++++++++++++++++++++++++
proposals/ideas/xxx-ntor-handshake.txt | 17 +-
2 files changed, 614 insertions(+), 4 deletions(-)
diff --git a/proposals/ideas/xxx-new-crypto-sketch.txt b/proposals/ideas/xxx-new-crypto-sketch.txt
new file mode 100644
index 0000000..a4893e1
--- /dev/null
+++ b/proposals/ideas/xxx-new-crypto-sketch.txt
@@ -0,0 +1,601 @@
+Title: Design sketch for new crypto ops
+Date: 19 Oct 2011
+Author: Nick Mathewson
+
+0. Overview
+
+ The point of this document is to discuss what crypto we ought to be using.
+ See "Initial Thoughts on Migrating Tor to New Cryptography" from last year
+ for general guidelines and principles.
+
+ In broad strokes, the parts of our crypto are:
+
+ IDENTITY KEYS AND FINGERPRINTS
+ Addressed here in Section 2.
+ LINK CRYPTO (TLS) --
+ Addressed in proposls 176, 184. We say a little here though in
+ section 5.
+ CREATE/EXTEND CRYPTO --
+ Addressed in xxx-ntor-handshake.txt and rransom's extend draft
+ RELAY CRYPTO
+ Addressed here in Section 6
+ DIRECTORY SYSTEM
+ Addressed here.
+ HIDDEN SERVICE SYSTEM
+ Addressed in a forthcoming document by rransom.
+
+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.
+
+ 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
+ * 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.
+
+
+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.
+
+2. New identities
+
+ Identity keys and their fingerprints are used:
+ - 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 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.
+ - To determine which part of the circuit ID space to use on a Tor
+ instance's links.
+
+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.
+
+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 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:
+
+ router foo...
+ ...
+ identity-key
+ -----BEGIN RSA KEY-----
+ 1024-bit RSA key here
+ -----END RSA KEY-----
+ ext-identity-key
+ -----BEGIN RSA KEY-----
+ 3072-bit RSA key here
+ -----END RSA KEY-----
+ ...
+ ext-signature
+ -----BEGIN SIGNATURE-----
+ 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
+ -----END SIGNATURE-----
+
+ ]
+
+ 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.
+
+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.
+
+2.4. Implications for current use of identity keys
+
+ Let's review our use of identity keys again and make sure that we can
+ handle all of them with the ideas above.
+
+ - To sign router descriptors
+
+ We discussed this in 2.2.
+
+ - To make sure we're talking to the right node in the link handshake
+
+ 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.
+
+ - 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.)
+
+ - 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.
+
+ - To identity nodes in consensus directories
+ - To identify nodes in the UI in various places
+ - Internally, to identify a node uniquely in the codebase.
+
+ See sections 3 and 4 below.
+
+ - To identify particular nodes in the hidden service subsystem
+
+ Out of scope.
+
+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.
+
+ 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.
+
+
+3. New fingerprints
+
+ Right now we compute fingerprints by taking the SHA1 hash of an ASN1
+ 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:
+
+ "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.
+
+ (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
+ 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.
+
+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.
+
+ 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?
+
+ In the UI we'll lose the property that no node has more than one
+ fingerprint: I do not believe that this actually hurts us.
+
+
+4. Directory changes
+
+4.1. Better cross-referencing
+
+ In some places, directory objects cross-reference one another by SHA1
+ hash. They should use a better hash algorithm instead.
+
+ XXX
+
+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 .
+
+
+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.)
+
+4.x.
+
+
+5. Link crypto changes
+
+
+
+
+6. Relay crypto changes
+
+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.
+
+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.)
+
+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.
+
+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.
+
+ 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).
+
+ (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.
+
+ 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.}
+
+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.
+
+ 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)
+ Mf (MAC key for forward direction)
+ Mb (MAC key for reverse direction)
+ SEEDf (PRNG key for forward direction)
+ And it also sets the following user-selected parameter:
+ MACBYTESf (an integer between 0 and 32 inclusive)
+ 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:
+
+ 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]
+ 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.
+
+ 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:
+
+ For node i in circuit from 1..N:
+ Let cells_i = all previous cells which we decided were from i,
+ and let cellbody = the body of the cell, except for the last
+ MACBYTESb[i] bytes.
+ {XXXX I'd be more comfortable if the MAC covered all cells
+ 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.
+
+ 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].
+
+ If no node sent this cell: it's junk and somebody is probably
+ messing with us! Destroy the circuit.
+
+ When the client *sends* a cell outbound to node N:
+
+ Let cells[i] start at "" for all i in 1...N initially, and get
+ updated as below.
+
+ Let MACLEN = SUM(MACBYTESf[1...N])
+
+ Let Body =
+ Relay Command [1 byte]
+ StreamID [2 bytes]
+ Length [2 bytes]
+ Data [Up to CELL_DATA_LEN-5-MACLEN bytes]
+ Padding [randomly generated,
+ CELL_DATA_LEN-5-MACLEN-len(Data) bytes]
+
+ Let PAD[i] = the next MACBYTESf[i] bytes from the PRNG keyed
+ with SEEDf[i], for i in 1...N.
+
+ Let STREAM[i] = the next CELL_DATA_LEN-MACBYTESf[i] bytes of
+ the stream keyed by Kf[i],IV[i], for i in 1...N.
+
+ Let PADSEEN[1] == ""
+
+ 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]
+
+ For i in N down to 1:
+
+ Let Encbody = Body xor STREAM[i][len(body)]
+ Let extra = "RECOGNIZED" if i == N, "OK" otherwise
+ Let cells[i] = cells[i] | Body | PADSEEN[i]
+ Let M = MAC(cells[i] | extra , Mf[i])
+
+ Let Body = M[:MACBYTESf[i]] | EncBody
+
+
+ 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.
+
+ 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.
+
+ ANOTHER VARIANT:
+
+ If we restrict MACBYTESf values to range 0..HL/2, where HL is the
+ length of the MAC output, we can replace
+ MAC(x | "RECOGIZED")[:MACBYTESf] and MAC(x | "OK")[:MACBYTESf]
+ with
+ MAC(x)[:MACBYTESf] and MAC(x)[HL-MACBYTESf:]
+
+ 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.
+
+ 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.
+
+ 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.
+
+ Michael Stone helped some with "relay option 4" above.
diff --git a/proposals/ideas/xxx-ntor-handshake.txt b/proposals/ideas/xxx-ntor-handshake.txt
index 41af5c7..1f988fc 100644
--- a/proposals/ideas/xxx-ntor-handshake.txt
+++ b/proposals/ideas/xxx-ntor-handshake.txt
@@ -67,13 +67,20 @@ Protocol:
NODEID: ID -- H_LENGTH bytes
KEYID: KEYID(B) -- H_LENGTH bytes
CLIENT_PK: X -- G_LENGTH bytes
+ PARAMSLEN: -- 2 bytes
+ PARMS: -- PARAMSLEN byets
+
+ (The "PARAMS" component is used to encode any additional authenticated
+ information that's needed for establishing the right kind of circuit.)
The server generates a keypair of y,Y = KEYGEN(), and computes
- secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID
+ secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PARAMSLEN | PARAMS
+ | PROTOID
KEY_SEED = H(secret_input, t_key)
verify = H(secret_input, t_verify)
- auth_input = verify | ID | B | Y | X | PROTOID | "Server"
+ auth_input = verify | ID | B | Y | X | PARAMSLEN | PARAMS | PROTOID
+ | "Server"
The server sends a CREATED cell containing:
@@ -82,10 +89,12 @@ Protocol:
The client then checks Y is in G^* [see below], and computes
- secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID
+ secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PARAMSLEN | PARAMS
+ | PROTOID
KEY_SEED = H(secret_input, t_key)
verify = H(secret_input, t_verify)
- auth_input = verify | ID | B | Y | X | PROTOID | "Server"
+ auth_input = verify | ID | B | Y | X | PARAMLENS | PARAMS | PROTOID
+ | "Server"
The client verifies that AUTH == H(auth_input, t_mac).
_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits