[messaging] libforwardsec: forward secure encryption for email and asynchronous messaging

[Tao Effect]

This looks really cool, thank you for sharing it, Ian! :-)

I look forward to learning more about it and hearing what others have to say; my only wish is for it to have been written in Rust instead of C++.

Cheers,
Greg

--
Please do not email me anything that you are not comfortable also sharing with the NSA.

> On Sep 4, 2015, at 12:42 PM, Ian Miers <imiers at cs.jhu.edu> wrote:
> 
> Matthew Green and I developed a scheme for forward secure encryption without interaction that, unlike early schemes, works with badly synchronized clocks and late messages. It was published at IEEE S&P (aka Oakland) this year and has a formal argument for security.  More importantly, we wrote a C++ library implementing it, available at https://github.com/imichaelmiers/libforwardsec/ <https://github.com/imichaelmiers/libforwardsec/> and we think it is actually useful in the real world.
> 
> TLDR :
> Performance: depends on message distribution. Assuming a poisson process for initial messages (you only need this for initial messages, after that use Axolotl or another ratchet):
> For desktops: decryption takes 20ms expected and with 99.99% less than 200 ms.
> Mobile is 3 to 4x worse but I haven't experimented with compiler optimization flags, so there's room for improvement.
> Ciphertexts are less than 0.5kb.
> A public key is 1.6kb and lasts for 68 years if we expect one message a second.
> Secret key material should be less than 1mb.
> Crypto:
> Pairings over BN256 curves
> Assumes Bilinear Diffie Hellman Inversion Assumption and Decisional Bilinear Diffie-Hellman
> Random oracle for CCA security via Fiat Shamir
> This code is in far better shape than most academic software and was written to be released. If people are interested in using it Matt and I need to review it more carefully and others may need to do so as well. We'd love to see it used. So please contact us if you are interested.
> 
> Because you can always use this to wrap a message encrypted with a vetted library, the worst case given a cryptographic failure of our library is you end up not having forward security for messages that, absent this, wouldn't have it anyway. The larger concern is buffer overflows and the like in our library , the underlying pairing library (RELIC), or GMP.
> 
> A BRIEF EXPLANATION  OF THE SCHEME
> Forward Secure Encryption (in contrast to key exchange protocols) typically works by mapping time intervals (e.g. one an hour) to portions of a secret key. (You can think of this as having one public/private key pair per time interval but with some advanced crypto that compresses the public key down to constant size and gets logarithmic sized private keys.) Messages for a given time interval can only be decrypted with the corresponding portion of the secret key.  After the time interval expires, that part of the secret key is deleted.
> 
> While this ensures forward security, it means late arriving messages (either due to delays or badly set clocks) can't be decrypted. This means we face a choice: either have fine grained forward security with short intervals and risk losing messages or have long intervals and leave more exposed.
> 
> Our scheme, Puncturable Forward Secure Encryption, avoids this. Instead of deleting keys, we update ("puncture" them) every time we receive a ciphertext. Once punctured on a ciphertext, a key cannot decrypt that message but can decrypt new ciphertexts (e.g. late arrivals). Obviously, keys can be deleted at some point to avoid an attacker dropping messages and then breaking into your computer later.
> 
> Unfortunately, decryption is linear in the number of punctures. However, punctures are per time interval and don't cary over, so if we make our time intervals short, we only expect to see one message per interval and never need to decrypt with a punctured key. This ends up being very efficient. It does mean performance depends on your message distribution. When you only get one message in an interval it works very well.
> 
> If you get many messages in an interval, performance only in that interval linearly worse but is still manageable for a while. (For those of you wondering about DOS, the system can always fall back to the time based approach. If too many messages arrive in an interval we can stop puncturing and lock in whatever performance we have for that interval.... you probably should delete that key soon after the interval expires). If you have high variance in your message distribution, you're going to need to use shorter intervals to ensure you usually get one message per interval. Past a certain point, this will also get expensive and the entire scheme might not be well suited to your needs.   I don't think this is close to the common case at all. For most applications, I think you can reasonably ensure you get one message per interval on average.
> 
> Ian Miers
> Ph.D. student,  JHU Computer Science
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150904/e41115b7/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 841 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150904/e41115b7/attachment.sig>