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

[Ian Miers]

There is a copy of the paper in the github repo if anyone else is looking
for it.

This isn't a ratchet, it's an encryption scheme you can use to replace
3DH/forward secure key exchange.  Why would you want this ? Because it
works without interaction and has a constant size public key (unlike signed
ephemerals which, even if not distributed by a server, require linear
storage).
You can and should use it to bootstrap a ratchet just like 3DH.

the application can pay extra CPU cost to allow for longer-delayed messages
> / worse-synchronised clocks",


The entire point of the combined scheme is that allowing for decrypting
late messages costs nothing: we simply keep interval keys around  because
forward security doesn't depend on us deleting them. When I said we combine
puncturable encryption with the time interval based approach, I didn't mean
we kept the deletion part. The entire point is we can avoid that.

The only time you pay the cost is if you get another message that was sent
in the same interval (late or otherwise) because then you have to decrypt
with a punctured key (and if you get n messages in the interval, with a key
punctured n times ). Minimizing the probability of this happening is why we
make intervals small.

If your traffic follows a Poisson distribution (i.e. it has an average rate
of arrival of x), you are unlikely to get many messages in a given interval
if you pick the interval appropriately(e.g. if you get 10 messages an hour
on average, make your interval 10 minute).  So occasionally your pay the
cost of decrypting with a key with once puncture, less frequently you
decrypt using a 2 puncture key, even less for 3, etc  because the odds of
getting n messages in an interval decrease very quickly as n increases.  So
costs stay manageable.  Real messaging traffic is probably more bursty than
a poisson process because of replies and such, but ratcheting smoothes that
over  since we use it for subsequent messages.


Ian

On Sat, Sep 5, 2015 at 9:08 AM, Ximin Luo <infinity0 at pwned.gg> wrote:

> On 05/09/15 12:27, Ximin Luo wrote:
> > Do you have a paper that describes this in more detail?
> >
>
> I just found the paper and skimmed through it. To answer my own questions,
> the differences between this and e.g. a typical ratchet is that:
>
> - the encrypted messages are not ordered, within an interval; ratchets
> encode an implicit order to the messages, in when they must be decrypted.
> This is probably a good thing; you can always add ordering on the layer
> above if needed.
> - don't need to generate a new random ephemeral key for each session,
> which is very good
>
> So I can see the benefits of using this to seed Axolotl sessions (or a
> non-lossy ratchet as I suggested previously).
>
> However, I don't think you suggest a good performance tradeoff for users
> of your library:
>
> - In a solely interval-based scheme, after a delay/unsync of T the message
> become undecryptable. Messages sent within <T of each other, are not
> forward-secret with respect to each other. If we want them to be so, we
> must reduce T.
>
> - Your scheme allows one to set a greater T, and still retain forward
> secrecy for individual messages within this time interval, at the cost of
> decryption performance. But then you suggest that users should set T to
> expect "1 message per interval", which roughly neutralises this benefit -
> messages delayed for longer than time T will again become undecryptable,
> just like in a naive interval-based scheme. Then the benefit is very small
> (i.e. those rare messages that are sent <T are still FS wrt each other),
> which probably doesn't justify the complexity of using this scheme.
>
> In other words, the tradeoff can be expressed as "the application can pay
> extra CPU cost to allow for longer-delayed messages / worse-synchronised
> clocks", and this (I guess) is something that users of your library will
> need to understand, judge for themselves, and set when using your library.
> The topic could be studied further too, to figure out what the best way of
> actually making this trade-off is.
>
> On another note, do you think it would be feasible to come up with a
> Puncture scheme that has a lower decryption cost? Or, alternatively, is
> this expected to be mathematically impossible?
>
> X
>
> --
> GPG: 4096R/1318EFAC5FBBDBCE
> git://github.com/infinity0/pubkeys.git
>
>
> _______________________________________________
> 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/20150905/71cdac92/attachment.html>