1
$\begingroup$

When I was in grad school, I invented (discovered?) a new PRNG algorithm. This algorithm has an infinite period length (given infinite memory). This in itself cannot be new, because all you need to do to accomplish this is simply take digits from an irrational number. What does make this different, is that it is able to use any size of key. 1 bit, 1 GB, whatever.

The next logical step for me was to turn this into a symmetric key algorithm. simply by generating the bits based off of the seed, and XORing the source file bits with the resulting output.

I am in the middle of developing this into an Android app. My problem is that 100% of my experience has been academic. I know that this algorithm (Binary Lagged Fibonacci) is valuable academically, but does it have a practical value? Does the flexible key size alone give it a benefit over, say, AES?

I have sent some emails out to a few companies, and I am trying to find out why no one has responded at all. My best guess is that 1. they get 1000 crackpots emailing them every day. Or 2. I sound like I have no idea what I am talking about. The second one is definitely true. I just learned the other day I need to be salting the seed when it gets passed.

$\endgroup$
  • 2
    $\begingroup$ Variable key-sizes aren't all that useful in practice where you'd use KBKDFs, PBKDFs and hashes to get down to supported and secure-enough sizes. $\endgroup$ – SEJPM Nov 28 '16 at 20:53
  • 3
    $\begingroup$ Related: How to submit a new method of encryption? $\endgroup$ – CodesInChaos Nov 28 '16 at 21:50
  • 1
    $\begingroup$ If you supply for example, a 512-bit key, can you prove that your algorithm provides 512-bits of security against all known attacks? $\endgroup$ – Richie Frame Nov 29 '16 at 2:13
  • 1
    $\begingroup$ Or, for that matter, any security at all? $\endgroup$ – poncho Nov 29 '16 at 2:43
  • 2
    $\begingroup$ "Binary Lagged Fibonacci"; Knuth (volume 2, section 3.2.2) references some lagged fibonacci generators dating back to the 50s. If what you have is a minor variant of what was invented almost 60 years ago, it's not clear if it's of any academic interest (and those wouldn't certainly not be of any cryptographical interest) $\endgroup$ – poncho Nov 29 '16 at 4:53
8
$\begingroup$

Without a proof of security or proper cryptanalysis including an argument why it covers all currently known methods:

The value (in the context of cryptography) is zero.

This might sound harsh, but you brought up the main reason yourself: It is basically impossible to design a new secure cryptosystem without the proper knowledge of the field, but amateurs are convinced otherwise and keep on trying. The only solution here is to write a publication in some peer-reviewed context (e.g. crypto conferences). Regarding your experience, it is not clear from your question, because you wrote:

My problem is that 100% of my experience has been academic

Or 2. I sound like I have no idea what I am talking about. The second one is definitely true


Regarding your algorithm:

A lagged Fibonacci generator is a well known construction. It is an improvement over the linear congruential generator, and is related to similar concepts like LFSR, Mersenne Twister, etc.. But that doesn't say much: Those are not cryptographically secure random number generators, and they have no security at all (from today's point of view). So it's quite reasonable, this is also true for your algorithm.

Considering an infinite period: A large period is required for a proper CSPRNG, but it is not sufficient. A well-known counter example is linear-feedback shift registers, which have large periods and were used for stream ciphers in the past. But they are quite easy to break.

Also irrational numbers might offer an infinite period of numbers, but that doesn't mean they are unpredictable or you can't get the seed back from the sequence. I am not aware of any computationally hard problem regarding irrational numbers.

$\endgroup$
  • $\begingroup$ lagged fibonacci generators create a 3 point correlation between bytes, which is the basis of the attacks against them. $\endgroup$ – Jacob Levinson Dec 4 '16 at 15:53
  • $\begingroup$ Knowing that lagged fibonacci is the algotithm, means the seed can be guessed through simple brute force. Additionally, the period size of lagged fibonacci generators is quite small. My algorithm is loosely based on lagged fibonacci generators, but without these deficiencies. As for a proof of security, how do I prove a negative? I ran the PRNG through the diehard test suite, and it passed. An earlier version was vulnerable to known-plaintext attacks, but that is fixed. $\endgroup$ – Jacob Levinson Dec 4 '16 at 16:00
  • $\begingroup$ From what I gather, it is not cryptographically secure if there is a faster than brute force method of guessing the seed. I have been theorising that perhaps someone can know whether there is an odd or even number of '1' bits in the seed if the sourcefile is known, but this can be eliminated. I just need to slightly adjust how the seed is created. It sounds like the best route is to have it published. That way, it can be attacked, or, perhaps it will be shown to have value due to its infinite period in monte carlo simulations like how the merzenne twister algorithm is used. $\endgroup$ – Jacob Levinson Dec 4 '16 at 16:33
  • $\begingroup$ The professors at my school all saw value in it, but obviously they are not industry experts either. We then sent the algorithm to the university of Iowa, and they pretty much said that it had academic value, but had no value as a patent because for a patent, the algorithm needs to be described in full, additionally, it being a private key algorithm means that the generated bits should be as completely without pattern as possible. All of that means that if someone were to steal it, I would have no way of knowing. I also realized later, that AES is free, and already works fine. $\endgroup$ – Jacob Levinson Dec 4 '16 at 16:49
  • $\begingroup$ @JacobLevinson "As for a proof of security, how do I prove a negative? I ran the PRNG through the diehard test suite, and it passed." Read the initial propoosals for the AES competition, and how they argue about the security there. Statistical tests like the diehard tests are necessary but not sufficient - if something fails those it can not be secure, but passing them does not mean much at all. $\endgroup$ – tylo Dec 5 '16 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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