-1
$\begingroup$

I recently developed a PRNG from scratch with a little inspiration from the initialization function used in the HC stream cipher. The state ($S$) of the basic version is an array of 5 bytes and uses this function in its update procedure: $F(x)=((x \mathbin{<\!\!<\!\!<} 1) \oplus x \oplus (x \mathbin{>\!\!>\!\!>} 1)) \boxplus x$ (three chevrons means rotation). The updated state is calculated all at once (in parallel) like so:

$S[0]=F(S[3]) \boxplus S[4] \boxplus S[1] \boxplus F(S[2])$

$S[1]=F(S[4]) \boxplus S[0] \boxplus S[2] \boxplus F(S[3])$

$S[2]=F(S[0]) \boxplus S[1] \boxplus S[3] \boxplus F(S[4])$

$S[3]=F(S[1]) \boxplus S[2] \boxplus S[4] \boxplus F(S[0])$

$S[4]=F(S[2]) \boxplus S[3] \boxplus S[0] \boxplus F(S[1])$

If $S=[0, 1, 2, 3, 4]$, then after the update $S=[149, 155, 22, 138, 144]$. The output of any particular state is $S[0] \boxplus S[1] \boxplus S[2] \boxplus S[3] \boxplus S[4]$. What can I do to improve upon this design? How much better would clocking them be or using an accumulator be? (I know I shouldn't "roll my own", but I'm not planning on using this for secure purposes and I don't really care either.)

$\endgroup$
2
  • $\begingroup$ This construction puzzles me. Examine first the relation between the components of the State Register! $\endgroup$ Mar 19, 2015 at 8:29
  • $\begingroup$ Whys don't you simply use Salsa 20? $\endgroup$
    – user24706
    May 27, 2015 at 6:11

2 Answers 2

2
$\begingroup$

Have you actually tried coding this thing? It's not a PRNG, it's an oscillator.

I tried running it with various seed values, and every time it ended up in a loop of about $1000$ iterations.

If the initial seed is $(0, 1, 2, 3, 4)$, then the resulting loop has just $560$ iterations.

A five-byte seed is also way too small. Even if you do get it running properly, it will inevitably start repeating itself within $2^{40}$ iterations. This is far too low to be of any use cryptographically.

In addition, your algorithm is more computationally intensive than established methods like RC4 that are known to provide much better results.

$\endgroup$
4
  • $\begingroup$ What is the difference? $\endgroup$
    – Melab
    Mar 19, 2015 at 18:15
  • $\begingroup$ A pseudo-random number generator generates pseudo-random numbers. An oscillator does the same thing over and over again. What you've come up with belongs in the latter category. $\endgroup$
    – r3mainer
    Mar 19, 2015 at 18:42
  • $\begingroup$ That is true for any PRNG with a bounded state. $\endgroup$
    – Melab
    Jan 26, 2016 at 3:51
  • $\begingroup$ @Melab Yes, but something that repeats itself every 560 iterations is of very little use as a source of randomness. $\endgroup$
    – r3mainer
    Jan 26, 2016 at 11:23
-1
$\begingroup$

Use RSA instead? eg: generate an RSA keypair, and discard the private key, then encrypt your starting state. If you want to make it faster, manually input the bigmath instructions needed for encryption, unroll them, then manually optimise: you get the added benefit that the result looks just like a "normal" IV, except if you've kept the secret key, you can later quickly ascertain the starting state for any known-plaintext attack (eg: your PRNG is reversible by you, and only you, no matter how people using it seed the thing).

$\endgroup$

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.