linux-kernel - Re: [PATCH 08/16] ext4: Calculate and verify checksums for inode bitmaps

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1315251928.15087.74.camel@dabdike.int.hansenpartnership.com>
Date:	Mon, 05 Sep 2011 14:45:28 -0500
From:	James Bottomley <James.Bottomley@...senPartnership.com>
To:	djwong@...ibm.com
Cc:	Andreas Dilger <adilger.kernel@...ger.ca>,
	Theodore Tso <tytso@....edu>,
	Sunil Mushran <sunil.mushran@...cle.com>,
	Amir Goldstein <amir73il@...il.com>,
	linux-kernel <linux-kernel@...r.kernel.org>,
	Andi Kleen <andi@...stfloor.org>,
	Mingming Cao <cmm@...ibm.com>,
	Joel Becker <jlbec@...lplan.org>,
	linux-fsdevel <linux-fsdevel@...r.kernel.org>,
	linux-ext4@...r.kernel.org, Coly Li <colyli@...il.com>
Subject: Re: [PATCH 08/16] ext4: Calculate and verify checksums for inode
 bitmaps

On Mon, 2011-09-05 at 11:22 -0700, Darrick J. Wong wrote:
> On Fri, Sep 02, 2011 at 03:27:21PM -0600, Andreas Dilger wrote:
> > On 2011-09-02, at 1:18 PM, Darrick J. Wong wrote:
> > > On Wed, Aug 31, 2011 at 10:49:05PM -0600, Andreas Dilger wrote:
> > >> On 2011-08-31, at 6:31 PM, Darrick J. Wong wrote:
> > >>> Compute and verify the checksum of the inode bitmap; the checkum is stored in
> > >>> the block group descriptor.
> > >> 
> > >> I would prefer if there was a 16-bit checksum for the (most common)
> > >> 32-byte group descriptors, and this was extended to a 32-bit checksum
> > >> for the (much less common) 64-byte+ group descriptors.  For filesystems
> > >> that are newly formatted with the 64bit feature it makes no difference,
> > >> but virtually all ext3/4 filesystems have only the smaller group descriptors.
> > >> 
> > >> Regardless of whether using half of the crc32c is better or worse than
> > >> using crc16 for the bitmap blocks, storing _any_ checksum is better than
> > >> storing nothing at all.  I would propose the following:
> > > 
> > > That's an interesting reframing of the argument that I hadn't considered.
> > > I'd fallen into the idea of needing crc32c because of its bit error
> > > guarantees (all corruptions of odd numbers of bits and all corruptions of
> > > fewer than ...4? bits) that I hadn't quite realized that even if crc16
> > > can't guarantee to find any corruption at all, it still _might_, and that's
> > > better than nothing.
> > > 
> > > Ok, let's split the 32-bit fields and use crc16 for the case of 32-byte block
> > > group descriptors.
> > 
> > I noticed the crc16 calculation is actually _slower_ than crc32c,
> > probably because the CPU cannot use 32-bit values when computing the
> > result, so it has to do a lot of word masking, per your table at
> > https://ext4.wiki.kernel.org/index.php/Ext4_Metadata_Checksums.
> > Also, there is the question of whether computing two different
> > checksums is needlessly complicating the code, or if it is easier
> > to just compute crc32c all the time and only make the storing of
> > the high 16 bits conditional.
> > 
> > What I'm suggesting is always computing the crc32c, but for filesystems
> > that are not formatted with the 64bit option just store the low 16 bits
> > of the crc32c value into bg_{block,inode}_bitmap_csum_lo.  This is much
> > better than not computing a checksum here at all.  The only open question
> > is whether 1/2 of crc32c is substantially worse at detecting errors than
> > crc16 or not?
> 
> All the literature I've read has suggested that crc16 can't guarantee any error
> detection capability at all with data buffers longer than 256 bytes.

Um, so in a hashing algorithm that maps f:Z_m -> Z_n you can never
guarantee error detection if m>n because of hash collisions.  All you
can guarantee is that if f(a) != f(b) then a != b, so crc16 wouldn't be
able to *guarantee* error detection in anything over 2 bytes.

All of the rest of the magic in hashing functions goes into making sure
that the collision sets don't include common errors (like bit flipping).
In theory, for the correct polynomial, CRC-16 should be able to detect
single, double and triple bit flip errors in blocks of up to 8191
bytes ... of course, if those aren't your common errors, then this
analysis is useless ...

James


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/