5 ms·

If you pull data from most OS-level RNGs (e.g. /dev/random on a Linux box), this is basically what you're getting. A bunch of hardware timing data, some of whic

If you pull data from most OS-level RNGs (e.g. /dev/random on a Linux box), this is basically what you're getting. A bunch of hardware timing data, some of which may be at least partially predictable or observable, is passed through a hashing algorithm. If the hashing algorithm is good, and an attacker is missing some reasonable chunk of the data that went into it, you're getting secure random numbers.

contingencies 13y ago
Thanks, that's almost exactly what I was looking for. However, it doesn't answer the question which is "can't we avoid that one big assumption" (ie. if the hashing algorithm is good) by combining them?
- nknighthb 13y ago
  Ultimately the answer is no, because your question is predicated on a nonexistent distinction. A combination of algorithms is simply a new, more complex algorithm. It may be an obvious and safe algorithm that enhances security, like Truecrypt's option of an AES/Twofish/Serpent cascade, or it may be a totally worthless algorithm -- like if you created a new "hashing" algorithm that consisted of CRC32 followed by SHA256. As that second example demonstrates, the naïve way of combining hashing algorithms is obviously not safe. If you simply layer them, any one of them could destroy entropy by producing biased/predictable results. Your new algorithm is crippled. If you try to "mix" them in some other way, all you've done is create a new hashing algorithm and fed it the output of other hashing algorithms. It's perhaps less likely that any one of those sub-algorithms will seriously cripple your system, but it's much more likely that you've made a mistake, and your new algorithm itself produces poor results. Somewhere along the way, you end up trusting something, even if it's your own algorithm. But since trusting yourself to get crypto right is a bad idea, the next best thing is to trust a well-vetted hashing algorithm, of which there are several that are likely "good enough", and aren't even NSA designed. If you're super-paranoid about backdoors, RIPEMD-160 might be your best bet -- it's a product of European academia. It gets some use, but not as much cryptanalysis as the SHA family has.
  - contingencies 13y ago
    your question is predicated on a nonexistent distinction. A combination of algorithms is simply a new, more complex algorithm. That's true if you combine multiple algorithms conventionally, for example by feeding inputs from one to the other or by passing the original entropy to the two algorithms in parallel. However, if you run one algorithm independently of another - with completely different entropy sources - then flip between supplying the output of each in rapid succession, then on the face of it for ~50% overheads you have probably mostly mitigated exploitable vulnerabilities in either of the two single PRNGs for most applications. (Optionally add another for more security, and take it a step further...) You are right that this would need to be done carefully .. perhaps the flip in which PRNG is used for the output stream occurs at hard-to-predict points in time (the range of periods for which, potentially, might be carefully chosen from a range that takes in to account some other cryptographically relevant factors ... from a complete non-cryptographer like me, this might include things like entropy draw size by typical applications (optimizing for multiple PRNGs over a typical application draw), the length of any feedback register or calibration cycle of individual cryptographic client algorithms, etc. Generally this would mean 'pretty frequently but not so frequently that it's predictably useful' - something of a paradox, true.) In short, I still think this approach may have some merit.
    - nknighthb 13y ago
      > That's true if you combine multiple algorithms conventionally What I said is true no matter how you combine them, including in the manner you propose. > flip between supplying the output of each in rapid succession You've just exposed yourself to a possible related-key attack. Also, the effective entropy of your key could be halved simply by one of the PRNGs being compromised, so even absent a related-key attack, you'd better be using an encryption algorithm with a big key size. (BTW, it's 100% overhead, not 50% overhead.) (Oh, and if both algorithms happen to be compromised, the results are or might as well be 0-entropy. Yet again, somewhere along the way you end up trusting something.) > perhaps the flip in which PRNG is used for the output stream occurs at hard-to-predict points in time "Hard-to-predict" requires a secure random number generator. You've gone on to describe yet another ad-hoc random number generator that you would use in the construction of your random number generator. Cryptography is hard.
- nhaehnle 13y ago
  Running different pseudo-random generators in parallel and then XORing their results should have the property that if at least one of the input algorithms is "good", then the output algorithm is "good". My intuition is based on the fact that this statement is correct for true random sources: If you take a bunch of random sources that generate streams of bits, then XORing those streams together will result in a stream of uniform and independent random bits if at least one of the source streams is a stream of uniform and independent random bits (this is an elementary argument in probability). I'm not certain at the moment whether this generalizes to pseudo-random generators, but it seems plausible enough to expect that the XORed bit stream is at least as "good" in terms of pseudo-randomness as the best of the input streams. Edit: Okay, I just realized that this is obviously false when the input streams themselves are correlated. For example, suppose that one of the input streams is PRNG A, and the other input stream is simply the negation of the output of PRNG A with the same seed. Then the output stream will consist of all 0s, which is not good. Perhaps some result can be salvaged when the seeds of the different PRNGs come from independent, truly random sources, but this means things get very tricky very quickly.
  - contingencies 13y ago
    Right, I came to the same realization. You'd need to make sure the input stream(s) (ie. entropy source(s)) to the PRNGs in question were not shared. Even if that was impractical, and this is pure conjecture from someone who is not a mathematician or cryptographer, then at the very least they should be well obfuscated, eg. unpredictably delayed throughout a large enough temporal keyspace with a not insignificant degree of feedback, or with large initial random seeds. But I'm not a cryptographer, so that's all baseless assertion. IMHO the notion stands, though.
    - eru 13y ago
      XORing multiple sources throws away lots of useful entropy. There are better approaches available, and they are used. Edit: nhaehnle, I can't reply to your comment (yet) because it's too deeply nested. I don't know the direct answer, but if you want to do some research yourself, you could do worse then reading this relevant Wikipedia article (https://en.wikipedia.org/wiki/Randomness_extractor https://en.wikipedia.org/wiki/Randomness_extractor) and following the links. They don't talk about provable extractors in the article itself, but you can probably identify at least the right terms you need to search for on arxive or so.

contingencies 13y ago

Thanks, that's almost exactly what I was looking for. However, it doesn't answer the question which is "can't we avoid that one big assumption" (ie. if the hashing algorithm is good) by combining them?

nknighthb 13y ago
Ultimately the answer is no, because your question is predicated on a nonexistent distinction. A combination of algorithms is simply a new, more complex algorithm. It may be an obvious and safe algorithm that enhances security, like Truecrypt's option of an AES/Twofish/Serpent cascade, or it may be a totally worthless algorithm -- like if you created a new "hashing" algorithm that consisted of CRC32 followed by SHA256. As that second example demonstrates, the naïve way of combining hashing algorithms is obviously not safe. If you simply layer them, any one of them could destroy entropy by producing biased/predictable results. Your new algorithm is crippled. If you try to "mix" them in some other way, all you've done is create a new hashing algorithm and fed it the output of other hashing algorithms. It's perhaps less likely that any one of those sub-algorithms will seriously cripple your system, but it's much more likely that you've made a mistake, and your new algorithm itself produces poor results. Somewhere along the way, you end up trusting something, even if it's your own algorithm. But since trusting yourself to get crypto right is a bad idea, the next best thing is to trust a well-vetted hashing algorithm, of which there are several that are likely "good enough", and aren't even NSA designed. If you're super-paranoid about backdoors, RIPEMD-160 might be your best bet -- it's a product of European academia. It gets some use, but not as much cryptanalysis as the SHA family has.
- contingencies 13y ago
  your question is predicated on a nonexistent distinction. A combination of algorithms is simply a new, more complex algorithm. That's true if you combine multiple algorithms conventionally, for example by feeding inputs from one to the other or by passing the original entropy to the two algorithms in parallel. However, if you run one algorithm independently of another - with completely different entropy sources - then flip between supplying the output of each in rapid succession, then on the face of it for ~50% overheads you have probably mostly mitigated exploitable vulnerabilities in either of the two single PRNGs for most applications. (Optionally add another for more security, and take it a step further...) You are right that this would need to be done carefully .. perhaps the flip in which PRNG is used for the output stream occurs at hard-to-predict points in time (the range of periods for which, potentially, might be carefully chosen from a range that takes in to account some other cryptographically relevant factors ... from a complete non-cryptographer like me, this might include things like entropy draw size by typical applications (optimizing for multiple PRNGs over a typical application draw), the length of any feedback register or calibration cycle of individual cryptographic client algorithms, etc. Generally this would mean 'pretty frequently but not so frequently that it's predictably useful' - something of a paradox, true.) In short, I still think this approach may have some merit.
  - nknighthb 13y ago
    > That's true if you combine multiple algorithms conventionally What I said is true no matter how you combine them, including in the manner you propose. > flip between supplying the output of each in rapid succession You've just exposed yourself to a possible related-key attack. Also, the effective entropy of your key could be halved simply by one of the PRNGs being compromised, so even absent a related-key attack, you'd better be using an encryption algorithm with a big key size. (BTW, it's 100% overhead, not 50% overhead.) (Oh, and if both algorithms happen to be compromised, the results are or might as well be 0-entropy. Yet again, somewhere along the way you end up trusting something.) > perhaps the flip in which PRNG is used for the output stream occurs at hard-to-predict points in time "Hard-to-predict" requires a secure random number generator. You've gone on to describe yet another ad-hoc random number generator that you would use in the construction of your random number generator. Cryptography is hard.
nhaehnle 13y ago
Running different pseudo-random generators in parallel and then XORing their results should have the property that if at least one of the input algorithms is "good", then the output algorithm is "good". My intuition is based on the fact that this statement is correct for true random sources: If you take a bunch of random sources that generate streams of bits, then XORing those streams together will result in a stream of uniform and independent random bits if at least one of the source streams is a stream of uniform and independent random bits (this is an elementary argument in probability). I'm not certain at the moment whether this generalizes to pseudo-random generators, but it seems plausible enough to expect that the XORed bit stream is at least as "good" in terms of pseudo-randomness as the best of the input streams. Edit: Okay, I just realized that this is obviously false when the input streams themselves are correlated. For example, suppose that one of the input streams is PRNG A, and the other input stream is simply the negation of the output of PRNG A with the same seed. Then the output stream will consist of all 0s, which is not good. Perhaps some result can be salvaged when the seeds of the different PRNGs come from independent, truly random sources, but this means things get very tricky very quickly.
- contingencies 13y ago
  Right, I came to the same realization. You'd need to make sure the input stream(s) (ie. entropy source(s)) to the PRNGs in question were not shared. Even if that was impractical, and this is pure conjecture from someone who is not a mathematician or cryptographer, then at the very least they should be well obfuscated, eg. unpredictably delayed throughout a large enough temporal keyspace with a not insignificant degree of feedback, or with large initial random seeds. But I'm not a cryptographer, so that's all baseless assertion. IMHO the notion stands, though.
  - eru 13y ago
    XORing multiple sources throws away lots of useful entropy. There are better approaches available, and they are used. Edit: nhaehnle, I can't reply to your comment (yet) because it's too deeply nested. I don't know the direct answer, but if you want to do some research yourself, you could do worse then reading this relevant Wikipedia article (https://en.wikipedia.org/wiki/Randomness_extractor https://en.wikipedia.org/wiki/Randomness_extractor) and following the links. They don't talk about provable extractors in the article itself, but you can probably identify at least the right terms you need to search for on arxive or so.