Session-less forward secrecy and cryptographic deniability using Triple Diffie-Hellman

[viralpoetry]

I would like to start a discussion how to change (or extend) current encryption protocol so we can use short therm ephemeral keys. This leads to a better security in an event of the long term key compromise.

I propose, that we can create new pubkey object version which will contain long term key bundled with the short term session key, and publish this object to the network more frequently. Everyone can then create ephemeral key and compose a message based on the information already available on the network. The only requirements is, that the recipient must cache private parts for some time.

My textbook example using BM pyelliptic:

import hashlib
import pyelliptic

'''
Bob's identity key IKB
Bob's signed prekey SPKB
Bob's prekey signature Sig(IKB, Encode(SPKB))
'''

# This should be in the Pubkey message broadcasted by Bob
IKB = pyelliptic.ECC(curve='sect571r1')  # Bob's identity key
SPKB = pyelliptic.ECC(curve='sect571r1') # Bob's signed prekey
SigSPKB =  IKB.sign(SPKB.get_pubkey())  # prekey signature

# Alice keys
# Alice verifies the prekey signature and aborts the protocol if verification fails.
# Alice then generates an ephemeral key pair with public key EKA.
IKA = pyelliptic.ECC(curve='sect571r1') # Alice's identity key
EKA = pyelliptic.ECC(curve='sect571r1') # Alice's ephemeral key

'''
Alice compute shared secret SK (with mutual authentification, as a result of IKA, IKB usage):
DH1 = DH(IKA, SPKB)
DH2 = DH(EKA, IKB)
DH3 = DH(EKA, SPKB)
SK = KDF(DH1 || DH2 || DH3)
'''

DHA1 = IKA.get_ecdh_key(SPKB.get_pubkey())
DHA2 = EKA.get_ecdh_key(IKB.get_pubkey())
DHA3 = EKA.get_ecdh_key(SPKB.get_pubkey())
SKA = hashlib.sha256(DHA1 + DHA2 + DHA3)
print 'Alice has:',  SKA.hexdigest()

# Bob compute
DHB1 = SPKB.get_ecdh_key(IKA.get_pubkey())
DHB2 = IKB.get_ecdh_key(EKA.get_pubkey())
DHB3 = SPKB.get_ecdh_key(EKA.get_pubkey())
SKB = hashlib.sha256(DHB1 + DHB2 + DHB3)
print 'Bob has:',  SKB.hexdigest()

# use SKA( == SKB) key as usual

For more info on this protocol, check https://whispersystems.org/docs/specifications/x3dh/

Bitmessage is by nature async protocol, so we should use this kind of construction instead of session based, like proposed in https://www.reddit.com/r/bitmessage/comments/3zzevp/forward_secrecy_for_bitmessage/ and https://bitmessage.org/forum/index.php/topic,2981.0.html
(which are also interesting!)

This will solve the issues #563 #454
If somebody wants to test this, we should start collecting dependencies.

[PeterSurda]

Since mirrorwish's post, I read more about how this is addressed, for example the double ratchet algorithm or puncturable encryption. I would like to use something like that.

[viralpoetry]

My proposed key exchange is actually derived from one used by the Signal protocol. I was thinking whether it's not better to use session-less version where we do offline key exchange "trick". Thus every message is standalone with new key, we do not have to ratchet the symmetric keya as in the instant messaging protocols.

Looking forward to see other implementation.

[stman]

Hello.

My two cents in this important discussion.

I think it is essential to restore the most important original (initial) BitMessage specification characteristics :

• BitMessage shall stay a pure P2P broadcasting network with NO ROUTING. This is absolutely mandatory in order to allow Anonymity at sending and receiving messages, so that no passive eavesdropping on telecommunication networks could allow to discover who is sending messages to who. It is not the only thing to do in order to have Anonymity both at sending and receiving messages, but it is one of the main ingredients to have.

• In order to do what I said earlier, it is absolutely mandatory to stick, with no exception, to the original BitMessage White paper specifications saying that NO META DATA shall be expressed in clear text, even public encryption keys when using PKI. The whole messages must be fully ciphered, and as specified in the white paper, each client must "try to decipher" all the messages going through his node with all the private keys he has. Adding public key informations in clear text side-by-side with all the rest of the message+META DATA ciphered, definitely breaks the possibility to have anonymity at sending messages.

• Another important point I have already discussed with Peter, is that still, in order to ensure Anonymity both at sending and receiving messages is that BitMessage protocol must be corrected in order to make it a "Side & Hidden channel safe protocol". This constraint allow us to block all the identification technics based on fingerprints to work with TOR/VPN's. Doing so is absolutely mandatory too. Still, it is not enough to garantee Anonymity at sending messages.

• There is a third thing to do to remain Anonymous at sending messages : We are going to be obliged to implement something similar to what TOR does, but at the BitMessage protocol level : When posting a message to a chan, or to a user, the message shall not directly reach its target, we must implement the equivalent of the Onion strategy : When sending a message, you first do it to reach a first "random" user who's public key is already known by the sender, when the targeted user gets the message, it deciphers it, and realize that it has to relay it to another user, using the same process, etc ... Doing so at least 3 or 4 times, it finaly reaches a user who will relay the message to the final user / chan.

• What I have just said above is not very hard to build on top of what is already implemented in BitMessage : It means adding a kind of Onion Relaying functionnality in clients. We have to define how a client makes the difference between a message that was really destinated to him, from the message he has to relay to intermediate user.

This is the only way to restore Anonymity at sending messages, both to Chans, and to specific users.

Please note that in the end, it is not that much TOR that provides true Anonymity at sending message, but this internal relaying protocol. Using TOR with BitMessage is only a good way to bypass firewalls and cipher the whole trafic of a peer from an attacker that would be monitoring your personnal internet access.

I don't know if my explainations were understood, but I am okay to plan a Mumble session with both of you to explain this to you.

Restoring Anonymity at sending messages, military grade, is the most difficult thing to do. It cannot be solved with a single strategy. It need several tricks that combined, offer true Anonymity at sending messages.

Kind regards,

Stman.
BM-2cWZW87PJN5VZjtJCpk3hXcYefhNCxdjU6

[stman]

Of course, doing so makes sending those messages in "Full Anonymity Mode" much slower, because of all the added delay due to relaying, but it worth it because all known "network trafic & timing analysis based" identification technics fail.

We could make this "Full Anonymity" option "selectable" through a new button on the user interface that handles composing new messages to send.

Restoring Anonymity at sending messages, provenly, through combined tricks, is something that is going to please all users of BitMessage.

[viralpoetry]

@stman
As you said, it is important feature ("onioning" the messages) ans should be supported by default. But it is another topic.