Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This question is related to this one in intention, and this one in scope.

Would I be guarding myself against future attacks on a single PRNG if I combine two (or more) together?

I am thinking of using the Fortuna PRNG together with AES in counter mode, each initialised by a different source of entropy (now exactly what the two sources will be is an open problem). The output of each will be combined with the XOR operation, they will run on a separate thread and computational power is not a problem.

My (informal) thinking is that, as long as one function remains unpredictable (in polytime), the output is secure (in polytime).

The answers may address Fortuna or AES specifically, or they may treat the generators as abstract functions. Is there a flaw in this design?

share|improve this question
    
This will most likely only make specific attacks targetting the algorithms you use harder. Do make sure the two PRNGs are unrelated; then, it’s a sound scheme, but will not help much if one of the PRNGs’ output is not distributed well. –  mirabilos Dec 6 '13 at 12:08

1 Answer 1

up vote 2 down vote accepted

It should not be possible to attack this scheme itself. The XOR function will work like a one time pad, where the output of each PRNG can be either the plaintext stream or the key stream. So the output of the function should be random as long as one of the two streams can be thought to be a secure and well seeded PRNG.

In real life scenarios the main cause for concern is not the PRNG itself; the source of entropy (seeding) is much more of a concern. In this scheme entropy is exchanged for a more secure PRNG. It is questionable if this is worth the cause. Using the same entropy is for both PRNGs is not a good idea, it may open the scheme to attacks and will certainly invalidate any security proof.

Furthermore, synchronizing the streams generated by the threads may require large buffers which are effectively representing the state of your new PRNG. It is required to deal with thread synchronizing issues and overhead as well and it is important not to leak any state while doing any of this. It may be easier to put the two functions in the same thread to maintain a small state.

In conclusion, I don't think there are theoretical issues with your scheme, but I don't see how it would be a practical scheme. Most importantly it seems to solve an issue that is not really present. You trade entropy and speed for a more secure PRNG, which is not likely to be a cause of concern in the first place.

Note that I don't see how the results of Boneh and all apply to the new PRNG. Their results are used when multiple hash functions are used on the same data, possibly using XOR. I don't see how it would apply on generating a key stream. That said, it is questionable if any attacks on the underlying hash function translate to the PRNG anyway.

You are likely better off using the additional entropy to reseed more often.

share|improve this answer
    
It may even be that entropy sources need to generate completely non-related bits for any security proof to be valid. That could be hard to prove. On the other hand, it may not be as big a problem as I would expect. If anybody has anything to add to that part I would be grateful. –  owlstead Aug 3 '13 at 12:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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