Cryptography-Digest Digest #845, Volume #11 Tue, 23 May 00 19:13:01 EDT
Contents:
Patent busting for AES usage
Re: Asynchronous and simple algorithm ("Martin Winter")
Re: Yet another block cipher: Storin (Mark Wooding)
Re: pentium timings (Jerry Coffin)
Re: Initialization Vector / Message Key with Stream Cipher? (David Hopwood)
Re: Asynchronous and simple algorithm (Gisle S�lensminde)
Re: Graphic Encryption (John Bailey)
Re: Patent busting for AES usage (Mok-Kong Shen)
Re: Yet another block cipher: Storin (Mok-Kong Shen)
Observation of Matsui's Sboxes (tomstd)
Newish SBOXGEN program (tomstd)
Re: Patent busting for AES usage (tomstd)
RE: Yet another block cipher: Storin ("Manuel Pancorbo")
Re: Patent busting for AES usage ("Lyalc")
----------------------------------------------------------------------------
From: <[EMAIL PROTECTED]>
Subject: Patent busting for AES usage
Date: Tue, 23 May 2000 18:04:21 GMT
I would like to start one or more threads with the
goal of creating prior art to spoil patents based on
using the algorithm or algorithms selected as the AES.
[Please, no discussion of the benefits of selecting
one, or more than one, candidate on this thread.] The
submitters have agreed to terms that allow free use of
the selected AES, so I am not worried about that.
[Please no discussion of the Hitachi patents on this
thread.]
What I would like to prevent are things like the MDC-2
and MDC-4 patents that IBM got on a DES mode of
operation that creates a cryptographic digest from DES
or similar block ciphers (see US Patent #4,908,861).
These threads could declare certain ideas as obvious
to a workman versed in the trade, or they could publish
novel ideas, which could no longer be the basis for a
patent.
Here are some ideas that are obvious to me:
1. When using AES in a CBC mode, using the IV to carry
information about the message. For example, the some
or all of the bits of the IV could be a cryptographic
transformation (such as a digest like MD5) of one or
more of the following: plaintext of the message,
sequence number, plaintext header of the message, the
time and/or the date, or a key known to one or more
parties of the communication.
2. Using AES as a drop-in replacement for a block
cipher like DES that works on 8-byte blocks by
performing pre and post processing on the size of the
input and output blocks respectively. For example, a
module that performs DES-OFB mode with 64-bit feedback
and output, could be replaced with a module that used
AES where the 64-bits of output are a selected subset
of the 128-bits of AES output, and the 64-bits of
feedback are the same, or differently selected, set of
64-bits of the AES output. Another example occurs in
counter mode: the 128-bit output could be reduced to a
64-bit output by a simple function such as an
exclusive-or of the left and right halves of the 128-
bit AES output.
------------------------------
From: "Martin Winter" <[EMAIL PROTECTED]>
Subject: Re: Asynchronous and simple algorithm
Date: Tue, 23 May 2000 18:17:57 GMT
Runu, thank you for your followup!
"Runu Knips" <[EMAIL PROTECTED]> wrote:
> Please be more specific. What features does your language actually HAVE
> ???
>
> Select from the list:
>
Well, Lingo is a scripting language built into Macromedia Director. It has
some similarity to JavaScript (but noch much). A few things are possible -
see below:
> [N] Shift + Rotate
> [Y] Multiplication
> [?] Unsigned arithmetics
Hm, I am not sure what you mean. The language can work with longints
and real.
> [N] Bitwise operations
> [Y] Arrays
> [Y] Multi-Dimensional arrays (a bit tricky, but is possible to handle)
> [N] Arithmetics without overflow exceptions
(but I may be able to check for overflow myself)
All in all I can say, that it would be possible to emulate bitwise
operations with string manipulation or integer arithmetics. My _BIG_
advantage is that speed is definately _not_ important. (okay, 5 minutes for
the encryption are too much ;-) )
I just want to encrypt a string of about 200 characters so that only a
different program on the server can decrypt it.
Hope that makes my problem a bit clearer...
Martin
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Yet another block cipher: Storin
Date: 23 May 2000 18:24:29 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
[Three top-bit changes into the matrix yields a single top-bit change in
the output.]
> I don't think that makes much of a difference, to be honest
In fact, if it does the whole scheme is blown out of the water. Anyway,
this has to happen for some combination of the inputs, so it may as well
be three-bits-set ones as anything else.
-- [mdw]
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Tue, 23 May 2000 12:43:53 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> A good measuring code can be downloaded from http://www.agner.org/assem. An
> explanation (a quite good one) is present at his "How to optimize...". Sample
> code is also included (although I dislike it due to its complexity).
Quite true -- Agner has a very nice site there. Phil Carmody has
just put up a chapter-by-chapter browsable version at:
http://fatphil.org/x86/pentopt/
as well, in case anybody's interested. There's also quite a bit of
information along the same lines at www.sandpile.org, though this is
less oriented toward code optimization and more toward x86 internals
in general.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
Date: Tue, 23 May 2000 17:04:32 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Initialization Vector / Message Key with Stream Cipher?
=====BEGIN PGP SIGNED MESSAGE=====
Elros wrote:
>
> Let's say that U is a key supplied by the user, that R is a string of
> "random" characters (different for each encryption), and that M is a
> message to be encrypted. With a stream cipher, is it better to:
>
> 1. Encrypt M with a key of R (giving Me). Encrypt R with a key of U
> (giving Re). Store the ciphertext as Re+Me.
For an additive stream cipher [*], encrypting two messages by this method
will leak the XOR of the corresponding R values, which may allow a
related key attack. If the R values are independent and the cipher is
resistant to related key attacks, that doesn't seem to be sufficient to
break it, but nevertheless I don't think this method is a good idea.
> OR
>
> 2. Encrypt M with a key of U+R (giving Me). Store the ciphertext as R+Me
> (i.e. R is not encrypted in the ciphertext).
This is better IMHO, but still may allow related key attacks. Use this
instead:
3. Encrypt M with a key of H(U, R) (giving Me), where H is a cryptographic
hash function (if the output of H is too long, truncate it). Store the
ciphertext as R+Me.
Also note that if U is a passphrase, then H should be made computationally
intensive in order to slow down dictionary attacks.
[*] An additive stream cipher is one that uses a reversible operator such
as XOR or modulo addition, to combine the output of a keystream
generator with the plaintext.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOSqr5DkCAxeYt5gVAQFg1Af6AyRN89g47QldRXGWWpcn3X/gITbR3Zg5
osunUz1P52B4SwOIdxAGDEJIRMGeQ4Iv907VvqYWjoyhpKnF1FsMA7HgFYwxctXX
831vsJsIut4KRkThQBiDe1dU2NHRGxa1Sw5I+uHDq6hv39Wnk7e7HL+kXcajkcvK
o7xXvvkME1NcQZRTX2s1jAgeIC/0ihpfwfQME24scGITABJ9zxdk2FMpZ/ESWrGG
iSoCwFxO+TCdhCd7vYiEIoCGAil6rOKmZkBSz5YEgyD0ver+Yxr74VxsJqrIA5aK
FBv9NV5vHDHe0EeQDqXcqTKWNvH1neR5xd1nRL39jRFy46KLuTfruA==
=lRQg
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Gisle S�lensminde)
Subject: Re: Asynchronous and simple algorithm
Date: 23 May 2000 21:40:56 +0200
In article <[EMAIL PROTECTED]>, Runu Knips wrote:
>Select from the list:
>
>[ ] Shift + Rotate
>[ ] Multiplication
>[ ] Unsigned arithmetics
>[ ] Bitwise operations (especially XOR and AND)
>[ ] Arrays
>[ ] Multi-Dimensional arrays
>[ ] Arithmetics without overflow exceptions
>
>A language without any of these might still allow some kinds of
>encryption, but it will become really tricky
Well, it is in fact _not_ particulary tricky to make a cryptosystem
without any of these primitives. I hacked up an implementation of
rc4 in Common Lisp not using any of these. The implementation including
lots of comments is less than 100 lines.
(It would have been harder in C though)
;;; On sci.crypt Runu Knips said that without any of the following
;;; primitives, it will be hard to do any encryption. Even this is the
;;; most common operations used for at least symetric ciphers. RSA use
;;; only one of these (multiplication) RC4 can in fact be implemented
;;; without any of these primitives quite easily, which this Common Lisp
;;; implementation demonstrates. Runu gave the following list:
;;;
;;;> [ ] Shift + Rotate
;;;> [ ] Multiplication
;;;> [ ] Unsigned arithmetics
;;;> [ ] Bitwise operations (especially XOR and AND)
;;;> [ ] Arrays
;;;> [ ] Multi-Dimensional arrays
;;;> [ ] Arithmetics without overflow exceptions
;;;>
;;;> A language without any of these might still allow some kinds of
;;;> encryption, but it will become really tricky
(defstruct rc4state
"This struct contains a list instead of an array for the rc4
permutation. This is of cause insane, but since an array was
one of the primitives it was difficult to make a cipher without,
I used a list instead."
(permlist (loop for i from 0 to 255 do collect i))
(x 0)
(y 0))
(defun modulo (op modulus)
"We cannot use the built-in modulo operator, so we implement
an operation for modulo using subtraction instead.
This might overflow the stack with large numbers, but rc4 will
never have numbers > 512."
(if (>= op modulus)
(modulo (- op modulus) modulus)
op))
(defun modulo256 (op) (modulo op 256))
(defun new-key(keystring)
"The key schedule - returns a key struct.
Since we are not allowed to use arrays, we take a list of
chars as input for the key string, since a string can be
considered to be an array of chars."
(let ((the-key (make-rc4state))
(keylength (length keystring))
(counter 0)
(index1 0)
(index2 0)
(tmp 0))
(dotimes (counter 256 the-key)
(setf index2
(modulo256 (+ (char-code (elt keystring index1))
(elt (rc4state-permlist the-key) counter)
index2)))
(setf tmp (elt (rc4state-permlist the-key) counter))
(setf (elt (rc4state-permlist the-key) counter)
(elt (rc4state-permlist the-key) index2))
(setf (elt (rc4state-permlist the-key) index2) tmp)
(setf index1 (modulo (+ index1 1) (length keystring))))))
(defun rc4-stream (the-key number-of-bytes)
"Generates 'number-of-bytes' keystream elements as a list of
numbers 0..255"
(let ((tmp 0))
(loop for i from 0 to number-of-bytes do collect
(progn
(setf (rc4state-x the-key)
(modulo256 (rc4state-x the-key)))
(setf (rc4state-y the-key)
(modulo256 (+ (elt (rc4state-permlist the-key)
(rc4state-x the-key))
(rc4state-y the-key))))
(setf tmp (elt (rc4state-permlist the-key)
(rc4state-x the-key)))
(setf (elt (rc4state-permlist the-key) (rc4state-x the-key))
(elt (rc4state-permlist the-key) (rc4state-y the-key)))
(setf (elt (rc4state-permlist the-key) (rc4state-y the-key)) tmp)
(modulo256 (+ (elt (rc4state-permlist the-key) (rc4state-x the-key))
(elt (rc4state-permlist the-key) (rc4state-y the-key))))))))
;; Usually a stream cipher like rc4 use xor for key mixing, but since
;; xor was one of the operations not allowed here, we use addition modulo
;; 256 instead. Well, even this is not implemented using unsigned/modular
;; arithmetic, but use the modulo function declared earlier in the program.
;; All are represented as integers and characters, which unlike C not is a
;; number modulo 8. This way the disallowed operation is avoided.
(defun rc4-encrypt (the-key plaintext)
"Encrypt a list of characters with rc4 using addition modulo 256"
(loop for i in plaintext collect
(code-char (modulo256 (+ (car (rc4-stream the-key 1))
(char-code i))))))
(defun rc4-decrypt (the-key ciphertext)
"Decrypt a list of characters with rc4 using subtraction modulo 256"
(loop for i in ciphertext collect
(code-char (modulo256
(- (+ (char-code i) 256)
(car (rc4-stream the-key 1)))))))
--
Gisle S�lensminde ( [EMAIL PROTECTED] )
ln -s /dev/null ~/.netscape/cookies
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Subject: Re: Graphic Encryption
Date: Tue, 23 May 2000 20:18:23 GMT
On Tue, 23 May 2000 18:17:14 +0100, "Will Critchlow" <[EMAIL PROTECTED]>
wrote:
>> My encrypted graphic is at:
>> http://www.frontiernet.net/~jmb184/cifrgrfx.gif
>> The key is at:
>> http://www.cl.cam.ac.uk/~fms27/vck/share1.gif
>
>
>Spoiler space
>
>1
>2
(snipped)
>14
>15
>
>Why Halley?
>
Try reading it upside down. My last name is hailey
:-]
Thanks for the feedback which implies that the two images worked.
As an assist to people without graphics editors, I tried a different
approach. http://www.frontiernet.net/~jmb184/demo.html MAY
demonstrate the process. It calls up both images--one as the
background and the second as a graphic image within the page and for
which white is a transparent color. If these two images are properly
aligned, the effect is the same as using a graphics editor. Alignment
is a problem, however. Adjusting the properties hspace and vspace
within the image tag, its possible to find an alignment that works,
but I could only do it by adding reference marks that I later deleted.
So, this may only work easily for users of Netscape whose browser
parameters match mine. Internet Explorer requires a different set of
alignment values which I haven't bothered to find.
John.
John
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Patent busting for AES usage
Date: Tue, 23 May 2000 23:04:31 +0200
[EMAIL PROTECTED] schrieb:
> I would like to start one or more threads with the
> goal of creating prior art to spoil patents based on
> using the algorithm or algorithms selected as the AES.
> [Please, no discussion of the benefits of selecting
> one, or more than one, candidate on this thread.] The
> submitters have agreed to terms that allow free use of
> the selected AES, so I am not worried about that.
> [Please no discussion of the Hitachi patents on this
> thread.]
>
> What I would like to prevent are things like the MDC-2
> and MDC-4 patents that IBM got on a DES mode of
> operation that creates a cryptographic digest from DES
> or similar block ciphers (see US Patent #4,908,861).
Shouldn't one argue that in general such patents shouldn't
be granted? I mean, one could also attack at the policy level,
if one has some good formulation of arguments.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Yet another block cipher: Storin
Date: Tue, 23 May 2000 23:04:41 +0200
Mark Wooding wrote:
> Maybe I'm remembering wrongly, but I thought the Hill cipher used
> multiplication by a secret *key* matrix. The matrix in Storin is
> *fixed* and *public*. You can use a different matrix if you like, but
> then what you've got isn't my cipher: it's a different and incompatible
> one. It's a constant, which provides good diffusion and nonlinearity
> for the rest of a block cipher.
Since Hill used only a matrix multiplication to encrypt and nothing
else, the matrix of course has to be secret. But the essential
contribution of Hill is that a matrix multiplication results in a very
compact way of doing substitutions (compare this with the
polyalphabetic substitution employing tables). On the other hand,
you employ a matrix multiplication inside a cipher. Because of
the presence of the other components, you can afford to have
the matrix constant and public, just like the S-boxes of DES.
Question: Excepting some additional computing cost, is there
anything against using a key-dependent matix in your cipher?
(A question that is also asked by Manuel Pancorbo.)
> If the Hill cipher is the one I think it is, iterating it is pointless
> because matrix multiplication is associative. Storin inserts layers of
> other transformations between the matrix multiplications to break
> everything up and ensure that I'm not wasting my time. The matrix on
> its own is not sufficient for security. The other components are there
> because they're necessary for the cipher to work well.
If you have something nontrivial that intervenes between two matrix
multiplications, you can't in the general case reduce that to one matrix
multiplication. In the other case, of course, a matrix product is
a matrix and one gains nothing. Thus Hill indeed used only one matrix.
(I indicated, though, the advantages of a variant using two matrices in a
recent thread. You might also consider using that variant.)
M. K. Shen
------------------------------
Subject: Observation of Matsui's Sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 23 May 2000 15:39:39 -0700
(This can be fetched from
http://www.tomstdenis.com/matsui-observation.txt)
-=-=-=-=-=-=-=-=-=
On the sub-optimality of Matsui's Sboxes
Tom St Denis
In [1] Matsui presents a method of creating even bit sized
sboxes that are non-linear,
bijective and differentially resilient. Namely the sbox is
formed from taking the
inverse of the arguement modulo a primitive degree n
polynomial. The sboxes formed
also follow the Bit Independance Criterion of order n - 1 as
well. Algebraically the
sboxes are explained as:
S(x) = x^-1 mod p
However the observation comes from two subtleties that make the
sboxes sub-optimal.
The first immediate observation is that
S(0) = 0, S(1) = 1, for all p
Which means no cryptosystem should use this type of sbox in
parrallel, unless the sbox
is keyed. The second observation is less obvious but just as
important. The sboxes
formed from the inverse modulo a primitive polynomial do not
follow the strict avalanche
criterion. In other words, there is less then ideal (>5%) error
in the expected avalanche
of single bit changes in the input.
For example with a 8x8 sbox (p = degree 8 polynomial), the table
below is formed. Where
each column represents an output difference, and each row is a
different input difference.
Each element of the table has been simplified by subtracting 128
from the element. In an
ideal sbox each of the entries should be relatively close to
zero which means each input bit
has a equal probability of effecting an output bit.
-8 12 -12 -8 12 -4 -12 12
4 -12 -4 -4 -4 -12 12 -8
8 -4 -4 0 -12 12 -8 4
12 -4 0 -8 12 -8 4 8
-8 0 -8 -12 -8 4 8 12
-12 -8 8 12 4 8 12 -8
-8 8 -4 -8 8 12 -8 -12
-4 -4 -8 12 12 -8 -12 -8
(Table 1, SAC observation for any polynomial of degree 8)
>From this table several observations are obvious. For example
column 4 (starting from
zero on the left) has three '12' entries. Which means that some
input bits swapped
(namely bits 0, 3 and 7) will effect the fifth output bit with a
higher probability then
random. Several other observations along the same line can be
drawn.
It's ironic that sboxes that are non-linear, have low input-
output xor pairs and follow
BIC fail the SAC test.
Considering the output of the SAC test is a fail, I recommend
not using Matsui's Sboxes.
---
[1] "On a Structure of Block Ciphers with Provable Security
against Differential
and Linear Cryptanalysis", M. Matsui, Trans. Fundamentals
Vol. E82-A, No.1
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Newish SBOXGEN program
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 23 May 2000 15:44:00 -0700
With the help of Adam Durana (hope I got the last name right) I
tweaked my sboxgen program to output sboxes much quicker. I
have easy-out code in all lengthy tests so the least amount of
time possible is wasted in anyone test. The code is a bit
cleaner and easier to follow. It's at
http://www.tomstdenis.com/sboxgen.c
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: Patent busting for AES usage
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 23 May 2000 15:53:20 -0700
In article <FKzW4.195$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
>I would like to start one or more threads with the
>goal of creating prior art to spoil patents based on
>using the algorithm or algorithms selected as the AES.
>[Please, no discussion of the benefits of selecting
>one, or more than one, candidate on this thread.] The
>submitters have agreed to terms that allow free use of
>the selected AES, so I am not worried about that.
>[Please no discussion of the Hitachi patents on this
>thread.]
>
>What I would like to prevent are things like the MDC-2
>and MDC-4 patents that IBM got on a DES mode of
>operation that creates a cryptographic digest from DES
>or similar block ciphers (see US Patent #4,908,861).
>These threads could declare certain ideas as obvious
>to a workman versed in the trade, or they could publish
>novel ideas, which could no longer be the basis for a
>patent.
>
>Here are some ideas that are obvious to me:
>
>1. When using AES in a CBC mode, using the IV to carry
>information about the message. For example, the some
>or all of the bits of the IV could be a cryptographic
>transformation (such as a digest like MD5) of one or
>more of the following: plaintext of the message,
>sequence number, plaintext header of the message, the
>time and/or the date, or a key known to one or more
>parties of the communication.
>
>2. Using AES as a drop-in replacement for a block
>cipher like DES that works on 8-byte blocks by
>performing pre and post processing on the size of the
>input and output blocks respectively. For example, a
>module that performs DES-OFB mode with 64-bit feedback
>and output, could be replaced with a module that used
>AES where the 64-bits of output are a selected subset
>of the 128-bits of AES output, and the 64-bits of
>feedback are the same, or differently selected, set of
>64-bits of the AES output. Another example occurs in
>counter mode: the 128-bit output could be reduced to a
>64-bit output by a simple function such as an
>exclusive-or of the left and right halves of the 128-
>bit AES output.`
>
>
>
>
>
>
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Manuel Pancorbo" <[EMAIL PROTECTED]>
Subject: RE: Yet another block cipher: Storin
Date: Wed, 24 May 2000 00:57:06 +0200
Mark Wooding <[EMAIL PROTECTED]> escribi=F3 en el mensaje de noticias=20
>=20
> Yes. That's another good reason for choosing larger matrices. =
Consider
> a top-bit change in one or more of the input words. Multiplying such =
an
> input word by an even number loses the change, beause it shifts off =
the
> top. Multiplying by an odd number doesn't lose the change. This is
> good.
>=20
> Let's look at the matrix mod 2. Let d_ij be the entry at row i, =
column
> j, mod 2. If we change the top bits of x_n for one or more rows n, =
then
> the top bit of output x'_i changes if and only if
>=20
> ---
> > d_in =3D 1 (mod 2)
> ---
> i
>=20
This is quite the kernel of my algorithm, thus I understand what you =
say; Nevertheless I see this question in a rather different way. Suppose =
'd' is a NxN mod 2 matrix, with its elements 'd_ij' arranged in a =
disordered pseudorandom way (of course Det(d) =3D 1 mod 2). Then, if we =
change a single bit, i-th, in the input vector _it doesn't matter =
whether high or low bit, this is the benefit of mod 2 matrices_ an =
average of N/2 bits will change on the output vector, and these coincide =
with the positions where we find '1'-s in the i-th column of the matrix.
Let me finish my cipher. I'll explain these things in it.
>=20
> > By the way, why don't you make the matrix key dependent?
>=20
> Finding invertible matrices over Z_{2^{24}} with good properties is
> tricky. Inverting them is tricky too. =20
Well, I have a "recipe" for you. Try it, perhaps you find it usefull.
Build a matrix 'G' this way:
2a + 1 =B7 A =B7 B =B7 C
0 =B7 2b + 1 =B7 D =B7 E
0 =B7 0 =B7 2c + 1 =B7 F
0 =B7 0 =B7 0 =B7 2d + 1
where {A, B, C, D, E, F} are 24-bit key-dependent numbers and {a, b, c, =
d} are 23-bit key-dependent numbers; so, you will need 24*6+23*4 =3D 236 =
key bits.
You can find the inverse of G easily this way:
{G^-1}_i,i =3D [G_i,i] ^ -1=20
{G^-1}_i,i+k =3D - Sum(j =3D 1 to k) [G_i,i+j][{G^-1}_i+j,i+k]
1 <=3D k < 4
0 < =3D i <=3D 4 - k
Of course all operations are mod 2^24.
(Note: I'm not quite sure about this expressions in this moment; =
furtherly I will post the correct ones if necessary)
Once you have G and its inverse you must diffuse the key bits along all =
matrix elements; for this purpose build:
M =3D (GZG)^2 (mod 2^24)
{M^-1} =3D ({G^-1}Z{G^-1})^2 (mod 2^24)
where Z is the antidiagonal matrix
0 =B7 0 =B7 0 =B7 1
0 =B7 0 =B7 1 =B7 0
0 =B7 1 =B7 0 =B7 0
1 =B7 0 =B7 0 =B7 0
which have the property Z^2 =3D I
voil=E0! You have your key-dependent matrices. Squaring is made to =
increase diffusion.
> This all takes up code space and
> time, which the DSP doesn't really want to have to do: storin-mktab =
(the
> program which generates the matrix) takes a noticeable amount of time =
to
> run on my PII at home!
>=20
Each matrix occupies 16 words, so 32 words total. You will need 3 or 4 =
temporal matrices, so 64 words of temporal rooming. I can't understand =
why your program takes so much time to compute the matrix.
> -- [mdw]
--=20
_________________________________________________________________
Manuel Pancorbo
[EMAIL PROTECTED]
"...
M=E1s vale aprender una sola l=EDnea de Ciencia
que postrarse cien veces en oraci=F3n. (Cor=E1n)
Pli valoras lerni ech nur unu linion de Scienco
ol preghe genui cent fojojn. (Korano)
..."
_________________________________________________________________
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: Patent busting for AES usage
Date: Wed, 24 May 2000 09:01:06 +1000
Need to be careful with 'ideas'.
Patents cover implementations of 'ideas'- an idea alone generally cannot be
patented.
Now you've described an idea, I could patent an implementation of that
idea - as could anyone else, provided our implementations didn't infringe
anyone elses. (Part of patent writing seems to describe as broad an
implementation as possible).
Once an few ideas are commonpleace, then it is possible to patent
'inventions based on combinations of those ideas - e.g first the XOR, then
the SBox, then "data-dependent" manipulation, then alongs comes an
RC5/6,DES,AES style patent based on specific combinations and arrangements
of the foregoing.
Without a good proposal to go forward, then the concept of 'patent spoiling'
is pointless.
Two options that might work
1. make implementaitons as specific or narrow as possible.
2. do away with the concept of all intellectual property.
I'm not sure what effect either would have on the industry, but it seems
unlikely to be positive to me.
lyal
[EMAIL PROTECTED] wrote in message ...
>I would like to start one or more threads with the
>goal of creating prior art to spoil patents based on
>using the algorithm or algorithms selected as the AES.
>[Please, no discussion of the benefits of selecting
>one, or more than one, candidate on this thread.] The
>submitters have agreed to terms that allow free use of
>the selected AES, so I am not worried about that.
>[Please no discussion of the Hitachi patents on this
>thread.]
>
>What I would like to prevent are things like the MDC-2
>and MDC-4 patents that IBM got on a DES mode of
>operation that creates a cryptographic digest from DES
>or similar block ciphers (see US Patent #4,908,861).
>These threads could declare certain ideas as obvious
>to a workman versed in the trade, or they could publish
>novel ideas, which could no longer be the basis for a
>patent.
>
>Here are some ideas that are obvious to me:
>
>1. When using AES in a CBC mode, using the IV to carry
>information about the message. For example, the some
>or all of the bits of the IV could be a cryptographic
>transformation (such as a digest like MD5) of one or
>more of the following: plaintext of the message,
>sequence number, plaintext header of the message, the
>time and/or the date, or a key known to one or more
>parties of the communication.
>
>2. Using AES as a drop-in replacement for a block
>cipher like DES that works on 8-byte blocks by
>performing pre and post processing on the size of the
>input and output blocks respectively. For example, a
>module that performs DES-OFB mode with 64-bit feedback
>and output, could be replaced with a module that used
>AES where the 64-bits of output are a selected subset
>of the 128-bits of AES output, and the 64-bits of
>feedback are the same, or differently selected, set of
>64-bits of the AES output. Another example occurs in
>counter mode: the 128-bit output could be reduced to a
>64-bit output by a simple function such as an
>exclusive-or of the left and right halves of the 128-
>bit AES output.
>
>
>
>
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
