Skip to content

Instantly share code, notes, and snippets.

@tarcieri
Created July 7, 2012 19:14
Show Gist options
  • Save tarcieri/3067720 to your computer and use it in GitHub Desktop.
Save tarcieri/3067720 to your computer and use it in GitHub Desktop.
Cryptosphere Key Exchange

Cryptosphere Key Exchange

Assumption #1: For protocol efficiency, we will use UDP, and to avoid packet loss associated with breaking apart large UDP messages, we will attempt to limit all messages to the "minimum maximum reassembly buffer size", which is 512 bytes. Packet loss may result in a failed opportunity to engage with a particular peer, but hopefully we have lots of peers. If we really care about engaging a particular peer we can retry the handshake M times after an N second timeout.

Assumption #2: Satan is watching our packets. We don't want him to be able to be able to track public keys we are using in key exchanges through casual packet inspection. Therefore, all public keys must be sent in encrypted form. Ideally all packets in the system should appear to be random to minimize the amount of information that can be gathered through packet inspection.

Assumption #3: Alice is able to securely obtain Bob's public key prior to the key exchange

Alice wants to do business with Bob and initiates the exchange. Alice encrypts her own public key using Bob's public key, then signs the ciphertext using her private key. We get the resulting packet:

| Alice's Signature | Alice's Encrypted Public Key |

Alice sends this packet to Bob. Bob attempts to decrypt the encrypted portion of the packet using his private key. The result should be Alice's public key. We can verify this by using this public key to check the signature of the original ciphertext. We've now verified that someone who is at least pretending to be Alice (e.g. they may capture/replay this packet) wants to talk to Bob.

Bob then generates a 256-bit random value that will be used as the symmetric key for all further communication. Bob encrypts this value using Alice's public key, then signs the resulting ciphertext with his private key. We get the resulting packet:

| Bob's Signature | Encrypted Symmetric Key |

Bob then sends this packet back to Alice, who can decrypt the symmetric key using her private key and verify the value's authenticity by checking Bob's signature.

The public key cipher must have the following properties in order to work:

  • The size of the ciphertext must be 256-bytes (2048-bytes) or less so both the ciphertext and signature fit in a 512-byte UDP packet
  • The public key must be small enough that it can be encrypted using its respective algorithm

Due to the 512-byte restriction on messages, and my desire to maximize that space for things other than large cryptographic keys. I would like to use elliptic curve cryptography, not just for the handshake, but everywhere. So far I've run into the following problems:

  • Ruby only implements ECDSA, which is fine for the signature checks, but can't be used for sending the encrypted public keys
  • I would like to use something like djb's Curve25519 for this purpose (see http://cr.yp.to/ecdh.html) as it provides authenticated encryption in only 32-bytes and uses 32-byte keys but it's unavailable in Ruby
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment