Storro Key Management

Remco Bloemen

Storro allows users to collaborate on projects. It creates an encrypted drive on the users devices. The drive contains a folder for each project the user has joined. Changes made to the folder distribute to the project’s other users. Every user independently validates correct operation. Storro resolves any conflicting changes without user interaction. A revision history logs all changes. All historical versions are retrievable. The integrity is cryptographically guaranteed.

A user can be in one of five different roles in a project. In monotonically increasing order of privilege they are:

  1. Uninvited: The user is not a part of the project in any way.
  2. Facilitator: The user provides backup and hosting. Other than that, there is not even read access. The user is not able to learn anything about the contents of the project. Not even a list of files.
  3. Observer: The user has full read-only access to the project. The user is a passive observer and not able to make any changes.
  4. Participant: The user participates in the project. The user has full write access to the project folder. He/she is able to create, change and remove all files and folders.
  5. Administrator: The user administrates the project. Like a participant, he/she has read/write access. Administrators can also change the project metadata. This includes adding or removing users and changing their roles. (With one exception: the last administrators can not remove him/her self.)

Storro enforces non-mutable privileges by controlling access to read-keys. It forces mutating privileges by having every participant confirm the correctness of the mutation. Storro limits storage of encrypted information to a set of allowed devices.

License Management

LicenseCertificate:
    user: User public key
    device: Device public key
    kind: enum of Server Desktop Laptop Smartphone
    validity: DateTime
    signature: Signature by a license authority

LicenseService:
    refreshLicense: ∅ → LicenseCertificate

A device maintains an up-to-date LicenseCertificate object. It periodically requests a new one from a license authority. The license authority’s signature validates a license. Storro has a fixed set of license authorities, compiled into the executable. Initial authentication uses the socialist millionaire protocol on the license key. Later authentications can also use user/device keys.

The full version of the licensing protocol contains more details about the licensee. Storro only shares these between the licensee and the license authority. The authority can hand out LicenseCertificate objects with longer or shorter validity. The validity forces peers to come online and refresh the license. The validity is a trade-off between offline functionality and revoking licenses.

Storro peers will request a valid LicenseCertificate object before they interact. An expired license will lock a user/device out of the network. The user can continue local work. A renewed license reconnects the user. Storro then integrates the local and remote changes.

Distributed Content Addressed Store

StoreCertificate:
    projectUuid: Uuid
    users: set of public key
    admins: set of public key
    timestamp: DateTime
    signature: signature by an admin

StoreService:
    exchangeCertificate: set of StoreCertificate → set of StoreCertificate
    get: (Uuid, Hash) → (Uuid, Value)
    put: (Uuid, Value) → ∅
    sync: Binary → Binary

Storro stores all the projects state in a content addressed store. The stores synchronize between all users that are at least facilitator in the project. Facilitators can not decrypt anything in the store. The facilitators know who to synchronize with and who administrates this. Storro maintains an up to date StoreCertificate object for every project. This object contains the list of devices that can access it. It also contains a list of admins that can update the certificate.

Exchange Certificate: When two Storro peers connect, they check which projects the other has access to. They then exchange the latest StoreCertificates for those projects. For every certificate received, the peer verifies and updates. Only admins can sign valid certificates. The timestamp guarantees that the latest certificates eventually reach every peer.

Get, Put and Sync: The store has the conventional get and put calls. Get retrieves a value based on its hash. The requester verifies correct behaviour by verifying the hash of the returned value. The sync call uses an efficient protocol to discover missing hashes between two stores. The put call is for completeness. Every store can validity it’s own integrity by checking the hashes. Observers can decrypt the contents and perform full integrity checks and garbage collection.

Version Management

VersionCertificate:
    projectUuid: Uuid
    readKey: set of encrypted keys to Version
    timestamp: DateTime
    signature: signature by an observer

VersionService:
    exchangeVersions: set of VersionCertificate → set of VersionCertificate

The readKey contains the keys to read the latest Version object. The certificate writer encrypts them for each user with at least observer role. Storro stores the Version object and related objects encrypted in the content addressed store:

Version:
    metadata: key to Metadata
    previous: set of key to Version
    root: key to Directory
    signature: user signature

Directory:
    name: string
    entries: set of (key to File or Director)

File:
    name: string
    contents: key to binary

The next section describes the Metadata object. The specification leaves out details such as modification times and compression. Observers can create a new version and corresponding certificate. This new version merges updates from every other version the device is aware off. Devices with observer role have one unique latest version. Facilitators have insufficient permission to create their own versions. Facilitator will store and pass along the latest versions of other users.

The Version objects satisfy invariants. They are a state-based conflict-free replicated data type with strong eventual consistency. The state is monotonically increasing. This is explicitly constructed by the previous hashes. These create a causal lattice of Version objects:

  1. The versions form a directed acyclic graph through their previous fields, the version graph.
  2. The version graph has a least element, the initial version.
  3. The hash of the initial version is the projects universally unique identifier.
  4. The version graph has a greatest element, the latest version.
  5. Converged replicas have the same latest version.
  6. Converged replicas have identical states.
  7. Non-initial versions have either one parent, the commits, or more, the merges.
  8. The initial version has one user with the administrator role, the founder.
  9. The initial version is signed by the founder.
  10. Commits differ from their previous in either the metadata or root field, not both. These are called meta-commits and root-commits.
  11. Root-commits are signed by user that has participant or administrator role in the previous version.
  12. The previous versions in a merge are commits.
  13. The previous versions in a merge are pair-wise unreachable.
  14. Merges are a known deterministic function of their previous versions.
  15. No two elements in a Directory.entries have the same name.

Create Project: The founder creates a initial version that satisfies all invariants. The founder can work in the project on his device and invite other users/devices.

Exchange Versions: Two devices start with the content addressed store synchronization. Next they exchange VersionCertificates for the latest versions of the project. Storro peers restrict this to versions the other device is also member of. Peers validate the certificate on receipt. Facilitators can stop here. Observers proceed to construct the Version object and verify the invariants. Peers ignore invalid data. Peers integrate new data and update their VersionCertificate.

Add Commit: The devices registers local changes to the projects directory. Storro peers store these changes as a commits in the Version history. They update their VersionCertificate and distributed it to other devices. Devices validate the new Version on receipt. Storro rejects illegal Versions. Illegal changes will not propagate the network beyond the malicious device(s).

User Management

Invitation:
    projectUuid:
    name: String
    readKey: key to Version
    voucher: private key
    expiry: DateTime

Storro devices store the following encrypted in the content addressed store:

Metadata:
    name: string
    description: string
    users: set of Credentials
    vouchers: set of Voucher

Credentials:
    user: user public key
    role: enum of Facilitator Observer Participant Administrator

Voucher:
    key: public key
    role: enum of Facilitator Observer Participant Administrator
    expiry: DateTime

The Metadata has extra invariants:

  1. A meta-commit is signed by and administrator, a regular user or a voucher.
  2. A regular user signed commit only affects that user and does not increase the maximal role of that users.
  3. A voucher signed commit removes that voucher and can add one user with the role specified in the voucher.
  4. Meta-commits have no vouchers with expiry dates before the signature date.
  5. There is at least one administrator.

Invite User: An admin can invite a user by adding the user/device keys to the credentials. The admin then distributes the updated StoreCertificate and VersionCertificate. When the user/device connects to an updated peer it can retrieve the latest version. The public keys of the user/device are not always known in advance. In this case, the admin can create a voucher. The admin can then send the user/device an Invitation by any secure channel. The voucher is a single-use right to create an account with a predetermined role. The user/devices can accept the invitation by creating its own account. The user/device can reject the invitation by making removing the voucher. This only requires retrieving the latest Version and Metadata objects.

Remove User: The admin or user/device creates a meta-commit that removes the user/device from the project. The device then distributes this update. Later VersionCertificates will not include a key for the user. Later requests to peers will fail for the removed user. The user/device still receives the meta-commit containing its removal. This allows it to detect its removal. When removed a Storro device will remove encrypted data.