Project Logs

Collapse

• Startup

  Yann Guidon / YGDES • an hour ago • 0 comments

  So far I have chosen the AES SBoxes to initialise the bi-LUT.

  Remember : with the rotation trick the only thing that matters is to initialise the LUT with an equal amount of 0s and 1s. The AES SBox seemed like a quick way to get you there cheaply, you can immediately pump data through it.

  Note : this is also a great way to make a biased generator (if the bias is not too strong), just initialise the required number of 0s and 1s in the LUT for the required ratio.

  Now what's the "expensive way", the "worst case" ? Initialise the LUT with one half 0xFFFF and the other 0x0000. And no entropy at all in the inputs : keep them at 0. And FG=0 too. This forces the system to bootstraps into PRNG mode the hardest way... It was not easy and several shortcomings have been found.

  • First, one of the inputs now gets XORed by a constant, though it could be a bit better than that.
  • Second, the rotation is now extracted from a independent 5-bit LFSR (thus giving values from 1 to 31, excluding the 0 speeds mixing up).

  I was not happy to add more internal bits, and even less happy to add a counter : this is the sign that "something wrong" happens and needs to be broken up. Well, in this case, it is... But then what is the minimum number of bits ?

  First test estimate 10K iterations but it's hard to be sure, when can the LUT be considered "OK" ?

  Have a look at scrambler_startup.tgz

  (note: I use Braille Unicode to represent 8 bits in one glyph, displays OK with chrome)
  

  The test starts at

  LUT:
  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  

  Can it be worse ?

  The trick is to start it up. Hence the 0xAA as a XOR in one input, though it would be better fed from a LFSR8 (which also feeds the rotation). But...

  Read more »

• First log, second stage.

  Yann Guidon / YGDES • 16 hours ago • 0 comments

  I just started the project and I'm already questioning a few early design choices.

  The first stage mixes D with F & G to provide the two addresses, and R is a direct result of the table lookup. There is not much to be done there, and the input entropy is meant to be already "minimal".

  The second stage does the dual update (regardless of A and B being identical). That's what I feel needs an enhancement.

  • First, the source of the twiddling is F and G, which is a dubious choice because it's also used for mixing in the first stage. I would have preferred another source but it's the best I have so far, and using E and H would leak information. I don't want a counter because it could leave a linear trace at the output, in some way, and it's one weakness of RC4.
  • Then the compaction function is just a XOR of 2×5 bits, it's not bad but not the best. A different reduction function would be required. I have considered PopCount but it has a pretty strong bias toward 16, it would be more predictable.
  • And the barrel shifter (that performs the rotation) is one easy simple operation but it takes quite some area (5×32 MUX2). It's not the fastest but I don't know yet a better method to shuffle bits. The number of set bits MUST remain equal to prevent bias at the output, so multiplies or division (integer or Galois) are not possible either.

  I have thought of extending the width of the LUT but 32 bits would only make the problem worse and the source of S=E^H would not be solved.

  For now, it works "well enough" to complement the basic rand(), since the LUT adds a pretty strong non-linearity to the output so it masks short-term correlations and greatly extends the period.
  

View all 2 project logs