Topic: How can you verify the randomness that's coming from a hardware? - page 5. (Read 1651 times)

Or fortunately that quantum computers have this as a problem, leaving security for all of banking!

I think there are a few different questions here:
1) What is random enough to provide security for generational wealth?
2) What is the most random system that you could ever create?
3) Are there sources that we think are random that could ever be backtraced or controlled?
4) Even if you have a purely random source, how do you ensure a flat spectral density?

It doesn't take much to make something be impossibly random.
I recommend a very different style of book, "A Short Stay in Hell", which deals with a man who has to overcome randomness to get out of hell.

Unfortunately even with entropy as low as in the super-cooled superconductors of quantum computers you would still hit the wall for physical measurements that we call Heisenberg's Uncertainty Principle.

"Decoherence and the Appearance of a Classical World in Quantum Theory" by H. D. Zeh is a great related-topic read, I recommend it.

From a mathematical perspective, random is defined as: different events are observed following identical initial circumstances. Currently such a definition of random cannot exist within our deterministic laws of physics.

You can generate the randomness artificially with mathematics and code alone, yes. Low entropy would be technically impossible to detect if you ignore the physics perspective and don't create your randomness generator with only a few lines of code and a limited output or input.

So I think that the point of entropy detection is moot.
 

Eliminating a lot of things, if you are using a wallet that has off the shelf parts and a list of what they use with a diagram and they publish the source code then *in theory* so long as you know the actual chip(s) they are using for RNG then you can be mostly assured it's safe.

Hardware wallets are a very very very small segment of what hardware randomness is used for. If people can't trust them then think about the number of devices that use them that would be impacted. Think about the number of video slots and stuff in casinos. If they are not random the amount that would be lost could be minor compared to any particular BTC hardware wallet.

-Dave

A dice roll should have a 1/6 chance of any given number being chosen. If for example, if a "roll" was a 4, then the chances of the next roll are:
1 - 95%
2 - 1%
3 - 1%
4 - 1%
5 - 1%
6 - 1%

if the previous roll was a 5, each of the above probabilities could be rotated by one index, so the probabilities would be 1, 95, 1, 1, 1, 1%. The probabilities could be similarly rotated for all six numbers.

The above weighting of the dice I believe would still pass randomness tests, because, over many tests, each number would be chosen 1/6 of the time.

---

A dice roll *should* be independent of one another. Often times, when someone is generating a private key via "dice rolls" they are actually generating a private key via some kind of simulated dice roll.

Only 99?
I have corrected the calculation. Oh, exponential numbers..

Still, 171 times could be used to create even more entropy, even if you are using less information than you collect.

A 20-sided dice is acting like a 2-sided dice with less bias than a natural 2-sided dice in this scheme.

I doubt anyone would disagree that a 2-sided dice has potential bias from one side having more weight than another, often because of larger marks. In practice, any of these biases would be minimal against other biases of the thrower, but we are discussing idealisations. A 20-sided dice should reduce the bias of a 2-sided by distributing the weight from slight changes in paint more evenly, especially after mapping the 20 numbers to only two numbers. A 50-sided dice mapped to create only two values would be even better because it should distribute whatever weights and rough edges to an increased number of values, all of which gets lost when mapping to only two values.

A 6 sided dice is worse than either a 2 or 20 sided dice in some way, so we can ignore 6 sides when imagining the ideal scenario.

I had given a reference.

You only need to roll a dice 99 times to get a 256-bit number. Which gives you a bitcoin private key.


The thing is, a 20 sided dice has more biases than a 6 sided dice. The more sides the more bias. So that might not be a good idea.

you can't cause or  influence when an atom undergoes radioactive decay. plus you don't know exactly when it will decay. look it up.

Check out this thread started by nullius: https://bitcointalksearch.org/topic/psa-coders-making-ad-hoc-random-schemes-are-like-kids-playing-with-matches-5326468

The problem with randomness is that you don't know whether something isn't random until there has been enough data measured and checked.

Even though you can't verify randomness, you could combine multiple sources of randomness to make it "more random" as long as your combination algorithm isn't causing additional bias and your sources are independent. The best route imo is to color one kind of randomness with other kinds of randomness. If one sensor is mostly random, then are two sensors more random? You could color your hardware randomness with a memory-given random seed generated from a second location, and the combined number would probably be just a little bit more random if used correctly.


Predictable entropy could be low entropy? It would encompass measurements of distribution, determinism, and independence.

One kind of predictability would be the distribution. There could be different random distributions: pink, brown, grey, etc noise are all types of noise and perfectly independent and random, but don't all have the same exact entropy. You would want a flat frequency spectrum, all values equally possible over all periods of time. "Random" is itself not the desired factor, but flatly distributed random with independence.

A predictably random distribution could also be something like Pi, which is dependent and deterministic, but is it random? Depends on the definition? Irrational numbers like pi are perfect examples of "predictable entropy". Pi looks entirely random. Pi is evenly distributed for each of 0-9 to 1,000,000,000,000 digits. There are no correlations with its own sequences of numbers as far as can be detected (https://doi.org/10.1080/00031305.2000.10474501). Pi is a deterministic sequence that will be calculated again and again as computers get more powerful. The gaps between prime numbers also come to mind as a predictable randomness.

It's not entirely paranoid. There was a flaw in a javascript code generating random numbers in some early addresses:
https://www.bleepingcomputer.com/news/security/old-javascript-crypto-flaw-puts-bitcoin-funds-at-risk/

You could use dice rolls, but you have to not influence the distribution with how you calculate the number. If you were to use a 6 sided dice, you could roll the dice log_6(2^256)= 99.03 times and convert a base-6 number to a 256-bit number.

If you wanted to be even more random - evenly distributed and independent - with dice, you could get a 20-sided dice but then collect the data in base-2 by saying every even number was 1 and odd number was zero, rolling it 256 times, and then converting that 256 bit number to a 32 hex / 64 byte character representation. This would reduce the bias towards any particular number. Obviously a bit of work, but this gets around that you might possibly have a small non-flat distribution in your dice rolls.

-

As for hardware, it depends on whether you need future randomness or something where you can control the historical randomness. Every system has flaws that prevent randomness in a very controlled future scenario.

There isn't anything that could be purely random without influence under the most controlled of circumstances (except maybe radioactivity, and that's a maybe). If you built your system off of thermal randomness, then I could cool your system. Radiofrequency waves? I could put your system in a shielded room. Even with radioactive decay, it's random but not a flat-spectrum and has exponential decay distributions. I'm not entirely convinced that it's always random - there are reports (which could be wrong) that radioactive decay is influenced by our distance from the sun http://arxivblog.com/?p=596 . Physics is such a beast that there could be a discovery on how to make radioactive decay not-random.

I agree with your "it's close enough" here. If you have 64 characters of complete entropy that no computer can crack for trillions of years, then do you need 10,000 bytes of entropy? Maybe, but hopefully not! At some point, we all make a choice as to what is good enough based on competing costs.

You can always be more random, independent, and evenly distributed. But where is good enough?

dice rolls are independent of one another. that's just a fact. the harder thing is for each outcome to have the same probability. but if it's a fair dice then it's probably close enough.

Predictable entropy? Not sure I understand? Like the rate of oxidation on microelectronic metal pins which can mess with the electrical flow in such ways that one could possibly guess which metals were being used in the chip or something and use that info to identify the part?

If predicting entropy is your game then from a physics perspective, that is impossible to tell at a certain tiny point but at a larger scale can be perhaps easier. But never with 100% accuracy.

Although I very much doubt we have the technology to measure the teeny tiny differences, even if you were to make all the hardware parts 99.999999% the same there still would be random noise from tiny differences.

So no, I very much doubt you can verify the randomness accurately.

Sensor-based random number generators are not truly random, and gaining control over sensor is making all data coming out compromised.
This is part of PRNG or Pseudorandom number generator that is probably deterministic and it is not strong enough to be used for bitcoin seed phrases.
One proven truly random stuff  I know that can be used is radioactive decay, and some people are working to do something similar with FM radio signals.

And that's the only difference. If you want to get some 256-bit number, it does not matter if you call some function that will return true/false 256 times, or if you call another function, that will return 256-bit value directly. If you have a state, then you can get it bit-by-bit and execute exactly the same algorithm. For deterministic outputs, you could get exactly the same results if you have a state. For random results, you can still get many samples and check if it is random enough, just by running the same randomness tests.

If you have a stateless function, then it is theoretically possible to get {4,4,4,4,4} result, mentioned above. If you have some kind of state, then you can design your algorithm differently, just to pass some randomness tests. And that will make your outputs more random, but also less resistant to some attacks, because then you can assume that you will never get {4,4,4,4,4}, just because that value will fail some randomness tests. Of course, usually the size of the output will protect you from those attacks, and you will not even notice that potential weakness.

Dice rolls are not the same as generating a seed. With a dice roll there are six possible outcomes, generating a seed, there are many more possible outcomes.

If you are using a dice roll to generate a seed, you should care more than just that each outcome has the same probability. You also care that a particular outcome does not affect the next outcome, in other words, that each outcome is independent of all other outcomes.

Also remember one thing: you don't need true randomness. You need randomness that is useful for your purpose. If you want to get a random number from 1 to 10000, getting {4,4,4,4,4} is unlikely, but still possible. However, not many random number generators will give you that result, because it will fail many tests. And that means some "nice, non-randomly looking values" are excluded, so here you have another potential attack vector.

I don't think that we can. While we expect they rather keep their business running than stealing people's money, we cannot know if they indeed play fair and go random, or generate their numbers by a rule. But...

In theory if they do this, the seeds the devices will generate will be a rather small subset of all the possible seeds (so they can brute force them in a reasonable amount of time).
However, if this would happen, there's a very big chance collision would happen, and rather often, between different users' seeds/wallets. If this happens, most do post about it (especially if it's them losing money).
Yes, I know, if this happens, people tend to point to hacks and unsafe storage of the keys, but still.. there would be much more of those imho.
Also I'd expect some users be nice and, instead of stealing, start writing about it.

Imho for now it's pretty safe to assume they did play fair until now.

I'm not paranoid enough to do that, I just wanted to know if this kind of function is verifiable. It doesn't matter if I roll a dice or not when the overwhelming majority uses hardware and software wallets. If, say, Trezor is proved to generate predictable entropy and steals everyone's funds in just one moment, it'll harm the entire bitcoin economy.

fractional part of onboard temp is unique. when system board has this sensor

Last year I wrote a topic about seed generation in hardware wallets and you can find some useful information there, but true randomness is a problem for software wallets also.
I think that software wallets are even worse than hardware wallets and it doesn't really matter much if they are open source or not.
Hardware wallets are mostly using combination of several elements mixing entropy of computer and device, and some are using closed source secure element for that.
Only verifiable seed generation for hardware wallets I was able to find was for Passport, Kestone, Coldcard, Trezor and BitBox02 walllet, others are more like a black box.

One true way to be sure that seed phrase is truly random is by using properly tested casino dices, so you don't have to trust any chips or computers that create fake random results that can be reproduced.

but what hardware you're talking about? say you have onboard temp sensor and system time. tell exactly what you wanna

I took a look at ledger nano and trezor hardwares. I found that there is a certification called AIS31-certified RNG which is the best in the world when talking about entropy.
As Ledger is not fully open source, they have such certification


Trezor doesn't have such a certification. However,  as it is open source you could  verify  their randomness in github.
It would be interesting to see the verification or audition of a professional
https://wiki.trezor.io/Recovery_seed

Unless you have capability to understand the design of the hardware or at least perform randomness test[1], you either trust the hardware company or someone who audit the hardware. I'm fairly sure there are decent amount of cryptography auditor, but i've no idea how common auditor for hardware design/architecture.

[1] https://en.wikipedia.org/wiki/Randomness_test#Specific_tests_for_randomness