Is gfcombinefs - a filesystem for n-of-m Shamir secret sharing - fundamentally read-only?

Question

With a view on using a tool similar to fgcombinefs in cloud situations, I would need a writable n-of-m Shamir secret sharing filesystem.

As a matter of routine security, I do not want the cloud provider to be able to reconstruct real data from what I store on his hardware.

If the data stored on his hardware is fundamentally random, because it is just one share in a Shamir shared secret, there is no point for anybody to try to look for a key, because there isn't one. The attacker would simply need find the other n-1 shares, stored at other cloud providers elsewhere on the globe.

fgcombinefs seems to implement 99% of the job, but unfortunately, its Shamir filesystem is read-only.

When looking at the fuse operations behind fgcombinefs, you can see that both read and write are actually supported :

int(*   write_buf )(const char *, struct fuse_bufvec *buf,
   off_t off, struct fuse_file_info *)

int(*   read_buf )(const char *, struct fuse_bufvec **bufp,
   size_t size, off_t off, struct fuse_file_info *)

You can see that in the case of writing a block, fuse will ask you to effectively perform a write to the file named as in the first string argument const char *, at offset off_t off. In the case of a read of a block in a file at a particular offset and a particular size, fuse will ask you to allocate a block, if needed, and return its address in bufp.

I would think that writing a Shamir block, amounts to first producing the m Shamir secret shares, and then writing them to the m underlying filesystems, while reading a Shamir block amounts to picking n filesystems from the m available, ask them to send the block, recombine the n secrets on the fly, and return the reconstituted block to the caller.

In these circumstances, I do not really understand why writing to a Shamir filesystem would fundamentally be unsupported?

However, if I overlooked an impossibility somewhere, I would be most grateful if someone pointed it out, because it would spare me the time wasted in trying to program something that would in fact be impossible. Is there fundamentally a reason why the author has made fgcombinefs read-only?

Answer 1

I am the author of gfcombinefs.

Instead of sharing your actual secret, I would suggest secret-sharing an immutable, securely-random bytestring, and using that bytestring as a symmetric encryption key. That way, you can use any standard encryption mechanism to change and re-encrypt your actual secret. That's what I now do instead of using gfcombinefs - I use the gfcombine tool to reconstitute a symmetric encryption key on a ramfs, and use it to decrypt an encrypted volume. This means I have the freedom to change the secret keys that are on the encrypted volume, back up the encrypted volume, and so on without needing to re-share anything (which is very inconvenient if you have written some of the shares to external media stored in a separate location, or to paper).

In these circumstances, I do not really understand why writing to a Shamir filesystem would fundamentally be unsupported?

Three reasons:

• I didn't need it when I wrote gfcombinefs, and I didn't implement what I didn't need :-)
• I haven't done the mathematics to prove whether it would be safe
• I would guess (although I have no proof for this assertion) that making it safe would require having all the shares online and modifiable at the same time

Another commenter wrote:

AFAICT, it should be safe against attackers who only get one look at the shares, but it might leak information if the attacker can observe the same n′< n shares before and after the change

You are welcome to do whatever you want with gfcombinefs (bearing in mind that it has absolutely no warranty, and I never actually did a proper release of it). However, if it was my secret being shared, I would not be comfortable with doing this until I had a security model, and a mathematical proof that the proposed scheme met the security model.

I wrote a mathematical proof that libgfshare had the properties I believed it did (https://sources.debian.net/src/libgfshare/2.0.0-2/doc/theory.tex/) before starting to use libgfshare for anything I valued. I would suggest doing the same if you use it differently.

Answer 2

Consider a situation with a $n$-of-$m$ Shamir secret sharing scheme (such as 4-of-6 as apparently implemented by gfcombinefs).

Consider now that only $n' < m$ of the shares are actually available (such as the example of keeping two shares on removable media, two more on the computer, and another two as backups, in a 4-of-6 scheme; $m = 6$ and $n' = 4$ shares available under normal circumstances).

Updating the contents of the secret would require rewriting $m > n' \Rightarrow 6 > 4$ shares, which is clearly not possible because the remaining two shares are not physically available to be rewritten.

I don't see anything inherently fundamental which would make a Shamir secret sharing file system read-only, but you would have to write out the shares such that the new shares can be redistributed to where they should be located, which means that they will need to be committed to some kind of storage in preparation for being distributed -- and that storage is all on the same system. In the presence of an adversary which is able to access the storage directly, this would appear to defeat the purpose of using Shamir secret sharing in the first place, because now all the shares are available in a single place!

Hence, probably not fundamentally impossible, but seems like a bad idea to support as a regular file operation because it leaves lots of data around in ways a user might not want or expect.

It might however be convenient if rewriting the secret is supported as a special operation that does not rely on external tooling, but rather can be done using tooling provided in the gfcombinefs package itself. (But I would probably rather see support for arbitrary $n$-of-$m$ schemes first.)