How can you verify the randomness that's coming from a hardware?

[kaggie]

If you were to use a 6 sided dice, you could roll the dice 8-byte/6-dice * 128 = 171 times and convert a base-6 number to a 128-byte base-8 number.

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

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.

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,

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.

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.

Physics is such a beast that there could be a discovery on how to make radioactive decay not-random.

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.

I had given a reference.

[PrimeNumber7]

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.

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.

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.

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.

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.

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.

[DaveF]

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

[goldkingcoiner]

Check out this thread started by nullius: https://bitcointalk.org/index.php?topic=5326468.0

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.

So, how do we verify that the hardware doesn't generate predictable entropy, regardless of whether the wallet developers have bad intentions or not? I don't care about the OS, let's assume you use an open-source one; my focus is on those who build the hardware that is used to generate randomness.

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.

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.

I know it sounds paranoid, but I don't know what to answer if one ever made me such question. Like, sure, most of the hardware is very unlikely to have this kind of weakness, but what about hardware wallets? They're designed for solely transacting bitcoins and their random number generator, as in all hardware, isn't apparent.
..
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.

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 32*16 times, and then converting that 32*16 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.

but if it's a fair dice then it's probably close enough.

I agree with your "it's close enough" here. If you have 128 bytes 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?

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.
 

[kaggie]

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.

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.

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.

[LoyceV]

I know it sounds paranoid
~
Couldn't one of all these hardware wallet companies implement something like that and steal millions of dollars worth of BTC, in just one moment?

That's always on my mind too. I use hardware wallets, but it always feels like I can't fully trust them.

I'm not sure how plausible this kind of attack would be though.

Not knowing is what makes me paranoid

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.

embedded in the Secure Element

Can you check if it's actually in there? What if some of the devices are shipped with a compromised RNG instead of the certified one?

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.

Isn't it much more likely to happen from a software wallet? Say someone manages to push a compromised update, that uploads the wallet when it gets unlocked.

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).

This is a good point. To prevent a collision, the number of possible wallets has to be much larger than the square of the number of wallets they sell. So, say they sell 10 million wallets and want less than 1% chance of a collision, there should be at least a billion different combinations per existing hardware wallet. That's still possible to brute-force, but doing all of them would mean 10¹⁶ combinations.

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

I think so too.

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?

One easy way to do that is by creating a split-key vanity address. If you create both parts on different hardware with different software, it doesn't matter if one of them is compromised.

I find it easier to trust generic hardware (and software for that matter), than anything dedicated to Bitcoin. Just like I find it easier to buy generic hardware than buying a hardware wallet. I don't mind that any shop knows I own a printer, but I wouldn't want them to know I own a hardware wallet.

The generation of random numbers is too important to be left to chance.
Robert R. Coveyou, Oak Ridge National Laboratory

[garlonicon]

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).

They can attack in a better way and make it much more clever. For example: some company could create some random 256-bit seed. Then, that seed can be used to derive public keys and to save some sample public key on each device, just by using some standard derivation path, or just by using things like device serial number to derive keys. Then, it could be possible to create 1-of-2 multisig each time when user needs a new key. And then, it is possible to just silently wait. To remain unnoticed, they can wait a lot of time and sweep coins only from some wallets, for example after a customer will notify them about lost keys. Then, they could sweep them and pretend that the user was hacked by using bad security practices (which, ironically, would be true, because he trusted that wallet).

[bitmover]

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.

embedded in the Secure Element

Can you check if it's actually in there? What if some of the devices are shipped with a compromised RNG instead of the certified one?

You can check the hardware integrity by following this guide by the manufacturer

It shows how to open the hardware and check by yourself if everything is as expected.  There are even pictures of what to expect inside

https://support.ledger.com/hc/en-us/articles/4404382029329-Check-hardware-integrity?support=true

All Ledger devices pass the genuine check during the onboarding process and then each time when they connect to Manager in Ledger Live. Genuine Ledger devices hold a secret key that is set during manufacture. Only a genuine Ledger device can use its key to provide the cryptographic proof required to connect with Ledger’s secure server.

Advanced users additionally can check the hardware integrity of the Ledger device to check that it has not been tampered with. This article contains detailed technical information about the security of your device.
Important notice

    Please note that opening your Ledger device will void the warranty.
    Once opened, your Ledger device will no longer be refundable or exchangeable.
...

As an additional check, you can open the device to verify that no additional chip has been added, compared with the images below, and that the MCU is an STM32WB55 (on revisions 1, 2, 3) and STM32WB35 (on revision 4).
Hardware revisions


...

There is a lot more information there.

[NeuroticFish]

Can you check if it's actually in there? What if some of the devices are shipped with a compromised RNG instead of the certified one?

I'm not sure it's so much relevant. If they're evil enough they can easily show nice hardware and use internally their own rigged software random generator.
I mean if we go paranoid, there are plenty of ifs and buts...

[LoyceV]

You can check the hardware integrity by following this guide by the manufacturer

The hardware integrity check will only show tampering by third parties. This topic is about verifying the original hardware, and if the manufacturer changed the internals of a component, they could make it look the same.

If they're evil enough they can easily show nice hardware and use internally their own rigged software random generator.
I mean if we go paranoid, there are plenty of ifs and buts...

That was indeed my point.

[dkbit98]

What is the most random system that you could ever create?

I don't have to invent the wheel all over again, and most human beings don't have the skills to create random systems.
People are generally very bad and randomness and very good in repeating things, but using casino dices as random system is working just fine for centuries if not ages.
For most people this will be enough, but for going extreme you can always use radioactive decay with geigers counter, that is something you can't fake.

If they're evil enough they can easily show nice hardware and use internally their own rigged software random generator.

All software random generators are not giving true random results, that is why nobody is using them for anything serious.
I think that gambling websites and casinos are using them a lot, and you know what they say - house always wins

[NeuroticFish]

If they're evil enough they can easily show nice hardware and use internally their own rigged software random generator.

All software random generators are not giving true random results, that is why nobody is using them for anything serious.
I think that gambling websites and casinos are using them a lot, and you know what they say - house always wins

I think that you've missed the point of this topic.
The idea is not how would you make a really good system. The idea is: what if the HW contains a ticking bomb?
And since the point is to *not* create actual randomness while pretending to .. even software generator may do.

[dkbit98]

I think that you've missed the point of this topic.

I think that you are missing the point, and I was just replying to your statement about software random generators.
Title of this topic is about randmoness from hardware, and casino dices are perfect simple hardware that can be verified and it doesn't have any software that can be exploited.

The idea is not how would you make a really good system. The idea is: what if the HW contains a ticking bomb?

Someone can hide ticking bomb almost anywhere, but I didn't saw OP talking about bombs here, so your ''ideas'' doesn't make any sense to me...

[goldkingcoiner]

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.

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.

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.

Unfortunate for the curious 
Interesting questions indeed. I will try a stab at them but I am sure everyone else in the Development & Technical Discussion subforum knows a lot more about it than me. So take my answers with a grain of salt.

1. I think you can make anything infinitely random but that all means nothing if someone reads your code to understand how the randomness is generated. So your randomness is only as good as your security.
2. Perhaps data from as many high entropy sources as possible for the input and a multitude of security layers? I really don't know how to express something as truly random so I have no idea.
3. For example weather. Even with current technology we cannot accurately predict the weather. Nobody technically knows if next week will be 1 degrees hotter or colder than predicted. Although it can be easily guessed/predicted due to the fact there are not many viable temperature numbers to choose from.  
4. Not sure. Perhaps by adding white noise to the intensity in discrete time sequences?


edit: Thanks for the book recommendation. Sound interesting.

[LoyceV]

human beings don't have the skills to create random systems.

That's only true for reproducible "random" systems, like passwords. Creating something random as a human is very easy: if I draw something on a piece of paper, scan it, and hash it, there's no way anyone (including me) can ever reproduce it! Doesn't that make it random?

In fact, I think it's harder for a computer: I've seen (old) computers that started with the same "random" number after each reboot, because they had nothing "random" in there. Any kid with a pencil creates random data if you look close enough.

[dkbit98]

That's only true for reproducible "random" systems, like passwords. Creating something random as a human is very easy: if I draw something on a piece of paper, scan it, and hash it, there's no way anyone (including me) can ever reproduce it! Doesn't that make it random?

I could always find digital copy of your scan and reproduce your drawing easily, how do you think people created fake money, coins and paintings since the beginning of time.
If I can reproduce your painting in any way that means it's not truly random, and there is a bunch of academic papers and research that can prove why you wrong, and why you need to read more about this to understand it better.
People are bad not only bad in creating but they are also bad in detecting randomness because it's hard, and you can read more about it in this Berkeley study:
https://cocosci.princeton.edu/tom/papers/hard.pdf

[BlackHatCoiner]

if I draw something on a piece of paper, scan it, and hash it, there's no way anyone (including me) can ever reproduce it!

It'll definitely be messed up, but not random, or at least not as much as in other ways. There's a significant percentage of the human factor, how does your hand move, which shapes will you think of, at which rate will you repeat the shame shapes etc. It's the same as the mouse detector RNG of bitaddress.org.

That's the best I can do is: Take few dices, put them on a cup, start mixing them, verify that they're fair, redo it to generate entropy for the seed.

[n0nce]

if I draw something on a piece of paper, scan it, and hash it, there's no way anyone (including me) can ever reproduce it!

It'll definitely be messed up, but not random, or at least not as much as with other ways. There's a significant percentage of the human factor, how does your hand move, which shapes will you think of, at which rate will you repeat the shame shapes etc. It's the same as the mouse detector RNG of bitaddress.org.

That's the best I can do is: Take few dices, put them on a cup, start mixing them, verify that they're fair, redo it to generate entropy for the seed.

If you trust a few dice trows to verify the randomness / entropy / fairness of the coins, actually I remember some hardware wallets do have a 'random dice throw' feature. Of course, an evil chip manufacturer could theoretically generate the seeds with bad randomness and use the actual RNG just for the dice throw applet.

Most aspects have already been brought up, like RNG chips being used in other applications outside Bitcoin hardware wallets, but one thing I'd like to touch on is the legal side and open-source aspect. There are two attack vectors I can think of: (a) the chip is not doing what it's supposed to, and (b) the chip installed on the PCB is not the one they claim to be using.
The first one is only really viable if the company that makes the hardware wallet also makes the chips and if they manage to fool everyone in the business to manufacture something other than what is shown in the source files without any of this leaking to the public.

Since I don't think any wallet manufacturer today is making their own chip, I'd tend towards option (b): rebranded, faked secure elements. They could have the same pinout but have another chip inside and the correct writings on the package.
To really make sure this is not happening, the devices would need to be disassembled, the chip desoldered and via direct connection you could verify that it at least runs the communication protocol that it's supposed to and returns data as per the datasheet.
I'm not sure how thorough entities like OSHWA^{OSHWA Certification provides an easy and straightforward way for producers to indicate that their products meet a uniform and well-defined standard for open-source compliance} are, but so far I'm aware of two hardware wallets that were certified by them, out of which one has a secure element: Passport OSHWA certificate.

In theory, they should have verified that (b) is not happening and the devices are built to the open-source spec (with the correct chips and logic board whose files are released publicly).

[NotATether]

To everyone mentioning trying to eliminate a "4" from dice rolls:

If you don't want that particular outcome from a dice just use a 5-sided dice without a 4...

And similarly, if you want to exclude particular outcomes from a software RNG, just keep regenerating it until you get an acceptible value, this comes at no loss of entropy.

Intel RNGs in their procesors are intelligency-agency backdoored, from information I've gathered several months ago, so definately don't rely on RDRAND for anything important. I don't think AMD even has an RNG hardware instruction.

AIS13 (or was it 31 ) sounds good as well as whatever ARM is coming up with - it's an open standard anyway so you're free to trust an individual vendor that their impl. is free from tampering.

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?

You generally only need 60-70 bits to ensure a random sequence that is unbreakable by criminals and govts. for the next ten years (never extrapolate beyond 10 years as the technological situation can change drastically by then).

There is no upper ceiling for entropy, but it'll be increasing proportionally to the length of the output sequence e.g. passwords.

CPU core temperatures can be artificially modulated by the hardware so that is not a particularly trustworthy source of entropy. Sound (from coil whine) would probably be a better choice as this can't be supressed by hardware.

[n0nce]

I just checked the Foundation Passport's security model again and it actually doesn't use the (closed source) secure element for randomness! I had this in my mind since another wallet does this and I looked up something about it recently.

Microchip ATECC608A secure element. This security chip is explicitly designed to safeguard private keys, but is simple enough that it does not execute any code. We use the 608a primarily for its secure key storage slots.

So the chip is only for storage, not for key generation / RNG like I hinted to earlier - at least on this hardware wallet_~n0nce~
[...]

Avalanche noise source. This open source implementation of a true random number generator allows for a provable source of entropy without any black-box silicon. Same general design used by bunnie in the Betrusted project.

The project they mention is this: https://betrusted.io/
It correctly states:

On-die RNGs such as ring-oscillator based RNGs leverage the metastability of sampling circuits to translate timing jitter into a random stream of bits. These are area and power efficient but are also tricky to verify. They are particularly vulnerable to subtle mask-editing attacks.

It then goes on to explain this 'Avalanche Noise Source' in great detail, which is very interesting and fascinating to me. The circuit is pretty simple and cheap to manufacture and doesn't require 'black box' components. Very clever. It allows companies like Foundation Devices to have an open-source RNG, even though the secure storage chip is closed-source.