Key privacy

[schulze]

Our Abstract:

Who communicates, exchanges data, uses a Qabel service when and with whom remains hidden, even from the provider.

RSA OAEP ciphertext is not "key-private" http://iacr.org/archive/asiacrypt2001/22480568.pdf, and I think by encrypting Drop message-keys using a public encryption-key we are leaking communication patterns.

Much simpler: If somebody (a Drop server, or a local network attacker) can build a list of public signing-keys, it is not hard to check random Drop-message signatures against many different keys to identify the sender of the message.

A drop-in solution to the problem would be to change signing-keys and encryption-keys regularly.

I think the nicest solution would be, to derive "session-keys" in the initial key-exchange with a new contact and then use these keys for Drop-messages to this contact.

[roeslpa]

We have to have a cryptographic instance which the trust relationship is built on after the initial (and for now personal) meeting. IMO that is the signing key.

We could use many encryption keys, signed by the signing key and published on our storage for example (after time new keys are added and old ones are removed; sender has to choose one from storage each time he wants to encrypt something). So this would bring us forward secrecy. I will think about the signing and anonymity problem, right now I have no idea how to solve this, but as mentioned changing the signing key is no solution to me.

Edit: Of course only partial forward secrecy depending on how often keys are changed

[schulze]

When you say "signing key" do you mean the "signing sub-key" or the "primary key" in the language of https://github.com/Qabel/qabel-doc/wiki/Components-Crypto#multiple-key-pair-concept?

The primary-key has to be long-term because trust is build on that key. The others could in principle be short-term.

[roeslpa]

I meant the primary signing key. What do we need signing sub keys for if they are not ephemeral?

Edit: Okay I see a reason, but only if they are just known to my contacts, that would help to gain key privacy if the primary signing key cannot be connected to them. And we define "key privacy" only for non-contacts or have different sub-signing keys for each contact.

[schulze]

I believe the possibility to make them ephemeral was one of the reasons for the introduction of the signing sub-keys. @L-Henke?

[L-Henke]

Yes. As long as the primary signing key remains the same, subkeys can be ephemeral...

[thechauffeur]

We need to decide on how and when to solve this.

[roeslpa]

A solution could be a key-renew-protocol:

First approach with real key privacy:
Wording:
PSKa A's primary signing key (long term key)
PEKa A's primary encryption key (long term key)
SSKab sub signing key for conversations between A and his contact B
SEKa A's sub encryption key
Enc(key,m), Sig(key,m)

Each contact gets an encrypted message with a sub signing key, which is only used to sign messages to him and a sub encryption key in a short interval (e.g every month):

1. A ---Sig(SSKab_priv_old,Enc(SEKb_pub,Sig(PSKa_priv,SSKab_pub_new||SEKa_pub_new)))--> B
2. A ---Sig(SSKac_priv_old,Enc(SEKc_pub,Sig(PSKa_priv,SSKac_pub_new||SEKa_pub_new)))--> C
   That means, private and public SSKs need to be stored connected to the contact they are used for.

Messages would look like this:
3) A ---Sig(SSKab_priv,Enc(SEKb_pub,m))--> B
4) A <--Sig(SSKba_priv,Enc(SEKa_pub,m))--- B

A needs to store this:
PSKa_priv, PSKa_pub, PSKa_priv, PSKa_pub
Contacts:
B: SSKab_priv, SSKab_pub, SSKba_pub, SEKb_pub

---

Second approach with key privacy for non-contacts:

Wording:
PSKa, PEKa, SEKa, Enc, Sig like above
SSKa A's sub signing key

Each contact gets an encrypted message with a sub signing key and a sub encryption key in a short interval (e.g every month):

1. A ---Sig(SSKa_priv_old,Enc(SEKb_pub,Sig(PSKa_priv,SSKa_pub_new||SEKa_pub_new)))--> B
2. A ---Sig(SSKa_priv_old,Enc(SEKc_pub,Sig(PSKa_priv,SSKa_pub_new||SEKa_pub_new)))--> C
   That means, only public SSKs from contacts need to be stored connected to it, like SEKs are.

Messages would look like this:
3) A ---Sig(SSKa_priv,Enc(SEKb_pub,m))--> B
4) A <--Sig(SSKb_priv,Enc(SEKa_pub,m))--- B

A needs to store this:
PSKa_priv, PSKa_pub, PSKa_priv, PSKa_pub, SSKa_priv, SSKa_pub
Contacts:
B: SSKb_pub, SEKb_pub

That would lead to forward secrecy and key privacy (for all/for non-contacts) after every renewal interval.

I know we don't want to reinvent every wheel but that is only an idea.

In my view this decision should be made until beta, because as @schulze mentioned no contact is anonymous with our recent concept.

[schulze]

I know we don't want to reinvent every wheel but that is only an idea.

I would prefer that we follow some existing protocol instead of trying to do our own stuff.
The best option I see at the moment would be to use Trevor Perrin's noise protocol https://github.com/trevp/noise/wiki. This is a simple but state-of-the-art design that a number of knowledgeable people have looked at already.

Especially his boxes provide all the properties we need: https://github.com/trevp/noise/wiki/Noise-properties-and-protocol-comparisons#box-properties.

The key privacy problems are killed just by switching from RSA to using ECC (as e.g. in the noise design).

[roeslpa]

I'm in favour of ECC and the noise protocol is an easy solution for key privacy but we would lose the possibility to sign..
It's often not needed, but might be useful sometimes.

[roeslpa]

Can be closed when noise is merged and used for drop messages.

[schulze]

This is now Qabel/qabel-core/issues/290 in the qabel-core repository.