The shard format

How a file under Shard Protection is kept: cut into pieces, each encrypted on its own and stored under a name that says nothing about it. This page is for whoever writes or reads it. Today that is FileFreak's SDK and CLI, each of which writes version 1 when it uploads into a protected place (the SDK from 0.3.0, the CLI from 0.9.0) and reads it when it downloads; the CLI writes version 2 from 0.10.0 for a file of more than 16 MiB. The website and the API run the SDK's own code for it. Every implementation must write the test files, for version 1 and for version 2, byte for byte, and refuse each of their refusals for the reason they give.

There are two versions, and a reader reads both; the first byte of every stored piece says which it is. Version 1 cuts a file into fragments of one size, each sealed to its content's own key, id, place and count. Version 2 cuts it into blocks by content, sealed under a key the file's versions share, so that a new version can keep the blocks the version before it has, and only what changed is sent and stored again. Version 2 is defined here, with its test files, and the SDK and the CLI read and write it on those files. The API takes it from a program that says it writes it, and hands it to one that says it reads it. The website, the SDK from 0.5.0 and the CLI from 0.10.0 read it; the CLI from 0.10.0 and the SDK from 0.6.0 write it, and the website still writes version 1.

Version 1

Terms

• Content: one version of a file's bytes. A new version is a new content.

• Content id: a UUID the API gives a content when it is first stored. A copy of a file keeps it, since a copy's fragments are copied unchanged.

• Key: 32 bytes from a cryptographically secure random source, made by the API, one per content and never used for another. A copy keeps it with the content id. How the key is kept is not part of the format: it is stored encrypted by a master key the API never holds.

• Fragment size: how many bytes of the file a fragment holds. The format does not fix it; the API chooses it for each content and gives it with the map. A file smaller than 16 MiB for each storage lane is cut into one fragment per lane, of ceil(size / lanes) bytes, so that no lane holds all of it; a larger one into fragments of 16 MiB, doubled while there would be more than 16,384, to at most 64 MiB. A reader takes it from the map and assumes nothing about it.

• Count: how many fragments the content has. Place: a fragment's number, from 0.

Cutting a file

For a file of size bytes and a fragment size of f:

• count is ceil(size / f), or 1 when the file is empty: an empty file is one empty fragment, so that even it has something to authenticate.

• Fragment p holds bytes p * f up to min((p + 1) * f, size). Every fragment but the last holds exactly f bytes; the last holds at least 1 (0 only for the empty file).

• count must fit in 32 bits (at most 4,294,967,295). A description with more, or with f of 0, is refused (layout).

Sizes are 64-bit. A file of 1 TiB in fragments of 64 MiB is 16,384 fragments, and the test files include it, past the 4 GiB point at which a 32-bit offset would wrap.

A stored fragment

So a stored fragment is the bytes it holds plus 29.

The associated data, which the tag covers but which is not stored:

Writing

For each place: take the fragment's bytes of the file, make a nonce, encrypt with the key, the nonce and the associated data for that place, and store the version, the nonce, the ciphertext and the tag, in that order. A writer refuses to seal a fragment whose length is not the one its place has.

A nonce is random rather than counted because the same content may be written by two clients at once, a browser and the CLI for instance, and neither can know what the other has counted. With a fresh key for every content, the chance of two of a content's nonces being the same is negligible at any count the format allows.

A writer is given what it needs by the API. An upload begun with protectable into a protected place is answered with how the file is cut (shards: the version, 1, the content id, the fragment size and the count), uploads.get gives the key, and each part of the upload is the fragment at its place, sent to that part's address and confirmed with uploads.fragments (the developer API's reference says each step). A fragment sent again, because storage did not keep it, is read and sealed again under a new nonce: the bytes read again may not be the bytes sealed before, and two sets of bytes sealed under one key and one nonce give away how they differ, and let a tag be forged.

Reading

A reader is given, by the API, the content id, the size, the fragment size and the key, and for each fragment where to fetch it: the file's map, a page of up to 1,000 fragments at a time. The website is given it by GET /api/files/:id/shards, and programs, the CLI among them, by GET /v1/files/:id/shards (files.shards in the developer API's reference). Somebody who is not the owner is given it through a link to the file, or from its public page, a page at a time with a grant that carries the reading on (Shard links). It checks each stored fragment in this order, refuses it at the first check that fails, and says which:

1. short: fewer than 29 bytes, which no fragment can be.

2. version: the first byte is not 0x01.

3. length: not the length the fragment's place gives: the size and the fragment size say how many bytes it holds, and it is that plus 29.

4. authentication: GCM's tag does not match, under the content's key and the associated data for the place the reader is filling.

A reader never releases any of the bytes of a fragment that failed, not even to a part of a file being written to disk: what it has decrypted is not known to be the file's until the tag has been checked.

The file is every fragment's bytes, in order of place.

What it protects, and what not

What the format makes true: whoever has the storage, or a signed address to a fragment, and not the key, learns nothing of a fragment's bytes but its length; cannot change a fragment without the change being found; cannot move a fragment to another place or another file, or give a reader fewer fragments than there are, without the reader refusing it, since the place and the count are in what the tag covers.

What it does not hide: the size of each fragment, and so the file's size to within the fragment size, from anyone who can list the storage; and the map itself (sizes, count, places, which lane holds which) from whoever has the database. It does not protect against someone who has both the database and the use of the master key, which is to say FileFreak itself, or against the devices of the people the file is shared with.

Version 2

Terms

• Content and content id: as in version 1.

• File key: 32 bytes from a cryptographically secure random source, made by the API and kept as version 1's key is. Unlike version 1's, one key may seal the blocks of several contents: the versions of one file. Which contents share a key is the API's to decide, not the format's. The file key is never used as it is: three keys are derived from it, below.

• Block: a run of the file's bytes. The format does not fix where a block ends; a writer cuts the file, and the outline gives each block's length. A block holds at most 64 MiB (67,108,864 bytes). An empty file is one empty block, and no other block is empty.

• Block id: 32 bytes, the HMAC-SHA256 of a block's bytes under the block key. The same bytes under the same file key have the same id, which is what lets a new version keep a block; under another file key they have another.

• Outline: the content id, the size, the count, and each block's id and length in order, with a MAC over all of it.

The keys

Each is HKDF-SHA256 (RFC 5869) of the file key with no salt (an empty salt, which HKDF takes as 32 zero bytes), 32 bytes long, the info being the ASCII text in the first column:

So sealing, naming a block and vouching for the outline each have a key of their own, and none can be played against another.

A stored block

So a stored block is the bytes it holds plus 29, as in version 1.

The associated data:

It says nothing about where the block is: a block a later version keeps is at another place in another content, and must open there unchanged. The outline holds the order instead.

The outline

Its MAC is the HMAC-SHA256, under the outline key, of:

An outline describes a file only if it names at least one block and no more than 4,294,967,295, no block holds more than 64 MiB, no block is empty unless the file is, and the lengths add up to the size. Any other is refused (layout), and no MAC is made or checked for it.

Cutting a file

Where blocks end is the writer's to choose, and a reader takes it from the outline. But the lengths are seen by whoever has the database or can list the storage, and if the rule were one anybody could run, they could cut a file they have and compare its lengths with a protected file's, which would tell them whether it is that file as surely as a plain hash would. So a writer must cut with a rule that depends on the file key.

FileFreak's writers cut by FastCDC as the fastcdc crate runs it (version 5, its 2020 form, normalised at level 1), with a table made from the file key in place of the crate's public one:

• The table. HKDF-SHA256 of the file key with no salt, the info being filefreak-shard-v2 cut, 2,048 bytes long, read as 256 unsigned 64-bit big-endian numbers, G[0] to G[255]. Like the three keys, it is never stored or sent.

• A piece begins where the last ended, the first at the start of the file. Counting its bytes from 0, take h = 0 and, for each byte b at place i from 1,048,576 (1 MiB) on, h = (2h + G[b]) mod 2^64. The piece ends before byte i, so that it is i bytes long, at the first i where h AND m is 0: m is 0x0000d93777537000 for i below 4,194,304 (4 MiB) and 0x0000d91767537000 from there. Places are tested in pairs, i even and i + 1, so a piece whose end is odd has its last byte hashed and never tested. A piece holds at most 16,777,216 bytes (16 MiB) and ends there if no place has matched; the last piece of the file is what is left, and one of 1 MiB or less is not tested at all.

• A piece's hash is h at the byte that matched, doubled (mod 2^64) when that byte's place is even; for a piece that ended at 16 MiB or at the end of the file, h after its last byte; and 0 for a last piece of 1 MiB or less. It decides only runs, below.

• Blocks. In a file of up to 32 GiB (34,359,738,368 bytes) each piece is a block. In a larger one, pieces are put together into runs, each run a block, so that the file is within 10,000 blocks: a run ends after a piece whose hash times 0x9e3779b97f4a7c15, mod 2^64, is below 2^62 (about one piece in four), once it holds 48 MiB or more, and at the end of the file. So no block holds more than 64 MiB.

• A file this cuts into fewer than two blocks or more than 10,000 is written in version 1 instead.

Plain files are cut by the same rule with the crate's public table, which is why the rule is the crate's: the CLI cuts both with the crate's own cut_gear. The crate makes that table from MD5 (for each value v, the first eight bytes, big-endian, of the MD5 of 64 bytes of v), and the SDK makes it the same way and cuts with its own FastCDC, so that the next version of a file either one sent keeps its blocks whichever sends it. That is no part of the format. The test files (cut in shard-format-v2.json) give the table for one key, the pieces four contents are cut into and the hash of each (one of them a piece of odd length whose last byte would be a place to cut, were it tested), the blocks one of them is declared as and its outline, which of a list of hashes end a run, and under plain the public table and the pieces of one content cut with it. The program that makes the test files follows the rule a byte at a time, as it is written here, and not the crate, so the two agree only if this says the crate's rule right; the CLI holds the crate to the files, and the SDK holds itself to them.

What the table does not do is make the lengths secret. Someone who has the database, and a file they think is a protected one, cannot cut it the way its writer did; but they can see every length, and with many lengths of a file they already hold they could try to work back to the table, as has been shown for other keyed rules of this kind. The format does not claim that block lengths say nothing.

Writing

For each block: compute its id; make a nonce; encrypt with the seal key, the nonce and the associated data for that id; and store the version, the nonce, the ciphertext and the tag, in that order. A writer refuses to seal a block of more than 64 MiB. Then it computes the outline's MAC, which goes with the upload's completion. A block the content before it already has under the same file key need not be sent: it has the same id, and the new outline names it.

A nonce is random, as in version 1. A file key lives as long as the file does, so more blocks are sealed under one key than in version 1: a file of 10,000 blocks rewritten every day for thirty years is about 2^27 sealings, far inside the 2^32 at which the chance of any two nonces being the same reaches 2^-32.

Through the developer API (its reference says each step):

1. Begin with protectable and shardFormats naming 2. A sealed file of more than 16 MiB, cut into no more than 10,000 blocks of the largest size, is then written in version 2, and any other as before: shards says format: 2, with the content id, no fragments and no parts yet. The website writes version 1 only, whatever it sends.

2. Get the key from uploads.get. Replacing a file whose current content is in version 2, with a key that may read files, it is the file's own key, which is what lets the new version keep blocks; for a new file, a file in version 1, or a key that may only write, it is a new key, and nothing is kept. An upload under the file's own key is then answered only to a key that may read files.

3. Declare the blocks with uploads.blocks: each one's size and id, in order, from 2 to 10,000 of them, adding up to the file's size. The answer says which places the file already has (reused), which are not sent, and gives addresses for the rest, each in the lane after the one the place before it is in. The same declaration again is answered the same; a different one is refused (blocks_declared).

4. Send and confirm each block that is not kept, sealed as above, to its part's address, and confirm it with uploads.fragments, as in version 1. uploadedParts counts the kept places with the confirmed ones, so a writer that resumes sends every place not among them.

5. Complete with outline, the outline's MAC in base64. The API checks it against the declared blocks under the file key, so a writer that made it wrong is told now (outline_mismatch), not by every reader afterwards. A block the file had that went before completing, because the file was replaced or deleted meanwhile, is answered upload_incomplete: that place is then sent like any other, and the upload completes.

An upload that ends without becoming the file queues for deletion only what it sent, never a block it kept.

Reading

A reader is given the outline and its MAC first, whole, then where to fetch each block. Before it releases a byte, it refuses the file unless the outline describes a file (layout) and its MAC holds under the outline key (outline). A reader that cannot hold the whole outline refuses the file rather than reading it unchecked. Then it checks each stored block in this order, refuses it at the first check that fails, and says which:

1. short: fewer than 29 bytes.

2. version: the first byte is not 0x02.

3. length: not the length the outline gives the block, plus 29.

4. authentication: GCM's tag does not match, under the seal key and the associated data for the id the outline gives at that place.

5. id: the HMAC-SHA256 of the opened bytes under the block key is not that id.

As in version 1, a reader never releases any of the bytes of a block that failed. The file is the blocks' bytes, in the outline's order.

The API gives a reader the same map as in version 1, by the same routes and links, with format: 2 and, on the first page only, outline: its MAC and each block's id and length, in base64. A place's fragment is then the block at that place. A reader says which versions it reads with formats=1,2; one that does not is answered 409 format_unsupported for a file in version 2, before a link's download is counted, so a program made before version 2 tells its user to update rather than failing on the file. The website reads version 2, as do the SDK from 0.5.0 and the CLI from 0.10.0. Each checks the outline before it fetches a block, and refuses a map whose count, or whose largest block, is not the outline's.

What it protects, and what not

As in version 1, whoever has the storage and not the key learns nothing of a block's bytes but its length, and cannot change a block without the change being found.

What version 2 adds: whoever has the database and not the key cannot reorder, drop, repeat or swap a content's blocks, or give one content's outline as another's, since the MAC covers the content id, the order, and every id and length; and cannot tell whether a block is a block of a file they have, since an id is made with the key, and two files with different keys never share an id.

What it binds less tightly than version 1: a block is bound to its file key and its id, not to a content and a place, so a block of one version of a file can be read in another version of the same file. That is what lets a version keep a block, and it happens only where that version's outline, which only the key can vouch for, names it.

What it does not hide: the length of every block, from whoever can list the storage or has the database, which is why the cut must depend on the key; which contents of a file share blocks, and so roughly how much each version changed; and, as in version 1, nothing against someone with both the database and the use of the master key, or against the devices of the people the file is shared with.

Test files

The test files for version 1 and for version 2 are made by a program of their own, which uses Node's own HKDF, HMAC and cipher rather than either implementation, so that a mistake in one of them cannot also be in the bytes it is checked against.

Version 1's holds:

• files: whole contents, an empty one, one fragment, several, a last fragment of one byte, whole fragments with no empty one after them, and fragments that end inside an AES block, each with its key, content id, size, fragment size, count and every fragment's nonce, associated data and stored bytes. A writer given the nonce must produce the stored bytes; a reader must give back the file.

• refused: stored bytes, the description a reader is given them under, and the check that must refuse them.

• layouts and badLayouts: the arithmetic alone, at FileFreak's sizes, and descriptions no reader may accept.

Version 2's holds:

• derived: a file key and the three keys derived from it.

• files: an empty file, one block, blocks of different lengths, a block the file repeats, and blocks that end inside an AES block, each with its file key, content id, size, and every block's length, id, nonce, associated data and stored bytes, and the outline's MAC.

• refused: stored blocks, the id and length a reader is given them under, and the check that must refuse them, among them blocks wrong in two ways at once, which only a reader that checks in the order above refuses for the reason given.

• refusedOutlines: outlines with their MACs that a reader must refuse, and why.

Only the test files choose a nonce. The writers' public functions make their own; the entry points that take one are the tests' and are not exported.

Another version

A change to any of this is a new version: a new first byte and a new label in the associated data, so that no stored piece can be read as another version's. A reader refuses a version it does not know, rather than guessing. Version 2 was made this way, beside version 1 rather than in place of it, since protected files written in version 1 are kept as they are.