The Double Ratchet Algorithm was developed by Trevor Perrin and Moxie Marlinspike, and is used in Open Whisper Systems Signal package. The method implements perfect forward secrecy for communications, with a triple Diffie-Hellman method for authentication and ECDHE for perfect forward secrecy. It is used in a number of systems including with Signal. The two parties exchange encrypted messages based on a shared secret key.They create a new set of keys every Double Ratchet message. In this way earlier keys cannot be calculated from the ones that follow. They also send Diffie-Hellman public values with their messages, and the results of the Diffie-Hellman calculations are then mixed together into the derived keys. The protocol is useful for making sure that a hack on one set of keys does not lead to a hack on the rest of the keys. In the following we will create two names (a and b), and the a will encrypt two messages for b, and b will encrypt one message for a:
Double Ratchet AlgorithmBackgroundWithin Signal we see the implementation of a double ratchet system which is able to generate a new encryption key for every message, and where a breach of any of the keys does not promise the previously used ones. An important concept in defending against a breach of the trust infrastructure is to implement key exchange methods (FS). With this a comprise of the long-term keys will not compromise any previous session keys. For example, if we send the public key of the server to the client, and then the client sends back a session key for the connection which is encrypted with the public key of the server, then the server will then decrypt this and determine the session. A leakage of the public key of the server would cause all the sessions which used this specific public key to be compromised. FS thus aims to overcome this by making sure that all the sessions keys could not be compromised, even though the long-term key was compromised. The problem with using the RSA method to pass keys is that a breach of the long keys would breach the keys previously used for secure communications. Another important concept is where is key is ephemeral. With some key exchange methods, the same key will be generated if the same parameters are used on either side. This can cause problems as an intruder could guess the key, or even where the key was static and never changed. With ephemeral methods a different key is used for each connection, and, again, the leakage of any long-term would not cause all the associated session keys to be breached. The problem with the core Diffie-Hellman method is that the keys are not ephemeral, so we should avoid it in generating keys. Signal, though, builds forward secrecy into their systems with a double ratchet method, and where each key will not lead to a breach of the previous ones. The double ratchet concept was created by Trevor Perrin and Moxie Marlinspike. In hashing, this is implemented by taking a secret ("A"), and then adding a value of zero to it and then hashing this. The next hash is then our secret with a one added to it, and so on. A breach of one of the hashed values will not reveal the original secret, and it will not be possible to guess the next key. Within the double ratchet method, we have an on-going renewal system and where the session keys are only ever short-lived. For this it uses the Elliptic Curve Diffie-Hellman (ECDH) key exchange method and a hashing method for deriving the keys - this gives it a "double" ratchet. The two parties exchange encrypted messages based on a shared secret key. They create a new set of keys for every Double Ratchet message. In this way earlier keys cannot be calculated from the ones that follow. They also send Diffie-Hellman public values with their messages, and the results of the Diffie-Hellman calculations are then mixed together into the derived keys. The protocol is useful for making sure that a hack on one set of keys does not lead to a hack on the rest of the keys. In the following we will create two names (a and b), and then a will encrypt two messages for b, and b will encrypt one message for a: Name 1: Bob Name 2: Alice Bob keys are: Identity key (Public key): tkUbaj1VwEIwi0kYRlWbl+0Don8WSgKOfbvij6+RT3c= ->Identity key (Private key): hIHdPPYfiF5eEoqXhAIOq1H5qy2VIJToadn1azjk96Q= Ratchet key (Public key): 7P3yOKPcAX5rVnQkQCmmGfQdo0mi4GL33Yy7DpFMbU0= -> Ratchet key (Private key): QYHS9FrJQ59VRDVqdwsDDVEbaaPp3myA+vUl3MTdC2Y= Handshake Public key: a/xifzSbU5wSwF8CFh+xP2ybY7jG/gKoY7dW0DTOHhA= ->Handshake Private key: lSvv3TRFq7xuHxeTjQDqXQc2+UOALDDNJmRXnoDCUBA= Encrypted message1 a->b: 2cuNbhbPkpcIck3j+9m76bUIr4X2cJdZSOARpGTzKPV3cs1NUrytT+CiNkgXVtJ2KEOzChxOeqLYoBjP11WW/UsSnkhFUkFH2So2iEXutBDHzlYExvQ9MCVkRkH6FaCnvpyPFvW5B6R+YUIok5CuZr0G9hI1Zqgcb0CRnZh0Nm4otP3f3A== Encrypted message2 a->b: efj2axgAmcBuyjkDzKARlaNzu5MzWqqqd0T9OZH/hW5Oy5JCQH1PN3/fYHu3lwU3N1gthhnGzHtJhlmq06pzXRcTJrhN5xlvsxAl+1K6t08QnD8Ev8myq1Ou719YySagwYRPBvZVo36GmFvN+qM05//weZtTFeL1fR2FZ1FMyjRR2+WiYjFzuE1AOw== Encrypted message3 b->a: H1gex6vZi0KTPywWK9XzVKmGiP2515XgYrM1Gx+kwq6JY8cQSLIKSHOjexqJhOR8MoGQs9IVX3aKbZkPRcKknsczl/jAdTav9ooFUe5c0XmJFWQEqwRkPgdpxFdbNmbMm7CwBne/6pyb7OfHEmzLUY+MYNLpF3dDwN6SOJFQTjzYe5eVaflBTrJn55TD b decrypt: The quick b decrypt: brown fox jumps a decrypt: over the lazy dog A mechanical ratchet only moves forward for one step at a time. In cryptography, a ratchet method allows for future states to be calculated but only if you know an original seed value. It is not possible to calculate previous states from the current state. Typically this is done with a one-way-function such as a hash with a seed value and a salt. For if we wanted to generate four ratchet values based a master key of "AlicePassword" (and using an HMAC hash, and were Alice will with an interactive hash of 0, 1, 2 and 3): \(H_0(\text{AlicePassword}) ≡ \text{HMAC}(\text{AlicePassword}, \text{0x00})\\ H_1(\text{AlicePassword}) ≡ \text{HMAC}(\text{AlicePassword}, \text{0x01})\\ H_2(\text{AlicePassword}) ≡ \text{HMAC}(\text{AlicePassword}, \text{0x02})\\ H_3(\text{AlicePassword}) ≡ \text{HMAC}(\text{AlicePassword}, \text{0x03})\) Each key is thus derived from the original seed. By observing H0(AlicePassword), it would not be possible to determine the next in the sequence (H1(AlicePassword)). As she sends messages, she creates an iterative hash for each one. With the double racket method, Bob and Alice use their own outbound session - with a ratchet and elliptic curve key exchange - to encrypt messages. The ratchet can only go forwards (and not backwards) and derives a unique key for each message. Ed25519 elliptic curve signatures are then used to prove authenticity. The value of the ratchet and the Ed25519 public key are shared with the other parties in the conversation. Initially, Alice and Bob each create three Elliptic Curve key pairs (Identity, Ratchet and Handshaking): The keys will then be derived from these. Bob, for example, exposes thre three public keys to Alice, but keeps his private keys for the generation of the shared secret key for the messages that Alice send to him. This key exchange will only be for the messages flowing between Alice and himself. CodingThe following is some sample code: import sys import binascii from pyaxo import Axolotl name1='bob' name2='alice' m1='hello' m2='goodbye' m3='nice' a = Axolotl(name1, dbpassphrase=None) b = Axolotl(name2, dbpassphrase=None) print "Name 1:\t",name1 print "Name 2:\t",name2 print "\n",name1," keys are:" print "Identity key (Public key):\t\t",binascii.b2a_base64(a.state['DHIs']), print "->Identity key (Private key):\t\t",binascii.b2a_base64(a.state['DHIs_priv']), print "Ratchet key (Public key):\t\t",binascii.b2a_base64(a.state['DHRs']), print "-> Ratchet key (Private key):\t\t",binascii.b2a_base64(a.state['DHRs_priv']), print "Handshake Public key:\t\t",binascii.b2a_base64(a.handshakePKey), print "->Handshake Private key:\t\t",binascii.b2a_base64(a.handshakeKey) # initialize their states a.initState(name2, b.state['DHIs'], b.handshakePKey, b.state['DHRs'], verify=False) b.initState(name1, a.state['DHIs'], a.handshakePKey, a.state['DHRs'], verify=False) msg0 = a.encrypt(m1) msg1 = a.encrypt(m2) msg2 = b.encrypt(m3) print 'Encrypted message1 a->b: ',binascii.b2a_base64(msg0) print 'Encrypted message2 a->b: ',binascii.b2a_base64(msg1) print 'Encrypted message3 b->a: ',binascii.b2a_base64(msg2) print 'b decrypt: ', b.decrypt(msg0) print 'b decrypt: ', b.decrypt(msg1) print 'a decrypt: ', a.decrypt(msg2) a.saveState() b.saveState() |