Ext4 data structures integrity

Ext4 data structures integrity

[Kasatkin, Dmitry]

Hello,

I have a question about Ext4 data structure integrity.

On Ext3 file system I was able to modify offline inode block mapping
in such a way,
that 2 inodes did point to the same data blocks, so when modifying one
file, did affect another file..
FSCK detects such problems and create duplicated blocks, so that inode
content will not overlap...

Does Ext4 suffers from the same problem?

Thanks,
Dmitry

Re: Ext4 data structures integrity

[Ted Ts'o]

On Wed, Sep 28, 2011 at 04:42:22PM +0300, Kasatkin, Dmitry wrote:
> Hello,
> 
> I have a question about Ext4 data structure integrity.
> 
> On Ext3 file system I was able to modify offline inode block mapping
> in such a way,
> that 2 inodes did point to the same data blocks, so when modifying one
> file, did affect another file..
> FSCK detects such problems and create duplicated blocks, so that inode
> content will not overlap...
> 
> Does Ext4 suffers from the same problem?

That's not a problem that's a feature!

It's REALLY REALLY BAD to try to corrupt the file system the way you
are doing.  If you at some point delete one of the files, then that
block will be marked free, and will get reused for something else,
which will then result in all sorts of data consistency problems.

Worse yet, if the block gets reused as a directory block, and then you
modify the remaining file, you could end up corrupting the file system
itself, leading to the loss of access many, many files.

Since ext4 uses the same file system consistency checker as ext3, it
will also find this sort of file system CORRUPTION, and correct it by
duplicating the blocks.

Why in the world would you want to do such a crazy thing in the first
place?

						- Ted

Re: Ext4 data structures integrity

[Kasatkin, Dmitry]

On Wed, Sep 28, 2011 at 4:56 PM, Ted Ts'o <tytso@mit.edu> wrote:
> On Wed, Sep 28, 2011 at 04:42:22PM +0300, Kasatkin, Dmitry wrote:
>> Hello,
>>
>> I have a question about Ext4 data structure integrity.
>>
>> On Ext3 file system I was able to modify offline inode block mapping
>> in such a way,
>> that 2 inodes did point to the same data blocks, so when modifying one
>> file, did affect another file..
>> FSCK detects such problems and create duplicated blocks, so that inode
>> content will not overlap...
>>
>> Does Ext4 suffers from the same problem?
>
> That's not a problem that's a feature!
>
> It's REALLY REALLY BAD to try to corrupt the file system the way you
> are doing.  If you at some point delete one of the files, then that
> block will be marked free, and will get reused for something else,
> which will then result in all sorts of data consistency problems.
>
> Worse yet, if the block gets reused as a directory block, and then you
> modify the remaining file, you could end up corrupting the file system
> itself, leading to the loss of access many, many files.
>
> Since ext4 uses the same file system consistency checker as ext3, it
> will also find this sort of file system CORRUPTION, and correct it by
> duplicating the blocks.
>
> Why in the world would you want to do such a crazy thing in the first
> place?
>
>                                                - Ted
>

Hello,

Thank you for the quick response.

I work on integrity protection subsystem IMA/EVM (linux/security/integrity).
The target is to protect against offline modifications.
Using block re-mapping I was able to implement simple attack which
allows to circumvent IMA integrity verification.
In order to prevent this kind of attack, it is necessary to run fsck every boot.

I want to know if there is a better way to prevent such attacks...


Thanks,

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

Re: Ext4 data structures integrity

[Ted Ts'o]

On Wed, Sep 28, 2011 at 06:19:12PM +0300, Kasatkin, Dmitry wrote:
> 
> I work on integrity protection subsystem IMA/EVM (linux/security/integrity).
> The target is to protect against offline modifications.
> Using block re-mapping I was able to implement simple attack which
> allows to circumvent IMA integrity verification.
> In order to prevent this kind of attack, it is necessary to run fsck every boot.
> 

OK, well, the way you worded your "bug report" it sounded like you
were complaining that fsck was fixing such file system corruptions.  I
wish you would have stated explicitly what you were trying to do from
the beginning.  Grumble....

> I want to know if there is a better way to prevent such attacks...

I suspect your real problem is that IMA is caching the results of its
integrity check.  If you don't want to require a full fsck to catch
this kind of double-mapped blocks, then you're going to have to do the
checksum each and every time the blocks are read into memory.  This
will catch the situation where a block is double mapped.

The file system isn't magic, you know.  There's a reason why we don't
check for cross-linked blocks except at fsck time; because otherwise
it would be an intolerable performance penalty.  If IMA wishes to
provide this kind of guarantee, it's IMA's responsibility to inflict
this performance penalty on the user, either by forcing an fsck check
every single time, or by doing integrity checksums every time.

This is not a defect in the file system.  It's a defect in your
expectations.

						- Ted

Re: Ext4 data structures integrity

[Kasatkin, Dmitry]

On Wed, Sep 28, 2011 at 6:45 PM, Ted Ts'o <tytso@mit.edu> wrote:
> On Wed, Sep 28, 2011 at 06:19:12PM +0300, Kasatkin, Dmitry wrote:
>>
>> I work on integrity protection subsystem IMA/EVM (linux/security/integrity).
>> The target is to protect against offline modifications.
>> Using block re-mapping I was able to implement simple attack which
>> allows to circumvent IMA integrity verification.
>> In order to prevent this kind of attack, it is necessary to run fsck every boot.
>>
>
> OK, well, the way you worded your "bug report" it sounded like you
> were complaining that fsck was fixing such file system corruptions.  I
> wish you would have stated explicitly what you were trying to do from
> the beginning.  Grumble....
>

Hello..

Sorry for such impression... I did not complain...

>> I want to know if there is a better way to prevent such attacks...
>
> I suspect your real problem is that IMA is caching the results of its
> integrity check.  If you don't want to require a full fsck to catch
> this kind of double-mapped blocks, then you're going to have to do the
> checksum each and every time the blocks are read into memory.  This
> will catch the situation where a block is double mapped.
>

This is exactly the problem...
After verification of the file, IMA sets status to INTEGRITY_OK.
If then I modify the content via "shadow file", then when reloading first one,
IMA will not verify it again...

> The file system isn't magic, you know.  There's a reason why we don't
> check for cross-linked blocks except at fsck time; because otherwise
> it would be an intolerable performance penalty.  If IMA wishes to
> provide this kind of guarantee, it's IMA's responsibility to inflict
> this performance penalty on the user, either by forcing an fsck check
> every single time, or by doing integrity checksums every time.
>

Yes. I know it's not magic :)
This exactly the current "already existing" solution - run fsck every boot...

> This is not a defect in the file system.  It's a defect in your
> expectations.
>

No. No. Never said like that :)

>                                                - Ted
>

Thanks!

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

Re: Ext4 data structures integrity

[Ted Ts'o]

On Thu, Sep 29, 2011 at 03:24:37PM +0300, Kasatkin, Dmitry wrote:
> 
> > This is not a defect in the file system.  It's a defect in your
> > expectations.
>
> No. No. Never said like that :)

To quote from your original message:

   "Does Ext4 suffers from the same problem?"

   	      	      	       	    - Ted

Re: Ext4 data structures integrity

[Kasatkin, Dmitry]

On Thu, Sep 29, 2011 at 3:56 PM, Ted Ts'o <tytso@mit.edu> wrote:
> On Thu, Sep 29, 2011 at 03:24:37PM +0300, Kasatkin, Dmitry wrote:
>>
>> > This is not a defect in the file system.  It's a defect in your
>> > expectations.
>>
>> No. No. Never said like that :)
>
> To quote from your original message:
>
>   "Does Ext4 suffers from the same problem?"
>
>                                    - Ted
>

Ok.. My mistake to say like that :)
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Ext4 data structures integrity

[Andreas Dilger]

On 2011-09-28, at 9:19 AM, "Kasatkin, Dmitry" <dmitry.kasatkin@intel.com> wrote:
> I work on integrity protection subsystem IMA/EVM (linux/security/integrity).
> The target is to protect against offline modifications.
> Using block re-mapping I was able to implement simple attack which
> allows to circumvent IMA integrity verification.
> In order to prevent this kind of attack, it is necessary to run fsck every boot.
> 
> I want to know if there is a better way to prevent such attacks...

There is work currently being done to add checksums for detecting filesystem corruption (see list archive). However, if the attacker can binary edit the underlying disk device then they can also edit the checksums (crc32c) at the same time. 

The only secure way to handle this would be a crypto checksum with a secret key. At that point you may as well just use a whole crypto/backed filesystem?

Cheers, Andreas

Re: Ext4 data structures integrity

[Kasatkin, Dmitry]

Hi

On Wed, Sep 28, 2011 at 8:16 PM, Andreas Dilger <adilger@dilger.ca> wrote:
> On 2011-09-28, at 9:19 AM, "Kasatkin, Dmitry" <dmitry.kasatkin@intel.com> wrote:
>> I work on integrity protection subsystem IMA/EVM (linux/security/integrity).
>> The target is to protect against offline modifications.
>> Using block re-mapping I was able to implement simple attack which
>> allows to circumvent IMA integrity verification.
>> In order to prevent this kind of attack, it is necessary to run fsck every boot.
>>
>> I want to know if there is a better way to prevent such attacks...
>
> There is work currently being done to add checksums for detecting filesystem corruption (see list archive). However, if the attacker can binary edit the underlying disk device then they can also edit the checksums (crc32c) at the same time.
>
> The only secure way to handle this would be a crypto checksum with a secret key.

This something came to my mind after reading previous sentence about crc32c...

>At that point you may as well just use a whole crypto/backed filesystem?
>

Yes... I know...

Thanks!

- Dmitry


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

Re: Ext4 data structures integrity

[Kasatkin, Dmitry]

>>
>> There is work currently being done to add checksums for detecting filesystem corruption (see list archive). However, if the attacker can binary edit the underlying disk device then they can also edit the checksums (crc32c) at the same time.
>>
>> The only secure way to handle this would be a crypto checksum with a secret key.
>

Can you please give me some links to it????

Thanks,

Dmitry

Re: Ext4 data structures integrity

[Ted Ts'o]

On Thu, Sep 29, 2011 at 04:33:52PM +0300, Kasatkin, Dmitry wrote:
> >>
> >> There is work currently being done to add checksums for detecting filesystem corruption (see list archive). However, if the attacker can binary edit the underlying disk device then they can also edit the checksums (crc32c) at the same time.
> >>
> >> The only secure way to handle this would be a crypto checksum with a secret key.
> >
> 
> Can you please give me some links to it????

Darrick Wong has been sending patches to the linux-ext4 mailing for
review to use crc32c to protect various parts of the file system
metadata.

There has been no work to the "crypto checksum with a secret key" bit;
the hard part is where you would securely store the secret key so that
only a trusted kernel has access to it.

       	    	   	   	      - Ted

Re: Ext4 data structures integrity

[Kasatkin, Dmitry]

On Thu, Sep 29, 2011 at 4:55 PM, Ted Ts'o <tytso@mit.edu> wrote:
> On Thu, Sep 29, 2011 at 04:33:52PM +0300, Kasatkin, Dmitry wrote:
>> >>
>> >> There is work currently being done to add checksums for detecting filesystem corruption (see list archive). However, if the attacker can binary edit the underlying disk device then they can also edit the checksums (crc32c) at the same time.
>> >>
>> >> The only secure way to handle this would be a crypto checksum with a secret key.
>> >
>>
>> Can you please give me some links to it????
>
> Darrick Wong has been sending patches to the linux-ext4 mailing for
> review to use crc32c to protect various parts of the file system
> metadata.
>
> There has been no work to the "crypto checksum with a secret key" bit;
> the hard part is where you would securely store the secret key so that
> only a trusted kernel has access to it.
>
>                                      - Ted
>

Hello again,

Running fsck on modified file system image with multiply-claimed block
gives such output
---------------------------------------
fsck 1.41.9 (22-Aug-2009)
e2fsck 1.41.9 (22-Aug-2009)
Pass 1: Checking inodes, blocks, and sizes

Running additional passes to resolve blocks claimed by more than one inode...
Pass 1B: Rescanning for multiply-claimed blocks
Multiply-claimed block(s) in inode 12: 1326
Multiply-claimed block(s) in inode 13: 1326
Pass 1C: Scanning directories for inodes with multiply-claimed blocks
Pass 1D: Reconciling multiply-claimed blocks
(There are 2 inodes containing multiply-claimed blocks.)

File /foo.hack (inode #12, mod time Fri Oct  7 11:27:03 2011)
  has 1 multiply-claimed block(s), shared with 1 file(s):
        /foo (inode #13, mod time Fri Oct  7 10:41:38 2011)
Clone multiply-claimed blocks<y>?
----------------------------

For large file system to run fsck takes a while..
One of the solution to decrease checking time is just to check only
for multiply-claimed blocks...
Could you please tell how many times faster it will be comparing just
to running fsck as it is...

Thanks,

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

Re: Ext4 data structures integrity

[Kasatkin, Dmitry]

On Fri, Oct 7, 2011 at 5:00 PM, Theodore Tso <tytso@mit.edu> wrote:
>
> On Oct 7, 2011, at 7:40 AM, Kasatkin, Dmitry wrote:
>
> For large file system to run fsck takes a while..
> One of the solution to decrease checking time is just to check only
> for multiply-claimed blocks...
> Could you please tell how many times faster it will be comparing just
> to running fsck as it is…
>
> In order to guard against multiply claimed blocks, you will need to complete
> fsck pass 1.
> You can time fsck pass1 for yourself by running e2fsck with the -tt option.
>  For ext3 pass 1 was approximately 70% of the total run time.  With ext4 the
> time to run pass 1 was significantly reduced.

Yes... It is really noticeable..
I assume it is achieved not by compromising check quality...
What is the reason?

Thanks

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

Re: Ext4 data structures integrity

[Theodore Tso]

On Oct 7, 2011, at 10:20 AM, Kasatkin, Dmitry wrote:
>> With ext4 the
>> time to run pass 1 was significantly reduced.
> 
> Yes... It is really noticeable..
> I assume it is achieved not by compromising check quality...
> What is the reason?

The use of extents significantly reduces the amount of metadata (specifically indirect blocks/double indirect blocks/triple indirect blocks) which required a lot of seeking during the pass 1 scan.   In addition, because we are using checksums to protect the block group descriptors against accidental corruption, we can afford to avoid scanning parts of the inode table which are unused.

Of course, we never worried about deliberately malicious attackers; so if you're going to depend on e2fsck's pass1 checks for IMA protection, we would need to add a check in ext4_get_inode_loc() in the kernel to flag the file system as containing an error (and you would have to require remounting the file system read-only in that circumstances) if there was an attempt to read in an inode which exceeds the high watermark of used inodes for the block group.

-- Ted

Re: Ext4 data structures integrity

[Mimi Zohar]

Ted Ts'o <tytso <at> mit.edu> writes:

> 
> On Thu, Sep 29, 2011 at 04:33:52PM +0300, Kasatkin, Dmitry wrote:
> > >>
> > >> There is work currently being done to add checksums for detecting
filesystem corruption (see list
> archive). However, if the attacker can binary edit the underlying disk device
then they can also edit the
> checksums (crc32c) at the same time.
> > >>
> > >> The only secure way to handle this would be a crypto checksum with a
secret key.
> > >
> > 
> > Can you please give me some links to it????
> 
> Darrick Wong has been sending patches to the linux-ext4 mailing for
> review to use crc32c to protect various parts of the file system
> metadata.
> 
> There has been no work to the "crypto checksum with a secret key" bit;
> the hard part is where you would securely store the secret key so that
> only a trusted kernel has access to it.

Sorry I missed this thread. Any reason that trusted/encrypted keys can't be
used for storing the secret key?

thanks,

Mimi

Re: Ext4 data structures integrity

[Kasatkin, Dmitry]

On Wed, Nov 9, 2011 at 1:44 AM, Mimi Zohar <zohar@linux.vnet.ibm.com> wrote:
> Ted Ts'o <tytso <at> mit.edu> writes:
>
>>
>> On Thu, Sep 29, 2011 at 04:33:52PM +0300, Kasatkin, Dmitry wrote:
>> > >>
>> > >> There is work currently being done to add checksums for detecting
> filesystem corruption (see list
>> archive). However, if the attacker can binary edit the underlying disk device
> then they can also edit the
>> checksums (crc32c) at the same time.
>> > >>
>> > >> The only secure way to handle this would be a crypto checksum with a
> secret key.
>> > >
>> >
>> > Can you please give me some links to it????
>>
>> Darrick Wong has been sending patches to the linux-ext4 mailing for
>> review to use crc32c to protect various parts of the file system
>> metadata.
>>
>> There has been no work to the "crypto checksum with a secret key" bit;
>> the hard part is where you would securely store the secret key so that
>> only a trusted kernel has access to it.
>
> Sorry I missed this thread. Any reason that trusted/encrypted keys can't be
> used for storing the secret key?
>

Probably because it is relatively new thing...

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

Re: Ext4 data structures integrity

[Andreas Dilger]

On 2011-09-29, at 7:33 AM, "Kasatkin, Dmitry" <dmitry.kasatkin@intel.com> wrote:
>>> 
>>> There is work currently being done to add checksums for detecting filesystem corruption (see list archive). However, if the attacker can binary edit the underlying disk device then they can also edit the checksums (crc32c) at the same time.
>>> 
>>> The only secure way to handle this would be a crypto checksum with a secret key.
>> 
> 
> Can you please give me some links to it????

My point wasn't that this is something to try and implement, but rather that if you have an attacker who can modify the disk directly then it is best to use cryptoloop or similar to encrypt the whole device.

Cheers, Andreas