Forward Secrecy


#1

TL;DR

An attacker who’s able to get hold of a 1:1 chat session key will be able to decrypt past and future messages on that 1:1 chat.

This thread aims to kick off a discussion (before the meeting in Basel July 4th-6th 2018) around the following points:

  • Should we try to implement Perfect Forward Secrecy as a deterrent?
  • If we implement PFS, what are the considerations/drawbacks/impediments? (seed topics below).

Context

One of the subjects that have been coming up regularly in discussions (e.g. in the Cardona meeting, as well as contributions from Jarrad, Oskar, and others) is the need to improve privacy by adding resistance regarding a 3rd-party who manages to get hold of the chat encryption keys. An established way to achieve this is by using the Double Ratchet algorithm, whereby we use different encryption keys every time we exchange messages, rendering earlier or later messages more protected against an eavesdropper who’s compromised one particular key.

The current situation is described in this Google Doc (Forward secrecy section, subject to confirmation from @cammellos that it is still accurate).

If we decide to implement PFS (which seems like a must if we want to be among the most secure messaging platforms out there), we need to have some discussions around:

  • User account recovery;
  • Usage on multiple devices;
  • Historic messages (mail server usage);
  • Should we have multiple modes? Should PFS be the default mode? How would it relate to Revolution Mode?
  • Advanced: dynamic whisper topic generation

Pinging @oskarth, @yenda, @cammellos, @arnetheduck, @Chad and anyone else who can contribute to the discussion.

Links:


Public Launch Scope
Media support in Status Chat
#2

I think if we want to provide a security on par of signal/whatsapp/etc forward secrecy is a must.
In terms of revolution mode, I am personally for “secure by default”, rather than the opposite, so forward secrecy should be the default.

Plausible deniability is fairly weak in whisper as it still requires some signing, even when enabled and until we find a good way to exchange the initial key (X3DH), it’s going to be difficult to provide any good guarantee, so I won’t be taking this into consideration for now.

Initial key exchange

The initial key exchange is what the document is trying to solve, as this is actually the hardest part, because signals relies on their server as a form of storage.

The document provides best effort forward secrecy and ensuring that:

  1. Both parties have successfully received the key before any sym-key encrypted message is exchanged
  2. We don’t prevent parties to communicate if the key has not been exchanged successfully

Which are very important properties for an asynchronous chat protocol.

X3DH would be a much better solution, but requires some form of storage (a server in signals case) which currently is not easy to replicate with IPFS/Swarm, as lacks of some properties. Smart contracts are an option and could be used for this, I will look at it more carefully.

There’s another option that would help us start a ratchet much faster, but I don’t know how cryptographically secure it would be, and we’d be in uncharted waters (basically we can start a ratchet using the PK of Alice & an ephemeral key sent by Bob, as both uses elliptic cryptography).

Best effort forward secrecy can be upgraded to just forward secrecy with a keepalive or a vanilla double ratchet implementation, as it’s only there to overcome account recovery.

Double ratchet

To fit a double ratchet onto whisper it would comes with a cost, which is likely to have to double encrypt messages, or otherwise we would need to find a way to send unencrypted messages on whisper (not sure if it’s currently possible, in any case, the payload would still be unencrypted, but the header won’t be, unless we chose for the encrypted header variant of the algorithm).

If we are willing to pay the cost of double encryption, then we can easily have a double ratchet implementation that is transport agnostic, and can be ported to pss easily.

Multiple devices

Multiple devices I believe needs to be treated in the same way group chats are treated, so that a conversation among 2 peers with one peer having 2 devices is the same a group chat with 3 participants, with pairwise encryption among the peers, which makes group management easier and more flexible than using a shared key among the group (same strategy signal has).

Account recovery

Account recovery and recovery of messages is incompatible with forward secrecy by definition, but if we want to provide this feature, I’d say to allow the user to backup his data somewhere, with a warning that we can’t guarantee safety of messages in case of key compromise.

In this case, I think there’s an argument for not using IPFS, and instead rely on a centralized form of storage which provides better access control at the cost of availability of course, but being a non-critical feature I think it might be worth taking the option in consideration.

Revolution mode

In terms of Revolution mode, long term maybe, so might be worth thinking about what we want, but we need to get the basics first, we definitely have a long way to go.

Dynamic whisper topic generation

Dynamic whisper topic generation is not too difficult to get working probably, but it might be a bit costly on terms of bandwidth.
It is important that any solution will not compromise the benefits given by a double ratchet, namely that is “fully asynchronous” ( I don’t need any previous message to decrypt the one I just received, so we don’t have to worry about ooo messages / dropped messages etc).

Steps to implement

This is how I would go about implementing it:

  1. Have a solid initial key exchange, using DH, which will need to be a bit synchronous, meaning there’s going to be a lift off phase where messages will be pk encrypted and we won’t be providing PFS for those. The reasoning to have this weaker version first is that this is actually the hardest problem to solve, so we solve it in a naive way first, and the come back to it, I would not want to spend too much time on this as the initial step, where we have quite a few unknowns.

  2. Implement a double ratchet, possibly paying the cost of double encryption, at the same time account recovery needs to be solved, so that a user that has recovered his account can still communicate with a contact. With a plain double ratchet that’s solved quite easily.

  3. Go back to the initial key exchange and fortify, ideally using X3DH backed up by some form of decentralized storage

  4. At this point backup of messages / topic ratcheting


#3

This is a very interesting topic, specially regarding our architecture.

HD wallets can help to generate ‘n’ specific new keys, and derivate some specific to some user.

It would be possible to implement a handshake mechanism, where using theirs public chat keys they exchange dedicated keys to each other.
This handshake can happen from time to time, by request or automatically, increasing a nonce in the derivance of HD key for that specific user.

Having the root hd wallet key, the user can decrypt all history from all users it interacted.

I think this can be the default behavior, and once using ENS usernames would be very powerful UX for this authenticated channel!

For mailserver it should not make any difference.


#4

@ricardo3

Having the root hd wallet key, the user can decrypt all history from all users it interacted.

This is something we want to avoid, as it breaks Forward Secrecy (unless I misunderstood what you mean), a DH exchange works similarly to what you described, but uses random keys, exchanged with each message in the double ratchet, so that even if one key is compromised ( or the root key ), no new messages can be decrypted, other than the ones already encrypted with that key of course.


#5

I see, but then how will the user read his own history? I imagined storing encrypted history in swarm and decrypted by hdwallet. If we want to fully detach from hdwallet than we should consider temporary history, or a mode with no history saving (memory only).


#6

how will the user read his own history

Do you mean in case he recovers their account?

If yes, allowing him to recover the history using a root key from swarm/ipfs it’s incompatible with forward secrecy, we can allow the user to store it, but we need to let him know that FS is lost if he does so.

Otherwise it is stored encrypted on his mobile device/desktop


#7

Yes, I mean that.

I think is not usual keeping history, and having a temporary DB seems that this DB will be locked inside device aswell.

Maybe we should survey users if they are interested in keeping chat history.


#8

In my opinion, public chat history is more interesting to users (so that they have some context when joinining a public chat) than 1:1 chat, but I might be wrong. Pinging @patrick regarding a survey. On the other hand, there will also be the case of group chats in the future…


#9

For multiple devices, would it make sense to have a command where you can ask from a 2nd device to sync from your 1st device, so that you have the complete history, as well that the double ratchet state for each chat restored to the 2nd device? In short:

  1. I install Status Desktop on my laptop;
  2. I ask it to sync my account from my phone;
  3. My phone does a secure pairing sequence where it asks me whether I want to allow the sync;
  4. Desktop gets all the information it needs through a secure channel, and it now has the same state as the phone.

#10

@pedro

yes, you need an initial sync so that the device is “authorized” ( you can transfer the history but you might need to force some Acks from the new device to keep ratcheting, as otherwise we only ratchet on one side, and we lose forward secrecy, but these are probably details).

For new conversations sharing state is tricky as effectively you would need to share state every time you send a message between the two devices, (I generate a private key with each message sent, but I need to share that with the desktop app, but can’t send it otherwise I don’t have forward secrecy, as if I compromise this message I will be able to decrypt the next message sent by the other peer).

One way (signal’s way), is to have one double ratchet between A1 & B, one double ratchet between A2 & B and one between A1 & A2, so that everytime you sent a message you send it to all the devices involved, at the cost of bandwidth/cpu.


#11

start by saying I know nothing about coding. I was just reading this string and had a thought about the issue of recovering messages in a private chat after doing an account recovery. I recently did a recovery of my account to test the recovery seed phrase, so I saw how you lose all contacts and all history of messages. I agree that backing up the messages kind of defeats the purpose of privacy in the messages. That said my history of messages are still on the other side of the conversation, i.e. on my friend’s phone. So if I do a full recovery I have to reconnect with my contacts, that is good and not a problem, kind of expected when you have to recover an account. Would it be possible to build a tool in the 1 to 1 chat where once I reconnect with my contact, he/she can send me a message that contains all our previous chats? Maybe data limited but it will get back a lot of recent (aka most valuable) history of our conversation. This would mean I don’t have to back up all conversation and lose privacy but once I reconnect with my contact we use the same privacy tool we use to communicate in Status and they send me the history of our conversation that is on their phone.

Again, I apologize if what I am saying is crazy because I do not know how to code. :wink:


#12

@Chopstick00 thanks for contributing in the discussion!

The issue with recovering messages in that way is that anyone who manages to get hold of your private key (when you recover an account your are re-creating your private key), will have access to all the messages, as it would be trivial to impersonate you. The method you described has some nice properties but for the purpose of this discussion is equivalent to any backup strategy.

This is incompatible with forward secrecy as the compromise of 1 key (your private key), will give an attacker access to messages from different sessions.

As far as I know, secure messaging apps tend not to store backups, from most secure to least:

  1. Signal allows you to create one locally, but you’d have to move it to the new device yourself, it is never transmitted over the wire
  2. Telegram (mind that it does not follow the “secure by default” philosophy), allows you to store encrypted backups only for non-secure chats
  3. Whatsapp/messenger etc store backups in a unsecure way, over the wire, in cloud storage services (as demonstrated recently by the Paul Manaford’s case)

https://en.wikipedia.org/wiki/Forward_secrecy#Example is a good example of the properties we are after.


#13

Very interesting idea for solving the history problem! Thanks for contribute with discussion.

We are building Identity with Friends Recovery, and this could be used as additional feature.

Basically the idea is then when Friends Recovery complete, and Identity is recovered, Status Wallet could request the backup history of 1:1 chat. I don’t think this should be automatic, but an action that require both participants to be online and agreement from history source.

About devices sync, I think we should support, can be whisper private messaging, so the history source encrypts to devices public key and send through whisper.


#14

@cammellos, thanks for the wiki article on forward secrecy. I did not fully understand it. So basically to be completely forward secret the past conversations can not be re-sent/deciphered, even if someone has your private key. So the goal, if I understand correctly, is to make the messaging app more secure than a Trezor or even a cold wallet for crypto. My understanding is if someone gets the private key to my Trezor then they can take my funds. So here speaking as an end user and coding neophyte, I would never expect my messaging to be more secure than my wallet, in fact the best case for my expectations would be for it to match the security of my wallet.

But I also understand I am not a Chinese dissident sending jokes to my friends about how President Xi looks like Whinnie the Pooh. :grinning: In that case I may want my text messages to be more secure than my wallet. This is sounding like the conversation about Ludicrous mode (@oskarth) and different end users having varying expectations. Maybe in Ludicrous mode you have Perfect Forward Secrecy and if I am part of leading a revolution in Egypt I understand that if I have to do a full recovery of my account from my seed phrase then all contacts and past conversations are automatically lost. In fact I would consider it a benefit if that was the case. In the event that I found myself in that situation and became a prisoner to the state, when they get out the wrench to get my seed phrase out of me, then I don’t need to take any blows from the wrench, just give up the seed phrase and when they restore the account all is gone.

All that said, for those of us who hope and pray we are never in need of Ludicrous mode and more likely will need to restore our account because we dropped the phone in the toilet while looking at social media; for those users, being able to get back my contacts would be valuable and again I think this users expectation of security is that if it matches my Trezor, I am pretty happy. I get it that if you have my private key you have any funds I have in my Trezor.

There was an interesting article on Medium about hiding your Trezor Wallets with multiple passphrases. Maybe there is a way to implement Ludicrous mode in a similar way, it being one of your “deeper wallets” inside your account. This way you only tell your Xi and Pooh jokes inside the Ludicrous level of your account. The rest of your account looks like a normal Xi loving citizen.

Here is the article:

Thanks again for responding and I have the utmost respect for your knowledge and ability to make things that I can only dream of become a reality.

One thing, impersonating me would not be trivial!! :grinning::+1:t4:


#15

Thanks for the great comments, @Chopstick00! I think one distinction that must be made between the hardware wallet and communications is that the 3rd party can perform surveillance of the communications 100% of the time, without your knowledge, whereas that is not the case with a hardware wallet. That being said, we will be meeting this week to discuss Chat security and the association of Ludicrous Mode and PFS will certainly be a subject of the conversation. :+1:


#16

@Chopstick00 your argument for the wallet is a very strong point and something that troubled me as well.

in addition to @pedro s point.

I don’t have a strong counterpoint to that but I have a few scattered ones:

  1. I agree with you that is a matter of expectations, if you installed Status to have a wallet and send/receive funds, you probably would expect that a wallet/account recovery to recover messages.
    if on the other hand you installed status as a secure messaging app, then automatic backup on by default might not be expected.

  2. At the moment you are highlighting a weakness (in my opinion) in the current way the app handles this 2 features, wallet/messaging: We couple wallet and chat, using the same key for both.
    Ideally I think we should move away from this, allowing the user to have 1 chat & multiple wallets for example ( or the opposite).
    Also it forces you to give away wallet information (therefore which transactions happened), every time you want to communicate with someone new, I can’t think this is a desirable feature.
    Having separate keys allows you to choose which information you want to share with whom, at the cost of usability.
    Generalizing I feel we should try to avoid coupling wallet & chat requirements, as it might not always be the case that we use the same key.

  3. Forward Secrecy is also a safe measure or the receiving end, not only for the sender ( think about a dissident contacting a journalist), having it on by default would prevent forcing ( or even just having) a lower level of security onto the receiving user.

  4. every time you send a message signed with your private key, you give away some cyphertext that can be used in attacks against your private key, so minimizing this is desirable (this is more to do with plausible deniability). having said that, there are no known attacks against rsa at the moment (dsa had this weakness), and also this is partially unavoidable as transaction needs to be signed . Messages are though a whole different scenario as it s much easier for an attacker to force arbitrarly encrypted cyphertext to be sent.

full disclosure I am not a big fan of having a revolution mode, (incognito mode in chrome is a ux failure ino), i am more for secure by default, with individual settings that can be tweeked to achieve more or less security, as for most people security is something they don’t know they needed until the did :slight_smile: but that’s for a different discussion.

again, thanks for the very insightful comments!


#17

A few days ago, @arnetheduck posted a link to Wire messenger whitepaper: https://wire-docs.wire.com/download/Wire+Security+Whitepaper.pdf

It describes how they implemented forward secrecy and it might be a good source of ideas. Of course, they approach relies on a server.


#18

@adam thanks for the link, I just had a quick read through the paper, they seem to be using the signal protocol (Axolot / double ratchet), with a simplied/weaker version of X3DH ( which is the actual bit that requires server side storage, and in our case is a bit tricky to implement)


#19

@cammellos thanks for the detailed response. I feel like my learning of the subject is happening exponentially in just this conversation.

I think you are correct in the position of Status should be security by default. If someone does not desire security they could just use WeChat, Telegram or any of the other apps that has not done it right yet. So maybe we are all thinking in the wrong direction. Maybe what everyone is calling Ludicrous or Revolution Mode should be default by design and the options should all be to lower security or provide simpler user interface. This is a great point, in that the community and developers need to all have an agreement on the basis of the app and work from there.

I really like your idea in item 2 above about having separate keys for the wallet and the chat. This kind of sounds like it would provide some of the functionality discussed in the Trezor article.

So lets go! I am on Team Forward Secrecy and separate keys by default. Convinced and sold. :slight_smile:


#20

Forgot to mention in the previous post, @Chopstick00, the link you sent for the Trezor wallet, that is actually easyish to implement in status and seems like a good idea ( basically if you get the password wrong, it will just open a new empty account, this kind of feature might make sense not to be enabled by default as it can be very confusing to the user if you are not aware of it).
We will be definitely discussing this and see whether to push forward, thank you!