[PATCH] loop: fixing cryptoloop troubles.

[PATCH] loop: fixing cryptoloop troubles.

[Fruhwirth Clemens]

[-- Attachment #1.1: Type: text/plain, Size: 442 bytes --]

In loop_transfer_bio the initial vector has been computed only once. For any
situation where more than one bio_vec is present the initial vector will be
wrong. Here is the trivial but important fix. 

This will fix the disk corruption problems of cryptoloop for block-backed
loop devices mentioned earlier this month on this list. 

This should close http://bugme.osdl.org/show_bug.cgi?id=1000 

Please confirm.

Regards, Clemens

[-- Attachment #1.2: loop-2.6t2.diff --]
[-- Type: text/plain, Size: 310 bytes --]

--- linux-2.6.0-test2/drivers/block/loop.c~	Sun Jul 27 19:03:16 2003
+++ linux-2.6.0-test2/drivers/block/loop.c	Sun Aug 10 04:22:44 2003
@@ -513,6 +513,7 @@
 					from_bvec->bv_len, IV);
 		kunmap(from_bvec->bv_page);
 		kunmap(to_bvec->bv_page);
+		IV += from_bvec->bv_len >> 9;
 	}
 
 	return ret;

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

Re: [PATCH] loop: fixing cryptoloop troubles.

[Pascal Brisset]

Fruhwirth Clemens writes:
> In loop_transfer_bio the initial vector has been computed only once. For any
> situation where more than one bio_vec is present the initial vector will be
> wrong. Here is the trivial but important fix. 

Looks good, but:
- I doubt this could explain the alteration pattern (1 byte every 512).
- Corruption also occured with cipher_null (which ignores the IV).

I just noticed a related thread: http://lkml.org/lkml/2003/8/6/313
("Device-backed loop broken in 2.6.0-test2?")


A side note: Doesn't crypto/crypto_null.c need this fix ?:

 static void null_encrypt(void *ctx, u8 *dst, const u8 *src)
-{ }
+{ memmove(dst, src, NULL_BLOCK_SIZE); }
 
 static void null_decrypt(void *ctx, u8 *dst, const u8 *src)
-{ }
+{ memmove(dst, src, NULL_BLOCK_SIZE); }

Re: [PATCH] loop: fixing cryptoloop troubles.

[Christophe Saout]

Am So, 2003-08-10 um 16.10 schrieb Pascal Brisset:

> > In loop_transfer_bio the initial vector has been computed only once. For any
> > situation where more than one bio_vec is present the initial vector will be
> > wrong. Here is the trivial but important fix. 
> 
> Looks good, but:
> - I doubt this could explain the alteration pattern (1 byte every 512).
> - Corruption also occured with cipher_null (which ignores the IV).

I personally think that the only way to get things right is to do
encryption sector by sector (not bvec by bvec) since every sector can
have its own iv.

I've implemented a crypto target for device-mapper that does this and it
doesn't seem to suffer from these corruption problems:
http://marc.theaimsgroup.com/?l=linux-kernel&m=105967481007242&w=2 and a
slightly updated patch: http://www.saout.de/misc/dm-crypt.diff

Unfortunately I haven't got a single response. :(

Just got one person outside LKML to (successfully) test it.

Should I repost the patch (inline this time) with an additional [PATCH]
or am I being annoying? Joe Thornber (the dm maintainer) would like to
see this patch merged.

--
Christophe Saout <christophe@saout.de>
Please avoid sending me Word or PowerPoint attachments.
See http://www.fsf.org/philosophy/no-word-attachments.html

Re: [PATCH] loop: fixing cryptoloop troubles.

[Fruhwirth Clemens]

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

On Sun, Aug 10, 2003 at 04:27:47PM +0200, Christophe Saout wrote:
> Am So, 2003-08-10 um 16.10 schrieb Pascal Brisset:
> 
> > > In loop_transfer_bio the initial vector has been computed only once. For any
> > > situation where more than one bio_vec is present the initial vector will be
> > > wrong. Here is the trivial but important fix. 
> > 
> > Looks good, but:
> > - I doubt this could explain the alteration pattern (1 byte every 512).
> > - Corruption also occured with cipher_null (which ignores the IV).

I could not find a way to explain that strange pattern either. With CBC it
would have to result in total mess if just one bit is flipped. Probably
read/writing is handled with different sized bio_vec.. no idea.

cipher_null does not ignore the IV. The CBC processing takes place no matter
what mapping function (aka electronic codebook) is used. The fact that
cipher_null is an identity mapping does not stop CBC. 

> I personally think that the only way to get things right is to do
> encryption sector by sector (not bvec by bvec) since every sector can
> have its own iv.

That's done anyway. Per convention the transformation module is allowed to
increase the IV every 512 bytes. The IV parameter is only the initial
initial vector ;). 

> I've implemented a crypto target for device-mapper that does this and it
> doesn't seem to suffer from these corruption problems:
> http://marc.theaimsgroup.com/?l=linux-kernel&m=105967481007242&w=2 and a
> slightly updated patch: http://www.saout.de/misc/dm-crypt.diff

Nice! It's definitely a feature worth merging. loop.c used to be the place
where to put this stuff, but why not replace it by newer in-kernel
techniques?

> Should I repost the patch (inline this time) with an additional [PATCH]
> or am I being annoying? Joe Thornber (the dm maintainer) would like to
> see this patch merged.

If you can't get attention for your patch, try to convince someone "more
important". DM maintainer is a good place to start :)

Regards, Clemens

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

Re: [PATCH] loop: fixing cryptoloop troubles.

[Christophe Saout]

Am So, 2003-08-10 um 23.03 schrieb Fruhwirth Clemens:

> cipher_null does not ignore the IV. The CBC processing takes place no matter
> what mapping function (aka electronic codebook) is used. The fact that
> cipher_null is an identity mapping does not stop CBC. 

The main problem with CBC is that you can't really do it. It only works
when you have a constant stream of data because you always need the
result from the previous encryption which you don't have when doing
something in the middle of the block device.

Before encryption the data to be encrypted gets xor'ed with the result
from the previous encrypted block. The idea in cryptoloop is that not
the result from the previous run gets used but a specially constructed
dummy block that has the sector number (little-endian encoded) in the
first four bytes and is null every where else. So you simply get some
additional perturbation based on the sector number, so that zero-filled
sectors always looked differently after encoding.

When decoding this means that the sector number is xor'ed over the
encrypted block. If, when decoding, the sector number doesn't match that
one that was put in the iv while encoding that sector, you will get
errors in the first four bytes, mostly one or few bits flipped.

> > I personally think that the only way to get things right is to do
> > encryption sector by sector (not bvec by bvec) since every sector can
> > have its own iv.
> 
> That's done anyway. Per convention the transformation module is allowed to
> increase the IV every 512 bytes. The IV parameter is only the initial
> initial vector ;). 

Yes, but as I described above, to get things right, the iv must be set
correctly on every sector.

Warning: A long analysis of obvious things is following. I think most of
you know everything I'm writing here, I'm just looking through the code
myself and trying to explain what's happening. On the end I'll find the
bug you fixed. I think that was the only bug regarding IV handling.

The cryptoloop code is doing things correctly. In ecb mode, every bio
could get converted at once, or every bvec. If this would have been done
with cbc mode as will, it could happen that 8 sectors get written at a
time, one full page, the cryptoloop encodes this into one scatterlist
entry (because only one bvec is used) and thus the iv from the first
sector will be used to encode all 8 sectors.

When reading a single sector in the middle of those a different iv would
be used to decrypt this data, some bits will be flipped (as described
above). Even worse things could have happened when several bvecs would
have been encoded one after the other without resetting the iv each time
(that's obvious).

============ analysis start ============

cryptoloop is getting this right:

const int sz = min(size, LOOP_IV_SECTOR_SIZE);
u32 iv[4] = { 0, };
iv[0] = cpu_to_le32(IV & 0xffffffff);

So the maximum block size can be a sector (LOOP_IV_SECTOR_SIZE is 512),
and the minimum block size too because auf the bio layer. So that's
fine.

IV++;
...

IV, the sector number is incremented after each run. Fine.

So, what's loop.c doing? do_lo_send:

index = pos >> PAGE_CACHE_SHIFT;
offset = pos & ((pgoff_t)PAGE_CACHE_SIZE - 1);
loop {
  IV = ((sector_t)index << (PAGE_CACHE_SHIFT - 9))+(offset >> 9);

So IV is basically pos >> 9 (position in file), the sector number.
That's fine.

  transfer(blabla);

  index++;
  pos += size;
  offset = 0;

pos isn't used be the iv code anymore, index is incremented by one page,
offset set to 0. Because size is always the remaining size to the end of
the cache page, that should be fine.
}

So encoding into a loop file should be fine.

lo_read_actor:

Mostly the same game, uses the page index and offset from sendfile,
that's the offset inside the file mapping. Should be correct. There's no
page looping done here, sendfile does it for us.

The loop over blockdevice uses a different function. loop_transfer_bio:

IV = from_bio->bi_sector + (lo->lo_offset >> 9);

The sector inside the device + the beginning on the block device gives
us the sector number on the block device. That's what we want.

__bio_for_each_segment(from_bvec, from_bio, i, 0) {
  ...
  ret |= lo_do_transfer(lo, bio_data_dir(to_bio), vto, vfrom,
               from_bvec->bv_len, IV);
  ...
}

Whoops... there is clearly something missing. IV is not a pointer That's
what you fixed. It seems to me that's the only bug. It also explains why
there are some bits flipped and nothing else.

========== analysis end ========== ;)

> > I've implemented a crypto target for device-mapper that does this and it
> > doesn't seem to suffer from these corruption problems:
> > http://marc.theaimsgroup.com/?l=linux-kernel&m=105967481007242&w=2 and a
> > slightly updated patch: http://www.saout.de/misc/dm-crypt.diff
> 
> Nice! It's definitely a feature worth merging. loop.c used to be the place
> where to put this stuff, but why not replace it by newer in-kernel
> techniques?

Yes, I think putting this into loop.c adds unnecessary complexity.
Especially the IV handling is ugly. Sometimes the IV is calculated in
loop.c (three times) and sometimes it gets incremented in cryptoloop.c.
Wow. Error prone and ugly.

The device-mapper is just where this should go, I think. With
device-mapper it's also possible to resize the device on the fly which
is needed if the could should get integrated into a volume manager. The
cryptoloop implementation would only be able to encrypt the whole
partition volume that's fixed in size.

And, it's a lot simpler. And it doesn't do this page -> virtual address
-> page ping-pong translation between loop.c/cryptoloop.c and cryptoapi.

It also passed the swap-on-dm-crypt-under-memory-pressuse test, at least
for me.

And you can still use dm over loop device if you want to encrypt a file.

> > Should I repost the patch (inline this time) with an additional [PATCH]
> > or am I being annoying? Joe Thornber (the dm maintainer) would like to
> > see this patch merged.
> 
> If you can't get attention for your patch, try to convince someone "more
> important". DM maintainer is a good place to start :)

Yes, the DM maintainer helped me write the patch and would like to see
it merged. Convincing some more important persons would be easier if I
would get any reaction from them. ;)

I've also written a file backed target for dm, this one is inspired from
loop.c and also copies some code, especially the file handling functions
itself. It's not as safe under extreme memory pressure though, it
produces a lot of page allocation failures. That must be somewhere in
the vfs layer. If someone is interested in this target I could try to
find out how this can be avoided.

--
Christophe Saout <christophe@saout.de>
Please avoid sending me Word or PowerPoint attachments.
See http://www.fsf.org/philosophy/no-word-attachments.html

Re: [PATCH] loop: fixing cryptoloop troubles.

[Fruhwirth Clemens]

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

On Mon, Aug 11, 2003 at 12:07:16AM +0200, Christophe Saout wrote:

> The main problem with CBC is that you can't really do it. It only works
> when you have a constant stream of data because you always need the
> result from the previous encryption which you don't have when doing
> something in the middle of the block device.

That's partially correct. As most block cipher operate on blocks of 16 bytes
size it perfectly makes sence to use CBC on a 512 byte block. 

> Warning: A long analysis of obvious things is following. I think most of
> you know everything I'm writing here, I'm just looking through the code
> myself and trying to explain what's happening. On the end I'll find the
> bug you fixed. I think that was the only bug regarding IV handling.

*knockonwood* :)

> The cryptoloop code is doing things correctly. In ecb mode, every bio
> could get converted at once, or every bvec. 

ECB mode is broken in 2.6.0-test[12]. See 

http://marc.theaimsgroup.com/?l=linux-kernel&m=106043148921893&w=2

It's a quite conservative patch. ECB processing can be optimized.

> ========== analysis end ========== ;)

Thanks :)

> Yes, I think putting this into loop.c adds unnecessary complexity.
> Especially the IV handling is ugly. Sometimes the IV is calculated in
> loop.c (three times) and sometimes it gets incremented in cryptoloop.c.
> Wow. Error prone and ugly.

Definitly. loop.c is anyway ugly :). It would be nice to rip out the
block-backend stuff of loop.c and recommend to use device mapper instead.
loop.c will benefit from that for sure since it doesn't have to handle two
different case in such a schizophrenic manner.

> And you can still use dm over loop device if you want to encrypt a file.

I like that idea. 

> > If you can't get attention for your patch, try to convince someone "more
> > important". DM maintainer is a good place to start :)
> 
> Yes, the DM maintainer helped me write the patch and would like to see
> it merged. Convincing some more important persons would be easier if I
> would get any reaction from them. ;)

I'll give it a try, promised :)

Regards, Clemens

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

Re: [PATCH] loop: fixing cryptoloop troubles.

[Christophe Saout]

Am Mo, 2003-08-11 um 15.11 schrieb Fruhwirth Clemens:

> > The main problem with CBC is that you can't really do it. It only works
> > when you have a constant stream of data because you always need the
> > result from the previous encryption which you don't have when doing
> > something in the middle of the block device.
> 
> That's partially correct. As most block cipher operate on blocks of 16 bytes
> size it perfectly makes sence to use CBC on a 512 byte block. 

Ah, you're right, I didn't look at it enough to see that the loop in
cipher.c only handles bsize bytes at once.

> > The cryptoloop code is doing things correctly. In ecb mode, every bio
> > could get converted at once, or every bvec. 
> 
> ECB mode is broken in 2.6.0-test[12].

I was speaking theoretically ;)

> It's a quite conservative patch. ECB processing can be optimized.

Yes, you're not restricted to split the request into 512 byte chunks.
But I don't think it's too much of a performance loss. Or should it
better be handled differently? Because I'm not doing it either in my
code.

> Definitly. loop.c is anyway ugly :). It would be nice to rip out the
> block-backend stuff of loop.c and recommend to use device mapper instead.
> loop.c will benefit from that for sure since it doesn't have to handle two
> different case in such a schizophrenic manner.

That's right. I could also write a losetup-like user space utility that
sets up a linear mapped device with the full size of the block device
and optionally uses encryption.

What do you think of this passphrase thing? I could optionally link a
against openssl or such a library to offer password hashing.

> I'll give it a try, promised :)

That'd be nice. :)

--
Christophe Saout <christophe@saout.de>
Please avoid sending me Word or PowerPoint attachments.
See http://www.fsf.org/philosophy/no-word-attachments.html

Re: [PATCH] loop: fixing cryptoloop troubles.

[David Wagner]

Christophe Saout  wrote:
>Before encryption the data to be encrypted gets xor'ed with the result
>from the previous encrypted block. The idea in cryptoloop is that not
>the result from the previous run gets used but a specially constructed
>dummy block that has the sector number (little-endian encoded) in the
>first four bytes and is null every where else. So you simply get some
>additional perturbation based on the sector number, so that zero-filled
>sectors always looked differently after encoding.
>
>When decoding this means that the sector number is xor'ed over the
>encrypted block. If, when decoding, the sector number doesn't match that
>one that was put in the iv while encoding that sector, you will get
>errors in the first four bytes, mostly one or few bits flipped.

Unrelated to the corruption issues:

Is this how cryptoloop works?  The sector number is used directly as the
IV (not the encrypted sector number)?  In other words, if X denotes the
first block of plaintext and S the sector number, then the first block
of ciphertext is C = E_K(X ^ S)?

If yes, I noticed a small security weakness.  This usage of CBC mode can
leak a few bits of information about the plaintext data, in some cases.
For instance, consider the following example.  Let X denote the first block
of plaintext at sector S, and X' the first block of plaintext at sector S'.
Suppose X' = X^1 and S' = S^1 (here "^" denotes xor, as usual).  Then
C = E_K(X^S), and C' = E_K(X'^S') = E_K((X^1)^(S^1)) = E_K(X^S) = C.
This condition can be recognized in the encrypted data.

In other words, here's the attack.  The attacker looks at two sectors,
number S and S', and looks at the first block of ciphertext in each sector,
call them C and C'.  If C = C', then the attacker knows that
X = X' ^ S ^ S', where X and X' denote the first block of plaintext in
each sector.  If plaintext were totally random, this would almost never
happen (with probability 2^-64 for a 64-bit block cipher).  However,
plaintext data often isn't exactly random.  There are some plausible
ways that the condition X = X' ^ S ^ S' could arise with non-negligible
probability, and if this happens, information leaks to the attacker.

Is this a problem worth fixing?  You'll have to decide.  Fortunately,
there is a simple fix: use the encrypted sector number as IV, not the
plaintext sector number.  In other words, the IV would be E_K(S), and
thus the first block of ciphertext would be C = E_K(X ^ E_K(S)).  This
fix makes the above attack go away.

Re: [PATCH] loop: fixing cryptoloop troubles.

[James Morris]

On Sun, 10 Aug 2003, Pascal Brisset wrote:

> A side note: Doesn't crypto/crypto_null.c need this fix ?:
> 
>  static void null_encrypt(void *ctx, u8 *dst, const u8 *src)
> -{ }
> +{ memmove(dst, src, NULL_BLOCK_SIZE); }
>  

What for?

See RFC 2410, section 2 :-)


- James
-- 
James Morris
<jmorris@intercode.com.au>

Re: [PATCH] loop: fixing cryptoloop troubles.

[Pascal Brisset]

James Morris writes:
 > See RFC 2410, section 2 :-)

This says NULL is the identity function, which is not the same as:

    static void null_encrypt(void *ctx, u8 *dst, const u8 *src)
    { }

In practice this code never gets called because cbc_process() has
a special case for iv==NULL.  But I'd rather see a semantically
correct reference implementation.  Or just leave .cia_encrypt=NULL.

Am I missing something here ?

-- Pascal

Re: [PATCH] loop: fixing cryptoloop troubles.

[James Morris]

On Sun, 10 Aug 2003, Pascal Brisset wrote:

> But I'd rather see a semantically correct reference implementation.

Ok, please take into account the case where src == dst.


- James
-- 
James Morris
<jmorris@intercode.com.au>

Re: [PATCH] loop: fixing cryptoloop troubles.

[Ingo Oeser]

Hi,

On Mon, Aug 11, 2003 at 02:28:08AM +1000, James Morris wrote:
> On Sun, 10 Aug 2003, Pascal Brisset wrote:
> 
> > But I'd rather see a semantically correct reference implementation.
> Ok, please take into account the case where src == dst.

Cryptoloop takes this into account?

This would mean, that you finally have in-place encryption
available. Good move!

Regards

Ingo Oeser

Re: [PATCH] loop: fixing cryptoloop troubles.

[Pascal Brisset]

James Morris writes:
 > Ok, please take into account the case where src == dst.

OK, looks like there is a tricky interplay between algorithms and
transforms.  Cipher implementors will need documentation here, e.g.
"cia_encrypt and cia_decrypt are always called with src==dst UNLESS
we are running in CBC mode AND cia_ivsize!=0" (Please confirm...)

Anybody who tries to bypass the scatterlist-based api by exporting
and calling crypto_alg_lookup() (as I did) will get bitten badly.

-- Pascal

Re: [PATCH] loop: fixing cryptoloop troubles.

[James Morris]

On Mon, 11 Aug 2003, Pascal Brisset wrote:

>  > Ok, please take into account the case where src == dst.
> 
> OK, looks like there is a tricky interplay between algorithms and
> transforms.  Cipher implementors will need documentation here, e.g.
> "cia_encrypt and cia_decrypt are always called with src==dst UNLESS
> we are running in CBC mode AND cia_ivsize!=0" (Please confirm...)

All implementors need to know at that level is that src may equal dst.


- James
-- 
James Morris
<jmorris@intercode.com.au>