PATCH - ext2fs privacy (i.e. secure deletion) patch

PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

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

Hi,

I've written a quick patch to the ext2fs which ensures that inodes, data 
  blocks, and directory entries are overwritten with null bytes when 
they are deleted. The patch adds a couple of inline functions to 
overwrite the appropriate data with zeroes. Its quite simple and 
self-explanitory. Both attached patches are to a vanilla 2.4.24 kernel.

inodes: ext2_delete_inode() now uses the inline function delete_inode() 
to mark the on-disk inode as 'deleted'. If the privacy option is not 
enabled, then the i_dtime is set as per usual operation, otherwise the 
meta-data are all set to 0. After the inode has been truncated, the 
i_data is set to 0 by delete_blocks() and the inode is written to disk 
again.

Splitting the delete_inode() and delete_blocks() functions is not ideal, 
I would prefer that one function remove the meta-data and the inode be 
written out just once. The problem is that ext2_truncate() needs the 
i_data information from the struct inode, and we want to remove this 
information from the inode on the disk. To ensure that the i_data is 0 
by the time it hits the disk, I write the inode to disk twice, which is 
not optimal.

directory entries: ext2_delete_entry() now uses the inline function 
mark_delete_dir() to indicate that the directory entry is no longer 
valid. If the privacy patch is not enabled, then the dir->inode is set 
to  0 as per normal operation, otherwise the entry is memset 0. Very 
straightforward.

blocks: ext2_free_blocks() now uses the inline function destroy_block() 
before it updates the group meta-data. The destroy_block() function 
overwrites the block with zeroes. I'm not sure that it is implemented 
correctly, I don't know anything about buffer_heads. The block is only 
overwritten with a single pass of zeroes. It is, of course, possible to 
have a full 37 pass overwriter with full bit toggling maps and all that, 
but I think it might make more sense to add a new option for that, 
something like: CONFIG_EXT2_FS_PRIVACY_EXTREME_PARANOIA. For preventing 
simple forensic analysis (that is, what the police, employers and even 
most government agencies do) a single pass with zeroes is sufficient. 
Users can use userland tools like wipe or srm for more thorough overwriting.

There is also a patch to ext3fs, which adds the same functionality (in 
the same way) as the ext2fs privacy patch. However, the main problem 
with privacy on the ext3fs is the journal. I am not familiar enough with 
how the journal transactions are handled to implement what seems to me 
the obvious solution: when a transaction is complete (i.e. doesn't need 
to be replayed by fsck) overwrite it with null bytes. If done correctly, 
it is possible to leave sufficient information for fsck to find the 
right transaction to begin replaying, without leaving any data which 
would be of use to a forensic analyst.

Given the existing global political climate, privacy control over a file 
system seems like a no-brainer to me. Full privacy options would include 
things like mounting disks with noatime, and possibly normalizing the 
mtime and ctime of all inodes (setting everthing to an arbitrary date, 
e.g. 0). Certainly this will break tools like make which require atime, 
but it would provide even less information to a forensic analyst 
examining the file system.



peace,

--gq

ps. apologies for posting to the kernel mailing list, but I'm not sure 
who is the maintainer for ext2/3.





[-- Attachment #2: privacy_patch_ext2 --]
[-- Type: text/plain, Size: 3509 bytes --]

--- linux-2.4.24/fs/Config.in	2003-11-28 18:26:21.000000000 +0000
+++ linux-2.4.24/fs/Config.in-ext2-privacy	2004-01-27 21:56:58.000000000 +0000
@@ -92,6 +92,7 @@
 tristate 'ROM file system support' CONFIG_ROMFS_FS
 
 tristate 'Second extended fs support' CONFIG_EXT2_FS
+dep_mbool '  ext2 privacy support' CONFIG_EXT2_FS_PRIVACY $CONFIG_EXT2_FS
 
 tristate 'System V/Xenix/V7/Coherent file system support' CONFIG_SYSV_FS
 
--- linux-2.4.24/fs/ext2/balloc.c	2003-06-13 15:51:37.000000000 +0100
+++ linux-2.4.24/fs/ext2-privacy/balloc.c	2004-01-28 00:52:59.000000000 +0000
@@ -247,6 +247,23 @@
 	return slot;
 }
 
+static inline void destroy_block(struct inode *inode, unsigned long block)
+{
+#ifdef CONFIG_EXT2_FS_PRIVACY
+	struct buffer_head	* bh;
+
+	bh = sb_getblk(inode->i_sb, block);
+
+	memset(bh->b_data, 0x00, bh->b_size);
+
+	mark_buffer_dirty(bh);
+	wait_on_buffer(bh);
+	brelse(bh);
+
+	return;
+#endif
+}
+
 /* Free given blocks, update quota and i_blocks field */
 void ext2_free_blocks (struct inode * inode, unsigned long block,
 		       unsigned long count)
@@ -319,6 +336,8 @@
 				   "bit already cleared for block %lu", block);
 		else {
 			DQUOT_FREE_BLOCK(inode, 1);
+
+			destroy_block(sb, block);
 			gdp->bg_free_blocks_count =
 				cpu_to_le16(le16_to_cpu(gdp->bg_free_blocks_count)+1);
 			es->s_free_blocks_count =
--- linux-2.4.24/fs/ext2/dir.c	2002-11-28 23:53:15.000000000 +0000
+++ linux-2.4.24/fs/ext2-privacy/dir.c	2004-01-25 17:15:27.000000000 +0000
@@ -468,6 +468,15 @@
 	return err;
 }
 
+static inline mark_deleted_dir(struct ext2_dir_entry_2 *dir)
+{
+#ifndef CONFIG_EXT2_FS_PRIVACY
+	dir->inode = 0;
+#else
+	memset(dir, 0, dir->rec_len);
+#endif
+}
+
 /*
  * ext2_delete_entry deletes a directory entry by merging it with the
  * previous entry. Page is up-to-date. Releases the page.
@@ -495,7 +504,7 @@
 		BUG();
 	if (pde)
 		pde->rec_len = cpu_to_le16(to-from);
-	dir->inode = 0;
+	mark_deleted_dir(dir);
 	err = ext2_commit_chunk(page, from, to);
 	UnlockPage(page);
 	ext2_put_page(page);
--- linux-2.4.24/fs/ext2/inode.c	2003-06-13 15:51:37.000000000 +0100
+++ linux-2.4.24/fs/ext2-privacy/inode.c	2004-01-27 21:33:59.000000000 +0000
@@ -46,6 +46,36 @@
 	ext2_discard_prealloc (inode);
 }
 
+static inline void delete_inode(struct inode *inode)
+{
+#ifndef CONFIG_EXT2_FS_PRIVACY
+	inode->u.ext2_i.i_dtime	= CURRENT_TIME;
+#else
+	inode->i_mode	= 0;
+	inode->i_uid	= 0;
+	inode->i_gid	= 0;
+	inode->i_nlink	= 0;
+	inode->i_atime	= 0;
+	inode->i_ctime	= 0;
+	inode->i_mtime	= 0;
+	inode->u.ext2_i.i_dtime	= 0;
+	inode->u.ext2_i.i_flags	= 0;
+	inode->u.ext2_i.i_faddr	= 0;
+	inode->u.ext2_i.i_frag_no	= 0;
+	inode->u.ext2_i.i_frag_size	= 0;
+	inode->u.ext2_i.i_file_acl	= 0;
+	inode->i_generation	= 0;
+#endif
+}
+
+static inline void delete_blocks(struct inode *inode)
+{
+#ifdef CONFIG_EXT2_FS_PRIVACY
+	inode->i_blocks	= 0;
+	memset(&inode->u.ext2_i.i_data, 0x00, sizeof(inode->u.ext2_i.i_data));
+#endif
+}
+
 /*
  * Called at the last iput() if i_nlink is zero.
  */
@@ -57,12 +87,18 @@
 	    inode->i_ino == EXT2_ACL_IDX_INO ||
 	    inode->i_ino == EXT2_ACL_DATA_INO)
 		goto no_delete;
-	inode->u.ext2_i.i_dtime	= CURRENT_TIME;
+
+	delete_inode(inode);
 	mark_inode_dirty(inode);
 	ext2_update_inode(inode, IS_SYNC(inode));
+
 	inode->i_size = 0;
 	if (inode->i_blocks)
 		ext2_truncate (inode);
+	delete_blocks(inode);
+       mark_inode_dirty(inode);
+       ext2_update_inode(inode, IS_SYNC(inode));
+
 	ext2_free_inode (inode);
 
 	unlock_kernel();

[-- Attachment #3: privacy_patch_ext3 --]
[-- Type: text/plain, Size: 2505 bytes --]

--- linux-2.4.24/fs/Config.in	2003-11-28 18:26:21.000000000 +0000
+++ linux-2.4.24/fs/Config.in-ext3-privacy	2004-01-27 21:57:22.000000000 +0000
@@ -34,6 +34,7 @@
 # dep_tristate '  Journal Block Device support (JBD for ext3)' CONFIG_JBD $CONFIG_EXT3_FS
 define_bool CONFIG_JBD $CONFIG_EXT3_FS
 dep_mbool '  JBD (ext3) debugging support' CONFIG_JBD_DEBUG $CONFIG_JBD
+dep_mbool '  ext3 privacy support' CONFIG_EXT3_FS_PRIVACY $CONFIG_EXT3_FS
 
 # msdos file systems
 tristate 'DOS FAT fs support' CONFIG_FAT_FS
--- linux-2.4.24/fs/ext3/balloc.c	2003-06-13 15:51:37.000000000 +0100
+++ linux-2.4.24/fs/ext3-privacy/balloc.c	2004-01-28 00:44:56.000000000 +0000
@@ -252,6 +252,23 @@
 	return slot;
 }
 
+static inline void destroy_block(struct inode *inode, unsigned long block)
+{
+#ifdef CONFIG_EXT3_FS_PRIVACY
+	struct buffer_head	* bh;
+
+	bh = sb_getblk(inode->i_sb, block);
+
+	memset(bh->b_data, 0x00, bh->b_size);
+
+	mark_buffer_dirty(bh);
+	wait_on_buffer(bh);
+	brelse(bh);
+
+	return;
+#endif
+}
+
 /* Free given blocks, update quota and i_blocks field */
 void ext3_free_blocks (handle_t *handle, struct inode * inode,
 			unsigned long block, unsigned long count)
@@ -370,6 +387,7 @@
 			BUFFER_TRACE(bitmap_bh, "bit already cleared");
 		} else {
 			dquot_freed_blocks++;
+			destroy_block(sb, block);
 			gdp->bg_free_blocks_count =
 			  cpu_to_le16(le16_to_cpu(gdp->bg_free_blocks_count)+1);
 			es->s_free_blocks_count =
--- linux-2.4.24/fs/ext3/inode.c	2003-08-25 12:44:43.000000000 +0100
+++ linux-2.4.24/fs/ext3-privacy/inode.c	2004-01-27 21:48:54.000000000 +0000
@@ -172,6 +172,28 @@
 	ext3_discard_prealloc (inode);
 }
 
+static inline void delete_inode(struct inode *inode)
+{
+#ifndef CONFIG_EXT3_FS_PRIVACY
+	inode->u.ext3_i.i_dtime	= CURRENT_TIME;
+#else
+	inode->i_mode	= 0;
+	inode->i_uid	= 0;
+	inode->i_gid	= 0;
+	inode->i_nlink	= 0;
+	inode->i_size	= 0;
+	inode->i_blocks	= 0;
+	inode->i_atime	= 0;
+	inode->i_ctime	= 0;
+	inode->i_mtime	= 0;
+	inode->u.ext3_i.i_dtime	= 0;
+	inode->u.ext3_i.i_flags	= 0;
+	inode->u.ext3_i.i_file_acl	= 0;
+	inode->i_generation	= 0;
+	memset(&inode->u.ext3_i.i_data, 0x00, sizeof(inode->u.ext3_i.i_data));
+#endif
+}
+
 /*
  * Called at the last iput() if i_nlink is zero.
  */
@@ -211,7 +233,7 @@
 	 * (Well, we could do this if we need to, but heck - it works)
 	 */
 	ext3_orphan_del(handle, inode);
-	inode->u.ext3_i.i_dtime	= CURRENT_TIME;
+	delete_inode(inode);
 
 	/* 
 	 * One subtle ordering requirement: if anything has gone wrong

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Pavel Machek]

Hi!

>  }
>  
> +static inline void destroy_block(struct inode *inode, unsigned long block)
> +{
> +#ifdef CONFIG_EXT2_FS_PRIVACY
> +	struct buffer_head	* bh;
> +
> +	bh = sb_getblk(inode->i_sb, block);
> +
> +	memset(bh->b_data, 0x00, bh->b_size);
> +
> +	mark_buffer_dirty(bh);
> +	wait_on_buffer(bh);
> +	brelse(bh);
> +
> +	return;
> +#endif
> +}
> +

Perhaps this should still be controlled by (chattr(1)) [its already
documented, just not yet implemented].

       When a file with the `s' attribute set is deleted, its blocks
	are zeroed and written back to the disk.

...at which point config option is not really neccessary.

								Pavel
-- 
When do you have a heart between your knees?
[Johanka's followup: and *two* hearts?]

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

Hey,


> Perhaps this should still be controlled by (chattr(1)) [its already
> documented, just not yet implemented].
> 
>        When a file with the `s' attribute set is deleted, its blocks
> 	are zeroed and written back to the disk.
> 
> ...at which point config option is not really neccessary.
> 

You're not the first person to mention this to me, Pádraig, brought this 
up on the day I posted. I certainly thing the 's' options should be 
implemented, however for a privacy patch I believe that the user 
shouldn't have to intervene to ensure a file is securely erased. It 
makes more sense to me, as a lazy person, that the file system should be 
set to always remove the file content... that way the user doesn't need 
to get involved.

All that said, the user's content is something that the user could be 
considered responsible for erasing themselves. The meta-data is the part 
of the file which they dont' have access to, so having privacy 
capabilities for meta-data erasure is a requirement. User data 
erasure... I can take it or leave it. I think it should be automatic if 
at all, but I'm not really that bothered about it.


peace,

--gq

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Pavel Machek]

Hi!

> >Perhaps this should still be controlled by (chattr(1)) [its already
> >documented, just not yet implemented].
> >
> >       When a file with the `s' attribute set is deleted, its blocks
> >	are zeroed and written back to the disk.
> >
> >...at which point config option is not really neccessary.
> >
> 
> You're not the first person to mention this to me, Pádraig, brought this 
> up on the day I posted. I certainly thing the 's' options should be 
> implemented, however for a privacy patch I believe that the user 
> shouldn't have to intervene to ensure a file is securely erased. It 
> makes more sense to me, as a lazy person, that the file system should be 
> set to always remove the file content... that way the user doesn't need 
> to get involved.
> 
> All that said, the user's content is something that the user could be 
> considered responsible for erasing themselves. The meta-data is the part 
> of the file which they dont' have access to, so having privacy 
> capabilities for meta-data erasure is a requirement. User data 
> erasure... I can take it or leave it. I think it should be automatic if 
> at all, but I'm not really that bothered about it.

Well, doing it on-demand means one less config option, and possibility
to include it into 2.7... It should be easy to have tiny patch forcing
that option always own for your use...
								Pavel
-- 
When do you have a heart between your knees?
[Johanka's followup: and *two* hearts?]

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

Hey,


> 
> Well, doing it on-demand means one less config option, and possibility
> to include it into 2.7... It should be easy to have tiny patch forcing
> that option always own for your use...

Works for me. Should I implement the chattr 's' handling then for the 
data blocks? Or do you think it should also include the meta-data 
deletion as well?


peace,

--gq

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Pavel Machek]

Hi!

> >Well, doing it on-demand means one less config option, and possibility
> >to include it into 2.7... It should be easy to have tiny patch forcing
> >that option always own for your use...
> 
> Works for me. Should I implement the chattr 's' handling then for the 
> data blocks? Or do you think it should also include the meta-data 
> deletion as well?

[Perhaps I got confused somewhere in between]

I think chattr +s file should be zeroed, along with its metadata. I
thought your patch already does that. If not, doing that would be
great...
								Pavel
-- 
When do you have a heart between your knees?
[Johanka's followup: and *two* hearts?]

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

Hey,

> 
> [Perhaps I got confused somewhere in between]

nope, just me.

> 
> I think chattr +s file should be zeroed, along with its metadata. I
> thought your patch already does that. If not, doing that would be
> great...

it does already zero the meta-data. I was simply asking if you think the 
whole "erase" operation should be under the control of chattr 's', or 
just a subset (i.e. only data overwriting is optional). Its clear now 
that you want the whole thing to be controled by chattr 's'. I'll knock 
that up then, and re-submit.


peace,

--gq

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Mike Fedyk]

On Wed, Feb 04, 2004 at 12:58:49AM +0000, the grugq wrote:
> it does already zero the meta-data. I was simply asking if you think the 
> whole "erase" operation should be under the control of chattr 's', or 
> just a subset (i.e. only data overwriting is optional). Its clear now 
> that you want the whole thing to be controled by chattr 's'. I'll knock 
> that up then, and re-submit.

Yes, some people want to *keep* as much information so that it can be
undeleted (think user mistakes).

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Valdis.Kletnieks]

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

On Wed, 04 Feb 2004 00:33:37 GMT, the grugq said:

> All that said, the user's content is something that the user could be 
> considered responsible for erasing themselves. The meta-data is the part 
> of the file which they dont' have access to, so having privacy 

Actually, I have encountered file systems where two successive
write() calls from userspace to the same offset in the file wouldn't
end up in the same physical location on the disk (AIX's JFS with compression).
It would LZ compress each 4K block, and then find a contiguous set of
512-byte sectors to write it.  So one write might compress down to 6 sectors
and be written in one place, the next time it doesn't compress as well
and takes 7 - so it ends up elsewhere because the previous hole was
exactly 6 - and if you try to zero it by writing a block of zeros, that
would compress down to 1 sector and fail to overwrite the others...

If we ever do a filesystem with compression, we'll have the same issue.



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

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Theodore Ts'o]

On Wed, Feb 04, 2004 at 01:43:18AM +0100, Pavel Machek wrote:
> > All that said, the user's content is something that the user could be 
> > considered responsible for erasing themselves. The meta-data is the part 
> > of the file which they dont' have access to, so having privacy 
> > capabilities for meta-data erasure is a requirement. User data 
> > erasure... I can take it or leave it. I think it should be automatic if 
> > at all, but I'm not really that bothered about it.
> 
> Well, doing it on-demand means one less config option, and possibility
> to include it into 2.7... It should be easy to have tiny patch forcing
> that option always own for your use...

The obvious thing to do would be to make it a mount option, so that
(a) recompilation is not necessary in order to use the feature, and
(b) the feature can be turned on or off on a per-filesystem feature.
In 2.6, it's possible to specify certain mount option to be specifed
by default on a per-filesystem basis (via a new field in the
superblock).  

So if you do things that way, then secure deletion would take place
either if the secure deletion flag is set (so it can be enabled on a
per-file basis), or if the filesystem is mounted with the
secure-deletion mount option.  

					- Ted

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

> 
> The obvious thing to do would be to make it a mount option, so that
> (a) recompilation is not necessary in order to use the feature, and
> (b) the feature can be turned on or off on a per-filesystem feature.
> In 2.6, it's possible to specify certain mount option to be specifed
> by default on a per-filesystem basis (via a new field in the
> superblock).  
> 
> So if you do things that way, then secure deletion would take place
> either if the secure deletion flag is set (so it can be enabled on a
> per-file basis), or if the filesystem is mounted with the
> secure-deletion mount option.  

Makes sense to me. If either the file system, or the file, are in 
'secure delete' mode, then erase everything about the file. Allowing the 
paranoid to have the option as default, and the concerned to target 
specific files. I like it.


peace,

--gq

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Bill Davidsen]

the grugq wrote:
> 
>>
>> The obvious thing to do would be to make it a mount option, so that
>> (a) recompilation is not necessary in order to use the feature, and
>> (b) the feature can be turned on or off on a per-filesystem feature.
>> In 2.6, it's possible to specify certain mount option to be specifed
>> by default on a per-filesystem basis (via a new field in the
>> superblock). 
>> So if you do things that way, then secure deletion would take place
>> either if the secure deletion flag is set (so it can be enabled on a
>> per-file basis), or if the filesystem is mounted with the
>> secure-deletion mount option.  
> 
> 
> Makes sense to me. If either the file system, or the file, are in 
> 'secure delete' mode, then erase everything about the file. Allowing the 
> paranoid to have the option as default, and the concerned to target 
> specific files. I like it.

It would be useful to have this as a directory option, so that all files 
in directory would be protected. I think wherever you do it you have to 
prevent hard links, so that unlink really removes the data.

-- 
bill davidsen <davidsen@tmr.com>
   CTO TMR Associates, Inc
   Doing interesting things with small computers since 1979

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Valdis.Kletnieks]

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

On Wed, 04 Feb 2004 12:05:07 EST, Bill Davidsen said:

> It would be useful to have this as a directory option, so that all files 
> in directory would be protected. I think wherever you do it you have to 
> prevent hard links, so that unlink really removes the data.

This of course implies that 'chattr +s' (or whatever it was) has to fail
if the link count isn't exactly one.  Also makes for lots of uglyiness
if it's a directory option - you then have to walk all the entries in the
directory and check *their* link counts.  Bad Juju doing it in the kernel
if you have a directory with a million entries - and racy as hell if you
do it in userspace.

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

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Bill Davidsen]

Valdis.Kletnieks@vt.edu wrote:
> On Wed, 04 Feb 2004 12:05:07 EST, Bill Davidsen said:
> 
> 
>>It would be useful to have this as a directory option, so that all files 
>>in directory would be protected. I think wherever you do it you have to 
>>prevent hard links, so that unlink really removes the data.
> 
> 
> This of course implies that 'chattr +s' (or whatever it was) has to fail
> if the link count isn't exactly one.

Do you disagree that the count does need to be one?

>                                       Also makes for lots of uglyiness
> if it's a directory option - you then have to walk all the entries in the
> directory and check *their* link counts.  Bad Juju doing it in the kernel
> if you have a directory with a million entries - and racy as hell if you
> do it in userspace.

I agree with everything you said, "useful" doesn't always map to "easy." 
But if you agree that the count needs to be one on files, then you could 
also fail if you tried to add it to a directory which was not empty.

In case I didn't make it clear, the use I was considering was to create 
a single directory in which created files would really go away when 
deleted. I hadn't considered doing it after files were present, what you 
say about overhead is clearly an issue. I think I could even envision 
some bizarre race conditions if the kernel had to do marking of each 
file, so perhaps it's impractical.

But what happens when the 'setgid' bit is put on a directory? At least 
in 2.4 existing files do NOT get the group set, only files newly 
created. So unless someone feels that's a bug which needs immediate 
fixing, I can point to it as a model by which the feature could be 
practically implemented.

Comment?


-- 
bill davidsen <davidsen@tmr.com>
   CTO TMR Associates, Inc
   Doing interesting things with small computers since 1979

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

> 
> But what happens when the 'setgid' bit is put on a directory? At least 
> in 2.4 existing files do NOT get the group set, only files newly 
> created. So unless someone feels that's a bug which needs immediate 
> fixing, I can point to it as a model by which the feature could be 
> practically implemented.
> 
> Comment?
> 
> 


So the proposal is specifically:

if a directory has its chattr 's' "bit" set, then all newly created 
files within that directory inherit the chattr 's' "bit".

Personally, I think that extends beyond simply privacy protection, and 
addresses how chattr values are handled by the file system. Privacy 
protection wouldn't affect the way in which the chattr values are 
handled, so if they are inherited through directories then fine... but I 
don't see this as specific to secure deletion.


--gq

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

> 
> But what happens when the 'setgid' bit is put on a directory? At least 
> in 2.4 existing files do NOT get the group set, only files newly 
> created. So unless someone feels that's a bug which needs immediate 
> fixing, I can point to it as a model by which the feature could be 
> practically implemented.

Implementing the privacy patch based on the suggestions put forward 
(chattr +s && mount options), i've hit something of a snag.

If a directory has "chattr +s" then whenever a directory entry is 
deleted, should the dirent contents be overwritten, or should only freed 
blocks be overwritten? It makes sense to me that the directory entry 
should be overwritten because it is inaccessible meta-data and exposes 
information about the file system. Since the user obviously wants the 
directory to be securely deleted, that could be construed as implying 
they want sensitive directory content securely deleted as well.



--gq

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Theodore Ts'o]

On Wed, Feb 04, 2004 at 12:14:18PM -0500, Valdis.Kletnieks@vt.edu wrote:
> > It would be useful to have this as a directory option, so that all files 
> > in directory would be protected. I think wherever you do it you have to 
> > prevent hard links, so that unlink really removes the data.
> 
> This of course implies that 'chattr +s' (or whatever it was) has to fail
> if the link count isn't exactly one.  Also makes for lots of uglyiness
> if it's a directory option - you then have to walk all the entries in the
> directory and check *their* link counts.  Bad Juju doing it in the kernel
> if you have a directory with a million entries - and racy as hell if you
> do it in userspace.

Disagree.  Unless you also want to make it illegal to establish a hard
link if the +s option is set.

A easier set of semantics is that when the inode count drops to zero,
the inode is securely deleted, but that if there are hard links, there
are hard links.  Basically the flag applies to inodes, and that in
some cases, where you create a file in a parent directory, the inode
may inherit the secure deletion flag.  But a creating a hard link
doesn't count as creating a new inode.

						- Ted

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Valdis.Kletnieks]

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

On Wed, 04 Feb 2004 18:47:54 EST, Bill Davidsen said:
> > This of course implies that 'chattr +s' (or whatever it was) has to fail
> > if the link count isn't exactly one.
> 
> Do you disagree that the count does need to be one?

I'm not prepared to say that there's no scenario where we *dont* care
how many links there are, as long as the file *does* get wiped when the
last one goes away.

The MH mail handler stores each message in a file - so a mail message is easily
stored in multiple folders by simply using multiple hard links.  I could
easily see having mail that I want to +s and go away when I remove it from
the last folder it was in....

> I agree with everything you said, "useful" doesn't always map to "easy." 
> But if you agree that the count needs to be one on files, then you could 
> also fail if you tried to add it to a directory which was not empty.

Yes you could.  The question is whether that's a desired semantic or not.

> In case I didn't make it clear, the use I was considering was to create 
> a single directory in which created files would really go away when 
> deleted. I hadn't considered doing it after files were present, what you 
> say about overhead is clearly an issue. I think I could even envision 
> some bizarre race conditions if the kernel had to do marking of each 
> file, so perhaps it's impractical.

As I said, ugly and murky....

> But what happens when the 'setgid' bit is put on a directory? At least 
> in 2.4 existing files do NOT get the group set, only files newly 
> created. So unless someone feels that's a bug which needs immediate 
> fixing, I can point to it as a model by which the feature could be 
> practically implemented.

Ahh.. but now you're suggesting a different model than "directory must
be empty".  Obviously more discussion of what we *want* it to do is needed ;)

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

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

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

Ok, I've update the secure delete patch to now check

is_secure_delete(inode)

to see if either the chattr +s bit is set, or if the superblock has 
EXT2FS_MOUNT_SECRM (which I've added) set.

I believe I've correctly modified the super.c to support a "secrm" mount 
option, but I haven't tested it so I can't say for sure. That is to say 
it compiles, but I haven't tried to run it. This rev of the patch is to 
see if the direction (and logic) of the secure delete functionality is 
in line with what people are thinking.

There is some complexity around directory files. If a directory file has 
chattr +s set, then any directory entry within that file will be erased 
when the entry is removed. If a file has chattr +s set, or the fs was 
mounted with SECRM then the directory entry is removed. I would like 
people to pay particular attention to this part of the patch, its the 
area I'm least confident with.

A directory entry's rec_len is preserved, in case we are removing the 
first entry for a directory block.

The rest of the patch is basicly unchanged from the previous patchs. I 
haven't done a patch for ext3, when this one is agreed on then I'll it 
port acroos to ext3.


peace,

--gq

[-- Attachment #2: secrm_ext2-2.6.2 --]
[-- Type: text/x-troff-man, Size: 5691 bytes --]

--- linux-2.6.2/include/linux/ext2_fs.h	2004-02-04 03:43:12.000000000 +0000
+++ linux-2.6.2/include/linux/ext2_fs.h-secrm	2004-02-05 22:08:59.000000000 +0000
@@ -310,6 +310,7 @@
 #define EXT2_MOUNT_MINIX_DF		0x0080	/* Mimics the Minix statfs */
 #define EXT2_MOUNT_NOBH			0x0100	/* No buffer_heads */
 #define EXT2_MOUNT_NO_UID32		0x0200  /* Disable 32-bit UIDs */
+#define	EXT2_MOUNT_SECRM		0x0400  /* Securely delete files */
 #define EXT2_MOUNT_XATTR_USER		0x4000	/* Extended user attributes */
 #define EXT2_MOUNT_POSIX_ACL		0x8000	/* POSIX Access Control Lists */
 
--- linux-2.6.2/fs/ext2/balloc.c	2004-02-04 03:43:42.000000000 +0000
+++ linux-2.6.2/fs/ext2-secrm/balloc.c	2004-02-05 21:02:10.000000000 +0000
@@ -173,6 +173,21 @@
 	}
 }
 
+static inline void delete_block(struct super_block *sb, unsigned long block)
+{
+	struct buffer_head	* bh;
+
+	bh = sb_getblk(sb, block);
+
+	memset(bh->b_data, 0, bh->b_size);
+
+	mark_buffer_dirty(bh);
+	wait_on_buffer(bh); /* XXX is this necessary? */
+	brelse(bh);
+
+	return;
+}
+
 /* Free given blocks, update quota and i_blocks field */
 void ext2_free_blocks (struct inode * inode, unsigned long block,
 		       unsigned long count)
@@ -240,8 +255,11 @@
 			ext2_error (sb, "ext2_free_blocks",
 				      "bit already cleared for block %lu",
 				      block + i);
-		else
+		else {
+			if (is_secure_delete(inode))
+				delete_block(inode->i_sb, block + i);
 			group_freed++;
+		}
 	}
 
 	mark_buffer_dirty(bitmap_bh);
--- linux-2.6.2/fs/ext2/dir.c	2004-02-04 03:43:56.000000000 +0000
+++ linux-2.6.2/fs/ext2-secrm/dir.c	2004-02-05 22:01:00.000000000 +0000
@@ -530,6 +530,7 @@
 {
 	struct address_space *mapping = page->mapping;
 	struct inode *inode = mapping->host;
+	struct inode *dino;
 	char *kaddr = page_address(page);
 	unsigned from = ((char*)dir - kaddr) & ~(ext2_chunk_size(inode)-1);
 	unsigned to = ((char*)dir - kaddr) + le16_to_cpu(dir->rec_len);
@@ -555,9 +556,24 @@
 		BUG();
 	if (pde)
 		pde->rec_len = cpu_to_le16(to-from);
-	dir->inode = 0;
+
+	dino = iget(inode->i_sb, dir->inode);
+	if (!dino || (!is_secure_delete(dino) && !is_secure_delete(inode))) {
+		dir->inode = 0;
+		inode->i_ctime = inode->i_mtime = CURRENT_TIME;
+	} else {
+		unsigned short rec_len = dir->rec_len;
+
+		memset(dir, 0, dir->rec_len);
+		dir->rec_len = rec_len;
+	}
+
+	if (dino)
+		iput(dino);
+
 	err = ext2_commit_chunk(page, from, to);
-	inode->i_ctime = inode->i_mtime = CURRENT_TIME;
+
+ 	/* XXX should this be in the if (!is_secure_delete()) above? */
 	EXT2_I(inode)->i_flags &= ~EXT2_BTREE_FL;
 	mark_inode_dirty(inode);
 out:
--- linux-2.6.2/fs/ext2/ext2.h	2004-02-05 20:46:40.000000000 +0000
+++ linux-2.6.2/fs/ext2-secrm/ext2.h	2004-02-05 20:45:25.000000000 +0000
@@ -79,6 +79,16 @@
 	return container_of(inode, struct ext2_inode_info, vfs_inode);
 }
 
+static inline int is_secure_delete(struct inode *inode)
+{
+	/* expanded for readibility */
+	if (EXT2_I(inode)->i_flags & EXT2_SECRM_FL)
+		return 1;
+	if (test_opt(inode->i_sb, SECRM))
+		return 1;
+	return 0;
+}
+
 /* balloc.c */
 extern int ext2_bg_has_super(struct super_block *sb, int group);
 extern unsigned long ext2_bg_num_gdb(struct super_block *sb, int group);
--- linux-2.6.2/fs/ext2/inode.c	2004-02-04 03:43:09.000000000 +0000
+++ linux-2.6.2/fs/ext2-secrm/inode.c	2004-02-05 22:18:56.000000000 +0000
@@ -64,6 +64,36 @@
 		ext2_discard_prealloc(inode);
 }
 
+static inline void delete_inode(struct inode *inode)
+{
+	if (!is_secure_delete(inode))
+		EXT2_I(inode)->i_dtime = get_seconds();
+	else {
+		inode->i_mode   = 0;
+		inode->i_uid    = 0;
+		inode->i_gid    = 0;
+		inode->i_nlink  = 0;
+		inode->i_atime.tv_sec  = 0;
+		inode->i_atime.tv_nsec  = 0;
+		inode->i_ctime.tv_sec  = 0;
+		inode->i_ctime.tv_nsec  = 0;
+		inode->i_mtime.tv_sec  = 0;
+		inode->i_mtime.tv_nsec  = 0;
+		EXT2_I(inode)->i_dtime = 0;
+		EXT2_I(inode)->i_faddr = 0;
+		EXT2_I(inode)->i_frag_no       = 0;
+		EXT2_I(inode)->i_frag_size     = 0;
+		EXT2_I(inode)->i_file_acl      = 0;
+		inode->i_generation     = 0;
+	}
+}
+
+static inline void delete_blocks(struct inode *inode)
+{
+	inode->i_blocks = 0;
+	memset(EXT2_I(inode)->i_data, 0, sizeof(EXT2_I(inode)->i_data));
+}
+
 /*
  * Called at the last iput() if i_nlink is zero.
  */
@@ -71,13 +101,21 @@
 {
 	if (is_bad_inode(inode))
 		goto no_delete;
-	EXT2_I(inode)->i_dtime	= get_seconds();
+	delete_inode(inode);
 	mark_inode_dirty(inode);
 	ext2_update_inode(inode, inode_needs_sync(inode));
 
 	inode->i_size = 0;
 	if (inode->i_blocks)
 		ext2_truncate (inode);
+
+	if (is_secure_delete(inode)) {
+		EXT2_I(inode)->i_flags = 0;
+
+		delete_blocks(inode);
+		mark_inode_dirty(inode);
+		ext2_update_inode(inode, inode_needs_sync(inode));
+	}
 	ext2_free_inode (inode);
 
 	return;
--- linux-2.6.2/fs/ext2/super.c	2004-02-04 03:44:04.000000000 +0000
+++ linux-2.6.2/fs/ext2-secrm/super.c	2004-02-05 22:04:17.000000000 +0000
@@ -270,7 +270,7 @@
 	Opt_bsd_df, Opt_minix_df, Opt_grpid, Opt_nogrpid,
 	Opt_resgid, Opt_resuid, Opt_sb, Opt_err_cont, Opt_err_panic, Opt_err_ro,
 	Opt_nouid32, Opt_check, Opt_nocheck, Opt_debug, Opt_oldalloc, Opt_orlov, Opt_nobh,
-	Opt_user_xattr, Opt_nouser_xattr, Opt_acl, Opt_noacl,
+	Opt_user_xattr, Opt_nouser_xattr, Opt_acl, Opt_noacl, Opt_secrm,
 	Opt_ignore, Opt_err,
 };
 
@@ -299,6 +299,7 @@
 	{Opt_nouser_xattr, "nouser_xattr"},
 	{Opt_acl, "acl"},
 	{Opt_noacl, "noacl"},
+	{Opt_secrm, "secrm"},
 	{Opt_ignore, "grpquota"},
 	{Opt_ignore, "noquota"},
 	{Opt_ignore, "quota"},
@@ -410,6 +411,9 @@
 			printk("EXT2 (no)acl options not supported\n");
 			break;
 #endif
+		case Opt_secrm:
+			set_opt(sbi->s_mount_opt, SECRM);
+			break;
 		case Opt_ignore:
 			break;
 		default:

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Jamie Lokier]

Valdis.Kletnieks@vt.edu wrote:
> Actually, I have encountered file systems where two successive
> write() calls from userspace to the same offset in the file wouldn't
> end up in the same physical location on the disk (AIX's JFS with compression).

See also:

    - ext3 with data journalling

    - reiser4 with wandering logs

    - experimental ext? patches for tail-packing small files

-- Jamie

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Hans Reiser]

Jamie Lokier wrote:

>Valdis.Kletnieks@vt.edu wrote:
>  
>
>>Actually, I have encountered file systems where two successive
>>write() calls from userspace to the same offset in the file wouldn't
>>end up in the same physical location on the disk (AIX's JFS with compression).
>>    
>>
>
>See also:
>
>    - ext3 with data journalling
>
>    - reiser4 with wandering logs
>
>    - experimental ext? patches for tail-packing small files
>
>-- Jamie
>-
>To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>Please read the FAQ at  http://www.tux.org/lkml/
>
>
>  
>
reiser4 probably does not need secure deletion as much as others, 
because once the encryption plugins are debugged we will most likely 
encourage users to use encryption by default.  Perhaps someone will show 
the error in my thinking though, I am not trying to be rigid here....

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

Well, I think secure deletion should be an option for everyone. Using 
encryption is a data hiding technique, you prevent people for detemining 
what sort of data is being stored there. Now, admittedly I dont know at 
what level the reiser4 encryption appears, but I would think its safer 
to have complete erasure when a file deleted regardless of how well 
protected its contents were.

just a thought.

--gq

Hans Reiser wrote:
> Jamie Lokier wrote:
> 
>> Valdis.Kletnieks@vt.edu wrote:
>>  
>>
>>> Actually, I have encountered file systems where two successive
>>> write() calls from userspace to the same offset in the file wouldn't
>>> end up in the same physical location on the disk (AIX's JFS with 
>>> compression).
>>>   
>>
>>
>> See also:
>>
>>    - ext3 with data journalling
>>
>>    - reiser4 with wandering logs
>>
>>    - experimental ext? patches for tail-packing small files
>>
>> -- Jamie
>> -
>> To unsubscribe from this list: send the line "unsubscribe 
>> linux-kernel" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>> Please read the FAQ at  http://www.tux.org/lkml/
>>
>>
>>  
>>
> reiser4 probably does not need secure deletion as much as others, 
> because once the encryption plugins are debugged we will most likely 
> encourage users to use encryption by default.  Perhaps someone will show 
> the error in my thinking though, I am not trying to be rigid here....
> 

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Jamie Lokier]

Hans Reiser wrote:
> reiser4 probably does not need secure deletion as much as others, 
> because once the encryption plugins are debugged we will most likely 
> encourage users to use encryption by default.  Perhaps someone will show 
> the error in my thinking though, I am not trying to be rigid here....

With encrypted block devices, there is the possibility that someone
may discover your key, or gain access to your computer (e.g. steal
your laptop while it's switched on, or someone puts a gun to your head
and makes you enter the key).

If someone gets access you might be glad you securely deleted some
files by overwriting the blocks.

When encryption is implemented in the filesystem itself, this is
preventable.

There is a cryptographic way to ensure deleted files cannot be
recovered even when someone knows the filesystem key, without needing
to overwrite the files.  This is even better than overwriting, because
it resists signal processing methods on the hard disk platter, and is
effective with virtual devices where overwriting does not actually
erase the original data (e.g. VMware or Bochs copy-on-write disk
image; LVM snapshots; some SAN devices).

Thanks in advance for the implementation :)

-- Jamie

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Bill Davidsen]

Valdis.Kletnieks@vt.edu wrote:
> On Wed, 04 Feb 2004 18:47:54 EST, Bill Davidsen said:
> 
>>>This of course implies that 'chattr +s' (or whatever it was) has to fail
>>>if the link count isn't exactly one.
>>
>>Do you disagree that the count does need to be one?
> 
> 
> I'm not prepared to say that there's no scenario where we *dont* care
> how many links there are, as long as the file *does* get wiped when the
> last one goes away.
> 
> The MH mail handler stores each message in a file - so a mail message is easily
> stored in multiple folders by simply using multiple hard links.  I could
> easily see having mail that I want to +s and go away when I remove it from
> the last folder it was in....

This is then a question of what we want it to do, and I assume that 
either of the obvious behaviours is not only possibe but practical. The 
question is if the objective is to make the data go away when the last 
link is removed, or to make removal of sach a file (unlink) remove the 
contents at the time of the unlink. I think the latter clearly implies 
allowing a single link to the inode.

Since I could make a case for either, I'd like to hear other feedback.
> 
> 
>>I agree with everything you said, "useful" doesn't always map to "easy." 
>>But if you agree that the count needs to be one on files, then you could 
>>also fail if you tried to add it to a directory which was not empty.
> 
> 
> Yes you could.  The question is whether that's a desired semantic or not.

Given my use of the 'setgid' bit as a possible model, I would say that 
having new files created with the attribute is useful, and the user 
putting the attribute on the directory should control the content at the 
time the attribute is set. In other words it will be as useful if we 
just make it apply on files as they are created.
> 
> 
>>In case I didn't make it clear, the use I was considering was to create 
>>a single directory in which created files would really go away when 
>>deleted. I hadn't considered doing it after files were present, what you 
>>say about overhead is clearly an issue. I think I could even envision 
>>some bizarre race conditions if the kernel had to do marking of each 
>>file, so perhaps it's impractical.
> 
> 
> As I said, ugly and murky....

And not needed.
> 
> 
>>But what happens when the 'setgid' bit is put on a directory? At least 
>>in 2.4 existing files do NOT get the group set, only files newly 
>>created. So unless someone feels that's a bug which needs immediate 
>>fixing, I can point to it as a model by which the feature could be 
>>practically implemented.
> 
> 
> Ahh.. but now you're suggesting a different model than "directory must
> be empty".  Obviously more discussion of what we *want* it to do is needed ;)

Yes, the person setting the attribute can control this. Unlike the 
setgid bit it can't be done (currently) as a part of creat().


-- 
bill davidsen <davidsen@tmr.com>
   CTO TMR Associates, Inc
   Doing interesting things with small computers since 1979

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Hans Reiser]

There is an extensive literature on how you can recover deleted files 
from media that has been erased a dozen times, but breaking encryption 
is harder.  It is more secure to not put the data on disk unencrypted at 
all is my point.....

Hans

the grugq wrote:

> Well, I think secure deletion should be an option for everyone. Using 
> encryption is a data hiding technique, you prevent people for 
> detemining what sort of data is being stored there. Now, admittedly I 
> dont know at what level the reiser4 encryption appears, but I would 
> think its safer to have complete erasure when a file deleted 
> regardless of how well protected its contents were.
>
> just a thought.
>

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

Sure, but to a large extent it depends on your threat model. If you say 
"an extremely well funded government entity wants to examine your hard 
drive" then they will have access to insane technologies like electron 
microscopes. This makes any software solution to secure deletion 
practically impossible (if we trust the literature).

If, on the other hand, we have a threat model of, say, the police, then 
things are very different. In the UK, there is a law which requires you 
to turn over your encryption keys when the court demands them. The 
police have a tactic for extracting keys which involves physical 
violence and intimidation. These are very effective against encryption. 
However, the police do not have access to hardware based analysis 
technologies, they are just too expensive. So, while they can recover 
something that has been encrypted, they can't recover something that has 
been securely deleted. (Not without begging the .gov to perform a 
hardware analysis, something which would be quite unlikely in the normal 
course of events).

The majority of forensic analysis is performed with software tools on a 
bit image of the hard drive. If this bit image doesn't contain the data, 
the software tools won't see it, and the forensic analysis will fail. I 
would suggest adding secure deletion, because it does provide a pretty 
good level of protection. It is not a 100% solution, but neither is 
encryption. The two in combination are complementary technologies.


peace,

--gq


Hans Reiser wrote:
> There is an extensive literature on how you can recover deleted files 
> from media that has been erased a dozen times, but breaking encryption 
> is harder.  It is more secure to not put the data on disk unencrypted at 
> all is my point.....
> 
> Hans
> 
> the grugq wrote:
> 
>> Well, I think secure deletion should be an option for everyone. Using 
>> encryption is a data hiding technique, you prevent people for 
>> detemining what sort of data is being stored there. Now, admittedly I 
>> dont know at what level the reiser4 encryption appears, but I would 
>> think its safer to have complete erasure when a file deleted 
>> regardless of how well protected its contents were.
>>
>> just a thought.
>>
> 
> 

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Albert Cahalan]

Hans Reiser writes:

> There is an extensive literature on how you can recover
> deleted files from media that has been erased a dozen
> times,

I doubt this is true in any way that matters.

Unless you get REALLY lucky with bad sector
substitution and you know the secret
vendor-specific drive commands to fetch bad
sectors, you'll need the physical hardware.

   no hardware  --->  no data recovery

Given that you do have the physical hardware,
how are you going to read it? You'll need
some equipment that will cost you many millions
of dollars. So this isn't going to be anybody
but the CIA, NSA, or non-US equivelent. They
won't bother very often; even a "black" budget
is limited. Are you so sure you're worth it?

Does the "extensive literature" cover drives
made in the last year? (decade?) These days,
manufacturers are using extremely thin layers
of surface material over an inert substrate.
Magnetic domains flip in an all-or-nothing
fashion; the old recovery methods rely on
finding some buried domains that didn't flip.
With the layers getting damn thin, I doubt
any will exist. There just won't be any
residual signal from previous writes, and so
the recovery methods have nothing to work with.

> but breaking encryption is harder.  It is more
> secure to not put the data on disk unencrypted at all
> is my point.....

This leads to one method of implementing the
secure deletion flag. At boot, generate a
random key for the log file. At file creation,
generate a random key for the file body and
inode. (these are internal to the filesystem)
When you want to destroy something, wipe the key.
Remember to flush and regenerate the log file.

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Jamie Lokier]

the grugq wrote:
> If, on the other hand, we have a threat model of, say, the police, then 
> things are very different. In the UK, there is a law which requires you 
> to turn over your encryption keys when the court demands them. The 
> police have a tactic for extracting keys which involves physical 
> violence and intimidation. These are very effective against encryption. 

This is how to implement secure deletion cryptographically:

   - Each time a file is created, choose a random number.

   - Encrypt the number with your filesystem key and store the
     encrypted version in the inode.

   - The number is used for encrypting that file.

Secure deletion is then a matter of securely deleting the inode.
The file data does not have to be overwritten.

This is secure against many attacks that "secure deletion" by
overwriting is weak against.  This includes electron microscopes
looking at the data, and UK law.  (The police can demand your
filesystem key, but nobody knows the random number that belonged to a
new-deleted inode).

There is a chance the electron microscope may recover the number from
the securely deleted inode.  That is the weakness of this system,
therefore the inode data should be very thoroughly erased or itself
subject to careful cryptographic hding.

-- Jamie

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

Yes, the allocation of the inode and data blocks should be randomized 
for security, but that would lead to performance impacts. Implementing 
that should definately be a compile time option.

I would advocate erasing all meta-data on a file, and also erasing the 
data. The end-user can be responsible for erasing the data, they can 
access it with write(), but they can't access the meta-data (not without 
directly accessing the file system). Thats why I'm putting these patches 
forward. The file system should be responsible for removing meta-data 
when a file is deleted. This secure deletion doesn't have to incorporate 
data block erasure (although my implemenation does).

Your suggestion would certainly work, but I think the performance impact 
of using random inodes and data blocks would dissuade many from having 
it enabled by default. Simple secure deletion of the data and meta-data 
would have a lower impact, and be more likely to be used on more file 
systems.


peace,

--gq

> 
> This is how to implement secure deletion cryptographically:
> 
>    - Each time a file is created, choose a random number.
> 
>    - Encrypt the number with your filesystem key and store the
>      encrypted version in the inode.
> 
>    - The number is used for encrypting that file.
> 
> Secure deletion is then a matter of securely deleting the inode.
> The file data does not have to be overwritten.
> 
> This is secure against many attacks that "secure deletion" by
> overwriting is weak against.  This includes electron microscopes
> looking at the data, and UK law.  (The police can demand your
> filesystem key, but nobody knows the random number that belonged to a
> new-deleted inode).
> 
> There is a chance the electron microscope may recover the number from
> the securely deleted inode.  That is the weakness of this system,
> therefore the inode data should be very thoroughly erased or itself
> subject to careful cryptographic hding.

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Jamie Lokier]

the grugq wrote:
> Yes, the allocation of the inode and data blocks should be randomized 
> for security, but that would lead to performance impacts. Implementing 
> that should definately be a compile time option.

What do you mean?

I haven't mentioned randomising block allocations at all.

The random number is an encryption key, private to the inode, used to
encrypt the data blocks.  The blocks are allocated efficiently as usual.

> Your suggestion would certainly work, but I think the performance impact 
> of using random inodes and data blocks would dissuade many from having 
> it enabled by default. Simple secure deletion of the data and meta-data 
> would have a lower impact, and be more likely to be used on more file 
> systems.

My suggestion would be much more efficient than yours: for every file
created and deleted, you do twice the I/O I do.

-- Jamie

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[the grugq]

> 
> What do you mean?
> 
> I haven't mentioned randomising block allocations at all.
> 
> The random number is an encryption key, private to the inode, used to
> encrypt the data blocks.  The blocks are allocated efficiently as usual.
> 

I didn't understand your proposal. nm.

As I now understand, you are proposing a file system which has per file 
encryption where the key is stored in the inode. The inode is then the 
only location with senstive data which needs to be removed.

What about directory files? That is, how would you propose handling the 
directory entries of deleted files?

Also, this proposal seems to me more related to how to implement an 
encrypted file system, than how to implement secure deletion on existing 
file systems.

> 
> My suggestion would be much more efficient than yours: for every file
> created and deleted, you do twice the I/O I do.

Sorry, per file encryption is more efficient than deffered block writes 
after deletion? What you are proposing is unrelated to secure deletion. 
Its an encrypted file system implementation. Comparing efficiency 
between secure deletion on ext2, for example, and encrypted files on 
some unimplemented file system doesn't make sense.

Now, given that my comments were on what I thought you were proposing 
(randomly allocating inodes and blocks to prevent an analyst being able 
to piece a file back toghether via guess work) not what you actually 
were proposing (an encrypted file system implementation), ignore the 
previous email.


peace,

--gq

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Jamie Lokier]

the grugq wrote:
> As I now understand, you are proposing a file system which has per file 
> encryption where the key is stored in the inode. The inode is then the 
> only location with senstive data which needs to be removed.

Yes.

> Also, this proposal seems to me more related to how to implement an 
> encrypted file system, than how to implement secure deletion on existing 
> file systems.

Not really, this is pointing out an alternative means of secure
deletion _if_ you have encryption.  The points I wanted to make were,
most important first:

   - Overwriting data does not always do what you think it does.
     Several block devices _do not_ overwrite the same storage blocks.
     Thus it is dangerous to call something "secure deletion"
     when it might not do anything at all.

   - Filesystems on top of encrypted block devices _do_ need
     overwriting-based secure deletion, if they are of the type where
     the block encryption key is derived from the block offset and device
     key only.

   - Eraseable per-file keys may be a more secure way of destroying
     data than overwriting data on a magnetic medium.

-- Jamie

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Hans Reiser]

Exactly right.

Hans

Jamie Lokier wrote:

>the grugq wrote:
>  
>
>>If, on the other hand, we have a threat model of, say, the police, then 
>>things are very different. In the UK, there is a law which requires you 
>>to turn over your encryption keys when the court demands them. The 
>>police have a tactic for extracting keys which involves physical 
>>violence and intimidation. These are very effective against encryption. 
>>    
>>
>
>This is how to implement secure deletion cryptographically:
>
>   - Each time a file is created, choose a random number.
>
>   - Encrypt the number with your filesystem key and store the
>     encrypted version in the inode.
>
>   - The number is used for encrypting that file.
>
>Secure deletion is then a matter of securely deleting the inode.
>The file data does not have to be overwritten.
>
>This is secure against many attacks that "secure deletion" by
>overwriting is weak against.  This includes electron microscopes
>looking at the data, and UK law.  (The police can demand your
>filesystem key, but nobody knows the random number that belonged to a
>new-deleted inode).
>
>There is a chance the electron microscope may recover the number from
>the securely deleted inode.  That is the weakness of this system,
>therefore the inode data should be very thoroughly erased or itself
>subject to careful cryptographic hding.
>
>-- Jamie
>-
>To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>Please read the FAQ at  http://www.tux.org/lkml/
>
>
>  
>

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Hans Reiser]

the grugq wrote:

>
>>
>> What do you mean?
>>
>> I haven't mentioned randomising block allocations at all.
>>
>> The random number is an encryption key, private to the inode, used to
>> encrypt the data blocks.  The blocks are allocated efficiently as usual.
>>
>
> I didn't understand your proposal. nm.
>
> As I now understand, you are proposing a file system which has per 
> file encryption where the key is stored in the inode. The inode is 
> then the only location with senstive data which needs to be removed.
>
> What about directory files? That is, how would you propose handling 
> the directory entries of deleted files?
>
> Also, this proposal seems to me more related to how to implement an 
> encrypted file system, than how to implement secure deletion on 
> existing file systems.

It will be easy to code on reiser4 which has encryption being built into it.

>
>>
>> My suggestion would be much more efficient than yours: for every file
>> created and deleted, you do twice the I/O I do.
>
>
> Sorry, per file encryption is more efficient than deffered block 
> writes after deletion? 

Oh yes.  Way so.

> What you are proposing is unrelated to secure deletion. Its an 
> encrypted file system implementation. Comparing efficiency between 
> secure deletion on ext2, for example, and encrypted files on some 
> unimplemented file system doesn't make sense.
>
> Now, given that my comments were on what I thought you were proposing 
> (randomly allocating inodes and blocks to prevent an analyst being 
> able to piece a file back toghether via guess work) not what you 
> actually were proposing (an encrypted file system implementation), 
> ignore the previous email.
>
>
> peace,
>
> --gq
>
>

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Hans Reiser]

Jamie Lokier wrote:

>
>   - Eraseable per-file keys may be a more secure way of destroying
>     data than overwriting data on a magnetic medium.
>
>
>  
>
I agree.

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Pavel Machek]

Hi!

> > As I now understand, you are proposing a file system which has per file 
> > encryption where the key is stored in the inode. The inode is then the 
> > only location with senstive data which needs to be removed.
> 
> Yes.
> 
> > Also, this proposal seems to me more related to how to implement an 
> > encrypted file system, than how to implement secure deletion on existing 
> > file systems.
> 
> Not really, this is pointing out an alternative means of secure
> deletion _if_ you have encryption.  The points I wanted to make were,
> most important first:
> 
>    - Overwriting data does not always do what you think it does.
>      Several block devices _do not_ overwrite the same storage blocks.
>      Thus it is dangerous to call something "secure deletion"
>      when it might not do anything at all.

But you have same vulnerability, crypto does not help here. If your
i-node happens to be put on other place, attacker still gets the key
intact etc.

There's not much you can do. [It may be even worse with that
crypto... If you kick the table while your top-secret .mpg.tgz collection
is accessed, you are likely to cause bad sector within i-node,
attacker can get the key, and decrypt it all. With on-place
overwriting he only gets one block.] 
								Pavel
-- 
When do you have a heart between your knees?
[Johanka's followup: and *two* hearts?]

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Jamie Lokier]

Pavel Machek wrote:
> >    - Overwriting data does not always do what you think it does.
> >      Several block devices _do not_ overwrite the same storage blocks.
> >      Thus it is dangerous to call something "secure deletion"
> >      when it might not do anything at all.
> 
> But you have same vulnerability, crypto does not help here. If your
> i-node happens to be put on other place, attacker still gets the key
> intact etc.

Yes, you're right.  I wanted to draw attention to the fact that ext2's
"secure deletion" attribute, when implemented, can be misleading.  I
should have pointed out that an inode-private key has the same weakness.

> There's not much you can do. [It may be even worse with that
> crypto... If you kick the table while your top-secret .mpg.tgz collection
> is accessed, you are likely to cause bad sector within i-node,
> attacker can get the key, and decrypt it all. With on-place
> overwriting he only gets one block.] 

There is something which can help:

First, the idea of an inode private key, which is itself encrypted by
a whole filesystem key, may be seen as a two level tree structure (the
filesystem key is its root).  You can also have deeper key structures.
The important thing is that without the root key, you cannot follow
any path to the tree's branches.  The key tree does not have to be the
same as the directory tree, in fact it's better if it isn't, so you
can keep the key tree balanced.

You can regularly change branch keys within the filesystem, updating
all the dependent keys when that's done.  That can be done
incrementally, as you make changes to the flesystem.  So for example,
whenever you want to erase an inode (secure deletion), you need to
modify its parent key in the key tree and re-encrypt all the inode
key's siblings with the new parent key.  Repeat all the way to the
root.

If you do those updates every time, then you confine the "snapshotting
block device" weakness to the problem of destroying old versions of
the root key - for which you should insist on choosing an appropriate
device.  You might also use multiple root keys, so that a single
remapped block on a hard disk which is used to hold the root key(s) is
not enough to decrypt old versions of the filesystem.

-- Jamie

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Edward Shishkin]

Hans Reiser wrote:
> 
> Exactly right.
> 
> Hans
> 
> Jamie Lokier wrote:
> 
> >the grugq wrote:
> >
> >
> >>If, on the other hand, we have a threat model of, say, the police, then
> >>things are very different. In the UK, there is a law which requires you
> >>to turn over your encryption keys when the court demands them. The
> >>police have a tactic for extracting keys which involves physical
> >>violence and intimidation. These are very effective against encryption.
> >>
> >>
> >
> >This is how to implement secure deletion cryptographically:
> >
> >   - Each time a file is created, choose a random number.
> >
> >   - Encrypt the number with your filesystem key and store the
> >     encrypted version in the inode.
> >
> >   - The number is used for encrypting that file.
> >
> >Secure deletion is then a matter of securely deleting the inode.
> >The file data does not have to be overwritten.
> >
> >This is secure against many attacks that "secure deletion" by
> >overwriting is weak against.  This includes electron microscopes
> >looking at the data, and UK law.  (The police can demand your
> >filesystem key, but nobody knows the random number that belonged to a
> >new-deleted inode).

Also they will demand this random number since the court can consider it
as a part of your secret key. So just delete your secret key without creating
meaningless infrastructure ;)
Edward.

> >
> >There is a chance the electron microscope may recover the number from
> >the securely deleted inode.  That is the weakness of this system,
> >therefore the inode data should be very thoroughly erased or itself
> >subject to careful cryptographic hding.
> >
> >-- Jamie
> >-
> >To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> >the body of a message to majordomo@vger.kernel.org
> >More majordomo info at  http://vger.kernel.org/majordomo-info.html
> >Please read the FAQ at  http://www.tux.org/lkml/
> >
> >
> >
> >

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Hans Reiser]

Edward Shishkin wrote:

>
>Also they will demand this random number since the court can consider it
>as a part of your secret key. So just delete your secret key without creating
>meaningless infrastructure ;)
>Edward.
>  
>
This is a good point.  A court may be able to demand your pass phrase, 
but if you rm the key itself, they can hardly expect you to have 
memorized that.....

RE: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Robert White]

At which point, in the presence of the theoretical mount option, it becomes
easy to reduce the work load to "a long list of block operations" by making
the shredding unconditional.

That is, instead of thinking of it as shredding a file, the (arbitrarily
named) "zerofree" mount option is passed and every block that is released
from active file system use is zeroed.  E.g. file blocks, directory blocks,
attribute blocks, everything.  That just takes (at the worst) a list/queue
and a block-write of a block-sized page containing all zeros (or, better
yet, an optionally-user-supplied squeegee pattern.)  So take/make the
free_block() routine and make it submit a "dirty block" to the I/O buffering
system.  If the block is immediately re-used then even the write expense
amortizes to near zero for clearing that block (or unwritten fragment).

The down side of the simple form comes up when the user unlinks that 20 gig
file.

And of course there is no such thing as un-erase for such a media.

On the more positive side this would be _*outstanding*_ for my NV-RAM
keychain drive where the files are warranted to be small and I don't want
some random person who finds my lost keychain even able to guess about that
pesky project I was working on last month.

Meh... 8-)

Rob.

-----Original Message-----
From: linux-kernel-owner@vger.kernel.org
[mailto:linux-kernel-owner@vger.kernel.org] On Behalf Of Theodore Ts'o
Sent: Tuesday, February 03, 2004 10:30 PM
To: Pavel Machek
Cc: the grugq; linux-kernel@vger.kernel.org
Subject: Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

On Wed, Feb 04, 2004 at 01:43:18AM +0100, Pavel Machek wrote:
> > All that said, the user's content is something that the user could be 
> > considered responsible for erasing themselves. The meta-data is the part

> > of the file which they dont' have access to, so having privacy 
> > capabilities for meta-data erasure is a requirement. User data 
> > erasure... I can take it or leave it. I think it should be automatic if 
> > at all, but I'm not really that bothered about it.
> 
> Well, doing it on-demand means one less config option, and possibility
> to include it into 2.7... It should be easy to have tiny patch forcing
> that option always own for your use...

The obvious thing to do would be to make it a mount option, so that
(a) recompilation is not necessary in order to use the feature, and
(b) the feature can be turned on or off on a per-filesystem feature.
In 2.6, it's possible to specify certain mount option to be specifed
by default on a per-filesystem basis (via a new field in the
superblock).  

So if you do things that way, then secure deletion would take place
either if the secure deletion flag is set (so it can be enabled on a
per-file basis), or if the filesystem is mounted with the
secure-deletion mount option.  

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

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Jamie Lokier]

Robert White wrote:
> On the more positive side this would be _*outstanding*_ for my NV-RAM
> keychain drive where the files are warranted to be small and I don't want
> some random person who finds my lost keychain even able to guess about that
> pesky project I was working on last month.

An encrypted and/or steganographic filesystem would be much better for
your NVRAM keychain drive, because that hides your files even when you
_haven't_ deleted them.

-- Jamie

RE: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Robert White]

For some forms of better, yes.  8-)  The disposable inode key and the fully
encrypted file system are clearly more potent and better.  Nice and
bank-vault.  Sometimes though, you just want and only need a $3 chain on
your door to keep out the neighbor children.  Were the fully vault-like
option available you can bet I'd partition my keychain to do both.
Meanwhile...

A generic mount option that does the write-over-on-free operation could be
easily ported to/integrated with the other file-systems like, say, vfat.
Which, in turn, would continue to let me use my keychain to carry things to
non-linux environments while giving me some anti-leave-behind protection
when I delete things (in linux).  (So I am evil in trying to get the
poor-man's feature in for general consideration. 8-)

"Truly secure" is a good thing but "casually secure and pervasive" is
relatively important too.

Consider the simple "strings /dev/sda1" "attack" on a raw device.  Even with
the VMWare journaling and such and its implications, from inside the
environment write-over-on-erase would go a long way to block the stupid
leave behind vulnerability.

[Discussion-Fork]

I have actually been looking into the removable media issues more than
anything else.  My exact area of focus has been the idea of "local root" for
a (removable) file system.  Basically it seems that there needs to be a way
to communicate a list of otherwise unassigned user ID numbers into the
kernel.  Then when a flagged file system were mounted, the real user ID
numbers in the file system image would map to known-unused numbers.  The
root-on-disk would become something arbitrary like 21901 and then user ID
21901 would enjoy root-like write permissions on that media, but no other
media in the system.  All the other UID/GID numbers would likewise be
translated to unused "real" nubers.  This way applications could "run
setuid" and such but in their own sandbox, leaving the file system
internally consistent after use, but never endangering the overall system
security state.  (e.g. setuid root is bad, setuid 21901 not so much. 8-)

Think "application cards" or, say, student terminals where the whole OS is
installed but the portable (firewire/usb/etc) drives the students use would
remain consistent and capable of running their apps.

I have many thoughts about the requirements. A callback daemon a-la hotplug
to coordinate UID and GID pools.  A shim over the "real" file system calls
(kind of like the way loop shims as a block device) to do the bidirectional
translations of ID number.  That sort of thing.

I could see wanting to drop signatures and otherwise "taint" the file system
image with a temporary/scratch file full of information during this
application, or god knows what else.  Casual wipe then applies and is highly
utilitarian because you can unlink-on-unmount and rely on the buffer flush
to do the dirty work, rather than have a window of time when the file system
is mounted but the scratch space is being de-constructed.  Yes, not Big-S
secure, but "highly utilitarian" if for no reason other than preventing an
fsck from casually restoring a scratch file with valid contents.

[/Discussion-Fork]

So meanwhile, having a simple zero-out/expunge on last unlink (ne block
free) flag for a whole file system serves the dual purpose of mistake
prevention and exceedingly trivial security, at the sole cost of "no
norton-grade casual un-erase".

Regardless of the "I don't want the government recovering evidence of my
illicit activities" elements to be gained by a cryptographically complete
solution to secure file removal; there is real and immediate utility to a
simple wipe-on-erase.  More-so if it were to become "expected to be
available" on all supported filesystem types.


Rob.



-----Original Message-----
From: Jamie Lokier [mailto:jamie@shareable.org] 
Sent: Thursday, February 12, 2004 7:41 PM
To: Robert White
Cc: 'Theodore Ts'o'; 'Pavel Machek'; 'the grugq';
linux-kernel@vger.kernel.org
Subject: Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

Robert White wrote:
> On the more positive side this would be _*outstanding*_ for my NV-RAM
> keychain drive where the files are warranted to be small and I don't want
> some random person who finds my lost keychain even able to guess about
that
> pesky project I was working on last month.

An encrypted and/or steganographic filesystem would be much better for
your NVRAM keychain drive, because that hides your files even when you
_haven't_ deleted them.

-- Jamie

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Pavel Machek]

Hi!

> At which point, in the presence of the theoretical mount option, it becomes
> easy to reduce the work load to "a long list of block operations" by making
> the shredding unconditional.
> 
> That is, instead of thinking of it as shredding a file, the (arbitrarily
> named) "zerofree" mount option is passed and every block that is released
> from active file system use is zeroed.  E.g. file blocks, directory blocks,
> attribute blocks, everything.  That just takes (at the worst) a list/queue
> and a block-write of a block-sized page containing all zeros (or, better
> yet, an optionally-user-supplied squeegee pattern.)  So take/make the
> free_block() routine and make it submit a "dirty block" to the I/O buffering
> system.  If the block is immediately re-used then even the write expense
> amortizes to near zero for clearing that block (or unwritten
> fragment).

I see a small problem with that: some "interesting" data, such as file
names, are smaller than a block. With this kind of implementation,
you'd never wipe those.
								Pavel
[un-erase no longer works even on ext3, that's nothing new]

-- 
When do you have a heart between your knees?
[Johanka's followup: and *two* hearts?]

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Bill Davidsen]

Jamie Lokier wrote:
> Robert White wrote:
> 
>>On the more positive side this would be _*outstanding*_ for my NV-RAM
>>keychain drive where the files are warranted to be small and I don't want
>>some random person who finds my lost keychain even able to guess about that
>>pesky project I was working on last month.
> 
> 
> An encrypted and/or steganographic filesystem would be much better for
> your NVRAM keychain drive, because that hides your files even when you
> _haven't_ deleted them.

But these are not mutually exclusive. Even if the data are encrypted, 
when I delete something I want it GONE. That way even if a TLA with 
resources to break the crypto steals my device, my previous password 
list is safe.

-- 
bill davidsen <davidsen@tmr.com>
   CTO TMR Associates, Inc
   Doing interesting things with small computers since 1979

Re: PATCH - ext2fs privacy (i.e. secure deletion) patch

[Jamie Lokier]

Bill Davidsen wrote:
> But these are not mutually exclusive. Even if the data are encrypted, 
> when I delete something I want it GONE. That way even if a TLA with 
> resources to break the crypto steals my device, my previous password 
> list is safe.

Fair point.  Per-inode keys won't protect against a resourceful TLA
(if such a TLA ever exists).

-- Jamie