Topic: Is it possible to generate an already existing seed? (Read 557 times)

You certainly covered a lot of ground in that response. At this moment my time is short so let me cover a couple of points.

A. Anything that can be construed as encouraging home-brew is wrong.

B. Dice cannot be the "home-brew" of which you warn against.

C. When I mentioned making random generators, I had basic transistor theory in mind. Google quickly enough shows people have done it many times. Here 'ya go.

https://makezine.com/projects/really-really-random-number-generator/

What I was getting to here is the idea that this is all out in the open, like open source code. Anyone can examine it, and let's say anyone can connect a test probe anywhere in the circuit.  What you see is what you get. You can criticize it and find flaws, then the circuit can be revised and improved. But still it's all totally out in the open.

Now on the contrary, say that I encapsulate and miniaturize this circuit, and sell it to you. In fact you don't know what is inside that black box.

Similarly you don't know what is inside the "black box" of your CPU. Not without some serious lab work, and even then I would argue that you know in part only.

This is wrong.  “likely possible”?  Is that how you give cryptography advice?  Is it, or isn’t it?  Can you do it?  Have you done it?  What can you demonstrate about the security properties of the results?

Back up one moment.

I could explain why I trust my system’s CSPRNG, in terms which reduce to my security assumptions about the properties of certain things (such as hash functions).  It may come out a bit muddled, and much less rigorous than a professional cryptographer would do.  But I could explain in some detail why I think my computer’s CSPRNG is secure.  (It would be a waste of my time and readers’ time; read something rigorous by an actual cryptographer if you want that level of detail.)

Can you explain what you said?  You made a positive assertion of “serious defects”.  Can you identify what they are?

This is an important question.  What you said encourages homebrew.  In crypto, almost invariably that results in a festival of foot-shooting.  (Are those hexadecimal gaming dice really well balanced?  Are you sure?  Also, are you aware of the research literature finding biases in actual flips of actual coins?)  Worse, you waved your hands and said it’s “likely possible” to cook up some homebrew electronic randomness gadget.  For anybody who lacks deep expertise in both maths and physics, this is a guaranteed security disaster.  (I linked to John Denker’s site.  He’s a physicist.  He has enough knowledge to design his own stateless random symbol generator based on thermodynamic noise in analogue circuits—still not using any home manufacture, either; just an ordinary computer soundcard.  I don’t have that knowledge; I am pretty sure that you don’t, either.)  Worst of all, deterring people from reliance on a good CSPRNG is sending them in the wrong direction.  That’s bad advice!

Also, I should emphasize, you said “library functions”.  I spoke above about the kernel, which has access to the hardware and can seed its PRNG until it contains not less than 256 bits of unpredictable interal state.  “Use /dev/urandom”.  I am not here saying that library functions are flawed!  Some are excellent; but they, too, must be seeded from somewhere—that is, from the kernel via the random device.

Sixteen side dice are available and enable quick and easily producing random numbers.

Any computer library random function has serious defects.

Side note.
It's likely possible to build a random generator with basic electronic parts, such that it's all out in the open and can be examined.

Well put about trust.  I began writing a long post here.  Rather than much delay my reply, and to better stimulate active discussion, I hope to address your questions a bit more concisely—if much less elegantly:

On a brief skim, I see some problems with that Calomel.org page:  0. It places too much reliance on statistical tests.  As I said above, statistical testing can prove that RNG is flawed, but can never prove it to be sound.  Experts faced this problem with the Intel RDRAND/NSA BULL RUN fiasco.  Try encrypting the output of /dev/zero with AES-CBC, approximately `dd if=/dev/zero bs=1m count=1 | openssl enc -e -aes-256-cbc`, and running the statistical tests on that; all tests will pass!  1. It gives advice on tuning your software RNG and also on hardware entropy gathering, all of which must be carefully audited.  2. It is outdated.  For example, I have not kept up with the latest in OpenBSD development; but I am under the impression they completely ripped out the flawed ARC4 cipher, replaced it with some ChaCha variant (one of djb’s stream ciphers), and deprecated /dev/arandom.  The Calomel page (wrongly) recommends symlinking all other random devices to /dev/arandom.  (Not sure about these things.  I’m not an OpenBSD user.  Please double-check.)

An excellent link in my prior post to which I should have given more attention is John Denker’s Turbid.  I do not know the exact status of its software implementation; but the Turbid paper will answer many of your questions much better than I could.

I do think that most modern “unixoide” systems (as you put it) will have adequately secure kernel random devices.  (I think I may borrow that terminology from you!)  Thus my repeated advice, read() off /dev/urandom.  If you have only one takeaway from this thread, please let it be that.

How is this linked to Bitcoin?  In brief:  If your randomness generator is flawed, then you risk losing all your money.  There are people who scan the blockchain for evidence of coins they can snatch this way.  Solution:  Use a good PRNG!  Most importantly, don’t break an expertly designed and implemented kernel RNG by trying to improve it.  Most Bitcoin users don’t get their coins stolen due to a bad PRNG; this should put things in better perspective.

If you need to generate some Bitcoin keys yourself, read() off /dev/urandom.  That’s what I do; see e.g. the sources of easyseed (forum thread).  If you run Core, then let Core do its job; there are Core developers who could run circles around me on this subject, and they pay careful attention to these issues.  (I don’t trust much other Bitcoin software; most of all, I explicitly distrust the popular save-a-webpage Javascript Bitcoin tools.)

Finally, please note:  I myself am not a cryptographer.  I wish to make that absolutely clear.  I am a programmer strongly oriented toward privacy and security; and I believe myself to be crypto-savvier than most.  I trust myself to tinker with my kernel’s PRNG—mostly because I know enough to know the limits of my own knowledge, so I know which parts of the code I must not touch.  I do trust myself to choose between cipher implementations; I do not attempt to write my own cipher implementations.  Likewise, wherever I feel my knowledge may be shaky on any subject, I will say so rather than risk giving you bad information.  I have already done so in this thread.

---

You refer to “modulo bias”.  It is one of those subtle DIY crypto dangers of which most people are totally unaware; props to you for even knowing about it.  I will later write another post explaining this, with a little quoted code snippet for avoiding the bias.


I tend to feel that way, too; but I recognize that it is a superstition, at least on properly designed and implemented system.  Your randomness generator should have two pertinent states, seeded and not seeded.  As soon as it reaches the former, it’s as good as it will ever get.⁰  Before that, it is in the latter state—and it should block, refusing to give any output.

Unfortunately, the Linux random/urandom system is not designed this way.  I am strongly critical of this.  Violating what I said above, the one time you should avoid using urandom instead of random is during or soon after the boot sequence.  urandom will give output, even when the generator as a whole has never been properly seeded.  This is only a concern if you run Linux.

---

0. I here wholly omit discussion of recovering from state compromise.  In the context of a kernel RNG of a running system, I am of the school of thought that this is somewhat ridiculous:  An attacker who can read your kernel’s internal state can probably grab your keys from userspace, too.  However, I may consider this opinion in view of Meltdown and Spectre; thanks for giving me the impetus to think it over.

1. Is this a good idea to generate random numbers with physical dice? I've heard that cheap gaming dice have poor quality of randomness, and if their sides are not a power of 2, you have to do some additional operations to remove bias when generating random bits.

2. Does quality of RNG that collects entropy becomes better with the system uptime - i.e. should I wait some time (while moving my mouse around and typing something?) before generating a new Bitcoin wallet after turning on my cold storage machine?

I do not trust - neither in someone else's god, nor in someone holding my private keys 

I am reading about entropy, especially in the bitcoin discussion, but not sure what is considered a good "value"  for entropy/randomness.
There is this thread from May 2017, which seems to indicate, that most modern unixoide systems have a good entropy. And of course I just checked my OSX and OpenBSD boxes, which show the expected (seemingly good) results.
How is this linked to bitcoin? Any hints?

I got the example and I really like and agree to your postings. You should be a merit source btw.
It is hard for our brains especially when it comes to very big numbers, so your pictorial explanations might help forum users a lot.
Btw. I guess since I was driving cars a lot in my life, I know about the forces included, but people really underestimate driving speed. That's true.

Assuming uniform distribution of the Hash160 (SHA256→RIPEMD160) output, each Bitcoin address can be spent by approximately 2⁹⁴ different keys.   (160+94=256)  There are numerous posts (indeed, entire threads) on this topic in the forum archives.  I regret that I don’t have any links handy.

Thus, te proper number to examine in this context is 2¹⁶⁰.  As I said above in this thread, that is on the order of 10⁴⁸.

Given that n addresses control spendable funds, where n is a number which can be determined from the public blockchain at any given point in time; and assuming that the n addresses are uniformly distributed throughout the 2¹⁶⁰ search space (viz. that people have working CSPRNGs); what you are asking is the probability of colliding with any of them, when you pick a new address randomly from a uniform distribution.

Working out the precise answer is left as an exercise to the reader.  A reader who is more solid with subtle statistical calculations than I am—I don’t want to give potentially bad information.

just as another thought on top:
and let's just assume, a collision was found - what is the probably that exactly this bitcoin address contains some spendable funds?

Glad to hear it.  It was just an example. The fact that your intuition didn't fail you in this one example is by no means proof that it will never fail you.

I infer to the point to be that you may risk your life on your intuition, when travelling in an automobile at x miles per hour.  But would you risk your Bitcoin on your intuition?  Perish the thought!

Well, the latter is exactly what you’d be doing if you were to cook up your own RNG based on intuition, “a little knowledge” (a dangerous thing!), or anything else other than studied expertise.

I was right by intuition.

This is why in my own post above, I specified, “with working random number generators”.  This is imperative for any cryptographic software of any kind; if you do not have a working CSPRNG, where the CS stands for Cryptographically Secure, then you have nothing else, either.


In my preferred kernel (FreeBSD), as of last time I read those portions of the code, the entropy harvester does not feed the PRNG an estimate of more than 1–2 bits of entropy for any hardware event.  I am of the school of thought that entropy estimation as a concept is problematic at best; but if and when it must be done, it must be done conservatively.

Estimating 10 bits of entropy off a single instance of any microsecond timer event seems suicidal to me.  Among other problems, this translates to an assumption that all precision below one millisecond in the timing of that event be completely unpredictable in all circumstances—even to unprivileged code running on the same CPU as handles the interrupt!

DannyHamilton is right:  The acquisition of cryptographically secure randomness is not only an expert domain, but a specialist expert domain which invokes both maths and physics.  Even professional mathematicians who are not cryptographers will probably get this wrong.  Almost all working programmers will get it wrong.  Once upon a time, the individual entrusted to maintain Debian’s vendored OpenSSL got it very, very wrong—causing a spectacular blow-up of most cryptography involving Debian systems from 2006–08.  Conventional wisdom gets an awful lot wrong.  There is a high probability (hah!) that you will get it wrong, too.

Worst of all, there is no certain means to prove that you got it right.  Statistical tests can easily demonstrate that a given bag of bits is not random; but no test can prove that one is.  Passing the DieHard suite (or similar) does not mean that your numbers are sufficiently random for cryptographic purposes.  The only way to be sure is to possess a deep theoretical knowledge matched by practical knowledge of real-world cryptanalytic attacks which target insufficiency of entropy.


Don’t take any chances with your randomness!

On Unix or Linux, read() off /dev/urandom; or use whatever special nonportable APIs may be offered to obtain randomness directly from the kernel (getrandom(), a special sysctl, etc.).  On other platforms, find the equivalent.  If writing a web application, use getRandomValues() (for most any current browser) or, if feasible, the generateKey method; then, pray to whatever gods you believe in that the browser is not too stupid.


Do not roll your own.  Do not conflate distinct meanings of the overloaded word “entropy”, then gather “entropy” the same measurements as taken by Panopticlick (!) (!!) (for Bitcoin!).  Also, do not roll your own using C’s rand(), e.g.:


Let that horror be a lesson.  For unless you have considerable specialist expertise, you cannot rely on your results being any better.  And I repeat:  If you do not have a working Cryptographically Secure PRNG, then you have nothing else, either.

Danny, speaking of things where people are non-intuitive, a interesting book if you haven’t seen it is The Undoing Project.

Which is why I specified in my example:
"a typical room"
and
"oxygen is RANDOMLY distributed throughout the room.  It is RANDOMLY bouncing off the walls, ceiling, other air molecules, and ourselves"

and I stated that I was talking about a situation where:
"EVERY POSSIBLE configuration of oxygen molecules in the room are EQUALLY possible"

You are talking about a non-typical room, where the distribution of the oxygen is no longer RANDOM (as it is being influenced directly by some industrial process) and most importantly you are talking about a situation where some configurations of oxygen molecules in the room are either impossible, or at least less likely than others.


Correct.  Private keys that are randomly chosen from the entire set of valid private keys are secure.  Private keys that are randomly chosen from a small definable subset of valid private keys can be VERY insecure.


Which is why it is generally a bad idea to try to reinvent cryptography on your own without a SIGNIFICANT amount of education, study, and expertise.  When it comes to maths and physics, what "feels intuitive" to someone that has a limited knowledge can often be COMPLETELY WRONG.

Slightly off topic for this thread, but related to our discussion about why it can be important to know the actual correct calculations:
Here's an example I recently heard about of how an intuitive feel for something that we ALL think we have good general knowledge of can be quite wrong...

Read the following and just think about this intuitively. This is not a "trick question", the answer just isn't as intuitive as most people might think it would be.

Assume a two lane road.
Assume two identical vehicles both traveling on the road in the same direction (one vehicle in each lane).
Assume that one vehicle is traveling at 70 miles per hour.
Assume the other vehicle is traveling at 100 miles per hour.

Assume that at the exact moment that the two vehicles are exactly next to each other, BOTH drivers simultaneously notice an obstruction up ahead that entirely blocks the road perpendicular to their direction of travel (in other words they both have exactly the same distance to travel at that moment before they will hit the obstruction).
Both drivers simultaneously hit their brakes and both apply the exact same maximum stopping force available to vehicle. Both vehicles are on identical surfaces and continue in a straight line towards the obstruction without any rotation of the vehicle.
The driver that was traveling at 70 miles per hour manages to stop within a fraction of a millimeter of colliding with the obstruction.
Which of the following is an accurate description of what happens with the vehicle that was traveling at 100 miles per hour:

The faster vehicle also stops before it collides with the obstruction
The faster vehicle collides with the obstruction and is traveling at a speed between 0 and 20 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed between 20 and 40 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed between 40 and 70 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed between 70 and 100 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed greater than 100 MPH when it collides.


Answer (copy/paste the following text or simply hit the "quote" button to read): Intuitively, most people that are very familiar with general concepts of driving and stopping a vehicle could easily rule out the first and last options. However, intuition from common experience will generally lead someone to believe that the vehicles will both lose 70 MPH of speed, resulting in the faster vehicle colliding at 30 MPH.  Some might realize that the faster vehicle has less time available to stop (since it is covering ground faster) and so they might guess between 40 and 70.  Surprisingly, the correct answer is that the faster vehicle is traveling between 70 and 100 MPH when it collides (approximately 71 MPH)

And yet there are (e.g. industrial) situations where exactly that can happen!

An analogous situation is when a random number generator isn't sufficiently random - the crypto seeds it generates may be a small population. The lack of randomness may have insidious causes, for example seeding the RNG with the microsecond timestamp of a keypress. But it may turn out that USB is polled at a rate derived from the same microsecond clock. You may think the timestamp has 10 bits of entropy, but it really only has 3. This may seem to generate unique seeds, but alas, they're not good enough.

Note, that the odds are not the same.  That is NOT an example of HOW UNLIKELY it is to encounter a private key collision.  It is just an example of WHY something can be considered to be "realistically impossible" even if it has a non-zero mathematical probability.

Yes it is possible to generate an existing seed. But hard. And it is harder to find a collision with a particular one.
If you want to know more about the odds, you can take a look at the birthday problem https://en.wikipedia.org/wiki/Birthday_problem.
You can also find someone who did the math here : https://download.wpsoftware.net/bitcoin-birthday.pdf

That is a very decent analogy. I might use that myself.

Theoreticians call this “possible”, because it is indeed possible in theory.  But your question cannot be adequately answered without focusing on the probability:  The precise reason why it is theoretically “possible” is that there is a nonzero probability.  To understand what that means requires discussing probabilities.

Humans generally have a problem grasping large numbers.  That is why comparisons are given, such as to the estimated number of atoms in the observable universe.  Otherwise, the reader may fail to grasp that the number is not only large:⁰  It is astronomically, unthinkably huge.

On a much smaller scale, this is also the failing which causes many people to buy lottery tickets—whereas a typical large-jackpot lottery typically has on the order of 10⁸ combinations.  N.b. that 10⁷⁷ is 10⁶⁹ times bigger than 10⁸.  This difference is itself so vast that it is difficult to explain in understandable terms.

The size of these numbers is why I must draw an important distinction:  Theoretically, it is possible for two people with working random number generators to pick the same keys.  However, in real-world, practical terms, such a thing is impossible.  The aforestated “nonzero probability” is so close to zero that we can safely ignore it.

Aside:

Terminology note:  You refer to 256-bit numbers.  Such numbers indeed have “64 hexadecimal” digits; but computers handle them in binary, that is to say, in bits. 

Also, you refer to a “seed”; I presume that you refer to Bitcoin’s private keys, which are 256-bit numbers.  A BIP 32 seed is 512 bits in total.

Most Bitcoin addresses (excepting the new P2WSH) have “only” 160 bits of substantial information.  Thus there are “only” on the order of 10⁴⁸ potential addresses of each other type (P2PKH, P2WPKH, P2SH).  That is still an astronomically large number.

If one billion Bitcoin users each generated one million addresses per second for the next thousand years, that would only come to on the order of 10²⁵ addresses.  Granted, at that point, the probability of a birthday collision in the 10⁴⁸ address space would be non-negligible.  I may consider that a long-term worry when there exist one billion Bitcoin users, each generating one million addresses per second—day and night.

---

0. My apologies to mathematicians who consider “huge” to start with Graham’s Number.  This discussion pertains to numbers so puny that they can be written in exponential notation.