[RFC][PATCH 2/2] Twofish cipher x86_64-asm optimized

[RFC][PATCH 2/2] Twofish cipher x86_64-asm optimized

[Joachim Fritschi]

Implementation:
-----------------------
This code is based on the current linux twofish cipher c implementation. Only 
the decrypt/encrypt routines were replaced by optimized assembler code. The 
in-kernel code by Matthew Skala takes care of the keysetup and precomputation 
of the sbox lookup tables.
I have eliminated stack use, tried to optimize the code as much as possible 
and limit code size. The patch is similar to the existing aes assembler 
implementation.

Testing:
-----------
The code passed the kernel test module and passed automated tests on a 
dm-crypt volume reading/writing large files with alternating modules ( c / 
assembler ) and comparing results. It is also running on my workstation for 
over a week now.

Benchmarks:
-------------------

Performance on a dm-crypt volume increased about 47% while reading. With 
256bit keylength its pretty close to the speed of the aes assembler version.

http://homepages.tu-darmstadt.de/~fritschi/twofish/output_20060426_175710_x86_64.html

The write performance in this benchmark was limited by the harddrive and not 
the algorithm / system speed. Any suggestions how to benchmark the overall 
speed accurately are welcome.


Patch:
----------

http://homepages.tu-darmstadt.de/~fritschi/twofish/twofish-x86_64-asm-2.6.17.diff


Please have a look, try, improve and criticise.

Regards,
Joachim

Re: [RFC][PATCH 2/2] Twofish cipher x86_64-asm optimized

[Andi Kleen]

Joachim Fritschi <jfritschi@freenet.de> writes:
> 
> Testing:
> -----------
> The code passed the kernel test module and passed automated tests on a 
> dm-crypt volume reading/writing large files with alternating modules ( c / 
> assembler ) and comparing results. It is also running on my workstation for 
> over a week now.

It would be good if you could run some random input encrypt/decrypt tests 
comparing the C reference version with yours. We have had bad luck 
with assembler functions not quite implementing the same cipher 
in the past.

> 
> Please have a look, try, improve and criticise.

Is it really needed to duplicate all the C code and tables - can't that 
be shared with the portable C code? 

Also don't make it a separate config - it should just be a replacement
on x86-64.

-Andi

Re: [RFC][PATCH 2/2] Twofish cipher x86_64-asm optimized

[Herbert Xu]

On Sun, May 07, 2006 at 12:38:30PM +0200, Andi Kleen wrote:
> 
> It would be good if you could run some random input encrypt/decrypt tests 
> comparing the C reference version with yours. We have had bad luck 
> with assembler functions not quite implementing the same cipher 
> in the past.

That's a very good point.  The tcrypt module provides both correctness
tests as well as speed tests for twofish.  Please run it with your
version versus the existing implementation.

BTW, crypto stuff should cc linux-crypto@vger.kernel.org.

Thanks,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [RFC][PATCH 2/2] Twofish cipher x86_64-asm optimized

[Joachim Fritschi]

> > Testing:
> > -----------
> > The code passed the kernel test module and passed automated tests on a
> > dm-crypt volume reading/writing large files with alternating modules ( c
> > / assembler ) and comparing results. It is also running on my workstation
> > for over a week now.
>
> It would be good if you could run some random input encrypt/decrypt tests
> comparing the C reference version with yours. We have had bad luck
> with assembler functions not quite implementing the same cipher
> in the past.

That's exactly what my skript did.

http://homepages.tu-darmstadt.de/~fritschi/twofish/test_twofish.sh

Be careful with this script. It formats the testpartition you specify. The 
script assumes you have both modules (c and asm) compiled as modules.
It generates a 1Gb random file and a random passphrase. It copies the file on 
your crypted partition with the c module and reads it again with the asm 
module. Then it copies the file again onto the crypto partition with the asm 
module and reads it with the c module. After each step the md5sum of the 
files are compared with the original file. Then the script starts all over 
again with a new random file and passphrase.

My modules also pass the tcrypt tests.

> > Please have a look, try, improve and criticise.
>
> Is it really needed to duplicate all the C code and tables - can't that
> be shared with the portable C code?

I really don't know. I'm quite a newbie when it comes to kernel programming. 
Maybe there is a way, but my reference for this module was the aes assembler 
code which duplicates everything as well. I assumed there is reason for this. 
Maybe someone with a little more knowledge about the crypto-api / kernel 
could pitch in here.
>
> Also don't make it a separate config - it should just be a replacement
> on x86-64.

There was a patch in 2.6.16:
-------------------------
commit c8a19c91b5b488fed8cce04200a84c6a35c0bf0c
Author: Herbert Xu <herbert@gondor.apana.org.au>
Date:   Sat Nov 5 18:06:26 2005 +1100

    [CRYPTO] Allow AES C/ASM implementations to coexist
    
    As the Crypto API now allows multiple implementations to be registered
    for the same algorithm, we no longer have to play tricks with Kconfig
    to select the right AES implementation.
    
    This patch sets the driver name and priority for all the AES
    implementations and removes the Kconfig conditions on the C implementation
    for AES.
------------------------------

That's why i did it the same way. 

Re: [RFC][PATCH 2/2] Twofish cipher x86_64-asm optimized

[Joachim Fritschi]

On Sunday 07 May 2006 14:33, Herbert Xu wrote:
> On Sun, May 07, 2006 at 12:38:30PM +0200, Andi Kleen wrote:
> > It would be good if you could run some random input encrypt/decrypt tests
> > comparing the C reference version with yours. We have had bad luck
> > with assembler functions not quite implementing the same cipher
> > in the past.
>
> That's a very good point.  The tcrypt module provides both correctness
> tests as well as speed tests for twofish.  Please run it with your
> version versus the existing implementation.

All tcrypt tests pass successfully on both architectures.

Here are the outputs from the tcrypt speedtests:

http://homepages.tu-darmstadt.de/~fritschi/twofish/tcrypt-speed-c-i586.txt
http://homepages.tu-darmstadt.de/~fritschi/twofish/tcrypt-speed-asm-i586.txt
http://homepages.tu-darmstadt.de/~fritschi/twofish/tcrypt-speed-c-x86_64.txt
http://homepages.tu-darmstadt.de/~fritschi/twofish/tcrypt-speed-asm-x86_64.txt

Regards,
Joachim

Re: [RFC][PATCH 2/2] Twofish cipher x86_64-asm optimized

[Joachim Fritschi]

After going over my patch again, i realized i missed the .cra_priority 
and .cra_driver_name setting in the crypto api struct. Here is an updated 
version of my patch:

http://homepages.tu-darmstadt.de/~fritschi/twofish/twofish-x86_64-asm-2.6.17-2.diff

And also a little patch for the generic twofish implementation adding the 
appropriate values :

http://homepages.tu-darmstadt.de/~fritschi/twofish/twofish-priority-fix-2.6.17.diff

Regards,
Joachim