On Fri, 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/ 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 _______________________________________________ Messaging mailing list Messaging@moderncrypto.org https://moderncrypto.org/mailman/listinfo/messaging