Man In The Middle

Our research paper, presented at MobiCom '13, provides a technical analysis of SafeSlinger's key exchange properties. Some highlights from our paper are outlined here. All exchanged data is encrypted using AES in CBC mode with PKCS#7 padding. Identity data integrity is achieved through verification of the initial commitment, hence, no additional Message Authentication Code (MAC) is needed. We use SHA-3 since previous hash algorithms, such as MD5 and SHA-1, have been successfully attacked in either theoretical or practical aspects. For clarity we separate our protocol into its multi-commitment tree setup and two rounds of verification.

Multi-Commitment Generation

The user selects which data to share, usually a public key, and enters the total number of protocol participants. The device computes the values needed for the group DH protocol by randomly generating the 1536-bit DH private key. The device also randomly selects 256-bit nonces to indicate a “match” and a “wrong” match. The device then encrypts the data to share with the match nonce used as a symmetric encryption key, using AES with 256-bit keys. We compute several branches of these elements using 256-bit SHA-3 as our hash function, finally deriving the final hash used as the initial commitment the device sends to to the server. Our paper depicts this multi-value commitment structure for each user in more detail.

Authenticity Verification Round

The server now distributes commitment values to all group members. Once a device receives all commitments, it opens up the first level decommitment, shared through the server. Decommitments are a set of values for each device: the match nonce-encrypted data, DH half-key, and a hash of the potential nonce choices. If validation of all decommitments is correct, devices compute a hash over all decommitments. Each device then computes a 3-word phrase that represents 24 bits of the hashed group's decommitments using the PGP Word List. The device also produces two decoy 3-word phrases, the rational for which guards against careless comparisions. If no phrase matches on another device, the user selects “No Match”, causing their device to send the “wrong” nonce (along with a paired hash of the match nonce to enable verification) to the server for distribution among all devices. This case is also triggered if the user selects one of the decoy word phrases or cancels the protocol. This approach cryptographically authenticates the “no match” message based on the commitment and thus prevents injection of an abort message by an adversary. If users correctly selected the matching word phrase, their device reveals the opposite pair of values including a hash of the "match" nonce indicating success, which the server distributes. Each device can verify that all users selected the correct word phrase.

Secret Sharing Round

After the data shared has been authenticated by each user, the devices proceed to construct a group DH tree. The group DH protocol is intricate, and we use the symmetric tree group DH key agreement STR, which is most efficient for our network use. Once the secret group key is established, the devices then proceed to send their match nonce, which also serves as the decryption key for their data, to the group encrypted under the secret group key. Each device decrypts each received match nonce from the other devices, verifies its integrity using the initial commitments, and finally uses each match nonce to decrypt and obtain each device’s data.