Topic: Measuring the randomness of a seed phrase - page 2. (Read 652 times)

Thank you for the entire response.  I want to pick up on this point.  No issues with your statement of not being able to positively prove randomness for the reasons you stated.  I would think though you could test the inverse.  Can you prove that a human-generate seed isn't random (or rather, is patterned/predictable).  I'm not suggesting that all 2048^12 possibilities are scorable for randomness on a scale.  I'm saying that if we know some are not sufficient, we should know why they are not sufficient and to what degree they are patterned/predictable.  At some point we will hit a limit, but what is that point?  

The chances of your wallets selecting those subset of numbers is astronomically low. You have 2^256 to choose from, I highly doubt you would ever get any address anywhere near those that were already tried. It would be a massive waste of resources to keep those indexes and limiting the pool of numbers wouldn't be that ideal either.

Yep, that is correct. Cognitively, the human brain works by associating events together through a part of their memory. If a human were to think of a certain string of phrases, chances are the phrases appeared somewhere before and they chose that specific string based on some form of recollection. You can possibly prove it, if you were to scrape all the data there is on the internet, it might be inconclusive because they aren't exhaustive.
The former is generally true but the latter would depend on the quality of the source of entropy (are they deterministic or stochastic processes?), the way the entropy is processed and how it gets used. Desktop wallets generally use entropy given by /dev/random (which by itself uses multiple sources of entropy -> debiasing before initializing the CSPRNG) , sometimes XORed with other random data and this is more than sufficient for our uses. There are flawed implementations out there, but so long as it has been rigorously tested and correctly implemented, it will be secure.
It was a pretty fruitful discussion! My initial venture into cryptography was filled with question like these as well, glad that you're bringing these topics up to discuss!

That means that a software should not mark 888 as a good choice, because while random, it is not secure. So there exists a subset of numbers that are not secure but are random. Is it wrong to think that if we excluded that subset, we'd have better security? Seems to me like the problem lies how to do it, and not on if it's wise to do it.

There is no such barrier. Again, the same answer, and the same link I gave you is still relevant: https://xkcd.com/221/


That means, you are good to go, if your key is generated in a way, that is hard to repeat by someone else. By this definition, 888 is not a good choice, because there are bots scanning keys from the base point upwards, and sweeping anything they could find. The same for Pi: it is a bad choice, if you use it directly. However, nullius created a puzzle based on that, and after many years, it is still not taken.

So, the answer to your question is: anything that could not be guessed by others, is random enough. Of course, if you are not an expert in cryptography, then trusting some wallet like Bitcoin Core is better than making your own algorithm from scratch.

Thank you all for the insights.  I hope it's understood, my intention isn't to be contrary, I'm trying to better understand this for myself and that it's purely for sake of the enjoyment of learning something new.  Further, I'm not trying to justify or convince anyone that a person can better produce a seed than a computer.


If I give you the following list of words:  
rookie, brand, fossil, soda, arena, neutral, mango, yellow, ticket, chair, reunion, husband

What I'm hearing is, the only way you can tell me, if this is a "quality" seed or not, is if you are told what generated it.  

• If it was a CSPNG that created it, then it's sufficiently random/unpatterned.  
• If I created it, then by way of natural human cognitive bias, there must be/highly likely to be some pattern that is more guessable by some computer program.  

But there's no way a computer program can ever tell if it's indeed quality or not based on the list itself.  We just *know* that if a human created it, it's certainly insufficient and if a CSPNG SW program created it, it is positively sufficient.

If what I've stated above correctly represents the consensus on this topic (albeit in a simplistic way), the logic of this still eludes me.  If there is agreement among the geniuses in the world that study this stuff for a living that this is indeed the case, then I guess I will just add it to one many of life's mysteries to me.  I'm new to this board, I hope I didn't immediately embarrass myself for asking the question!

One thing I never understood is what sets the barrier between looking random and being random. For example, number 888 has the same chances theoretically to be picked between 1 and ~2^256, but it shouldn't, even if the process was completely random, because anyone playing with strange numbers can compromise the key. So you don't want a completely random process, you want one that generates randomly looking numbers, which raises the question of which numbers are looking random, or more importantly, which ones don't?

What proof do we have that Pi is random, even if not definite? Do you mean it is very questionably random?

Depends on implementation. Brainflyer is astonishingly good at cracking V1 Brainwallet phrases. Scrypt with salt would slow the process down a lot but I definitely wouldn't trust my money with it.

Unfortunately, that is the best that we can do. As we've said, the predictability of a seed or a random binary string cannot be determined from a single sample and that you need a relatively large sample to be able to ascertain that it is free of bias, and therein lies the question; how big of a sample size is sufficient? The answer is definitely not just a few of them and would possibly just be infinity.

The whole concept of "Don't trust, verify" comes with the fact that we are able to determine the authenticity of binary files with hash functions, or ability to inspect the code before compiling the code yourself. Entropy is unfortunately, something that you cannot measure and trying to evaluate a random process with certainty would be absurd (because then it won't be considered unpredictable anymore). ** Though note that urandom actually estimates the amount of entropy that is being added to the pool, but that involves a constant stream of data.

/dev/(u)random provides sufficient entropy for all the cases that we need. You can certainly generate your own entropy, a fair unbiased dice, atmospheric noise or the decay of an uranium ore if you want something random. I'd like to think of the security of Bitcoin as a binary result, "sufficient" or "insufficient". If you were to use a fair unbiased dice (6 sided), record down 99 rolls and calculate a SHA256 hash of that, I guarantee that the entropy would be sufficient (not perfectly perfect, but I won't have any doubts about it). What is the possibility that someone replicates all of your 99 rolls, with the same numbers, in the same exact sequence?

Indeed in all integer bases greater than or equal to 2.

If it were possible to check if the numbers being outputted were indeed completely random and cryptographically secure, then there wouldn't be such a large field of research dedicated to random number generators, or so many cases of weak random number generators leading to wallets bring compromised. Testing a single output as you are suggesting is meaningless. Let's say I toss a completely fair coin five times and get the following results: HTHHT. Fine, that looks random enough. Now I do it again and get TTTTT. Wait, that doesn't look random at all! Why? Both of those sequences had exactly a 1/32 chance of occurring.

A Chi-squared test simply tests for bias. It cannot tell you whether you are generating actually random numbers. It also requires multiple observations for each expected value, so cannot be applied to 256 bit numbers.

The issue here is there are potentially trillions of text inputs to analyze, so it becomes largely impractical to test the seed phrase against all of them (that is not mentioning the many different and creative ways the inputs could be transformed into the seed phrase).

It becomes more of an issue to analyze what are the more common ways people abuse randomness to make random-looking but statistically speaking, weak sequences, and I don't think you'll get very far with that without machine learning.

The issue is not the term you are using, it is what you are measuring. When you measure randomness, you are measuring the process and not the result itself. So, the question should be "how random is the process that generated this string of bits?" and not "how random is this string of bits?" The reason is simply that in a purely random process, every result is equally likely and thus equally hard to guess.

The problem of results with identifiable patterns is not that they aren't random results, it is that they are potentially results from a non-random process, and it is much more effective to attack non-random processes. However, the likelihood of generating such results using a random process is low enough that it is not a problem. For example, a password that happens to be one of the 1 million variations of the most commonly used 8-character passwords would be trivial to guess, but the odds of a random 8-character password using letters and numbers being one of those is 1 in 2 billion.

OTOH, there are statistical methods of evaluating the randomness of a process using the results. One example is the Chi-squared test. The accuracies of these tests depend on the amount of data and a single seed is not enough to be useful.

Thanks all.  Interesting discussion.

Perhaps my semantics weren't the best, using the word "randomness" whereas a better word could have been "non-patterned". 

If the randomness or "non-patternedness" isn't quantifiable/measurable as is the consensus here, then the scientific method can't be fully applied to the effectiveness of seed generators.  We only get to hypothesis based on deductive reasoning.  To judge the quality of outputted seed phrase solely on what generated (such as CSPRNG) it, rather than something intrinsic to the phrase itself that is testable, seems to violate the "Don't trust, verify" principle, no? 

It is still an open question whether pi is  normal or not. Academics continue their discussions on this matter. Read for instance the brief on the results obtained by David H. Bailey from Lawrence Berkeley National Laboratory which emphasizes "that the new result he and Crandall have obtained does not constitute a proof that pi or log(2) is normal".

So, before taking any conclusion on my statement, DYOR,  and don't rely entirely on Wikipedia. There are plenty research works on this matter.

And to conclude - just nice citation supporting my thought:

Pi is believed to be normal in base 10 [1], meaning it contains all finite sequences of digits. In which case your statement is obviously false.

An occurrence of some sequence of k digits in pi is only a sign of non-randomness if ithe index at which it occurs can be written in much less than k digits...

[1] https://en.wikipedia.org/wiki/Normal_number

Try 10111000, you'll realize that you can always win the code after a while. Essentially a De Bruijn sequence in combinatoric math, and if you analyze the source code, then you would realize exactly how to outsmart that algorithm.

But the point is actually to get 50-50, with neither side winning. Winning/losing would both point to your inputs having a pattern and the code to either always play the wrong moves or the right moves. It's one of the many possible ways to see a pattern in inputs, but it serves as a good demonstration why humans cannot be good at entropy.

This looks interesting: http://www.loper-os.org/bad-at-entropy/manmach.html

I have tried this website here for fun: https://numbergenerator.org/random-256-bit-binary-number

It produced the following:

0000000000001000101110010110010111110110100010101101110111000011110010111100001 0110101000100100011101001000100100100001001110101111000001001110000000000001010 0100110110000001011010101010000010011001001101111001000010101001011100100111000 0111011101001001101

I have played the game above using this input and it "won" the machine with a score of 56% approximately.

Ahh ok. In that case 12 zeroes in a row from a set of 16 possible characters would indeed by exponentially more unlikely. My (quick) calculations put it at approximately 1 in 76,569,678,407.

That's another problem you've touched on there. Pi, as far as we know, is random, uniform, and normal, although this hasn't been definitively proven. It could potentially be a good source of entropy, except that it is a widely known mathematical constant. And given that pi is infinite, random, and normal, then at some point in it you will find sequences of numbers which appear decidedly non-random. Since we are talking about 12 zeroes in a row, pi contains 12 zeroes in a row at position 1,755,524,129,973.

pi is the  mathematical constant with fixed digits, so any part of it can not be viewed as random because it can be calculated and besides  knowing it allow you with near 100% guarantee to point out the next digit/s.

AFAIK true random numbers may  be obtained only via digitization of fundamentally unpredictable and  stochastic  physical phenomena like quantum ones, atmospheric, etc..

How about 9428367110839506348425063820855586539232765? Looks random, right? Except that it's part of the first million decimals of pi.

The same with seed phrases: you can create one based on a Shakespear book. The seed will look random, but it's created deterministically. You can only tell it's not random once you find the source.

I stand corrected. I wasn't thinking about the binary representation, just in hex representation. I'll have a go at this combinatorics problem when I have some time but I suspect you're right that it isn't exactly extraordinary case even when considering that.

It isn't too useful actually. The suite is used to test for generation of a large set of entropy seeds, and it cannot be used to calculate the entropy of a specific keys, or a bunch of specific keys even. Usually used by people who are directly testing the source of entropy.

In addition, the suite is recommended to test for the randomness but not about non-predictability (which is also different). If you are developing your own source of CSPRNG (ie. another implementation of urandom), then you should use that. Otherwise, it is useless to evaluate for individual entropy because the sample size is far far smaller than required to test for that.

An interesting article by Random.org discusses this issue better than me: https://www.random.org/analysis/, stumbled upon it while finding sources of RNG previously. They conduct real-time analysis with the test as well, they yield interesting results.

The seed phrases are random as much as random  the sequences of bits from which they are generated. The ideal case is that when those the sequences are truly random and unpredictable.

To assess the randomness of generated bits one can use NIST Statistical Test Suite which includes 15 specific tests. The output of those tests  are  capable to tell if provided data are the result of pure chance.

The relevant guide on how to use NIST Statistical Test Suite is located here.