[noise] Strengthening the Noise framework's metadata protection with PURBs

[Bryan Ford]

Hi everyone,

We recently published the final version of our PETS ’19 paper on Padded Uniform Random Blobs or PURBs, which I hope the Noise framework community will find interesting and relevant if you haven’t seen it already:

	Reducing Metadata Leakage from Encrypted Files and Communication with PURBs
	http://bford.info/pub/sec/purb-abs/ <http://bford.info/pub/sec/purb-abs/>

In particular, I’d like to see if there’s interest in strengthening the Noise framework’s metadata leakage protection in a future update so that as many as its message transmissions as possible are leakage-resistant PURBs?

In summary, there are two main elements to the PURB encryption discipline: (a) ensuring that all content of encrypted messages is indistinguishable from uniform random bits to anyone without a relevant decryption key, and (b) padding encrypted messages to a “PADMÉ” length, or a floating-point number with a mantissa no longer than its exponent, to minimize potential information leakage via length while keeping padding overhead low.

I was happy to learn from Trevor that Noise’s transport messages already satisfy part (a) of the PURBs discipline due to the “indistinguishable from random” requirement on the AEAD cipher functions (section 4.2 of the Noise spec).  That would just leave the padding aspect.  I see that in section 13 of the current spec, applications are “recommended to use a data format for the payloads of all encrypted messages that allows padding”, which is a great start, but a bit weak and vague.  Perhaps the PURB discipline offers an appropriate way to strengthen and flesh out the padding recommendation?

Where applying the PURB discipline would be less trivial and perhaps more interesting, of course, is in application to Noise handshake messages.  Defining a PURB-compliant version of the Noise handshake protocol could provide a stronger way to address the “handshake indistinguishability” issues the spec discusses in 10.5 among other related metadata leakage and privacy issues.  A simple approach to this is merely to do as section 10.5 already suggests and use Elligator encoding for ephemeral public keys.

But if it’s considered useful, the techniques in the PURBs paper above (e.g., the “MrPURB” and “MsPURB” algorithms) could enable Noise handshakes to negotiate among multiple potential keys and ciphersuites efficiently while keeping all messages fully indistinguishable from random.  This will only be fully possible in scenarios where the initiator already has at least one potential long-term public key for the responder, either cached or learned via some other channel, but I think this is often the case.  And even when not, it would be great if all messages starting from the second (the first encrypted response) could be maximally leakage-protected.

Looking forward to hearing your thoughts and feedback.

Cheers
Bryan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/noise/attachments/20190807/793b01f1/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: Message signed with OpenPGP
URL: <http://moderncrypto.org/mail-archive/noise/attachments/20190807/793b01f1/attachment.sig>