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

[Jeff Burdges]

How damaging are the bilinear Diffie-Helman assumptions needed by the
pairing based cryptography here?  It's simply that the curve involved
must be huge or something?  Are those costs and risks well understood?

Also, I'm curious about the scheme for sterilizing HIBE keys mentioned
on page 9, sounds useful for air-gapped keys.  Is there is reasonable
way to do that but avoid the bilinear Diffie-Helman assumptions needed
by pairing based cryptography?  I could imagine doing that with a server
that stores signed keys for each time interval, not sure if the server
can be avoided though.

Jeff



signature.asc
Description: This is a digitally signed message part
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

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

[Trevor Perrin]

On Fri, Sep 4, 2015 at 12:42 PM, Ian Miers  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 (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
___

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

[Ximin Luo]

Thanks for the explanation previously. Let me put it into different terms, 
which might make it clearer for others. Your scheme decouples these two things:

1. the ability to prevent decryption of messages sent in the past (that were 
not received)
2. the abliity to prevent re-decryption of already-decrypted ciphertext

The first one as you say is dependent on the user, and is something that would 
affect *all* forward secrecy schemes; the second one is always safe to do.

In a simple interval-based approach, these two things are bound together. So we 
keep the key for one interval around, because keeping keys for N intervals is 
equivalent to setting T = N * T'. Then the user has the awkward decision of 
having to choose T to balance (1) with (2).

In your scheme, you can keep keys for multiple intervals around, and this has 
equivalent security to setting T = N * T', but lets us avoid paying the 
Puncture decryption cost. (I see now that you did actually suggest this in 
section VIII of the paper.) This is better for the user, who now only has to 
consider (1) when choosing T, since the library handles (2) in all cases.

I think it's good to make this point (the decoupling) with more weight moving 
forward. It is, at first, non-intuitive to suggest to set T to expect 1 message 
per interval, since this "feels pointless" ("if you Puncture once most of the 
time, how is this different from just deleting the key"), but it's this 
decoupling of concerns that makes this not actually pointless.

X

On 05/09/15 22:17, Ian Miers wrote:
> Yep. There definitely is that issue. At some point, you should delete 
> interval keys to protect you from a TLA dropping your messages in transit and 
> then sending a black bag team into your house/cave/press office or grabbing 
> your computer at the border.   At  least  that decision is completely an 
> OPSEC consideration  and one that varies considerably between users. For 
> some, an hour is probably too long. For others, 24 hours might be on the 
> short side. But it's a completely free choice (you can even change it after 
> making your keys) for individuals or for application developers using 
> libforwardsec. And unlike previous schemes, if you choose a long window you 
> are not exposing messages you did receive.
> 
> I think this is an inherent problem with the intersection of  offline 
> delivery and forward security.  If I recall correctly, TextSecure faces a 
> similar trade off on when to delete  prekeys. 
> 
> - Ian (apparently that one)
> 
> On Sat, Sep 5, 2015 at 3:28 PM, Ian Goldberg  > wrote:
> 
> Ian,
> 
> Overall, a very nice scheme, and it's great you're producing
> production-quality code for it!
> 
> There's still the potential issue I asked about at the end of your
> Oakland talk, though: the forward secrecy only kicks in if the intended
> recipient actually _receives_ the original message, which is a slightly
> different property than "traditional" forward secrecy.  If the TLA
> (three-letter agency) doesn't just snoop the message, but actually
> intercepts (blocks) it, they can come a-knocking an arbitrary(*) time
> later to the intended recipient to compel the key that will decrypt it.
> 
> (*) Up to when you _do_ decide to delete old keys, which is when you
> give up on any messages that arrive late/desynchronized.
> 
>- Ian (not that one)

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git



signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

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

[Van Gegel]

Another approach with proposed scheme: 
receiver can punctures decryption key regularly with known time-period. So 
sender can manages PFS himself: send message with "best before" life-time 
(while receiver still viable and honest of course). This can be useful in some 
cases. 

___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

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

[Ximin Luo]

Hey, thanks for the post. It's always nice to hear about new work on ratchets.

+1 for writing new applications/libraries in Rust and ditching C/C++.

On 04/09/15 21:42, Ian Miers wrote:
>   * 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):  
> 

Could you explain the intention of {combining this with a ratchet} in a bit 
more detail? From your description, it sounds like your protocol "offers the 
same service" as a ratchet. What is the point of using two of them? Or from 
another viewpoint, why don't I use only "a ratchet" and avoid your scheme 
entirely?

In general, I think lossy ratchets are not good things to use for *a single 
session* which should have its whole integrity guaranteed. But one can use them 
to bootstrap "seed keys" for non-lossy ratchets that protect a whole session, 
to prevent drop attacks forcing you to re-use the same long-term key for the 
first message of each session. (By "non-lossy ratchet" I mean ones that don't 
allow holes in the middle of the session as Axolotl does; one can always 
implement a "delete keys and end the session if I don't get a heartbeat within 
X time", as you mentioned later.)

> [..]
> 
> 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.
> 

Do you have a paper that describes this in more detail?

It sounds sort of like an inside-out Axolotl - i.e. chaining ("intervals") then 
a DH-ratchet inside that ("puncturing"), or maybe even a chain-inside-a-chain? 
Could you compare your scheme with those options?

I'm not sure why you distinguish "puncture" as a different operation from 
"delete". In forward-secure protocols, whenever you "delete" a key you usually 
replace it with a new one so you can keep decrypting later ciphertext, but 
that's what you also define "puncture" to be.

> 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.
> 

Are you expecting the application / higher layer to manage this itself? This 
would get awfully complex to do "properly", especially for non-security-trained 
application writers.

X

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git



signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [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  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  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  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@moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging
>
>
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

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

[Ximin Luo]

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 

signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

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

[carlo von lynX]

On Fri, Sep 04, 2015 at 03:42:52PM -0400, Ian Miers wrote:
> Matthew Green and I developed a scheme for forward secure encryption

Thanks. For completeness I mention that there is something
vaguely similar at https://github.com/stealth/opmsg

Disclaimer: From my point of view these technologies solve one
out of 15 reasons not to use e-mail for privacy.

-- 
  E-mail is public! Talk to me in private using encryption:
 http://loupsycedyglgamf.onion/LynX/
  irc://loupsycedyglgamf.onion:67/lynX
 https://psyced.org:34443/LynX/
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

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

[Ian Miers]

Yep. There definitely is that issue. At some point, you should delete
interval keys to protect you from a TLA dropping your messages in transit
and then sending a black bag team into your house/cave/press office or
grabbing your computer at the border.   At  least  that decision is
completely an OPSEC consideration  and one that varies considerably between
users. For some, an hour is probably too long. For others, 24 hours might
be on the short side. But it's a completely free choice (you can even
change it after making your keys) for individuals or for application
developers using libforwardsec. And unlike previous schemes, if you choose
a long window you are not exposing messages you did receive.

I think this is an inherent problem with the intersection of  offline
delivery and forward security.  If I recall correctly, TextSecure faces a
similar trade off on when to delete  prekeys.

- Ian (apparently that one)

On Sat, Sep 5, 2015 at 3:28 PM, Ian Goldberg  wrote:

> Ian,
>
> Overall, a very nice scheme, and it's great you're producing
> production-quality code for it!
>
> There's still the potential issue I asked about at the end of your
> Oakland talk, though: the forward secrecy only kicks in if the intended
> recipient actually _receives_ the original message, which is a slightly
> different property than "traditional" forward secrecy.  If the TLA
> (three-letter agency) doesn't just snoop the message, but actually
> intercepts (blocks) it, they can come a-knocking an arbitrary(*) time
> later to the intended recipient to compel the key that will decrypt it.
>
> (*) Up to when you _do_ decide to delete old keys, which is when you
> give up on any messages that arrive late/desynchronized.
>
>- Ian (not that one)
> ___
> Messaging mailing list
> Messaging@moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging
>
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

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

[Tao Effect]

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  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 (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