The easiest way to do this would be to derive some kind of a hash that would be the same regardless of who of the two computed it, and impossible to compute by anybody else. In addition, we would need to identify whether two identical versions of that hash were computed by the same user or by different users.

Metamour scenario (3-party 1-stage shared key exchange)

We should somehow identify when three users form a full graph.

The easiest way to do this would be to derive some kind of a hash that would be the same regardless of who of the three computed it, and impossible to compute by anybody else.

In addition, we would need to identify whether three identical versions of that hash were computed by three different users; and this should be unforgeable.

This second part could be solved by either storing some additional hashes along the common hash; these hashes would have to be different between users and unforgeable (i.e. derived on a server side only from user's public key, and data used to obtain the common hash).

Unfortunately, it seems that there are no well-researched algorithms that would allow to derive a common hash from one private key and two public keys.

Or alternatively it could be solved by some form of secret sharing protocol without parties communicating to each other: encrypt some piece of an information with a common public key, attach a part of a common "private" key (only used for that purpose for that triple of users); every user should be able to compute a common public key and their part of a common private key; all three parts are required to decrypt a message. I am not aware of any protocols that allow to do this.

Metamour scenario (2-party key exchange)

A more realistic approach is to make every user in a triple to generate two hashes, each based on two-party shared key and the remaining user's public key.

That means six hashes total, or three unique hashes (each of them common for two users with the corresponding shared key).

A way to detect whether all six sympathies in a triple exist would be to check whether both hashes submitted by an user were already submitted by someone else.

For example, X submits a hash based on XY shared key and Z public key, and a hash based on XZ shared key and Y public key. Besides X, only Y can compute a hash based on XY shared key and Z public key; and only Z can compute a hash based on XZ shared key and Y public key. So if these hashes were already submitted by someone else, it means that Y did the same for X and Z, and that Z did the same for X and Y.

Assumptions

Every user has an elliptic curve keypair; server only knows their public keys.

There are public CLIENT_PADDING_XXX values which are supposed to uniquely identify the instance of the platform used (it could be an instance URL concatenated with a purpose, for example).

There are also SERVER_PADDING_XXX values that are never supposed to leave the server.

Used cryptographic primitives

sign(private_key, data), verify(public_key, signed_data): verify(public_key, sign(private_key, data)) == true. Additionally, sign output should not leak information about the public key.
encrypt(public_key, data), decrypt(private_key, encrypted_data): decrypt(private_key, encrypt(public_key, data)) == data. encrypt does not have to be stable. Additionally, encrypt should not leak information about the public key.
symmetric_encrypt(key, data), symmetric_decrypt(key, encrypted_data). symmetric_encrypt should be unstable (never produce the same result for the same data).
hash(data1, data2, ...): should be stable (always produce the same result) and irreversible.
derive_key(data1, data2, ...): generates a new symmetric encryption key, should be stable (always produce the same result for the same data) and irreversible.
shared_key2(private_key_a, public_key_b): shared_key2(private_key_a, public_key_b) == shared_key2(private_key_b, public_key_a). shared_key2 has to be stable (to always return the same result for the same input data).
shared_key3(private_key_a, public_key_b, public_key_c) == shared_key3(private_key_a, public_key_c, public_key_b) == shared_key3(private_key_b, public_key_a, public_key_c). shared_key3 has to be stable (to always return the same result for the same input data).
- It looks like there are no industry standard ways to do this: https://crypto.stackexchange.com/a/1034 , so it is not used below

The following methods are used

ECDSA for signing (does it leak public key?)
ECIES for asymmetric encryption (does it leak public key?)
AES-256 for symmetric encryption
SHA-256 for hashing (if multiple values are supplied, sha256(sha256(data1) + sha256(data2) + sha256(data3) + ...) is used).
ECDH for shared_key2

All requests to the server are signed with user's private key. Server verifies the signature against the supplied public key.

All responses from the server are encrypted with that public key. So that the user can decrypt them with their private key.

Scenarios

Basic scenario

Data submitted to the server

If an user X wants to save their sympathy towards Y, they have the following data:
- private_X (their private key)
- public_Y (Y's public key)
- metadata (an information they want to privately associate with this sympathy for their own purpose)
- outgoing_message (a message they want Y to get if there is a match)
Then they compute the following data:
- shared_key = shared_key2(private_X, public_Y)
- private_symmetric_key = derive_key(private_X, PUBLIC_PADDING_METADATA)
- shared_symmetric_key = derive_key(shared_key, PUBLIC_PADDING_MESSAGE)
- shared_hash = hash(shared_key, PUBLIC_PADDING_SHARED2)
- encrypted_metadata = symmetric_encrypt(private_symmetric_key, metadata)
- encrypted_outgoing_message = symmetric_encrypt(shared_symmetric_key, outgoing_message)
Then they submit the following data to the server:
- shared_hash
- encrypted_metadata
- encrypted_outgoing_message

Server logic

Given a request with the following data:
- public_key (from authentication)
- shared_hash
- encrypted_metadata
- encrypted_outgoing_message
- current_date (from clock)
Compute the following values:
- server_shared_hash = hash(shared_hash, SERVER_PADDING_SHARED2)
- server_shared_symmetric_key = derive_key(shared_hash, SERVER_PADDING_KEY2)
- public_key_hash_pending = hash(public_key, SERVER_PADDING_PUBLIC_KEY_HASH_PENDING)
- encrypted_public_key = symmetric_encrypt(server_shared_symmetric_key, public_key)
- server_encrypted_metadata = symmetric_encrypt(server_shared_symmetric_key, encrypted_metadata)
- server_encrypted_outgoing_message = symmetric_encrypt(server_shared_symmetric_key, encrypted_message)
- server_encrypted_creation_date = symmetric_encrypt(server_shared_symmetric_key, current_date)
Do the rate limiting: check if the number of non-mutual sympathies for that public_key_hash_pending is within allowed limit.
Check if there is an entry with this server_shared_hash but different public_key_hash_pending in the table of pending sympathies.
- If there is not:
  - Save a new entry to that table (or overwrite an exiting entry) with the following fields:
    - server_shared_hash
    - public_key_hash_pending
    - encrypted_public_key
    - server_encrypted_metadata
    - server_encrypted_outgoing_message
    - server_encrypted_creation_date
  - Respond with "sympathy registered"
- If there is:
  - Retrieve and remove that other_entry
  - Compute the following values:
    - other_public_key = symmetric_decrypt(server_shared_symmetric_key, other_entry[encrypted_public_key])
    - other_encrypted_metadata = symmetric_decrypt(server_shared_symmetric_key, other_entry[server_encrypted_metadata])
    - other_encrypted_outgoing_message = symmetric_decrypt(server_shared_symmetric_key, other_entry[server_encrypted_outgoing_message])
    - public_key_hash_mutual = hash(public_key, SERVER_PADDING_PUBLIC_KEY_HASH_MUTUAL)
    - other_public_key_hash_mutual = hash(previous_public_key, SERVER_PADDING_PUBLIC_KEY_HASH_MUTUAL)
    - server_symmetric_user_key = derive_key(public_key, SERVER_PADDING_PUBLIC_KEY)
    - server_symmetric_other_user_key = derive_key(previous_entry[public_key], SERVER_PADDING_PUBLIC_KEY)
    - server_reencrypted_metadata = symmetric_encrypt(server_symmetric_user_key, encrypted_metadata)
    - server_reencrypted_incoming_message = symmetric_encrypt(server_symmetric_user_key, other_encrypted_outgoing_message)
    - server_other_reencrypted_metadata = symmetric_encrypt(server_symmetric_other_user_key, other_encrypted_metadata)
    - server_other_reencrypted_incoming_message = symmetric_encrypt(server_symmetric_other_user_key, encrypted_outgoing_message)
  - Store in a table of mutual sympathies:
    - A following entry:
      - public_key_hash_mutual
      - server_reencrypted_metadata
      - server_reencrypted_incoming_message
    - And a following entry:
      - other_public_key_hash_mutual
      - server_other_reencrypted_metadata
      - server_other_reencrypted_incoming_message
  - Send a notification to the previous user (using its other_public_key);
  - Respond with "sympathy is mutual" and other_encrypted_outgoing_message.

Security

Malicious API usage

TODO: to be written...

Stored data

Prior to match, the following fields are stored:

server_shared_hash: only exposes information to the holder of shared_hash (i.e. one of the private keys plus other person's public key) plus SERVER_PADDING_SHARED2. So in case of DB+secrets leak, Y would be able to learn about X's non-mutual sympathy towards Y.
public_key_hash_pending: exposes information about who registered a sympathy to the holder of SERVER_PADDING_PUBLIC_KEY_HASH_PENDING (in case of DB+secrets leak) who is able to go through all public keys and compute their hashes (or targets a specific person).
encrypted_public_key: exposes information about who registered a sympathy to the holder of shared_hash (i.e. one of the private keys plus other person's public key) plus SERVER_PADDING_KEY2. The risks are the same as for server_shared_hash.
server_encrypted_metadata: additionally encrypted by client using the key derived from their private key, so does not expose any data.
server_encrypted_outgoing_message: additionally encrypted by client using the key derived from the shared key, in case of DB+secrets leak exposes cleartext message content to the other person even if the sympathy is not mutual.
server_encrypted_creation_date: exposes information about the creation date to the holder of shared_hash (i.e. one of the private keys plus other person's public key) plus SERVER_PADDING_KEY2.

All values are unique (should not occur in DB more than once), except for public_key_hash_pending. Aggregating data from the leaked DB would expose information about how many non-mutual sympathies are there for every public_key_hash_pending. Additionally, if server secrets are also leaked and an attacker is able to go through the list of all public keys (or targets a specific person), an attacker would be able to learn how many non-mutual sympathies an owner of a specific public_key has.

After match, the following fields are stored:

public_key_hash_mutual: similar to public_key_hash_pending
server_reencrypted_metadata: additionally encrypted by client using the key derived from their private key, so does not expose any data
server_reencrypted_incoming_message: additionally encrypted by client using the key derived from the shared key, so only exposes any data to the sender and the recipient who have it anyway
other_public_key_hash_mutual
server_other_reencrypted_metadata
server_other_reencrypted_incoming_message

All values are unique (should not occur in DB more than once), except for public_key_hash_pending. Similarly to the "prior to match" case, aggregating data from the leaked DB+secrets and going through the list of all public keys or targeting a specific person would allow attacker to learn how many mutual sympathies an owner of a specific public_key has.

Additionally a special care should be taken to make sure there is no way to deduce "mutual date" from these entries, especially since they are inserted into DB in roughly the same time. Otherwise an attacker with DB access would be able to deduce that two entries are related.

Handled data

TODO: to be written...

Metamour scenario

Data submitted to the server

If an user X wants to also learn about the shared connections when registering a sympathy, in addition to the two fields above they also submit the following data to the server:

For every mutual and non-mutual sympathy towards every user Z:
- hash(shared_key2(private_X, public_Y), public_Z, INSTANCE_ID) (referred to as common_XY_Z below);
- common_XZ_Y
- encrypted_metadata_X_Y (with an information about Y and Z)
- encrypted_metadata_X_Z (encrypted with a different nonce, to avoid matching the two)

Additionally, they store all such public_Z in the encrypted_metadata field for their pending sympathy towards Y.

Note that common_XY_Z == common_YX_Z

Server logic

For every entry in the list:
- Compute the following fields:
  - hash(common_XY_Z, SECRET_PADDING_COMMON3) (referred to as padded_common_XY_Z below; note that padded_common_XY_Z == padded_common_YX_Z)
  - padded_common_XZ_Y
  - hash(common_XY_Z, public_X, SECRET_PADDING_ID) (referred to as id_X_Y_Z below; note that id_X_Y_Z is different from any other permutation such as id_Y_X_Z)
  - id_X_Z_Y
  - symmetric_encrypt(derive_key(hash(common_XY_Z, SECRET_PADDING_KEY)), [common_XZ_Y, public_X]) (referred to as encrypted_data_XY_Z below)
  - encrypted_data_XY_Z
- Check how many entries are there with the same padded_common values but different id values in the table of pending metamour sympathies:
  - If there is not one of each (for the total of two):
    - Add the following two entries to the table:
      - padded_common_XY_Z, id_X_Y_Z, encrypted_data_XY_Z, encrypted_metadata_X_Y
      - padded_common_XZ_Y, id_X_Z_Y, encrypted_data_XZ_Y, encrypted_metadata_X_Z
    - Respond with sympathy registered
  - If there is one of each:
    - Retrieve them and remove them from the table of pending metamour sympathies
    - Decrypt the encrypted_data field, obtain the third remaining padded_common value plus both remaining public keys
    - Remove two entries for the third padded_common value
    - Add the following three entries to the table of completed metamour sympathies:
      - public_X, encrypted_metadata_X (any of the two)
      - public_Y (obtained by decrypting encrypted_data), encrypted_metadata_Y (obtained from the previously existing entry)
      - public_Z, encrypted_metadata_Z
    - Send notifications to Y and Z
    - Respond with sympathy mutual

16 KiB Raw Permalink Blame History

Thoughts

Basic scenario

Metamour scenario (3-party 1-stage shared key exchange)

Metamour scenario (2-party key exchange)

Assumptions

Used cryptographic primitives

Scenarios

Basic scenario

Data submitted to the server

Server logic

Security

Malicious API usage

Stored data

Handled data

Metamour scenario

Data submitted to the server

Server logic

Explanation

Security

Managing the existing sympathies

Viewing

Removing pending

Removing all data

Managing the existing metamour sympathies

Viewing

Caveat

Removing pending

Caveat

Removing all data

16 KiB

Raw Permalink Blame History