[messaging] Post-quantum forward-secrecy

[Jeff Burdges]

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.



-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150805/0f4ee54a/attachment.sig>