5 ms·

Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. - John von Neumann The very definition of a pseudo-rand

by cdumler 13y ago

Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. - John von Neumann The very definition of a pseudo-random number generator is that it's deterministic, i.e. an algorithm. If you know in what the state of the algorithm is, you know what the next number will be. Attempting to add some ad hoc behavior on top of crypto has two common issues: First, adding of deterministic behavior to deterministic behavior does not in any way spontaneously add randomness (see quote). In fact, it can expose additional state on which an attack can be focused. For instance, perhaps when I learn that the system you are using is an interleaved set of numbers, I can use the starting set from each to guess the seed on which all PRNGs started. Second, crypto PRNGs that are well vetted are already at the top of the game for being apparently random in output. There shouldn't be a need to do anything like what you're suggesting, ever, with a valid PRNG. What Schneier is pointing out is that good crypt doesn't have a whiff of smell. Dual_EC_DRBG does. And, badly. Just use the others, instead. Importantly, learn the first rule of crypto: Unless you're well versed in crypto, presume you will do a very bad job of trying to implement something yourself. Understand for what the crypto library is meant to be used, understand how to use it properly, and don't try to do something on your own. It is hard for even the experts to do it well. Some simple "why don't I just.." is practically guaranteed to have a flaw. Adding your own deterministic behavior is a sin.

malandrew 13y ago
How about using a stream of true random numbers and putting it through a set of deterministic functions that "multiply" the quantity of random numbers. e.g. make thousands upon thousands of functions, where the function names are sequential. Use the data itself to determine which of the functions will be called. Allow functions to call each other based on the random number values it calculates from its true random input. To figure out how much random data to produce, simply add an extra bit that is passed along to all the functions that indicates depth (how much show the true random data be processed before returning it to the program that needs a random number). This approach would produce a lot more random data that could only be determined if you knew the original true random data input and the amount of entropy that was required at the time since you'd need to know the depth used to know when to exit the functions.
- contingencies 13y ago
  Err, I think you'll find what you described is roughly the definition of a PRNG (though usually more mathematical in its verbiage). The problem is, we don't trust any particular PRNG. My question was, why not combine them so as to remove the need for absolute trust in any given PRNG.
  - cdumler 13y ago
    When part of your system becomes flawed (part or whole), the whole can be attacked. Thus, adding more deterministic behavior doesn't add more randomness (i.e. more safety). Generally, when crypto falls down, it falls somewhat gracefully (i.e. there are a class of known attacks under certain particular situations.) As Crypto is an on-going war between those creating the security and those trying to break it, expect to have to change your crypto over time.
    - contingencies 13y ago
      > When part of your system becomes flawed (part or whole), the whole can be attacked. This is the most concise and meaningful argument against the proposed approach thus far. Hats off.
  - malandrew 13y ago
    I really need to get up to speed on cryptography. I've been a software developer for a while but haven't had a chance to get into it. Part of the reason is time, the other reason is that I haven't a clue where to start. I've heard about the books Security Engineering and Cryptography Engineering. Are they good books for someone new to all this?
    - enoch_r 13y ago
      I'd recommend the Coursera crypto course: https://www.coursera.org/course/crypto https://www.coursera.org/course/crypto
contingencies 13y ago
shouldn't be a need to do anything like what you're suggesting, ever, with a valid PRNG OK, but the point was that if we approach PRNGs like any other element of a secure system, ie. without trust, as the article was suggesting, then combining them in some way may assist with QA on the overall output. (Example: I mean, we don't trust the NSA - but do we trust Schneier? He could be paid handsomely by the NSA as a false stooge and EFF board plant, who are we to know? And if you're an overseas government without a native cryptographic/cryptanalytic tradition, would you trust him? He's a US citizen connected to BT - that's UKUSA - two of the 'five eyes'!) Similar to how multiple hashing algorithms are often used to preserve overall functional integrity in the case of individual hash function vulnerabilities that enable an attacker to propose collisions.
- cdumler 13y ago
  The difference is between a PRNG and encryption. Encryption's design is to obscure the data stream; thus, if there is a failure in an encryption it is masked by another encryption. Personally, I do not think this is a particularly useful activity. Public vetted encryption rarely spontaneously falls over. A modern encryption, like AES256, is well beyond the far future in computing requirements to brute force. It's better to be aware of changes over time and switch to a current crypto if things change, like how 3DES died. PRNG, on the other hand, is a string of numbers. They don't obscure anything. Either A) you don't try to obscure, and part of your numbers are weak anyways and need to be replaced or B) you're attempting to write your own crypto and you're going to do it badly. Using PRNG to obscure another one is a sin, you're trying to write encryption. (Sin being "to miss the mark" or point.)
  - contingencies 13y ago
    The similarity was drawn to hashing algorithms (which function to produce a message digest or checksum given a message as input), not to cipher algorithms (which perform encryption to ciphertext given one or more keys and a plaintext as input). A lot of people have responded suggesting there is no way to combine PRNGs to offset the risk of a single PRNG's potential compromise, however I have not seen any citations to this effect and it does really make logical sense to me. Arguments tend to fall back to table-thumping on mathematical proofs, which is a demonstrably naieve way of building a secure system if, for example, your mathematical process, computational platform or side-channel security assumptions are outmoded by an attacker.

by cdumler 13y ago

malandrew 13y ago

How about using a stream of true random numbers and putting it through a set of deterministic functions that "multiply" the quantity of random numbers. e.g. make thousands upon thousands of functions, where the function names are sequential. Use the data itself to determine which of the functions will be called. Allow functions to call each other based on the random number values it calculates from its true random input. To figure out how much random data to produce, simply add an extra bit that is passed along to all the functions that indicates depth (how much show the true random data be processed before returning it to the program that needs a random number). This approach would produce a lot more random data that could only be determined if you knew the original true random data input and the amount of entropy that was required at the time since you'd need to know the depth used to know when to exit the functions.

contingencies 13y ago
Err, I think you'll find what you described is roughly the definition of a PRNG (though usually more mathematical in its verbiage). The problem is, we don't trust any particular PRNG. My question was, why not combine them so as to remove the need for absolute trust in any given PRNG.
- cdumler 13y ago
  When part of your system becomes flawed (part or whole), the whole can be attacked. Thus, adding more deterministic behavior doesn't add more randomness (i.e. more safety). Generally, when crypto falls down, it falls somewhat gracefully (i.e. there are a class of known attacks under certain particular situations.) As Crypto is an on-going war between those creating the security and those trying to break it, expect to have to change your crypto over time.
  - contingencies 13y ago
    > When part of your system becomes flawed (part or whole), the whole can be attacked. This is the most concise and meaningful argument against the proposed approach thus far. Hats off.
- malandrew 13y ago
  I really need to get up to speed on cryptography. I've been a software developer for a while but haven't had a chance to get into it. Part of the reason is time, the other reason is that I haven't a clue where to start. I've heard about the books Security Engineering and Cryptography Engineering. Are they good books for someone new to all this?
  - enoch_r 13y ago
    I'd recommend the Coursera crypto course: https://www.coursera.org/course/crypto https://www.coursera.org/course/crypto

contingencies 13y ago

shouldn't be a need to do anything like what you're suggesting, ever, with a valid PRNG OK, but the point was that if we approach PRNGs like any other element of a secure system, ie. without trust, as the article was suggesting, then combining them in some way may assist with QA on the overall output. (Example: I mean, we don't trust the NSA - but do we trust Schneier? He could be paid handsomely by the NSA as a false stooge and EFF board plant, who are we to know? And if you're an overseas government without a native cryptographic/cryptanalytic tradition, would you trust him? He's a US citizen connected to BT - that's UKUSA - two of the 'five eyes'!) Similar to how multiple hashing algorithms are often used to preserve overall functional integrity in the case of individual hash function vulnerabilities that enable an attacker to propose collisions.

cdumler 13y ago
The difference is between a PRNG and encryption. Encryption's design is to obscure the data stream; thus, if there is a failure in an encryption it is masked by another encryption. Personally, I do not think this is a particularly useful activity. Public vetted encryption rarely spontaneously falls over. A modern encryption, like AES256, is well beyond the far future in computing requirements to brute force. It's better to be aware of changes over time and switch to a current crypto if things change, like how 3DES died. PRNG, on the other hand, is a string of numbers. They don't obscure anything. Either A) you don't try to obscure, and part of your numbers are weak anyways and need to be replaced or B) you're attempting to write your own crypto and you're going to do it badly. Using PRNG to obscure another one is a sin, you're trying to write encryption. (Sin being "to miss the mark" or point.)
- contingencies 13y ago
  The similarity was drawn to hashing algorithms (which function to produce a message digest or checksum given a message as input), not to cipher algorithms (which perform encryption to ciphertext given one or more keys and a plaintext as input). A lot of people have responded suggesting there is no way to combine PRNGs to offset the risk of a single PRNG's potential compromise, however I have not seen any citations to this effect and it does really make logical sense to me. Arguments tend to fall back to table-thumping on mathematical proofs, which is a demonstrably naieve way of building a secure system if, for example, your mathematical process, computational platform or side-channel security assumptions are outmoded by an attacker.