Topic: Generating a seed phrase with biased dice - page 2. (Read 458 times)

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?

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://bitcointalksearch.org/topic/m.59967945.

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.

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.

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.

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.

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.

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.

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 used: https://pastebin.com/raw/ctWm3jTH)

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

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.

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.

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.

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?   

Can you provide a few examples?

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.

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?   

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.

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.

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.

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.

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

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.

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.

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.

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

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

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.

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

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.


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

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.