Compute secure data randomly

Question

Random functions are not entirely random in computation. I wonder if there is a safe way to generate a salt, or any other random string safely, without using external hardware.

Can randomization be achieved without the use of external hardware, for example by using the time it takes for a process to be done? Isn’t that something that’s intrinsic to the quantum states of the processor materials? If not, theoretically, in the smallest computable unit of time by a computer, an exactly equal process is always calculated at the same speed.

Answer 1

Before directly answering your question, I would like to establish some parallels that will help in understanding the answer.

First, evaluate the sequences below and their corresponding formulas:

01010101010101010101010101   f(X) = NOT X
AAAAAAAAAAAAAAAAAAAAAAAAAA   f(X) = "A"
ABCDEFGHIJKLMNOPQRSTUVWXYZ   f(X) = CHAR(ASCII(X) + 1)

Without much work, we come to the conclusion that the predictability (or deterministic definition) of these sequences is very high - or, conversely, that entropy is very low.

But what is entropy? It is the measure of chaos in a system. The term was originally created to describe thermodynamic systems, but the concept is also applicable to other domains - data, for example.

When we talk about the generation of random or random content by computers, we are talking about formulas that generate values that have a distribution similar to that found in a system with high entropy and continuous uniform distribution.

An example of easy-to-see uniform continuous distribution is white noise, where the distribution is seemingly impossible to describe with a deterministic formula - but where we can use statistics to describe density. This is a white noise bitmap generated in Random.org:

For comparison, this is the bit map of PHP’s Rand() function as demonstrated by developer Bo Allen in a 2012 post on his personal blog entitled Pseudo-Random vs. True Random. Note how easily you detect the generation pattern:

While in nature systems lose order and gain entropy, the reverse occurs in data systems. Whenever you 'generate' random numbers, you are stealing the entropy system, and entering order.

As an example, let’s assume that I have the following random string of letters via the Random.org Random String Generator:

Chave
JPVPUUWWJAZEEUMLXDVT

Which I use in a simple encryption formula, where I 'add' the variation relative to the letter A of each position when applying to a letter of my payload at the same position.

Payload               Conteúdo encriptado
AAAAAAAAAAAAAAAAAAAA  JPVPUUWWJAZEEUMLXDVT
BBBBBBBBBBBBBBBBBBBB  KQWQVVXXKBAFFVNMYEWU

But note that if my payload is equal to or greater than the key, I will reset the system entropy. So, assume I concaten my key, for the following payload:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

My encrypted content would be:

JPVPUUWWJAZEEUMLXDVTJPVPUUWWJAZEEUMLXDVT
^^^                 ^^^

I can easily detect the repetition and predict the rest of the sequence.

From a safety point of view, safe random functions are those that periodically recharge with entropy, in order to prevent predictability.

You can recharge entropy in many ways; The best source of entropy is the real world. Some examples, which can be used in conjunction with a pseudo-random function in the form of Seeds (seeds):

• Access the trending Topics from Twitter. Take the last 128 tweets generated. Extract the day and time of each, convert to a byte array.
• Capture images from 2 or more public webcams around the world. Extract MD5 from all. Convert to one byte array.
• Let your cat walk on the keyboard. Convert the generated characters to a bytearray. (Add a hamster to the system for more data. Prevent the abandonment of the system’s scope with a box around the three.)

Each of these examples provides different sample size and rate. The more random source data you enter into a hybrid system with a connected pseudo-random generator, the smaller the pattern detection changes.

The answer, therefore, is nay: You need to import entropy from an external system.

Sources:

http://www.random.org/strings/? num=10&Len=10&upperalpha=on&unique=on&format=html&rnd=new

http://boallen.com/random-numbers.html

_{Edit-Disclaimer: Added, directly in the text, the mention to the post where the function image RAND() was withdrawn.}

Answer 2

Use external hardware

Cannot generate fully random numbers without external hardware.

As already indicated in the comments of your reply, could use either the Lavarand

If you enter the sites that use Really Random services (Random.org or Hotbits) use external hardware to ensure that the numbers are random:

Random.org: uses noises in atmospheric signals (reference).

Hotbits: uses the decay of radioactive particles (reference).

I can’t see why use external hardware, like the Random.org API could bring you security problems.

If you insist on not using them:

As you requested (examples in PHP or C++), I will post below the best way to get pseudo-random numbers in PHP:

<?php
mt_srand((double)microtime()*1000000);

echo "<b>mt_rand() com mt_srand()</b><br><br>";


for($i = 0; $i != 5; $i++)
{
    echo mt_rand(0, 100)."<br><br>";
}
?> 

The mt_rand() is much higher than srand() for using the Marsenne Twister is probably one of the best pseudo-random number implementations that exists.

If you want to compare with other forms in php:

<?php

echo "<b>rand() sem srand() (semente/alimentação)</b><br><br>";

for($i = 0; $i != 5; $i++)
{

echo rand(0, 100)."<br><br>";

}

srand((double)microtime()*1000000);

echo "<b>rand() com srand()</b><br><br>";


for($i = 0; $i != 5; $i++)
{

echo rand(0, 100)."<br><br>";

}

echo "<b>mt_rand() sem mt_srand()</b><br><br>";

for($i = 0; $i != 5; $i++)
{

echo mt_rand(0, 100)."<br><br>";

}

mt_srand((double)microtime()*1000000);

echo "<b>mt_rand() com mt_srand()</b><br><br>";


for($i = 0; $i != 5; $i++)
{

echo mt_rand(0, 100)."<br><br>";

}

?>

EDITED:

I found a bit suspicious the images of the answer accepted and decided to take the test:

Random.org

Rand()

mt_rand()

The code of this test is in gist the experiment was performed with PHP 5.3 and can also run online (without having to install anything on that website).

Answer 3

Random data can only be obtained from random procesoss. Physically, only quantum processes are really random and so there are external devices that generate random data: Geiger counters, reversally polarized PN junctions etc.

Without using external equipment, you can:

• obtain data from sites that generate random numbers: if you trust these sources and the process they use, you can obtain this data externally

• use the pseudo-random numbers generated on your own computer: the best sources are those of your operating system, as they must have been built following the best practices in force at the time of its construction.

• In general, if you use the functions/methods/whatever is in your programming language, it will look for those of the operating system. And will be the best sources available to you.

• make your own source: in general, it is very easy to make a mistake and end up generating less random numbers than those obtained by the operating system itself. Unless you suspect/know that your OS numbers are unreliable, which in this case means that your problems are worse than just trusting or not the numbers it provides.

[Edited by changing the question]

Randomization can be achieved without the use of external hardware, for example by using the time it takes a process to be done?

Yes, the time that a process takes can change, since the processing frequency of a processor can vary with temperature, voltage etc. But this variation can be extremely small, perhaps imperceptible. Could it be checked with the use of a watch? Yes, it could, with an extremely precise watch, e.g. an atomic watch or GPS. But this is not "internal" to a computer. A program, running inside a computer, does not know how long it took to run, without using an external precision clock.

Isn’t that something that’s intrinsic to the quantum states of the processor materials? If not, theoretically, in the smallest computable unit of time by a computer, an exactly equal process is always calculated at the same speed.

Exactly. If you have a processor running at 3.2GHz and each instruction takes a cycle to run, it means that each instruction will run at 0.3125 nanoseconds to run. If your processor is running at 3.199GHz, each instruction will take 0.3126 nanoseconds. It is not simple to own a watch that can detect this time difference.