1. Z = 0
2. for i from 1 to m do
2.1 C[i] = Ek(P[i] xor F2(i))
2.2 Z = Z xor F2(P[i] xor C[i])
3. Z = F1(Z xor F2(m + 1))
4. Return C[1..m], Z

And timed just step 2.1/2.2 [since they form the crux of the
system]. Using
full RC6 as F1 and three rounds of RC6 as F2 I got a timing of about
28
cycles per byte [all in C on my Athlon]. RC6 itself takes 20
cycles/byte in
C [timed from LTC]. So really this mode has a trivial amount of
overhead.

I'd like to submit the paper to Crypto'04 which means I only have a
month to write the paper.

Also a general thought on the scheme - if step 3 is executed only
once-a-message - you might want to try to compromise a small percent
of speed for better clarity and simply use a full version of a block
cipher as F1, even if it was not necessary for the security of the
scheme.

Tom St Denis wrote:
1. Z = 0
2. for i from 1 to m do
2.1 C[i] = Ek(P[i] xor F2(i))
2.2 Z = Z xor F2(P[i] xor C[i])
3. Z = F1(Z xor F2(m + 1))
4. Return C[1..m], Z

And timed just step 2.1/2.2 [since they form the crux of the
system]. Using
full RC6 as F1 and three rounds of RC6 as F2 I got a timing of about
28
cycles per byte [all in C on my Athlon]. RC6 itself takes 20
cycles/byte in
C [timed from LTC]. So really this mode has a trivial amount of
overhead.
(...)
I'd like to submit the paper to Crypto'04 which means I only have a
month to write the paper.

When thinking of submitting, you might want to think of picking
another fast cipher for F1 and F2 - RC6 has a patent issue, is that
right? I don't know exactly what consequences are risked but maybe it
would be safer to use an intellectal-rights-free algorithm?

I took the mode I discussed earlier... that is

1. Z = 0
2. for i from 1 to m do
2.1 C[i] = Ek(P[i] xor F2(i))
2.2 Z = Z xor F2(P[i] xor C[i])
3. Z = F1(Z xor F2(m + 1))
4. Return C[1..m], Z

Tom St Denis wrote:

I took the mode I discussed earlier... that is

1. Z = 0
2. for i from 1 to m do
2.1 C[i] = Ek(P[i] xor F2(i))
2.2 Z = Z xor F2(P[i] xor C[i])
3. Z = F1(Z xor F2(m + 1))
4. Return C[1..m], Z

I like to know what is the intention underlying step 3?
(Wouldn't 2.2 alone lead to a useful final value of Z?)

"Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote:


Tom St Denis wrote:

I took the mode I discussed earlier... that is

1. Z = 0
2. for i from 1 to m do
2.1 C[i] = Ek(P[i] xor F2(i))
2.2 Z = Z xor F2(P[i] xor C[i])
3. Z = F1(Z xor F2(m + 1))
4. Return C[1..m], Z

I like to know what is the intention underlying step 3?
(Wouldn't 2.2 alone lead to a useful final value of Z?)

The idea is to prevent messages of different lengths that collide [sorta
like MD-strengthening].

Sorry that my poor knowledge doesn't yet permit me to
understand what you meant. Could you elaborate a little
bit? Since 2.2 already employs encryption, I suppose
that could be good enough. If you employ just a non-linear
function (cf. the Latin square thread) to mix into Z the
entities P[i] and C[i], i.e. without protection by
encryption, then one would of course need at the final
stage an encryption of Z. (I think that such a scheme
could well function.)

"Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote:

Sorry that my poor knowledge doesn't yet permit me to
understand what you meant. Could you elaborate a little
bit? Since 2.2 already employs encryption, I suppose
that could be good enough. If you employ just a non-linear
function (cf. the Latin square thread) to mix into Z the
entities P[i] and C[i], i.e. without protection by
encryption, then one would of course need at the final
stage an encryption of Z. (I think that such a scheme
could well function.)

The point of mixing the length is that while two different P' and P may
collide in the xorsum their different lengths will yield a different value.

This doesn't prevent collisions [obviously since it's a many to one
function] but it does make them harder to find.

Z=Ek(IV);
for i=1 to m+1 do
{ C[i]=Ek(P[i] xor Z);
Z=u(Z,P[i]); Z=u(Z,C[i]);
}
send IV,C[1..m+1];

This requires some algebraic latin square, re: slow. ...
[snip]

Tom St Denis wrote:


This requires some algebraic latin square, re: slow. ...
[snip]

Sorry, I don't yet capture this. The operation is
2*x*y+x+y mod 2^n (n = no. of bits in word) plus some
rotations. Could it be slower than the functions that
you use?

"Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote:


Tom St Denis wrote:


This requires some algebraic latin square, re: slow. ...
[snip]

Sorry, I don't yet capture this. The operation is
2*x*y+x+y mod 2^n (n = no. of bits in word) plus some
rotations. Could it be slower than the functions that
you use?

It has to be the size of the block, that is, n = 128 otherwise the scheme is
useless.

Why is that? Why couldn't the 4 words in an 128-bit
block be operated on separately? Analogy, S-boxes are
normally even smaller, e.g. 8 bits only.)

"Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote:

Why is that? Why couldn't the 4 words in an 128-bit
block be operated on separately? Analogy, S-boxes are
normally even smaller, e.g. 8 bits only.)

First off, the entire block has to be pair-wise decorrelated or you cannot
reduce the security to F1. That is anything you can learn about the
plaintext without inverting F1 shows the design cannot be reduced to F1 in
terms of security.