3
$\begingroup$

Is there a floating-point CSPRNG that operates, natively, using floating point operations?

Looking for a CSPRNG that's very fast on GPUs, and would be hard for a CPU to beat.

EDIT: Floating point doesn't matter too much. Specifically, I'm looking for something for which GPUs or FPUs are, by far, the optimal hardware to use: as opposed to custom hardware, because the operations used are already heavily optimized on GPU.

My understanding is that floating-point-operations (FLOPS) are probably the best candidate here. (It seems to me that most chaotic attractors can be trivially run using FLOPS.)

$\endgroup$
  • $\begingroup$ Why does fast on GPU imply using floating point operations? I thought that GPU could also be fast at some integer operations, for example some people use them to mine bitcoins and that's centered on calculating SHA-256 hashes. You can use SHA-256 to build a CSPRNG. $\endgroup$ – Gilles 'SO- stop being evil' Apr 25 '17 at 18:49
  • 1
    $\begingroup$ There are two issues with this question: 1) You can beat almost anything with a FPGA as you can have pseudo-custom hardware. 2) integer math is so much faster, so you could have a "fixed point" system beat a floating-point system any day, for anything. $\endgroup$ – b degnan Apr 25 '17 at 19:14
  • $\begingroup$ Nobody uses GPUs to mine bitcoins because the specific integer operations on GPUs are slower and less energy efficient than in custom hardware. FLOPs have been so heavily optimized on GPUs that whole supercomputing campus facilities have been built around them. The idea is to have a CSPRNG that GPUs are simply the best at and probably always will be. $\endgroup$ – Erik Aronesty Apr 28 '17 at 13:44
  • $\begingroup$ Why not just use the Alternating Step Generator which has no public break since it was invented in 1987. It uses just 3 shift registers and some simple logic gates and is considered to be cryptographically secure as long as the shift registers are at least 128 cells long and seeded from a reliable entropy source. $\endgroup$ – William Hird Jun 13 '17 at 20:30
  • $\begingroup$ @ErikAronesty But of course GPUs are used to mine bitcoins: Bitcoin mining "tech savvy users and even groups have taken to buying high-end "gaming processor cards" – GPUs (otherwise known as graphics processing unit cards) – to build "mining rigs" to generate the highly valuable cryptocurrencies." $\endgroup$ – zaph Jul 8 '18 at 2:45
11
$\begingroup$

Are you sure?

Float operations are very hard to reproduce in diverse environments.

Do you round towards positive, negative or zero? Do you handle denormals or just treat them as zero? What about dividing by zero?

I'm sure we would love to have that problem with every cipher we implement.

Looking for a CSPRNG that's very fast on GPUs, and would be hard for a CPU or FPGA to beat.

To beat FPGA... don't do anything. There are problems that are slow on CPUs & GPUs, but otherwise you won't have as big FPGA that can reach nearly same frequency. If that wasn't case we wouldn't have processors, just builtin FPGAs that switch between GPUs and CPUs...

To beat CPU... just use something that uses a lot of simple math... +,-,xor,ror,rol etc. This doesn't have to be on floats, ints will suffice. Chacha20 might work well on GPUs. Note that this won't be slow on CPUs, it will just be faster on GPUs because it parallelizes well (and this is always case, because CPUs are complex beasts that can do more than GPU, except there just isn't enough of it for raw number crunching at that speed).

Honestly, most cryptographic primitives will be faster on GPUs because they frequently rely on number crunching, and rarely do any significant memory access and/or branching.

Just remember that there are still ASICs that will always win against you, because they are exceptionally good at number crunching (and if you are looking to outrun them, argon2 and CPU are your friends).

| improve this answer | |
$\endgroup$
  • $\begingroup$ FPGA is a non issue. ASICs are not going to beat FPUs at floating-point operations. As long as the ops are FP heavy, it should be OK. And since many CSPRNG's are integer analogs of chaotic formulae that can be represented as FP operations, using a true FP version should work well. My problem is that most algos capture only one bits of entropy per iteration... Maybe the best way to do this is to simple use SHA3 on a series of steps. $\endgroup$ – Erik Aronesty May 1 '17 at 16:55
  • 3
    $\begingroup$ @ErikAronesty you are mistaking things. ASICs will beat FPUs, since FPUs are all made of ASICs, so you can make more specialized ASICs to win with your general FPU. CSPRNG operations cannot usually be represented as FP operations, because of precision and defined modulus. Also you seem to mistake what entropy is, and that FP has defined precision and because of that entropy (which is actually more limited than in integer operations!). $\endgroup$ – axapaxa May 1 '17 at 21:32
  • $\begingroup$ Obviously any FP operation can be modeled as integer and vice versa, so claims to the existence of entropy in one or the other is odd at best. It would be very challenging to make a special-purpose FPU that beat a general purpose FPU.... unless the algorithm was poorly developed. $\endgroup$ – Erik Aronesty Jun 1 '18 at 18:01
  • $\begingroup$ @ErikAronesty Of course they can be modeled as one another, using very complex routines (that are very slow). Of course entropy exists in one and second, but floats have less entropy (NaNs come to mind, those aren't correct values for FPU calculations). Making special-purpose FPU is hard, but is easily in reach of powerful adversary. Please if you have any more questions, ask new question. $\endgroup$ – axapaxa Jun 11 '18 at 13:50
  • 2
    $\begingroup$ Floating-point arithmetic is not hard to reproduce in diverse environments. IEEE 754 arithmetic is well-understood, widely implemented, and absolutely predictable and reproducible. Floating-point division by zero is no more a problem than integer division by zero, which is already not a problem any cipher designers worry about—actually, floating-point division by zero has more consistent semantics than integer division by zero, spelled out and consistently implemented for decades. Sometimes crypto is effectively implemented with floating-point arithmetic, like Poly1305. $\endgroup$ – Squeamish Ossifrage Jul 10 '18 at 21:47
-2
$\begingroup$

No. There are no common floating point PRNGs.

If you search the literature there are few PRNG that utilises native floating point computation. This not so cunning program illustrates why they are unreliable across different architectures. Try the following on i386 stuff:-

for ($i=0; $i<1000; $i=$i+0.1) {}
print "$i";

The answer is:-

1000.00000000016

The (unexpected) extra 16 part at the end is rounding due to the inability to accurately represent decimal numbers in binary. And this rounding is highly dependant on the underlying hardware /software.

Repeating with:-

i=0
while i<1000:
    i=i+0.1
print(i)

I get:-

1000.0000000001588

Where's the 16 bit gone as I added up exactly the same numbers, this time using Python rather than Perl? And on Atmel, the answer is a round 1000.00. A CSPRNG is validated against an output run of mega bytes of data. With such unpredictable rounding errors, it would be difficult to validate on various platforms. As a relevant aside, it's why computer currency calculations are performed as integers.

Another unexpected issue with floating point is that bit wise adjacent numbers aren't the same numerical distance apart. One single adjacent bit change can alter a floating point number by a difference that can vary by an astonishing 24 orders of magnitude. This is better represented with picture like so:-

precision changes

Generators like RC4 and ISAAC (to name two) are entirely based around array indirection functions, and array indices have no meaning unless they're integers. Commonly used left and right bit manipulations also become meaningless on a floating point number as the exponents would break storage conventions.

Of course you can always roll your own thing that will produce random looking output. So a construction using a hash of the output of my example would produce a cryptographic ally irreversible number stream. So you'd have:-

Hash(Perl program output).

However, the rounding error will bite you as it will form a deterministic (for your specific machine) error bias. So the number stream will be useless for all but the most trivial of applications. So speed is kinda irrelevant. There aren't any CSPRNGs out there.

| improve this answer | |
$\endgroup$
  • $\begingroup$ That's not a concern of mine. All IEEE standard FP representations in CUDA are binary compatible.Indeed, this "rounding error" problem is largely obsolete on modern x86 machiens that implement standard optimized FPU operations. $\endgroup$ – Erik Aronesty May 1 '17 at 16:56
  • 3
    $\begingroup$ By enforcing type and rounding mode, different CPUs/compilers/OS can compute the same result, especially when using hardware FP (not available on arduino), thanks to well-defined IEEE arithmetic. But a serious issue is that results obtained using a given FP representation often differs form the mathematical result, and that discrepancy grows exponentially with the number of iterations, to the point that FP and true result quickly diverge totally. Consequence: elementary mathematical demonstrations of chaotic behavior or long PRNG cycles do not apply to FP implementations. $\endgroup$ – fgrieu Aug 30 '17 at 16:47
  • 1
    $\begingroup$ This answer is false on its face. If you search the literature you will find examples like George Marsaglia and Arif Zaman, ‘A New Class of Random Number Generators’, Annals of Applied Probability 1(3), August 1991, pp. 462–480. It's not a cryptographic PRNG, of course. But IEEE 754 floating-point arithmetic is well-understood, widely implemented, and absolutely predictable and reproducible. $\endgroup$ – Squeamish Ossifrage Jul 10 '18 at 15:43
  • 3
    $\begingroup$ @fgrieu's comment does not change the fact that the opening sentence of this answer is false. Indeed, fgrieu's comment really only addresses naive substitution of floating-point operations for integer operations. It doesn't address whether floating-point arithmetic can be used in the design of a PRNG, to which the answer is obviously yes, though the performance for cryptographic security might be disappointing compared to other algorithms based on integer arithmetic or bitwise operations. $\endgroup$ – Squeamish Ossifrage Jul 10 '18 at 22:19
  • 1
    $\begingroup$ @PaulUszak Can you find environments with non-IEEE floating-point arithmetic? Yes. The VAX in my friend's basement is another one. But the vast majority of computers that anyone cares about today provide IEEE 754 floating-point arithmetic. Maybe 8-bit microcontrollers have slow/software-only floating-point, but they also have slow/software-only 32-bit or 64-bit integer arithmetic like other cryptography such as ChaCha or BLAKE2 uses. You still haven't corrected your factually false assertion that there isn't a single PRNG using native floating-point arithmetic in the literature. $\endgroup$ – Squeamish Ossifrage Jul 10 '18 at 22:39
-3
$\begingroup$

Here is an example of what I'm looking for. Yes, it hasn't been tested. The underlying attractor has been proven a good source of randomness, and approximations of this technique have been used for other CSPRNG systems.

While the hashes are fast, the FP operations will be slow. So this will, slowly, generate pseudorandom numbers, and will be both FP heavy, with highly sequential FLOPs.

  • To prevent cryptanalysis, the settings for N and X must be high enough that you're not capturing too many bits per iteration. Keeping X low increases the ratio of FLOPS. Keeping N low makes the algorithm more efficient, but less secure.

EDIT: Although the lorenz family of attractors are provably unpredictable and well-studied, the number of bits to capture per iteration is a matter that would require some experimentation and analysis to be provably secure. Possibly it could be a number much less than one. In which case this could be terribly inefficient. There are other attractors used in secure cryptographic pseudo random number generators that may yield a better entropy level per iteration.

(I suspect that a fun paper to write would be one that can turn any chaotic attractor into a CSPRNG by determining optimal values of X and N for a given level of security required, level of leakage, etc. Autotune for CSPRNG.)

The concern responders have for the approximations used in FP operations aren't really an issue and are basically useless non-information, please stop posting them. Far more data is discarded and approximations made in other attractor-based integer CSPRNGs. In fact you could simply change any FP system into an integer system with sufficient motivation. But the point would be to make a system that's optimized for FPU's... which are can be analogized as the cheapest, most powerful and plentiful ASICs on earth.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ What makes this cryptographically secure? The SHA-3 step is not invertible except by brute force, but what about the floating point steps? How well do they preserve entropy? Where is a peer-reviewed analysis of this algorithm? $\endgroup$ – Gilles 'SO- stop being evil' Apr 29 '17 at 10:28
  • $\begingroup$ @Gilles - I edited this to explain the level of security. The entropy perserving qualities of the lorenz family of attractors is extremely well studied. Choosing a specific one should be done using some peer-reviewed papers as the basis... which is why I didn't specify which one. $\endgroup$ – Erik Aronesty May 1 '17 at 17:01
  • 3
    $\begingroup$ It is not addressed the the fact that FP operations only compute an approximation of "the hyperlorenz attractor (..) for N iterations", that the approximations (provably) cause overwhelming error after a small number of iterations, and that whatever provable results there are about that attractor become invalid when accounting for the approximations. $\endgroup$ – fgrieu Jun 12 '17 at 8:46
  • $\begingroup$ I suspect that the "overwhelming error" will be sufficiently chaotic as well. But yeah, you'd have to test that for skew, etc. $\endgroup$ – Erik Aronesty Aug 29 '17 at 15:12
  • 1
    $\begingroup$ Software implementations of Keccak are slow even when implemented on the CPU. I would be very surprised if there were no CPU optimized algorithm that was faster than Keccak on most GPU. It's possible for maybe a few GPUs (present or future) but I doubt it would be common. If for some reason you can invoke Keccak then you can use SHAKE's extendable output alone as a PRNG. The hyperlorenz attractor using FP arithmetic part is completely unnecessary. I'm reminded of this cartoon clip youtube.com/watch?v=d59J78yhwtg And don't invent your own algorithms it's hard even for experts. $\endgroup$ – Future Security Jun 1 '18 at 17:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.