I considered the following construct as the 64-bit F-function for a
128-bit Feistel cipher (since it isn't necessarily reversible):

Split 64-bit input into A and B
for(i=0; i<4; i++) {
A *= B;

A += subkey[i];
A = G(A);
Swap A, B
}
Recombine A and B into 64-bit output

Let G() be a nonlinear function, e.g. substitute each of the 4 bytes
in an 8x8 S-box.
Let subkey[] be an array of 32-bit subkeys.

I thought that the advantages of multiplication over rotation would be
- Much higher diffusion

- Closer to decorrelation than rotations

And the advantages of data-dependent multiplication over just
key-dependent multiplication on a half of the block:
- Provides diffusion without needing an XOR between the halves of the
block

My question is, would it provide sufficient decorrelation to prevent
differential and linear cryptanalysis, supposing this F-function were
used in a Feistel cipher with, say, 8 rounds?

I considered the following construct as the 64-bit F-function for a
128-bit Feistel cipher (since it isn't necessarily reversible):

Split 64-bit input into A and B
for(i=0; i<4; i++) {
A *= B;

A += subkey[i];
A = G(A);
Swap A, B
}
Recombine A and B into 64-bit output

Let G() be a nonlinear function, e.g. substitute each of the 4 bytes
in an 8x8 S-box.
Let subkey[] be an array of 32-bit subkeys.

I thought that the advantages of multiplication over rotation would be
- Much higher diffusion

- Closer to decorrelation than rotations

And the advantages of data-dependent multiplication over just
key-dependent multiplication on a half of the block:
- Provides diffusion without needing an XOR between the halves of the
block

My question is, would it provide sufficient decorrelation to prevent
differential and linear cryptanalysis, supposing this F-function were
used in a Feistel cipher with, say, 8 rounds?

[snip]
My question is, would it provide sufficient decorrelation to prevent
differential and linear cryptanalysis, supposing this F-function were
used in a Feistel cipher with, say, 8 rounds?

[snip]
My question is, would it provide sufficient decorrelation to prevent
differential and linear cryptanalysis, supposing this F-function were
used in a Feistel cipher with, say, 8 rounds?

I considered the following construct as the 64-bit F-function for a
128-bit Feistel cipher (since it isn't necessarily reversible):

Split 64-bit input into A and B
for(i=0; i<4; i++) {
A *= B;
A += subkey[i];
A = G(A);
Swap A, B
}
Recombine A and B into 64-bit output

I considered the following construct as the 64-bit F-function for a
128-bit Feistel cipher (since it isn't necessarily reversible):

Split 64-bit input into A and B
for(i=0; i<4; i++) {
A *= B;
A += subkey[i];
A = G(A);
Swap A, B
}
Recombine A and B into 64-bit output

In article <7eeb3109.0401010519.12e706a7@posting.google.com>,
Benjamin Choi <nospam@technosoft21.com> wrote:
I considered the following construct as the 64-bit F-function for a
128-bit Feistel cipher (since it isn't necessarily reversible):

Split 64-bit input into A and B
for(i=0; i<4; i++) {
A *= B;
A += subkey[i];
A = G(A);
Swap A, B
}
Recombine A and B into 64-bit output

Without putting a lot of thought into it, I have
a feeling this will be a sucker for differential
cryptanalysis. Consider what happens when the B
half is zero; you destroy all information in the A
half. Now if the B half is 0x80000000, you get
left with just one bit of A. If the G()
transformation is known, this might be
manipulable.

Anyway, the fact that multiplication loses
information worries me a lot. RC6 and MARS went to
a lot of trouble to ensure that the
multiplications were always safe, but you haven't
done that.

Greg.

In article <7eeb3109.0401010519.12e706a7@posting.google.com>,
Benjamin Choi <nospam@technosoft21.com> wrote:
I considered the following construct as the 64-bit F-function for a
128-bit Feistel cipher (since it isn't necessarily reversible):

Split 64-bit input into A and B
for(i=0; i<4; i++) {
A *= B;
A += subkey[i];
A = G(A);
Swap A, B
}
Recombine A and B into 64-bit output

Without putting a lot of thought into it, I have
a feeling this will be a sucker for differential
cryptanalysis. Consider what happens when the B
half is zero; you destroy all information in the A
half. Now if the B half is 0x80000000, you get
left with just one bit of A. If the G()
transformation is known, this might be
manipulable.

Anyway, the fact that multiplication loses
information worries me a lot. RC6 and MARS went to
a lot of trouble to ensure that the
multiplications were always safe, but you haven't
done that.

Greg.

I agree with Greg. The problem is even at the byte-level: if the least
significant byte of B is 0, then the least significant byte of A after
the multiply is 0 as well, meaning that the least significant byte of the
subkey gets sent directly into the S-box.
What if the multiplications were made bijective, as in IDEA?

Same problem if the least
significant byte of A is 0. Even at the bit-level, there seems to be
potential problems: with probability 3/4, the least significant bit of
A or B is zero, implying that 3/4ths of the time, the least significant
bit going into the S-box is going to be the subkey. This must be leaking
subkey bits.
Indeed I didn't realise that.

I dont know your complete design yet, but I am very skeptical that it can be
secure.
Don't worry, I don't have a complete design. It was just a concept

For an example of a cipher that used multiplication poorly,
see "Cryptanalysis of multi-swap" by Borisov, Chew, Johnson, and Wagner:
http://www.cs.berkeley.edu/~rtjohnso/multiswap/
Multi-Swap seems very linear in nature (the swaps can be considered

I agree with Greg. The problem is even at the byte-level: if the least
significant byte of B is 0, then the least significant byte of A after
the multiply is 0 as well, meaning that the least significant byte of the
subkey gets sent directly into the S-box.
What if the multiplications were made bijective, as in IDEA?

Same problem if the least
significant byte of A is 0. Even at the bit-level, there seems to be
potential problems: with probability 3/4, the least significant bit of
A or B is zero, implying that 3/4ths of the time, the least significant
bit going into the S-box is going to be the subkey. This must be leaking
subkey bits.
Indeed I didn't realise that.

I dont know your complete design yet, but I am very skeptical that it can be
secure.
Don't worry, I don't have a complete design. It was just a concept

For an example of a cipher that used multiplication poorly,
see "Cryptanalysis of multi-swap" by Borisov, Chew, Johnson, and Wagner:
http://www.cs.berkeley.edu/~rtjohnso/multiswap/
Multi-Swap seems very linear in nature (the swaps can be considered

contini@matmail.com (Scott Contini) wrote in message news:<6f35025c.0401012053.48595a3e@posting.google.com>...
snip

I agree with Greg. The problem is even at the byte-level: if the least
significant byte of B is 0, then the least significant byte of A after
the multiply is 0 as well, meaning that the least significant byte of the
subkey gets sent directly into the S-box.
What if the multiplications were made bijective, as in IDEA?