Apache Wave is a software framework for online real-time collaborative edition. Similarly to Google Docs and Etherpad, it uses Operational Transformations to manage user collaboration. During this Google Summer of Code we are providing end-to-end encryption to wave documents. This means that only the people with access to the documents (those who have shared a symmetric key) can edit and retreive the contents of a document, protecting in that way the privacy of wave users.

We base our GSOC work in this awesome paper that explains how some researchers encrypted Google Docs’ Operational Transformations. They used a simplified model to explain how document operations (called revisions in the paper) can be encrypted.

In this blog post, we translate the paper insights to Apache Wave architecture, on which SwellRT is based. Let’s start with some basics of Apache Wave, and what is the structure of a document. If you are already familiar with them, you can just skip the next section.

Documents and Operations

As this fabulous blog post explains, Wave documents are well-formed XML documents that carry additional metadata called “annotations”. Annotations are (potentially-overlapping) key/value ranges which span across specific regions of the document and are usually used to style the text.

Documents can be modified by (and also represented as) a document operation. A document operation is a series of components that move the cursor across the document. Those components can be of the type:

  • insertCharacters — Inserts the specified string at the current index.
  • deleteCharacters — Deletes the specified string from the current index.
  • openElement — Creates a new XML open-tag at the current index.
  • deleteOpenElement — Deletes the specified XML open-tag from the current index.
  • closeElement — Closes the first currently-open tag at the current index.
  • deleteCloseElement — Deletes the XML close-tag at the current index.
  • annotationBoundary — Defines the changes to any annotations (starting or ending) at the current index.
  • retain — Advances the index a specified number of items.

So, the document operation retain(8); deleteCharacters('m'); insertCharacters('M'); retain(38); would remove the “m” at position 8 and add an “M” in the same position.

Now we are ready to understand how to encrypt those operations.

Encrypting Operations

In the paper, clients share a symmetric key in order to encrypt and decrypt operations, and the server has no knowledge of it, so encryption and decryption of operations must be carried on the client side.

The simplified model of the paper only considers two components (called primitive operations or mutations): insertion and deletion. Insertions insert the text v at a particular position p of the document, and deletions delete k characters forward or backward, depending on if k is positive or negative. Only the inserted text is encrypted and decrypted, remaining the document structure visible by the server.

In Wave, we have a plenty more of components, as we have seen in the previous section. We are going to encrypt the text components only, remaining the XML format of the document in plaintext and visible by the server. The components that deal directly with the text are insertCharacters and deleteCharacters, so we are going to encrypt the text of their parameters.

When a text is encrypted, its length is usually expanded due to randomization and integrity requirements (commonly known as initialization vector and MAC). This represents a challange in an Operational Transformation system, in which the length of the inserted and deleted text is something to take into account in order to compose and transform the operations.

In the paper, it is solved by adding two more components at the end of each operation, an insertion of the extra information, and a deletion of that information. This is a clever approach that solves the problem, maintaining the cursor constant between the encrypted and non-encrypted operations.

We can not use the same approach in Wave because its operations can not move the cursor backwards as it is done in the paper (delete something that the same operation is adding). Fortunately, we can obtain a similar effect storing the additional text in a particular operation without moving the cursor, I am talking about the annotations.

Using annotations to store the ciphertext, we can encrypt any operation with any number of insertCharacters and deleteCharacters components, by concatenating their texts and storing its ciphertext in the annotation. For example, for the following operation:

retain(8); deleteCharacters('m'); insertCharacters('M'); retain(38);

We would concatenate all the texts as “mM”, encrypt it using the shared key obtaining something similar to:

qOg89Tc6KjH9HyeC;6pQAClv6a8MnFoAHWsT06WIV;

And we would add an annotation from the beginning to the end of the document that we will strip in the decryption process.

annotationBoundary(changes: [
  cipher = null -> 'qOg89Tc6KjH9HyeC;6pQAClv6a8MnFoAHWsT06WIV;']);
retain(8);
deleteCharacters('*');
insertCharacters('*');
retain(38);
annotationBoundary(ends: ['cipher']);

Note that component parameters have been replaced by asterisks (*) in order to maintain a character there and do not leak any information of the underlying text that was there.

So, now the rest of the clients can receive that operation and decrypt it by decrypting the text of the annotation and splitting its characters among the asterisks of the insertCharacters and deleteCharacters components.

This encryption and decryption process is done just before and after the Wavelet Operations are sent to and received from the server, respectively, at a class called StaticChannelBinder.

UPDATE 2017-07-25: Since Wave does not check if the deleted characters in the document correspond to the deleted characters received as a document operation component, we can optimize the algorithm by do not encrypting and decrypting the deleteCharacters operations. We only have to ofuscate the deleted text using a predefined character, such as the asterisk (*).

The code that encrypts and decrypts operations is already available in our repo, and a video with the demo can be watched here:

Next steps

Now that we have designed the encryption and decryption of operations “on-the-fly”, we need clients to be able to decrypt a document that has already been written. In order to do it, the client needs all the ciphertext from which the current state of the document is formed of. The paper uses a smart approach to see which operations in the history are useful for the current state of the document, so the server could use it to send to the clients just the information they need in order to decrypt the document, reducing the bandwidth and the computational power needed to perform the entire replay of the whole document history. These are the things we are going to focus on the following weeks, and we will share them in another blog post when it will be ready.

Stage 2 of GSOC has already begun.