[tahoe-dev] Invitation protocol

[Michael Rogers]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Brian,

You assume the invitation code remains secret until Alice and Bob have
completed the protocol, but may be discovered later. Is that a safe
assumption for email, IM, postcards, etc? Later, in the attacks
section, you assume Mallory can eavesdrop on the relay to learn the
channel ID. Why can't she eavesdrop on Alice and Bob to learn the
invitation code?

Maybe an explicit adversary model would be useful.

Cheers,
Michael

On 11/06/12 01:15, Brian Warner wrote:
> So in my previous email I mentioned the need for an Invitation
> protocol. The idea is to allow someone who's in a Tahoe grid to
> type:
> 
> tahoe admin invite Bob # -> "ixyn6bxeq6ydr3us6k3emwa23yq"
> 
> and get back a short "Invitation Code",$IC. Then they deliver this
> to someone else, via some out-of-band mechanism (maybe they email
> it, or send it over IM, or even transcribe it over the phone). The
> recipient installs Tahoe, creates a node (no Introducer, no
> parameters), and does:
> 
> tahoe admin accept Alice ixyn6bxeq6ydr3us6k3emwa23yq
> 
> and then, after the message-passing dust has settled, Alice and Bob
> will wind up with each others' public keys, associated with the
> petnames they offered, and maybe some extra contact information
> (hostname/port). Everything else can be bootstrapped from those.
> 
> My assumption is that we're allowed to bake-in a "relay": some
> server that provides a broadcast channel which all clients know how
> to access. This can be application-specific (e.g. all Tahoe clients
> would use http://relay.tahoe-lafs.org). By embedding the contact
> information (URL) into the application, we don't have to put it in
> the IC code. (you should be able to use your own relay, if you
> like, but that'll make the IC longer).
> 
> I also assume that the IC remains secret until the protocol is
> complete, but is likely to become public after that point, so if we
> need any forward-secrecy, it must come from something other than
> the IC.
> 
> I've spent a lot of time thinking about different protocols to make
> this safe, at various tradeoffs between length of the invitation
> code, restrictions imposed on how you use it, and resistance to
> attack. The attacker's goal here is to get her own keys injected
> into Alice and Bob's tables, allowing her to perform a persistent
> MitM attack on them. Getting her key into just one of their tables
> might be interesting too. A less interesting DoS attack is to flood
> the channel with messages, preventing the protocol from
> completion.
> 
> ## Protocol
> 
> If the IC can be at least 128 bits (plus a one-byte version
> marker), like "ixyn6bxeq6ydr3us6k3emwa23yq", and if the data being
> exchanged is public, then the simplest safe thing to do is this:
> 
> Alice: IC = "i"+base32(os.urandom(128/8)) HMACkey,DestroyCap =
> HKDF(IC) ChannelID = HKDF(DestroyCap) relay.create(ChannelID,
> (msg1, HMAC(HMACkey, msg1)))
> 
> Relay: creates messages[ChannelID] = [] stores (msg1, HMAC) under
> messages[ChannelID]
> 
> Bob: receives IC computes HMACkey, ChannelID does
> relay.get(ChannelID), fetches all messages[ChannelID] checks HMAC,
> accepts msg1 relay.add(ChannelID, (msg2, HMAC(HMACkey, msg2)))
> 
> Relay: adds (msg2, HMAC) to messages[ChannelID]
> 
> Alice: polls relay.get(ChannelID) waiting for msg2 checks HMAC,
> accepts msg2 relay.destroy(DestroyCap)
> 
> Relay: computes ChannelID=HKDF(DestroyCap) deletes
> messages[ChannelID]
> 
> (here HKDF and HMAC are both using SHA256)
> 
> The IC is base32-encoded in case it needs to be verbally
> transcribed, and contains no punctuation to be cut-and-paste
> -friendly and avoid line-wrapping inside email bodies.
> 
> If the client wants to use an alternate relay, the relay URL should
> be base32-encoded (to retain those properties) and appended to the
> IC, taking advantage of the fixed length of the random part. A URL
> of "http://1.2.3.4:5678/relay" would result in an IC like:
> 
> qa3wihm2bwtpewpepohz644kg4uhi5dqhixs6mjogixdglruhi2tmnzyf5zgk3dbpe
> 
> If the data being exchanged needs to be kept secret, then msg1 and
> msg2 should be one-time Curve25519 public keys, and you add a
> msg3/msg4 which are both boxed (using nacl_box, so encrypted and
> authenticated by the curve25519-generated shared key). This
> provides forward-secrecy: as long as Mallory doesn't successfully
> inject her own curve25519 pubkey in the msg1/msg2 phase, and if
> Alice and Bob delete the generated private keys before anyone
> learns them, then Mallory is forever locked out of the msg3/msg4
> contents, even after the IC is revealed.
> 
> (there's an alternate scheme in which the IC is used to generate a 
> symmetric auth+encrypt key, but that fails to provide forward
> secrecy once the IC is revealed, and might require a 256-bit key to
> achieve 128-bit security, not sure).
> 
> ## Attacks
> 
> The best attack is for Mallory to find a pre-image of the public 
> ChannelID, allowing her to forge the HMAC and get Bob (and then
> Alice) to accept an alternate msg1. With a 128-bit IC, this attack
> ought to require 2^128 operations. (someone please tell me if I'm
> wrong.. I believe that we care about pre-images rather than
> collisions, so we don't need a 256-bit IC to achieve a 128-bit
> security level). Mallory can compute this in a Rainbow Table ahead
> of time, and use the same table against everybody, so shorter codes
> (e.g. 64-bit) are breakable (I estimate about $600K and 256GB to
> build that table).
> 
> Since Mallory learns the ChannelID by eavesdropping, she can call 
> relay.add() and inject bogus messages into the channel. The relay
> has no way to distinguish these from real ones. Alice and Bob will
> ignore them, but they might be annoying. This could be avoided by
> deriving a private Ed25519 signing key from IC, making ChannelID be
> the corresponding public key, and making the relay (and clients)
> check signatures. (again, this might require a 256-bit IC to
> achieve 128-bit security against this noise, but even 64-bit
> security against this noise would be plenty).
> 
> ## Shorter Invitation Codes
> 
> I've also thought about what needs to happen if you want to use a 
> shorter code than 128 bits. I haven't put any numbers to it, but
> in general, as the code gets shorter, you need to add in more
> context, to reduce the attacker's ability to brute-force the IC
> (given whatever information they have available). The basic form is
> A=KDF(IC,stuff) and then derive HMACkey and the ChannelID from A.
> 
> Some tools include:
> 
> * add key-stretching into the derivation of A, like a few seconds
> of scrypt(). This increases the cost of the pre-image attack. *
> include public context into A: things like the sender's email
> address, and the receiver's email address. This prevents the
> attacker from amortizing guessing attacks across all users, so they
> must attack (Alice->Bob) separately from Alice->Carol, or
> other->Bob, or even Bob->Alice. On the downside, it requires that
> Alice accurately tell her client about Bob's email address (easy if
> her client is sending the email anyways, harder if the IC will go
> over IM), and the same for Bob (requires manual transcription of
> the email's "From" header, so error-prone) * for mobile-to-mobile
> applications (think Bump), include the rough location of the two
> nodes into A (trying multiple times to deal with fencepost errors),
> so that the attacker needs to know Bob's location to successfully
> spoof him. This may be easy for Alice (who is face-to-face with
> Bob), but expensive/annoying for Mallory. * when integrated with
> instant-messaging clients, include the user-account or
> chat-room-name information in A. This turns into OTR. * for
> interactive applications, when IC is too short to identify a single
> node (imagine millions of people are performing invitations at the
> same time), have the relay return a list of potential applicants, 
> winnowed by name or proximity, then have Alice and Bob select icons
> on a screen with personal non-private information (picture, avatar,
> full name) to indicate the expected partner. Once partner is
> selected, perform the protocol. * put more trust into the relay
> (allowing it to perform attacks that other intruders cannot): * use
> secure transport to the relay, by embedding the relay's pubkey into
> the application. This removes eavesdropping and offline attacks.
> The external attacker must constantly poll for likely ChannelIDs,
> hoping to beat Bob to his relay.add() call. * have the relay
> publish a frequently-changing 256-bit salt. Include the salt when
> computing A. The receiver fetches salts too, and must try several
> different (older) ones until they find one that matches, depending
> upon how stale the invitation is. *  The attacker must re-compute
> their preimage table for each salt. The attack window thus starts
> when a salt is published, and closes when Bob responds to the
> message. Needing to constantly rebuild the preimage table, even for
> windows during which Alice and Bob do not run the protocol (almost
> all of them), can be a large ongoing expense. The cost depends upon
> the size of the window (the relay could publish a new salt every 5
> minutes, and Bob could tolerate invitations up to 20 minutes old),
> which depends upon how long an Invitation lasts before it expires. 
> * to deter a colluding Relay from pre-computing salts (giving the 
> attacker more time to build their pre-image table), require them to
> include a hash of some public predictable value, like a stock price
> (q.v. "geohashing"), or the bitcoin block chain. Clients must
> verify, of course. * relay can actively rate-limit guessing
> attacks, forcing attacker to use more IP (expensive) addresses.
> Other rate-limiting tools are available: CAPTCHA, proof-of-work,
> bitcoin-based bonds. Using Bitcoin could let you set arbitrarily
> high costs-per-guess, at the expense of including settlement time
> in the overall latency budget. * derive ChannelID only from public
> context, turning offline attacks ("find preimage of channelid")
> into online (guessing channelid, asking "is this channelid
> valid?"), which can be subject to rate-limiting * adaptive IC
> lengths: if more context information is available (e.g. sending
> invitation over email means Bob's address is easy to use, or 
> integration with an IRC client makes the channel name available),
> then reduce the IC length. If Invitations are to be valid for
> several days (e.g. delivery over email rather than over IM or
> phone), make the IC longer.
> 
> With the right context, rate-limiting techniques, and UI work, I
> suspect this could allow safe use of codes as short as a few bits.
> 
> But, for Tahoe's current purposes, I think the 128-bit code is
> short enough, plenty simple, and entirely safe.
> 
> cheers, -Brian _______________________________________________ 
> tahoe-dev mailing list tahoe-dev at tahoe-lafs.org 
> https://tahoe-lafs.org/cgi-bin/mailman/listinfo/tahoe-dev

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)

iQEcBAEBAgAGBQJP1c53AAoJEBEET9GfxSfMDjgH+QFOpWVEfB6ZlybQbcifJppI
GDXMKJLBACSZZzTvarvWaGm5B0GkaXrJW0Qudz2hNSkaQ+ZXOpsDdv3VjtnWRcar
li+q2u+3FUPFB+vPOMQuW5ybzdhhPrqNE9LaDsW4bkS7p0GR4cdQknUP/1IaOLEo
PpSDo/OaLWmnY+eBsRnRFTmHfWuq1wL5lXDq7mihaixWKp7LD187aFvBOXIvLcTn
zZQl3EeuyecGGIo9yXxskFPJqVvtaXqUrl/Xt6pH0TwvARaASgkiT2+A7Yj/w44R
WIl+9YOQjoDas9frRE5ACnOWQlxMp8JHzwsa6sOLWbSiJop43998HVzOPGSDbzc=
=5vhF
-----END PGP SIGNATURE-----