Services/Sync/P2P Key Exchange And Rotation

Support secure and intuitive key exchange and key rotation between Weave Sync clients.

Over a number of versions of Weave Sync different key exchange mechanisms have been implemented, however to date they have had significant weaknesses in either security or user experience (UX) or both. This wiki describes (yet another) proposal which attempts to find the balance between (good enough) security and an intuitive UX.

Overview

The objective of the P2P Key Exchange protocol is to securely transfer a secret key to a new weave client during registration. Importantly, as such it is only relevant for Weave Sync versions which utilise a randomly generated secret key, namely Weave Sync v1.1 API/v5 Data and the pairing extension of Weave Sync v1.5 API/v5 Data.

Arguable the J-PAKE based key exchange protocol used in Weave Sync v1.1/v5 already achieves this, however as discussed below a significant weakness is that it requires three round trips to complete and thus requires both the new and an already registered client to be online concurrently and with good connectivity. Also Weave Sync v1.1/v5, as currently implemented, does not support rotation of the secret key.

The P2P Key Exchange Protocol aims to address these issues by implementing a 3DHE based key exchange protocol with pre-generated ephemeral keys, allowing the key exchange to be completed asynchronously and in a single round trip. The same technique can also be leveraged for key rotation, although in this case only a single message needs to be sent by the initiating client, a response is not required but can be used to indicate success. The key exchange is also implemented within Weave Sync storage meaning no changes are required to the Weave Sync registration API to implement.

The P2P Key Exchange protocol is inspired by TextSecure.

'Pros'

• User only needs to know username and password to register device
• Secret key is randomly generated
• Secret key does not leave device
• Key exchange is implemented using Weave Sync storage and thus is compatible with both Weave Sync v1.1/v5 and the Weave Sync v1.5/v5 pairing extension

'Cons'

• Registering additional devices after the first requires access to an already registered device
• Performing key exchange within Weave Sync storage may have security ramifications.

Existing Weave Sync Key Exchange Implementations

Passphrase (v1.1 API/v3 Data)

The Passphrase implementation derives a secret key from a user selected passphrase independent of the account password.

'Pros'

• Registering additional devices does not require access to an already registered device
• Secret key does not leave device

'Cons'

• User needs to know passphrase in addition to username and password to register device
• Secret key is only as secure as passphrase

Easy Setup (v1.1 API/v5 Data)

The Easy Setup implementation generates a secret key on account registration and for additional clients performs key exchange using J-PAKE.

'Pros'

• User only needs to know username and password to register device
• Secret key is randomly generated
• Secret key does not leave device

'Cons'

• Registering additional devices after the first requires access to an already registered device
• J-PAKE key exchange requires three round trips and hence both devices must be connected concurrently and with good connectivity

One Password (v1.5 API/v5 Data)

Like the Passphrase implementation, the One Password (onepw) implementation derives a secret key from a user selected passphrase, however a single password/passphrase is used for both authentication and key derivation to address useability issues with maintaining independent passwords/passphrases.

'Pros'

• User only needs to know username and password to register device
• Registering additional devices does not require access to an already registered device

'Cons'

• Secret key is derived from password which is partially known by authentication server
• Secret key is only as secure as password
• Registration and authentication protocol significantly more complex

Design

User Stories

• Information is secure: As a user I want my data to be secure, hence the secret key must be secure
• Easy to register: As a user I want to be able to register a new device with only the username and password
• Easy to change key: As a user I want to be able to change the secret key and de-register a device in the case that it has become compromised, i.e. device lost or stolen

Desired Behaviour

1) Register a device using only username and password

2) If verification is required this must be no more than one additional step and involve no more than one additional device

3) A registered device can change the sync key and re-distribute it to other selected devices with minimal actions, i.e. see (2) above.

Implementation

Note for the purposes of describing the technical implementation the term client will be used in place of device and similarly authorised/unauthorised will be used in place of registered/unregistered.

What Needs To Be Done

• Implement messaging protocol to support sending of messages between both authorised (registered) and unauthorised (unregistered) clients (devices)
• Implement registration protocol to authorise a new client (device) and exchange the master key for an existing Weave Sync account
• Implement key rotation protocol to change the master key and re-distribute to other authorised (registered) clients (devices)

eXfio Peer v1

Messaging Protocol

Version 1 of the eXfio Peer protocol leverages 3DHE key exchange. A bonus of using 3DHE is that it naturally abstracts in to a generalised messaging protocol that can be used to send an arbitrary messages encrypted with the session key derived during the 3DHE key exchange. In addition perfect forward secrecy can be achieved using axolotl key ratcheting as used in the Text Secure application. Although this is not implemented at this stage it presents an opportunity to extend functionality to include peer to peer key management that can be shared between multiple devices.

Protocol Sequence

0. Each client publishes an identity key (AIp, BIp) and a set of ephemeral keys (AE{1..n}p, BE{1..n}p)
1. Client A generates a new ephemeral key (AEp) and randomly selects one of Client B's ephemeral keys (BEp). Using 3DHE and a KDF, client A generates the shared secret (SK) then sends message including own ephemeral key (AE) and an identifier for Client B's ephemeral key (BEp). Client B can now also generate the shared secret (SK) and hence the message body can be encrypted immediately.

Both Client A and Client B can now continue to communicate using the shared secret (SK) as a session key.

           Alice (Client A)                       Eve (Public)     Bob (Client B)

t0         AIs                                    AIp, BIp         BIs
                                                  BE{1..n}p        BE{1..n}s

t1         AIs                                    AIp, BIp         BIs
           AEs                                    AEp, BEp         BEs
           SK = KDF(3DHE(AIs, AEs, BIp, BEp))                      SK = KDF(3DHE(BIs, BEs, AIp, AEp))
           PT = <message>                                          CT
           CT = ENCRYPT(PT, SK)                                    PT = DECRYPT(CT, SK)
                                                                   

EphemeralKey JSON

{
  keyid:     "id of ephemeral key",
  key:       "ephemeral public key"
}

Client JSON

{
  version:   "version of client record",
  clientid:  "id of client",
  name:      "name of client",
  key:       "identity public key",
  ekeys:     [EphemeralKey1, EphemeralKey2, ..., EphemeralKeyn],
  status:    "indicates if client is authorised, i.e. 'authorised' or 'pending'",
  authlevel: "will this client accept messages from unauthorised clients, 
             i.e. 'all' indicates all clients, 'authorised' indicates authorised clients only"
  hmac:      "HMAC of all other client fields"
}

Message JSON

{
  version:      "version of message record",
  srcclientid:  "id of sender",
  srckeyid:     "id of sender's ephemeral key",
  srckey:       "sender's ephemeral key (optional after first message, i.e. sequence > 1)",
  dstclientid:  "id of receiver",
  srckeyid:     "id of receiver's ephemeral key",
  sequence:     "sequence of this message in session",
  type:         "message type",
  content:      "message content"
  hmac:         "HMAC of all other message fields"
}

Registration Protocol

IMPORTANT: If the attacker has full access to the storage, i.e. a hostile systems administrator, and knows the password a man-in-the-middle (MITM) attack is possible. At this time there is an implicit (and quite possibly incorrect) assumption that the systems administrator does not know the password. See version 2 of protocol for improved handling of this risk.

When Alice registers a new device with the Weave Sync server the client first checks if there are other authorised clients, if not it initialises the storage, if so it requests authorisation by following the procedure below.

0. Client A: Authenticate to sync server and create client record with status of 'pending'
1. Client A: Send ClientAuthRequestMessage to existing authorised clients, i.e. Client B, including authcode digest (AD)
2. Out-of-Band: Client A displays authcode (AC) and user enters it on Client B
3. Client B: If authcode (AC) is verified send ClientAuthResponseMessage with sync key

Finally Alice is notified of registration status and if successful client record is updated with status of 'approved'.

           Alice (Client A)                       Eve (Public)     Bob (Client B)

t0         AIs                                    AIp, BIp         BIs, MK
                                                  BEp              BEs

t1         AIs                                    AIp, BIp         BIs, MK
           AEs                                    AEp, BEp         BEs
           SK = KDF(3DHE(AIs, AEs, BIp, BEp))                      SK = KDF(3DHE(BIs, BEs, AIp, AEp))
           VC = RANDOM()                                           VD
           VD = DIGEST(VC + DIGEST(password))

t2         AIs                                    AIp, BIp         BIs, MK
(OoB)      VC                                                      VCui = <user input>
           VD                                                      VD
                                                                   Verified = (VD == DIGEST(VCui + DIGEST(password)))

t3         AIs, MK                                AIp, BIp         BIs, MK

Notes:

• The authcode is a random alphanumeric string which needs to be entered on the authorising device to verify the authenticity of the request. If the authcode is entered correctly then a man-in-the-middle attack is highly unlikely.

ClientAuthVerifier JSON

{
  innersalt:  "Salt value for inner hash, i.e. hash(password)
  salt:       "Salt value for outer hash
  digest:     "hash(authcode + hash(password))
}

ClientAuthRequestMessage JSON

{
  clientid:  "id of client",
  name:      "name of client",
  auth:      ClientAuthVerifier
}

ClientAuthResponseMessage JSON

{
  clientid:  "id of client",
  name:      "name of client",
  status:    "okay|fail",
  message:   "authorisation approved|authorisation rejected",
  synckey:   "Master key for Weave Sync account (required if status 'okay')"
}

Key Rotation Protocol

TODO

eXfio Peer v2

Version 2 of the eXfio Peer protocol improves the protection against a man in the middle (MITM) attack, at the expense of a more complex protocol requiring two round-trips. Importantly the starting assumption is that an adversary has full access to the storage and knows the password, i.e. a hostile systems administrator. Fortunately an elegant means to mitigate against this threat is to use a SCIMP style hash commitment, which results in an adversary, Eve, having to select a public key without knowing the public key of either Alice or Bob, giving Eve a single opportunity to guess a 4 character base32 authcode with a probability of 1.05 x 10^-6. Thus making it very difficult to launch a MITM attack without detection.

Messaging Protocol

Although version 2 of the eXfio Peer protocol requires two round trips it has been designed such that the user input for out-of-band verification takes place on the registered device, Client B, which can determine if the verification of Client A has been successful without exchanging additional messages between clients. However to detect a MITM adversary impersonating Client B an additional verification check is needed on the new device, Client A. Although this attack would not result in a compromise of the master key it could result in the sharing of confidential data. Thus if a user incorrectly enters the authcode Client A must assume the session is compromised or exchange additional messages between clients to give the user additional opportunities to enter the correct authcode.

Protocol Sequence

0. Each client publishes an identity key (AIp, BIp)
1. Client A: Generates a new ephemeral key (AEp) and to initiate a verified session sends a message to Client B including a digest of the key (AEd), thereby committing to a specific ephemeral key without revealing it
2. Client B: Generates a new ephemeral key (BEp) and sends a message to Client A including the key (not a digest). Both parties have now committed to a specific ephemeral key without first knowing the key of the other party
3. Client A: Sends a message to Client B including the ephemeral key (AEp)
4. Out-of-Band: Client B can now verify the session by confirming that Client A's ephemeral key (AEp) matches the digest (AEd), provided earlier, and using user input to avoid interception, i.e. out-of-band, that an authcode (VCS) derived from Client A's ephemeral key (AEp) and identity key (AIp) has the same value on Client A and Client B.
5. Client B: Derives a shared secret (SK) using 3DHE and sends an encrypted message to Client A including the status of the verification, i.e. okay|fail, and a random component of the authcode (VCRui) thus proving the response is from the registered device, i.e. Client B. If verification is successful the message can optionally include additional information such as account keys

Assuming verification is successful Client A and Client B can now communicate using the shared secret (SK) as a session key.

           Alice (Client A)                       Eve (MITM)       Bob (Client B)

t0         AIs                                    AIp, BIp         BIs                                                  

t1         AIs                                    AIp, BIp         BIs
Key        AEs                                    AEd              
Commit     AEp                                    

t2         AIs                                    AIp, BIp         BIs
           AEs                                    BEp              BEs
           AEp                                    AEd              

t3         AIs                                    AIp, BIp         BIs
Key        AEs                                    AEp, BEp         BEs
Verify

t4         AIs                                    AIp, BIp         BIs
(OoB)      AEs                                    AEd              BEs
           AEp                                                     BEp
           VCS = DIGEST(AIp, AEp)                                  VCSui = <user input>
           VCR = RANDOM()                                          VCRui = <user input>
                                                                   Verified = (VCSui == DIGEST(AIp, AEp) + AEd == DIGEST(AEp))

t5         AIs                                    AIp, BIp         BIs
           SK = KDF(3DHE(AIs, AEs, BIp, BEp))                      SK = KDF(3DHE(BIs, BEs, AIp, AEp))
           VCR                                                     VCRui
           VCRui                                                   
           Verified = (VCRui == VCR)                               

Notes:

• The authcode (VCS + VCR) is a digest of Client A's identity key and ephemeral key and a random value respectively. This code must be entered on a registered device to verify the user is in possession of the device requesting authorisation. If the authcode displayed by Client A matches the VCS value generated on Client B and if Client A's hash commit matches the digest of Client A's public key then a man-in-the-middle attack impersonating Client A is highly unlikely. Finally if the VCRui value returned to Client A matches the original VCR random value then a man-in-the-middle attack impersonating Client B is highly unlikely.
• To minimise errors during user input the authcode can be represented using a word list, i.e. PGP, Diceware, S/KEY or optionally scanned using a QR code.
• By including Client A's identity key in the authcode provides the additional benefit of verifying both keys

Client JSON (compatible with v1 protocol)

{
  version:   "version of client record",
  clientid:  "id of client",
  name:      "name of client",
  key:       "identity public key",
  ekeys:     [EphemeralKey1, EphemeralKey2, ..., EphemeralKeyn],
  status:    "indicates if client is authorised, i.e. 'authorised' or 'pending'",
  authlevel: "will this client accept messages from unauthorised clients, 
             i.e. 'all' indicates all clients, 'authorised' indicates authorised clients only"
  hmac:      "HMAC of all other client fields"
}

Message JSON (compatible with v1 protocol)

{
  version:      "version of message record, i.e. 1|v1",
  srcclientid:  "id of sender",
  srckeyid:     "id of sender's ephemeral key",
  srckey:       "sender's ephemeral key (optional after first message, i.e. sequence > 1)",
  dstclientid:  "id of receiver",
  dstkeyid:     "id of receiver's ephemeral key",
  sequence:     "sequence of this message in session",
  type:         "message type",
  content:      "message content"
  hmac:         "HMAC of all other message fields"
}

Verified Session Message JSON

{
  version:      "version of message record, i.e. v2verified",
  srcclientid:  "id of sender",
  dstclientid:  "id of receiver",
  sessionid:    "id of session",
  sequence:     "sequence of this message in session",
  cipher:       "encryption type, i.e. none|3dhe"
  type:         "message type",
  content:      "message content"
  hmac:         "HMAC of all other message fields"
}

SessionKeyCommitRequestMessage

{
  clientid:     "id of client",
  name:         "name of client",
  keydigest:    "digest of sender's ephemeral key",
  getkeys:      "when true and session verified account keys will be included in SessionKeyVerifyResponseMessage, optional. See Registration protocol"
}

SessionKeyCommitResponseMessage JSON

{
  clientid:  "id of client",
  name:      "name of client",
  key:       "receivers ephemeral key",
}

SessionVerifier JSON

{
  authcode:  "Random component of authcode entered by user, i.e. VCRui"
}

SessionKeyVerifyRequestMessage JSON

{
  clientid:  "id of client",
  name:      "name of client",
  key:       "senders ephemeral key",
}

SessionKeyVerifyResponseMessage JSON

{
  clientid:    "id of client",
  name:        "name of client",
  status:      "okay|fail",
  message:     "ephemeral key okay|ephemeral key mismatch",
  auth:        SessionVerifier (if status okay),
  payload:     Optional. See Registration protocol,
}

SessionCloseRequestMessage JSON

{
  clientid:  "id of client",
  name:      "name of client”,
  status:    "verified|failed",
  message:   "session verification okay|session verification failed",
}

SessionCloseResponseMessage JSON

{
  clientid:  "id of client",
  name:      "name of client”,
  status:    "verified|failed",
  message:   "session verification okay|session verification failed",
}

Registration Protocol

The objective of the registration protocol is for a user, i.e. Alice, to authorise a new device and transfer to it the master key (sync key) thus allowing it to read and write encrypted data to and from the storage. To maintain the security of the master key the protocol must defend against a man-in-the-middle (MITM) attack from an adversary. Importantly for version 2 of the eXfio Peer protocol the starting assumption is that an adversary has full access to the storage and knows the password, i.e. a hostile systems administrator.

When a user registers a new device with the Weave Sync server the client first checks if any devices have already been registered. If there are no registered devices it generates a master key (MK) and initialises the storage. If there are existing registered devices it requests authorisation by following the procedure below. A key difference from the messaging protocol is that to improve user experience we want to avoid the user having to wait for messages to be exchanged, thus the out-of-band step is brought forward as early as possible and is able to take place immediately after Client A has sent the SesssionKeyCommitRequestMessage although it cannot be completed until Client B has received the message, hence good connectivity is required on both Client A and Client B, but not necessarily simultaneously.

Note: When the new device is mobile a QR code could be used for the out-of-band verification, which would remove the need for user input and mitigate against the impersonation of Client A and Client B.

0. Client A: Authenticate to sync server and create client record with status of 'pending'
1. Client A: Send SessionKeyCommitRequestMessage to existing device, Client B, including digest of ephemeral key (AEd) and with a getkeys value of 'true'
2. Out-of-Band: User sights authcode displayed on Client A, generated from identity and key ephemeral key and random value, and enters it on Client B
3. Client B: Send SessionKeyCommitResponseMessage to new device, Client A, providing an ephemeral key (BEp)
4. Client A: Send SessionKeyVerifyRequestMessage to Client B including ephemeral key (AEp)
5. Client B: Send SessionKeyVerifyResponseMessage to Client A encrypted with a session key derived from the shared secret (SK) and including a status indicating if the identity and ephemeral key component (VCS) of authcode have been verified. If verification is successful include the AccountKeys payload, i.e. master key (MK)

Finally the user is notified of the registration status and if successful client record is updated with status of 'approved'

           Alice (Client A)                       Eve (MITM)       Bob (Client B)

t0         AIs                                    AIp, BIp         BIs, MK                                                    

t1         AIs                                    AIp, BIp         BIs, MK
Key        AEs                                    AEd              
Commit     AEp                                    

t2         AIs                                    AIp, BIp         BIs, MK
(OoB)      AEs                                    AEd              BEs
           AEp                                                     BEp
           VCS = DIGEST(AIp, AEp)                                  VCSui = <user input>
           VCR = RANDOM()                                          VCRui = <user input>

t3         AIs                                    AIp, BIp         BIs, MK
           AEs                                    BEp              BEs
           AEp                                    AEd              VCSui     
           VCS                                                     VCRui                     

t4         AIs                                    AIp, BIp         BIs, MK
Key        AEs                                    AEp, BEp         BEs
Verify     VCS                                                     VCSui
           VCR                                                     VCRui
                                                                   Verified = (VCSui == DIGEST(AIp, AEp) + AEd == DIGEST(AEp))

t5         AIs, MK                                AIp, BIp         BIs, MK
           SK = KDF(3DHE(AIs, AEs, BIp, BEp))                      SK = KDF(3DHE(BIs, BEs, AIp, AEp))
           VCR                                                     VCRui
           VCRui                                                   
           Verified = (VCRui == VCR)                               

Notes:

• A QR code including Client A's entire key (AEp) would allow step 2, 3 and 4 to be collapsed into a single step. See Signal (TextSecure) Registration Protocol below.

AccountKeys JSON

{
  masterkey:  "time used as input in to verification"
}

Key Rotation Protocol

TODO

Vulnerabilities

On deeper inspection of eXfio Peer v2 there are two vectors of attack that present themselves, a honeypot and a targeted phishing attack.

Honeypot

An adversary could set up a sync server and invite users to join, with say an offer of unlimited stage. When the user creates an account the hostile sync server initialises the storage with a fictitious authorised device, thus giving the impression that the user had previously registered with the service. The user could be presented with an authcode to enter on their device this transferring a pre-generated master key, known by the server, to the newly registered device.

Countermeasures

TODO

Targeted Phishing

Similar to a honeypot, but targeted at a user that has already registered one or more devices, an adversary with control of the sync server could request the user to authorise the registration of a fictitious device, i.e. with a similar name to a device familiar to the user. If the user then enters the authcode as requested, i.e. into a web page, the master key will be transferred to the fictitious device.

Countermeasures

TODO

Other Key Exchange Protocols

SCIMP Messaging Protocol

           Alice (Client A)                       Eve (Public)     Bob (Client B)

t1         AEs                                    AEd              
           AEp

t2         AEs                                    AEd              BEs
           AEp                                    BEp              

t3         AEs                                    AEd              BEs
                                                  AEp, BEp         Verified = (AEd = DIGEST(AEp))

t4         AEs                                    AEd              BEs
           SK = ECDH(BEp, AEp, AEs)               AEp, BEp         SK = ECDH(AEp, BEp, BEs)

t5         SK                                                      SK
(OoB)      VC = DIGEST(SK)                                         VC = DIGEST(SK)
           VCui = <user input>                                     VCui = <user input>
           Verified = (VCui == VC)                                 Verified = (VCui == VC) 

Signal (TextSecure) Registration Protocol

           Alice (Client A)                       Eve (Public)     Bob (Client B)
t0                                                AUID, BUID       BIs, MK
                                                  BIp

t1         AIs                                    AUID, BUID       BIs, MK
(OoB)      AIp                                    BIp              AIp = <user input>

t2         AIs, MK                                AUID, BUID       BIs, MK
                                                  AIp, BIp