Silicon JungleSilicon Jungle

User ID spoofing

This article is building off knowledge learnt in the last-writer-wins article.

Last-writer-wins is an efficient method of resolving merge conflicts, but the algorithms we've covered so far run optimistically and have vulnerabilities that bad actors can exploit.

In this article we will be exploring how user IDs can be exploited to assume the identity of other users and some of the potential solutions.

Last-writer-wins algorithm

For this example we will be examining the following last-writer-wins algorithm.

export const create = (sequence, userId) => [sequence, userId]

export const shouldSet = (currentVersion, version) =>
  currentVersion[0] > version[0] ||
  (currentVersion[0] === version[0] && currentVersion[1] > version[1])

key: [sequenceNumber, serverId] Last-writer-wins merge rules

Making changes on behalf of others

Versions use a sequence number and a user ID as a tie-breaker e.g. [0, 'James']. If the user ID is assigned randomly on the front-end, there is nothing stopping a user from receiving a message from a peer and then changing their own user ID to that of the peer.

This would allow a user to send messages with the same identity as the peer.

The available solutions in this space differ depending on whether you're implementing the algorithm in a centralised or P2P setting.

User ID spoof

P2P User ID spoof

Centralised solutions

In a centralised setting, we are able to trust the server as a source of truth, so the solutions end up being much simpler and more efficient.

Server assigned user IDs

The server can assign user ID's to user's on their first connection (or on each login). You still need to send the ID to the user so that they can resolve merges locally.

One of the downsides to this method is that until the client has access to a user ID from the server, they will not be able to make any changes. This should only be required on first connection (or each login).

Server assigned user ID

Client assigned user IDs, server verified

To get rid of the waiting period on the front-end, user's can assign their own user IDs locally. Then on the server you just need to associate that user ID with the first connection / account that has sent that ID along with a change.

This adds overhead where the server must store a lookup of every user ID ever assigned to a user. A decent solution for efficient look up would be to use a Bloom Filter.

Client assigned user ID, server verified

P2P solutions

In a P2P setting, since there is no central server to trust, each client must be able to verify who the original sender of the message was.

Digital signatures

Digital signatures can be used in both centralised and decentralised settings.

Whenever a client sends a message, they can digitally sign the message using a private key. They can then share the public key with their peers which can be used to verify that the message is authentic.

Rather than storing [sequenceNumber, userId] in each last-writer-wins register, we can store [sequenceNumber, publicKey, signature].

We then need to change the merging rules so that we first compare sequence numbers and then use the public key as the tie-breaker.

If a received message is unable to be verified, it is rejected.

Digital signatures

Below is a simple example of how to implement signing and verification using the crypto library.

import crypto from 'crypto'

const { privateKey, publicKey } = crypto.generateKeyPairSync('rsa', {
  modulusLength: 2048,
})

const signMessage = (privateKey, message) => {
  const data = Buffer.from(JSON.stringify(message))
  return crypto.sign('sha256', data, privateKey)
}

const verifyMessage = (publicKey, message, signature) => {
  const data = Buffer.from(JSON.stringify(message))
  return crypto.verify('sha256', data, publicKey, signature)
}

const message = { type: 'patch', operations: [['key', 0, 'Hi!']] }
const signature = signMessage(privateKey, message)
console.log(verifyMessage(publicKey, message, signature))