We should somehow identify when two users have sympathies toward each other.
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.
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.
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.
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).
*`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).
*`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.
*`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.
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):
