Re: [PATCHv2 4/6] crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)
On Tue, Nov 28, 2006 at 10:17:39PM +0100, [EMAIL PROTECTED] wrote:
>
> Did you try my patch: [PATCH] adding speed_test_template for lrw(aes)
> which I sent on Sep 23?
Aha, that got buried in my mailbox. I'll push it out soon.
Cheers,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[EMAIL PROTECTED]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
-
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCHv2 4/6] crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)
Hello Herbert, On Wed, Nov 29, 2006 at 08:13:40AM +1100, Herbert Xu wrote: > > It's OK. The source will be more maintainable, but constantly converting > > between big and little-endian (on little endian machines) may have a > > significant performance impact (I will just test when your gf128 hits > > cryptodev-2.6, and complain if it is the case). > > BTW, the tcrypt speed test for lrw doesn't work for me. Did you try my patch: [PATCH] adding speed_test_template for lrw(aes) which I sent on Sep 23? > > This seems to be the problem, the table is constructed wrongly. > > All the calculations take place as if we are on a big endian machine, so > > the table entries should never be swapped, so the above line should read > > > > +#define xx(p, q) 0x##p##q > > Yes you're quite right. That was the problem. I'll push this into mm > as soon as I get the speed tests fixed. Ok, that's good news. Greetings, Rik. -- Nothing is ever a total loss; it can always serve as a bad example. - To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCHv2 4/6] crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)
Hi Rik:
[EMAIL PROTECTED] wrote:
>
> It's OK. The source will be more maintainable, but constantly converting
> between big and little-endian (on little endian machines) may have a
> significant performance impact (I will just test when your gf128 hits
> cryptodev-2.6, and complain if it is the case).
BTW, the tcrypt speed test for lrw doesn't work for me.
> Two more remarks (errors in v2 of my patch): b128ops.h and gf128mul.h
> should be in include/ (so they can be used in modules) and the inline
> functions in b128ops.h should also be static.
Yep they're in include/crypto with all the functions being static inline.
> This seems to be the problem, the table is constructed wrongly.
> All the calculations take place as if we are on a big endian machine, so
> the table entries should never be swapped, so the above line should read
>
> +#define xx(p, q) 0x##p##q
Yes you're quite right. That was the problem. I'll push this into mm
as soon as I get the speed tests fixed.
Thanks!
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[EMAIL PROTECTED]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
-
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCHv2 4/6] crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)
Hello Herbert,
On Mon, Nov 27, 2006 at 10:56:07AM +1100, Herbert Xu wrote:
> On Sat, Sep 02, 2006 at 03:00:25AM +0200, [EMAIL PROTECTED] wrote:
>
> Sorry it took so long. But I've been trying to modify the code so
> that the same source is used for both BE and LE machines. I've
> finally accumulated enough time to finish it.
It's OK. The source will be more maintainable, but constantly converting
between big and little-endian (on little endian machines) may have a
significant performance impact (I will just test when your gf128 hits
cryptodev-2.6, and complain if it is the case).
Two more remarks (errors in v2 of my patch): b128ops.h and gf128mul.h
should be in include/ (so they can be used in modules) and the inline
functions in b128ops.h should also be static.
> Unfortunately it seems that the end result doesn't quite agree with
> your test vectors :) In particular, the LE version of your mul_x and
> mul_x8 functions don't agree with mine.
>
> Could you please compare the two versions and double-check them?
> I'm unsure why 15 was used above as a shift count. It would seem
> that 7 would seem to make more sense as endianness is byte-based
> not word-based.
> >
> > +#define M80X 0x8080808080808080LLU
> > +#define M01X 0x0101010101010101LLU
> > +
> > +static void gf128mul_x_lle(u64 r[2], const u64 x[2])
> > +{
> > + u64 _tt = gf128mul_table_lle[(x[1] >> 49) & 0x80];
> > + r[1] = ((x[1] >> 1) & ~M80X) | (((x[1] << 15) | (x[0] >> 49)) & M80X);
> > + r[0] = (((x[0] >> 1) & ~M80X) | ((x[0] << 15) & M80X)) ^ _tt;
> > +}
I'll try to explain why I think the above code is correct:
As in my comment in gf128mul.h, lle means the polynomials in gf127 are
stored in little-little-endian format. So
1000 .. = 0x80 0x00 .. 0x00 = 1
0100 .. = 0x40 0x00 .. 0x00 = X^1
01010001 .. 1000 = 0x51 0x00 .. 0x80 = X^1 + X^3 + X^7 + X^120
.. 0001 = 0x00 0x00 .. 0x01 = X^127
The u64 type emulates a little endian 64bit processor (on my 32bit
intel) so when we load the these examples in two 64bit little endian
integers they are:
0x0080 0x = 1
0x0040 0x = X^1
0x0051 0x8000 = X^1 + X^3 + X^7 + X^120
0x 0x0100 = X^127
Let's multiply the third example by X, we should get
00101000 1000 .. 0100 = 0x28 0x80 .. 0x40 = X^2 + X^4 + X^8 + X^121
Represented as two little endian 64 bit values:
0x8028 0x4000
The above code implements this shift (efficiently?) by noting:
in each byte bit 1 moves to bit 0, bit 2 moves to bit 1, ..., bit 7
moves to bit 6 and all 7th bits are zeroed afterwards.
(this is done by ((x[1] >> 1) & ~M80X)), the 7th bits are set by moving
the least significant bits of the bytes to the right position (15 bits
to the left) and orring.
Let's look at the example: the first 8 in 0x0...008028 comes from the
least significant bit of 0x00.00051. So the shift by 15 to get the 7th
bit of every byte right is correct. (I have included a simple program
to compare the different implementations)
> I've attached my version of gf128mul which is based on your BE
> code.
Ok, will comment.
> The other main change I've made is to remove the need to
> allocate a contiguous 64K table in gf128mul. Requiring every
> tfm to allocate a contiguous 64K chunk of memory is not realistic
> on Linux.
Ok.
> I also added a be128/le128/u128 type to make 128-bit operations
> easier.
I assume it is: typedef struct { u64 a, u64 b } be128;
As long as compilers don't do u128 natively it is just a matter of taste.
> [...]
> +#define xx(p, q) __constant_be16_to_cpu(0x##p##q)
This seems to be the problem, the table is constructed wrongly.
All the calculations take place as if we are on a big endian machine, so
the table entries should never be swapped, so the above line should read
+#define xx(p, q) 0x##p##q
While investigating the problem, I wrote a small program to compare
a bytewise implementation with Brian's and your implementation of mul_x,
it only works in the lle implementation.
Once I found this problem, I stopped looking, so let me know if the test
vectors still don't match up, then I will need to take a closer look.
Greetings,
Rik.
/* test program for mutiplying by X in GF(2^128) in lle representation
* on a little endian machine. */
/* GNU GPL >= v2 applies, (C) Brian Gladman, Herbert Xu, Rik Snel. */
#include
#include
#include
#include
#include
typedef uint64_t u64;
typedef uint16_t u16;
typedef struct {
u64 a;
u64 b;
} be128;
#define gf128mul_dat(q) { \
q(0x00), q(0x01), q(0x02), q(0x03), q(0x04), q(0x05), q(0x06), q(0x07),\
q(0x08), q(0x09), q(0x0a), q(0x0b), q(0x0c), q(0x0d), q(0x0e), q(0x0f),\
q(0x10), q(0x11), q(0x12), q(0x13), q(0x14), q(0x15), q(0x16), q(0x17),\
q(0x18), q(0x19), q(0x1a), q(0x1b), q(0x1c), q(0x1d), q(0
Re: [PATCHv2 4/6] crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)
On Sat, Sep 02, 2006 at 03:00:25AM +0200, [EMAIL PROTECTED] wrote:
>
> +#define M80X 0x8080808080808080LLU
> +#define M01X 0x0101010101010101LLU
> +
> +static void gf128mul_x_lle(u64 r[2], const u64 x[2])
> +{
> + u64 _tt = gf128mul_table_lle[(x[1] >> 49) & 0x80];
> + r[1] = ((x[1] >> 1) & ~M80X) | (((x[1] << 15) | (x[0] >> 49)) & M80X);
> + r[0] = (((x[0] >> 1) & ~M80X) | ((x[0] << 15) & M80X)) ^ _tt;
> +}
Hi Rik:
Sorry it took so long. But I've been trying to modify the code so
that the same source is used for both BE and LE machines. I've
finally accumulated enough time to finish it.
Unfortunately it seems that the end result doesn't quite agree with
your test vectors :) In particular, the LE version of your mul_x and
mul_x8 functions don't agree with mine.
Could you please compare the two versions and double-check them?
I'm unsure why 15 was used above as a shift count. It would seem
that 7 would seem to make more sense as endianness is byte-based
not word-based.
I've attached my version of gf128mul which is based on your BE
code.
The other main change I've made is to remove the need to
allocate a contiguous 64K table in gf128mul. Requiring every
tfm to allocate a contiguous 64K chunk of memory is not realistic
on Linux.
I also added a be128/le128/u128 type to make 128-bit operations
easier.
Thanks,
--
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[EMAIL PROTECTED]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--
0c3bbb342495d510631b11c45a70d55fc83afe3f
diff --git a/crypto/Kconfig b/crypto/Kconfig
index 34f10d5..0a4ff51 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -139,6 +139,16 @@ config CRYPTO_TGR192
See also:
