Re: XORShift PRNG as a diffusion structure

From: Tom St Denis (tomstdenis_at_yahoo.com)
Date: 03/23/04 

Date: 22 Mar 2004 16:04:58 -0800

Mok-Kong Shen <mok-kong.shen@t-online.de> wrote in message news:<c3n3r6$ln3$01$1@news.t-online.com>...
> Tom St Denis wrote:
> > Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>
> >>I believe there is a misunderstanding between us. What I
> >>meant is: If one has, say, somewhere in a block encryption
> >>algorithm a statement x^=(x << c), then knowing c and the
> >>new x doesn't permit one to recover the old x. This is
> >>clear in the special case where c=0 (the new x is then
> >>always identical to 0).
> >
> >
> > Actually quite the opposite. Provided c is not congruent to zero the
> > statement is fully bijective. The only time it is not is when c == 0
> > which is not a case that proves the rule.
> >
> > Consider the case of say c == 1 that's
> >
> > x ^= x << 1;
> >
> > To undo this you simply xor the LSB against the 2nd bit, then the 2nd
> > against the 3rd, then the 3rd against the fourth, etc...
>
> O.k. So you have to exclude that case in your codes and
> to stepwise recover x.

I don't know what this means. All values of "c" will lead to a
"step-wise" recovery of x.

> On the other hand, is that sort of
> device that fine for achieving diffusion as compared to
> employing S-boxes and linear transformation as e.g. done
> in AES anyways? Thanks.

They're sub-optimal in most respects. For example, in a 16-byte block
cipher the CSQUARE transform [which is very hardware efficient]
achieves 48 active 8x8 sboxes per four rounds. If you configure that
as a 4x32 bitsliced cipher the best 32x32 high weight transform [made
from four consecutive shifts/xors operations] has a branch of seven.
Over four rounds that is 14 active 4x4 sboxes.

so even though the bitsliced approach would be more efficient per
round the fact that you need more rounds [and achieve a slower rate of
confusion] makes the approach less desireable.

Tom

Relevant Pages

  • Re: 20:1 lossless RGB image compression
    ... > Tom St Denis wrote: ... In fact a trivial transform like the 2D ... Has quite a bit of compaction. ... Will that get you 20:1 for all images? ...
    (comp.compression)
  • Re: Unbreakable Encryption - Scenarios - What encryption method would be best?
    ... > Tom St Denis wrote: ... IIRC 7 rounds are enough for CPA and 10 rounds for ... ram] for 10 rounds. ... Make a 16-bit Feistel [which would only require 2.5KB ...
    (sci.crypt)
  • Re: "Alien" cryptanalysis: Gwyn a "two-bit troll"?
    ... >>Tom, you're burning all sorts of bridges both ahead of and behind you ... >way Tom hasn't properly cleaned the toilets using the toilet brush: ... and I've made 16 rounds. ... You know Clem your OK I couldn't have stated it better myself. ...
    (sci.crypt)
  • Re: Formulae for Latin squares of size 2^n
    ... > Tom St Denis wrote: ... > Now, if finding MDS is at high cost, one could consider ... A cipher with a huge transform would be wickedly slow. ...
    (sci.crypt)
  • Re: I misread the question
    ... > Tom St Denis wrote: ... 17 rounds *IS NOT* 20 rounds. ... should be RC6 since no attack on all rounds exists [or existed, ... > then having that assurance may be worth something, ...
    (sci.crypt)