Reiser4 crypto-compression design

Reiser4 crypto-compression design

[Edward Shushkin]

 This is a short report about Reiser4 crypto-compression design.

Reiser4 will provide transparent data compression and encryption so
every desirable crypto and compression algorithm can be easily
built-in due to plugin architecture. 
  Besides standard unix files, reiser4 will support so-called
crypto-compression files.
  Currently we implement the approach when all crypto-compressed files
are stored in tail items (fragments) on disk. The first obvious
advantage of this approach is that it allows to achieve ideal
compression ratio even when we use small clusters ({1,2}*BLOCK_SIZE),
while it is impossible in traditional approach (when we store file in
whole number of blocks. I use the term "traditional", because this
approach is already implemented in ext2 compression port). At the same
time, small clusters provide better random access to the file data. So
we hope to take some benefit by storing compressed data in tails. All
the compression issues for the traditional approach described in the
following paper:
ttp://www.namesys.com/compression.txt
  When user creates a crypto-file, the file system asks for a secret
key and calculates its id (128-bit word) which supposed to be stored
in file's stat-data on disk.
  When user opens crypto-file, the file system asks for a secret key,
checks (by the id) if it is valid, and places a pointer to the
crypto-file info to the reiser4 specific part of inode. This info
includes cpu key words created by special method of the crypto plugin
by the valid secret key.
  Crypro-compression specific reiser4_read() method is well known
generic_file_read(), it calls special reiser4 readpage() method,
which performs "curve" mapping of on-disk clusters (sliced into tail
items) to the page cache by using main reiser4 disk search procedure
and calling decryption and decompression method. So we fill pages by 
decrypted and decompressed data. 
  Crypto-compression specific write_page() method just copies data
from user to the page cache. Its compression and encryption are
performed by reiser4 flush algorithm before it will be written on disk.
So before squeezing, relocation and other common tasks, the flush
algorithm processes appropriate clusters from the page cache, slices
the result into tails (fragments) and inserts it into the main
balanced tree.
  The cluster approach (which is required for compression) is also
useful for encryption purposes: it allows to support various complex
"per cluster" crypto stream modes, which provides more security then 
simple "per crypto-block" encryption (crypto-block means minimal input
data unit accepted by the crypto algorithm).
 Generally, small chunks of data can not get a good compression, so we	
don't try to compress the flow which size <= MIN_SIZE_FOR_COMPRESSION.
The last value supposed to be found experimentally. Also we don't create
compressed format if the compression algorithm detects that flow can not
get a good compression (more precisely, if 

    orig_size - size_after_compression >= crypto_blocksize +
    end-of-cluster_magic_size
).
In all other cases we append at the end of compressed data a special
"aligning" signature which indicates the end of compressed cluster. We
need to align this up to multiple of crypto block size to make
possible encryption. Also by this signature we can restore
original length of the input size for decompression. Also this
signature allows to handle IO_ERROR during read of cluster, etc..

All wishes and suggestions are welcome.
Thanks, 
Edward.

Re: Reiser4 crypto-compression design

[Hendrik Visage]

On Tue, Mar 25, 2003 at 10:52:36PM +0300, Edward Shushkin wrote:
> All
> the compression issues for the traditional approach described in the
> following paper:
 http://www.namesys.com/compression.txt

>   When user creates a crypto-file, the file system asks for a secret
> key and calculates its id (128-bit word) which supposed to be stored
> in file's stat-data on disk.

What about Public-Private key setups?
Ie. using a Public key to encrypt the data (Or at least encrypt the
shared key with the public key). Also, there might/would be the need for
escrow(Right term?) keys. Ie. keys that the Security Officer could use
to decrypt data (In case of bus accident or dismissal etc.)

Or rather, how will the FS "ask"/request a key for decryption in a secure way?

Hendrik

Re: Reiser4 crypto-compression design

[Edward Shushkin]

Hendrik Visage wrote:
> 
> On Tue, Mar 25, 2003 at 10:52:36PM +0300, Edward Shushkin wrote:
> > All
> > the compression issues for the traditional approach described in the
> > following paper:
>  http://www.namesys.com/compression.txt
> 
> >   When user creates a crypto-file, the file system asks for a secret
> > key and calculates its id (128-bit word) which supposed to be stored
> > in file's stat-data on disk.
> 
> What about Public-Private key setups?

Hans, do we need public-private interface in reiser4?

> Ie. using a Public key to encrypt the data (Or at least encrypt the
> shared key with the public key).

  You mean whether Alice can read a file, which Bob created by Alice's
public key? 
  I think yes. Alice just need to post her 128-bit key-id as a part of her
public key, BUT next time Bob won't be able to open the file he just created
for Alice (he will need Alice's private key for this). This is because the
file system  won't distinguish Bob from other users which don't have Alice's
private key. At the same time, the file system should ask for a secret (private)
key when someone tries to open existing crypto-file, since there can be decrypted
data in page cache intended only for Alice. So the only thing that Bob will be
able to do is delete this file as an owner, but not read. This inconvenience 
probably can be eliminated by using shared keys (although it doesn't provide 
a great security: if I remember correctly, shared key is a private key which
is known by group of certain users.. ) 
  I want to specify precisely, what is 128-bit key-id. 
Our private(secret) key consists from two parts: 
1) key required by crypto algorithm to decrypt data
2) special random string which was created during key generation procedure.
  In order to calculate key-id we decrypt (2) by (1) and apply to the result 
a crypto-stable hash function. This key-id supposed to be stored in stat-data
and is used by the FS to identify private key. Also this key-id is a part of
public key which is a pair:
a) key required by crypto algorithm to encrypt data
b) key-id
Obviously, public key makes sense only for asymmetric crypto algorithms.

> Also, there might/would be the need for
> escrow(Right term?) keys. Ie. keys that the Security Officer 

is it a kind of shared key?

> could use to decrypt data (In case of bus accident or dismissal etc.)
> 
> Or rather, how will the FS "ask"/request a key for decryption in a secure way?

So when user creates new crypto-file and writes into it, the FS requires only a 
public key (his own, or someone's else). For all future accesses to this crypto-file
the FS will require both keys (private key for access and read, and public key 
for write); it may be the same key if crypto algorithm is symmetric).

Thanks for interesting question, 
Edward.

> 
> Hendrik

Re: Reiser4 crypto-compression design

[Hans Reiser]

Edward Shushkin wrote:

>Hendrik Visage wrote:
>  
>
>>On Tue, Mar 25, 2003 at 10:52:36PM +0300, Edward Shushkin wrote:
>>    
>>
>>>All
>>>the compression issues for the traditional approach described in the
>>>following paper:
>>>      
>>>
>> http://www.namesys.com/compression.txt
>>
>>    
>>
>>>  When user creates a crypto-file, the file system asks for a secret
>>>key and calculates its id (128-bit word) which supposed to be stored
>>>in file's stat-data on disk.
>>>      
>>>
>>What about Public-Private key setups?
>>    
>>
>
>Hans, do we need public-private interface in reiser4?
>
I think not in the first release, but eventually, yes I suppose so.

>
>  
>
>>Ie. using a Public key to encrypt the data (Or at least encrypt the
>>shared key with the public key).
>>    
>>
>
>  You mean whether Alice can read a file, which Bob created by Alice's
>public key? 
>  I think yes. Alice just need to post her 128-bit key-id as a part of her
>public key, BUT next time Bob won't be able to open the file he just created
>for Alice (he will need Alice's private key for this). This is because the
>file system  won't distinguish Bob from other users which don't have Alice's
>private key. At the same time, the file system should ask for a secret (private)
>key when someone tries to open existing crypto-file, since there can be decrypted
>data in page cache intended only for Alice. So the only thing that Bob will be
>able to do is delete this file as an owner, but not read. This inconvenience 
>probably can be eliminated by using shared keys (although it doesn't provide 
>a great security: if I remember correctly, shared key is a private key which
>is known by group of certain users.. ) 
>  I want to specify precisely, what is 128-bit key-id. 
>Our private(secret) key consists from two parts: 
>1) key required by crypto algorithm to decrypt data
>2) special random string which was created during key generation procedure.
>  In order to calculate key-id we decrypt (2) by (1) and apply to the result 
>a crypto-stable hash function. This key-id supposed to be stored in stat-data
>and is used by the FS to identify private key. Also this key-id is a part of
>public key which is a pair:
>a) key required by crypto algorithm to encrypt data
>b) key-id
>Obviously, public key makes sense only for asymmetric crypto algorithms.
>
>  
>
>>Also, there might/would be the need for
>>escrow(Right term?) keys. Ie. keys that the Security Officer 
>>    
>>
>
>is it a kind of shared key?
>
>  
>
>>could use to decrypt data (In case of bus accident or dismissal etc.)
>>
>>Or rather, how will the FS "ask"/request a key for decryption in a secure way?
>>    
>>
>
>So when user creates new crypto-file and writes into it, the FS requires only a 
>public key (his own, or someone's else). For all future accesses to this crypto-file
>the FS will require both keys (private key for access and read, and public key 
>for write); it may be the same key if crypto algorithm is symmetric).
>
>Thanks for interesting question, 
>Edward.
>
>  
>
>>Hendrik
>>    
>>
>
>
>  
>


-- 
Hans

Re: Reiser4 crypto-compression design

[Hendrik Visage]

On Wed, Mar 26, 2003 at 08:03:40PM +0300, Edward Shushkin wrote:
> Hendrik Visage wrote:
> > >   When user creates a crypto-file, the file system asks for a secret
> > > key and calculates its id (128-bit word) which supposed to be stored
> > > in file's stat-data on disk.
> > 
> > What about Public-Private key setups?
> 
> Hans, do we need public-private interface in reiser4?

Without it (Even W2K uses a public private setup of some sort) the
whole shared[1] key you've described below, would be missing some features.

> > Ie. using a Public key to encrypt the data (Or at least encrypt the
> > shared key with the public key).
> 
>   You mean whether Alice can read a file, which Bob created by Alice's
> public key? 

Partly yes, but typically you use the public keys of groups of users
to encrypt the shared key of the file for them to later be able to
decrypt the shared key independently.

>   I want to specify precisely, what is 128-bit key-id. 
> Our private(secret) key consists from two parts: 
> 1) key required by crypto algorithm to decrypt data

Isn't 128bit a bit "weak"? I'd prefer a *minimum* 128bit, with it being
extensible (It offcourse depends on the file and user choices)

> 2) special random string which was created during key generation procedure.
>   In order to calculate key-id we decrypt (2) by (1) and apply to the result 
> a crypto-stable hash function. This key-id supposed to be stored in stat-data
> and is used by the FS to identify private key. Also this key-id is a part of
> public key which is a pair:

Hmmmm.... 
 Could you refer me to the references you've used for this system?

> a) key required by crypto algorithm to encrypt data
> b) key-id
> Obviously, public key makes sense only for asymmetric crypto algorithms.

No, you'll have the generate the public-private keys for the asymmetric crypto
algorithms based on the specific algorithm's methods.

> > Also, there might/would be the need for
> > escrow(Right term?) keys. Ie. keys that the Security Officer 
> 
> is it a kind of shared key?

It means that the key used for the encryption/decryption, is accesible
to the security officers. 

also, what about integration with Kerberos for the keys? Or should I rather ask
How would I be able to interact via a process to give/deny access to keys?
 
> > could use to decrypt data (In case of bus accident or dismissal etc.)
> > 
> > Or rather, how will the FS "ask"/request a key for decryption in a secure way?
> 
> So when user creates new crypto-file and writes into it, the FS requires only a 
> public key (his own, or someone's else). For all future accesses to this crypto-file
> the FS will require both keys (private key for access and read, and public key 
> for write); it may be the same key if crypto algorithm is symmetric).

The description above is correct, but public-private key algorithms are 
too slow for any usefull "realtime" data/communication en/decryption, and
that's why they are mostly only used for the shared/secret key exchange.

> Thanks for interesting question, 
> Edward.

Note [1]: 
 Public-Private (asymetric) encryption is usualy only used for the
 setup of shared keys. Shared keys are sometimes called secret keys
 and is the keys used in a symetric algorithm (typically the algorithm
 used in a block mode to encrypt the file data).

 The difference is that private keys are only known to the owner, (public
offcourse known to all and that's what get "certified" in certificates)
while the shared/secret is known/accesible by all that have a need to the
communication/data.

 Ie. AFAIK, pgp/gnupg encrypts the data with a "secret" key using an algorithm
like des/idea/rc4/blowfih/aes. This secret/shared key is then seperately
encrypted with the public keys of everybody that the data data is destined for.
Thus for twenty users, there will be twenty encrypted shared keys (one for 
each user) that's encrypted with each of their public keys. Each user would
then decrypt the key encrypted with his public key, and use that to 
decrypt the file.

Re: Reiser4 crypto-compression design

[Edward Shushkin]

Hendrik Visage wrote:
> 
> On Wed, Mar 26, 2003 at 08:03:40PM +0300, Edward Shushkin wrote:
> > Hendrik Visage wrote:
> > > >   When user creates a crypto-file, the file system asks for a secret
> > > > key and calculates its id (128-bit word) which supposed to be stored
> > > > in file's stat-data on disk.
> > >
> > > What about Public-Private key setups?
> >
> > Hans, do we need public-private interface in reiser4?
> 
> Without it (Even W2K uses a public private setup of some sort

Huh? W2K has a file system with transparent encrypton/compression?

) the
> whole shared[1] key you've described below, would be missing some features.
> 
> > > Ie. using a Public key to encrypt the data (Or at least encrypt the
> > > shared key with the public key).
> >
> >   You mean whether Alice can read a file, which Bob created by Alice's
> > public key?
> 
> Partly yes, but typically you use the public keys of groups of users
> to encrypt the shared key of the file for them to later be able to
> decrypt the shared key independently.
> 
> >   I want to specify precisely, what is 128-bit key-id.
> > Our private(secret) key consists from two parts:
> > 1) key required by crypto algorithm to decrypt data
> 
> Isn't 128bit a bit "weak"? I'd prefer a *minimum* 128bit, with it being
> extensible (It offcourse depends on the file and user choices)

Yes, 128 bit (md5 output) is a minimum.
User should assign the hash function to make key-id.

> 
> > 2) special random string which was created during key generation procedure.
> >   In order to calculate key-id we decrypt (2) by (1) and apply to the result
> > a crypto-stable hash function. This key-id supposed to be stored in stat-data
> > and is used by the FS to identify private key. Also this key-id is a part of
> > public key which is a pair:
> 
> Hmmmm....
>  Could you refer me to the references you've used for this system?

There is no any reference, this is our decision which is based on difficulty
of finding of hash collisions. We need a public fingerprint of private key
to identify it. Actually this is a file system who needs this identification, 
but it lives on disk, and everything on disk is "public".

> 
> > a) key required by crypto algorithm to encrypt data
> > b) key-id
> > Obviously, public key makes sense only for asymmetric crypto algorithms.
> 
> No, you'll have the generate the public-private keys for the asymmetric crypto
> algorithms based on the specific algorithm's methods.
> 
> > > Also, there might/would be the need for
> > > escrow(Right term?) keys. Ie. keys that the Security Officer
> >
> > is it a kind of shared key?
> 
> It means that the key used for the encryption/decryption, is accesible
> to the security officers.
> 
> also, what about integration with Kerberos for the keys? Or should I rather ask
> How would I be able to interact via a process to give/deny access to keys?

But I know that Kerberos uses stream crypto modes which is to detect transfer errors 
for large flows, I am not sure if it is compatible with our transparent encryption
which deals with small clusters (4-32)K..

> > > could use to decrypt data (In case of bus accident or dismissal etc.)

>  Ie. AFAIK, pgp/gnupg encrypts the data with a "secret" key using an algorithm
> like des/idea/rc4/blowfih/aes.

Btw, des packs 48 bits into double cpu word, which is suboptimal, 
blowfish seems to be better..

Thanks, 
Edward.

 This secret/shared key is then seperately
> encrypted with the public keys of everybody that the data data is destined for.
> Thus for twenty users, there will be twenty encrypted shared keys (one for
> each user) that's encrypted with each of their public keys. Each user would
> then decrypt the key encrypted with his public key, and use that to
> decrypt the file.

Re: Reiser4 crypto-compression design

[Pierre Abbat]

On Tuesday 25 March 2003 14:52, Edward Shushkin wrote:
>   When user creates a crypto-file, the file system asks for a secret
> key and calculates its id (128-bit word) which supposed to be stored
> in file's stat-data on disk.
>   When user opens crypto-file, the file system asks for a secret key,
> checks (by the id) if it is valid, and places a pointer to the
> crypto-file info to the reiser4 specific part of inode. This info
> includes cpu key words created by special method of the crypto plugin
> by the valid secret key.

Can a directory be marked as encrypted, so that all new files in the directory 
will be encrypted with the same key? Can a process hold an encryption key, so 
that all its children automatically can read files encrypted with that key?

Re: Reiser4 crypto-compression design

[Hans Reiser]

Pierre Abbat wrote:

>On Tuesday 25 March 2003 14:52, Edward Shushkin wrote:
>  
>
>>  When user creates a crypto-file, the file system asks for a secret
>>key and calculates its id (128-bit word) which supposed to be stored
>>in file's stat-data on disk.
>>  When user opens crypto-file, the file system asks for a secret key,
>>checks (by the id) if it is valid, and places a pointer to the
>>crypto-file info to the reiser4 specific part of inode. This info
>>includes cpu key words created by special method of the crypto plugin
>>by the valid secret key.
>>    
>>
>
>Can a directory be marked as encrypted, so that all new files in the directory 
>will be encrypted with the same key? Can a process hold an encryption key, so 
>that all its children automatically can read files encrypted with that key?
>
>
>
>  
>
Both of these are desirable features.  We need to work out the details 
of integrating with a PKI infrastructure.

-- 
Hans

Re: Reiser4 crypto-compression design

[Hubert Chan]

>>>>> "Pierre" == Pierre Abbat <phma@webjockey.net> writes:

[...]

Pierre> Can a directory be marked as encrypted, so that all new files in
Pierre> the directory will be encrypted with the same key?

A related, but different question, which may have already been answered
by Edward's document: can a directory be encrypted, so that only a user
with the password can list its contents?

-- 
Hubert Chan <hubert@uhoreg.ca> - http://www.uhoreg.ca/
PGP/GnuPG key: 1024D/124B61FA
Fingerprint: 96C5 012F 5F74 A5F7 1FF7  5291 AF29 C719 124B 61FA
Key available at wwwkeys.pgp.net.   Encrypted e-mail preferred.

Re: Reiser4 crypto-compression design

[Hans Reiser]

Hubert Chan wrote:

>>>>>>"Pierre" == Pierre Abbat <phma@webjockey.net> writes:
>>>>>>            
>>>>>>
>
>[...]
>
>Pierre> Can a directory be marked as encrypted, so that all new files in
>Pierre> the directory will be encrypted with the same key?
>
>A related, but different question, which may have already been answered
>by Edward's document: can a directory be encrypted, so that only a user
>with the password can list its contents?
>
>  
>
No, that is beyond the scope of our DARPA contract, and more than I want 
to do in 4.0

-- 
Hans

Re: Reiser4 crypto-compression design

[Pierre Abbat]

On Wednesday 26 March 2003 15:35, Hubert Chan wrote:
> A related, but different question, which may have already been answered
> by Edward's document: can a directory be encrypted, so that only a user
> with the password can list its contents?

The way that's done in CFS is that the filenames are stored as regular 
directory entries, but the names are encrypted. Anyone with permission can 
list the contents, but without knowing the key he gets gibberish. The names 
are stored in hex; we could also use base64 or base85, or come up with a 
cipher that avoids producing nulls and slashes.

Re: Reiser4 crypto-compression design

[Hans Reiser]

Pierre Abbat wrote:

>On Wednesday 26 March 2003 15:35, Hubert Chan wrote:
>  
>
>>A related, but different question, which may have already been answered
>>by Edward's document: can a directory be encrypted, so that only a user
>>with the password can list its contents?
>>    
>>
>
>The way that's done in CFS is that the filenames are stored as regular 
>directory entries, but the names are encrypted. Anyone with permission can 
>list the contents, but without knowing the key he gets gibberish. The names 
>are stored in hex; we could also use base64 or base85, or come up with a 
>cipher that avoids producing nulls and slashes.
>
>
>
>  
>
I'll take a patch;-)

-- 
Hans

Re: Reiser4 crypto-compression design

[Pierre Abbat]

On Thursday 27 March 2003 11:30, Hans Reiser wrote:
> Pierre Abbat wrote:
> >The way that's done in CFS is that the filenames are stored as regular
> >directory entries, but the names are encrypted. Anyone with permission can
> >list the contents, but without knowing the key he gets gibberish. The
> > names are stored in hex; we could also use base64 or base85, or come up
> > with a cipher that avoids producing nulls and slashes.
>
> I'll take a patch;-)

I don't know enough about ReiserFS internal to write one, nor do I have a 
machine running Reiser4 to try it on.

Here's how to make a cipher that avoids producing nulls and slashes:
Break the filename into 8-byte blocks (assuming 8 bytes in an encryption 
block). The last block is invalid if a null is followed by a nonnull or a 
slash occurs anywhere; all other blocks are invalid if a null or a slash 
occurs anywhere. Encrypt each block. If a block is invalid, encrypt it again 
until it is valid. This requires ECB mode; since this is the weakest mode, 
the key should be different for each block, perhaps by adding the tree key 
and the block number. This rules out Blowfish, which takes too long to set up 
the key.

phma
-- 
.i toljundi do .ibabo mi'afra tu'a do
.ibabo damba do .ibabo do jinga
.icu'u la ma'atman.