How is the Seed generated?

[Bitcoin++]

The computer needs some input key to generate the seed, right?

Do you know how/where it finds the input key? A very simple function could use the computer's clock, but that would obviously be easy to replicate. A hacker could generate the same seed as someone else and steal his bitcoins.

I'm sure the Electrum developers have done an excellent job in making such an attack impossible. I'm just curious about how it is done.

[dabura667]

https://github.com/spesmilo/electrum/blob/5d9b9492e16fce6c61332dd1cc3a37978a033ad1/lib/wallet.py#L1692

Uses ECDSA's randrange function. (through the random_seed function in bitcoin.py)

[Bitcoin++]

ok, I had a look at the code but it went a bit over my head 

With TrueCrypt for example you are required to move the pointer around the screen for a while. It is impossible to replicate this, which guarantees a unique input key. Since Electrum does not have such a feature, it must have some other input which is impossible to replicate. I just don't understand how the programmers solved this problem.

[dabura667]

Ask the people who made the Python implementation of ECDSA.

To put it in perspective, ECDSA is a tool that was made by someone else, electrum just imports that tool and uses one of its functions.

If you look into the python version of ECDSA, you can find out the details if you want.

[Bitcoin++]

This thread clarified a little bit
https://bitcointalk.org/index.php?topic=153990.0

"...I wanted to give a little margin in case your system does not have a high-quality entropy pool at creation time"

http://stackoverflow.com/questions/19981189/how-does-the-kernel-entropy-pool-work

"..."the kernel entropy pool". Apparently it relies on keyboard timings, mouse movements, and IDE timings."

So I guess the ECDSA, or more precisely the Python implementation of ECDSA, gathers the key input from the entropy pool. Is this is how all bitcoin applications, Electrum included, do it?
I'd be happy to see a video or an article where someone explains it. 

[dabura667]

So I guess the ECDSA, or more precisely the Python implementation of ECDSA, gathers the key input from the entropy pool. Is this is how all bitcoin applications, Electrum included, do it?
I'd be happy to see a video or an article where someone explains it.  

For the OldWallet implementation, as well as the NewWallet implementation of the seed generation, it uses the randrange function from ecdsa. (the file is util.py)

OldWallet is the seed generation used currently, and it routes through the random_seed function in bitcoin.py

From the ecdsa implementation packaged with the 1.9.7 tar.gz

Code:

def randrange(order, entropy=None):
    """Return a random integer k such that 1 <= k < order, uniformly
    distributed across that range. For simplicity, this only behaves well if
    'order' is fairly close (but below) a power of 256. The try-try-again
    algorithm we use takes longer and longer time (on average) to complete as
    'order' falls, rising to a maximum of avg=512 loops for the worst-case
    (256**k)+1 . All of the standard curves behave well. There is a cutoff at
    10k loops (which raises RuntimeError) to prevent an infinite loop when
    something is really broken like the entropy function not working.

    Note that this function is not declared to be forwards-compatible: we may
    change the behavior in future releases. The entropy= argument (which
    should get a callable that behaves like os.entropy) can be used to
    achieve stability within a given release (for repeatable unit tests), but
    should not be used as a long-term-compatible key generation algorithm.
    """
    # we could handle arbitrary orders (even 256**k+1) better if we created
    # candidates bit-wise instead of byte-wise, which would reduce the
    # worst-case behavior to avg=2 loops, but that would be more complex. The
    # change would be to round the order up to a power of 256, subtract one
    # (to get 0xffff..), use that to get a byte-long mask for the top byte,
    # generate the len-1 entropy bytes, generate one extra byte and mask off
    # the top bits, then combine it with the rest. Requires jumping back and
    # forth between strings and integers a lot.

    if entropy is None:
        entropy = os.urandom
    assert order > 1
    bytes = orderlen(order)
    dont_try_forever = 10000 # gives about 2**-60 failures for worst case
    while dont_try_forever > 0:
        dont_try_forever -= 1
        candidate = string_to_number(entropy(bytes)) + 1
        if 1 <= candidate < order:
            return candidate
        continue
    raise RuntimeError("randrange() tried hard but gave up, either something"
                       " is very wrong or you got realllly unlucky. Order was"
                       " %x" % order)

Electrum feeds in 128 bytes for the "order" variable in the function (160 for NewWallet, not yet actually used), and entropy is left default.

This triggers the first if, setting the entropy function as os.urandom.

It then checks to make sure the order value is greater than 1.

Then basically, it attempts at the most 10,000 times to return those 128 bytes of entropy created by os.urandom, converted to number plus 1.

If the candidate is greater than or equal to 1 and less than the order given (which is the highest value for the number of bytes, in this case 128) it returns the candidate.

So in the end it comes out to the question: Do you trust os.urandom? This is the entropy function of python, so if it wasn't cryptographically secure, a LOT of applications not even remotely related to bitcoin would be compromised.

But yeah, hey, if you want to write a pull request that takes mouse movements and includes them into the seed generation, I'd use it.

[DeathAndTaxes]

This thread clarified a little bit
https://bitcointalk.org/index.php?topic=153990.0

"...I wanted to give a little margin in case your system does not have a high-quality entropy pool at creation time"

http://stackoverflow.com/questions/19981189/how-does-the-kernel-entropy-pool-work

"..."the kernel entropy pool". Apparently it relies on keyboard timings, mouse movements, and IDE timings."

So I guess the ECDSA, or more precisely the Python implementation of ECDSA, gathers the key input from the entropy pool. Is this is how all bitcoin applications, Electrum included, do it?
I'd be happy to see a video or an article where someone explains it.  

To clarify further this doesn't have anything specifically to do with ECDSA.  The ECDSA library isn't creating the random numbers it is using the random numbers.  Random numbers are used in lots of applications (including ECDSA).  The random values are being taken from the OS level PRNG (pseudo random number generator) implementation.  PRNGs are always deterministic (you can't make a deterministic computer produce random events) that means for a given seed it will produce the same sequence of values.  However the PRNG is seeded with entropy by the OS from chaotic inputs (like keyboard and mouse movements, drive latency, least significant digit of CPU temp reading, etc).  http://en.wikipedia.org/wiki/Entropy_(computing)

If the implementation is valid, then the numbers are secure.  If it isn't then they are (see flawed k values on Android OS as an example).  If electrum allows manually entering a seed you could always roll a lot of dice (or flip a whole lot of coins).  Your other option would be a TRNG (true random number generator) a hardware device which either samples chaotic environmental values (i.e. atmospheric radio noise) or observes a quantum event (i.e. time between radioactive decays).

If you have more than one source of random values and are paranoid that they may not actually be random you can combine them using XOR which can only increase entropy.  As an example if the OS provided the 256 bit random value:
e3c0b6f6383908e5df7c944070f893

and you obtained from a TRNG or a service like random.org the 256 bit random value:
54e599c6d9aa57a56571b3aef76ec8

Now you aren't completely sure that either number has sufficient entropy (a reproducible value has 0 entropy) by XOR the values together the entropy of the new value is at least the entropy of the higher entropy value (and possibly more).

Code:

e3c0b6f6383908e5df7c944070f893 = 010101001110010110011001110001101101100110101010010101111010010101100101011100011011001110101110111101110110111011001000
54e599c6d9aa57a56571b3aef76ec8 = 111000111100000010110110111101100011100000111001000010001110010111011111011111001001010001000000011100001111100010010011

010101001110010110011001110001101101100110101010010101111010010101100101011100011011001110101110111101110110111011001000
111000111100000010110110111101100011100000111001000010001110010111011111011111001001010001000000011100001111100010010011
-------------------------------------------------------------------------------------------------------------------------------------------
101101110010010100101111001100001110000110010011010111110100000010111010000011010010011111101110100001111001011001011011

The XOR (exclusive or) of the two values is b7252f30e1935f40ba0d27ee87965b

Even if one value is known and reproducible (due to flaw or backdoor) the XOR of two values is not (known XOR unknown = unknown).  Now if both sources are conspiring against you well then you are screwed but at that point I think it is time to give up or build your own quantum random number generator.

[Bitcoin++]

The random values are being taken from the OS level PRNG (pseudo random number generator) implementation.  PRNGs are always deterministic (you can't make a deterministic computer produce random events) that means for a given seed it will produce the same sequence of values.  However the PRNG is seeded with entropy by the OS from chaotic inputs (like keyboard and mouse movements, drive latency, least significant digit of CPU temp reading, etc).

Very well explained. Thank you.

This leads me to a related question. It's been recommended to use an offline computer with Electrum to generate a paper wallet (at least if you have a large fortune of bitcoins). Often this would mean an old computer that you had stacked away. I can imagine that these have terrible PRNG, hence an attacker can try to replicate these not-so-random inputs?

[Abdussamad]

The random values are being taken from the OS level PRNG (pseudo random number generator) implementation.  PRNGs are always deterministic (you can't make a deterministic computer produce random events) that means for a given seed it will produce the same sequence of values.  However the PRNG is seeded with entropy by the OS from chaotic inputs (like keyboard and mouse movements, drive latency, least significant digit of CPU temp reading, etc).

Very well explained. Thank you.

This leads me to a related question. It's been recommended to use an offline computer with Electrum to generate a paper wallet (at least if you have a large fortune of bitcoins). Often this would mean an old computer that you had stacked away. I can imagine that these have terrible PRNG, hence an attacker can try to replicate these not-so-random inputs?

Why would it matter if the computer was online or not? PRNG is implemented in software specifically the operating system. You can install the same OS on an offline computer as you can on an online one.

[DeathAndTaxes]

This leads me to a related question. It's been recommended to use an offline computer with Electrum to generate a paper wallet (at least if you have a large fortune of bitcoins). Often this would mean an old computer that you had stacked away. I can imagine that these have terrible PRNG, hence an attacker can try to replicate these not-so-random inputs?

It is a possible risk but as pointed out one can install a modern OS on older hardware.   The PRNG in Windows XP (and 2000) is one notable example of a flawed implementation.
http://en.wikipedia.org/wiki/Random_number_generator_attack#Prominent_examples

The bad thing about PRNG is that in most cases they don't fail like they did in the Android exploit, that would be the reuse as the exact same number, which is immediately obvious.  On the contrary they tend to fail in ways that may not be immediately detectable but still undermine the security of the cryptosystem which is relying on it.  A key which is 512 bits in length but drawn from a source with only 64 bits of entropy is no stronger than a 64 bit key.  It would produce an output which in most instances would appear random and uniformly distributed (all values in a set have equal chance of occurring) but could be brute forced relatively easy by someone who knew the flaw and limited the scope of their attack to the reduced range as opposed to the entire 512 bit keyspace.

[Yuki1988]

This leads me to a related question. It's been recommended to use an offline computer with Electrum to generate a paper wallet (at least if you have a large fortune of bitcoins). Often this would mean an old computer that you had stacked away. I can imagine that these have terrible PRNG, hence an attacker can try to replicate these not-so-random inputs?

It is a possible risk but as pointed out one can install a modern OS on older hardware.   The PRNG in Windows XP (and 2000) is one notable example of a flawed implementation.
http://en.wikipedia.org/wiki/Random_number_generator_attack#Prominent_examples

The bad thing about PRNG is that in most cases they don't fail like they did in the Android exploit, that would be the reuse as the exact same number, which is immediately obvious.  On the contrary they tend to fail in ways that may not be immediately detectable but still undermine the security of the cryptosystem which is relying on it.  A key which is 512 bits in length but drawn from a source with only 64 bits of entropy is no stronger than a 64 bit key.  It would produce an output which in most instances would appear random and normally distributed (all values in a set have equal chance of occurring) but could be brute forced relatively easy by someone who knew the flaw and brute forced that limited range as opposed to the entire 512 bit keyspace.

Shouldn't it be uniformly distributed instead?

[DeathAndTaxes]

Shouldn't it be uniformly distributed instead?

Yes.  Fixed.

[jonald_fyookball]

It is a possible risk but as pointed out one can install a modern OS on older hardware.   The PRNG in Windows XP (and 2000) is one notable example of a flawed implementation.
http://en.wikipedia.org/wiki/Random_number_generator_attack#Prominent_examples

Is this risk mostly just theoretical about using an old Windows XP offline machine?

The original paper discussing WindowsRNG is here: http://eprint.iacr.org/2007/419.pdf
  
I didn't read this entire paper, but skimming it reveals that WRNG starts with 3584 bytes of
system entropy.

It also seems to be pointing out weaknesses that would be
exploitable only if one were to be able to determine the state at a given time.  
I don't see how someone would be able to use this to steal your electrum
seed  (but again, I only studied this paper for 5-10 minutes)

[Ibian]

If cpu temp, mouse input etc is what makes the seed, would it be less secure to use a new laptop for an offline installation than a several years old one?

[jonald_fyookball]

I fail to see the connection between age of hardware and the entropy.

[DeathAndTaxes]

I fail to see the connection between age of hardware and the entropy.

There isn't (or shouldn't) be one, with any properly designed entropy pool.  I can only assume that Ibian believes that for example a newer system temp would be more consistent and predictable but that isn't a factor.   Selection of entropy needs to be carefully done so as an example you wouldn't use the entire cpu temp value (which is periodic and not a uniform distribution) and instead use the sub degree values.

So for example 82.77 only the 77 would be added to the entropy pool.   Is a new computer more or less likely to have temps which are xx.77?  That is the kind of decision making that needs to go into entropy extraction. 

[jonald_fyookball]

Enlightening as usual, DT.  Care to comment on my previous comment? It was meant more as a question than a conclusive analysis on WRNG weakness.

[DeathAndTaxes]

Enlightening as usual, DT.  Care to comment on my previous comment? It was meant more as a question than a conclusive analysis on WRNG weakness.

My understanding is that if the attacker doesn't know the state of the PRNG either at the time the seed is generated or prior to the seed being generated then there is no risk.   If the attacker does then it is not beyond brute force to compute the state and thus seed at the time it is generated.   That being said it is a very old vulnerability on an obsolete OS.  Windows XP should not be used any more but if it is, the vulnerability could be patched.  I am going from memory here so someone should do there own research but this flaw was patched in SP1 so even a clean install using SP1 media would be immune to this attack. 

[Abdussamad]

If cpu temp, mouse input etc is what makes the seed, would it be less secure to use a new laptop for an offline installation than a several years old one?

Age of hardware doesn't matter as far as seed generation goes. Note that electrum's seed is just 128 bits. That is a very small amount and you can always generate that many random bits. So it's not something you should worry about:

https://bitcointalk.org/index.php?topic=167276.msg1763759#msg1763759

Age of hardware does matter as far as reliability goes. Older hardware tends to be less reliable, so take that into account as well.