<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">This looks really cool, thank you for sharing it, Ian! :-)<div class=""><br class=""></div><div class="">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++.</div><div class=""><br class=""></div><div class="">Cheers,</div><div class="">Greg</div><div class=""> <br class="Apple-interchange-newline"><span style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; display: inline !important; float: none;" class="">--</span><br style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; display: inline !important; float: none;" class="">Please do not email me anything that you are not comfortable also sharing</span><span style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; display: inline !important; float: none;" class=""> with the NSA.</span> </div> <br class=""><div><blockquote type="cite" class=""><div class="">On Sep 4, 2015, at 12:42 PM, Ian Miers <<a href="mailto:imiers@cs.jhu.edu" class="">imiers@cs.jhu.edu</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div style="font-size:12.8px" class=""><font class=""><span style="font-size:13px" class="">Matthew Green and I developed a scheme <span class="">for</span> <span class="">forward</span> 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 <span class="">for</span> security. More importantly, we wrote a C++ library implementing it, available at </span><a href="https://github.com/imichaelmiers/libforwardsec/" style="font-size:13px" target="_blank" class="">https://github.com/imichaelmiers/<span class="">libforwardsec</span>/</a><span style="font-size:13px" class=""> </span><span style="font-size:13px" class="">and we think it is actually useful in the real world.</span></font></div><div class=""><font style="font-size:12.8px" class=""><br class=""></font><div style="font-size:13px" class=""><font class="">TLDR :</font></div><div class=""><ul class=""><li style="font-size:13px;margin-left:15px" class=""><font class="">Performance: depends on message distribution. Assuming a poisson process <span class="">for</span> initial messages (you only need this <span class="">for</span> initial messages, after that use Axolotl or another ratchet): <br class=""></font></li><ul style="font-size:13px" class=""><li style="margin-left:15px" class=""><font class=""><span class="">For</span> desktops: decryption takes 20ms expected and with 99.99% less than 200 ms.</font></li><span class=""><li style="margin-left:15px" class=""><font class="">Mobile is 3 to 4x worse but I haven't experimented with compiler optimization flags, so there's room for improvement.</font></li></span><li style="margin-left:15px" class=""><font class="">Ciphertexts are less than 0.5kb.</font></li><span class=""><li style="margin-left:15px" class=""><font class="">A public key is 1.6kb and lasts <span class="">for</span> 68 years if we expect one message a second.</font></li></span><li style="margin-left:15px" class=""><font class="">Secret key material should be less than 1mb.</font></li></ul><li style="font-size:13px;margin-left:15px" class=""><font class="">Crypto: </font></li><ul class=""><li style="font-size:13px;margin-left:15px" class=""><font class="">Pairings over BN256 curves</font></li><li style="margin-left:15px" class=""><font style="font-size:13px" class="">Assumes Bilinear Diffie Hellman Inversion Assumption and</font><font class=""> Decisional Bilinear Diffie-Hellman</font></li><span style="font-size:13px" class=""><li style="margin-left:15px" class=""><font class="">Random oracle <span class="">for</span> CCA security via Fiat Shamir </font></li></span></ul></ul></div><div style="font-size:13px" class=""><font class="">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.</font></div><span style="font-size:12.8px" class=""><font class=""><div style="font-size:13px" class=""><br class=""></div><div style="font-size:13px" class="">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 <span class="">forward </span>security <span class="">for</span> 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. </div><div style="font-size:13px" class=""><br class="">A BRIEF EXPLANATION OF THE SCHEME </div></font></span><div class=""><div style="font-size:13px" class=""><font class=""><span class="">Forward</span> 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 <span class="">for</span> 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.</font></div><div style="font-size:13px" class=""><font class=""><br class=""></font></div><div style="font-size:13px" class=""><font class="">While this ensures <span class="">forward</span> 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 <span class="">forward</span> security with short intervals and risk losing messages or have long intervals and leave more exposed.</font></div><div style="font-size:13px" class=""><font class=""><br class=""></font></div><div style="font-size:13px" class=""><font class="">Our scheme, Puncturable <span class="">Forward</span> 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.</font></div><div style="font-size:13px" class=""><font class=""><br class=""></font></div><div class=""><font class="">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.<br class=""><br class="">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 <span style="font-size:13px" class="">for</span> 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.<br class=""><br class=""></font></div><div style="font-size:13px" class=""><font class="">Ian Miers <br class="">Ph.D. student, JHU Computer Science </font></div></div></div></div> _______________________________________________<br class="">Messaging mailing list<br class=""><a href="mailto:Messaging@moderncrypto.org" class="">Messaging@moderncrypto.org</a><br class="">https://moderncrypto.org/mailman/listinfo/messaging<br class=""></div></blockquote></div><br class=""></body></html>