Main Page | Report this Page
 
Loading..
   
Science Forum Index  »  Cryptography Forum  »  Yet another cipher design
Page 1 of 1    
Author Message
Tom St Denis
Posted: Sun Jan 04, 2004 10:24 pm
Guest
First the specs

128-bit block size, upto 256-bit key
286 cycles/block on Athlon, 400 cycles/block on P4 [same binary]
324 cycles/key [regardless of size] on Athlon, 520 cycles/key on P4

The source for the above test was all C [http://iahu.ca:8080/tc27-alg.c].

The design is rather simple. You take an 8x8 FFT [radix-2] with a single
8x8 sbox. That's the F function. The trick comes from the implementation.
The 8x8 FFT is [in this case]

08 04 04 02 04 02 02 01
04 04 02 02 02 02 01 01
04 02 04 02 02 01 02 01
02 02 02 02 01 01 01 01
04 02 02 01 04 02 02 01
02 02 01 01 02 02 01 01
02 01 02 01 02 01 02 01
01 01 01 01 01 01 01 01

Which only has two unique 4x4s [like a circulant MDS]. Except in this case
the last 4 inputs are sent through the same transform twice. So the optimal
implementation only has twelve lookups instead of 16.

The 8x8 sbox is actually composed of two 4x4s and a 2x2 MDS [three rounds]
so it's hardware friendly as well. The FFT itself can be composed as three
layers of a simple transform [the 2x2 mixer is just [[2 1] [1 1]]].

I haven't performed much cryptanalysis but I doubt DC/LC would be likely to
succeed. The 8x8 FFT has a branch of six and the sbox has a NL of 98 and a
DP of 8/256 [and an algebraic degree of seven]. So while I doubt a trivial
proof of security exists I'm certain the upper bound on a DC/LC attack is
very low [lower than 2^-100].

So far I've tried my hand at an ASM with MMX routine but it's slower [307
cycles/block] than my GCC optimized C code...

I plan to write a paper on this design provided I [or someone else] doesn't
break it in the interim.

Tom
Back to top
Spodumene
Posted: Mon Jan 05, 2004 7:44 am
Guest
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Tom St Denis wrote:
| First the specs
|
| 128-bit block size, upto 256-bit key
| 286 cycles/block on Athlon, 400 cycles/block on P4 [same binary]
| 324 cycles/key [regardless of size] on Athlon, 520 cycles/key on P4
|
| The source for the above test was all C [http://iahu.ca:8080/tc27-alg.c].
|
| The design is rather simple. You take an 8x8 FFT [radix-2] with a single
| 8x8 sbox. That's the F function. The trick comes from the
implementation.
| The 8x8 FFT is [in this case]
|
| 08 04 04 02 04 02 02 01
| 04 04 02 02 02 02 01 01
| 04 02 04 02 02 01 02 01
| 02 02 02 02 01 01 01 01
| 04 02 02 01 04 02 02 01
| 02 02 01 01 02 02 01 01
| 02 01 02 01 02 01 02 01
| 01 01 01 01 01 01 01 01
|
| Which only has two unique 4x4s [like a circulant MDS]. Except in this
case
| the last 4 inputs are sent through the same transform twice. So the
optimal
| implementation only has twelve lookups instead of 16.
|
| The 8x8 sbox is actually composed of two 4x4s and a 2x2 MDS [three rounds]
| so it's hardware friendly as well. The FFT itself can be composed as
three
| layers of a simple transform [the 2x2 mixer is just [[2 1] [1 1]]].
|
| I haven't performed much cryptanalysis but I doubt DC/LC would be
likely to
| succeed. The 8x8 FFT has a branch of six and the sbox has a NL of 98
and a
| DP of 8/256 [and an algebraic degree of seven]. So while I doubt a
trivial
| proof of security exists I'm certain the upper bound on a DC/LC attack is
| very low [lower than 2^-100].
|
| So far I've tried my hand at an ASM with MMX routine but it's slower [307
| cycles/block] than my GCC optimized C code...
|
| I plan to write a paper on this design provided I [or someone else]
doesn't
| break it in the interim.
|
| Tom
|
|
Please, Tom --- into the sci.crypt sandbox with this rather than here.
Bandwidth here is much too valuable for such things. I suggest you read
some books on cryptography before polluting this newsgroup again with
such offal.

Your Friend, Spodumene Smith

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3-nr1 (Windows XP)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQEVAwUBP/lcPpu4igFmGFo1AQIkswf/dy2AXqc7wNSvHhcc2R9ocNZ0/4h2ti5+
YfHlR9PigReTLIebt/9lgk8feeO5t9qI/0tC0iAj+ia91bjrMNJMCT/loujyaXfJ
HDRiz4ucOeNm7/rTIz1jwxLBTa/mk8qjBKHaChhlemNQ0KGlylCe2eyXPUtuSJsv
7KAS3EYey26rbjJqnJ+YFsU4b0bxYkFRQIGA8Ubeod4xVfa/TofpsQr9cPcpxPg9
k2FLZgfcPOgSoF1H21AoT93hsQ/BC19KGI22hz+x6KWHtj1w3z/AJddBXUXEk5uf
wBqqFtBfGjEiUfQMFAJRY5ufefQFHo5ekeg8xuNBE5IakhD++wEu/w==
=Y1uV
-----END PGP SIGNATURE-----
Back to top
Sebastian Gesemann
Posted: Mon Jan 05, 2004 1:20 pm
Guest
On Mon, 5 Jan 2004, Tom St Denis wrote:

Quote:
First the specs

128-bit block size, upto 256-bit key
286 cycles/block on Athlon, 400 cycles/block on P4 [same binary]
324 cycles/key [regardless of size] on Athlon, 520 cycles/key on P4

The source for the above test was all C [http://iahu.ca:8080/tc27-alg.c].

The design is rather simple. You take an 8x8 FFT [radix-2] with a single
8x8 sbox. That's the F function. The trick comes from the implementation.
The 8x8 FFT is [in this case]

08 04 04 02 04 02 02 01
04 04 02 02 02 02 01 01
04 02 04 02 02 01 02 01
02 02 02 02 01 01 01 01
04 02 02 01 04 02 02 01
02 02 01 01 02 02 01 01
02 01 02 01 02 01 02 01
01 01 01 01 01 01 01 01

Which only has two unique 4x4s [like a circulant MDS]. Except in this case
the last 4 inputs are sent through the same transform twice. So the optimal
implementation only has twelve lookups instead of 16.

Interesting...
I already wondered if a Fourier Transform can be used as a *fast*
diffusion layer. (You all probably know that the actual FFT algo
takes O(n*log(n)) operation instead of O(n^2) because its matrix
can be factored in log(n) matrices with many zeros. But I guess
this doesn't work in finite fields generally.

(Does anyone have good references on discrete fourier transforms
in finite fields ?)

Quote:
The 8x8 sbox is actually composed of two 4x4s and a 2x2 MDS [three rounds]
so it's hardware friendly as well. The FFT itself can be composed as three
layers of a simple transform [the 2x2 mixer is just [[2 1] [1 1]]].

Are you aware of the S-Box construction of the Khazad block cipher ?
Your design sounds alike except that you use a MDS transform instead
of a permutation. See:
http://planeta.terra.com.br/informatica/paulobarreto/KhazadPage.html

I havn't seen your implementation yet, but I guess the hardware version
of Khazad's S-BOX is faster than yours because it doesn't involve a
matrix multiplication.

BTW1: You said "F-function". So I guess it's a Feistel block cipher.
How many rounds does it use ?

BTW2: I studied some CryptoNessi block cipher proposals and must
admit that I was a bit disappointed when I found out that the
so-called legacy block cipher Khazad is about half as fast as AES.
It uses an 8x8 MDS matrix as linear mixing layer as well as you do
in your F function. I think that's one of the reasons why it's so
slow compared to AES or Anubis. (At least in software is)

Quote:
[...]

What about the key schedule ?
A paper would be cool. I don't like reading other ppl's
C code ;)


Quote:
Tom

Ghis!
Sebastian
Back to top
Tom St Denis
Posted: Mon Jan 05, 2004 1:29 pm
Guest
"Sebastian Gesemann" <isnt@valid.net> wrote in message
news:Pine.LNX.4.58.0401051818260.10260@helena...

Quote:
Interesting...
I already wondered if a Fourier Transform can be used as a *fast*
diffusion layer. (You all probably know that the actual FFT algo
takes O(n*log(n)) operation instead of O(n^2) because its matrix
can be factored in log(n) matrices with many zeros. But I guess
this doesn't work in finite fields generally.

Well stricly it isn't an FFT. The name "FFT like" comes from the way you
implement the transform (e.g. 2x2 transforms applied to N/2 pairs in log2(N)
steps).

The design has been used in the CS-Cipher (by Vaudenay et al.) and I did
some unpublished research on it (branch of an 8x8 is 6 for instance).

Quote:
The 8x8 sbox is actually composed of two 4x4s and a 2x2 MDS [three
rounds]
so it's hardware friendly as well. The FFT itself can be composed as
three
layers of a simple transform [the 2x2 mixer is just [[2 1] [1 1]]].

Are you aware of the S-Box construction of the Khazad block cipher ?
Your design sounds alike except that you use a MDS transform instead
of a permutation. See:
http://planeta.terra.com.br/informatica/paulobarreto/KhazadPage.html

I havn't seen your implementation yet, but I guess the hardware version
of Khazad's S-BOX is faster than yours because it doesn't involve a
matrix multiplication.

The matrix in my 2x2 for the sbox is just [[2 1][1 1]] which requires less
than 15 (2,1)-XOR gates. It's trivial to implement.

Quote:
BTW1: You said "F-function". So I guess it's a Feistel block cipher.
How many rounds does it use ?

I use ten rounds. I don't have a proof of security. Ten just felt like a
nice number. As I said earlier I suspect it will resist DC/LC or at the
least have a prop ratio of less than 2^{-100}. Which is good enough for all
practical purposes.

Quote:
BTW2: I studied some CryptoNessi block cipher proposals and must
admit that I was a bit disappointed when I found out that the
so-called legacy block cipher Khazad is about half as fast as AES.
It uses an 8x8 MDS matrix as linear mixing layer as well as you do
in your F function. I think that's one of the reasons why it's so
slow compared to AES or Anubis. (At least in software is)

[...]

What about the key schedule ?
A paper would be cool. I don't like reading other ppl's
C code Wink

tc27_setup() is the key schedule. It takes a key from 0..32 bytes in length
and schedules it into 24 32-bit round keys.

I plan to write a paper shortly [e.g. starting it today]. I just want to
post it here and see if there are any hugely obvious attacks. So far I
haven't figured out anything obviously wrong with the design. A correctly
bounded prop-ratio will be nice to have...

Tom
Back to top
 
Page 1 of 1       All times are GMT - 5 Hours
The time now is Wed Oct 08, 2008 3:49 am
Science Forum Index

Powered by phpBB & ML | Disclaimer



Contact Us