Checksum and transform layering

Checksum and transform layering

[Gregory Maxwell]

I noticed in the compression support that the checksum is over the
uncompressed data.

While this has the advantages that the checksum does not have to be
changed as transformations are changed and the system might catch
errors in the compression layer, this design decision will be
problematic if/when encryption is supported:  Plaintext checksums
would leak substantial amounts of information about the content of
files.  The system could be switched to a keyed cryptographic hash,
but then you will have made the "checksum" part of the file system
intimately tied to the cryptographic part (including having to deal
with key management, not being able to check blocks with keys that are
currently unavailable which would break automated scrubbing), and a
potential source of security problems. I think there is currently
enough space to store per-block a 64 bit checksum for integrity, a
64bit nonce for uniqueness, and a 128bit cryptographic hash for
authentication.

A minor additional point, by applying the checksum before other
transformations you lose the straightforward algebraic relationship
with the disk bits and check data. One advantage checksums and RS
codes have over cryptographic hashes is that advanced recovery tools
could be created which utilize all available data (multiple mirror
blocks, raid data, known corrupted sectors from the disk, and multiple
check) to provide maximum likelihood decodes, for cases where
known-perfect decoding is not possible, and the data can't be
otherwise replaced. I don't know if anyone will bother building such
tools, but maybe someone cares.

Re: Checksum and transform layering

[Claudio Martins]

On Thursday 06 November 2008, Gregory Maxwell wrote:
>
> While this has the advantages that the checksum does not have to be
> changed as transformations are changed and the system might catch
> errors in the compression layer, this design decision will be
> problematic if/when encryption is supported:  Plaintext checksums
> would leak substantial amounts of information about the content of
> files.  The system could be switched to a keyed cryptographic hash,

 Indeed. The most obvious (and quite trivial) attack one can do is buil=
d a=20
huge database of checksums for known files or chunks of files.

 AFAIK this has already been done by law enforcement/security agencies =
to=20
detect "illegal" files, so it's definitely an issue that would affect a=
ny=20
future encryption code implemented in btrfs.

Regards

Cl=C3=A1udio

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" =
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Checksum and transform layering

[Tracy Reed]

[-- Attachment #1: Type: text/plain, Size: 407 bytes --]

On Thu, Nov 06, 2008 at 12:15:12PM +0000, Claudio Martins spake thusly:
>  AFAIK this has already been done by law enforcement/security agencies to 
> detect "illegal" files, so it's definitely an issue that would affect any 
> future encryption code implemented in btrfs.

Indeed, it has: 

http://www.schneier.com/blog/archives/2008/11/us_court_rules.html

-- 
Tracy Reed
http://tracyreed.org

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: Checksum and transform layering

[Gregory Maxwell]

Thanks for entertaining my comments.

On Thu, Nov 6, 2008 at 9:40 AM, Chris Mason <chris.mason@oracle.com> wrote:
> For encryption we have a few choices.  We can checksum the encrypted
> blocks and disallow compression, or we can use a stronger checksum.
[snip]

The first sounds viable, although mutually exclusive features aren't
very user-friendly.

The latter would need to be a probably need to be a secret-keyed HMAC
to prevent watermarking attacks and information leakage, I don't think
simply salting with the sector number or other public information
would be sufficient: I could still take your encrypted disk and answer
the question "Does Chris have block X?" by checking the checksums.

But if the checksum is a keyed transform we can't sweep the
file-system for bit-rot without having all the keys available.  I
expect the common use case for encrypted btrfs is similar to eCryptfs
where each user may have their own keys which are only available when
they are logged in (single key whole disk encryption can still be
easily done with a dmcrypt).  So having all the keys at once may not
be especially realistic.  But being able to scan for failing blocks is
important in catching errors before there is too much damage.

Re: Checksum and transform layering

[Xavier Nicollet]

Le 06 novembre 2008 =E0 09:58, Gregory Maxwell a =E9crit:
> The latter would need to be a probably need to be a secret-keyed HMAC
> to prevent watermarking attacks and information leakage, [...]

Dm-crypt on every disks seems a good alternative, doesn't it ?
You would use dm-crypt for your swap anyway.

Did I miss something ?

--=20
Xavier Nicollet
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" =
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Checksum and transform layering

[Gregory Maxwell]

T24gVGh1LCBOb3YgNiwgMjAwOCBhdCAxMDoyNyBBTSwgWGF2aWVyIE5pY29sbGV0IDxuaWNvbGxl
dEBqZXJ1Lm9yZz4gd3JvdGU6Cj4gTGUgMDYgbm92ZW1icmUgMjAwOCDDoCAwOTo1OCwgR3JlZ29y
eSBNYXh3ZWxsIGEgw6ljcml0Ogo+PiBUaGUgbGF0dGVyIHdvdWxkIG5lZWQgdG8gYmUgYSBwcm9i
YWJseSBuZWVkIHRvIGJlIGEgc2VjcmV0LWtleWVkIEhNQUMKPj4gdG8gcHJldmVudCB3YXRlcm1h
cmtpbmcgYXR0YWNrcyBhbmQgaW5mb3JtYXRpb24gbGVha2FnZSwgWy4uLl0KPgo+IERtLWNyeXB0
IG9uIGV2ZXJ5IGRpc2tzIHNlZW1zIGEgZ29vZCBhbHRlcm5hdGl2ZSwgZG9lc24ndCBpdCA/Cj4g
WW91IHdvdWxkIHVzZSBkbS1jcnlwdCBmb3IgeW91ciBzd2FwIGFueXdheS4KPgo+IERpZCBJIG1p
c3Mgc29tZXRoaW5nID8KCkRtY3J5cHQgaXMgZmluZSBidXQgYSByYXRoZXIgYmx1bnQgdG9vbDog
SXQncyBhbGwgb3Igbm90aGluZywgYW5kIG9ubHkKYSBzaW5nbGUga2V5LiAgSXQgYWxzbyBjYW4g
bm90IHN0b3JlIGEgdW5pcXVlIG5vbmNlIHBlciBibG9jayB1cGRhdGUsCndoaWNoIG1heSBjcmVh
dGUgc29tZSAodGhlb3JldGljYWwpIHNlY3VyaXR5IHdlYWtuZXNzZXMuICBUaGUgd2hvbGUKdGhp
bmcgd2lsbCBuZWVkIHRvIGJlIG1vdW50ZWQgd2l0aCBrZXlzIGluIG1lbW9yeSBldmVuIHdoZW4g
eW91IG9ubHkKY2FyZSBhYm91dCBhIGZldyBmaWxlcy4gKHNvIHNvbWVvbmUgd2hvIGdhaW5zIGFj
Y2VzcyB0byB0aGUgc3lzdGVtCmNvdWxkIGFjY2VzcyBoaWdoIHNlY3VyaXR5IGZpbGVzIGV2ZW4g
aWYgdGhlIHN5c3RlbSB3YXMganVzdCBiZWluZwp1c2VkIGZvciB3ZWItYnJvd3NpbmcgYXQgdGhl
IHRpbWUpCgpXaXRoIGEgbW9yZSBpbnRlbGxpZ2VudCB5b3UgY291bGQgaGF2ZSBwZXItc3Vidm9s
dW1lIGtleWluZywgb3IgZXZlbgpiZXR0ZXIgcGVyLWZpbGUgYWxsb3dpbmcgdGhlIGVuY3J5cHRl
ZCBmaWxlc3lzdGVtIHRvIGNvbnRhaW4gYSBtaXggb2YKZmlsZXMgd2l0aCBkaWZmZXJpbmcgc2Vj
dXJpdHkgY2xhc3Nlcy4KClRha2UgYSBsb29rIGF0IGh0dHA6Ly9lY3J5cHRmcy5zb3VyY2Vmb3Jn
ZS5uZXQvIGZvciBhbiBleGFtcGxlIG9mIGEKbW9yZS1zb3BoaXN0aWNhdGVkIGZpbGVzeXN0ZW0g
ZW5jcnlwdGlvbiBmZWF0dXJlIHNldC4KCkF0IHRoZSBsZWFzdCBJIHRoaW5rIGl0IHdvdWxkIGJl
IHVzZWZ1bCBpZiBidHJmcyBwcm92aWRlZCBkbWNyeXB0CmZ1bmN0aW9uYWxpdHkgcGVyIHN1YnZv
bHVtZSwgdGhvdWdoIGZ1bGwgZWNyeXB0ZnMgbGV2ZWwgZnVuY3Rpb25hbGl0eQp3b3VsZCBiZSBx
dWl0ZSBpbnRlcmVzdGluZy4K

Re: Checksum and transform layering

[Chris Mason]

On Thu, 2008-11-06 at 09:40 -0500, Chris Mason wrote:
> On Thu, 2008-11-06 at 01:34 -0500, Gregory Maxwell wrote:
> > I noticed in the compression support that the checksum is over the
> > uncompressed data.
> 
> Thanks for looking things over, more eyes always helps.
> 
> > 
> > While this has the advantages that the checksum does not have to be
> > changed as transformations are changed and the system might catch
> > errors in the compression layer, this design decision will be
> > problematic if/when encryption is supported:  Plaintext checksums
> > would leak substantial amounts of information about the content of
> > files.  
> 
> We checksum the uncompressed data because it allows us to layer other
> transformations without confusing the code, and because the checksums
> are strictly tied to logical offsets in the file.  Additional metadata
> would be required to do things differently.  It's possible but I'd
> prefer not to introduce that complexity.
> 

Just FYI, the new disk format I've pushed out checksums the data on disk
instead of the uncompressed (or unencrypted) data.  There are lots of
tradeoffs here, but I think this is a much better system overall.

Thanks for your feedback, it sparked me thinking of this now, before we
tried to finalize the disk format.

-chris

Re: Checksum and transform layering

[Florian Weimer]

* Gregory Maxwell:

> I noticed in the compression support that the checksum is over the
> uncompressed data.
>
> While this has the advantages that the checksum does not have to be
> changed as transformations are changed and the system might catch
> errors in the compression layer, this design decision will be
> problematic if/when encryption is supported:  Plaintext checksums
> would leak substantial amounts of information about the content of
> files.

Would this be an issue if metadata (including file names) were
encrypted as well?

--=20
=46lorian Weimer                <fweimer@bfk.de>
BFK edv-consulting GmbH       http://www.bfk.de/
Kriegsstra=DFe 100              tel: +49-721-96201-1
D-76133 Karlsruhe             fax: +49-721-96201-99
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" =
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Checksum and transform layering

[Gregory Maxwell]

On Thu, Nov 6, 2008 at 11:31 AM, Florian Weimer <fweimer@bfk.de> wrote:
> * Gregory Maxwell:
>
>> I noticed in the compression support that the checksum is over the
>> uncompressed data.
>>
>> While this has the advantages that the checksum does not have to be
>> changed as transformations are changed and the system might catch
>> errors in the compression layer, this design decision will be
>> problematic if/when encryption is supported:  Plaintext checksums
>> would leak substantial amounts of information about the content of
>> files.
>
> Would this be an issue if metadata (including file names) were
> encrypted as well?

If the checksum is encrypted, no, at least not obviously. But as I've
mentioned if the checksum is encrypted then you can't scrub the FS for
checksum errors without the keys.

A lack of metadata encryption would be another possible information
leak, but at least it's one which can probably be understood by users.
It would be nice if subvolume level encryption provided metadata
encryption.   If metadata is encrypted but block checksums are
unencrypted and on plaintext then information will leak about the
files, even if the checksum is replaced with an unkeyed or
non-secret-keyed cryptographic hash, a secret-keyed hash is equivalent
to an encrypted checksum.