Topic: Generating a seed phrase with biased dice (Read 458 times)

Did some poking around, they are showing not available from a bunch of different IPs when going to Amazon.
Guess since it's 'sold by' someone else but shipped from Amazon they are only in the US warehouses.
If you want a set PM me and I'll ship them to you. Going to be interesting as what to put on the customs form....

---

Dice for seeds has been done for a while, and as discussed they just add to the entropy from the device.
BUT if the entropy is bad / wrong on the device and the dice are loaded not just biased? Over a large enough set of wallet creation with rolls you can run into other people generating the same info. The question is how many. But, you also then have to answer how bad is the entropy and how loaded are the dice.

-Dave

Coldcard provides all three options - PRNG only, PRNG + dice, or dice only.

https://coldcard.com/docs/middle-ground/#generating-seed-words
https://coldcard.com/docs/paranoid/#generating-seed-words-with-256-bits-of-entropy-by-dice-rolls

In the thread I linked, the OP chose dice only and then proceeded with a single dice roll of 5. You can verify this yourself by going to Ian Coleman, showing entropy, putting in "5", choosing dice rolls, choosing 24 words, choosing BIP 84, and generating the same addresses as OP:

https://mempool.space/address/bc1qln3mjur5h67xenn04vepunx27fhpvfgvqgwelx
https://mempool.space/address/bc1qmq80v8cxlsuwkxc8yt7hzjf05jyga3q5uea9uk

No, I am not from the US, and currently not logged in to my Amazon account either. I am still getting a "Product Unavailable" description, though.

According to the calculations by BlackHatCoiner, even a visibly biased die is good enough to create enough entropy. And based on what Coldcard's documentation says, the entropy from dice is just an extra that goes on top of the hardware-generated entropy from the device.

I see them as available here, are you US based?

The biggest issue is HOW loaded they are. Are you going to roll 20% more sixes or 50% more 90% more?
I would think that if you didn't know they were loaded after a few rolls it would be obvious. But the question would be how many till you go hmmmmm something is wrong here.

-Dave

Oh sure, this is not about dice games, my mistake, my brain always thinks about dice and when I read word biased, I quickly thought it was about the problem with provably fairness.

I don't say you shouldn't use any software other than Electrum. I simply suggest to use what has been used and tested for years in bitcoin industry, what has been proven to be safe and reliable. You can use Sparrow, no problem but it doesn't have android or ios app if that matters for you.

Btw if seed phrase randomness is a problem for you, then I would use vanity address generator on airgapped personal computer and generate bitcoin address with short random prefix. You'll receive private keys that there is absolutely no way they'll be biased or untrustworthy.

There is an interesting experiment that someone like BlackHatCoiner and possibly o_e_l_e_o could partake in. The dice that you linked to aren't available anymore, but if they could get an equal set, it would be fun to see how much entropy you could generate despite their bias towards rolling sixes.

Slightly OT, but something that was said to me years ago that stuck.

All 6 sided casino dice are biased over hundreds of thousands of rolls. They are man made and will show it given time. But in the short term of hours that they are actually on the table it does not matter.

If the dice here that @Pmalek are not used for anything else and came from an unknown source then it will never matter because there is still enough randomness in them.

Now, loaded dice: https://www.amazon.com/Character-Builder-Loaded-Koplow-Games/dp/B001N1JIU8 that is a different thing.

-Dave

That's interesting. I didn't know that. I thought that if you select the dice rolls seed generation method, that the entropy comes only from that source. But according to the documentation you linked to, 256 bits of entropy is already generated from Coldcard's hardware and the dice rolls are an addition on too of that.

But if that is true, I don't know how to explain this situation that o_e_l_e_o shared a few posts above. The user claims to have rolled a dice and got a '5' which he used to generate his seed. I seriously doubt he used advanced methods to bypass Coldcard's automatic entropy generation (the automated one you talked about), but still got his coins stolen (allegedly) within minutes. The whole story could, of course, be a a smear campaign and complete bullshit, but it's still different from what you said and what the Coldcard docs claim. 

It's already happening in the background on Coldcard - https://coldcard.com/docs/faq/#entropy


Every time you roll the dice, also flip a coin.  If the coin lands heads, keep the dice result.  If the coin lands tails, invert the dice and record that result instead.

With that logic, you could also ask why would anyone use any other wallet than Electrum. And still we have loads of software, better or worse than Electrum. Electrum doesn't generate BIP39 seeds, which is the standard for many other wallets. They have their own unique system that is older than BIP39 but far less represented in other wallets. So that's one reason. It also seems to me that you have confused dice and a die with the casino game Dice. This isn't about dice games.

How can you verify that your seed is generated randomly, on a hardware level? Short answer: you can't. You can rely on cryptographic libraries, which rock and the like, but when it comes to generating random numbers, while CSRNG are pretty good sources, there is no manner to verify they aren't tampered whatsoever.

Tossing coin can provide complete and provable randomness. It doesn't go more transparent user interface than that.

Is there any reason to generate seed phrase with dice when you can generate it in Electrum? There is no reason and when problem is easy to solve, you shouldn't start looking for more complex solutions.
If we want to get number 2 by adding some numbers to each other, easy solution is: 1 + 1 = 2
Hard solution is: 49+60-5+17+43-150+12-24 = 2

I hope I explained well what I wante to say. If OP's discussion is just a theory, then my answer will be that you are safe to generate a see phrase with biased dice if no one knows that you are generating a seed when you roll dice. There are millions of rolls every day on many casinos, if no one knows that during 10:18 - 10:20 Pmalek logged in in his account and played dice and saved their results on paper, then there is absolutely no way someone will be able to hack your wallet.

That would have defeated the purpose of him buying a new hardware wallet. He bought his Coldcard to get away from Ledger that he lost his trust in. Obviously, you have to move away from the old seed phrase also.

They can at least add a warning message informing users if the provided number of dice rolls isn't sufficient enough for a safe wallet. After that, it's up to the user to make a greater effort. It's easy to blame the user after something like this, but honestly, I don't know what he was thinking.

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

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.