Apologies if this gets long and painful to follow. There are numerous points where I'm not precise enough, lack knowledge, etc.
Question : Can we design a post-quantum ratchet like Axolotl? It could use NTRU or perhaps another approach. Here would be my naive approach : Afaik, any "two step" ratchet like Axolotl, Axolotl without hash iteration, etc. needs to communicate the curve25519 public key that updates the ratchet for the current message in a header outside the body of the message itself. If we leave this key unencrypted, then an attacker with information on weaknesses in a sizable portion of the curve25519 key space could examine a conversation history in parallel to discover how much of the conversation they could potentially decipher, and then choose to spend their resources attacking all those keys, again in parallel. Pond addresses this by encrypting the Axolotl header with a key derived from a the previous root key. In essence, this creates a three-step ratchet for the Axolotl header from the Axolotl two-step ratchet. As I understand it, there are no mature post-quantum Diffie-Hellman alternatives, but NTRU is a relatively mature post-quantum public key system. Any attempt to use NTRU thus requires three steps. Also, we should not give up on curve25519 of course, maybe NTRU is vulnerable and useful quantum computers cannot be built. We should therefore focus on adding NTRU to Axolotl or similar. In principle, we could communicate an NTRU encrypted packet that modifies the Axolotl root key inside the Axolotl body, but that'd feels slightly complicated. thoughts? I'd propose instead that we encrypt the Axolotl header with NTRU, as that's a three step ratchet anyways. Does that sound reasonable? As I understand it, there is no reason to encrypt every Axolotl header with NTRU, as they only contribute to the root key if we're Alice. Additionally, we might not even want to use NTRU with every message that should impact the root key, as NTRU requires more computation than curve25519, and the keys are larger, like 1.6 KB I think. I'd love to hear any opinions on the following rough sketch : We add two variable size collections to the ratchet state : - a hash map our_extra_privates whose entries consist of an algorithm selection number field, a private key, and whose index key is the hash of the corresponding public key. - a list their_extra_publics whose whose entries consist of an algorithm selection number field, a public key, and a marker field. Algorithm selection number 1 is some symmetric cypher, which we'll discuss later, and algorithm number selection number 2 is NTRU. We encrypt/decrypt the full header with a key derived from the previous rootkey, exactly like Pond. Inside this envelope header, the first field is the hash of a key, and probably the second is a length or whatever. On the receiver side of header processing : If this hash is zero, then the remainder contains the usual header. If the hash is nonzero, then the receiver looks up the corresponding entry in our_extra_privates and decrypts with the listed algorithm and private key, and the result is the usual header. If decryption succeeds, then the receiver deletes the private key from our_extra_privates for forward-secrecy. We issue an error if the sender was not Alice. On the sender side of header processing : If we're Alice and the list their_extra_publics is non-empty, then we encrypt the header with the oldest unmarked key from their_extra_publics, and prefix with the stored hash, and then wrap this by encrypting with the value derived from the old root key. We now put a hash of our sent Axolotl curve25519 public key in the marker field. In future, if the recipient sends to that curve25519 public key, then we delete the marked entry in their_extra_publics for forward-secrecy. We should unmark and retry keys whose messages definitely got dropped, although I need to think a bit more about how to do this. On the sender side of message processing : We periodically create a new NTRU key, derive it's public key, update our_extra_privates, using algorithm number 2 for NTRU, and send algorithm number 2 and the public key inside message envelope but as a special prefix to the message body our applications sees. On the receiver side of message processing : If we receive the special prefix, then we store the algorithm number and key in their_extra_publics. Is this sketch post-quantum? Not as stated. An adversary who can break curve25519 but not NTRU can simply drop all the message that contain or use NTRU public keys. Yes, optional encryption is bad! We could detect drops of packets that use NTRU keys on the sender side by monitoring the number of marked private keys. It requires more finesse to detect drops of messages that contain NTUR public keys, or do recipient side detection, but sounds doable. It's maybe easiest to establish a convention about when to send NTRU keys. Additionally, the system is post-historically-quantum (PHQ) in the sense that an adversary who cannot break curve25519 today cannot determine what packets contain NTRU keys and thus cannot archive the traffic for analysis after they develop a quantum computer years later. There is a suggestion that PHQ should be called property 69 because it "one ups" Utah state route 68 that passes near a certain facility. Amusing, but probably not completely accurate. Why have an extra symmetric cypher as algorithm number 1? Axolotl becomes amazingly strong if the adversary cannot process even one root key update, think one-time-pad strong. Axolotl handles messages being out-of-order, but massively delayed messages cannot be successful Alice messages that update the root key. We're free to update our_extra_privates and their_extra_publics anyway we like however, like meetings at conference, alternative protocols, postal mail, etc. We'd probably need good verification of when these keys get used, and that complicates the user-interface, but sounds doable. In particular, there are aspects of OtR's socialist millionaire's protocol (SMP) that are difficult to replicate with asynchronous systems like Pond, but an extra header key could provide similar benefits. Isn't this impinging upon the user interface? Yes a bit, if we're asking users to print out QR codes to mail to their friends, but not if we're discussing a mixnet used for transporting messages that already offers many different routes. Imagine we've a mixnet that uses a Axolotl for an asynchronous messaging layer and Axolotl, or Axolotl minus hash iteration, for a synchronous link layer between servers. At both layers, we occasionally communicate NTRU keys to provide a measure of resistance to quantum attacks. We ask that servers who communicate at the link layer also give themselves pseudo-mailboxes and key up with one another at the messaging layer. We then make servers occasionally message each other new algorithm 1 keys through the messaging layer. Now a real-time adversary need only beak both curve25519 and NTRU. A PHQ adversary must potentially record much of the network though to ensure they capture all the needed messages. A PHQ adversary can still record all the traffic entering and leaving a single node. A stable server node can establish some post-quantum links by manually transferring algorithm 1 keys. Anonymous user nodes should not want long running link layer ratchets though, as their identify them to their guard nodes across sessions, and force servers to keep too many ratchets. Anonymous users could however have long term PHQ ratchets with servers besides their guards who then forward messages back to the user's guard node, probably by wrapping a message of the underlying mixnet, assuming it used a stateless OR protocol like Sphinx or HORNET. Again, apologies if this got painful to read. I'll attempt to write something more formal eventually, but I wanted to try to write something shorter first. There might be simpler ways to do effectively the same things too. Best, Jeff p.s. I posted about this on the curves list first, mostly because I wasn't opinions on NTRU itself, but messaging is better for discussing ratchets.
signature.asc
Description: This is a digitally signed message part
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
