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

[Ian Miers]

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/ 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150904/b0908267/attachment.html>