1
$\begingroup$

So I developed this algorithm as RNG, although it looks random to me, I wanted to know the opinion of more experienced persons in the topic.

from time import time_ns
from math import sqrt
class Random:
    incr = 0
    seed = 0
    defloat = lambda x: x*(10^(len(str(x))-(str(x).find(".")+1)))
    def __init__(self,seed=None):
        
        if seed == None:
            seed = ''
            for _ in range(10):
                t = time_ns()
                
                l = round(len(str(time_ns()))/3)
                o = str(time_ns())
                a = int(o[:l])
                b = int(o[l:2*l])
                c = int(o[-l:])
                try:
                    x = hash(((sqrt(b**2-(4*a*c)))-b)/(2*a))
                except:
                    
                    pass
                
                e = time_ns() - t
                seed += str(e)
            
        h = round(len(str(seed))/2)
        s = str(seed)
        self.seed = int(s[:h])
        self.incr = int(s[h:])
    
    def _bit(self):
            
            result = sqrt(self.incr+self.seed)
            self.seed = Random.defloat(self.incr+result)
            self.incr = Random.defloat(result)
            return round(result) % 2

    def fair_bit(self):

        bits = [self._bit(),self._bit()]
        while not bits in [[0,1],[1,0]]:
            bits.pop(0)
            bits.append(self._bit())
            
        
        return bits[-1]
        
    def octabit_number(self):
            
            r = 0
            for i in range(8):
                
                r += self.fair_bit() * (2**i)
            return r
```
$\endgroup$
2
  • $\begingroup$ Welcome to the forum! Err, is this a native floating point RNG? That's brave - kudos. You realise that floats are virtually non deterministic on modern computers? $\endgroup$
    – Paul Uszak
    Sep 8, 2023 at 16:34
  • $\begingroup$ You could put it through NIST's statistical test suite. $\endgroup$
    – lamontap
    Sep 8, 2023 at 18:10

1 Answer 1

2
$\begingroup$

In order to produce a cryptographically secure pseudorandom number generator (CSPRNG), the output has to pass the next-bit test. Roughly, that means that if an attacker has a given amount of output of that generator, they cannot guess the next bit with a better probability than 0.5 (random chance). Due to Kerckhoff's principle, that means that the attacker can poke, prod, and analyze the algorithm at will to determine that information.

To determine if this generator meets that test, let's look at the internals. First, let's skip the entropy generation part with time_ns and always specify a seed. This will make our output deterministic and easier to analyze, and, since we assume in a CSPRNG that the seed or entropy input is the only private data, we're no worse off.

We can also note that fair_bit is effectively output whitening. To aid in analysis, we'll simply call _bit in octabit_number, which will help us better understand the output of the raw generator.

If we break down defloat into a multiplication and the rest (which we can call semi_defloat), we get a definition like this: semi_defloat = lambda x: (10^(len(str(x))-(str(x).find(".")+1))). We can observer that the result of semi_defloat is typically a small integer, usually 4, 5, or 7. Other values are possible, but, for analysis's sake, we'll want to determine the most likely internal state to see if we can more effectively cryptanalyze it. Thus, defloat is effectively multiplying its input by a small integer.

I noted that it may have been the intention to perform an exponentiation here, but that is not what ^ does in Python (it performs an XOR). I tested with an exponentiation and that leads to the generator devolving into producing entirely zero bits as the values become very large and consistently even, so that is not an improvement in design.

One thing I noted is that if the input state is all zeros, then the output is also zeros. In both this case and my test exponentiation above, the real generator simply hangs since the whitening step fails. While not insecure, this is practically inconvenient, and as such would be considered a weak state.

Thus, the core of the generator consists of two values, which it updates with a square root, an addition, and some multiplications by small integers.

We should note that the fractional part of the square root operation is very important because if we use int on the sqrt, the generator tends to devolve into a fixed state (usually all-ones) very quickly. Similarly, if we change the call to Random.defloat with a call to multiply 4, 5, or 7, then we also devolve into a fixed state (either odd or even, depending on the integer) quite rapidly, so the exact semantics of Random.defloat are very important.

A final thing I noted examining this is the internal state values tend to end up hovering around having 2 or 3 digits before the decimal point. If we assume that we're using a normal double-precision float here, that means that we're expressing a tiny fraction of the valid 64-bit values we can. Thus, the internal state here is substantially smaller than 128 bits, and thus this is probably subject to brute force.

I don't have a huge amount of time to spend on analyzing this further, but due to the smaller-than-expected effective internal state and the absolute dependence on the variation in the small integer of Random.defloat to not devolve into a fixed state, I'm not very confident in this design. It's my expectation that a real cryptographer (which I am not) with more experience would probably be successful in attacking this without too much difficulty.

$\endgroup$
6
  • $\begingroup$ Hi, thank you for your analysis, I will try to improve this further. The defloat function was added to exactly prevent the generator to devolve into a fixed state. It was indeed to be an exponential as to use the last digit of the float (thankfully my mistype worked better). I suppose you might be busy, but it would be lovely if I could send you further versions for analysis. $\endgroup$
    – lucas
    Sep 9, 2023 at 0:36
  • 1
    $\begingroup$ In general, I don't think I'm a good person to cryptanalyze algortihms because I'm not a cryptographer, only a software engineer. However, I hope that you can apply the techniques I've mentioned here, as well as techniques mentioned in the literature, such as differential and linear cryptanalysis, to analyze your own algorithms and see how they compare to ones we use in real life. $\endgroup$
    – bk2204
    Sep 9, 2023 at 1:01
  • $\begingroup$ Thanks for your time, could you summarize in bulletin points your suggestions please. Also, I did some analyzing of the bitstream, and It's very likely that the digit that comes after an "00" is an "1" (70%~).Again, thanks for your time, peace. $\endgroup$
    – lucas
    Sep 9, 2023 at 1:10
  • $\begingroup$ I think the answer is great. This is a site where people voluntarily answer questions. Maybe you should summarize the points in bullet form? That will help you understand what the answer is saying and ask for comments afterwards. $\endgroup$
    – kodlu
    Sep 10, 2023 at 12:58
  • $\begingroup$ Didn't think by that side, thanks :) $\endgroup$
    – lucas
    Sep 10, 2023 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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