I’m trying to put together a new SFC variant (SFC56, for direct implementation in Python) and I’m not exactly sure if there’s evidence for how that was done out there. My guess is it was done by some sort of empirical testing approach, so I’m wondering what a good one would be. I’m leaning toward avalanche testing but I’m not quite sure how to do that.

As for why I want to do SFC56 in particular, it has a few useful properties in my opinion: 56 bit integers are small enough that they will usually trigger Python’s small integer optimization on 64 bit platforms, but large enough that there are enough bits for any double.

Has anyone here managed to get TestU01 working?

Can anyone help with TestU01?

My RNG produces 32bit integers natively. So I ran the "Crush" series of tests and it passes .

However, I tried running the "Crush" tests with real/float numbers, by converting the 32bit integers to real/float with the following code:

R = (I / 4294967296.0);

But many of the "Crush" tests fail:

       Test                          p-value
 ----------------------------------------------
  8  MatrixRank                       eps
  9  HammingIndep                     eps
 10  RandomWalk1 H                    eps
 10  RandomWalk1 M                    eps
 10  RandomWalk1 J                    eps
 10  RandomWalk1 R                    eps
 10  RandomWalk1 C                    eps
 ----------------------------------------------

OR

R = ((double) I) / 4294967296.0;

In which case I get a "segmentation fault" error.

I'm a little surprised that my RNG integer output will pass the "BigCrush" test, but the exact same numbers converted to real/float cannot pass the "SmallCrush" tests.

Just in case you are wondering, I have read the TestU01 manual. However, C is not my preferred language, so my integer to float conversion might be faulty.

I'm happy to post my code if anyone wishes...

Right now, I'm still designing things in my head and this information is for everyone, not just me. I'm still considering mainly just 74xx ICs. One of the more obvious designs has some obvious flaws.

Suppose you start with a couple of ring oscillators, XOR them, and then clock that into a shift register. The problem is that the output will be predictable before the jitter becomes significant and before beating occurs. It might be good enough later, but not at first.

I asked the AI bot for ideas. One is to create an LFSR with an XNOR gate and a shift register. But instead of leaving it like that, add a couple of ring oscillators and multiplexers to move the tap points. So this adds a little more randomness due to the RO jitter.

Another suggestion to get a noisier clock signal would be to create a way to jump over an even number of inverters in a ring oscillator. A multiplexer should work for that. Then have a jittery oscillator (another ring oscillator) to drive the mux so that the clock frequency constantly speeds up and slows down.

Syncing

I've pondered sync issues too when using a vastly different CPU frequency. Unless leaving things that unpredictable is desirable (it could be), a synchronizer comes to mind. Insert 2 OR gates into the ring, 1 before and 1 after an inverter. Maybe add others with one input tied to Ground as buffers if you really need a balanced circuit (in case there are injection issues with an imbalanced RO). Anyway, attach the outputs of a demux to the OR gates used for syncing. Then connect the selector line to the OR gate after the inverter that is being controlled. If it is one, the active demux line feeds that OR gate. If it is 0, the active demux line feeds the first OR gate instead. The input to the demux would be a control line. So this is a dynamic clock stretcher.

One might get by with AND gates instead of a demux. In that case, the control line feeds an input of each AND. The other input is the respective side of the inverter. So if the control line and the input of the inverter are high, the control signal goes there, and if the control line and the output of the same inverter are 1, then that side is held high. So this setup should allow a slower system clock to freeze this complex RO in its current state if things are too unreadable or parasitic capacitance interferes with sampling random numbers. The idea is to stop it without influencing it, if possible.

xoshiro

David Blackman & Sebastiano Vigna introduced the xoshiro/xoroshiro family of pseudorandom number generators. They are efficient and have a relatively small footprint but still display excellent statistical properties.

C versions of the generators are available on the author's website. Wrapping those routines so they conform to the C++ std::uniform_random_bit_generator concept is a trivial exercise. Once done, you can use the generators to drive any distribution in the standard C++ library.

We have a single header file xoshiro.h implementation of the generators that does that and which is distinguished in other ways:

1. The library classes are templatized across the many parameters that define a specific xoshiro/xoroshiro variant. This means you can instantiate any member of the xoshiro/xoroshiro family.
2. Of course, only a few have been vetted as “good”. Therefore, we provide some simple type aliases for the recommended default generators. The overall default is just xso::rng (everything is in the xso namespace).
3. Efficient jump-ahead methods are provided that work for arbitrary jump sizes. The jump sizes can be enormous so that you can partition a single random number stream into non-overlapping sub-streams large enough for parallel processing applications. There is a xso::partition class that makes this easy to do.
4. By optionally incorporating the extra header-only bit library for linear algebra over GF(2), you can access additional functions to extract the transition matrix for any xoshiro/xoroshiro generator. This is the key to the mathematical analysis of a generator.
5. The library has a comprehensive long-form documentation site built using Quarto. It explains how we implemented the jump techniques originally discovered by Haramoto et al.

The code is available here. It has a permissive MIT License

NOTE: This project replaces and extends an earlier library hosted elsewhere.

Hope this is the right place to ask for advice. I've need to get randoms in linux c that a crypto secure and have sampling bias removed. I've looked at several solutions and have came up with this. Is this viable for my needs?

unsigned long getDicetypeRoll(unsigned long max_value) { if (max_value == 0) { return 0; // No valid range if max_value is 0 }

unsigned long random_value;
unsigned long range = max_value + 1;
unsigned long threshold = ULONG_MAX - (ULONG_MAX % range);

do {
    ssize_t result = getrandom(&random_value, sizeof(random_value), 0);
    if (result != sizeof(random_value)) {
        // Handle error, for example, by throwing an exception
        throw std::runtime_error("Failed to get random value");
    }
} while (random_value >= threshold);

return random_value % range;

}

I mean this thread more as entertainment. Some ideas come to mind:

• Cameras in skid row. I can see weaknesses in this such as everyone being passed out at once and various attacks. For instance, let's say the footage is analyzed to produce random numbers for high-stakes illegal gambling. Then someone pays certain people to stand in certain places to generate known numbers.

• A wrinkle-counting harness that fastens to a dog's privates. That comes from the guy who got in trouble with a judge for saying he'd much rather count the wrinkles on his dog's privates than show up for jury duty. He was found in contempt of court. So I'm thinking, maybe there's enough entropy down there.

• A man used a banana as an RNG source. I would have assumed he hashed images of bananas. No, he had a Geiger counter reacting to the potassium in the banana.

• Microphones on your walls to use your noisy neighbors to produce random numbers.

• Insects. Get a capacitive sensor and put syrup on it. Then the ants and roaches might produce random numbers.

I'm curious about others.

Background

To an extent, we've had this discussion before. I'm one who needs to discuss things fully. In time, I'd like to include a homebrew RNG circuit as a part of a homebrew computer design.

For most homebrew projects, a lot of common suggestions are not necessarily feasible. Reverse-biased semiconductors require 9 to 18 volts and circuitry to amplify/buffer the output. Plus, ADCs are not very homebrew-friendly. Geiger-Mueller tubes require 90 to several hundred volts. Light sensors might be good for seeds, but not for sustained RNG production.

Homebrew-Friendly solutions.

Ideally, your RNG would use a supply voltage you're already using. It would not require special sensors or ADC ICs. Using mainly 74xx ICs would be nice. Several strategies for doing this come to mind.

An LFSR PRNG: You can create a Linear Feedback Shift Register as a crude PRNG with a shift register and an XNOR gate. I wouldn't rely on that, but you can use it to whiten the random numbers and help when other RNG stages stall. A shortcoming of those is that the period is short 1 digit unless mitigation is applied. That might require a mechanism to pause the shift register, use muxes to supply the missing value, and then switch back to the shift register while restarting it. It's easier to add traps to the software version of the Linear Feedback Shift Register (LFSR) PRNG. But keeping it quick and dirty in hardware, you might simply want to use a longer shift register and take 8 lines above the first bit. An 8-bit, hardware, XNOR-based LFSR can only return digits 0-254 (whereas an XOR-based software LFSR can only return 1-255). If you use 9 bits and take the upper 8 bits, then you should get 255 at least a couple of times in the period.

Ring Oscillators: Then, of course, is the trusty ring oscillator (RO). Connect a chain of inverters through each other and then connect the output of the last one to the input of the first one. On the surface, it seems deterministic. However, the larger the ring and the more complex the inverters, the more its speed will fluctuate based on voltage and temperature changes. Using only one isn't all that useful, so you'd need 2 or more sets of inverter rings and combine them somehow such as XORing them. A 7404 is probably the most stable IC to use for an oscillator, so you'd likely want to use others since you are after variability (jitter). NAND or NOR gates wired as inverters would be more complex. XOR or XNOR gates wired as inverters would be even more complex.

Wiring a multiplexer as an inverter is probably about as complex of an inverter as possible. You can do that by wiring the output to the selector line (or through an even chain of inverters) and wiring input 0 as 1 and input 1 as o. I would not use many of these. The 2:1 multiplexers come with 4 ganged channels and only 1 selector line for every channel. They're much like a 4PDT relay. You don't want to use many this way as that would be wasting channels. However, the other channels can be useful. For instance, if you wire a channel with the same inputs, that would buffer the channel used as an oscillator. Or you can use the mux RO to alternate between 2 other ring oscillators Using a channel in a way that one input is another ring oscillator and the other is its inverse effectively XORs (or XNORs) the input RO with the mux RO.

Multiplexers for Whitening: You can use a 4:1 mux for whitening. If an XORed ring oscillator set feeds a shift register, you can use bits 0 and 1 of the shift register to drive the mux's selector lines. So set input 10 to 1, input 01 to 0, and the other 2 inputs can come from different tap points on an LFSR. Ideally, you'd use two RNG setups so you can alternate between them to keep the bits non-overlapping.

Floating Inputs: Another way to get random numbers in hardware is to use certain ICs that generate random garbage when the inputs are left open. Floating inputs are usually considered bad practice for most applications. However, you can use certain logic gates and flip-flops this way to produce random numbers. The TTL family is better to use for this than the CMOS family since latch-up is less likely to occur. Just use multiple D octal flip-flops and XOR them. Then XOR them with an LFSR. You can also leave an MCU's ADC inputs open and use the internal ADC features.

Other Considerations: If the propagation delay is too long, you can pipeline things with flip-flops. That makes it take it longer to start producing random numbers, but if you run into timing issues or need to reduce the critical path of your overall RNG system, using flip-flops to create a pipeline may help.

Hello everyone!

I am a CS student who has been developing a PRNG focused on producing cryptographically strong bits. It is a 64-bit generator by default available as a simple CLI interface or library.

I am sharing this project now because I just reached a big milestone where the library has reached a certain point of stability. I have tried to document everything as well as I can, but I want to seek external input on the design. I want to know how to pursue further cryptographic validation, and continue to improve the design.

I guess to make this easier for everyone I'll provide some specific quick links here too in addition to the main repo.

Main Repository

Algorithm Explanation

Testing Results and Explanation

Source Files

A note about performance: It has consistently displayed high throughput so far even though I have not done proper benchmarking and comparison with other RNGs, but it comes to around 7 GB/s @ 0.5 cycles/byte on my M2 Macbook Pro. I will test on my older 2017 Windows laptop as well as a newer Windows laptop and other machines once I conduct the benchmarks, but in previous iterations, the Windows speeds have largely matched the Macbook speeds.

I would definitely consider myself more of a beginner / intermediate in this world so I think there are a lot of things I just do not know. So I'm really looking forward to your feedback!

Thanks guys :)

EDIT3: See below. I was doing something wrong, and it turns out Alea can pass PractRand to 32TB and passes gjrand up to either --big or --huge. For the performance in JavaScript, it's really not a bad choice at all.

I found out about the Alea PRNG earlier today, and I decided to run it through PracRand and gjrand. If I did the tests correctly, it is bad. It fails multiple PracRand tests after 1KB and gets a p-value of 0 on mcp --tiny.

I'm wondering if I did something to mess up my test script, could somebody else check it as well? Specifically, I was checking the uint32 output from the Node library I linked above.

EDIT: After fixing my code, it appears Alea's actually pretty OK. I haven't finished testing but it can pass PractRand out to at least 1TB.

EDIT2: My Rust implementation, linked below, passes PractRand out to 32TB. I think it's equivalent to the JS implementation. I'm not aware of anybody having done tests on Alea before, with the exception of BigCrush, so at the very least I think that's new.

I'm trying to understand Pokemon Emeralds's RNG system. What I know so far is that it uses a LCRNG and based on what the player did in the previous frame a different number is added to the seed which is what the game uses to determine what will happen in the next frame. That made sense until I came across this formula result = 0x41C64E6D × seed + 0x00006073 which in theory determines the next seed. From my understanding if there is a fixed formula it doesn't really matter what the player did in the previous frame the outcome will always be the same and what really changes is just where it's going to happen due to the player going around. Does the last player action actually interfere with the seed generation or am I just tripping balls. (Btw the seed always starts at 0).

For anything RNG, is it ever possible to never get something good in "forever"?

First off, I'll start by sharing my interpretations of "RNG", using the example of an RNG, with numbers from 1 to 100,000.

1. Lets say you want to spin for the number 3,000. It will mean that, theoretically, you have to spin 100,000 times to get the number 3,000.

2. Also wanting to spin for the number 3,000. This means that everytime you click "spin", there is a 1 in 100,000 chance that you will spin for the number 3,000, and the chances for all spins are equal.

However, these 2 interpretations are linked. Let me explain. Only in theory will interpretation 1 be guaranteed, i.e. getting the number 3,000 in 100,000 rolls. However, in real life, some discrepancies might happen, and those discrepancies are like interpretation 2.

So, this begs the question: If you spin the RNG for "forever", will it ever be possible to never get the number 3,000?

I realize this may not be the right place for this. But does anybody know of an online calculator/program that can generate the number of attempts until a certain number is reached.

For instance I want to generate a random number out of 12,000, say 5,608 And then I’d want the calculator to tell me how many actual attempts it would take to generate 5,608 again out of 1-12,000, because as we know it can take more than 12,000 tries to get that same number.

I know this would probably be pretty easy to code but let’s assume I can’t do this.

For context, I have a double degree in physics and computer science and I recently developed a basic secure password generator software made in Java using the SecureRandom class. And this made me very interested in Random Cryptography, RNG Algorithms, their variants and related topics. And I really liked it so much that I want to start studying more about this specific subject to specialize in my academic career, start publishing articles about it and maybe one day become a reference in this.

Reading a few references I found about RNG algorithms, I learned some basic concepts, (for example I saw that, as far as I know, my secure password generator software can be classified as what its called CSPRNG), and I also learned some other variations, such as TRNGs, which has its sources of entropy coming from physical phenomena of chaotic systems (which can be, for example, the movement of fluids in lava lamps like Cloudflare does, or also quantum mechanics based algorithms, or using radio noise, and much more)...

However, in my attempts to research books or materials about this to really study/learn, I noticed that it is very difficult to find books or materials specifically about that. Whenever I tried to search specifically about these things, I either found some superficial results from technology sites speaking superficially about RNGs, or Cryptography books that teachs Cryptography in general, (I mean, not specifically about Random Cryptography or RNGs)...

And, having already made secure password manager software, I know the basics of cryptography and I've already learned a lot more of things along the way, of course, cryptography in its most general form is obviously related to the subject of Random Cryptography and RNGs... But what I'm trying to say is that sometimes it can be very dense to read an entire cryptography book (that teaches cryptography in general) without much relation to Random Cryptography or RNGs, that is what I'm trying to research...

So, I come here humbly to ask:

1. First, where to start? (besides doing a password generation software, because I already did)
2. What good books/materials are there on Random Cryptography and RNGs Algorithms?
3. What scientific papers or authors should I read on the subject?
4. What types of tests are standards for metrics in the scientific papers on this subject for RNGs algorithms?
5. Is there something else that I should know? Give me tips please.

​

With a function that takes a uint64_t n and returns (n+a)*b where an and b are constants, how can I find values for them that would lead to a period o 2^64-1? I can't really brute force it

I've been testing a new idea for almost infinite PRNGs.

I'm using multiple LCGs with prime numbers as multiplier, modulus and initial value; the constant does not seem to matter that much, so I'm using 1. I combine the output from each LCG with XOR to produce the final output.

Although LCGs are not particularly good individually, I've found that when several are combined together, the output rapidly becomes excellent (passes all tests in Practrand), and the period also increases significantly.

I've been using LCG parameters selected from a table containing 10million primes from 100003 to 179606689, and I've typically been using 10-20 LCGs. My tests suggest that the period of the combined 20-LCG is equal to the product of the periods of the each individual LCG. So for a 20-LCG RNG, the period would something in the order of 100000000 ^ 20 = 10e160. If another 20-LCG RNG was started whenever the previous RNG repeated (and so on), then the combined period would be in the order of ((10e8 ^ 20) ^ (10e7 ^ 3)) = 10e3360 (if my maths is correct). This could be increased if the table of primes was made bigger.

I recently found that this idea is not new... it's called Wichmann-Hill, but the original definition used just 3 LCGs, whereas I'm suggesting a larger number.

Obviously, I've only been able to test a relatively small number of the total possible RNGs I could create from my primes table, but every one has passed all tests in Practrand.

I would be interested to hear what others think, and especially from anyone who has experimented with the same idea.

​

I'm fascinated with RNGs and I found your wiki files. That has a lot of good stuff and things I don't know yet. I'd be glad to be approved for wiki access (editing) if the mod will give it.

There are a couple of things I'd like to say about HWRNGs. One is that they can be deterministic. You can do both types in hardware. You can use a shift register and an XNOR gate (or XOR with more work). You can tap the 2 highest pins of the shift register, XNOR them, and feed that back in as the input. That is an LFSR (linear feedback shift register). LFSRs are deterministic since you always get the same numbers in the same order.

LFSRs tend to inherently have certain weaknesses, namely 2 unless more extensive hardware or coding is used. There will be 1 number it cannot return. The other problem is that if by chance the number it cannot return is somehow put there, it latches up. So there is always a missing result and an unusable seed. If software, you can trap for these conditions. You can use logic to mitigate the seed that cannot be used. That prevents the latching problem but exacerbates the other problem since you not only have a result that cannot be returned but another result is returned twice. So then you replace the output of that number with the unusable seed. So with proper trapping, every number can be used as a seed, and every possible result can be returned.

In a hardware LFSR, XNOR is preferred since the shift register initializes to 0. XNOR is an equality function (only in the 2-input version). So if you take the top 2 bits of the shift register and XNOR them, the 2 starting zeroes become 1. Then you are feeding the 1 back in. But really thinking it through in my head, I realize that for an 8-bit shift register, you'd only get numbers 0-254. 255 is the number that latches the LFSR and cannot be returned. For something like white noise generation in an arcade game (like Asteroids), that might be good enough. The simplest mitigation I know of would be to make it at least a bit wider. So you would get 0-510, but never 511, but if you take only 8 bits, you will have 2 periods, one with and without 255. That is not a perfect solution, and if you add more bits, you get better odds. Of course, you could do other things in terms of trapping, or you could use counters, pause the LFSR, and insert the missing result. Or, you can just settle with it being a result short of a perfectly balanced period. You could combine that with another HWRNG on the same board.

In terms of noise sources, one is shot noise. Schottky noise is a similar phenomenon. You take a diode or transistor (usually with the collector lead clipped or unused) and reverse bias it to its breakdown voltage. Often, that is about 12-18 volts, depending on what diode is used, and 9-12 volts for certain transistors. Theoretically, you should expect nothing since diodes and transistors are supposed to only allow current through in one direction. However, if you block enough current, some electrons will slip through and attempt to conduct. Then you amplify/buffer the output of that. There are at least 2 different things you can do at this point. One is to treat this as an analog signal. So you can send it to an ADC IC or a microcontroller ADC input line. Then you can read bytes or words at a time. Or, you can treat that as a digital signal. You could control the gain using a potentiometer and/or a Zener diode, and then maybe feed that to a Schmitt trigger to clean up the signal, and then clock that into a shift register. (Or, you could even do both, treating the signal as both AM/analog and as FM/digital, and reuse some of the entropy within a different context and span of time.)

Now, I've been pondering designing a true HRNG using mostly 74xx ICs and very few support components. One of the easier ways would be to use ring oscillators. A ring oscillator is just a looping inverter (NOT gate) chain. There are an odd number. It seems that the longer the chain, the more entropy you have, but also, the slower things change. You'd use at least 2 of them of different lengths to get both the effects of entropy and the deterministic aspects of beating/adding/XORing 2 clocks. If 2 clocks that are out of tune with each other were to start at the precise same time and remain the precise same size the entire time of operation, that would be deterministic. However, there are tiny variations in this, and using a ring oscillator as opposed to a crystal oscillator would increase the variations (jitter) present. So using longer inverter chains and multiple inverter chains should increase the entropy. And using 3 of these together is considered good practice. That way, if there is a chance one of the ROs synchronizes to the board frequency, you'd have a 3rd RO to mitigate this.

Then, where you would go from this would be to use a shift register to make bytes (or words, doubles, quads) out of the input stream. You could apply whitening as you make them and even have multiple RO units to increase yield. For instance, you could have 2 RO units and take turns switching between them and whitening the stream. Then you can complete an evaluation of 2 bits each cycle. That would allow each shift register to have moved twice before you evaluate it. And really, you can tap off 2 points on the shift register, XOR them for a control signal, and if they XOR to 1, then the higher of the 2 bits is used for the output. And if they XNOR to 1, maybe use another source altogether such as an LFSR, or conversely, rotate the shift register and maybe only use an LFSR as the output when you've exhausted rotating the shift registers.

And you could get fancy with this if you wanted. I've wondered what would happen if you take 2 ROs to drive 2 different sets of counters. Then take another oscillator to drive a multiplexer (mux). That sounds more deterministic than above, but you could use a wider mux and either 2 ROs to switch it, or an oscillator and another counter. So, if you use a quad mux, what would the other 2 inputs be? One could come from a shift register with ROs A and B XORed together. For a 4th input, one could add the counters. And if one uses an 8-channel mux? Maybe add an LFSR. XOR the LFSR with the other shift register, and do 2 other things. Like maybe have 2 more shift registers and XOR a bit from the LFSR with A for one and B for the other. Or options to invert the counters, etc.

Another note. I read how someone used a 555 timer and an Arduino to make random numbers. To me, it blurs the line between deterministic and nondeterministic. But in practice, it may be more nondeterministic. So the 555 is configured to produce sawtooth waves. There is a line that is normally used that you can leave floating to possibly improve the entropy. Then the output is fed into the ADC line on the Arduino. Then some whitening is done using code. That seems to produce acceptable results and pass most Monte Carlo tests. Some others will read the line with nothing connected to it and get reasonable enough random numbers.

Now, one thing that stands out to me here is that the 555 approach may not be all that different from using a ring oscillator driving a counter. The sawtooth wave is sampled at different points on it, depending on the CPU/MCU clock. Then that is converted to a digital result, ranging from 0-255 (or 0-65535) or whatever. It seems this could be easily simulated digitally. Just use a ring oscillator and counter ICs. The increasing count is like the increasing amplitude of the sawtooth wave, and then it rolls over to zero, just like the sudden drop of the sawtooth wave.

This is two line PRNG which I named CWG128:

static __uint128_t c[4]; // c[0] must be odd

__uint128_t CWG128(void){
c[1] = (c[1] >> 1) * ((c[2] += c[1]) | 1) ^ (c[3] += c[0]);
return c[2] >> 96 ^ c[1];
}

By using different c[0], you can initialize 2^127 independent streams, using random numbers or just a counter, but then you have to skip 96 outpus to decorelate states of the generators.

One of the simplest generator based on the original Collatz sequences is:

static __uint128_t x, weyl, s; // s must be odd

bool Collatz_Weyl(void){
x = (-(x & 1) & (x + ((x + 1) >> 1)) | ~-(x & 1) & (x >> 1)) ^ (weyl += s);
return x & 1;
}

It returns one bit in each iteration. It can produce 2^127 bits, until the Weyl sequence will loop. It is bassically just a Collatz funtion combined with a Weyl sequence, to prevent short cycles:

static __uint128_t x, weyl, s; // s must be odd

bool Collatz_Weyl(void){
if(x % 2 == 1){x = (3*x+1)/2;}
else{x = x/2;}
x ^= (weyl += s);
return x & 1;
}

Several authors have previously tried to use Collatz sequences to generate randomness. For example, Givens R. in "On Conway’s generalization of the 3x + 1 problem" considered certain generalizations, functions that generated sequences very slowly diverging to infinity. The problems have always been short cycles or divergence to infinity. The use of Weyl sequences and modulo operation eliminates these problems - the number of schemes that we can create this way is as huge as number of generalizations of Collatz-type functions we can think of. For example generator:

static __uint128_t x, weyl, s; // s must be odd
 
bool Five_x_Weyl(void){
if(x % 2 == 1){x = (5*x+1)/2;} 
else{x = x/2;} 
x ^= (weyl += s); 
return x & 1; 
}

Produces good quality pseudorandom bits as well.

Paper:

https://arxiv.org/abs/2312.17043

(I don’t know crap about RNGs) The Acura MDX has an HDD music source where you can upload CDs to build up a playlist, and it has a Random setting that shuffles the music. The shuffle kind of sucks, playing a much smaller variety of songs than there is available (anecdotal, heard many accounts though). I was curious what makes the shuffle system tick, anyone know or know how to determine?

https://www.sensitiveresearch.com/Objects/GTNG/

Discovered today while hunting around for the General Radio 1390B using general terms (I couldn't remember the company name, but knew it had a gas tube in it).

An Idea

The other night I got to thinking about manual, by-hand, non-electronic random number generators. We're already familiar with flipping coins, tossing dice, shuffling playing cards, drawing lottery balls from a spinning tumbler, and shaking paper, but what else is there? I have a 3×3 Rubik's Cube on my bookshelf and thought that might work.

The Math

The number of unique permutations for different sized N×N cubes is well known:

• 2×2: 3,674,160
• 3×3: 43,252,003,274,489,856,000
• 4×4: 7.40×10^(45)
• 5×5: 2.83×10^(74)
• 6×6: 1.57×10^(116)
• 7×7: 1.95×10^(160)
• 8×8: 3.52×10^(217)

Scrambling the Cube

The goal is scrambling the cube enough times to put it in one of those unique states such that it's improbable for an adversary to duplicate. The trick is in figuring out how many scrambles are necessary to create that security margin. It's critical that each smaller cube has the uniform possibility of reaching every position (except the center for odd-number N×N cubes), and that each position has the uniform possibility of seeing every possible rotation.

For the 3×3 Rubik's Cube God's Number is 26. This means that every possible permutation of the 3×3 cube can be solved in 26 quarter turns or less. In other words, you cannot scramble a 3×3 cube worse than one that requires 26 quarter turns to solve.

The World Cube Association's official TNoodle software averages 18-19 turns from a solved state before presenting a 3×3 cube to the contestant to solve. Note that each twist is not a quarter turn however—some are half turns.

As such, it seems reasonable to assume that 18-26 turns (quarter or half) might be sufficient for scrambling a 3×3 cube preventing someone else from blindly duplicating it. More rigor should be done here to confirm this, however.

Security Margins

If we were to use TNoodle as a ballpark number for the number of turns necessary to maximize the work of an adversary wishing to duplicate the final state, then for each N×N cube, it would look something like this:

The World Cube Association doesn't have contests for 8×8 cubes, so it's not an option in the TNoodle software. However, considering the above pattern of approximately 20 turns per N×N cube, it seems reasonable that at 8×8 cube would require 120 turns to sufficiently scramble the cube.

Other than an 8×8 cube, the 3×3 cube remains the most efficient when it comes to maximizing the security per turn. For a 512-bit RNG, you need to record the state of 8 separate scrambles of 19 turns each. This is a total of 152 turns.

How-To

Obviously, scrambling the cube should be done blind. This would remove any influence or bias you might have on the cube trying to put specific colors into specific positions. Scrambling the cube behind your back while counting the turns might be the best approach. Once the cube is sufficiently scrambled, all you have left to do is record all 6 faces. You could do this face-by-face or layer-by-layer.

For example, you could record the top face from the top left smaller cube working left-to-right then top-to-bottom ending with the lower right smaller cube. The take the same approach with the right face, back face, left face, and bottom face.

If you wished to do it layer-by-layer, then again, you could start with the upper left smaller cube on the top face ending with the bottom right smaller cube. Then record all outer colors on the top row, starting with the front face, then right face, bottom face, and ending with the left face. Move to the middle row following the same pattern, then the bottom row, and end with recording the faces on the bottom row.

All HWRNGs have inherent biases, and this Rubik's Cube RNG is no different. When you know the color pattern of one of the smaller cubes, this provides information about what's left with the remaining smaller cubes, as the position and orientation of each smaller cube is dependent on the others. So we'll need to whiten the RNG to remove the bias. This is best accomplished by running the output through a cryptographic hashing function, such as SHA-3.

Example

Knowing that each scramble provides about 65 bits of symmetric security for a 3×3 cube, if I wished to generate a 256-bit symmetric key, then I would need to record the output for scrambles. Suppose they were (O=orange, G=green, Y=yellow, W=white, R=red, B=blue):

I could then get my 256-bit key via:

$ cat << '.' | sha3sum -a 256
GOOYWGRRBYRBOOBOWRWGYRGWYBWOOGBRGRWRWBOYBYBWWGYGOYRBGY
OYWWWOROGGGBWOBOYGWWROGBROBWORRRGWWOYGYRBBYYGYGORYRWBB
YORYWWWGBRRRYOWWBWBOYRGGOGROOWWRWYBOGYBBBBGGOBRGOYRGYY
YWWBWWWYGBYBRORGOGOWWYGOYWGORRBRYRRBBGOOBGYYROOYGYBWGR
.
dc4ca75eaeb54aff44aacc19e4b6c842e1016af3ec607a835847ad821611caf5  -

Gotchas

When recording the colors with an odd N×N cube, don't be tempted to put the center squares into a certain position (EG, white on top). When you're done scrambling, just place it on the table and start recording, regardless of orientation.

This RNG is obviously error-prone. As a HWRNG, it's not important that the process can be repeated, so mistakes are generally okay. However, you really should make every effort to be as accurate as possible. The more mistakes you introduce transcribing the colors, the more you could be reducing the security margin.

Taking two photos of the cube with your phone might be a better idea, where each photo can see all the colors of 3 unique faces. Concatenate both photos and hash with SHA-3, then you don't need to worry about being error-prone with the transcription. This does reduce the elegance a bit though of being "by hand", but then again, you're still relaying on SHA-3, so meh.

The scrambling process is kinda slow. Obviously this isn't going to be something you want to do regularly. Instead, rather than using the output directly, you would be better off sending the output once to a CSPRNG and using the CSPRNG going forward to get your keys. So seed your kernel RNG, then use that for everything cryptographically related:

$ echo 'GOOYWGRRB...' > /dev/random

THIS PART IS CRITICAL: Once you've recorded the colors of the cube, you need to destroy the transcription (or photos) as well as further scrambling the cube. This also means erasing the command(s) from your shell history. Remember, the goal is to make the adversary reproducing the state as difficult as theoretically possible. Kind of defeats the purpose if you leave the state lying around for them to discover.

However, it does beg the question: if you want to use the cube again as an RNG, should you start from a solved state, or is carrying the previous state into the next okay? My intuition tells me that carrying the state along with you is fine, so long as you continue to provide the sufficient number of twists for your cube (after destroying the previous state). But solving it "resets" the cube giving the adversary no information about any previous states should they come in possession of your cube. Solving it also could be good practice. Shrug.