Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cracking Random Number Generators Using Machine Learning

research.nccgroup.com

Post reply on HN
Print view View original

11–20 of 100 posts

Re: Cracking Random Number Generators Using Machine Learning

#11

Post by cblconfederate »

CodesInChaos wrote: post #8
cblconfederate wrote: post #2

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 ?

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 could…

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?

Re: Cracking Random Number Generators Using Machine Learning

#12

Post by cblconfederate »

saithound wrote: post #10
cblconfederate wrote: post #6

Earlier quoted context omitted.

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?

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, an…

but ANNs are universal approximators, they dont care if a function is recursive or anything as long as it's deterministic

Re: Cracking Random Number Generators Using Machine Learning

#13

Post by [deleted] »

adrian_b wrote: post #9
cblconfederate wrote: post #6

Earlier quoted context omitted.

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?

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 red…

[deleted]

Re: Cracking Random Number Generators Using Machine Learning

#14

Post by joshuaissac »

adrian_b wrote: post #9
cblconfederate wrote: post #6

Earlier quoted context omitted.

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?

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 red…

There are CSPRNGs like Fortuna that contain an entropy accumulator, so even if the secret part of the state is compromised, it can recover.

Re: Cracking Random Number Generators Using Machine Learning

#15

Post by _hl_ »

cblconfederate wrote: post #11
CodesInChaos wrote: post #8

Earlier quoted context omitted.

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 could…

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?

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.

Re: Cracking Random Number Generators Using Machine Learning

#16

Post by MauranKilom »

cblconfederate wrote: post #11
CodesInChaos wrote: post #8

Earlier quoted context omitted.

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 could…

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?

> I mean a theoretically absurdly large/wide network can approximate almost any function

Yes. But chances are that the network size scales exponentially with the number of e.g. input bits. Good luck building/training/storing a model with 2^128 neurons in the hidden layer.

Post reply on HN