More scrambling

A project log for PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

yann-guidon-ygdesYann Guidon / YGDES 03/30/2023 at 00:180 Comments

How to make a PEAC sequence more "random-looking", or more scrambled ?

There seems to be an easy way : introduce a rotation operator in the feedback. Rotation is a simple bijection using quite few resources. Unfortunately, most high-level language don't define rotation so it must be emulated with a series of mask&shifts&OR, then re-optimised by the compiler. C'm'on.

But since it is a bijection, the rotation ensures that the sequence is twisted but not otherwise altered, only reordered.

The amount of reordering is limited because for a N-bit wide PEAC generator, there are only N possible rotations. But it is worth analysing the various results.

PEAC-Rx is possible only for the binary PEAC generators, the generalised PEAC can't do rotations.

Generalised PEAC have better scrambling characteristics but rotated binary PEAC might provide a good alternative, so it's suitable for hash tables for example.

Rotated PEAC is way easier to implement in HW than gPEAC because it's only a matter of swapping wires. In fact, ANY permutation of the bits is possible ! Further, the permutation can be performed by a collection of S-tables (S-boxes) borrowed from a crypto algo.

It remains to be seen if the rotation actually improves fault detection in the checksum configuration.

I'm not sure that variable rotation amounts are a good idea : at least the amount must not come from the data stream itself but from another generator (probably a smaller PEAC or LFSR). This increases the state size and the length of the orbit.

Now it's approaching crypto-style scramblers...



OK I did try a few things and it's not a silver bullet but the results are pretty interesting.

above is the result of this code,

There are many sensitive parameters and many combinations don't work.

TODO : try with XOR or ADD instead of ROT ?

  var S = X + Y;
  var C=0;

  if (S >= 16) {
    S -= 16;

//  Y = X+C;   => the normal way
// The altered way:
  Y = C+ ( mask & ((X<<rot) | (X>>>(bits-rot) )));

  rot = 3 & (rot-1);   // Dumb but enough depending on initial states

  X = S;

Play with the code ! 

Oh and by the way, the results are very different if you play with where the carry is reinjected.

  C = 0;
  if (S >= 16) {
    S -= 16;
  Y = X+C;
  X = S;

if very different from

  if (S >= 16) {
    S -= 15;
  Y = X;
  X = S;

because in the last case, both X and Y will have the off-by-one value and the algorithm explodes.

That's pretty significant for the gPEAC/non-binary.