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

[Trevor Perrin]

On Fri, 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/ and we think it is actually
> useful in the real world.


Nice paper, thanks for sharing this!

I'm glad researchers are looking at asynchronous public-key
forward-security beyond the "blunt instrument" of forward-secure
public-key encryption with time intervals, which you rightly
criticize:

"it must leave some messages exposed until the receiver can be certain
that it is safe to wind the key forward.  When one factors in clock
drift and delivery latency, the result may be a period ranging from
hours to weeks during which data remains vulnerable".

I also like how your model deals with the costs and limitations of
*per-message* asynchronous public-key forward-security by combining it
with:
 * A ratcheting protocol, so the costs of the per-message system only
need to be paid on initial messages, not every message.
 * Time-based deletion of old keys for "fallback" forward-security of
messages that didn't arrive, or when the per-message system is
overwhelmed by the rate of initial messages.

One thing your model doesn't consider is whether a server associated
with the recipient can coordinate senders so that each message uses a
different tag (or sequence number, or "prekey") from a small space,
without colliding.

If such a server exists, then I think the increased power of
"puncturable" public-key encryption versus "forward-secure" public-key
encryption isn't needed.  In other words: for forward-secure
messaging, if a server can hand out per-message keys (or tags) in
sequence, and the recipient receives the messages roughly in sequence,
then FS-PKE should be sufficient, and the more-powerful-but-less
efficient construct of P-PKE doesn't seem necessary?

---

The server-assistance case is interesting to me, so to delve into it further:

There's a "trivial" FS-PKE where the recipient publishes a bunch of
one-time public keys, and performs updates by deleting one of the
private keys (e.g. TextSecure's "one-time prekeys" [1]).  An
interesting question is whether pairing-based crypto for FS-PKE would
offer practical advantages.

I think the trivial FS-PKE works well for per-message forward
security, particularly when:
 * FS-PKE occurs at a low rate in normal use (e.g only on the initial
message between correspondents).
 * A DH-based ratcheting protocol supplies additional forward security
to subsequent messages, so the FS-PKE scheme is only responsible for
the initial message's forward security.
 * There's a fallback time-based mechanism that replaces and deletes
old keys, so even if pre-keys get entirely consumed forward-security
of initial messages gets reduced, but doesn't disappear.
 * Anti-abuse and throttling can limit malicious consumption of pre-keys.
 * Recipients are frequently online so can replenish their pre-keys quickly.

Pairing-based crypto brings new crypto assumptions and new and
complicated code.  So it would have to offer a dramatic improvement in
efficiency or attack-resistance to have a chance of being worthwhile
(and even then the simplicity of the trivial scheme, and the
mitigations above, makes it hard to beat).  But let's consider:

On the efficiency front, I think pairing-based FS-PKE like BBG [2] or
CHK [3] would be overall worse than the trivial scheme: the recipient
would publish less public-key info to the server, but the server would
give more public-key data to each sender, ciphertexts would get
bigger, and encryption/decryption compute times would increase by a
factor of several.

Attack resistance is harder to characterize:  the trivial scheme works
great until someone maliciously consumes all prekeys, when it falls
back to whatever your time-based mechanism is.  A pairing/HIBE-based
FS-PKE works until someone consumes enough updates / prekeys that it
becomes impractical for the recipient to perform that many updates or
store that many skipped-over private keys (because they might arrive
later).  So there will be some point where it gets overwhelmed and
falls back as well.

I'm not sure how efficient pairing-based FS-PKE can be made against
malicious consumption.  Most published work on HIBE-based FS-PKE
assumes time-based updates, not per-message updates.  So this would be
a good area for follow-on research, though I admit I'm skeptical any
benefits here would outweigh the simplicity of the trivial scheme, in
the end.


Trevor


[1] https://whispersystems.org/blog/asynchronous-security/
[2] https://eprint.iacr.org/2005/015.pdf
[3] https://eprint.iacr.org/2003/083