Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Why?

I wanted to add some security and privacy to a chat-type server for playing various games (with a few things that are done on the server to limit cheating). Going by the "Don't implement anything yourself, use NaCl etc" general guideline, I started to work on a protocol to allow this using NaCl. I then swiftly realized I was probably far better using TLS (with ephemeral DH) to supply the security/privacy requirements, instead of figuring out my own protocol using the NaCl boxes. But then continued the development around the protocol as a thought exercise. So I'm interested in getting critique on the protocol set out here, big (or little) holes, can it be simplified etc.

This protocol draws some influence from the CurveCP protocol, but there is no requirement for client auth, for example, so it does vary a little.

Requirements

  • Perfect Forward Secrecy - Compromise of the long-term (LT) server key shouldn't compromise past conversations. This is one of the main reasons its problematical to use NaCL in the obvious way, i.e. a single keypair.
  • Client repudiation of logs - While the server is needed to mediate some aspects of the service, it shouldn't have an authoritative log. Neither should clients.
  • (Optional) Serverside authentication of clients via LT clientside key - for private servers, be sure of identities.
  • Client anonymity - Someone outside the server (or retrospectively in the case of the LT key being stolen) shouldn't know who was on the server.
  • mitm resistance - via key pinning. i.e. client should be sure its talking to the same server as yesterday and can optionally check out of band for the public key. This is the ssh security model, but even with TLS, it's unlikely server operators will pay for a certificate, so its likely to have the same validation.

Terminology

All keys mentioned in the protocol are NaCl keypairs. S is a long-term key for the server, C' is a short-term key for the client. In what should hopefully be a statement of the obvious, when it is mentioned that keys are sent, only the public key from the pair is.

  • Box[...](s->p) - NaCl crypto_box from key s to key p. This is the notation from CurveCP.
  • {...} - packet sent over the network.

Protocol

Unless otherwise noted, the NaCl nonces are 64-bit counters (maintained separately for client and server), implicitly prefixed with a 16-byte string to ensure client and server never use the same nonce. Any message with a counter less than or equal to the count last seen is dropped without further consideration, avoiding replay attacks.

  1. Client generates a new short-term key pair, C'.
  2. Client sends {C',Box[N](C'->S)} where N is a 128-bit cryptographically random nonce. While this packet can be intercepted by an attacker, the contents are not readable unless they have the server's long-term key, S, so the value of the nonce is secret.
  3. Server sends {Box[N,S',flag](S->C')} where N is the nonce it just received and S' is the current short term key. If the nonces don't match, the server obviously doesn't have access to the LT server key and so isn't the same server. This should prevent an attacker from inserting themselves between client and server, since while packet 1 can be replaced with the attacker's pk, the chance of them guessing the 128-bit nonce to send back to the client is negligible, so the client can then reject the supplied key. flag indicates if the server wishes client-side pk auth.
  4. Client sends {Box[...,Box[0](C->S')](C'->S')). "..." includes items like username, client version etc. to weakly identify the client to the server and other users. The Box[0](C->S') crypto_box is included if the server wants it to verify the long-term identity of the client. 0 is a 32-byte string of zeros. The nonce for this transaction is a 4byte timestamp of the seconds since the epoch, a 8 byte random value, and implicit 0s to pad to 24 bytes. The inclusion of the timestamp protects against replay attacks (which shouldn't be an issue given this box is already wrapped in a box between short term keys and is itself to the short-term key), with the 64-bit random value to guard against two rapid connection attempts accidentally revealing something. Server aborts if this box isn't (a) valid, (b) all zeros, and (c) from the last 10s.
  5. Server sends {Box[...](S'->C')} as normal messages, Client sends a series of {Box[...](C'->S')}. Messages are dropped if the tags don't authenticate or the nonce is out of step. Messages are the 8-byte counter, with box contents split/padded such that each (nonce,box) is 1024 bytes. This increases bandwidth and cryptographic effort requirements, but further obscures the information sent and provides a much larger 'message space' should client or server wish to repudiate a communication.
  6. Every 5 minutes, the server generates a new S' and sends a packet encrypted with the old S' to notify all connected clients of the new public key. Counters for the crypto_box nonces are reset at this point. The old key remains until the next key rotation, to allow for messages sent in the cross-over period, therefore compromise of the server should reveal at most 10 minutes of conversation. At the cost of more entropy and bandwidth, the rotation can be made faster (say to 1 minute), to reduce the window.
  7. Client disconnects and destroys C'.

Other remarks

  • This protocol is trying to strike a balance between individual privacy and server resources. The only randomness needed on the server side is the new short-term keypair every x minutes, so an attacker with a large number of connections cannot exhaust the entropy available on the server. While this does mean that compromise of the short-term key reveals all clients communications in that epoch, since many clients will be in a 'room'/'channel' with many other clients, compromise of only one client's server-side key would likely reveal the communication of many others anyway.
  • The client doesn't need to rotate their short-term key. While they could, any compromise of the client likely reveals the full transcript in the memory of the client, so there's no need to decrypt anything for an attacker.
  • The client can maintain as many or as few long-term keys as it likes, to present different identities to different servers. Or, I guess, different identities to the same server.
  • Supplying the client's long-term public key C is currently done out of band. Given access to C and s, it is possible to prove a given client was on the server. I'm not sure how a more temporary authenticator could be constructed and if you're that paranoid, you can always periodically rotate your long-term key.
  • The server doesn't need to be privy to all client communications, only ones related to shared resources e.g. the state of the board, dicerolls, tokens, so as an extension to this, a protocol like mpOTR could be used for the contents of 'chat' type messages in a given channel on the server.
share|improve this question
1  
Your change in notation from CurveCP is a bit annoying. –  CodesInChaos Jan 17 '13 at 9:36
    
That was a very good point. I've updated the question to reflect the CurveCP notation. That was just a more or less direct transcription from the notepad where I'd been puzzling this out. –  namelessjon Jan 17 '13 at 20:27
    
Also, after some more thought, I'm fairly certain now that actually the Nonce pass back and forth at the start of the conversation does nothing. The security of that comes from the fact that without the server's private key, it should be unfeasible to forge a packet encrypted between the server's long term and the client's short term key. So my question mostly boils down to "Can you be sure of the authenticity of a key wrapped in a crypto_box?", to which the answer should be "Yes", since crypto_boxes are authenticated. –  namelessjon Jan 17 '13 at 20:33
    
You probably don't need the nonce, but only because the client short term key already serves as a nonce. And the server short term key serves as a server chosen nonce. If either were used multiple times, that could open up replay attacks. –  CodesInChaos Jan 17 '13 at 20:50
    
I was talking about the nonce, N, in that case. If the server is re-using short-term keys, that would blow the whole system open, assuming you had the same client keys connected, because then you would also probably get crypto_box nonce reuse with the same keypair, and at that point, you can just XOR the two packets. The keys shouldn't repeat naturally by chance, though. However, I should make the start of the protocol more specific either way. –  namelessjon Jan 17 '13 at 21:28
show 3 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.