partially encrypted filesystem

partially encrypted filesystem

[Kallol Biswas]

Hello,
      We have a requirement that a filesystem has to support
encryption based on some policy. The filesystem also should be able 
to store data in non-encrypted form. A search on web shows a few 
encrypted filesystems like "Crypto" from Suse Linux, but we need a
system  where encryption will be a choice per file. We have a hardware
controller to apply encryption algorithm. If a filesystem provides hooks
to use a hardware controller to do the encryption work then the cpu can
be freed from doing the extra work.

Any comment on this?

Kallol
NucleoDyne Systems.
nucleon@nucleodyne.com
408-718-8164

Re: partially encrypted filesystem

[Richard B. Johnson]

On Wed, 3 Dec 2003, Kallol Biswas wrote:

>
> Hello,
>       We have a requirement that a filesystem has to support
> encryption based on some policy. The filesystem also should be able
> to store data in non-encrypted form. A search on web shows a few
> encrypted filesystems like "Crypto" from Suse Linux, but we need a
> system  where encryption will be a choice per file. We have a hardware
> controller to apply encryption algorithm. If a filesystem provides hooks
> to use a hardware controller to do the encryption work then the cpu can
> be freed from doing the extra work.
>
> Any comment on this?
>
> Kallol
> NucleoDyne Systems.
> nucleon@nucleodyne.com
> 408-718-8164

I think you just need your application to encrypt data where needed.
Or to read/write to an encrypted file-system which always encrypts.
You really don't want policy inside the kernel.

Let's say you decided to ignore me and do it anyway. The file-systems
are a bunch of inodes. Every time you want to read or write one, something
has to decide if it's encrypted and, if it is, how to encrypt or
decrypt it. Even the length of the required read or write becomes
dependent upon the type of encryption being used. Surely you don't
want to use an algorithm where a N-byte string gets encoded into a
N-byte string because to do so gives away the length, from which
one can derive other aspects, resulting in discovering the true content.
So, you need variable-length inodes --- what a mess. The result
would be one of the slowest file-systems you could devise.

Encrypted file-systems, where you encrypt everything that goes
on the media work. Making something that could be either/or,
while possible, is not likely going to be very satisfying.

Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (797.90 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: partially encrypted filesystem

[Jörn Engel]

On Wed, 3 December 2003 13:07:56 -0800, Kallol Biswas wrote:
> 
> Hello,
>       We have a requirement that a filesystem has to support
> encryption based on some policy. The filesystem also should be able 
> to store data in non-encrypted form. A search on web shows a few 
> encrypted filesystems like "Crypto" from Suse Linux, but we need a
> system  where encryption will be a choice per file. We have a hardware
> controller to apply encryption algorithm. If a filesystem provides hooks
> to use a hardware controller to do the encryption work then the cpu can
> be freed from doing the extra work.
> 
> Any comment on this?

Haven't heard about anything working yet, but it shouldn't be too hard
to change something existing.  For jffs2, I would guesstimate one or
two month to add the necessary bits, but jffs2 is not first choice as
a hard drive filesystem.  Not sure about other filesystems.

Jörn

-- 
Geld macht nicht glücklich.
Glück macht nicht satt.

Re: partially encrypted filesystem

[bill davidsen]

In article <Pine.LNX.4.53.0312031627440.3725@chaos>,
Richard B. Johnson <root@chaos.analogic.com> wrote:
| On Wed, 3 Dec 2003, Kallol Biswas wrote:
| 
| >
| > Hello,
| >       We have a requirement that a filesystem has to support
| > encryption based on some policy. The filesystem also should be able
| > to store data in non-encrypted form. A search on web shows a few
| > encrypted filesystems like "Crypto" from Suse Linux, but we need a
| > system  where encryption will be a choice per file. We have a hardware
| > controller to apply encryption algorithm. If a filesystem provides hooks
| > to use a hardware controller to do the encryption work then the cpu can
| > be freed from doing the extra work.
| >
| > Any comment on this?
| >
| > Kallol
| > NucleoDyne Systems.
| > nucleon@nucleodyne.com
| > 408-718-8164
| 
| I think you just need your application to encrypt data where needed.
| Or to read/write to an encrypted file-system which always encrypts.
| You really don't want policy inside the kernel.
| 
| Let's say you decided to ignore me and do it anyway. The file-systems
| are a bunch of inodes. Every time you want to read or write one, something
| has to decide if it's encrypted and, if it is, how to encrypt or
| decrypt it. Even the length of the required read or write becomes
| dependent upon the type of encryption being used. Surely you don't
| want to use an algorithm where a N-byte string gets encoded into a
| N-byte string because to do so gives away the length, from which
| one can derive other aspects, resulting in discovering the true content.
| So, you need variable-length inodes --- what a mess. The result
| would be one of the slowest file-systems you could devise.
| 
| Encrypted file-systems, where you encrypt everything that goes
| on the media work. Making something that could be either/or,
| while possible, is not likely going to be very satisfying.

Well said. This isn't the way to do it as you say, although you could
add an O_CRYPTO flag to creat() if you really wanted to.


Crypto in the program is definitely the better solution.
-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: partially encrypted filesystem

[Linus Torvalds]

On Wed, 3 Dec 2003, Jörn Engel wrote:
>
> Haven't heard about anything working yet, but it shouldn't be too hard
> to change something existing.  For jffs2, I would guesstimate one or
> two month to add the necessary bits, but jffs2 is not first choice as
> a hard drive filesystem.  Not sure about other filesystems.

Encryption is not that easy to just tack on to most existing filesystems
for one simple reason: for performance (and memory footprint) reasons,
most of the filesystems out there are doing "IO in place". In other words,
they do IO directly into and directly from the page cache.

With an encrypted filesystem, you can't do that. Or rather: you can do it
if the filesystem is read-only, but you definitely CANNOT do it on
writing. For writing you have to marshall the output buffer somewhere
else (and quite frankly, it tends to become a lot easier if you can do
that for reading too).

And that in turn causes problems. You get all kinds of interesting
deadlock schenarios when write-out requires more memory in order to
succeed. So you need to get careful. Reading ends up being the much easier
case (doesn't have the same deadlock issues _and_ you could do it in-place
anyway).

So encryption per se isn't hard. But adding the extra indirect buffer
layer _can_ be pretty nasty, and makes it nontrivial to retrofit later.

** NOTE NOTE NOTE **

If you don't need to mmap() the files, writing becomes much easier.
Because then you can make rules like "the page cache accesses always
happen with the page locked", and then the encryption layer can do the
encryption in-place.

So it is potentially much easier to make encrypted files a special case,
and disallow mmap on them, and also disallow concurrent read/write on
encrypted files. This may be acceptable for a lot of uses (most programs
still work without mmap - but you won't be able to encrypt demand-loaded
binaries, for example).

		Linus

Re: partially encrypted filesystem

[Jeff Garzik]

Linus Torvalds wrote:
> With an encrypted filesystem, you can't do that. Or rather: you can do it
> if the filesystem is read-only, but you definitely CANNOT do it on
> writing. For writing you have to marshall the output buffer somewhere
> else (and quite frankly, it tends to become a lot easier if you can do
> that for reading too).
> 
> And that in turn causes problems. You get all kinds of interesting
> deadlock schenarios when write-out requires more memory in order to
> succeed. So you need to get careful. Reading ends up being the much easier
> case (doesn't have the same deadlock issues _and_ you could do it in-place
> anyway).


FWIW zisofs and ntfs have to do this too, since X on-disk compressed 
pages must be expanded to X+Y in-memory pages...

	Jeff

Re: partially encrypted filesystem

[Linus Torvalds]

On Wed, 3 Dec 2003, Jeff Garzik wrote:
> Linus Torvalds wrote:
> >
> > And that in turn causes problems. You get all kinds of interesting
> > deadlock schenarios when write-out requires more memory in order to
> > succeed. So you need to get careful. Reading ends up being the much easier
> > case (doesn't have the same deadlock issues _and_ you could do it in-place
> > anyway).
>
>
> FWIW zisofs and ntfs have to do this too, since X on-disk compressed
> pages must be expanded to X+Y in-memory pages...

Note how zisofs only has to handle the read-only case. cramfs does the
same.

Reading is trivially done by having a few extra buffers (either through
the buffer cache or explicit buffering).

Writing is the more interesting case. I don't know how well NTFS does in
low-memory circumstances.

(Which is by no means to say that it is somehow impossible to get right:
you just have to be careful).

		Linus

Re: partially encrypted filesystem

[Charles Manning]

> ** NOTE NOTE NOTE **
>
> If you don't need to mmap() the files, writing becomes much easier.
> Because then you can make rules like "the page cache accesses always
> happen with the page locked", and then the encryption layer can do the
> encryption in-place.
>
> So it is potentially much easier to make encrypted files a special case,
> and disallow mmap on them, and also disallow concurrent read/write on
> encrypted files. This may be acceptable for a lot of uses (most programs
> still work without mmap - but you won't be able to encrypt demand-loaded
> binaries, for example).
>

Is there a useful half-way point here: how about supporting mmap reading but 
not mmap writing. JFFS2, which incidentally also does compression, does this 
to allow execution of binaries.

-- Charles

Re: partially encrypted filesystem

[Valdis.Kletnieks]

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

On Wed, 03 Dec 2003 13:07:56 PST, Kallol Biswas <kbiswas@neoscale.com>  said:
>       We have a requirement that a filesystem has to support
> encryption based on some policy. The filesystem also should be able 
> to store data in non-encrypted form. A search on web shows a few 
> encrypted filesystems like "Crypto" from Suse Linux, but we need a
> system  where encryption will be a choice per file. We have a hardware
> controller to apply encryption algorithm. If a filesystem provides hooks
> to use a hardware controller to do the encryption work then the cpu can
> be freed from doing the extra work.
> 
> Any comment on this?

1) Key management will be a royal pain in the posterior, especially if more
than one key is in use on the filesystem (either at the same time, or at
different times).

2) Encryption of files is not all it's cracked up to be, security-wise.  In
particular, it only really guards against an attacker who gets access to the
data while the key isn't accessible (in other words, it does NOT protect
against your root user, or against any trojan horse or other attack that reads
the files while they're accessible in a decrypted form).  You will probably
drive the user bonkers if they have to enter the key at each open() call,
unless you're in a high-enough security model that making it that difficult for
the legitimate user is called for, in which case...

3) Only encrypting some files means an *incredible* amount of data leakage -
even without the file data, you're leaking the file name (unless the directory
is also encrypted), and all the inode data.  That's data an attacker can use -
knowing that an "interesting" file is more than a megabyte in size, has a
filename that's 17 chars long, and was modified yesterday may be enough to tell
them something crucial.

4) Remember information leakage to /tmp and the like - it's pointless to use
crypto on a file that gets vi'ed and puts a copy in a plaintext /tmp for
recovery once the laptop gets stolen. ;)  Better bets here are using tmpfs for /
tmp (and encrypted swap on a loopback so if it DOES hit the disk it's not
useful).

All in all, you're probably better off just using PGP to encrypt individual
files, or an encrypted loopback.   Note that the following *will* work if you
don't want to burn a whole partition per user:

mkdir /crypto
mkdir /crypto/${USER}
chown ${USER} /crypto/${USER}

mkdir ~user/.crypto
dd if=/dev/zero of=~user/.crypto/diskfile bz=1M count=20
losetup -e AES ~user/.crypt/diskfile
mkfs /dev/loop/0

After that, 'mount -o loop,ecryption=aes ~user/crypto/diskfile /crypto/${USER}'
will do it.

(I've probably glossed over a bunch of utii-linux version dependencies - the exact details
are different between the 2.12 and 2.11+loop-aes-patch versions)

Amazingly enough, if you need more space, you can just unmount it, use something
like 'dd if=/dev/zero >> disfkile' to increase it, losetup it, fsck it, resize2fs it,
and remount it....

This is done with already-existing standard tools, and fulfills the requirement
(just put only the crucial files in there).  You can even use symlinks to
redirect (for instance) ~/.important into the encrypted space.

Writing stuff like a Gnome prompter for use at login is left as an excersize
for the reader ;)


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

Re: partially encrypted filesystem

[H. Peter Anvin]

Followup to:  <3FCE8CF5.4030006@pobox.com>
By author:    Jeff Garzik <jgarzik@pobox.com>
In newsgroup: linux.dev.kernel
>
> Linus Torvalds wrote:
> > With an encrypted filesystem, you can't do that. Or rather: you can do it
> > if the filesystem is read-only, but you definitely CANNOT do it on
> > writing. For writing you have to marshall the output buffer somewhere
> > else (and quite frankly, it tends to become a lot easier if you can do
> > that for reading too).
> > 
> > And that in turn causes problems. You get all kinds of interesting
> > deadlock schenarios when write-out requires more memory in order to
> > succeed. So you need to get careful. Reading ends up being the much easier
> > case (doesn't have the same deadlock issues _and_ you could do it in-place
> > anyway).
> 
> 
> FWIW zisofs and ntfs have to do this too, since X on-disk compressed 
> pages must be expanded to X+Y in-memory pages...
> 

zisofs is read-only, so it doesn't apply.

	-hpa
-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
If you send me mail in HTML format I will assume it's spam.
"Unix gives you enough rope to shoot yourself in the foot."
Architectures needed: ia64 m68k mips64 ppc ppc64 s390 s390x sh v850 x86-64

Re: partially encrypted filesystem

[Jörn Engel]

On Wed, 3 December 2003 16:08:17 -0800, Linus Torvalds wrote:
> On Wed, 3 Dec 2003, Jörn Engel wrote:
> >
> > Haven't heard about anything working yet, but it shouldn't be too hard
> > to change something existing.  For jffs2, I would guesstimate one or
> > two month to add the necessary bits, but jffs2 is not first choice as
> > a hard drive filesystem.  Not sure about other filesystems.
> 
> Encryption is not that easy to just tack on to most existing filesystems
> for one simple reason: for performance (and memory footprint) reasons,
> most of the filesystems out there are doing "IO in place". In other words,
> they do IO directly into and directly from the page cache.
> 
> With an encrypted filesystem, you can't do that. Or rather: you can do it
> if the filesystem is read-only, but you definitely CANNOT do it on
> writing. For writing you have to marshall the output buffer somewhere
> else (and quite frankly, it tends to become a lot easier if you can do
> that for reading too).

Isn't that a problem already handled by all compressing filesystems?
Or did I miss something really stupid?

Jörn

-- 
Optimizations always bust things, because all optimizations are, in
the long haul, a form of cheating, and cheaters eventually get caught.
-- Larry Wall 

Re: partially encrypted filesystem

[Linus Torvalds]

On Thu, 4 Dec 2003, Jörn Engel wrote:
>
> Isn't that a problem already handled by all compressing filesystems?
> Or did I miss something really stupid?

Yes, compression and encryption are really the same thing from a fs
implementation standpoint - they just have different goals. So yes, any
compressed filesystem will largely have all the same issues.

And compression isn't very easy to tack on later either.

Encryption does have a few extra problems, simply because of the intent.
In a compressed filesystem it is ok to say "this information tends to be
small and hard to compress, so let's not" (for example, metadata). While
in an encrypted filesystem you shouldn't skip the "hard" pieces..

(Encrypted filesystems also have the key management issues, further
complicating the thing, but that complication tends to be at a higher
level).

		Linus

Re: partially encrypted filesystem

[Phillip Lougher]

Linus Torvalds wrote:
> 
>
> Encryption does have a few extra problems, simply because of the intent.
> In a compressed filesystem it is ok to say "this information tends to be
> small and hard to compress, so let's not" (for example, metadata). While
> in an encrypted filesystem you shouldn't skip the "hard" pieces..

Squashfs is I think the only Linux filesystem that does compress the 
metadata.  I did this more as a technical challenge, but the extra 
compression is sometimes worthwhile, especially with filesystems with 
lots of small files.  Normally, however, it probably isn't worth the effort.

Phillip

> 
> (Encrypted filesystems also have the key management issues, further
> complicating the thing, but that complication tends to be at a higher
> level).
> 
> 		Linus

Re: partially encrypted filesystem

[Jörn Engel]

On Thu, 4 December 2003 07:20:21 -0800, Linus Torvalds wrote:
> On Thu, 4 Dec 2003, Jörn Engel wrote:
> >
> > Isn't that a problem already handled by all compressing filesystems?
> > Or did I miss something really stupid?
> 
> Yes, compression and encryption are really the same thing from a fs
> implementation standpoint - they just have different goals. So yes, any
> compressed filesystem will largely have all the same issues.
> 
> And compression isn't very easy to tack on later either.

So - as sick as it sounds - jffs2 may actually be the fs of choice
when doing encryption, even though working on a hard drive and not
flash.  Cool. :)

> Encryption does have a few extra problems, simply because of the intent.
> In a compressed filesystem it is ok to say "this information tends to be
> small and hard to compress, so let's not" (for example, metadata). While
> in an encrypted filesystem you shouldn't skip the "hard" pieces..

Depends on how much security you really care about.  If you really
don't mind the pain involved, some metadata should explicitly *not* be
encrypted, to avoid known plaintext attacks.  To a serious attacker,
this could be a death stroke for ext[23] over cryptoloop, actually.

In real life, though, the humans are usually the weakest link, so this
doesn't matter anyway.

> (Encrypted filesystems also have the key management issues, further
> complicating the thing, but that complication tends to be at a higher
> level).

Trivial, as long as you can live with a single key for the whole
filesystem.  If that is not acceptable, there may even be problems in
the vfs already.

Jörn

-- 
Data dominates. If you've chosen the right data structures and organized
things well, the algorithms will almost always be self-evident. Data
structures, not algorithms, are central to programming.
-- Rob Pike

Re: partially encrypted filesystem

[Hans Reiser]

Edward Shushkin is working full-time on compression and encryption 
plugins for Reiser4, which are selected on a per file basis.  The 
compression and encryption is done at flush to disk time, rather than 
with each write, which means that repeated writes to the same object are 
done efficiently.  He has been working on it for a year, and sometime 
early next year he will have something usable you can try.:)

Hans



-- 
Hans

Re: partially encrypted filesystem

[Phillip Lougher]

Jörn Engel wrote:
> 
> So - as sick as it sounds - jffs2 may actually be the fs of choice
> when doing encryption, even though working on a hard drive and not
> flash.  Cool. :)
> 

Considering that Jffs2 is the only writeable compressed filesystem, yes. 
  What should be borne in mind is compressed filesystems never expect 
the data after compression to be bigger than the original data.  In the 
case where the compressed data is bigger, the original data is used 
instead, which is hardy ideal for an encrypted filesystem, and so more 
than a direct substitution of compression function for encrypt function 
is needed - this is of course only relevant if the encryption algorithm 
used could return more data...


> 
> Depends on how much security you really care about.  If you really
> don't mind the pain involved, some metadata should explicitly *not* be
> encrypted, to avoid known plaintext attacks.  To a serious attacker,
> this could be a death stroke for ext[23] over cryptoloop, actually.
> 

You're assuming the metadata (inodes, indexes and directory entries), 
are encrypted with the same key, and therefore decrypting the directory 
data using plaintext attacks will give the attacker the key to the 
entire metadata?  There is nothing preventing the directory data being 
encrypted separately with a different key, and therefore a plaintext 
attack would get nothing more than the directory information.

As you say, you highlight a drawback with cryptoloop and cloop, because 
they cannot distinquish between different types of data.  This sort of 
thing should always be done at the fs level rather than the block level...

> In real life, though, the humans are usually the weakest link, so this
> doesn't matter anyway.
> 

Hmmm, why not give give up completely then?

Phillip

Re: partially encrypted filesystem

[Jörn Engel]

On Thu, 4 December 2003 18:20:05 +0000, Phillip Lougher wrote:
> Jörn Engel wrote:
> >
> >So - as sick as it sounds - jffs2 may actually be the fs of choice
> >when doing encryption, even though working on a hard drive and not
> >flash.  Cool. :)
> >
> 
> Considering that Jffs2 is the only writeable compressed filesystem, yes. 
>  What should be borne in mind is compressed filesystems never expect 
> the data after compression to be bigger than the original data.  In the 
> case where the compressed data is bigger, the original data is used 
> instead, which is hardy ideal for an encrypted filesystem, and so more 
> than a direct substitution of compression function for encrypt function 
> is needed - this is of course only relevant if the encryption algorithm 
> used could return more data...

Correct.  But this requirement can easily be weakened a enough for
encryption to work.  A couple ALIGN(..., encrypt_blocksize) at two or
three places should do the trick.

> >Depends on how much security you really care about.  If you really
> >don't mind the pain involved, some metadata should explicitly *not* be
> >encrypted, to avoid known plaintext attacks.  To a serious attacker,
> >this could be a death stroke for ext[23] over cryptoloop, actually.
> 
> You're assuming the metadata (inodes, indexes and directory entries), 
> are encrypted with the same key, and therefore decrypting the directory 
> data using plaintext attacks will give the attacker the key to the 
> entire metadata?  There is nothing preventing the directory data being 
> encrypted separately with a different key, and therefore a plaintext 
> attack would get nothing more than the directory information.

True, although that barely makes a difference.  In either case you
have to seperate known-plaintext data from the rest and either not
encrypt it or use a different key.  The hard part is seperating the
data.

> As you say, you highlight a drawback with cryptoloop and cloop, because 
> they cannot distinquish between different types of data.  This sort of 
> thing should always be done at the fs level rather than the block level...

If it is done, yes.  "fsck it, who cares" may also be a valid design.

> >In real life, though, the humans are usually the weakest link, so this
> >doesn't matter anyway.
> 
> Hmmm, why not give give up completely then?

Because it is fun doing so or someone pays for it.  And - more to the
point - the humans should be the weakest link, that is bad enough
already.  No reason to make/leave things worse.

Jörn

-- 
To recognize individual spam features you have to try to get into the
mind of the spammer, and frankly I want to spend as little time inside
the minds of spammers as possible.
-- Paul Graham

Re: partially encrypted filesystem

[David Wagner]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 465 bytes --]

Jörn Engel  wrote:
>Depends on how much security you really care about.  If you really
>don't mind the pain involved, some metadata should explicitly *not* be
>encrypted, to avoid known plaintext attacks.

What?  No.  Modern cryptosystems are designed to be secure against
known plaintext attacks.  Making your system more convoluted merely to
avoid providing known plaintext is a lousy design approach: the extra
complexity usually adds more risk than it removes.

Re: partially encrypted filesystem

[Erez Zadok]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 683 bytes --]

In message <3FCF7AD5.4050501@lougher.demon.co.uk>, Phillip Lougher writes:
> Jörn Engel wrote:
> > 
> > So - as sick as it sounds - jffs2 may actually be the fs of choice
> > when doing encryption, even though working on a hard drive and not
> > flash.  Cool. :)
> > 
> 
> Considering that Jffs2 is the only writeable compressed filesystem, yes. 
[...]

Part of our stackable f/s project (FiST) includes a Gzipfs stackable
compression f/s.  There was a paper on it in Usenix 2001 and there's code in
the latest fistgen package.  See
http://www1.cs.columbia.edu/~ezk/research/fist/

Performance of Gzipfs is another matter, esp. for writes in the middle of
files. :-)

Cheers,
Erez.

Re: partially encrypted filesystem

[Jörn Engel]

On Thu, 4 December 2003 14:41:48 -0500, Erez Zadok wrote:
> 
> Part of our stackable f/s project (FiST) includes a Gzipfs stackable
> compression f/s.  There was a paper on it in Usenix 2001 and there's code in
> the latest fistgen package.  See
> http://www1.cs.columbia.edu/~ezk/research/fist/
> 
> Performance of Gzipfs is another matter, esp. for writes in the middle of
> files. :-)

You don't seriously treat big files as a single gzip stream, do you?
;)

Jörn

-- 
Geld macht nicht glücklich.
Glück macht nicht satt.

Re: partially encrypted filesystem

[Jörn Engel]

On Thu, 4 December 2003 19:18:26 +0000, David Wagner wrote:
> 
> What?  No.  Modern cryptosystems are designed to be secure against
> known plaintext attacks.  Making your system more convoluted merely to
> avoid providing known plaintext is a lousy design approach: the extra
> complexity usually adds more risk than it removes.

All cryptosystems are designed around the hope that noone figures out
how to break them.  Many smart people trying and failing to do so
gives a good general feeling, but nothing more.  It remains hope.

How can you claim that modern cryptosystems are immune to known
plaintext attacks?

Jörn

-- 
When you close your hand, you own nothing. When you open it up, you
own the whole world.
-- Li Mu Bai in Tiger & Dragon

Re: partially encrypted filesystem

[Erez Zadok]

In message <20031205112050.GA29975@wohnheim.fh-wedel.de>, =?iso-8859-1?Q?J=F6rn?= Engel writes:
> On Thu, 4 December 2003 14:41:48 -0500, Erez Zadok wrote:
> > 
> > Part of our stackable f/s project (FiST) includes a Gzipfs stackable
> > compression f/s.  There was a paper on it in Usenix 2001 and there's code in
> > the latest fistgen package.  See
> > http://www1.cs.columbia.edu/~ezk/research/fist/
> > 
> > Performance of Gzipfs is another matter, esp. for writes in the middle of
> > files. :-)
> 
> You don't seriously treat big files as a single gzip stream, do you?
> ;)

Of course not.  We're not *that* bad.  :-)

We compress each chunk separately; currently chunk==PAGE_CACHE_SIZE.  For
each file foo we keep an index file foo.idx that records the offsets in the
main file of where you might find the decompressed data for page N.  Then we
hook it up into the page read/write ops of the VFS.  It works great for the
most common file access patterns: small files, sequential/random reads, and
sequential writes.  But, it works poorly for random writes into large files,
b/c we have to decompress and re-compress the data past the point of
writing.  Our paper provides a lot of benchmarks results showing performance
and resulting space consumption under various scenarios.

We've got some ideas on how to improve performance for writes-in-the-middle,
but they may hurt performance for common cases.  Essentially we have to go
for some sort of O(log n)-like data structure, which'd make random writes
much better.  But since it may hurt performance for other access patterns,
we've been thinking about some way to support both modes and be able to
switch b/t the two modes on the fly (or at least let users "mark" a file as
one for which you'd expect a lot of random writes to happen).

If anyone has some comments or suggestions, we'd love to hear them.

BTW, our support in the stackable templates (described in the paper) is more
general than just for compression.  We support any (monotonically
continuous) size-changing algorithm: compression, encryption, etc.  In our
paper we also show a size-expanding file system called uuencodefs.

Cheers,
Erez.

Re: partially encrypted filesystem

[Frank v Waveren]

On Fri, Dec 05, 2003 at 02:02:02PM +0100, J?rn Engel wrote:
> How can you claim that modern cryptosystems are immune to known
> plaintext attacks?
Just as it's perfectly reasonable to say that factoring large
prime products is computationally infeasible. True, it might turn out
to be untrue, but it's one of the general assumptions you go
by when implementing a cryptographic system.

-- 
Frank v Waveren                                      Fingerprint: 21A7 C7F3
fvw@[var.cx|stack.nl|dse.nl] ICQ#10074100               1FF3 47FF 545C CB53
Public key: hkp://wwwkeys.pgp.net/fvw@var.cx            7BD9 09C0 3AC1 6DF2

Re: partially encrypted filesystem

[Matthew Wilcox]

On Fri, Dec 05, 2003 at 11:16:51AM -0500, Erez Zadok wrote:
> We compress each chunk separately; currently chunk==PAGE_CACHE_SIZE.  For
> each file foo we keep an index file foo.idx that records the offsets in the
> main file of where you might find the decompressed data for page N.  Then we
> hook it up into the page read/write ops of the VFS.  It works great for the
> most common file access patterns: small files, sequential/random reads, and
> sequential writes.  But, it works poorly for random writes into large files,
> b/c we have to decompress and re-compress the data past the point of
> writing.  Our paper provides a lot of benchmarks results showing performance
> and resulting space consumption under various scenarios.
> 
> We've got some ideas on how to improve performance for writes-in-the-middle,
> but they may hurt performance for common cases.  Essentially we have to go
> for some sort of O(log n)-like data structure, which'd make random writes
> much better.  But since it may hurt performance for other access patterns,
> we've been thinking about some way to support both modes and be able to
> switch b/t the two modes on the fly (or at least let users "mark" a file as
> one for which you'd expect a lot of random writes to happen).
> 
> If anyone has some comments or suggestions, we'd love to hear them.

Sure.  I've described it before on this list, but here goes:

What Acorn did for their RISCiX product (4.3BSD based, ran on an ARM box
in late 80s/early 90s) was compress each 32k page individually and write
it to a 1k block size filesystem (discs were around 50MB at the time,
1k was the right size).  This left the file full of holes, and wasted
on average around 512/32k = 1/64 of the compression that could have been
attained, but it was very quick to seek to the right place.

Now 4k block size filesystems are the rule, and page size is also
4k so you'd need to be much more clever to achieve the same effect.
Compressing 256k chunks at a time would give you the same wastage, but
I don't think Linux has very good support for filesystems that want to
drop 64 pages into the page cache when the VM/VFS only asked for one.

If it did, that would allow ext2/3 to grow block sizes beyond the current
4k limit on i386, which would be a good thing to do.  Or perhaps we just
need to bite the bullet and increase PAGE_CACHE_SIZE to something bigger,
like 64k.  People are going to want that on 32-bit systems soon anyway.

-- 
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain

Re: partially encrypted filesystem

[Erez Zadok]

Thanks for the info, Matthew.  Yes, clearly a scheme that keeps some "holes"
in compressed files can help; one of our ideas was to leave sparse holes
every N blocks, exactly for this kind of expansion, and to update the index
file's format to record where the spaces are (so we can efficiently
calculate how many holes we need to consume upon a new write).

Cheers,
Erez.

Re: partially encrypted filesystem

[Pat LaVarre]

> ... but I don't think Linux has very good support for filesystems that
> want to drop 64 pages into the page cache when the VM/VFS only asked
> for one.
> 
> If it did, that would allow ext2/3 to grow block sizes beyond the
> current 4k limit on i386, which would be a good thing to do.  Or
> perhaps we just need to bite the bullet and increase PAGE_CACHE_SIZE
> to something bigger, like 64k.  People are going to want that on
> 32-bit systems soon anyway.

Issue now yes.  Three pieces of evidence:

1)

I hear CD-RW commonly report 64 KiB per write block, DVD-RAM/ DVD+RW
often report 32 KiB per write block.

2)

http://marc.theaimsgroup.com/?l=linux-scsi&m=106700651518749
Subject:  Re: aligned /dev/scd$n reads less rare how
Date: 2003-10-24 14:41:16
is me saying a naive lk 2.6 test like `dd if=/dev/scd0 bs=1M` doesn't
yet improve read thruput by polite alignment, much less improve write
thruput by polite alignment.

Specifically I see we lose alignment in the second cdb and following,
til the end of the disc.

3)

http://marc.theaimsgroup.com/?l=linux-scsi&m=107004995921559
Subject: cdrom sr ide-cd - CDC_WR, 1999 op x46 GPCMD_GET_CONFIGURATION
Date: 2003-11-28 20:05:03
is me saying cdrom.ko does not yet fetch via SCSI over whatever (USB2HS/
ATAPIUDMA133/ 1394a/ ...) the 1999 ANSI T10 standard plug 'n play
descriptor that distinguishes the 32/64 KiB bytes per write block from
the 2 KiB bytes per read block.  (Relevant patches appear incomplete,
nearby.)

Pat LaVarre

Re: partially encrypted filesystem

[Matthew Wilcox]

On Fri, Dec 05, 2003 at 02:47:56PM -0500, Erez Zadok wrote:
> Thanks for the info, Matthew.  Yes, clearly a scheme that keeps some "holes"
> in compressed files can help; one of our ideas was to leave sparse holes
> every N blocks, exactly for this kind of expansion, and to update the index
> file's format to record where the spaces are (so we can efficiently
> calculate how many holes we need to consume upon a new write).

But the genius is that you don't need to calculate anything.  If the
data block turns out to be incompressible (those damn .tar.bz2s!), you
just write the block in-place.  If it is compressible, you write as much
into that block's entry as you need and leave a gap.  The underlying
file system doesn't write any data there.  There's no need for an index
file -- you know exactly where to start reading each block.

-- 
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain

Re: partially encrypted filesystem

[Pat LaVarre]

> data block turns out to be incompressible (those damn .tar.bz2s!)

Also such already compressed bitmap/ audio/ photo/ video as .png, .mp3,
.jpg, .mov, etc. that occupy large fractions of consumer hdd ... yes?

Pat LaVarre

Re: partially encrypted filesystem

[David Wagner]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1503 bytes --]

Jörn Engel  wrote:
>On Thu, 4 December 2003 19:18:26 +0000, David Wagner wrote:
>> What?  No.  Modern cryptosystems are designed to be secure against
>> known plaintext attacks.  Making your system more convoluted merely to
>> avoid providing known plaintext is a lousy design approach: the extra
>> complexity usually adds more risk than it removes.
>
>All cryptosystems are designed around the hope that noone figures out
>how to break them.  Many smart people trying and failing to do so
>gives a good general feeling, but nothing more.  It remains hope.

What's your point?  Nothing you are saying contradicts my conclusion.
I'll repeat my point: adding extra complexity adds more risk than it
takes away.  Sure, maybe you reduce the risk of a cryptographic failure
a teeny little bit by avoiding known plaintext, but doing so generally
makes the system more convoluted and hard to understand and maintain,
and *that* generally increases the risk of a security failure more than
enough to counterbalance any gains.

Basic principle: All else being equal, it's generally a good idea to
put more effort into defending against the more likely failure modes,
and less effort into less likely failures.

What are the chances that AES gets broken in the next 10 years?
Pretty small, I believe.  What are the chances that there is a bug
in the encrypting filesystem software that is discovered at some point
in the next 10 years?  Considerably higher.  So, focus on the software.
Complexity is your enemy.

Re: partially encrypted filesystem

[Maciej Zenczykowski]

> But the genius is that you don't need to calculate anything.  If the
> data block turns out to be incompressible (those damn .tar.bz2s!), you
> just write the block in-place.  If it is compressible, you write as much
> into that block's entry as you need and leave a gap.  The underlying
> file system doesn't write any data there.  There's no need for an index
> file -- you know exactly where to start reading each block.

You are pushing this down to the file system.  I'd venture too say that 
this will majorly stress the fs code, make its indexing slower and 
majorly fragment the file on disk (if it's later overwritten).  Sure - you 
have less work to do (less to code) - but the end effect might be 
painful, especially on often written files (if the file ain't written to 
then there are much better compression solutions).

Cheers,
MaZe.

Re: partially encrypted filesystem

[Phillip Lougher]

Matthew Wilcox wrote:
> On Fri, Dec 05, 2003 at 02:47:56PM -0500, Erez Zadok wrote:
> 
>>Thanks for the info, Matthew.  Yes, clearly a scheme that keeps some "holes"
>>in compressed files can help; one of our ideas was to leave sparse holes
>>every N blocks, exactly for this kind of expansion, and to update the index
>>file's format to record where the spaces are (so we can efficiently
>>calculate how many holes we need to consume upon a new write).

FYI, Acorn's scheme was described in "Compressed Executables: An 
Exercise in Thinking Small" by Mark Taunton, in the Usenix Spring '91 
conference, it doesn't seem to be online, but a search on google groups 
for "group:comp.unix.internals taunton compressed executables" brings up 
a description.  I used to work with Mark Taunton at Acorn.

> 
> But the genius is that you don't need to calculate anything.  If the
> data block turns out to be incompressible (those damn .tar.bz2s!), you
> just write the block in-place.  If it is compressible, you write as much
> into that block's entry as you need and leave a gap.  The underlying
> file system doesn't write any data there.  There's no need for an index
> file -- you know exactly where to start reading each block.
> 

Of course this is all being done at the file level, which relies on 
proper support of holes in the underlying filesystem (which Acorn's BSD 
FFS filesystem did).  FiST's scheme is much more how it would be 
implemented without hole support, where you *have* to pack the data, 
otherwise the "unused" space would physically consume disk blocks. In 
this case an index to find the start of each compressed block is essential.

I'm guessing that FiST lacks support for holes or data insertion in the 
  filesystem model, which explains why on writing to the middle of a 
file, the entire file from that point has to be re-written.

Of course, all this is at the logical file level, and ignores the 
physical blocks on disk.  All filesystems assume physical data blocks 
can be updated in place.  With compression it is possible a new physical 
block has to be found, especially if blocks are highly packed and not 
aligned to block boundaries.  I expect this is at least partially why 
JFFS2 is a log structured filesystem.

Phillip

Re: partially encrypted filesystem

[Pat LaVarre]

> You are pushing this down to the file system.  I'd venture too say that 
> this will majorly stress the fs code, make its indexing slower and 
> majorly fragment the file on disk (if it's later overwritten).  Sure - you 
> have less work to do (less to code) - but the end effect might be 
> painful, especially on often written files (if the file ain't written to 
> then there are much better compression solutions).

Suppose we wish to encrypt the files on a disc or disk or drive that we
carry from one computer to another.

Where else can the encryption go, if not "down to the file system"?

Pat LaVarre

Re: partially encrypted filesystem

[Valdis.Kletnieks]

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

On Fri, 05 Dec 2003 18:35:55 MST, Pat LaVarre said:

> Suppose we wish to encrypt the files on a disc or disk or drive that we
> carry from one computer to another.
> 
> Where else can the encryption go, if not "down to the file system"?

It could also be above the filesystem, a la PGP, or below the file system,
a la encrypted loopback.  Other options, such as steganography and "purloined
letter" schemes, are also at least theoretically possible, if not totally workable.

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

Re: partially encrypted filesystem

[Maciej Zenczykowski]

> Suppose we wish to encrypt the files on a disc or disk or drive that we
> carry from one computer to another.
> 
> Where else can the encryption go, if not "down to the file system"?

Of course down to the file system - in this sense.  My point was that you
were utilizing sparse features of the filesystem in ways for which it
likely wasn't designed, thus you would likely encounter problems and/or
slowdowns.  Face it: sparse files are seldom used and when they are used
it is mostly for static files.  It is unusual for a file of 500 blocks to
have 200 1 block sparse holes and 25 2 block sparse holes.  This is what
you'd get with your compression (assuming a 50% comp ratio).  That's a
single smallish files with 225 sparse empty regions.  I doubt the
filesystem is optimized to deal nicely with that.  The problem being that
any later write access to such a file which compresses better or worse
than the original data in that area (ie uses one (or more) less/more
blocks than what used to be there) causes fragmentations and requires
extra pointers etc... you may soon end up with a 500 block file with 225
sparse holes and 275 pointers to single blocks (instead of one long
continuous area with data represented with a single pointer and length).  
Sure, the file system will likely manage to deal with it - but a) this'll
be a real filesystem stress test (assuming stuff like this happens in
every file... you'd have millions of single blocks instead of thousands of
contiguous areas)) and b) this'll stress code (which hasn't been as
optimized as the rest) and algorithms (which aren't fast to begin with).  
In other words you are likely to hit fs bugs and slowdowns.  I'm not
saying this isn't the best way to do it - but, you may be required to
invest significant time into making sparse file handling work _well_ in
extreme cases in order for this to work stabily and/or quickly.  And of 
course if you then change the underlying file system you'll have to start 
the sparse handling rewrite over from the bottom-up.  That's why I'm not 
sure whether this shouldn't be done with some other method - a method 
which would be less likely to cause massive disk fragmentation.

Cheers,
MaZe.

Re: partially encrypted filesystem

[Shaya Potter]

On Sat, 2003-12-06 at 06:43, Maciej Zenczykowski wrote:
> > Suppose we wish to encrypt the files on a disc or disk or drive that we
> > carry from one computer to another.
> > 
> > Where else can the encryption go, if not "down to the file system"?
> 
> Of course down to the file system - in this sense.  My point was that you
> were utilizing sparse features of the filesystem in ways for which it
> likely wasn't designed, thus you would likely encounter problems and/or
> slowdowns.  Face it: sparse files are seldom used and when they are used
> it is mostly for static files.  It is unusual for a file of 500 blocks to
> have 200 1 block sparse holes and 25 2 block sparse holes.  This is what
> you'd get with your compression (assuming a 50% comp ratio).  That's a
> single smallish files with 225 sparse empty regions.  I doubt the
> filesystem is optimized to deal nicely with that.  The problem being that
> any later write access to such a file which compresses better or worse
> than the original data in that area (ie uses one (or more) less/more
> blocks than what used to be there) causes fragmentations and requires
> extra pointers etc... you may soon end up with a 500 block file with 225
> sparse holes and 275 pointers to single blocks (instead of one long
> continuous area with data represented with a single pointer and length).  
> Sure, the file system will likely manage to deal with it - but a) this'll
> be a real filesystem stress test (assuming stuff like this happens in
> every file... you'd have millions of single blocks instead of thousands of
> contiguous areas)) and b) this'll stress code (which hasn't been as
> optimized as the rest) and algorithms (which aren't fast to begin with).  
> In other words you are likely to hit fs bugs and slowdowns.  I'm not
> saying this isn't the best way to do it - but, you may be required to
> invest significant time into making sparse file handling work _well_ in
> extreme cases in order for this to work stabily and/or quickly.  And of 
> course if you then change the underlying file system you'll have to start 
> the sparse handling rewrite over from the bottom-up.  That's why I'm not 
> sure whether this shouldn't be done with some other method - a method 
> which would be less likely to cause massive disk fragmentation.

on this topic, bittorrent on linux would also stree the system, as I
believe what it does is first create one huge sparse file (empty) and
then begins to fill in regions.

Re: partially encrypted filesystem

[David Woodhouse]

On Thu, 2003-12-04 at 18:20 +0000, Phillip Lougher wrote:
> Considering that Jffs2 is the only writeable compressed filesystem, yes. 
>   What should be borne in mind is compressed filesystems never expect 
> the data after compression to be bigger than the original data.

In fact that assumption is fairly trivial to remove, if you can put an
upper bound on the growth. Adding encryption of data to JFFS2 would
actually be fairly trivial; encryption of metadata would be harder. 

You could do it without touching or grokking the core of JFFS2 at all --
just poke at fs/jffs2/compr.c and note that you're expected to eat as
much of the input as will fit into the output buffer, returning success
even if it didn't all fit.

-- 
dwmw2

Re: partially encrypted filesystem

[David Woodhouse]

On Sat, 2003-12-06 at 00:50 +0000, Phillip Lougher wrote:
> Of course, all this is at the logical file level, and ignores the 
> physical blocks on disk.  All filesystems assume physical data blocks 
> can be updated in place.  With compression it is possible a new physical 
> block has to be found, especially if blocks are highly packed and not 
> aligned to block boundaries.  I expect this is at least partially why 
> JFFS2 is a log structured filesystem.

Not really. JFFS2 is a log structured file system because it's designed
to work on _flash_, not on block devices. You have an eraseblock size of
typically 64KiB, you can clear bits in that 'block' all you like till
they're all gone or you're bored, then you have to erase it back to all
0xFF again and start over.

Even if you were going to admit to having a block size of 64KiB to the
layers above you, you just can't _do_ atomic replacement of blocks,
which is required for normal file systems to operate correctly.

These characteristics of flash have often been dealt with by
implementing a 'translation layer' -- a kind of pseudo-filesystem --
which pretends to be a block device with the normal 512-byte
atomic-overwrite behaviour. You then use a traditional file system on
top of that emulated block device. 

JFFS2 was designed to avoid that inefficient extra layer, and work
directly on the flash. Since overwriting stuff in-place is so difficult,
or requires a whole new translation layer to map 'logical' addresses to
physical addresses, it was decided just to ditch the idea that physical
locality actually means _anything_.

Given that design, compression just dropped into place; it was trivial.

-- 
dwmw2

Re: partially encrypted filesystem

[phillip]

dwmw2@infradead.org wrote:
> On Sat, 2003-12-06 at 00:50 +0000, Phillip Lougher wrote:
> > Of course, all this is at the logical file level, and ignores the 
> > physical blocks on disk.  All filesystems assume physical data blocks 
> > can be updated in place.  With compression it is possible a new physical 
> > block has to be found, especially if blocks are highly packed and not 
> > aligned to block boundaries.  I expect this is at least partially why 
> > JFFS2 is a log structured filesystem.
> 
> Not really. JFFS2 is a log structured file system because it's designed
> to work on _flash_, not on block devices. You have an eraseblock size of
> typically 64KiB, you can clear bits in that 'block' all you like till
> they're all gone or you're bored, then you have to erase it back to all
> 0xFF again and start over.

Curiously, I am aware of how flash and log structured filesystems work.

> 
> JFFS2 was designed to avoid that inefficient extra layer, and work
> directly on the flash. Since overwriting stuff in-place is so difficult,
> or requires a whole new translation layer to map 'logical' addresses to
> physical addresses, it was decided just to ditch the idea that physical
> locality actually means _anything_.

Maybe okay for a flash filesystem which is slow anyway, but many filesystem designers *are* concerned about physical locality of blocks, for example video filesystems.
> 
> Given that design, compression just dropped into place; it was trivial.
> 

Or maybe 'not in(to)-place' :-) I don't think I was saying compression is difficult, it is not difficult if you've designed the filesystem correctly.

Phillip

Re: partially encrypted filesystem

[phillip]

dwmw2@infradead.org wrote:
> On Thu, 2003-12-04 at 18:20 +0000, Phillip Lougher wrote:
> > Considering that Jffs2 is the only writeable compressed filesystem, yes. 
> >   What should be borne in mind is compressed filesystems never expect 
> > the data after compression to be bigger than the original data.
> 
> In fact that assumption is fairly trivial to remove, if you can put an
> upper bound on the growth. Adding encryption of data to JFFS2 would
> actually be fairly trivial; encryption of metadata would be harder. 
> 

I was pointing out it had to be considered.  Modesty prevented me from mentioning that adding encryption of both data and metadata to Squashfs would be very easy :-)

Phillip

Re: partially encrypted filesystem

[David Woodhouse]

On Mon, 2003-12-08 at 13:44 +0000, phillip@lougher.demon.co.uk wrote:
> dwmw2@infradead.org wrote:
> > On Sat, 2003-12-06 at 00:50 +0000, Phillip Lougher wrote:
> > > Of course, all this is at the logical file level, and ignores the 
> > > physical blocks on disk.  All filesystems assume physical data blocks 
> > > can be updated in place.  With compression it is possible a new physical 
> > > block has to be found, especially if blocks are highly packed and not 
> > > aligned to block boundaries.  I expect this is at least partially why 
> > > JFFS2 is a log structured filesystem.
> > 
> > Not really. JFFS2 is a log structured file system because it's designed
> > to work on _flash_, not on block devices. You have an eraseblock size of
> > typically 64KiB, you can clear bits in that 'block' all you like till
> > they're all gone or you're bored, then you have to erase it back to all
> > 0xFF again and start over.
> 
> Curiously, I am aware of how flash and log structured filesystems work.

This I assumed. The explanation was more for the benefit of the peanut
gallery than yourself.

> > JFFS2 was designed to avoid that inefficient extra layer, and work
> > directly on the flash. Since overwriting stuff in-place is so difficult,
> > or requires a whole new translation layer to map 'logical' addresses to
> > physical addresses, it was decided just to ditch the idea that physical
> > locality actually means _anything_.
> 
> Maybe okay for a flash filesystem which is slow anyway, but many
> filesystem designers *are* concerned about physical locality of
> blocks, for example video filesystems.

Oh, absolutely. 

> Or maybe 'not in(to)-place' :-)

:)

>  I don't think I was saying compression is difficult, it is not
> difficult if you've designed the filesystem correctly.

My point was that it's trivial in JFFS2 not because I designed the file
system 'correctly', but mostly because of other factors which just
happened to lead to a design which, by coincidence, made compression
trivial.

-- 
dwmw2

Re: partially encrypted filesystem

[Jörn Engel]

On Sat, 6 December 2003 12:43:28 +0100, Maciej Zenczykowski wrote:
> 
> In other words you are likely to hit fs bugs and slowdowns.

If you hit bugs, great!  File a bug report, the developers should be
glad you found it.

And before ranting about the possible massive slowdown, make a quick
benchmark.  If there really is, *then* you can rant on. :)

Jörn

-- 
Beware of bugs in the above code; I have only proved it correct, but
not tried it.
-- Donald Knuth

Re: partially encrypted filesystem

[Pat LaVarre]

> Even if you were going to admit to having a block size of 64KiB to the
> layers above you,

Within pdt x05 dvd/ cd, as contrasted with pdt x00 hdd/ flash, since
1999 we have an ansi t10 paper standard for a device to report bytes per
write block inequal to bytes per read block i.e. the 1999 mmc x0020
RandomWritable "feature" that describes a disc in a drive.

I haven't yet seen an fs run in Linux that bothers to fetch this plug 'n
play data, hence my op x46 GPCMD_GET_CONFIGURATION patches of
linux-scsi.

> you just can't _do_ atomic replacement of blocks,
> which is required for normal file systems to operate correctly.

Google tells me cd-rw and dvd+rw likewise do not support random writing
without load balancing e.g.

http://fy.chalmers.se/~appro/linux/DVD+RW/
http://fy.chalmers.se/~appro/linux/DVD+RW/#udf

"... As you might know DVD+RW media can sustain only around 1000
overwrites. The thing about fully fledged file systems is that every
read [or tight bunch of 'em] is accompanied by corresponding i-node
update or in other words a write! ..."

> These characteristics of flash have often been dealt with by
> implementing a 'translation layer' -- a kind of pseudo-filesystem --
> which pretends to be a block device with the normal 512-byte
> atomic-overwrite behaviour. You then use a traditional file system on
> top of that emulated block device. 

Ick.

Naive read-modify-write to raise bytes-per-write-block passed-thru drops
thruput like 7X in the benchmarks I've seen.

Pat LaVarre

Re: partially encrypted filesystem

[Pavel Machek]

Hi!

> > Of course, all this is at the logical file level, and ignores the 
> > physical blocks on disk.  All filesystems assume physical data blocks 
> > can be updated in place.  With compression it is possible a new physical 
> > block has to be found, especially if blocks are highly packed and not 
> > aligned to block boundaries.  I expect this is at least partially why 
> > JFFS2 is a log structured filesystem.
> 
> Not really. JFFS2 is a log structured file system because it's designed
> to work on _flash_, not on block devices. You have an eraseblock size of
> typically 64KiB, you can clear bits in that 'block' all you like till
> they're all gone or you're bored, then you have to erase it back to all
> 0xFF again and start over.
> 
> Even if you were going to admit to having a block size of 64KiB to the
> layers above you, you just can't _do_ atomic replacement of blocks,
> which is required for normal file systems to operate correctly.

Are those assumptions needed for something else than recovery after
crash/powerdown? [i.e., afaics 64K ext2 should work on flash, but fsck
might have some troubles...]

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

[OT?]Re: partially encrypted filesystem

[Charles Manning]

On Tuesday 09 December 2003 02:44, phillip@lougher.demon.co.uk wrote:
> > JFFS2 was designed to avoid that inefficient extra layer, and work
> > directly on the flash. Since overwriting stuff in-place is so difficult,
> > or requires a whole new translation layer to map 'logical' addresses to
> > physical addresses, it was decided just to ditch the idea that physical
> > locality actually means _anything_.
>
> Maybe okay for a flash filesystem which is slow anyway, but many filesystem
> designers *are* concerned about physical locality of blocks, for example
> video filesystems.

Sure, just because JFFS2 choses to do something a certain way for a certain 
reason does not mean that others cannot choose to do something the different 
(or even the same) for a different reason.  The choices made in JFFS2 were 
done to work around the constraints of flash memory. When those are not 
present then 

Like JFFS2, YAFFS is also a log-structured flash file system that does not 
use a block device and does not assume physical data blocks can be updated in 
place. YAFFS uses a log structure for exactly the same reasons David 
presented (to get away from a physical location dependence - a killer for 
flash file systems). However, YAFFS uses fixed-size chucks as "log records" 
and is thus not really compression friendly. The differences between JFFS2 
and YAFFS are there for good reasons, beyond the scope of this discussion.

>
> > Given that design, compression just dropped into place; it was trivial.
>
> Or maybe 'not in(to)-place' :-) I don't think I was saying compression is
> difficult, it is not difficult if you've designed the filesystem correctly.

Effectively saying that a fs that can't easily support compression is badly 
designed is a dangerous over-simplfication/generalisation/slur. 

There are over 40 file systems for Linux - each is valid and exists because 
it does something that other fs don't do well or solve some particular 
problem.  Often, these fs jump through enough hoops of fire just to work 
effectively and adding compression could easily compromise the main goals of 
the fs.

As an example (that I'm familiar with :-)), I'd say that adding compression 
to YAFFS would at best compromise some of the YAFFS design goals and make it 
at best slower and at worst not be possible at all - without major upheaval. 
For those that simply *must* have compression on a YAFFS-based storage, I 
advise the use of a loop-mounted fs that provides compression (eg. cramfs) 
backed by a YAFFS file. This is being used in some products to great effect.  
It might seem that this adds extra overheads, but there is some saving 
because the whole file system does not have to carry the burden of 
compression etc.


-- CHarles

Re: partially encrypted filesystem

[Pat LaVarre]

> > Even if you were going to admit to having a block size of 64KiB to the
> > layers above you, you just can't _do_ atomic replacement of blocks,
> > which is required for normal file systems to operate correctly.
> 
> Are those assumptions needed for something else than [1] recovery after
> crash/powerdown? [i.e., afaics 64K ext2 should work on flash, but fsck
> might have some troubles...]

2) Space occupied divided by space usable.  Rounding up file sizes to 64
KiB can waste much space.

3) Thruput.  Read 64 KiB to overlay one byte to write back as 64 KiB can
be slow, especially in devices that spin slowly (e.g. 10,000rpm) to
reach the 64 KiB block again.

4) ... anyone know?

Pat LaVarre

Re: partially encrypted filesystem

[Charles Manning]

On Wednesday 10 December 2003 13:07, Pavel Machek wrote:
>
> > Even if you were going to admit to having a block size of 64KiB to the
> > layers above you, you just can't _do_ atomic replacement of blocks,
> > which is required for normal file systems to operate correctly.
>
> Are those assumptions needed for something else than recovery after
> crash/powerdown? [i.e., afaics 64K ext2 should work on flash, but fsck
> might have some troubles...]

The main reason for this in JFFSx and YAFFS (but particularly JFFSx on NOR) 
is that flash memory cannot be arbitrarily overwritten without an erase and 
an erase takes a long time.

Eg:  NOR flash typically takes around 1 second to erase a block (typically 
64kB in size) and approx 10usec or so per byte/word to program. So to  change 
a single byte in a block in place would typically require something like:
1.  Read into buffer 
2. Erase block [1 second].
3. Reprogram [0.6 seconds]

+ do that all over again for the update to the file info.

On NAND flash, where erase is far faster, the cost is far less. Still in a 
comparison of YAFFS (which uses log structuring for the same reasons as 
JFFS2) and FAT + block driver for NAND, YAFFS could sustain a write speed of 
approx 10 times the FAT + block driver solution on the same hardware.

Then there are issues like wear levelling (because flash has a limited 
lifetime) and bad block handling etc... but performance (and crash recovery) 
are the main issues.

-- Charles

Re: [OT?]Re: partially encrypted filesystem

[Phillip Lougher]

Charles Manning wrote:
> On Tuesday 09 December 2003 02:44, phillip@lougher.demon.co.uk wrote:
>>Or maybe 'not in(to)-place' :-) I don't think I was saying compression is
>>difficult, it is not difficult if you've designed the filesystem correctly.
> 
> 
> Effectively saying that a fs that can't easily support compression is badly 
> designed is a dangerous over-simplfication/generalisation/slur. 
> 

Apologies all round to anyone who feels offended.  What I meant to say 
is compression is not that difficult if you design the filesystem from 
the outset with compression in mind - retro fitting compression to an 
existing filesystem, however, can be very difficult (especially 
compressed metadata), and that's why it's not a good idea.

The concept that all well designed filesystems should easily support 
compression is wrong, and I didn't intend to imply that.

Phillip

Re: partially encrypted filesystem

[Rik van Riel]

On Wed, 3 Dec 2003, Linus Torvalds wrote:

> And that in turn causes problems. You get all kinds of interesting
> deadlock schenarios when write-out requires more memory in order to
> succeed.

I suspect this should be fixable with just a simple mempool.

Opportunistic allocation of encrypt-and-IO buffers to keep
performance decent when there's lots of memory available,
fallback to the mempool when free memory is low.

In real emergencies the IO completion code could probably
free the encrypt-and-IO buffer into the mempool.

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: partially encrypted filesystem

[Valient Gough]

This is slightly off topic, as it isn't a kernel implementation.  But in
regards to encryption options above the filesystem, there are user-space
tools for doing this.

For example (ahem, shamelessly plugging my own work)
pobox.com/~vgough/encfs.html - an encrypted filesystem in user-space
which uses the Linux kernel module FUSE (sf.net/projects/avf) to export
a filesystem interface to userland.  As a side note, FUSE also has
python, perl, and Java bindings for your programming pleasure.  

EncFS acts as a pass-thru layer to an existing filesystem, so it does
not require allocating space ahead of time.  But it does not do what the
original email asked, of encrypting on a file by file basis.  It is more
like a reimplementation of CFS, but without NFS being involved.  What
was asked for sounds more like TCFS (for 2.0.x and 2.2.x kernels).

regards,
Valient
vgough@pobox.com

Re: partially encrypted filesystem

[Maciej Zenczykowski]

>  > some other method ....
>  > less likely to cause massive disk fragmentation.
> 
> Such as?

If I knew how to do this correctly I'd be earning a lot of money... :)  
Truthfully this is work for at least a good two weeks of designing, likely
much, much more... to just determine the very basics.  Even assuming you
already have good fast compressors/decompressors which run in neglible
time and achieve the best compression ratio on the market - it's still
very, very non-trivial to make a compressed random-access read-write
filesystem out of that.  Some files should be compressed max, some only
slightly, some not at all, this should all be user selectable on a per
file (or even per file section) basis and the default should allow the
file-system to learn which files to compress and how-badly... etc. etc.  
The file-system has to auto-defragment and it has to minimize 
fragmentation in the first place.

Cheers,
MaZe.

Re: partially encrypted filesystem

[Pat LaVarre]

 > > Suppose we wish to encrypt the files on a
 > > disc or disk or drive that we carry from one
 > > computer to another.
 > >
 > > Where else can the encryption go, if not
 > > "down to the file system"?
 >
 > From: ...maze...
 > ... sparse feature... of the filesystem ...
 > ways for which it likely wasn't designed,
 > thus ... likely ... problems ... slowdowns ...
 > sparse .... seldom used ... mostly ... static ...
 > later write access ... better or worse .... fragmentations ...
 > may ... required ... significant ... making ... work _well_

Agreed.

 > some other method ....
 > less likely to cause massive disk fragmentation.

Such as?

 > From: ...valdis...
 > ... Other ... theoretically ... if not totally workable.

Aye personally I focus on workable application of theory.

 > above ... a la PGP ...

Aye I see "compressed folders" arriving on desktops, and I see 
commercial encryption using that same approach.

 > below ... a la encrypted loopback ....

I'm guessing encryption raises many/all the same issues as compression.

Frustratingly, I find I can't quite lay hold of why people haven't more 
widely adopted compression/ encryption in random-access storage.

Personally I mostly ignored storage until 1994, then I dug in, then I 
felt most shocked to discover nothing like modem compression deployed, 
not even compression for each concentric track of an HDD.  Conceptually 
I like e.g. Usenix talk re garbage-collected log-structured 
filesystems, but nobody's made those real, I'm not yet clear why.

I want compression to trade away time for space, to mess with the 
phenomenon of people living all life at 95% of quota, and to contradict 
the theory that no fs works well when more than 50% full.

Pat LaVarre

P.S. Maybe my second deepest culture shock was finding max bytes/cdb 
choked off near zero e.g. 64 KiB in many places, 128 KiB now rumoured 
for parts of lk 2.6.  I'm not sure how often quantitative measurements 
of algorithms wrongly show no improvement because swamped by that limit.