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 <imi...@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@moderncrypto.org > https://moderncrypto.org/mailman/listinfo/messaging
signature.asc
Description: Message signed with OpenPGP using GPGMail
_______________________________________________ Messaging mailing list Messaging@moderncrypto.org https://moderncrypto.org/mailman/listinfo/messaging
