4 ms·

ANNs are function approximators so it s trivial for them to learn a mathematical function like a prng. The seed is irrelevant to the ANN, it just learns the fun

ANNs are function approximators so it s trivial for them to learn a mathematical function like a prng. The seed is irrelevant to the ANN, it just learns the function's sequence, regardless of where it started. Which makes the interesting question how many people are already cracking PRNGs with ANNs ?

seanhunter 5y ago
I could see how they could learn to approximate the function if they could observe the internal state, but without being able to see the state, if it's a strong PRNG how would they be able to do it? Edit: Reading the paper they're approximating xorshift which as I understand it is fast and efficient but has very little internal state and is not a strong PRNG.
- cblconfederate 5y ago
  Would it be called pseudorandom if it had an undecipherable internal state such as temperature or sth? aren't all PRNGs deterministic functions by definition?
  - adrian_b 5y ago
    For some PRNGs it is intended that the output values must be unpredictable, e.g. for using in cryptographic applications. For such PRNGs, you can either view them as having a known state and an unknown output function or you can view them as having a known output function and a state composed of a known part and of an unknown, secret, part. The second point of view is more general, as the first case can always be reduced to the second, because the unknown output function must be derived using known functions from a secret key, so you can consider the secret key as the part of the state that is unknown. (There is a third possible structure for a PRNG, with known state, known output function and unknown transition function, but this is obsolete for making unpredictable PRNGs, as it has inferior properties). So yes, a pseudo RNG that has a part of its state that remains unknown may produce an output sequence from which it is computationally infeasible to determine its complete state. Nonetheless, an unpredictable PRNG remains a PRNG, not a true RNG. You can reproduce any time its output sequence if you know the secret part of the state, e.g. when you are the recipient of an encrypted message. If a ML method would be able to recover the secret part of the state when given the output sequence, obviously that PRNG would be considered broken. Many PRNGs are designed for high-speed in non-cryptographic applications, e.g. simulations, and for those PRNGs it is usually very easy to determine the internal state from the output sequence, without the need of any ML.
    - deleted 5y ago
      [deleted]
    - joshuaissac 5y ago
      There are CSPRNGs like Fortuna that contain an entropy accumulator, so even if the secret part of the state is compromised, it can recover.
      - adrian_b 5y ago
        True, but they belong to a different class, which are used for applications like key generation, where there is no need to ever reproduce a certain output sequence. Such RNGs are used instead of true RNGs, which might not be able to provide the required random numbers fast enough. They cannot be used instead of normal PRNGs in most of their applications. Unpredictable cryptographic PRNGs can be used instead of any other PRNG for simulations, games, MonteCarlo integration etc. and they are actually better than simpler predictable PRNGs, except that they might be too slow. On modern CPUs with hardware AES instructions, any of the traditional PRNGs that is not faster than computing AES, has become obsolete, as using AES with a counter would provide a random sequence with a higher quality.
        rurban 5y ago
        Wrong as we can see with x64's new rdrand which relies on a fast aesna, but is terribly broken.
  - saithound 5y ago
    Generally, PRNGs have an internal state, a transition function that determines a new internal state based on the current internal state, and an output function that determines the output value based on the current internal state. In most cases, the output is determined by the output function based on a small part of the state (e.g. you may have 128 bits of state, feed the first 64 bits of it to an output function, and derive a 32-bit output as a result). This means that you don't learn much about the internal state of the generator merely by looking at an output value: you need to observe a lot of consecutive outputs to recover the internal state of the generator, and without knowing the internal state it's difficult (i.e. very hard to impossible) to use a relatively small number of known outputs to predict the next output. The xorshift128 generator tested in the article has a nigh-trivial output function (because it's designed to be fast, not hard-to-predict) and a very simple transition function, which is why 4 outputs can be used to recover the internal state and to train a NN to predict the next output.
    - cblconfederate 5y ago
      but ANNs are universal approximators, they dont care if a function is recursive or anything as long as it's deterministic
      - saithound 5y ago
        The point is precisely that predicting the next output based on a number of known outputs is not deterministic. Predicting the next _internal state_ from the current _internal state_ is deterministic, but that doesn't help, since you don't have access to the internal state. Here's a simple random number generator. You start with a 16 bit number x, (your internal state). At each step you update your internal state to 75x + 74 (mod 65537), and output the first digit of your internal state (your random number) Here's a sequence of outputs: 6,5,3,3,3,5. Does this information allow you to predict the next output? No. For example, if the generator's starting state is x=60160, then the generator's internal state evolves as follows: [60160,55558,38093,38958,38296,54183,505]. So the seventh output will be 5. However, if your generator's starting state was instead x=6, then the generator's state evolved as follows: [6,524,39374,3959,34851,57956,21332]. So the seventh output will be 2. The releationship between the first six outputs and the seventh output is not deterministic.
visskiss 5y ago
Uhh yeah right.
- saithound 5y ago
  cblconfederate happens to be right in this specific case (although wrong about using neural nets for predicting PRNGs in general): the author uses four consecutive non-truncated outputs of the xorshift128 generator as the network input, and learn to predict the next output. Since four consecutive outputs expose the entire internal state of the xorshift128 generator, this amounts to little more than approximating a (very simple) four-variable function.
CodesInChaos 5y ago
1. For many functions ANNs will never converge to an approximation of that function given only (input, output) tuples, even if the function is simple enough that the ANN could represent it. Chaotic functions rarely have a useful gradient the NN can follow. 2. To break a PRF it'd need to learn its inverse. For many of them it's unlikely that a small circuit computing the inverse even exists, so a non-iterated NN couldn't even represent the desired function, let alone converge to it.
- cblconfederate 5y ago
  i dont know much about cryptography but why would it need to learn its inverse? I mean a theoretically absurdly large/wide network can approximate almost any function . Are PRFs resistant to that?
  - _hl_ 5y ago
    The underlying assumption of all of modern cryptography is that one-way functions exist (implying P != NP), and further that the algorithms we use in practice are actually instances of these theoretically hard problems. So there provably always exists an algorithm that breaks any given PRNG, it will just always take you very long to compute and/or a lot of queries to the PRNG. ANNs are nothing special in that regard, they are just algorithms and have the same theoretical lower bound on their runtime. So yes, an absurdly large ANN will break any PRNG, but so will other absurdly long-running algorithms, some of which are quite trivial: Just try every possible seed until you get the same sequence as what you observe, repeat until only one candidate seed is left. EDIT: To add to this, you seem to be referring to the universal approximation theorems for ANNs. These theorems state that for any function (subject to some conditions not relevant here) and any arbitrary approximation ratio, there exists a finite ANN that approximates the function to within the desired approximation ratio. It says nothing about whether it's possible to train such an ANN, merely that it exists. Which in this case is a fairly trivial results, you could feasibly create a look-up table of PRNG sequences to seeds and encode that as an enormous ANN. But finding/training this ANN is prohibitively expensive.
    - 5y ago
ChrisLomont 5y ago
They're already trivial to crack 100% with Z3. Using something fuzzy like a neural net is by far not an optimal way to break it.

seanhunter 5y ago

I could see how they could learn to approximate the function if they could observe the internal state, but without being able to see the state, if it's a strong PRNG how would they be able to do it? Edit: Reading the paper they're approximating xorshift which as I understand it is fast and efficient but has very little internal state and is not a strong PRNG.

cblconfederate 5y ago
Would it be called pseudorandom if it had an undecipherable internal state such as temperature or sth? aren't all PRNGs deterministic functions by definition?
- adrian_b 5y ago
  For some PRNGs it is intended that the output values must be unpredictable, e.g. for using in cryptographic applications. For such PRNGs, you can either view them as having a known state and an unknown output function or you can view them as having a known output function and a state composed of a known part and of an unknown, secret, part. The second point of view is more general, as the first case can always be reduced to the second, because the unknown output function must be derived using known functions from a secret key, so you can consider the secret key as the part of the state that is unknown. (There is a third possible structure for a PRNG, with known state, known output function and unknown transition function, but this is obsolete for making unpredictable PRNGs, as it has inferior properties). So yes, a pseudo RNG that has a part of its state that remains unknown may produce an output sequence from which it is computationally infeasible to determine its complete state. Nonetheless, an unpredictable PRNG remains a PRNG, not a true RNG. You can reproduce any time its output sequence if you know the secret part of the state, e.g. when you are the recipient of an encrypted message. If a ML method would be able to recover the secret part of the state when given the output sequence, obviously that PRNG would be considered broken. Many PRNGs are designed for high-speed in non-cryptographic applications, e.g. simulations, and for those PRNGs it is usually very easy to determine the internal state from the output sequence, without the need of any ML.
  - deleted 5y ago
    [deleted]
  - joshuaissac 5y ago
    There are CSPRNGs like Fortuna that contain an entropy accumulator, so even if the secret part of the state is compromised, it can recover.
    - adrian_b 5y ago
      True, but they belong to a different class, which are used for applications like key generation, where there is no need to ever reproduce a certain output sequence. Such RNGs are used instead of true RNGs, which might not be able to provide the required random numbers fast enough. They cannot be used instead of normal PRNGs in most of their applications. Unpredictable cryptographic PRNGs can be used instead of any other PRNG for simulations, games, MonteCarlo integration etc. and they are actually better than simpler predictable PRNGs, except that they might be too slow. On modern CPUs with hardware AES instructions, any of the traditional PRNGs that is not faster than computing AES, has become obsolete, as using AES with a counter would provide a random sequence with a higher quality.
      - rurban 5y ago
        Wrong as we can see with x64's new rdrand which relies on a fast aesna, but is terribly broken.
- saithound 5y ago
  Generally, PRNGs have an internal state, a transition function that determines a new internal state based on the current internal state, and an output function that determines the output value based on the current internal state. In most cases, the output is determined by the output function based on a small part of the state (e.g. you may have 128 bits of state, feed the first 64 bits of it to an output function, and derive a 32-bit output as a result). This means that you don't learn much about the internal state of the generator merely by looking at an output value: you need to observe a lot of consecutive outputs to recover the internal state of the generator, and without knowing the internal state it's difficult (i.e. very hard to impossible) to use a relatively small number of known outputs to predict the next output. The xorshift128 generator tested in the article has a nigh-trivial output function (because it's designed to be fast, not hard-to-predict) and a very simple transition function, which is why 4 outputs can be used to recover the internal state and to train a NN to predict the next output.
  - cblconfederate 5y ago
    but ANNs are universal approximators, they dont care if a function is recursive or anything as long as it's deterministic
    - saithound 5y ago
      The point is precisely that predicting the next output based on a number of known outputs is not deterministic. Predicting the next _internal state_ from the current _internal state_ is deterministic, but that doesn't help, since you don't have access to the internal state. Here's a simple random number generator. You start with a 16 bit number x, (your internal state). At each step you update your internal state to 75x + 74 (mod 65537), and output the first digit of your internal state (your random number) Here's a sequence of outputs: 6,5,3,3,3,5. Does this information allow you to predict the next output? No. For example, if the generator's starting state is x=60160, then the generator's internal state evolves as follows: [60160,55558,38093,38958,38296,54183,505]. So the seventh output will be 5. However, if your generator's starting state was instead x=6, then the generator's state evolved as follows: [6,524,39374,3959,34851,57956,21332]. So the seventh output will be 2. The releationship between the first six outputs and the seventh output is not deterministic.

visskiss 5y ago

Uhh yeah right.

saithound 5y ago
cblconfederate happens to be right in this specific case (although wrong about using neural nets for predicting PRNGs in general): the author uses four consecutive non-truncated outputs of the xorshift128 generator as the network input, and learn to predict the next output. Since four consecutive outputs expose the entire internal state of the xorshift128 generator, this amounts to little more than approximating a (very simple) four-variable function.

CodesInChaos 5y ago

1. For many functions ANNs will never converge to an approximation of that function given only (input, output) tuples, even if the function is simple enough that the ANN could represent it. Chaotic functions rarely have a useful gradient the NN can follow. 2. To break a PRF it'd need to learn its inverse. For many of them it's unlikely that a small circuit computing the inverse even exists, so a non-iterated NN couldn't even represent the desired function, let alone converge to it.

cblconfederate 5y ago
i dont know much about cryptography but why would it need to learn its inverse? I mean a theoretically absurdly large/wide network can approximate almost any function . Are PRFs resistant to that?
- _hl_ 5y ago
  The underlying assumption of all of modern cryptography is that one-way functions exist (implying P != NP), and further that the algorithms we use in practice are actually instances of these theoretically hard problems. So there provably always exists an algorithm that breaks any given PRNG, it will just always take you very long to compute and/or a lot of queries to the PRNG. ANNs are nothing special in that regard, they are just algorithms and have the same theoretical lower bound on their runtime. So yes, an absurdly large ANN will break any PRNG, but so will other absurdly long-running algorithms, some of which are quite trivial: Just try every possible seed until you get the same sequence as what you observe, repeat until only one candidate seed is left. EDIT: To add to this, you seem to be referring to the universal approximation theorems for ANNs. These theorems state that for any function (subject to some conditions not relevant here) and any arbitrary approximation ratio, there exists a finite ANN that approximates the function to within the desired approximation ratio. It says nothing about whether it's possible to train such an ANN, merely that it exists. Which in this case is a fairly trivial results, you could feasibly create a look-up table of PRNG sequences to seeds and encode that as an enormous ANN. But finding/training this ANN is prohibitively expensive.
  - 5y ago

ChrisLomont 5y ago

They're already trivial to crack 100% with Z3. Using something fuzzy like a neural net is by far not an optimal way to break it.