I read this https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d
and if the key is generated with an old browser using math.random via chrome v8, could the AES encrypted message be cracked just by trying all the combinations? This assumes you only have the output and not the computer.
this however suggests it cannot be done https://www.reddit.com/r/cryptography/comments/fw2cdu/can_you_retrieve_aes_key_that_was_generated_using/
Your question is a little unclear, so I'm going to interpret it as "if I generate a 256-bit key with a weak random number generator like Math.random(), can someone feasibly crack it?"
If the key was generated with a proper cryptographically secure pseudo-random number generator (CSPRNG), then the answer would absolutely be no. Using sheer brute-force, attacking even a 96-bit key is a significant undertaking that would require massive computing resources and take years to complete with today's resources. Every time you add one bit to the key length, you double the computational effort it takes to crack it with brute force.
So if these long keys are so strong, how could anyone even begin to crack them? The answer lies in the attack approach. If you use a brute-force approach, i.e. try every key in the key space until you find the right one, the attack will take a very long time even if the method used to generate the keys was flawed. However, if you leverage flaws in the key generation technique, you can massively accelerate the process.
Most standard libraries in programming languages include a function that generates random numbers. That function is designed to be used for things like guessing games, load distribution, and other non-security-related behaviours. Its goal is to give the appearance of randomness, and roughly even probabilities of any given output, while being as fast as possible.
The most common non-cryptographic RNG implementations are based on LFSRs, which take some internal state and combine parts of it to generate each new number, and LCGs, which uses modular arithmetic over some internal state to generate each new number. Perhaps the most well-known and widely used algorithm is Mersenne Twister, which uses a variant of the LFSR approach.
These PRNGs work by holding some internal state that is modified every time a new random number is generated. The initial state, before the first number is generated, is called the seed. If you run the algorithm twice, giving it the same seed each time, it'll generate the same sequence of random numbers twice. We call this a deterministic random number generator, or DRNG.
Obviously it is usually undesirable to have the same sequence of numbers generated every time you run the program. Most programming libraries that include a DRNG will automatically generate a seed from based on information from the environment that is likely to change, such as the process ID and the current time.
Consider what happens if an attacker knows the seed you used for your random number generator, or can reasonably guess the seed. The attacker can use that seed to generate exactly the same sequence of numbers that your program does, allowing them to know what numbers will come next.
In addition, since the sequence of numbers that will be generated by the DRNG is based on the DRNG's internal state, if the attacker can discover the internal state then they can also generate the same sequence of random numbers as your program will. These non-cryptographic DRNGs are not designed to prevent this from occurring. For many of them, you can discover the state, and therefore predict all future outputs, just by looking at known outputs from the DRNG.
But how does this apply to generating random keys? Well, let's consider the following code:
for (int i = 0; i < 32; i++)
{
key[i] = random(0, 255);
}
ciphertext = encrypt(message, key);
This code generates 32 numbers between 0 and 255 (inclusive), which is the equivalent of a 256-bit key. It then uses that to encrypt a message.
If we assume that I have no other information than the encrypted message and the program code, I don't know the value of the key, which means I don't know any outputs of the DRNG in order to recover the state. But what I do know is that the library that implements the random function picks its seed based on the current time as a 32-bit UNIX timestamp (i.e. number of milliseconds since midnight Jan 1st 1970). Instead of trying to crack that 256-bit key, I can try to crack the seed. This reduces my keyspace from 2256 to just 232, making it entirely feasible to break! Even worse, if I can take a reasonable guess at the time window in which the key might have been generated, I can reduce the keyspace even further. For example, if I know the key was generated on a particular day, that means there are only 24 * 60 * 60 * 1000 possible values for the seed, which is about 226. You can crack that in just a few seconds on a modern computer.
But the problem doesn't stop there. Imagine that, for some reason, you can't crack the seed value. If the internal state of the DRNG is small, for example under 64 bits, an attacker can just brute-force the state instead of the seed. This is far quicker than trying to brute-force a 128-bit or 256-bit key.
This problem is related to the pigeonhole principle. If your RNG can only be in one of 232 states, it doesn't matter how large the key it generates is - it can only generate 232 possible different keys.
Further, we can optimise this attack in a case where we can observe outputs from the DRNG. Imagine that the code above is running on a server, generating keys for users. A malicious user of the system can request a key. This provides them with 32 sequential outputs from the DRNG. Since the DRNG isn't designed to protect its internal state from being discovered using those outputs, the attacker may be able to use some clever maths to figure out the state, and predict every key that the code will generate in future. The exact requirements, such as how many numbers need to be observed, depend on the exact random number generator.
CSPRNGs solve this by making the system secure against recovering the RNG state from the outputs, ensuring that the outputs do not exhibit any patterns or biases that can be exploited via cryptanalysis, and ensuring that the seed is large and sufficiently unpredictable. The last part is often referred to as "entropy gathering", and it depends on how much unpredictable state that is accessible to the system. Modern platforms offer hardware random number generators, based on physically random processes in the silicon, to aid with this entropy problem.
As a practical demo, consider this C# program:
var victimRNG = new Random();
var key = victimRNG.Next();
var sw = new Stopwatch();
sw.Start();
Parallel.For(0, int.MaxValue, (i, state) =>
{
var attackerRandom = new Random(i);
if (attackerRandom.Next() == key)
{
Console.WriteLine("Cracked! Seed is {0}", i);
Console.WriteLine("Attacker RNG thinks the next output value will be {0}", attackerRandom.Next());
state.Stop();
}
});
sw.Stop();
Console.WriteLine("Victim RNG's next output is {0}", victimRNG.Next());
Console.WriteLine("Done in {0}", sw.Elapsed);
This program creates an RNG using the System.Random class, which is a non-cryptographic DRNG, that by default is seeded using the number of milliseconds since the computer was powered on. It then uses that DRNG to generate a key value. Then, it creates a new System.Random instance for every possible seed, and tries to find the seed that matches in order to discover it. Once the attack finds an RNG that generates a matching key, it prints the seed and what it thinks the next output will be. The victim RNG then prints what the real next output was, which should match if the attack was successful.
On a computer with lots of fast cores, this can be quite quick:
Cracked! Seed is 34182842
Attacker RNG thinks the next output value will be 133712629
Victim RNG's next output is 133712629
Done in 00:01:25.8381633
(the 1337 in the output is purely happy coincidence - you can verify this yourself with the seeds shown here!)
