From: Mok-Kong Shen on

In DES, in which Feistel's technique was first commonly known,
a block is divided to two fields B_1 and B_2 and one of the basic
operations in the algorithm is e.g.:

B_2 = F1(B_1) ^ B_2

where F1 is a key-dependent non-linear function which is
different for different rounds (via the different round keys).

This means that in the general case, where there are, say, three
fields B_1, B_2 and B_3, the 'natural' operations corresponding
to the above will be:

B_2 = F1(B_1) ^ B_2 B_3 = F1(B_1) ^ B_3

Below we'll say that in the above B_1 is the pivot field in the
operation. After the above F2(B_2) will be computed to xor B_1
and B_3, i.e. B_2 will be the pivot field, etc.

There is a tiny possibility of variation of the scheme for a block
having m fields B_i with i in [1,m], namely the sequence of pivot
fields for a block of m fields need not be in the natural order
1, 2, ... m but may be a key-dependent permutation of that and, if
the algorithm has h such permutations being used in succession in
the procesing of a block, these h permutations may be all different.

M. K. Shen

--------------------------------------------------------------

[OT] In an attempt to reduce annoyance to the general readers, I am
unfortunately forced to forgo any opportunities of discussion with
those, who have the unnice impulse (urge, "Drang" in German) to
overload their posts with bandwidth-wasting personal stuffs and/or
bad words, by placing them into my kill-file. Those who dislike my
posts for whatever reasons are requested to kindly put me into their
kill-files as well.




From: unruh on
On 2010-07-22, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote:
>
> In DES, in which Feistel's technique was first commonly known,
> a block is divided to two fields B_1 and B_2 and one of the basic
> operations in the algorithm is e.g.:
>
> B_2 = F1(B_1) ^ B_2
>
> where F1 is a key-dependent non-linear function which is
> different for different rounds (via the different round keys).
>
> This means that in the general case, where there are, say, three

No this does not mean that at all. There is no reason to have say three
fields. It is liable to require more work for worse security.

> fields B_1, B_2 and B_3, the 'natural' operations corresponding
> to the above will be:
>
> B_2 = F1(B_1) ^ B_2 B_3 = F1(B_1) ^ B_3
>
> Below we'll say that in the above B_1 is the pivot field in the
> operation. After the above F2(B_2) will be computed to xor B_1
> and B_3, i.e. B_2 will be the pivot field, etc.
>
> There is a tiny possibility of variation of the scheme for a block
> having m fields B_i with i in [1,m], namely the sequence of pivot
> fields for a block of m fields need not be in the natural order
> 1, 2, ... m but may be a key-dependent permutation of that and, if
> the algorithm has h such permutations being used in succession in
> the procesing of a block, these h permutations may be all different.

Why? Operations in cryptography need to be justified.

Eg, in the limit we do single bit operations. And have a weak cypher.



>
> M. K. Shen
>
> --------------------------------------------------------------
>
> [OT] In an attempt to reduce annoyance to the general readers, I am
> unfortunately forced to forgo any opportunities of discussion with
> those, who have the unnice impulse (urge, "Drang" in German) to
> overload their posts with bandwidth-wasting personal stuffs and/or
> bad words, by placing them into my kill-file. Those who dislike my
> posts for whatever reasons are requested to kindly put me into their
> kill-files as well.
>
>
>
>
From: Greg Rose on
In article <i2aftl$1gi$00$1(a)news.t-online.com>,
Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote:
[usual stuff.]

I guess M-K has never heard of unbalanced feistel
networks, or looked at the design of most hash
functions like SHA-1. As usual.

I do however like his advice to kill-file him.
The trouble being that many newsreaders don't support
killfiles. So I usually just ignore his stuff, but
occasionally (like now) use it as a teachable
moment.

Greg.
--
From: Tom St Denis on
On Jul 22, 8:27 pm, g...(a)nope.ucsd.edu (Greg Rose) wrote:
> In article <i2aftl$1gi$0...(a)news.t-online.com>,
> Mok-Kong Shen  <mok-kong.s...(a)t-online.de> wrote:
> [usual stuff.]
>
> I guess M-K has never heard of unbalanced feistel
> networks, or looked at the design of most hash
> functions like SHA-1. As usual.

There you go again citing sources, I bet you spout all the talking
points from the elites!!!! :-)

> I do however like his advice to kill-file him.
> The trouble being that many newsreaders don't support
> killfiles. So I usually just ignore his stuff, but
> occasionally (like now) use it as a teachable
> moment.

I've been saying that for years, yet all it got me was turmoil.... I
guess said in your Aussie accent it's more charming :-) hehehehe.

Tom
From: Mok-Kong Shen on
Mok-Kong Shen wrote:
>
> In DES, in which Feistel's technique was first commonly known,
> a block is divided to two fields B_1 and B_2 and one of the basic
> operations in the algorithm is e.g.:
>
> B_2 = F1(B_1) ^ B_2
>
> where F1 is a key-dependent non-linear function which is
> different for different rounds (via the different round keys).
>
> This means that in the general case, where there are, say, three
> fields B_1, B_2 and B_3, the 'natural' operations corresponding
> to the above will be:
>
> B_2 = F1(B_1) ^ B_2 B_3 = F1(B_1) ^ B_3
>
> Below we'll say that in the above B_1 is the pivot field in the
> operation. After the above F2(B_2) will be computed to xor B_1
> and B_3, i.e. B_2 will be the pivot field, etc.
>
> There is a tiny possibility of variation of the scheme for a block
> having m fields B_i with i in [1,m], namely the sequence of pivot
> fields for a block of m fields need not be in the natural order
> 1, 2, ... m but may be a key-dependent permutation of that and, if
> the algorithm has h such permutations being used in succession in
> the procesing of a block, these h permutations may be all different.

Since this was meant to be a very tiny "supplement" to the common
description of the Feistel technique and the points made are in fact
fairly simple/commonplace, I omitted to mention a couple of issues
(which I now regret).

(1) The post was stimulated by discussions in a recent thread of Ross
MacGregor of 22.06.2010 entitled "Encrypting odd sized buffers", where
I proposed a scheme to solve his particular problem based on the
Feistel technique, but that is not identical to the above. The name
Ruby and Rackoff was mentioned in that thread by participants in
discussions. So I should have mentioned the term unbalanced Feistel
cipher for completeness in the present context. But see (2) below.

(2) In the common description of the unbalanced Feistel cipher, e.g.
http://en.wikipedia.org/wiki/Feistel_cipher, a pivot field (in my term)
is used to only process one another field. Since however the computation
of Fi(B_i) is certainly much more expensive than xor, it's sort of
waste that way. So I want in the present scheme to have each Fi(B_i)
xor (and thus affect) all the other fields so to achieve a higher
overall computational efficiency.

(3) In the common description of the unbalanced Feister cipher, the
pivot fields are chosen in sequential order. Since having that order
key dependent instead (and also having different permutations of the
order in the processing of a block) essentially complicates analysis
but involves almost no cost, I have introduced that.

(4) A point that I "really" should have mentioned in the original post
is that, if one uses different permutations in succession in the
processing of a block, one should do a check in order to avoid an
undesirable effect. For, if the last pivot field of a permutation
"happens" to be the first pivot field of the following permutation,
then the effect of xoring would be cancelled out (except when one
also uses rotation of bits, see (5), in between the two steps).

(5) In MacGregor's thread Tran Ngoc Duong pointed out a deficiency of
my proposal in which the functions Fi are chosen to be permutation
polynomials mod 2^n. In that case it is desirable to introduce (key
dependent) rotations of bits in words. Rotation of bits is cheap anyway
and evidently helps to enhance the difficulty of the analyst. Thus it
should preferably be done in general.

M. K. Shen