User/Device invitation protocol v2

In line with #997 #1011, here is a draft of the new invitation protocol:

Invitee (Alice)              Inviter (Bob)

--- Diffie-Hellman key exchange ---

Generate key Ask/Apk
Apk -->

                             Generate key Bsk/Bpk
                             Compute s = f(Bsk, Apk)
                             <-- Bpk

Compute s = f(Ask, Bpk)

--- Shared key verification ---

Generate 32bits nonce An
hAn = hmac(s, An)
hAn -->
                            TODO: useful to send hBn == hmac(s, Bn) ???
                            Generate 32bits nonce Bn
                            <-- Bn

An -->
                            Verifies hAn == hmac(s, An)
                            Computes Bsas = hmac(s, An | Bn)[:20b]
                              (first 20bits of the hmac)
                            Transmit Bsas as 7 digit number by out of band canal

Receive Bsas
Verifies Bsas == hmac(s, An | Bn)[:20b]
*** Invitee knows canal is secure ***
*Invitee ready* -->

Compute Asas = hmac(s, An | Bn)[20b:40b]
  (bits ]20, 40] of the hmac)
Transmit Asas as 7 digit
  number by out of band canal

                            Receive Asas
                            Verifies Asas == hmac(s, An | Bn)[20b:40b]
                            *** Inviter knows canal is secure ***
                            <-- *Inviter ready*

--- Actual client or device inviation ---

User/Device pub key -->
 (Device pub key in case of Device invitation)

                           Create User certificate & send it to backend
                           <-- root public key
                              (+ user private key in case of Device invitation)

Few key points:

It is heavily based on https://tools.ietf.org/id/draft-ietf-dnssd-pairing-03.html

There is only one nonce-hash passed from invitee to inviter (hAn). This is to follow what is done in the IETF draft. However I think we should investigate better the lack of need for a inviter to invitee nonce-hash.

Unlike the current protocol, there is 2 token to pass (inviter send to invitee, then invitee send to inviter)

Though the token could be replace by a visual comparison between invitee and inviter, it's much safer to force them to provide each other a different code so they cannot "just click ok and go on"

The 2 tokens are each 20 bits long, so we end up with 5bytes of data. This is pretty big (~10¹² possibilities) but oblige to pass two 7 digits numbers. We could use 4 digits numbers instead (12bits tokens) and still have 16 millions possibilities (still much higher than 1 million possiblities of the single 7 digit token used in the IETF draft).

In theory 4 digits numbers provides 13bits (8096 possibilities), however the blake2b hash that we will most likely use can output hash with a size between 1 and 64 bytes. Using two 12bits tokens allow us to use a hash size of 3 bytes, were 13bits tokens would consume only 26bits out of the 32bits of a 4bytes hash... In theory this wouldn't be an issue, but I would prefer hard evidence before mangling cryptographic output.

There is only one nonce-hash passed from invitee to inviter (hAn). This is to follow what is done in the IETF draft. However I think we should investigate better the lack of need for a inviter to invitee nonce-hash.

I've seen the same thing in a TLS-SAS memo: https://tools.ietf.org/html/draft-miers-tls-sas-00#section-3 In this draft, hAn is described as a "commitment" so that sounds ok to me.

In theory 4 digits numbers provides 13bits (8096 possibilities), however the blake2b hash that we will most likely use can output hash with a size between 1 and 64 bytes. Using two 12bits tokens allow us to use a hash size of 3 bytes, were 13bits tokens would consume only 26bits out of the 32bits of a 4bytes hash... In theory this wouldn't be an issue, but I would prefer hard evidence before mangling cryptographic output.

I don't see what's the problem with generating a larger hash (i.e 8 bytes or so) and then have the protocol only check the n first bits of the hash (this way you can easily change the strength of the check without modifying the hashing operations).

Also, I think we're more interested in the size in digits rather than bits, since this is what the user has to transmit. Here's a table summing up this info:

n-digits	n-bits	2**n-bits
2	6	64
3	9	512
4	13	8 192
5	16	65 536
6	19	524 288
7	23	8 388 608

Last, I wonder how high the hash size really needs to be. As far as I understand, the attacker can't do much but hoping for a hash collision. How realistic is it to imagine an attack that succeeds once in 500_000 times, but prevent the system to work correctly the rest of the time?

@stefan-contiu I'd be curious to hear your opinion on this topic :)

Unlike the current protocol, there is 2 token to pass (inviter send to invitee, then invitee send to inviter) Though the token could be replace by a visual comparison between invitee and inviter, it's much safer to force them to provide each other a different code so they cannot "just click ok and go on"

I'd like more investigation on this. I think it would be a mistake to start exchanging more tokens simply because it feels safer.

For instance, in the your following computation you add up the 20 bits of both tokens to compute 2**40 ~= 10**12 possibilities. But as far as I understand you can't just add up the bits like that: the first token might collide despite a MITM-attack but not the second one. If the users do not send a confirmation back to each others, there is still a one in 10**6 chance for the invited user to successfully join an organization controlled by the attacker, and one in 10**6 chance for the inviting user to successfully invite the attacker into the system. Not that any of this is necessarily problematic, but simply to point out that the strength of the tokens cannot be added together.

That being said, great work :) I'm looking forward to seeing this implemented!

Unlike the current protocol, there is 2 token to pass (inviter send to invitee, then invitee send to inviter)

More info about this particular point, following up after a call with @touilleMan.

The SAS protocol doesn't require 2 tokens. Theoretically, it's only required for Alice and Bob to make sure that they share the same token. The question then is how do we make sure that the users correctly check, both ways, that the tokens are identical. 3 possible solutions are listed below.

Solution 1: Two tokens, exchanged sequentially

This is the original solution proposed in this issue:

Alice is prompted with a first token
Alice communicates the token to Bob
Bob validates the token, and is prompted with all the info related to the current invitation
Bob validates the information and is prompted with a new token
Bob communicates the second token to Alice
Alice validates the second token and gets logged in if done successfully

Pros:

Guided, sequential
The validation going both ways is enforced
The risk of a true MITM-attack (as opposed to a one-way attack) is greatly reduced since the attacker would have to hit two hash collisions.

Cons:

Extra information exchange is required, the procedure is longer
Increase the chance to get one of the token wrong

Solution 2 - Single long token

An extra secret could be used to validate the procedure:

Alice is prompted with a token in two parts (say 6 then 6 digits)
Alice communicate the token to Bob
Bob is prompted with all the information regarding the current invitation
Bob validates the invitation by entering the full token
- The first part of the token is the SAS that validates the channel on Bob's side
- The second part of the token is the secret sent through the channel to Alice
- Alice's parsec client receives and check the secret, validating the channel on Alice's side
Bob and Alice are both prompted with message indicating a successful invitation

Pros:

Few user steps are required
Alice could simply text the token to Bob, et get back later when the procedure is over (given Alice's parsec client keeps running)

Cons:

An attacker that has read access to the information in the secondary channel could still perform a MITM attack
The strength of protection is only half the token as guessing the SAS is enough to perform a MITM attack

Solution 3 - Single token with user validation

Another solution is to make sure that Alice acknowledge a confirmation from Bob that the invitation has been validated

Alice is displayed with a first token
Alice communicates the token to Bob
Bob validates the token, and is prompted with all the info related to the current invitation
Bob validates the information and is prompted with the instruction to confirm the invitation
Bob confirms the invitation to Alice
Alice acknowledge having received the confirmation from Bob and gets logged in

Pros:

A single, short token is required to be exchanged, plus the confirmation

Cons:

It's unclear how we can make sure that Alice waits for the actual confirmation before acknowledging it with the parsec client

Implémentation POC

from enum import Enum
import nacl.encoding
import nacl.utils
from nacl.public import PrivateKey
from nacl.hash import blake2b
from nacl.bindings import crypto_scalarmult

# Parsec user/device invite protocol v2
#
# Based on https://tools.ietf.org/id/draft-ietf-dnssd-pairing-03.html
#
# Invitee (Alice)              Inviter (Bob)
#
# --- Diffie-Hellman key exchange ---
#
# Generate key Ask/Apk
# Apk -->
#
#                              Generate key Bsk/Bpk
#                              Compute s = f(Bsk, Apk)
#                              <-- Bpk
#
# Compute s = f(Ask, Bpk)
#
# --- Shared key verification ---
#
# Generate 32bits nonce An
# hAn = hmac(s, An)
# hAn -->
#                             TODO: useful to send hB == hmac(s, Bn) ???
#                             Generate 32bits nonce Bn
#                             <-- Bn
#
# An -->
#                             Verifies hAn == hmac(s, An)
#                             Computes Bsas = hmac(s, An | Bn)[:20b]
#                               (first 20bits of the hmac)
#                             Transmit Bsas as 7 digit number by out of band canal
#
# Receive Bsas
# Verifies Bsas == hmac(s, An | Bn)[:20b]
# *** Invitee knows canal is secure ***
# *Invitee ready* -->
#
# Compute Asas = hmac(s, An | Bn)[20b:40b]
#   (bits ]20, 40] of the hmac)
# Transmit Asas as 7 digit
#   number by out of band canal
#
#                             Receive Asas
#                             Verifies Asas == hmac(s, An | Bn)[20b:40b]
#                             *** Inviter knows canal is secure ***
#                             <-- *Inviter ready*
#
# --- Actual client or device inviation ---
#
# User/Device pub key -->
#  (Device pub key in case of Device invitation)
#
#                            Create User certificate & send it to backend
#                            <-- root public key
#                               (+ user private key in case of Device invitation)

def generate_client_sas(src):
    # Big endian number extracted from bits [0, 20[
    return (
        src[0] << 12 |
        src[1] << 4 |
        src[2] >> 4
    )

def generate_server_sas(src):
    # Big endian number extracted from bits [20, 40[
    return (
        (src[2] & 0xF) << 16 |
        src[3] << 8 |
        src[4]
    )

def client_operations():
    client_private_key = PrivateKey.generate()

    # 1) Send client pubkey & 2) receive server pubkey
    server_public_key = yield client_private_key.public_key

    shared_secret_key = crypto_scalarmult(client_private_key.encode(), server_public_key.encode())
    print('shared_secret_key:', shared_secret_key)

    # 3) Send shared_secret_key's HMAC & 4) Receive server nonce
    client_nonce = nacl.utils.random(size=32)
    shared_secret_key_hmac_with_client_nonce = blake2b(
        client_nonce, key=shared_secret_key
    )
    server_nonce = yield shared_secret_key_hmac_with_client_nonce
    assert len(server_nonce) == 32

    # Computes combined HMAC
    combined_nonce = client_nonce + server_nonce
    # Digest size of 5 bytes so we can split it beween two 20bits SAS
    combined_hmac = blake2b(combined_nonce, digest_size=5, key=shared_secret_key, encoder=nacl.encoding.RawEncoder)

    # Compute & display the client SAS
    client_sas = generate_client_sas(combined_hmac)
    print(f'Client SAS: {client_sas:0>7}')

    # 5) Send client nonce & get back server confirmation
    server_banco = yield client_nonce
    assert server_banco

    # Retreive & check the server SAS
    server_sas = int(input('Server SAS ? '))
    assert server_sas == generate_server_sas(combined_hmac)

    # Now we can do parsec stuff ;-)

def server_operations():
    server_private_key = PrivateKey.generate()

    # Wait for client to initiate communication
    client_public_key = yield

    shared_secret_key = crypto_scalarmult(server_private_key.encode(), client_public_key.encode())

    # 2) Send server pubkey & 3) receive shared_secret_key's HMAC
    shared_secret_key_hmac_with_client_nonce = yield server_private_key.public_key

    # 4) Send server nonce & 5) receive client nonce
    server_nonce = nacl.utils.random(size=32)
    client_nonce = yield server_nonce
    assert len(client_nonce) == 32

    # Verify client_nonce against shared_secret_key_hmac_with_client_nonce
    assert shared_secret_key_hmac_with_client_nonce == blake2b(client_nonce, key=shared_secret_key)

    # Computes combined HMAC
    combined_nonce = client_nonce + server_nonce
    # Digest size of 5 bytes so we can split it beween two 20bits SAS
    combined_hmac = blake2b(combined_nonce, digest_size=5, key=shared_secret_key, encoder=nacl.encoding.RawEncoder)
    print('combined_hmac:', len(combined_hmac), combined_hmac.hex())

    # Retreive & check the client SAS
    client_sas = int(input('Client SAS ? '))
    assert client_sas == generate_client_sas(combined_hmac)

    # Compute & display the server SAS
    server_sas = generate_server_sas(combined_hmac)
    print(f'Server SAS: {server_sas:0>7}')

    # Send banco, wait for client banco
    client_banco = yield True
    assert client_banco

    # Now we can do parsec stuff ;-)

def main():
    client = client_operations()
    server = server_operations()

    server_frame = None
    client_frame = None

    server.send(None)  # Wait for client to initiate communication
    while True:
        try:
            client_frame = client.send(server_frame)
            server_frame = server.send(client_frame)
        except StopIteration:
            break

if __name__ == '__main__':
    main()

Implemented in #1115

Scille / parsec-cloud