Perfect Forward Secrecy, Deniability (Trac #1358)

[str4d]

It would be a huge win if we could have Bote have the properties of Perfect Forward Secrecy and of Deniability/Malleability, as we know from OTR.

In the background bote could send encrypted mails to peers in the addressbook and send them a time-limited and quantity-limited symmetric key, and sign it. the recipient confirms. the key is cached until it a) expires or b) was used to its use limit. When you want to send a bote mail, instead of signing it, you encrypt it with that symmetric key - since it is only known to sender and receiver it is as good as signing for the reciever, but no proof for third parties. In case of contacts not in the addressbook, have option to send without these features or with, in case of with, the mail is held in suspense while the above provcess is executed in the backgournd. This can significantly delay the delivery in case of rarely connected peers and therefore a warnung must be displayed.

ref:

http://security.stackexchange.com/questions/40451/is-off-the-record-style-encryption-possible-with-email

http://en.wikipedia.org/wiki/Off-the-Record_Messaging

Migrated from https://trac.i2p2.de/ticket/1358

{
    "status": "assigned", 
    "changetime": "2017-01-15T13:54:35", 
    "description": "It would be a huge win if we could have Bote have the properties of\nPerfect Forward Secrecy and of Deniability/Malleability, as we know from OTR.\n\nIn the background bote could send encrypted mails to peers in the addressbook and send them a time-limited and quantity-limited symmetric key, and sign it. the recipient confirms.\nthe key is cached until it a) expires or b) was used to its use limit. \nWhen you want to send a bote mail, instead of signing it, you encrypt it with that symmetric key - since it is only known to sender and receiver it is as good as signing for the reciever, but no proof for third parties. \nIn case of contacts not in the addressbook, have option to send without these features or with, in case of with, the mail is held in suspense while the above provcess is executed in the backgournd. This can significantly delay the delivery in case of rarely connected peers and therefore a warnung must be displayed. \n\n\nref:\n\nhttp://security.stackexchange.com/questions/40451/is-off-the-record-style-encryption-possible-with-email\n\nhttp://en.wikipedia.org/wiki/Off-the-Record_Messaging", 
    "reporter": "user", 
    "cc": "", 
    "resolution": "", 
    "_ts": "1484488475063299", 
    "component": "apps/plugins", 
    "summary": "Bote, Perfect Forward Secrecy, Deniability", 
    "priority": "major", 
    "keywords": "I2P-Bote security", 
    "version": "0.9.14.1", 
    "parents": "", 
    "time": "2014-08-24T22:41:21", 
    "milestone": "", 
    "owner": "str4d", 
    "type": "enhancement"
}

[str4d]

Trac update at 20140826T02:00:39: somewon commented:

What you are describing is not mathematically possible, unfortunately. There is no such thing as a decryption key that expires in such a way that it can no longer decrypt data. For instance, a GPG key that "expires" is only a very "soft" limit - all it means is that users verifying signatures from that expired key will receive a warning message, but the signature still works and can still be verified.

Computers do not have a "hard" definition of "time." Any value of "what time it is" on a computer is unreliable and can be spoofed. Even if it isn't spoofed, conditions of any given specific time can be emulated, along with any other conditions necessary to derive the key from the given supplemental data - most especially if the desired time value is one that has already elapsed (in the case of certain timestamp hardening efforts, like perhaps a proof-of-work blockchain).

Therefore, an "expiring" symmetric key offers zero deniability or forward secrecy - if the initial asymmetric key(s) are compromised, the symmetric session keys are also available, even into the future, and will work perfectly fine for verifying and decrypting the session's cleartext. True forward secrecy requires an interactive, multi-part handshake such as a Diffie-Hellman Key Exchange which establishes a secure, symmetric key that is never actually transmitted, either in the clear or encrypted. It is also generated non-deterministically (partially randomly) and therefore cannot be easily emulated or recreated.

Even your own links explain this, though it is certainly difficult to follow, so I don't fault you.

As explained in your links, ring signatures could provide a certain degree of deniability, but not forward secrecy (as defined as message cleartext privacy even in the event of a private key compromise). But higher-level protocols in the Bote system would probably not have any trouble calculating and comparing hashes of sent/received messages, anyway (and probably already do), without the need for ring signatures.

All in all, what you are describing is simply not mathematically feasible at this time, except by exchanging a multitude of Bote messages as a lower level means of establishing a Diffie-Hellman exchange, which is indeed feasible, but fairly slow and inefficient, and would not be as secure (or ephemeral) if either party's computer rebooted at any point before the communication was completely halted.

[str4d]

Trac update at 20140826T02:04:47:

• somewon changed resolution from "" to "invalid"
• somewon changed status from "new" to "closed"

[str4d]

Trac update at 20140826T08:25:06:

• user commented:

you have not fully understood the goal here. the keys are ephimeral. you don't use them over a long time. and they are wiped after use.

deniability/malleability follows directly from the use of symmetric keys. (Some define deniability in a different way. Here it refers to the fact that the receiver of a message cannot prove to a third party that the message was sent by a certain sender bote destination (you))

• user changed resolution from "invalid" to ""
• user changed status from "closed" to "reopened"

[str4d]

Trac update at 20140826T20:30:38: somewon commented:

I think one of us is misunderstanding something, then.

Let me explain this as I see it:

Consider the threat being secured against and the results of the proposed scheme. In our case, the primary threat is an observer (either passive or active) intercepting and presumably saving Bote ciphertexts. The scheme would hope to provide Forward Secrecy (defined as preserving message encryption keys indefinitely, even in the event of compromised private keys) and Deniability (defined as ensuring the integrity and authenticity of the message and its sender without the message data itself containing any demonstrable link to that sender).

You propose:

send them a time-limited and quantity-limited symmetric key

What I hoped to make clear is that such a key does not exist. There simply is not any such thing, at least not without relying on a centralized oracle of some kind that passes judgment on whether the key is currently valid or not (probably with some kind of multi-sig operation, like Shamir's).

Because the adversary has a saved record of all enciphered communications, they will always hold a copy of the symmetric key (perhaps encrypted to the recipient's public key, however), and there is no way to force them to delete it.

Likewise, the adversary also holds saved copies of all the following messages' ciphertexts, and can likewise not be forced to delete them. If they can gain access to the unecrypted symmetric key that was transmitted, they can then use it to decrypt their saved copies of the message ciphertexts that it was used for, at any time into the entire future.

So, even if the keys are "ephemeral," as long as they are in fact transmitted, they are essentially permanent. The same goes for the messages.

GPG uses a very similar scheme to encrypt its messages. A given message to be GPG-encrypted is symmetrically encrypted to a random key, and then a copy of the key is encrypted asymmetrically to each recipient's public key, and included with the symmetric ciphertext. However, this does not offer any kind of forward secrecy or deniability (in fact, it's rather like the opposite of those things).

That is the situation as I understand it. If I have misinterpreted your proposal at all, I would be corrected gladly. The goals for your idea are absolutely good ones and I, too, would like very much for them to be achieved.

[str4d]

Trac update at 20140826T21:36:32:

• user changed _comment0 from:

The idea is to use DH and AES for perfect forward secrecy. For deniable authentication OTR uses MAC's. But my current thinking - I may be totally wrong and blind now - is that if only two thwo parties know the key, the fact that the decypted mail is meaningful, already shows that it was encrypted with the correct key, i.e. the sender is who we think he is, ie. the mail is authenticated. If that does not suffice, then MACs could of course be added.

The difference between OTR and Bot ein that respect is just the timeframes.

to:

1409089167030944

• user changed _comment1 from:

The idea is to use DH and AES for perfect forward secrecy. For deniable authentication OTR uses MAC's. But my current thinking - I may be totally wrong and blind now - is that if only two thwo parties know the key, the fact that the decypted mail is meaningful, already shows that it was encrypted with the correct key, i.e. the sender is who we think he is, ie. the mail is authenticated. If that does not suffice, then MACs could of course be added.

The difference between OTR and Bot ein that respect is just the timeframes.

ps: if we go on signing the mail with our private keys, then the receiver can prove that a cipher text has come from us, and can then hsow that the cypher text decrypts to the plain text he has there. Thas making it extremely unlikely he has made up that text. Therefore we must use symmetric encryption here.

to:

1409142163478727

• user commented:

The idea is to use DH and AES for perfect forward secrecy. For deniable authentication OTR uses MAC's. But my current thinking - I may be totally wrong and blind now - is that if only two thwo parties know the key, the fact that the decypted mail is meaningful, already shows that it was encrypted with the correct key, i.e. the sender is who we think he is, ie. the mail is authenticated. If that does not suffice, then MACs could of course be added.

The difference between OTR and Bote in that respect is just the timeframes.

ps: if we go on signing the mail with our private keys, then the receiver can prove that a cipher text has come from us, and can then hsow that the cypher text decrypts to the plain text he has there. Thas making it extremely unlikely he has made up that text. Therefore we must use symmetric encryption here.

[str4d]

Trac update at 20140827T23:21:07: somewon commented:

The idea is to use DH

DH doesn't work with asynchronous messaging. As a bare minimum, three messages must be sent back and forth to establish a shared secret with DH. There are other ephemeral keying schemes that can work with only a two-part handshake, but the problem is still the same: both sender and recipient must be online at the same time, and exchange multiple messages, in order to calculate a shared secret.

But my current thinking - I may be totally wrong and blind now - is that if only two thwo parties know the key, the fact that the decypted mail is meaningful, already shows that it was encrypted with the correct key, i.e. the sender is who we think he is, ie. the mail is authenticated.

That is correct, additional authentication would not be necessary.

ps: if we go on signing the mail with our private keys, then the receiver can prove that a cipher text has come from us, and can then hsow that the cypher text decrypts to the plain text he has there. Thas making it extremely unlikely he has made up that text.

This is true. Signing removes deniability, and so it is not desirable in all circumstances. However, knowledge of the symmetric key also removes deniability, for the same reason that it provides authentication. The only way that I know of to keep message authenticity while preserving deniability is how OTR does it, with some clever SIGMA hacks.

So unless I'm mistaken, it still seems that what you're proposing is not only infeasible, but would also not accomplish all of the goals you would like it to.

[str4d]

Trac update at 20140827T23:31:57:

• user changed _comment0 from:

Quite the opposite: Knowledge of tge symmetric key die ont remove deniability but increase it. and I see no reason why you need to to be online all the time will the messages are exchanged. They are simply messages. And one mail in each direction might suffice for establishment.

to:

1409326656105604

• user commented:

Quite the opposite: Knowledge of the symmetric key does not remove deniability but increase it. and I see no reason why you need to be online all the time while the messages are exchanged. They are simply messages. And one mail in each direction should suffice for establishment.

edit: fixed some nasty typos

[str4d]

Trac update at 20140827T23:48:15: user commented:

without relays being used, considering curret delivery times, session establishment and sending the actual mail could be done in about an hour or little more. The process starts once bote starts up. Even with pidgin otr you only know that you were talking with the user you authenitcated, in the very moment of authentication, 5 minutes later someone else could be sitting at the computer. So that's what we have the local encryption for. when you send establish a secure session than the shared secret is saved encrypted or maybe not even that, but only kept in mem, and unlocked only once the user gets back to screen and enters the correct pw. Only then can he decrypt the mails he received or send authenticated mails. since the shared secret is then delete, this provides PFS if you sign your messages you need for that, than authenticity is for the receiver as guaranteed as now, however since you never sign the actual mail packets, there is deniability

[str4d]

Trac update at 20140827T23:49:17: user commented:

the thing is how to accomodate those pieces into the current storage and retrieval scheme

[str4d]

Trac update at 20140828T07:59:06:

• user changed _comment0 from:

since we can still encrypt it additionally the way it is done right now (using the recipient's dest), without losing any of the above propperties, there wouldn't be a need to change anything wrt the storing of the bote mails.

The shared secret could be calculated only when the user is in front of the screen.

to:

1409213676058393

• user commented:

since we can still encrypt it additionally the way it is done right now (using the recipient's dest), without losing any of the above propperties, there wouldn't be a need to change anything wrt the storing of the bote mails. (this refers just to encrypting the pre-encrypted mail and storing the packets, only the signing must be left out and the mail must have been pre-encrypted)

The shared secret could be calculated only when the user is in front of the screen.

[str4d]

Trac update at 20140921T11:59:18: user commented:

ok, we'd want a MAC too. Just relying on the fact that only the authentic peer really knows the encrpytion key is not secure. So first check if the MAC matches when you receive a ciphertext, then if it does match, decrypt it and mark it as authentic, else drop it.

Also an interesting read: https://whispersystems.org/blog/advanced-ratcheting/

[str4d]

Trac update at 20140928T15:18:14:

• zzz changed owner from "" to "HungryHobo"
• zzz changed status from "reopened" to "assigned"

[str4d]

Trac update at 20150110T04:14:22: str4d changed keywords from "I2P-Bote, security, perfect forward secrecy, deniability, malleability" to "I2P-Bote security"

[str4d]

Trac update at 20150319T22:15:39: user changed priority from "minor" to "major"

[str4d]

Trac update at 20150915T06:58:38: user commented:

Basically, this ticket should be renamed to: Incorporating Axolotl protocol into I2P-Bote. It offers OTR features for asynchronous messaging and has pretty neat propperties. However, it was not designed with a p2p infrastructure in mind. So especially the prekeys may need some thought.

[str4d]

Trac update at 20150919T14:52:33:

• user changed _comment0 from:

Description / Overview:

https://whispersystems.org/blog/simplifying-otr-deniability/ https://whispersystems.org/blog/advanced-ratcheting/ https://whispersystems.org/blog/asynchronous-security/

Protocol spec:

https://github.com/trevp/axolotl/wiki

Reference Java Implementation:

https://github.com/WhisperSystems/libaxolotl-java

to:

1442758193731178

• user commented:

Description / Overview:

https://whispersystems.org/blog/simplifying-otr-deniability/ https://whispersystems.org/blog/advanced-ratcheting/ https://whispersystems.org/blog/asynchronous-security/

Protocol spec:

https://github.com/trevp/axolotl/wiki (public domain)

Reference Java Implementation:

https://github.com/WhisperSystems/libaxolotl-java (GPL)

EDIT: see also https://whispersystems.org/blog/asynchronous-security/#the-textsecure-protocol

[str4d]

Trac update at 20150919T22:28:07: zzz commented:

Thanks for the links. I'm no expert, but they appear to rebut many of somewon's objections e.g. "DH doesn't work with asynchronous messaging".

Note that this protocol requires a centralized prekey server, which, as you imply in comment 15 above, is problematic. You can't just spray them out to a DHT, because each prekey may only be used once. Maybe you need a blockchain of prekeys and "spend" them?

[str4d]

Trac update at 20150919T22:32:06: zzz commented:

It's also useful to evaluate our current Garlic ElG/AES+tags implementation in the router in the whisper systems terminology, especially 'ratchet', with the view of modifying/replacing it someday.

[str4d]

Trac update at 20150920T14:24:20: user commented:

I'm not a big fan of blockchains myself. But yes, as you pointed out, the problem lies with the prekeys. More precisely, - they need to be stored somewhere so they are available when the respective peer is offline - they must be used only once - they must be repopulated/refilled

We currently use the DHT to store mails and a distributed addressbook, so yes, it could also store the keys. For fetched mail packets there are deletion packets that instruct the storage nodes to delete the mail packet. Something like this might be used to address point two. However, it does not guarantee its timely deletion. To address 2 and 3, in my original proposal the "prekeys" were not stored on a server or in DHT, but exchanged directly between the two parties in a previous connection. This would however restrict you to sending a first mail only after the other side has received a reqest by you and answered to it. For all subsequent mails you would not have any problems. But still, this is not ideal either. So maybe the delete keys or block chains should be looked at in more detail.

[str4d]

Trac update at 20170115T13:54:35: zzz changed owner from "HungryHobo" to "str4d"