cryptoapi highmem bug

cryptoapi highmem bug

[Christophe Saout]

Hi,

someone noticed strange corruptions with dm-crypt and highmem. After I
found out that I could force my machine to use highmem even though it
only has 256MB, I finally found the problem after some debugging:

The problem is in cbc_process (well, partly):

>      const int need_stack = (src == dst);
>      u8 stack[need_stack ? crypto_tfm_alg_blocksize(tfm) : 0];
>      u8 *buf = need_stack ? stack : dst;

src == dst fails if the page was in highmem because crypto_kmap will
assign two different virtual addresses for the same page.

The result is data corruption.

How could this be fixed?

scapperwalk_map could check if this page was already mapped (walk_in)
and reuse the virtual address if so. So a single page is only mapped
once and the check in cbc_process will work.

I can really use the src == dst case because I would need to allocate
unnecessary buffers (at least 512 bytes at a time and per cpu).

(I just hacked dm-crypt to allocate 512 bytes on the stack and use it
temporarily and kmap around myself to copy it back and the problem is
gone. Ugly.)

Re: cryptoapi highmem bug

[Jean-Luc Cooke]

Christophe,

What is calling cbc_process directly?  I don't see how any other function
could possibly call this function directly.

cipher.c's cipher() function called cbc_process() with two different src and
dst buffers, *always*.

Have any more info?

JLC

On Tue, Feb 24, 2004 at 09:49:14PM +0100, Christophe Saout wrote:
> Hi,
> 
> someone noticed strange corruptions with dm-crypt and highmem. After I
> found out that I could force my machine to use highmem even though it
> only has 256MB, I finally found the problem after some debugging:
> 
> The problem is in cbc_process (well, partly):
> 
> >      const int need_stack = (src == dst);
> >      u8 stack[need_stack ? crypto_tfm_alg_blocksize(tfm) : 0];
> >      u8 *buf = need_stack ? stack : dst;
> 
> src == dst fails if the page was in highmem because crypto_kmap will
> assign two different virtual addresses for the same page.
> 
> The result is data corruption.
> 
> How could this be fixed?
> 
> scapperwalk_map could check if this page was already mapped (walk_in)
> and reuse the virtual address if so. So a single page is only mapped
> once and the check in cbc_process will work.
> 
> I can really use the src == dst case because I would need to allocate
> unnecessary buffers (at least 512 bytes at a time and per cpu).
> 
> (I just hacked dm-crypt to allocate 512 bytes on the stack and use it
> temporarily and kmap around myself to copy it back and the problem is
> gone. Ugly.)
> 
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

-- 
http://www.certainkey.com
Suite 4560 CTTC
1125 Colonel By Dr.
Ottawa ON, K1S 5B6

Re: cryptoapi highmem bug

[Christophe Saout]

Am Di, den 24.02.2004 schrieb Jean-Luc Cooke um 23:34:

> What is calling cbc_process directly?  I don't see how any other function
> could possibly call this function directly.

Nobody is calling it directly.

> cipher.c's cipher() function called cbc_process() with two different src and
> dst buffers, *always*.

It you pass the same to ->encrypt_iv (like kblockd for reads) it will
kmap the same page twice and call cbc_process with two different virtual
addresses pointing to the same page.

Re: cryptoapi highmem bug

[Jean-Luc Cooke]

On Wed, Feb 25, 2004 at 12:01:24AM +0100, Christophe Saout wrote:
> Am Di, den 24.02.2004 schrieb Jean-Luc Cooke um 23:34:
> 
> > What is calling cbc_process directly?  I don't see how any other function
> > could possibly call this function directly.
> 
> Nobody is calling it directly.
> 
> > cipher.c's cipher() function called cbc_process() with two different src and
> > dst buffers, *always*.
> 
> It you pass the same to ->encrypt_iv (like kblockd for reads) it will
> kmap the same page twice and call cbc_process with two different virtual
> addresses pointing to the same page.

Ah right.  Wanring: this is a cryptographer hacking kernel - danger!

How do I check for equal real addresses from two virtual ones?

JLC

-- 
http://www.certainkey.com
Suite 4560 CTTC
1125 Colonel By Dr.
Ottawa ON, K1S 5B6

Re: cryptoapi highmem bug

[Andrew Morton]

Jean-Luc Cooke <jlcooke@certainkey.com> wrote:
>
> How do I check for equal real addresses from two virtual ones?

I don't think there is a practical way of doing this.  It would involve
comparing the virtual address with the kmap and atomic kmap regions,
performing a pagetable walk, extracting the pageframe.  If the page is not
in a kmap area generate the pageframe directly.  Make that work on all
architectures.  Very yuk.

If practical this API should have been defined in terms of
(page/offset/len) and it should have kmapped the pages itself.  I guess
it's too late for that.

Re: cryptoapi highmem bug

[James Morris]

On Tue, 24 Feb 2004, Andrew Morton wrote:

> Jean-Luc Cooke <jlcooke@certainkey.com> wrote:
> >
> > How do I check for equal real addresses from two virtual ones?
> 
> I don't think there is a practical way of doing this.  It would involve
> comparing the virtual address with the kmap and atomic kmap regions,
> performing a pagetable walk, extracting the pageframe.  If the page is not
> in a kmap area generate the pageframe directly.  Make that work on all
> architectures.  Very yuk.
> 
> If practical this API should have been defined in terms of
> (page/offset/len) and it should have kmapped the pages itself.  I guess
> it's too late for that.

Do you mean that the crypt() function should do kmapping?

It's not too late to change internals.



- James
-- 
James Morris
<jmorris@redhat.com>

Re: cryptoapi highmem bug

[Jean-Luc Cooke]

On Wed, Feb 25, 2004 at 08:27:49AM -0500, James Morris wrote:
> > If practical this API should have been defined in terms of
> > (page/offset/len) and it should have kmapped the pages itself.  I guess
> > it's too late for that.
> 
> Do you mean that the crypt() function should do kmapping?
> 
> It's not too late to change internals.

Can I get an example of how to do this with scatterlists?

JLC

-- 
http://www.certainkey.com
Suite 4560 CTTC
1125 Colonel By Dr.
Ottawa ON, K1S 5B6

Re: cryptoapi highmem bug

[Christophe Saout]

On Tue, Feb 24, 2004 at 10:00:30PM -0800, Andrew Morton wrote:

> I don't think there is a practical way of doing this.  It would involve
> comparing the virtual address with the kmap and atomic kmap regions,
> performing a pagetable walk, extracting the pageframe.  If the page is not
> in a kmap area generate the pageframe directly.  Make that work on all
> architectures.  Very yuk.

We could also "simply" avoid to map the same page twice. My first idea
turned out slightly more complicated than I expected but works.

It's just a proof of concept though, it would be less complicated if we
would just pass the other walk struct to the functions that take one
and let them do the checking (no need to disable preemption and use
per cpu variables). Hmm.


--- linux-2.6.3/crypto/cipher.c	2004-02-25 13:49:53.000000000 +0100
+++ linux-2.6.3.test/crypto/cipher.c	2004-02-25 16:23:53.094207712 +0100
@@ -15,6 +15,7 @@
 #include <linux/kernel.h>
 #include <linux/crypto.h>
 #include <linux/errno.h>
+#include <linux/percpu.h>
 #include <linux/mm.h>
 #include <linux/slab.h>
 #include <linux/pagemap.h>
@@ -42,6 +43,14 @@
 	KM_SOFTIRQ1,
 };
 
+struct kmapped_page {
+	struct page	*page;
+	void		*vaddr;
+	int		out;
+};
+
+static DEFINE_PER_CPU(struct kmapped_page[4], kmapped_pages);
+
 static inline void xor_64(u8 *a, const u8 *b)
 {
 	((u32 *)a)[0] ^= ((u32 *)b)[0];
@@ -64,7 +73,7 @@
 	return sg + 1;
 }
 
-void *which_buf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
+static void *which_buf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
 {
 	if (nbytes <= walk->len_this_page &&
 	    (((unsigned long)walk->data) & (PAGE_CACHE_SIZE - 1)) + nbytes <=
@@ -98,7 +107,38 @@
 
 static void scatterwalk_map(struct scatter_walk *walk, int out)
 {
-	walk->data = crypto_kmap(walk->page, out) + walk->offset;
+	struct kmapped_page *kmaps;
+	int idx = (in_softirq() ? 2 : 0) + out;
+	void *vaddr;
+
+	preempt_disable();
+	kmaps = __get_cpu_var(kmapped_pages);
+
+	if (kmaps[idx ^ 1].page == walk->page) {
+		vaddr = kmaps[idx ^ 1].vaddr;
+		out = kmaps[idx ^ 1].out;
+	} else
+		vaddr = crypto_kmap(walk->page, out);
+
+	kmaps[idx].page = walk->page;
+	kmaps[idx].vaddr = vaddr;
+	kmaps[idx].out = out;
+
+	walk->data = vaddr + walk->offset;
+}
+
+static void scatterwalk_unmap(void *vaddr, int out)
+{
+	struct kmapped_page *kmaps = __get_cpu_var(kmapped_pages);
+	int idx = (in_softirq() ? 2 : 0) + out;
+
+	if (kmaps[idx ^ 1].page != kmaps[idx].page)
+		crypto_kunmap(vaddr, kmaps[idx].out);
+
+	kmaps[idx].page = NULL;
+	kmaps[idx].vaddr = NULL;
+
+	preempt_enable();
 }
 
 static void scatter_page_done(struct scatter_walk *walk, int out,
@@ -127,7 +167,7 @@
 
 static void scatter_done(struct scatter_walk *walk, int out, int more)
 {
-	crypto_kunmap(walk->data, out);
+	scatterwalk_unmap(walk->data, out);
 	if (walk->len_this_page == 0 || !more)
 		scatter_page_done(walk, out, more);
 }
@@ -145,7 +185,7 @@
 			buf += walk->len_this_page;
 			nbytes -= walk->len_this_page;
 
-			crypto_kunmap(walk->data, out);
+			scatterwalk_unmap(walk->data, out);
 			scatter_page_done(walk, out, 1);
 			scatterwalk_map(walk, out);
 		}

Re: cryptoapi highmem bug

[Jean-Luc Cooke]

Not to be annoying...

Could you make this change against my patch at:
  http://jlcooke.ca/lkml/crypto_28feb2004.patch

I moved all the scatterwalk stuff into a scatterwalk.c file.

JLC

On Wed, Feb 25, 2004 at 04:51:22PM +0100, Christophe Saout wrote:
> On Wed, Feb 25, 2004 at 04:31:26PM +0100, Christophe Saout wrote:
> 
> > It's just a proof of concept though, it would be less complicated if we
> > would just pass the other walk struct to the functions that take one
> > and let them do the checking (no need to disable preemption and use
> > per cpu variables). Hmm.
> 
> Ok, this also works. It makes copy_chunks and crypt responsible for
> tracking the walk struct which might contain a page to reuse:
> 
> 
> --- linux-2.6.3/crypto/cipher.c	2004-02-25 13:49:53.000000000 +0100
> +++ linux-2.6.3.test/crypto/cipher.c	2004-02-25 16:46:58.430294600 +0100
> @@ -29,6 +29,7 @@
>  struct scatter_walk {
>  	struct scatterlist	*sg;
>  	struct page		*page;
> +	int			out;
>  	void			*data;
>  	unsigned int		len_this_page;
>  	unsigned int		len_this_segment;
> @@ -64,7 +65,7 @@
>  	return sg + 1;
>  }
>  
> -void *which_buf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
> +static void *which_buf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
>  {
>  	if (nbytes <= walk->len_this_page &&
>  	    (((unsigned long)walk->data) & (PAGE_CACHE_SIZE - 1)) + nbytes <=
> @@ -96,9 +97,23 @@
>  	walk->offset = sg->offset;
>  }
>  
> -static void scatterwalk_map(struct scatter_walk *walk, int out)
> +static void scatterwalk_map(struct scatter_walk *walk,
> +			    struct scatter_walk *other, int out)
>  {
> -	walk->data = crypto_kmap(walk->page, out) + walk->offset;
> +	if (other && other->page == walk->page) {
> +		walk->data = (other->data - other->offset) + walk->offset;
> +		walk->out = other->out;
> +	} else {
> +		walk->data = crypto_kmap(walk->page, out) + walk->offset;
> +		walk->out = out;
> +	}
> +}
> +
> +static void scatterwalk_unmap(struct scatter_walk *walk,
> +			      struct scatter_walk *other, int out)
> +{
> +	if (!other || other->page != walk->page)
> +		crypto_kunmap(walk->data, walk->out);
>  }
>  
>  static void scatter_page_done(struct scatter_walk *walk, int out,
> @@ -125,9 +140,10 @@
>  	}
>  }
>  
> -static void scatter_done(struct scatter_walk *walk, int out, int more)
> +static void scatter_done(struct scatter_walk *walk,
> +			 struct scatter_walk *other, int out, int more)
>  {
> -	crypto_kunmap(walk->data, out);
> +	scatterwalk_unmap(walk, other, out);
>  	if (walk->len_this_page == 0 || !more)
>  		scatter_page_done(walk, out, more);
>  }
> @@ -137,7 +153,7 @@
>   * has been verified as multiple of the block size.
>   */
>  static int copy_chunks(void *buf, struct scatter_walk *walk,
> -			size_t nbytes, int out)
> +		       struct scatter_walk *other, size_t nbytes, int out)
>  {
>  	if (buf != walk->data) {
>  		while (nbytes > walk->len_this_page) {
> @@ -145,9 +161,9 @@
>  			buf += walk->len_this_page;
>  			nbytes -= walk->len_this_page;
>  
> -			crypto_kunmap(walk->data, out);
> +			scatterwalk_unmap(walk, other, out);
>  			scatter_page_done(walk, out, 1);
> -			scatterwalk_map(walk, out);
> +			scatterwalk_map(walk, other, out);
>  		}
>  
>  		memcpy_dir(buf, walk->data, nbytes, out);
> @@ -189,21 +205,21 @@
>  	for(;;) {
>  		u8 *src_p, *dst_p;
>  
> -		scatterwalk_map(&walk_in, 0);
> -		scatterwalk_map(&walk_out, 1);
> +		scatterwalk_map(&walk_in, NULL, 0);
> +		scatterwalk_map(&walk_out, &walk_in, 1);
>  		src_p = which_buf(&walk_in, bsize, tmp_src);
>  		dst_p = which_buf(&walk_out, bsize, tmp_dst);
>  
>  		nbytes -= bsize;
>  
> -		copy_chunks(src_p, &walk_in, bsize, 0);
> +		copy_chunks(src_p, &walk_in, &walk_out, bsize, 0);
>  
>  		prfn(tfm, dst_p, src_p, crfn, enc, info);
>  
> -		scatter_done(&walk_in, 0, nbytes);
> +		scatter_done(&walk_in, &walk_out, 0, nbytes);
>  
> -		copy_chunks(dst_p, &walk_out, bsize, 1);
> -		scatter_done(&walk_out, 1, nbytes);
> +		copy_chunks(dst_p, &walk_out, NULL, bsize, 1);
> +		scatter_done(&walk_out, NULL, 1, nbytes);
>  
>  		if (!nbytes)
>  			return 0;

-- 
http://www.certainkey.com
Suite 4560 CTTC
1125 Colonel By Dr.
Ottawa ON, K1S 5B6

Re: cryptoapi highmem bug

[Christophe Saout]

On Wed, Feb 25, 2004 at 04:31:26PM +0100, Christophe Saout wrote:

> It's just a proof of concept though, it would be less complicated if we
> would just pass the other walk struct to the functions that take one
> and let them do the checking (no need to disable preemption and use
> per cpu variables). Hmm.

Ok, this also works. It makes copy_chunks and crypt responsible for
tracking the walk struct which might contain a page to reuse:


--- linux-2.6.3/crypto/cipher.c	2004-02-25 13:49:53.000000000 +0100
+++ linux-2.6.3.test/crypto/cipher.c	2004-02-25 16:46:58.430294600 +0100
@@ -29,6 +29,7 @@
 struct scatter_walk {
 	struct scatterlist	*sg;
 	struct page		*page;
+	int			out;
 	void			*data;
 	unsigned int		len_this_page;
 	unsigned int		len_this_segment;
@@ -64,7 +65,7 @@
 	return sg + 1;
 }
 
-void *which_buf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
+static void *which_buf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
 {
 	if (nbytes <= walk->len_this_page &&
 	    (((unsigned long)walk->data) & (PAGE_CACHE_SIZE - 1)) + nbytes <=
@@ -96,9 +97,23 @@
 	walk->offset = sg->offset;
 }
 
-static void scatterwalk_map(struct scatter_walk *walk, int out)
+static void scatterwalk_map(struct scatter_walk *walk,
+			    struct scatter_walk *other, int out)
 {
-	walk->data = crypto_kmap(walk->page, out) + walk->offset;
+	if (other && other->page == walk->page) {
+		walk->data = (other->data - other->offset) + walk->offset;
+		walk->out = other->out;
+	} else {
+		walk->data = crypto_kmap(walk->page, out) + walk->offset;
+		walk->out = out;
+	}
+}
+
+static void scatterwalk_unmap(struct scatter_walk *walk,
+			      struct scatter_walk *other, int out)
+{
+	if (!other || other->page != walk->page)
+		crypto_kunmap(walk->data, walk->out);
 }
 
 static void scatter_page_done(struct scatter_walk *walk, int out,
@@ -125,9 +140,10 @@
 	}
 }
 
-static void scatter_done(struct scatter_walk *walk, int out, int more)
+static void scatter_done(struct scatter_walk *walk,
+			 struct scatter_walk *other, int out, int more)
 {
-	crypto_kunmap(walk->data, out);
+	scatterwalk_unmap(walk, other, out);
 	if (walk->len_this_page == 0 || !more)
 		scatter_page_done(walk, out, more);
 }
@@ -137,7 +153,7 @@
  * has been verified as multiple of the block size.
  */
 static int copy_chunks(void *buf, struct scatter_walk *walk,
-			size_t nbytes, int out)
+		       struct scatter_walk *other, size_t nbytes, int out)
 {
 	if (buf != walk->data) {
 		while (nbytes > walk->len_this_page) {
@@ -145,9 +161,9 @@
 			buf += walk->len_this_page;
 			nbytes -= walk->len_this_page;
 
-			crypto_kunmap(walk->data, out);
+			scatterwalk_unmap(walk, other, out);
 			scatter_page_done(walk, out, 1);
-			scatterwalk_map(walk, out);
+			scatterwalk_map(walk, other, out);
 		}
 
 		memcpy_dir(buf, walk->data, nbytes, out);
@@ -189,21 +205,21 @@
 	for(;;) {
 		u8 *src_p, *dst_p;
 
-		scatterwalk_map(&walk_in, 0);
-		scatterwalk_map(&walk_out, 1);
+		scatterwalk_map(&walk_in, NULL, 0);
+		scatterwalk_map(&walk_out, &walk_in, 1);
 		src_p = which_buf(&walk_in, bsize, tmp_src);
 		dst_p = which_buf(&walk_out, bsize, tmp_dst);
 
 		nbytes -= bsize;
 
-		copy_chunks(src_p, &walk_in, bsize, 0);
+		copy_chunks(src_p, &walk_in, &walk_out, bsize, 0);
 
 		prfn(tfm, dst_p, src_p, crfn, enc, info);
 
-		scatter_done(&walk_in, 0, nbytes);
+		scatter_done(&walk_in, &walk_out, 0, nbytes);
 
-		copy_chunks(dst_p, &walk_out, bsize, 1);
-		scatter_done(&walk_out, 1, nbytes);
+		copy_chunks(dst_p, &walk_out, NULL, bsize, 1);
+		scatter_done(&walk_out, NULL, 1, nbytes);
 
 		if (!nbytes)
 			return 0;

Re: cryptoapi highmem bug

[Jean-Luc Cooke]

Darn.

http://jlcooke.ca/lkml/crypto_24feb2004.patch will work.

JLC

On Wed, Feb 25, 2004 at 05:13:41PM +0100, Christophe Saout wrote:
> Am Mi, den 25.02.2004 schrieb Jean-Luc Cooke um 16:44:
> 
> > Could you make this change against my patch at:
> >   http://jlcooke.ca/lkml/crypto_28feb2004.patch
> 
> The link is broken.
> 

-- 
http://www.certainkey.com
Suite 4560 CTTC
1125 Colonel By Dr.
Ottawa ON, K1S 5B6

Re: cryptoapi highmem bug

[Christophe Saout]

Am Mi, den 25.02.2004 schrieb Jean-Luc Cooke um 16:44:

> Could you make this change against my patch at:
>   http://jlcooke.ca/lkml/crypto_28feb2004.patch

The link is broken.

cryptoapi OMAC (was: cryptoapi highmem bug)

[Christophe Saout]

On Wed, Feb 25, 2004 at 11:09:35AM -0500, Jean-Luc Cooke wrote:

> http://jlcooke.ca/lkml/crypto_24feb2004.patch will work.

It didn't compile. I fixed some compile problems so that it works.
I have disabled CRYPTO_OMAC though. And it goes boom when calling
hmac_init (or something like that), the machine halts without Oops.

I've seen the cit_omac is kmalloc'ed. Hmm. Didn't we want to try
to avoid that? Well. Perhaps it should be allocated when the
omac_init is called and freed after omac_final.

Or what about this:
If the user wants OMAC he calls omac_init and passes a pointer to
a buffer where the omac will be computed. omac_init then sets
the omac_update function so that xxx_process will call it. After
the encryption is finished the user calls omac_final and finds
the omac in his buffer.

And shouldn't the omac functions be put into a separate omac.c?

Moving the scatterwalk functions seems like a good idea to me.

Well, here are the compile fixes:

diff -Nur linux.orig/crypto/cipher.c linux/crypto/cipher.c
--- linux.orig/crypto/cipher.c	2004-02-25 18:58:22.955601768 +0100
+++ linux/crypto/cipher.c	2004-02-25 18:59:30.970261968 +0100
@@ -280,7 +280,7 @@
 			/* mac = Zeros */
 			memset((u8*)tfm->crt_u.cipher.cit_omac, 0, crypto_tfm_alg_blocksize(tfm));
 		}
-#endif
+#endif /* CONFIG_CRYPTO_OMAC */
 
 		return ret;
 	}
@@ -475,9 +475,12 @@
 	    	ops->cit_iv = kmalloc(ops->cit_ivsize, GFP_KERNEL);
 		if (ops->cit_iv == NULL)
 			ret = -ENOMEM;
+
+#ifdef CONFIG_CRYPTO_OMAC
 		ops->cit_omac = kmalloc(ops->cit_ivsize, GFP_KERNEL);
 		if (ops->cit_omac == NULL)
 			ret = -ENOMEM;
+#endif /* CONFIG_CRYPTO_OMAC */
 	}
 
 #ifdef CONFIG_CRYPTO_OMAC
@@ -499,5 +502,5 @@
 #ifdef CONFIG_CRYPTO_OMAC
 	if (tfm->crt_cipher.cit_omac)
 		kfree(tfm->crt_cipher.cit_omac);
-#endif
+#endif /* CONFIG_CRYPTO_OMAC */
 }

Re: cryptoapi highmem bug

[Christophe Saout]

On Wed, Feb 25, 2004 at 10:44:53AM -0500, Jean-Luc Cooke wrote:

> Not to be annoying...
> 
> Could you make this change against my patch at:
>   http://jlcooke.ca/lkml/crypto_28feb2004.patch

Ok, here it is. Still working (when not using omac or hmac) after
fixing the compile problems (see other mail).

If this is ok someone should split out the scatterwalk_* move from
your patch and submit it and this one to Andrew so that dm-crypt
doesn't go boom on highmem machines.


diff -Nur linux.orig/crypto/cipher.c linux/crypto/cipher.c
--- linux.orig/crypto/cipher.c	2004-02-25 18:59:30.970261968 +0100
+++ linux/crypto/cipher.c	2004-02-25 19:00:08.673530200 +0100
@@ -72,21 +72,21 @@
 	for(;;) {
 		u8 *src_p, *dst_p;
 
-		scatterwalk_map(&walk_in, 0);
-		scatterwalk_map(&walk_out, 1);
+		scatterwalk_map(&walk_in, NULL, 0);
+		scatterwalk_map(&walk_out, &walk_in, 1);
 		src_p = scatterwalk_whichbuf(&walk_in, bsize, tmp_src);
 		dst_p = scatterwalk_whichbuf(&walk_out, bsize, tmp_dst);
 
 		nbytes -= bsize;
 
-		scatterwalk_copychunks(src_p, &walk_in, bsize, 0);
+		scatterwalk_copychunks(src_p, &walk_in, &walk_out, bsize, 0);
 
 		prfn(tfm, dst_p, src_p, crfn, enc, info);
 
-		scatterwalk_done(&walk_in, 0, nbytes);
+		scatterwalk_done(&walk_in, &walk_out, 0, nbytes);
 
-		scatterwalk_copychunks(dst_p, &walk_out, bsize, 1);
-		scatterwalk_done(&walk_out, 1, nbytes);
+		scatterwalk_copychunks(dst_p, &walk_out, NULL, bsize, 1);
+		scatterwalk_done(&walk_out, NULL, 1, nbytes);
 
 		if (!nbytes)
 			return 0;
diff -Nur linux.orig/crypto/scatterwalk.c linux/crypto/scatterwalk.c
--- linux.orig/crypto/scatterwalk.c	2004-02-25 18:58:22.956601000 +0100
+++ linux/crypto/scatterwalk.c	2004-02-25 18:54:32.567626064 +0100
@@ -63,13 +63,27 @@
 	walk->offset = sg->offset;
 }
 
-void scatterwalk_map(struct scatter_walk *walk, int out)
+void scatterwalk_map(struct scatter_walk *walk, struct scatter_walk *other,
+		     int out)
 {
-	walk->data = crypto_kmap(walk->page, out) + walk->offset;
+	if (other && other->page == walk->page) {
+		walk->data = (other->data - other->offset) + walk->offset;
+		walk->slot = other->slot;
+	} else {
+		walk->data = crypto_kmap(walk->page, out) + walk->offset;
+		walk->slot = out;
+	}
+}
+
+static void scatterwalk_unmap(struct scatter_walk *walk,
+			      struct scatter_walk *other)
+{
+	if (!other || other->page != walk->page)
+		crypto_kunmap(walk->data, walk->slot);
 }
 
 static void scatterwalk_pagedone(struct scatter_walk *walk, int out,
-			      unsigned int more)
+				 unsigned int more)
 {
 	/* walk->data may be pointing the first byte of the next page;
 	   however, we know we transfered at least one byte.  So,
@@ -92,9 +106,10 @@
 	}
 }
 
-void scatterwalk_done(struct scatter_walk *walk, int out, int more)
+void scatterwalk_done(struct scatter_walk *walk, struct scatter_walk *reuse,
+		      int out, int more)
 {
-	crypto_kunmap(walk->data, out);
+	scatterwalk_unmap(walk, reuse);
 	if (walk->len_this_page == 0 || !more)
 		scatterwalk_pagedone(walk, out, more);
 }
@@ -104,7 +119,7 @@
  * has been verified as multiple of the block size.
  */
 int scatterwalk_copychunks(void *buf, struct scatter_walk *walk,
-			size_t nbytes, int out)
+			   struct scatter_walk *reuse, size_t nbytes, int out)
 {
 	if (buf != walk->data) {
 		while (nbytes > walk->len_this_page) {
@@ -112,9 +127,9 @@
 			buf += walk->len_this_page;
 			nbytes -= walk->len_this_page;
 
-			crypto_kunmap(walk->data, out);
+			scatterwalk_unmap(walk, reuse);
 			scatterwalk_pagedone(walk, out, 1);
-			scatterwalk_map(walk, out);
+			scatterwalk_map(walk, reuse, out);
 		}
 
 		memcpy_dir(buf, walk->data, nbytes, out);
diff -Nur linux.orig/crypto/scatterwalk.h linux/crypto/scatterwalk.h
--- linux.orig/crypto/scatterwalk.h	2004-02-25 18:58:22.956601000 +0100
+++ linux/crypto/scatterwalk.h	2004-02-25 18:54:32.573625152 +0100
@@ -26,6 +26,7 @@
 	struct scatterlist	*sg;
 	struct page		*page;
 	void			*data;
+	int			slot;
 	unsigned int		len_this_page;
 	unsigned int		len_this_segment;
 	unsigned int		offset;
@@ -40,8 +41,8 @@
 
 void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch);
 void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg);
-int scatterwalk_copychunks(void *buf, struct scatter_walk *walk, size_t nbytes, int out);
-void scatterwalk_map(struct scatter_walk *walk, int out);
-void scatterwalk_done(struct scatter_walk *walk, int out, int more);
+int scatterwalk_copychunks(void *buf, struct scatter_walk *walk, struct scatter_walk *reuse, size_t nbytes, int out);
+void scatterwalk_map(struct scatter_walk *walk, struct scatter_walk *reuse, int out);
+void scatterwalk_done(struct scatter_walk *walk, struct scatter_walk *reuse, int out, int more);
 
 #endif  /* _CRYPTO_SCATTERWALK_H */

Re: cryptoapi highmem bug

[Andrew Morton]

James Morris <jmorris@redhat.com> wrote:
>
> On Tue, 24 Feb 2004, Andrew Morton wrote:
> 
> > Jean-Luc Cooke <jlcooke@certainkey.com> wrote:
> > >
> > > How do I check for equal real addresses from two virtual ones?
> > 
> > I don't think there is a practical way of doing this.  It would involve
> > comparing the virtual address with the kmap and atomic kmap regions,
> > performing a pagetable walk, extracting the pageframe.  If the page is not
> > in a kmap area generate the pageframe directly.  Make that work on all
> > architectures.  Very yuk.
> > 
> > If practical this API should have been defined in terms of
> > (page/offset/len) and it should have kmapped the pages itself.  I guess
> > it's too late for that.
> 
> Do you mean that the crypt() function should do kmapping?

Passing the page* down one more level would permit cbc_process() to get at
the pageframes themselves, so it can sanely determine if src and dest
overlap.  (I assume this is for encryption-in-place).

Or maybe it's sufficient for crypt() to pass a simple boolean down to the
prfn() callout which says "this is in-place encryption".

Re: cryptoapi highmem bug

[Jean-Luc Cooke]

On Wed, Feb 25, 2004 at 07:15:40PM +0100, Christophe Saout wrote:
> Ok, here it is. Still working (when not using omac or hmac) after
> fixing the compile problems (see other mail).
> 
> If this is ok someone should split out the scatterwalk_* move from
> your patch and submit it and this one to Andrew so that dm-crypt
> doesn't go boom on highmem machines.

Great thanks a bunch.

Here is the scatterlist+"Le Patch de Christophe":
  http://jlcooke.ca/lkml/cryptowalk_christophe_25feb2004.patch

Reguarding dm-crypt:
 I didn't get a response back when suggesting we store IV and MAC info for
 each block.  Can we do this?  Can I do this?  Where's the source, in
 2.3.6-main?  I'd like to implement this IV and optional OMAC stuff for
 encrypted filesyetems (I assume that's that dm-crypt is replacing)

JLC

-- 
http://www.certainkey.com
Suite 4560 CTTC
1125 Colonel By Dr.
Ottawa ON, K1S 5B6

Re: cryptoapi highmem bug

[Christophe Saout]

On Wed, Feb 25, 2004 at 03:12:16PM -0500, Jean-Luc Cooke wrote:

> Here is the scatterlist+"Le Patch de Christophe":
>   http://jlcooke.ca/lkml/cryptowalk_christophe_25feb2004.patch

Andrew hat another idea that would be even shorter. I don't know if
it's much cleaner though. Trying to implement it.

> Reguarding dm-crypt:
>  I didn't get a response back when suggesting we store IV and MAC info for
>  each block.

Yes, sorry, it's on my todo list (but I kept pushing it back because
explaining the problems in detail would have taken a lot of time). ;)

>  Can we do this?

It's very non-trivial. Think about journalling filesystems, write
ordering and atomicity. If the system crashes between two write
operations we must be able to still correctly read the data. And
write to these "crypto info blocks" should be done in a ways that
doesn't kill performance. Do you have a proposal?

It would make dm-crypt *a lot more* complicated. We need caches
for the info blocks, etc...

>  Can I do this?  Where's the source, in
>  2.3.6-main?

Which source? dm-crypt? In 2.6.3-bk and 2.6.3-mm*. Andrew's latest
tree also has my first "more secure IV proposal" patch in it and I
posted a (broken, racy) hmac IV patch in the other thread.

Re: cryptoapi highmem bug

[Jean-Luc Cooke]

On Wed, Feb 25, 2004 at 09:39:32PM +0100, Christophe Saout wrote:
> >  I didn't get a response back when suggesting we store IV and MAC info for
> >  each block.
> 
> Yes, sorry, it's on my todo list (but I kept pushing it back because
> explaining the problems in detail would have taken a lot of time). ;)

:)  That's cool.

> >  Can we do this?
> 
> It's very non-trivial. Think about journalling filesystems, write
> ordering and atomicity. If the system crashes between two write
> operations we must be able to still correctly read the data. And
> write to these "crypto info blocks" should be done in a ways that
> doesn't kill performance. Do you have a proposal?

I see.  From a security point of view, no.  OMACs need to be updated after
the data is updated to keep integrity checks passing.  IVs need to be updated
before the data is updated or plaintext is leaked. (IV + data + OMAC can be
written to device at once).

I assume then that IVs and OMACs will not be stored in the same read-chunk as
the data then?  Bummer if this is the case.

> It would make dm-crypt *a lot more* complicated. We need caches
> for the info blocks, etc...

Yes I see how that would be nasty.  But I've never written for things this
low to the device so you are likly better off without me.

> >  Can I do this?  Where's the source, in
> >  2.3.6-main?
> 
> Which source? dm-crypt? In 2.6.3-bk and 2.6.3-mm*. Andrew's latest
> tree also has my first "more secure IV proposal" patch in it and I
> posted a (broken, racy) hmac IV patch in the other thread.
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

-- 
http://www.certainkey.com
Suite 4560 CTTC
1125 Colonel By Dr.
Ottawa ON, K1S 5B6

Re: cryptoapi OMAC (was: cryptoapi highmem bug)

[Jean-Luc Cooke]

OK.

Using a base kernel, apply the scatterwalk change:
  http://jlcooke.ca/lkml/cryptowalk_christophe_25feb2004.patch

Then apply this:
  http://jlcooke.ca/lkml/crypto_omac_hmac_ctr_25feb2004.patch

This is my HMAC/OMAC/CTR patch.  I think I fixed your HMAC issue.
I was giving a scatterlist a stack memory reference (!).  It now more
closely uses the digest.c functions.

JLC

On Wed, Feb 25, 2004 at 07:11:33PM +0100, Christophe Saout wrote:
> On Wed, Feb 25, 2004 at 11:09:35AM -0500, Jean-Luc Cooke wrote:
> 
> > http://jlcooke.ca/lkml/crypto_24feb2004.patch will work.
> 
> It didn't compile. I fixed some compile problems so that it works.
> I have disabled CRYPTO_OMAC though. And it goes boom when calling
> hmac_init (or something like that), the machine halts without Oops.
> 
> I've seen the cit_omac is kmalloc'ed. Hmm. Didn't we want to try
> to avoid that? Well. Perhaps it should be allocated when the
> omac_init is called and freed after omac_final.
> 
> Or what about this:
> If the user wants OMAC he calls omac_init and passes a pointer to
> a buffer where the omac will be computed. omac_init then sets
> the omac_update function so that xxx_process will call it. After
> the encryption is finished the user calls omac_final and finds
> the omac in his buffer.
> 
> And shouldn't the omac functions be put into a separate omac.c?
> 
> Moving the scatterwalk functions seems like a good idea to me.
> 
> Well, here are the compile fixes:
> 
> diff -Nur linux.orig/crypto/cipher.c linux/crypto/cipher.c
> --- linux.orig/crypto/cipher.c	2004-02-25 18:58:22.955601768 +0100
> +++ linux/crypto/cipher.c	2004-02-25 18:59:30.970261968 +0100
> @@ -280,7 +280,7 @@
>  			/* mac = Zeros */
>  			memset((u8*)tfm->crt_u.cipher.cit_omac, 0, crypto_tfm_alg_blocksize(tfm));
>  		}
> -#endif
> +#endif /* CONFIG_CRYPTO_OMAC */
>  
>  		return ret;
>  	}
> @@ -475,9 +475,12 @@
>  	    	ops->cit_iv = kmalloc(ops->cit_ivsize, GFP_KERNEL);
>  		if (ops->cit_iv == NULL)
>  			ret = -ENOMEM;
> +
> +#ifdef CONFIG_CRYPTO_OMAC
>  		ops->cit_omac = kmalloc(ops->cit_ivsize, GFP_KERNEL);
>  		if (ops->cit_omac == NULL)
>  			ret = -ENOMEM;
> +#endif /* CONFIG_CRYPTO_OMAC */
>  	}
>  
>  #ifdef CONFIG_CRYPTO_OMAC
> @@ -499,5 +502,5 @@
>  #ifdef CONFIG_CRYPTO_OMAC
>  	if (tfm->crt_cipher.cit_omac)
>  		kfree(tfm->crt_cipher.cit_omac);
> -#endif
> +#endif /* CONFIG_CRYPTO_OMAC */
>  }
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

-- 
http://www.certainkey.com
Suite 4560 CTTC
1125 Colonel By Dr.
Ottawa ON, K1S 5B6

Re: cryptoapi highmem bug

[Christophe Saout]

On Wed, Feb 25, 2004 at 11:50:27AM -0800, Andrew Morton wrote:

> Or maybe it's sufficient for crypt() to pass a simple boolean down to the
> prfn() callout which says "this is in-place encryption".

Yes, this works. As usual I was simply thinking too complicated. ;)

It looks like this now. It's on top of Jean-Luc's patch. Jean-Luc, can
update your patch and use this one instead? It's much simpler this way
and it keeps the whole voodoo in cipher.c.

diff -ur linux.orig/crypto/cipher.c linux/crypto/cipher.c
--- linux.orig/crypto/cipher.c	2004-02-25 17:26:06.000000000 +0100
+++ linux/crypto/cipher.c	2004-02-25 22:11:03.000000000 +0100
@@ -26,7 +26,7 @@
 
 typedef void (cryptfn_t)(void *, u8 *, const u8 *);
 typedef void (procfn_t)(struct crypto_tfm *, u8 *,
-                        u8*, cryptfn_t, int enc, void *);
+                        u8*, cryptfn_t, int enc, void *, int);
 
 static inline void xor_64(u8 *a, const u8 *b)
 {
@@ -81,7 +81,9 @@
 
 		scatterwalk_copychunks(src_p, &walk_in, bsize, 0);
 
-		prfn(tfm, dst_p, src_p, crfn, enc, info);
+		prfn(tfm, dst_p, src_p, crfn, enc, info,
+		     scatterwalk_samebuf(&walk_in, &walk_out,
+					 src_p, dst_p));
 
 		scatterwalk_done(&walk_in, 0, nbytes);
 
@@ -185,8 +187,8 @@
 }
 #endif /* CONFIG_CRYPTO_OMAC */
 
-static void cbc_process(struct crypto_tfm *tfm,
-                        u8 *dst, u8 *src, cryptfn_t fn, int enc, void *info)
+static void cbc_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
+			cryptfn_t fn, int enc, void *info, int in_place)
 {
 	u8 *iv = info;
 	
@@ -202,9 +204,8 @@
 		fn(crypto_tfm_ctx(tfm), dst, iv);
 		memcpy(iv, dst, crypto_tfm_alg_blocksize(tfm));
 	} else {
-		const int need_stack = (src == dst);
-		u8 stack[need_stack ? crypto_tfm_alg_blocksize(tfm) : 0];
-		u8 *buf = need_stack ? stack : dst;
+		u8 stack[in_place ? crypto_tfm_alg_blocksize(tfm) : 0];
+		u8 *buf = in_place ? stack : dst;
 		
 		fn(crypto_tfm_ctx(tfm), buf, src);
 		tfm->crt_u.cipher.cit_xor_block(buf, iv);
@@ -214,13 +215,12 @@
 	}
 }
 
-static void ctr_process(struct crypto_tfm *tfm,
-                        u8 *dst, u8 *src, cryptfn_t fn, int enc, void *info)
+static void ctr_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
+			cryptfn_t fn, int enc, void *info, int in_place)
 {
 	u8 *iv = info;
-	const int need_stack = (src == dst);
-	u8 stack[need_stack ? crypto_tfm_alg_blocksize(tfm) : 0];
-	u8 *buf = need_stack ? stack : dst;
+	u8 stack[in_place ? crypto_tfm_alg_blocksize(tfm) : 0];
+	u8 *buf = in_place ? stack : dst;
 	int i;
 
 	/* Null encryption */
@@ -255,7 +255,7 @@
 
 
 static void ecb_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
-                        cryptfn_t fn, int enc, void *info)
+			cryptfn_t fn, int enc, void *info, int in_place)
 {
 	/* we can use dst as scratch space since we overwrite it later */
 	omac_update(tfm, dst, src);
diff -ur linux.orig/crypto/scatterwalk.h linux/crypto/scatterwalk.h
--- linux.orig/crypto/scatterwalk.h	2004-02-25 17:26:06.000000000 +0100
+++ linux/crypto/scatterwalk.h	2004-02-25 22:10:15.000000000 +0100
@@ -38,6 +38,14 @@
 	return sg + 1;
 }
 
+static inline int scatterwalk_samebuf(struct scatter_walk *walk_in,
+				      struct scatter_walk *walk_out,
+				      void *src_p, void *dst_p)
+{
+	return walk_in->page == walk_out->page &&
+	       walk_in->data == src_p && walk_out->data == dst_p;
+}
+
 void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch);
 void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg);
 int scatterwalk_copychunks(void *buf, struct scatter_walk *walk, size_t nbytes, int out);

Re: cryptoapi highmem bug

[Christophe Saout]

On Wed, Feb 25, 2004 at 03:46:51PM -0500, Jean-Luc Cooke wrote:

> > >  Can we do this?
> > 
> > It's very non-trivial. Think about journalling filesystems, write
> > ordering and atomicity. If the system crashes between two write
> > operations we must be able to still correctly read the data. And
> > write to these "crypto info blocks" should be done in a ways that
> > doesn't kill performance. Do you have a proposal?
> 
> I see.  From a security point of view, no.  OMACs need to be updated after
> the data is updated to keep integrity checks passing.

Yes. But if the machine doesn't get to update the OMAC but the data has
already been written you must be able to still read the data somehow.

> IVs need to be updated before the data is updated or plaintext is leaked.

Hmm? What could be done: The IV "sequence number" is incremented by one
every time a sector gets written. The IV sequence numbers get written
to the info block later (after a timeout, memory pressure and we to
free some space in the cache or if the sequence has gone too far). When
we read and the OMAC doesn't match we can try to increase the IV
several times until it matches. Still the problem with the OMAC
atomicity...

> (IV + data + OMAC can be written to device at once).

You can't guarantee that anything gets written at once. You can only
make sure that something has been written. Or that something gets
written before something else (using barriers, but I don't know if that
is stable, it has never been used on bio level yet).

> I assume then that IVs and OMACs will not be stored in the same read-chunk as
> the data then?  Bummer if this is the case.

Well, we can't store it in the same sector because all 512 bytes are
already used data.

We could store less than 512 bytes in a sector but that would mean
splitting up data on a sub-sector level. That means we have to read
some sectors with untouched data (the first and the last), update
the data and write several sectors. But then we can't even guarantee
that sectors are atomicically written as seen by the filesystem.
This is... yuck.

Re: cryptoapi highmem bug

[Jean-Luc Cooke]

Read my mind Christophe!

This...
  http://jlcooke.ca/lkml/crypto_omac_hmac_ctr_25feb2004.patch

...and C.Saout's latest patch in single serving form:
  http://jlcooke.ca/lkml/crypto_omac_hmac_ctr_25feb2004_b.patch

JLC

On Wed, Feb 25, 2004 at 10:27:08PM +0100, Christophe Saout wrote:
> On Wed, Feb 25, 2004 at 11:50:27AM -0800, Andrew Morton wrote:
> 
> > Or maybe it's sufficient for crypt() to pass a simple boolean down to the
> > prfn() callout which says "this is in-place encryption".
> 
> Yes, this works. As usual I was simply thinking too complicated. ;)
> 
> It looks like this now. It's on top of Jean-Luc's patch. Jean-Luc, can
> update your patch and use this one instead? It's much simpler this way
> and it keeps the whole voodoo in cipher.c.
> 
> diff -ur linux.orig/crypto/cipher.c linux/crypto/cipher.c
> --- linux.orig/crypto/cipher.c	2004-02-25 17:26:06.000000000 +0100
> +++ linux/crypto/cipher.c	2004-02-25 22:11:03.000000000 +0100
> @@ -26,7 +26,7 @@
>  
>  typedef void (cryptfn_t)(void *, u8 *, const u8 *);
>  typedef void (procfn_t)(struct crypto_tfm *, u8 *,
> -                        u8*, cryptfn_t, int enc, void *);
> +                        u8*, cryptfn_t, int enc, void *, int);
>  
>  static inline void xor_64(u8 *a, const u8 *b)
>  {
> @@ -81,7 +81,9 @@
>  
>  		scatterwalk_copychunks(src_p, &walk_in, bsize, 0);
>  
> -		prfn(tfm, dst_p, src_p, crfn, enc, info);
> +		prfn(tfm, dst_p, src_p, crfn, enc, info,
> +		     scatterwalk_samebuf(&walk_in, &walk_out,
> +					 src_p, dst_p));
>  
>  		scatterwalk_done(&walk_in, 0, nbytes);
>  
> @@ -185,8 +187,8 @@
>  }
>  #endif /* CONFIG_CRYPTO_OMAC */
>  
> -static void cbc_process(struct crypto_tfm *tfm,
> -                        u8 *dst, u8 *src, cryptfn_t fn, int enc, void *info)
> +static void cbc_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
> +			cryptfn_t fn, int enc, void *info, int in_place)
>  {
>  	u8 *iv = info;
>  	
> @@ -202,9 +204,8 @@
>  		fn(crypto_tfm_ctx(tfm), dst, iv);
>  		memcpy(iv, dst, crypto_tfm_alg_blocksize(tfm));
>  	} else {
> -		const int need_stack = (src == dst);
> -		u8 stack[need_stack ? crypto_tfm_alg_blocksize(tfm) : 0];
> -		u8 *buf = need_stack ? stack : dst;
> +		u8 stack[in_place ? crypto_tfm_alg_blocksize(tfm) : 0];
> +		u8 *buf = in_place ? stack : dst;
>  		
>  		fn(crypto_tfm_ctx(tfm), buf, src);
>  		tfm->crt_u.cipher.cit_xor_block(buf, iv);
> @@ -214,13 +215,12 @@
>  	}
>  }
>  
> -static void ctr_process(struct crypto_tfm *tfm,
> -                        u8 *dst, u8 *src, cryptfn_t fn, int enc, void *info)
> +static void ctr_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
> +			cryptfn_t fn, int enc, void *info, int in_place)
>  {
>  	u8 *iv = info;
> -	const int need_stack = (src == dst);
> -	u8 stack[need_stack ? crypto_tfm_alg_blocksize(tfm) : 0];
> -	u8 *buf = need_stack ? stack : dst;
> +	u8 stack[in_place ? crypto_tfm_alg_blocksize(tfm) : 0];
> +	u8 *buf = in_place ? stack : dst;
>  	int i;
>  
>  	/* Null encryption */
> @@ -255,7 +255,7 @@
>  
>  
>  static void ecb_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
> -                        cryptfn_t fn, int enc, void *info)
> +			cryptfn_t fn, int enc, void *info, int in_place)
>  {
>  	/* we can use dst as scratch space since we overwrite it later */
>  	omac_update(tfm, dst, src);
> diff -ur linux.orig/crypto/scatterwalk.h linux/crypto/scatterwalk.h
> --- linux.orig/crypto/scatterwalk.h	2004-02-25 17:26:06.000000000 +0100
> +++ linux/crypto/scatterwalk.h	2004-02-25 22:10:15.000000000 +0100
> @@ -38,6 +38,14 @@
>  	return sg + 1;
>  }
>  
> +static inline int scatterwalk_samebuf(struct scatter_walk *walk_in,
> +				      struct scatter_walk *walk_out,
> +				      void *src_p, void *dst_p)
> +{
> +	return walk_in->page == walk_out->page &&
> +	       walk_in->data == src_p && walk_out->data == dst_p;
> +}
> +
>  void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch);
>  void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg);
>  int scatterwalk_copychunks(void *buf, struct scatter_walk *walk, size_t nbytes, int out);

-- 
http://www.certainkey.com
Suite 4560 CTTC
1125 Colonel By Dr.
Ottawa ON, K1S 5B6

Re: cryptoapi OMAC (was: cryptoapi highmem bug)

[Christophe Saout]

Am Mi, den 25.02.2004 schrieb Jean-Luc Cooke um 21:59:

> Then apply this:
>   http://jlcooke.ca/lkml/crypto_omac_hmac_ctr_25feb2004.patch
> 
> This is my HMAC/OMAC/CTR patch.  I think I fixed your HMAC issue.
> I was giving a scatterlist a stack memory reference (!).

Hmm? That's not a problem per se.

I will look at it. But I still see a lot of room for improvement
especially concerning the cipher.c changes. And I don't think all of
your changes to the digest code are really necessary.

Re: cryptoapi highmem bug

[Jean-Luc Cooke]

On Wed, Feb 25, 2004 at 10:36:48PM +0100, Christophe Saout wrote:
> On Wed, Feb 25, 2004 at 03:46:51PM -0500, Jean-Luc Cooke wrote:
> 
> > > >  Can we do this?
> > > 
> > > It's very non-trivial. Think about journalling filesystems, write
> > > ordering and atomicity. If the system crashes between two write
> > > operations we must be able to still correctly read the data. And
> > > write to these "crypto info blocks" should be done in a ways that
> > > doesn't kill performance. Do you have a proposal?
> > 
> > I see.  From a security point of view, no.  OMACs need to be updated after
> > the data is updated to keep integrity checks passing.
> 
> Yes. But if the machine doesn't get to update the OMAC but the data has
> already been written you must be able to still read the data somehow.

Agreed.  Some magic is needed here.

> > IVs need to be updated before the data is updated or plaintext is leaked.
> 
> Hmm? What could be done: The IV "sequence number" is incremented by one
> every time a sector gets written. The IV sequence numbers get written
> to the info block later (after a timeout, memory pressure and we to
> free some space in the cache or if the sequence has gone too far). When
> we read and the OMAC doesn't match we can try to increase the IV
> several times until it matches. Still the problem with the OMAC
> atomicity...

At mkfs, each block is given IV=HMAC(Key,blockNum).  Every time data is written
to the block, encrypt with IV'=IV+1 and store IV'.

Donno if I like the "if at first we don't succeed, try try again" approach.
But you know better then I do how difficult caching info blocks will be.

> > (IV + data + OMAC can be written to device at once).
> 
> You can't guarantee that anything gets written at once. You can only
> make sure that something has been written. Or that something gets
> written before something else (using barriers, but I don't know if that
> is stable, it has never been used on bio level yet).

Caching sounds like a good way out.  Always consult the cache struct with a
lock for each N-blocks in the FS to reduce bottleneck-ing and let the cache
update at a sensible interval.  ...or am I talking black (block?) magic of the
worst kind here?

How about we set a goal for ourselves saying "we're prepared to accept X
performance degradation for encrypted file systems"?

> > I assume then that IVs and OMACs will not be stored in the same read-chunk as
> > the data then?  Bummer if this is the case.
> 
> Well, we can't store it in the same sector because all 512 bytes are
> already used data.
> 
> We could store less than 512 bytes in a sector but that would mean
> splitting up data on a sub-sector level. That means we have to read
> some sectors with untouched data (the first and the last), update
> the data and write several sectors. But then we can't even guarantee
> that sectors are atomicically written as seen by the filesystem.
> This is... yuck.

The "try try again" approach maybe our only way.  Yet, if someone reads data
from the FS and the IV wasn't written to disk yet (or ever in the case of a
crash) then incrementing will not solve anything.  Screwed again.

JLC - will think about this on the bus ride home.

-- 
http://www.certainkey.com
Suite 4560 CTTC
1125 Colonel By Dr.
Ottawa ON, K1S 5B6

[PATCH 1/2] move scatterwalk functions to own file

[Christophe Saout]

Hi,

I've cleaned up the latest patches and adjusted the header files.

This patch moves the scatterwalk functions from cipher.c to
scatterwalk.c and adds a header file.

diff -Nur linux.orig/crypto/cipher.c linux/crypto/cipher.c
--- linux.orig/crypto/cipher.c	2004-02-25 23:40:51.976030000 +0100
+++ linux/crypto/cipher.c	2004-02-25 23:43:39.125619688 +0100
@@ -4,7 +4,6 @@
  * Cipher operations.
  *
  * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
- * Generic scatterwalk code by Adam J. Richter <adam@yggdrasil.com>.
  *
  * This program is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License as published by the Free
@@ -17,31 +16,14 @@
 #include <linux/errno.h>
 #include <linux/mm.h>
 #include <linux/slab.h>
-#include <linux/pagemap.h>
-#include <linux/highmem.h>
 #include <asm/scatterlist.h>
 #include "internal.h"
+#include "scatterwalk.h"
 
 typedef void (cryptfn_t)(void *, u8 *, const u8 *);
 typedef void (procfn_t)(struct crypto_tfm *, u8 *,
                         u8*, cryptfn_t, int enc, void *);
 
-struct scatter_walk {
-	struct scatterlist	*sg;
-	struct page		*page;
-	void			*data;
-	unsigned int		len_this_page;
-	unsigned int		len_this_segment;
-	unsigned int		offset;
-};
-
-enum km_type crypto_km_types[] = {
-	KM_USER0,
-	KM_USER1,
-	KM_SOFTIRQ0,
-	KM_SOFTIRQ1,
-};
-
 static inline void xor_64(u8 *a, const u8 *b)
 {
 	((u32 *)a)[0] ^= ((u32 *)b)[0];
@@ -57,108 +39,6 @@
 }
 
 
-/* Define sg_next is an inline routine now in case we want to change
-   scatterlist to a linked list later. */
-static inline struct scatterlist *sg_next(struct scatterlist *sg)
-{
-	return sg + 1;
-}
-
-void *which_buf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
-{
-	if (nbytes <= walk->len_this_page &&
-	    (((unsigned long)walk->data) & (PAGE_CACHE_SIZE - 1)) + nbytes <=
-	    PAGE_CACHE_SIZE)
-		return walk->data;
-	else
-		return scratch;
-}
-
-static void memcpy_dir(void *buf, void *sgdata, size_t nbytes, int out)
-{
-	if (out)
-		memcpy(sgdata, buf, nbytes);
-	else
-		memcpy(buf, sgdata, nbytes);
-}
-
-static void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
-{
-	unsigned int rest_of_page;
-
-	walk->sg = sg;
-
-	walk->page = sg->page;
-	walk->len_this_segment = sg->length;
-
-	rest_of_page = PAGE_CACHE_SIZE - (sg->offset & (PAGE_CACHE_SIZE - 1));
-	walk->len_this_page = min(sg->length, rest_of_page);
-	walk->offset = sg->offset;
-}
-
-static void scatterwalk_map(struct scatter_walk *walk, int out)
-{
-	walk->data = crypto_kmap(walk->page, out) + walk->offset;
-}
-
-static void scatter_page_done(struct scatter_walk *walk, int out,
-			      unsigned int more)
-{
-	/* walk->data may be pointing the first byte of the next page;
-	   however, we know we transfered at least one byte.  So,
-	   walk->data - 1 will be a virutual address in the mapped page. */
-
-	if (out)
-		flush_dcache_page(walk->page);
-
-	if (more) {
-		walk->len_this_segment -= walk->len_this_page;
-
-		if (walk->len_this_segment) {
-			walk->page++;
-			walk->len_this_page = min(walk->len_this_segment,
-						  (unsigned)PAGE_CACHE_SIZE);
-			walk->offset = 0;
-		}
-		else
-			scatterwalk_start(walk, sg_next(walk->sg));
-	}
-}
-
-static void scatter_done(struct scatter_walk *walk, int out, int more)
-{
-	crypto_kunmap(walk->data, out);
-	if (walk->len_this_page == 0 || !more)
-		scatter_page_done(walk, out, more);
-}
-
-/*
- * Do not call this unless the total length of all of the fragments 
- * has been verified as multiple of the block size.
- */
-static int copy_chunks(void *buf, struct scatter_walk *walk,
-			size_t nbytes, int out)
-{
-	if (buf != walk->data) {
-		while (nbytes > walk->len_this_page) {
-			memcpy_dir(buf, walk->data, walk->len_this_page, out);
-			buf += walk->len_this_page;
-			nbytes -= walk->len_this_page;
-
-			crypto_kunmap(walk->data, out);
-			scatter_page_done(walk, out, 1);
-			scatterwalk_map(walk, out);
-		}
-
-		memcpy_dir(buf, walk->data, nbytes, out);
-	}
-
-	walk->offset += nbytes;
-	walk->len_this_page -= nbytes;
-	walk->len_this_segment -= nbytes;
-	return 0;
-}
-
 /* 
  * Generic encrypt/decrypt wrapper for ciphers, handles operations across
  * multiple page boundaries by using temporary blocks.  In user context,
@@ -191,19 +71,19 @@
 
 		scatterwalk_map(&walk_in, 0);
 		scatterwalk_map(&walk_out, 1);
-		src_p = which_buf(&walk_in, bsize, tmp_src);
-		dst_p = which_buf(&walk_out, bsize, tmp_dst);
+		src_p = scatterwalk_whichbuf(&walk_in, bsize, tmp_src);
+		dst_p = scatterwalk_whichbuf(&walk_out, bsize, tmp_dst);
 
 		nbytes -= bsize;
 
-		copy_chunks(src_p, &walk_in, bsize, 0);
+		scatterwalk_copychunks(src_p, &walk_in, bsize, 0);
 
 		prfn(tfm, dst_p, src_p, crfn, enc, info);
 
-		scatter_done(&walk_in, 0, nbytes);
+		scatterwalk_done(&walk_in, 0, nbytes);
 
-		copy_chunks(dst_p, &walk_out, bsize, 1);
-		scatter_done(&walk_out, 1, nbytes);
+		scatterwalk_copychunks(dst_p, &walk_out, bsize, 1);
+		scatterwalk_done(&walk_out, 1, nbytes);
 
 		if (!nbytes)
 			return 0;
@@ -229,7 +109,7 @@
 		const int need_stack = (src == dst);
 		u8 stack[need_stack ? crypto_tfm_alg_blocksize(tfm) : 0];
 		u8 *buf = need_stack ? stack : dst;
-		
+
 		fn(crypto_tfm_ctx(tfm), buf, src);
 		tfm->crt_u.cipher.cit_xor_block(buf, iv);
 		memcpy(iv, src, crypto_tfm_alg_blocksize(tfm));
diff -Nur linux.orig/crypto/internal.h linux/crypto/internal.h
--- linux.orig/crypto/internal.h	2004-02-25 23:40:51.978029000 +0100
+++ linux/crypto/internal.h	2004-02-25 23:44:24.367741840 +0100
@@ -11,6 +11,7 @@
  */
 #ifndef _CRYPTO_INTERNAL_H
 #define _CRYPTO_INTERNAL_H
+#include <linux/crypto.h>
 #include <linux/mm.h>
 #include <linux/highmem.h>
 #include <linux/interrupt.h>
diff -Nur linux.orig/crypto/Makefile linux/crypto/Makefile
--- linux.orig/crypto/Makefile	2004-02-25 23:41:19.026917000 +0100
+++ linux/crypto/Makefile	2004-02-25 23:43:39.132618624 +0100
@@ -4,7 +4,7 @@
 
 proc-crypto-$(CONFIG_PROC_FS) = proc.o
 
-obj-$(CONFIG_CRYPTO) += api.o cipher.o digest.o compress.o \
+obj-$(CONFIG_CRYPTO) += api.o scatterwalk.o cipher.o digest.o compress.o \
 			$(proc-crypto-y)
 
 obj-$(CONFIG_CRYPTO_HMAC) += hmac.o
diff -Nur linux.orig/crypto/scatterwalk.c linux/crypto/scatterwalk.c
--- linux.orig/crypto/scatterwalk.c	1970-01-01 01:00:00.000000000 +0100
+++ linux/crypto/scatterwalk.c	2004-02-25 23:43:39.133618472 +0100
@@ -0,0 +1,124 @@
+/*
+ * Cryptographic API.
+ *
+ * Cipher operations.
+ *
+ * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
+ *               2002 Adam J. Richter <adam@yggdrasil.com>
+ *               2004 Jean-Luc Cooke <jlcooke@certainkey.com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option) 
+ * any later version.
+ *
+ */
+#include <linux/kernel.h>
+#include <linux/mm.h>
+#include <linux/pagemap.h>
+#include <linux/highmem.h>
+#include <asm/scatterlist.h>
+#include "internal.h"
+#include "scatterwalk.h"
+
+enum km_type crypto_km_types[] = {
+	KM_USER0,
+	KM_USER1,
+	KM_SOFTIRQ0,
+	KM_SOFTIRQ1,
+};
+
+void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
+{
+	if (nbytes <= walk->len_this_page &&
+	    (((unsigned long)walk->data) & (PAGE_CACHE_SIZE - 1)) + nbytes <=
+	    PAGE_CACHE_SIZE)
+		return walk->data;
+	else
+		return scratch;
+}
+
+static void memcpy_dir(void *buf, void *sgdata, size_t nbytes, int out)
+{
+	if (out)
+		memcpy(sgdata, buf, nbytes);
+	else
+		memcpy(buf, sgdata, nbytes);
+}
+
+void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
+{
+	unsigned int rest_of_page;
+
+	walk->sg = sg;
+
+	walk->page = sg->page;
+	walk->len_this_segment = sg->length;
+
+	rest_of_page = PAGE_CACHE_SIZE - (sg->offset & (PAGE_CACHE_SIZE - 1));
+	walk->len_this_page = min(sg->length, rest_of_page);
+	walk->offset = sg->offset;
+}
+
+void scatterwalk_map(struct scatter_walk *walk, int out)
+{
+	walk->data = crypto_kmap(walk->page, out) + walk->offset;
+}
+
+static void scatterwalk_pagedone(struct scatter_walk *walk, int out,
+				 unsigned int more)
+{
+	/* walk->data may be pointing the first byte of the next page;
+	   however, we know we transfered at least one byte.  So,
+	   walk->data - 1 will be a virutual address in the mapped page. */
+
+	if (out)
+		flush_dcache_page(walk->page);
+
+	if (more) {
+		walk->len_this_segment -= walk->len_this_page;
+
+		if (walk->len_this_segment) {
+			walk->page++;
+			walk->len_this_page = min(walk->len_this_segment,
+						  (unsigned)PAGE_CACHE_SIZE);
+			walk->offset = 0;
+		}
+		else
+			scatterwalk_start(walk, sg_next(walk->sg));
+	}
+}
+
+void scatterwalk_done(struct scatter_walk *walk, int out, int more)
+{
+	crypto_kunmap(walk->data, out);
+	if (walk->len_this_page == 0 || !more)
+		scatterwalk_pagedone(walk, out, more);
+}
+
+/*
+ * Do not call this unless the total length of all of the fragments 
+ * has been verified as multiple of the block size.
+ */
+int scatterwalk_copychunks(void *buf, struct scatter_walk *walk,
+			   size_t nbytes, int out)
+{
+	if (buf != walk->data) {
+		while (nbytes > walk->len_this_page) {
+			memcpy_dir(buf, walk->data, walk->len_this_page, out);
+			buf += walk->len_this_page;
+			nbytes -= walk->len_this_page;
+
+			crypto_kunmap(walk->data, out);
+			scatterwalk_pagedone(walk, out, 1);
+			scatterwalk_map(walk, out);
+		}
+
+		memcpy_dir(buf, walk->data, nbytes, out);
+	}
+
+	walk->offset += nbytes;
+	walk->len_this_page -= nbytes;
+	walk->len_this_segment -= nbytes;
+	return 0;
+}
diff -Nur linux.orig/crypto/scatterwalk.h linux/crypto/scatterwalk.h
--- linux.orig/crypto/scatterwalk.h	1970-01-01 01:00:00.000000000 +0100
+++ linux/crypto/scatterwalk.h	2004-02-25 23:43:39.133618472 +0100
@@ -0,0 +1,42 @@
+/*
+ * Cryptographic API.
+ *
+ * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
+ * Copyright (c) 2002 Adam J. Richter <adam@yggdrasil.com>
+ * Copyright (c) 2004 Jean-Luc Cooke <jlcooke@certainkey.com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option)
+ * any later version.
+ *
+ */
+
+#ifndef _CRYPTO_SCATTERWALK_H
+#define _CRYPTO_SCATTERWALK_H
+#include <linux/mm.h>
+#include <asm/scatterlist.h>
+
+struct scatter_walk {
+	struct scatterlist	*sg;
+	struct page		*page;
+	void			*data;
+	unsigned int		len_this_page;
+	unsigned int		len_this_segment;
+	unsigned int		offset;
+};
+
+/* Define sg_next is an inline routine now in case we want to change
+   scatterlist to a linked list later. */
+static inline struct scatterlist *sg_next(struct scatterlist *sg)
+{
+	return sg + 1;
+}
+
+void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch);
+void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg);
+int scatterwalk_copychunks(void *buf, struct scatter_walk *walk, size_t nbytes, int out);
+void scatterwalk_map(struct scatter_walk *walk, int out);
+void scatterwalk_done(struct scatter_walk *walk, int out, int more);
+
+#endif  /* _CRYPTO_SCATTERWALK_H */

[PATCH 2/2] fix in-place de/encryption bug with highmem

[Christophe Saout]

This patch fixes the bug where in-place encryption was not detected
when the same highmem pages is mapped twice to different virtual
addresses.

This adds a parameter to xxx_process to indicate whether this is an
in-place encryption and moves the responsability to the caller using
a helper function scatterwalk.h.

diff -Nur linux.orig/crypto/cipher.c linux/crypto/cipher.c
--- linux.orig/crypto/cipher.c	2004-02-25 23:43:39.125619688 +0100
+++ linux/crypto/cipher.c	2004-02-25 23:44:51.335642096 +0100
@@ -22,7 +22,7 @@
 
 typedef void (cryptfn_t)(void *, u8 *, const u8 *);
 typedef void (procfn_t)(struct crypto_tfm *, u8 *,
-                        u8*, cryptfn_t, int enc, void *);
+                        u8*, cryptfn_t, int enc, void *, int);
 
 static inline void xor_64(u8 *a, const u8 *b)
 {
@@ -78,7 +78,9 @@
 
 		scatterwalk_copychunks(src_p, &walk_in, bsize, 0);
 
-		prfn(tfm, dst_p, src_p, crfn, enc, info);
+		prfn(tfm, dst_p, src_p, crfn, enc, info,
+		     scatterwalk_samebuf(&walk_in, &walk_out,
+					 src_p, dst_p));
 
 		scatterwalk_done(&walk_in, 0, nbytes);
 
@@ -92,8 +94,8 @@
 	}
 }
 
-static void cbc_process(struct crypto_tfm *tfm,
-                        u8 *dst, u8 *src, cryptfn_t fn, int enc, void *info)
+static void cbc_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
+			cryptfn_t fn, int enc, void *info, int in_place)
 {
 	u8 *iv = info;
 	
@@ -106,9 +108,8 @@
 		fn(crypto_tfm_ctx(tfm), dst, iv);
 		memcpy(iv, dst, crypto_tfm_alg_blocksize(tfm));
 	} else {
-		const int need_stack = (src == dst);
-		u8 stack[need_stack ? crypto_tfm_alg_blocksize(tfm) : 0];
-		u8 *buf = need_stack ? stack : dst;
+		u8 stack[in_place ? crypto_tfm_alg_blocksize(tfm) : 0];
+		u8 *buf = in_place ? stack : dst;
 
 		fn(crypto_tfm_ctx(tfm), buf, src);
 		tfm->crt_u.cipher.cit_xor_block(buf, iv);
@@ -119,7 +120,7 @@
 }
 
 static void ecb_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
-                        cryptfn_t fn, int enc, void *info)
+			cryptfn_t fn, int enc, void *info, int in_place)
 {
 	fn(crypto_tfm_ctx(tfm), dst, src);
 }
diff -Nur linux.orig/crypto/scatterwalk.h linux/crypto/scatterwalk.h
--- linux.orig/crypto/scatterwalk.h	2004-02-25 23:43:39.133618472 +0100
+++ linux/crypto/scatterwalk.h	2004-02-25 23:44:51.342641032 +0100
@@ -33,6 +33,14 @@
 	return sg + 1;
 }
 
+static inline int scatterwalk_samebuf(struct scatter_walk *walk_in,
+				      struct scatter_walk *walk_out,
+				      void *src_p, void *dst_p)
+{
+	return walk_in->page == walk_out->page &&
+	       walk_in->data == src_p && walk_out->data == dst_p;
+}
+
 void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch);
 void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg);
 int scatterwalk_copychunks(void *buf, struct scatter_walk *walk, size_t nbytes, int out);

Re: [PATCH 2/2] fix in-place de/encryption bug with highmem

[James Morris]

On Wed, 25 Feb 2004, Christophe Saout wrote:

> This patch fixes the bug where in-place encryption was not detected
> when the same highmem pages is mapped twice to different virtual
> addresses.
> 
> This adds a parameter to xxx_process to indicate whether this is an
> in-place encryption and moves the responsability to the caller using
> a helper function scatterwalk.h.

These patches look good (now in -mm4), thanks for doing this.

Have you verified that the data corruption bug you saw has been fixed?
(Just in case there's more to it).


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 2/2] fix in-place de/encryption bug with highmem

[Christophe Saout]

Am Do, den 26.02.2004 schrieb James Morris um 05:13:

> Have you verified that the data corruption bug you saw has been fixed?
> (Just in case there's more to it).

Yes, it's fixed. I've got a collection of tests scripts here to verify
the data integrity. They are able to trigger all kinds of bugs (assuming
there is a bug of course).