Generating a seed phrase with biased dice

[Pmalek]

This topic has probably been covered many times, but I have a few questions I want to address.

As an intro, we can use dice to generate a seed phrase. Bitcoin hardware wallets/signing devices such as Coldcard or Seedsigner allow you to input the results of 50/99/x number of rolls and convert that into a seed.

A big danger of using dice rolls is if the dice are biased and more likely to land on one or multiple numbers. It affects the randomness, hence the security of your seed and Bitcoin. A truly unique dice roll is one where each outcome is equally likely. If one or more numbers have a greater chance to land on top, that is obviously not the case. It limits the keyspace from where the seed is generated, making brute forcing easier. Surely not easy enough, but easier.


A couple of questions:
In what ways are dice biased? Is the bias random?
For instance, am I more likely to roll a 2 than any other numbers on dice #1 and a 3 on dice #2?

Are dice manipulated on purpose, and if so, manipulated to achieve what results (rolls)? Or is the bias a result of low-quality production? If they are not manipulated on purpose, and the bias is random for each dice, wouldn't it even out if I have multiple dice (10, for instance) and roll them as many times as possible? If each dice is biased to a different number, can we really talk about a significant loss of randomness in the final result?

To take this further, how could someone take advantage of the bias in my dice to bruteforce my seed without knowing what that bias is? Even if 8/10 of my dice are biased and only 2 produce near-perfect results, wouldn't you need to know the exact bias to brute force my seed? If my thinking is correct, having knowledge of this bias would be essential for whoever or whatever is trying to hack my seed phrase because, based on the results alone, you can't possibly know that one of my dice has a tendency to roll a 2. In theory, if I throw 10 dice in the air, biased or unbiased, they could all show the result 2. Very unlikely, but still possible. How would the attacker differentiate the biased from the unbiased rolls? 

As a way to mitigate bias, it's better to use different types of dice from different manufacturers, sizes, etc. Although I can't possibly see all dice from manufacturer #1 as being biased to the same number and the dice from manufacturer #2 to a different number. It must be a random bias.

When we are on the subject of manually testing a die, it's very difficult to discover a slight bias. Obviously, if every second roll lands on the same number and you rolled it hundreds of times, it's enough proof that something is wrong. If all numbers appear in what seems to be a random fashion, it isn't easy to come to a conclusion. Randomness means that the number 5 could be rolled 1/10 times. But even if you roll it 7/10 times, we can't talk about bias if you don't get approximately the same number of unexpected results after dozens and hundreds of attempts.   

[Findingnemo]

A couple of questions:
In what ways are dice biased? Is the bias random?
For instance, am I more likely to roll a 2 than any other numbers on dice #1 and a 3 on dice #2?

A die can be biased for two reasons one is intentional means that is created to favor one particular number for cheating purposes. Another one is unintentional like it can happen due to a faulty process while manufacturing and become biased on one side so in both cases the bias is non-random and will likely favor one side but every die can be unique with their bias so if we use 10 different biased dice on multiple rolls then more likely we will see the same combination of number.

To take this further, how could someone take advantage of the bias in my dice to bruteforce my seed without knowing what that bias is? Even if 8/10 of my dice are biased and only 2 produce near-perfect results, wouldn't you need to know the exact bias to brute force my seed?

Even though it is not entirely possible to find the biased nature of a die, if they can find the noticeable results when rolling a die multiple times then it can be considered as the die is biased towards number 2 so they will incorporate it into the brute forcing process which will reduce the time to crack the result if their guess is right.

So I feel the bias dice can affect the security of seed generation.

What could be the best alternative?

I feel going completely digital can ensure complete randomness and it can be done with the Dice rolling applications built on Pseudorandom Number Generators (PRNGs).

[BlackHatCoiner]

You've asked a lot of questions, so I'll stick with those that I feel more confident answering.

If each dice is biased to a different number, can we really talk about a significant loss of randomness in the final result?

I don't think dice bias can cause a significant problem, given that you'll roll it 99 times as said. As I have already demonstrated, even in a very biased dice which results in '6' half of the time and every other result 10% of the time each, the generated entropy is more than necessary.

To take this further, how could someone take advantage of the bias in my dice to bruteforce my seed without knowing what that bias is?

It's all about entropy. If a biased dice gives only 1 bit of entropy in every roll, then 99 rolls would give you 99 bits. All the attacker needs to do is brute force anything in the range of 99 bits, because you can't have possibly exceed that. Practically speaking, that could be implemented by a program that hashes sequences of biased results. (i.e., attempt #1: hash("666123"))

[philipma1957]

We have hand the same discussion with 2 bingo machines

if you buy this machine
https://www.amazon.com/GSE-Plastic-Master-Board-Parties/dp/B07GQ3P2CM/ref=sr_1_17?


and this machine
https://www.amazon.com/Regal-Games-Jumbo-Professional-Brass/dp/B071G1W6JW/ref=sr_1_16?

then use 32red  x 64white = 2048
and use 32 white and 64 red = 2048

make 64 columns  each has 32 seed words
so do 12 seed with white picking the  columns and red the spot on that column
and do 12 seeds with red picking the columns and white the spot on that column

you will get plenty of bits of entropy

and it is easier to test if the shit is bias badly by studying duplicating word patterns. A bad bias would allow far more then 0.11 shot at repeated words
so if you did 100 seeds and got  lots of repeats you could say maybe a number has bias.



abandon
ability
able
about
above
absent
absorb
abstract
absurd
abuse
access
accident
account
accuse
achieve
acid
acoustic
acquire
across
act
action
actor
actress
actual
adapt
add
addict
address
adjust
admit
adult
advance

[Kruw]

The caution around biased dice is really overblown:

First, the randomness from your dice rolls is combined with the randomness from your device.  It's purely additional safety, not a single source of failure.

Second, a bias can be detected by the human eye after enough repetition.  The greater the bias, the more obvious the detection becomes.

Third, you can circumvent the bias on the dice by adding your own human randomness.  For 50% of your dice rolls, you can invert the dice and record the opposite result instead.

[o_e_l_e_o]

In what ways are dice biased? Is the bias random?
For instance, am I more likely to roll a 2 than any other numbers on dice #1 and a 3 on dice #2?

You will never know unless you actually test for the bias, which essentially no one does.

Are all the dice from a particular batch or from a particular manufacturer biased towards a certain number? Or perhaps all the dice are biased in their own way? Imagine how cheaply most dice are mass produced. Expecting them to be free from bias is very naive. Even casino grade dice are going to have some intrinsic bias.

and the bias is random for each dice, wouldn't it even out if I have multiple dice (10, for instance) and roll them as many times as possible?

Again, you will never know unless you actually test your dice. Perhaps all 10 dice are biased to the same number, and so you are just compounding the problem rather than addressing it.

To take this further, how could someone take advantage of the bias in my dice to bruteforce my seed without knowing what that bias is?

If you produce a number with fewer bits of entropy then it is less secure, regardless of the bias which got you there.

As a way to mitigate bias, it's better to use different types of dice from different manufacturers, sizes, etc.

Maybe. A better option would be to test the dice first using a Chi squared test. A better still option would be to use a debiasing approach which guarantees a completely random result regardless of how biased your dice are.

When we are on the subject of manually testing a die, it's very difficult to discover a slight bias.

Correct, and actually it's impossible to prove there is no bias whatsoever. The best you can do is asymptotically approach 100% confidence, but you will never actually reach 100%. And as you want to become more and more sure, you need more and more rolls. I've not ran the numbers, but you could likely rule out a 10% bias with a few dozen rolls, but to exclude a 1% bias you will need hundreds, if not thousands, of rolls.

[Accardo]

An interesting question, that has to do with probability; Binomial distribution. If the outcome of a specific numbers appears often than others it could be said to be biased. Getting a 4 fifty times in 100 rolls and other numbers taking the other 50 rolls. It's simply biased. In statistic you'll have to make assumptions and work toward it to get a result. For instance, putting aside a standard deviation and deciding if the outcome of a dice is outside or far from the mean, let it be biased. You can also roll the dice more than 100 times to know the actual results of the dice and what number appeared the most, how many times it did, analyze it and conclude a decision. As for a die with abstract results or outcome. I don't think they'll be need to check if it's biased or not. Since the results seem unbiased. I can't say for sure why a dice is bias or not. But since the dice used for generating seed phrase is also used in casinos, then it'll go a long way to answer the question. Casinos can use it to maximize profit for themselves by tricking players. No, an attacker may not correctly predict if your dice are biased and use it as an advantage to brute force your seed phrase. Like a member above said, you can as well make changes to the results if you're not satisfied or feel it's biased, to boost the security of your wallet. I was thinking of mass production, where some dices have similar outcomes. Don't know how possible it is, the hacker can use the outcome of his own dice to try brute forcing other people's seed phrase. But, that'll require a hell of stressful predictions, computing power and thoughts, to brute force. Hence your mitigation process is quite fine, to escape from such an attacker. However, I don't think the producers of the dice would have anything to do with trying to spoof buyer's seed phrase. They may not know why a specific user bought the dice. Hence, they may not have a their reasons for making it biased, other than for casino purposes.

As for determining the if a die is biased or not this math forum can help; http://www.mathisfunforum.com/viewtopic.php?id=14785 they settled the problem with some graphs and equations.

[philipma1957]

But the point is the bias if really high would be detected in creating the 24 seed words.

Obviously a 25%  roll of any of the numbers ie 25 of 100 would show bias reliably.

If any number on the die is rolling at 25% you will see it. As you are main a lot of rolls to get your seed of 24 words.

If the number 1 is 25%

and the other 5 numbers are 15% each, As determined with 100000 test rolls.

There are formulas that would show your bits of entropy.

and yeah it won't be 256 like a true 24 word seed. But it still would be really good amount bits.

So if you do a calculation for

25,15,15,15,15,15 die you can get the exact number of bits of entropy and find out if you 24 word seed is more like a 17 or 18 word seed.

Die are not going to be as bad as 25,15,15,15,15,15 unless they were intentionally loaded die.

[Pmalek]

Even though it is not entirely possible to find the biased nature of a die, if they can find the noticeable results when rolling a die multiple times then it can be considered as the die is biased towards number 2 so they will incorporate it into the brute forcing process which will reduce the time to crack the result if their guess is right.

But it's my die/dice. You can't test them for bias because I own them. You would have to be using the dice I was using.

I don't think dice bias can cause a significant problem, given that you'll roll it 99 times as said. As I have already demonstrated, even in a very biased dice which results in '6' half of the time and every other result 10% of the time each, the generated entropy is more than necessary.

That post and calculation of yours you linked to is way above my understanding. All I can see is the final result in bits of entropy (without knowing if your calculation is ok) showing more than what a 12-word seed has.

To take this further, how could someone take advantage of the bias in my dice to
It's all about entropy. If a biased dice gives only 1 bit of entropy in every roll, then 99 rolls would give you 99 bits. All the attacker needs to do is brute force anything in the range of 99 bits, because you can't have possibly exceed that. Practically speaking, that could be implemented by a program that hashes sequences of biased results. (i.e., attempt #1: hash("666123"))

In that post you linked to above, you demonstrated that even a biased dice produces enough entropy with a big number of rolls. If that is true, the dice would have to be awfully biased to only produce 99 bits to the point you can see it with the naked eye.

The caution around biased dice is really overblown:

First, the randomness from your dice rolls is combined with the randomness from your device.  It's purely additional safety, not a single source of failure.

Are you saying that we should be combining two sources of randomness or that it's already happening in the background? Is that what the Coldcard and Seedsigner are doing when you input dice rolls into the devices to generate your seed?   

Third, you can circumvent the bias on the dice by adding your own human randomness.  For 50% of your dice rolls, you can invert the dice and record the opposite result instead.

Can you provide a few examples?

You will never know unless you actually test for the bias, which essentially no one does.

If I were to ever generate a seed like that, I would throw each die many times before to satisfy my own curiosity and see if I can notice patterns that shouldn't be there.

And as you want to become more and more sure, you need more and more rolls. I've not ran the numbers, but you could likely rule out a 10% bias with a few dozen rolls, but to exclude a 1% bias you will need hundreds, if not thousands, of rolls.

In that case, wouldn't 100-200 rolls with 10 different dice (even if biased) be enough to generate randomness of somewhere between 130-200 bits of entropy which is more than enough as you don't get more from 12-word seeds and bitcoin private keys anyway?   

[BlackHatCoiner]

If the number 1 is 25%

If the probability of having '1' is 25%, and 15% for each other, each dice roll will produce 2.67 bits of entropy. This means that you would have sufficient entropy with 48 dice rolls.

That post and calculation of yours you linked to is way above my understanding. All I can see is the final result in bits of entropy (without knowing if your calculation is ok) showing more than what a 12-word seed has.

All you need to know is that we have an equation that tells us how entropy bits are worked out. These units define how unpredictable an event is. For example, a dice that gives '1' 99% of the time generates a lot less entropy bits in each roll than a completely unbiased.

In that post you linked to above, you demonstrated that even a biased dice produces enough entropy with a big number of rolls. If that is true, the dice would have to be awfully biased to only produce 99 bits to the point you can see it with the naked eye.

Correct. It would need to be so awful, that you could feel it's improper for generating entropy. A dice that generates 128 bits in 99 rolls, which are necessary for a Bitcoin seed phrase, generates 1.29 bits per roll. Imagine that even a dice that rolls '1' 75% of the time (and 5% for each other result) gives more than 1.39 bits of entropy.

And to give you a picture, these would be potential results from such a flawed dice:

Code:

Try #1: 1113111111161112111111114132111151111111111131511114131111111111141311565612111111141111113141111111
Try #2: 5411151515121111131111111111114111125213151411111161211113111111111411121311111161211611111611111151
Try #3: 1226141131111111164161116251411141542111111654311111511412111512141111111665411113111141111111411111

(code used: https://pastebin.com/raw/ctWm3jTH)

I think everyone could notice they're using a bad dice in such a case.  

[philipma1957]

If the number 1 is 25%

If the probability of having '1' is 25%, and 15% for each other, each dice roll will produce 2.67 bits of entropy. This means that you would have sufficient entropy with 48 dice rolls.

That post and calculation of yours you linked to is way above my understanding. All I can see is the final result in bits of entropy (without knowing if your calculation is ok) showing more than what a 12-word seed has.

All you need to know is that we have an equation that tells us how entropy bits are worked out. These units define how unpredictable an event is. For example, a dice that gives '1' 99% of the time generates a lot less entropy bits in each roll than a completely unbiased.

In that post you linked to above, you demonstrated that even a biased dice produces enough entropy with a big number of rolls. If that is true, the dice would have to be awfully biased to only produce 99 bits to the point you can see it with the naked eye.

Correct. It would need to be so awful, that you could feel it's improper for generating entropy. A dice that generates 128 bits in 99 rolls, which are necessary for a Bitcoin seed phrase, generates 1.29 bits per roll. Imagine that even a dice that rolls '1' 75% of the time (and 5% for each other result) gives more than 1.39 bits of entropy.

And to give you a picture, these would be potential results from such a flawed dice:

Code:

Try #1: 1113111111161112111111114132111151111111111131511114131111111111141311565612111111141111113141111111
Try #2: 5411151515121111131111111111114111125213151411111161211113111111111411121311111161211611111611111151
Try #3: 1226141131111111164161116251411141542111111654311111511412111512141111111665411113111141111111411111

(code used: https://pastebin.com/raw/ctWm3jTH)

I think everyone could notice they're using a bad dice in such a case.  

Exactly that. So if you use die and do 24:word seeds yeah maybe due to the unknown bias it is like a perfectly done 17-20 word seed.

[BlackHatCoiner]

Exactly that. So if you use die and do 24:word seeds yeah maybe due to the unknown bias it is like a perfectly done 17-20 word seed.

You shouldn't be counting in words. Words do not provide security. Entropy does.

In my previous example, every roll produces 1.39 bits of entropy. A 24 words long seed phrase is an encoded version of 256 bits (plus a checksum that is dependent on these). This means you can produce a secure such phrase by rolling said dice for 256 / 1.39 = 185 times. It would provide the same security as to tossing an unbiased coin 256 times, or rolling an unbiased dice for 99 times.

[o_e_l_e_o]

If I were to ever generate a seed like that, I would throw each die many times before to satisfy my own curiosity and see if I can notice patterns that shouldn't be there.

Simply noticing a pattern is insufficient to exclude bias. If you roll your die 60 times and get 15 ones, is that biased, or is that random chance? As I mentioned above, you need to use proper statistical testing, and even then you can only approach a confidence limit and never exclude a bias 100%. I've outlined one possible approach more in this post: https://bitcointalk.org/index.php?topic=5395587.msg59967945#msg59967945.

You need to decide how much bias is acceptable to you, and how sure you want to be you have excluded it. The number of rolls required exponentially increases as you want to be more certain you have excluded smaller biases.

In that case, wouldn't 100-200 rolls with 10 different dice (even if biased) be enough to generate randomness of somewhere between 130-200 bits of entropy which is more than enough as you don't get more from 12-word seeds and bitcoin private keys anyway?

Maybe. Maybe not. The numbers given so far in this thread discuss the Shannon entropy, but have you calculated the min-entropy you would achieve from doing this? What randomness extractor algorithm are you planning to use to turn those dice rolls in to usable entropy? How are you converting those dice rolls to binary without introducing modulo bias? It's not as simple as just "roll the dice more" - it's a very complex topic which most people do not fully understand (and I do not profess to either), which is why whenever the topic of manually generating entropy comes up, I always suggest von Neumann's coin flips to simply, quickly, and most importantly verifiably generate 128 or 256 bits of provably unbiased entropy.

[Pmalek]

...which is why whenever the topic of manually generating entropy comes up, I always suggest von Neumann's coin flips to simply, quickly, and most importantly verifiably generate 128 or 256 bits of provably unbiased entropy.

I am not familiar with it, but I wouldn't trust myself with coin flips and I will tell you why. If I throw a pen in the air and tell myself I am going to catch it by the tip, guess what, more often than not, I manage to do that. That's not a random throw because I figured out how high to throw it, how many times it's going to spin before it lands in my hands, etc. Obviously, a coin is different, but the point is we aren't good sources of entropy if our subconscious tells us to manipulate the result to see if it works.

If my coin flip would land on tails twice, for instance, I can't trust myself not trying to land another tails just to see if I can. You might say you can do that with dice as well. Sure, but a die has 6 possible results, while a coin flip only has two. I hope you understand what I am trying to say. Does von Neumann's system account for that, and in what way?

[philipma1957]

If I were to ever generate a seed like that, I would throw each die many times before to satisfy my own curiosity and see if I can notice patterns that shouldn't be there.

Simply noticing a pattern is insufficient to exclude bias. If you roll your die 60 times and get 15 ones, is that biased, or is that random chance? As I mentioned above, you need to use proper statistical testing, and even then you can only approach a confidence limit and never exclude a bias 100%. I've outlined one possible approach more in this post: https://bitcointalk.org/index.php?topic=5395587.msg59967945#msg59967945.

You need to decide how much bias is acceptable to you, and how sure you want to be you have excluded it. The number of rolls required exponentially increases as you want to be more certain you have excluded smaller biases.

In that case, wouldn't 100-200 rolls with 10 different dice (even if biased) be enough to generate randomness of somewhere between 130-200 bits of entropy which is more than enough as you don't get more from 12-word seeds and bitcoin private keys anyway?

Maybe. Maybe not. The numbers given so far in this thread discuss the Shannon entropy, but have you calculated the min-entropy you would achieve from doing this? What randomness extractor algorithm are you planning to use to turn those dice rolls in to usable entropy? How are you converting those dice rolls to binary without introducing modulo bias? It's not as simple as just "roll the dice more" - it's a very complex topic which most people do not fully understand (and I do not profess to either), which is why whenever the topic of manually generating entropy comes up, I always suggest von Neumann's coin flips to simply, quickly, and most importantly verifiably generate 128 or 256 bits of provably unbiased entropy.

I know you push the coin flip method. Makes the most sense.

[Medusah]

If my coin flip would land on tails twice, for instance, I can't trust myself not trying to land another tails just to see if I can.

That is why o_e_l_e_o suggests to use von Neumann's method.  It eliminates that bias: https://xlinux.nist.gov/dads/HTML/vonNeumannCoinFlip.html

[alani123]

To test for bias you would have to make thousands of impartial iterations, this becomes harder in real world conditions because entropy comes into play a lot with many things.

In that sense this is a very nuanced question. I don't think it would be practical  to go at such great lengths for a seed generation technique maybe no one else has used. But if you want to test randomness for security's sake on something like this, you might have to do it yourself. Get a dataset of dice rolls, plug it into your seed generation algorithm, and examine the randomness. Probably you'd need another algorithm for that. A biased dice could lead to some patterns where following certain paths becomes more likely through a certain algorithm for seed creation. But if the bias is too small then maybe it's not a risk.

[Pmalek]

That is why o_e_l_e_o suggests to use von Neumann's method.  It eliminates that bias: https://xlinux.nist.gov/dads/HTML/vonNeumannCoinFlip.html

Mathematics, formulas, and algorithms have never been my strong suit, but why is this considered random if you are specifically looking for only 2/4 combinations after a set of two coin flips, without considering the other two combinations? Heads-Tails and Tails-Heads are ok, while Heads-Heads and Tails-Tails aren't. Randomness should allow all possible combinations, it's just that humans can't generate it. 

[o_e_l_e_o]

Mathematics, formulas, and algorithms have never been my strong suit, but why is this considered random if you are specifically looking for only 2/4 combinations after a set of two coin flips, without considering the other two combinations? Heads-Tails and Tails-Heads are ok, while Heads-Heads and Tails-Tails aren't. Randomness should allow all possible combinations, it's just that humans can't generate it.

Let's say you have a biased coin, or you flip a coin in biased way, such that you have a 60% chance of heads and a 40% chance of tails.

The combinations HT or TH are exactly as equal as each other. HT has a probability of 0.6*0.4 = 0.24. TH has a probability of 0.4*0.6 = 0.24. They are exactly equal, and so if you treat one of these combinations as 0 and the other combination as 1, you will be guaranteed to have a random result. This holds true regardless of how biased your coin is, and crucially, it also holds true even if you don't know the bias. Flipping HT or TH will always have identical probabilities.

You exclude HH and TT exactly because the probabilities of these will not be equal, leaving you with only two possible results for each pair of flips with an identical probability and therefore a random result.


Talking of generating a seed phrase with dice, I just stumbled across this post on Reddit: https://www.reddit.com/r/coldcard/comments/17epqk8/040_bitcoin_taken_instantly_from_my_coldcard/

OP used a single dice roll to generate his seed phrase. He rolled a 5, used that as his entropy, and had his funds immediately stolen. Obviously it's a failure on OP's part to understand what is going on, but it's also a massive failure on Coldcard's part that it let him proceed to generate a seed phrase using a single dice roll.

[Pmalek]

Talking of generating a seed phrase with dice, I just stumbled across this post on Reddit: https://www.reddit.com/r/coldcard/comments/17epqk8/040_bitcoin_taken_instantly_from_my_coldcard/

OP used a single dice roll to generate his seed phrase. He rolled a 5, used that as his entropy, and had his funds immediately stolen. Obviously it's a failure on OP's part to understand what is going on, but it's also a massive failure on Coldcard's part that it let him proceed to generate a seed phrase using a single dice roll.

Very bad situation that would have been easily avoided if the user had simply calmed down, used common sense, and done some research. Coldcard has videos and documentation explaining the process of rolling dice and generating a seed from dice rolls. He didn't bother checking any of that, and was more concerned getting his money off his Ledger as soon as possible, even though there isn't an immediate threat. 

Coldcard is partially to blame for allowing it, but that's what you get if you want absolute control. I am not a Linux user, but I know the system gives you much more freedom than Windows. That also means a possibility of making serious self-destructive mistakes.