4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – mirabilos
    Dec 6, 2013 at 12:08
  • $\begingroup$ For what it's worth, combining multiple sources of (potentially-questionable) entropy is exactly what Fortuna is designed to do. $\endgroup$
    – Stephen Touset
    Oct 23, 2014 at 19:29
  • 1
    $\begingroup$ I am using a similar system, CTR mode XOR with the OS PRNG, which is then hashed. This guarantees minimum entropy per output bit (7 bits of input to hash for 1 bit out), as well as maintaining security with a potentially malicious CryptGenRandom/RDRAND $\endgroup$
    – Richie Frame
    Oct 24, 2014 at 0:04

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Aug 3, 2013 at 12:30
  • $\begingroup$ Concerning practical use: Imagine your OS PRNG works just like Debian OpenSSL 2006-2008. Wouldn't you recommend to add some own stuff in order to counter this? $\endgroup$
    – maaartinus
    Oct 27, 2014 at 3:21
  • $\begingroup$ @maaartinus That particular issue would be avoided by adding real entropy to the stream as well. But I agree, it could also be avoided by mixing in a PRNG that was seeded with such entropy. Theoretically speaking, the PRNG wasn't the issue. $\endgroup$
    – Maarten Bodewes ♦
    Oct 27, 2014 at 8:45
  • $\begingroup$ Agreed, but there could be something else broken with the OS PRNG (what could block my attempts to add entropy), so I'd prefer to combine it with my own (even if my own seeding was far from perfect; still better than 2**15). $\endgroup$
    – maaartinus
    Oct 28, 2014 at 0:00
0
$\begingroup$

I understand your question to be related with stream encoding by XORing a source using the bytes emitted from two by XORed PRNG. (By the way, you don't need to combine them before XOR the source - the result remains the same, if you XOR the source by bytes from both PRNGs in the same sequence.) I guess, you want to be able to decipher the result back to the source.

Thus you will use a symmetric key to seed for encoding / decoding. And in practice you will use the same key (or keys deriving from the same source, i.e hash(key)/reverse(hash key) or hash(key)/ (other-)hash(hash(key))..) for both PRNGs.

Using two PRNGs will have the effect, that an attacker even knowing one PRNG+key will not be able to decode the cypher. But your primary concern will be the key secret anyway if the keys derive from the same source(see above).

Good PRNGs are designed to produce equally distributed byte streams (baskets 0:255). The distribution pattern might be broken by your approach. Breaking the distribution might or might not be a problem (i.e. think text-encoding vs. steganography).

Using two PRNGs (or one with two different seeds) with a lower risk of changing distribution patterns can be accomplished by toggling the byteStream between two PRNGs like x[0] ^prng-1 , x[1] ^prng-2, x[2] ^prng-1 …

The latter design would furthermore prevent performance losses. On the other hand, a scheme should not been used on clear text / images … better use it with compressed/encapsulated or otherwise obscured sources to prevent guessing from a half decoded cipher fragment (one prng-seed combination known by the attacker).

Improve this answer
$\endgroup$
6
  • $\begingroup$ Good PRNGs are designed to produce bitstreams that are indistinguishable from random, a large byte stream that has near equal frequencies for each byte is NOT what random behaves like $\endgroup$
    – Richie Frame
    Oct 23, 2014 at 19:18
  • $\begingroup$ @RichieFrame Reading bits to bytes from a (PRNG) random bitstream produces random bytes that are (near) equally distributed (see also: NIST statistic package csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html). $\endgroup$
    – ABri
    Oct 23, 2014 at 20:44
  • $\begingroup$ Only with an extremely large output sample (half a megabyte+), as compared to a large cryptographic key output which is 4096 bits or smaller in general, which should never see an even byte distribution.CTR is already good at producing statistically pseudorandom outputs, so it should not effect the bite/byte distribution of a good PRNG in a negative way. I think you may have misunderstood the OP in regards to the purpose; he will not be using the output to encrypt plaintext, rather to generate key material $\endgroup$
    – Richie Frame
    Oct 23, 2014 at 23:58
  • $\begingroup$ Your first comment cited 'a large byte stream that has near equal frequencies for each byte is NOT what random behaves like'. Now you are talking about distribution assessment in small streams (i.e. from hash algorithms). Anyway, PRNGs should deliver equally distributed bits/bytes assessable on the long run. And even (cryptographic save) hash one way functions do so if using them to produce larger sequences as can be shown by analyzing iterative produced bitstreams (hash(hash(hash(..))). $\endgroup$
    – ABri
    Oct 24, 2014 at 5:40
  • $\begingroup$ size is relative, 4096 bits is large for a cryptographic key, but very small for a lot of other reasons. A cryptographic key with equal distribution of bytes would look like a nonrandom permutation, but in the long run (megabytes) yes, a PRNG should have a near even byte distribution. $\endgroup$
    – Richie Frame
    Oct 25, 2014 at 2:15

Your Answer

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

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