Forward secrecy (and forward anonymity)

[schulze]

In the current design we use long-term key-pairs to guarantee confidentiality and integrity. This doesn't provide any forward secrecy, and because of the problems raised in #72, also no forward anonymity.

[See http://en.wikipedia.org/wiki/Forward_secrecy or https://www.imperialviolet.org/2013/12/03/forwardsecretforjournalists.html for details about the concept of "forward secrecy.
Short version: It is the E in the ECDHE of the TLS-ECDHE_RSA_WITH_AES.... cipher-suite I am using with Github right now. It is a Good Thing, but not vital. ]

Changing the encryption-keys in regular intervals, as mentioned in #72, is not enough to implement forward secrecy. We also need to make sure that the old key-material is destroyed, so we first have to make sure that all contacts do have the new key-material.

[aBothe]

Why not hand out one-time-pads to new users :P

[schulze]

Alexander Bothe:

Why not hand out one-time-pads to new users :P

Because we are not building yet another toy for crypto people.

[schulze]

Why not hand out one-time-pads to new users 📦

Also, I fail to see what this has to do with forward secrecy.

[aBothe]

It was just a humorous interjection, nothing actually constructive :)

[schulze]

Forward secrecy unfortunately complicates handling of multiple devices a lot. That means we should consider how we can implement our ideas for updating keys (c.f. #72) in a multi-device setup.
Interesting mailing-list thread about the problem: http://moderncrypto.org/mail-archive/messaging/2014/thread.html#1013

The TextSecure protocol manages to combine both features, but I don't see that their solution can be used in Qabel's drop-server design.

[aBothe]

Perhaps a temporary solution for sharing/distributing keys etc could be found in using Sync.
Still, synchronous distribution where all devices are required to get the keys asap might not be solvable with that 'solution' though.

[roeslpa]

If we use the noise protocol, we only need to share ephemeral encryption keys. IMO TextSecures method could be used by using a file on the storage as a "key server":
All devices upload signed ephemeral keys and a sender is asked to encrypt a message with all device keys. Of course the number of devices can be seen easily, but that problem applies to TextSecure as well.
As soon as a device receives a message, one group of ephemeral public keys can be deleted, as far as a new group of keys is already uploaded.

To reduce the number of keys on the "key server" <#encryptedMessagesToMe we could implement the chain-key approach from TextSecure.

The usage of ECC would save storage space and the chain-key approach only works with EC keys.

Edit: the chain-key approach works with DH, but not with RSA.

[roeslpa]

@L-Henke, @schulze, @aBothe and maybe @cburkert lets have a discussion about this and #72 on Monday, because I think a decision if and how these issues can be solved, should be done soon to keep in time for beta (if 1st December is fix).

[thechauffeur]

@roeslpa good idea. Did you guys discussed this? An update of this issue would be nice if possible.

[cburkert]

@thechauffeur The guys discussed this and came to the conclusion that we redesign the crypto, switching to a crypto protocol called noise https://github.com/trevp/noise/wiki which @schulze mentioned in #72
The guys are currently working on a Java implementation of noise or a noise-inspired protocol.

[roeslpa]

Yep that's right, but since noise doesn't serve full forward secrecy, I will think about the approach of TextSecures axolotl and how we could use it. I will update this when I have a usable concept.

[roeslpa]

I thought about this for a while but I do not have a solution yet. Of course axolotl is the best choice to implement forward secrecy as it is wanted, but there is one problem:
Distributing ephemeral keys for all devices for an initial contact. As it is stated in here, for the initial contact there need to be ephemeral keys, but if A or B have multiple devices and want to get in contact with one device, the ephemeral keys of the other devices need to be stored online or on the initial-contact-device. One possibility would be leaving out the ephemeral keys for initial contact, but then we would not follow the protocol. Two other ideas would be uploading ephemeral keys to the storage or having ephemeral keys for each device on each device, but both of them would fail, if the exchange/update of those keys is slower than the speed of having new initial contacts (e.g. if one device is offline for a while and the previous list of keys is too short).
Having an offline device could lead to an attack on forward secrecy as well: as long as a device is offline all "received" messages to it would depend on the last updated key. That could be enforced by blocking key-update messages from this device.

If we leave out the ephemeral keys for initial contact I would say:
We should use axolotl, all device keys are stored on each device (only public keys of the other devices are needed). As soon as an initial contact is started both parties start key chains on all devices with all opposite devices.
Key updates are done by appending a new keys to normal messages.

IMHO we should use axolotl, but I am not convinced by the ideas of distributing ephemeral keys and I don't know what your opinion is about "breaking" the protocol. I did not find the way TextSecure is handling/planning to handle it. What do you say, @schulze @L-Henke ?

[roeslpa]

I was looking at this again from a more abstract perspective: if we use axolotl (~if we want real forward secrecy), each device has to have its own key, so each message needs be sent to all own devices and all devices of the receiver. Result:
#msg received per dev = avg(#msg sent per user) * (avg(#dev per user) * 2 - 1) //This formula is mathematically improvable
=> #downloads per dev = #msg received per dev * #dev per drop
If we had one key for all devices:
#downloads per dev = avg(#msg sent per user) * #dev per drop
That means the amount of messages increases by #dev per drop and #dev per user (3 dev/user =>5 times more traffic).. IMHO in long term perspective that is too much for mobile devices since nearly all traffic, not only chat, increases that much.. It also affects the number of possible drop users, so we could gain less anonymity by having forward secrecy..
In fact we partly gain forward secrecy by using noise. We might think about a "manual" key update, which a user can initiate by connecting his devices for the future.
What do you think?

[aBothe]

What about serving an extra drop channel that protects contents via PFS (Perfect Forward Secrecy cough)?
Couldn't this even be implemented in a separate qabel module then?
So if there's even more secure™ communication required by e.g. a chatting app, that PFS module is just 'hooked' in between the chat sender & drop crypto/upload.

This might be a good compromise between not letting the 'normal' traffic exhaust hardware resources and having PFS somewhere in Qabel. Additionally, public relation folks can still claim that Qabel provides PFS :D

[schulze]

Forward secrecy isn't a problem with respect to hardware resources or something like that. I would just make the protocol and key management more complicated.

I think it is a key design goal, that modules don't need to implement their own crypto and that module developers don't need to make decisions about which crypto provider to use.

I still think that in the long run we should do something like what you suggested. E.g. the core could provide an API to create OTR/axolotl sessions for synchronous forward secure communications for modules that have a concept of a session.

But that shouldn't be a priority right now :)

[roeslpa]

So the result is:
We want to have forward secrecy but only session-based, not for all communications and axolotl is a protocol that fulfils our needs. Since it is much work, we will do it later.
Reason for session-based forward secrecy: download overhead too big or too few users behind a drop-server

[thechauffeur]

@schulze you want to write a wrap-up and close this.

[thechauffeur]

@schulze what is the status of this?

[aBothe]

Noise provides Forward Secrecy (not Perfect, though..but that's okay, imho), so this issue is obsolete
(Am I right with this?)

[schulze]

(Am I right with this?)

No.

(I will write something after lunch :-) )

[aBothe]

I just thought because Noise uses temporary keys which are used one time only, it has some sort of forward secrecy.
But yeah, the primary keypair owned by an Identity is used all along for communication, so there's indeed no such thing as forward secrecy - hopefully I explained it right myself, at least up to some point :-D

[schulze]

Basically. Noise Boxes provide Sender forward secrecy: The sender can't decrypt boxes once they are encrypted, thus after compromise of the private key an attacker also can decrypt these messages.

The same does not hold for received messages: If your private key gets compromised an attacker can decrypt all messages send to you in the past and in the future.

(not Perfect, though..but that's okay, imho)

The word "perfect" in the context of forward secrecy is subtle, problematic and probably useless. "Perfect" has a very specific meaning in the context of Shannon's theory of information-theoretic cryptography. In the context of forward secrecy it was meant to have a similar meaning, but the meaning is probably very different from what you think it means.

[ Side note: The term "forward secrecy" is also somewhat problematic, because many people intuitively get a wrong idea about the benefits it provides. It does not mean that previous messages somehow get more secure or unbreakable. If somebody breaks AES or curve25519 then there actually is little benefit in having used a forward secret protocol. ]

About the future of this issue: I think we already decided how we want to proceed, so I will try to write a short summary and then we can decide if we want to close this and open a new issue (POST BETA) with a concrete plan of action.

[thechauffeur]

About the future of this issue: I think we already decided how we want to proceed, so I will try to write a short summary and then we can decide if we want to close this and open a new issue (POST BETA) with a concrete plan of action.

@schulze all right, do this. The thing is you labeled this issue POST BETA but you stated you write this summary and let the rest be POST BETA, right?

[schulze]

Our ideas in the past were, that we want to have a not too complicated protocol, that multi-client support is very important for many users, and that most of the data we transmit is long-lived and will be stored on the users devices. Forward secrecy would bring much additional value and only complicate the protocol. I think this still is correct.

(See also the thread on the messaging@ starting with http://moderncrypto.org/mail-archive/messaging/2014/001013.html about the design of forward secret multi-device protocols.)

It could still make sense to offer a forward secure channel, probably using noise pipes, for e.g. chat applications. I created issue #127 POST BETA for that.