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

Handing over freedom to users; decentralization. Still has disadvantages like self-destructive mistakes. Most cold card guides I've read suggest for 100 rolls or more, but from his responses he never looked into it. He thought it'll be just like his ledger wallet experience. I'd support one of the responses on the thread; saying that inexperienced users should use the coldcard generated seed phrase. Instead of using the rolling dice feature of generating seed phrase. He shot himself on the leg trying to increase the security or entropy of his seed phrase; make it hard to guess or brute-force. Cold card is not to blame. It's not their responsibility. As they were not present with the user to guide them physically, on how to use the dice generated seed feature. With their true random number generator in the hardware chip. The hardware's seed picking methods are still secure against attackers.  Not every user can boost the entropy of their seeds using the dice. How then can CC help them? It's now a personal encounter or issue. It would have been better if the victim imported seeds from his previous wallet. The dice generated seed phrase is easy to guess if the user is not experienced at generating entropy. It'll be a better security development if they restricts users that use a single dice roll to generate seed phrase.

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.

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.

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. 

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.

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

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

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