DIY high quality entropy with low cost

[jl2012]

Targets:

1. DIY: A 10-year old child should be able to do it

2. High quality: true 256bit randomness

3. Human verifiable: using CCD noise or radioactive decay is not acceptable because it is difficult to verify the randomness

4. Low cost: cheap, not too time-consuming to generate a random number

----------

Procedures:

1. Buy a deck of at least 43 blank, name card sized, white paper cards. All cards should be perfectly same size

2. Pick a card, write "1" and "2" on it in this way:



3. Flip to the other side, write "3" and "4" in the same way

4. Pick another card, write "5", "6", "7", "8" in the same way

5. Repeat for totally 43 cards (1 to 172)

6. Put the cards into a big black bag

7. Shake the bag really really vigorously and randomly

8. Stake the cards without looking a them

9. Determine the "upper side" of the deck without looking at it. (To determine the upper side, there are 2 dimensions)

10. By the order of the cards, write down the numbers on the upper side

11. You have a sequence of 43 numbers with 261bit entropy. Do whatever you want with it



Permutation of 43 cards give you 175 bits, and the orientation of each card gives you 2 extra bits

-------------------

If you are able to find some perfectly square cards, you can reduce the number of cards to 38 by doing like this:



So each card will have 8 numbers on it.

Permutation of 38 cards give you 148 bits, and the orientation of each card gives you 3 extra bits. Totally you get 262 bits.

You can also do the same with 34 perfect octagon cards.

Having smaller number of cards will not only save you some time, but also make the shuffling easier and thus more random

-------------------

Why not standard playing cards? A full deck of 54 cards give only 237 bits, and more cards means more time to record the results

Other ideas are welcomed

[DeathAndTaxes]

Aren't you over thinking it. 

Deck of card ~226 bits of entropy.  You can buy one in just about any store.
Make your own four sided deck ~262 bits of entropy.   

Both are (way) beyond brute force.  The first is simple and straightforward.  The later requires constructing your own deck and a two dimensional shuffle.

[jl2012]

Aren't you over thinking it. 

Deck of card ~226 bits of entropy.  You can buy one in just about any store.
Make your own four sided deck ~262 bits of entropy.   

Both are (way) beyond brute force.  The first is simple and straightforward.  The later requires constructing your own deck and a two dimensional shuffle.

I'd like to minimize the number of cards. It could make a difference if more than a few high quality keys is needed.

[grue]

I'd like to minimize the number of cards. It could make a difference if more than a few high quality keys is needed.

A deck of cards has 52 cards, so you are saving... 9 cards. Is all that hassle worth it to make the deck a few mm thinner and a few grams lighter?

[railzand]

It's a brilliant educational tool, though, in the family or the classroom.

[gmaxwell]

Less efficient, but set membership is a bit harder to screw up:

Take N distinct cards, permute them at random (shake in a bag if you like), separate into two groups— you now have N bits (which set they ended up in).

This has a nice property that you can use it for ultra-fast key agreement: take a $2 drugstore pack of playing cards, shuffle well.. give the other person the other half. Nearly instant, computer free, minimal preparation, 52-bit shared secret.

[jonald_fyookball]

Less efficient, but set membership is a bit harder to screw up:

Take N distinct cards, permute them at random (shake in a bag if you like), separate into two groups— you now have N bits (which set they ended up in).

This has a nice property that you can use it for ultra-fast key agreement: take a $2 drugstore pack of playing cards, shuffle well.. give the other person the other half. Nearly instant, computer free, minimal preparation, 52-bit shared secret.

They should use that in a movie somewhere.

[jl2012]

I'd like to minimize the number of cards. It could make a difference if more than a few high quality keys is needed.

A deck of cards has 52 cards, so you are saving... 9 cards. Is all that hassle worth it to make the deck a few mm thinner and a few grams lighter?

This comparison is not fair as permutation of 52 cards just gives you 225 bits. You need 58 cards to make it just over 256. So 15 cards, or 25% is saved. It also means 25% of time is saved in recording of results. If you need many good random numbers that would make a difference

[DeathAndTaxes]

There is no conceivable scenario where 256 bits is needed and 225 bits is insufficient.  128 bits is beyond brute force.  One may want to hedge than some to compensate for possible biases but even 160 bits is fine.   If a standard deck was smaller that would be fine as well but since the extra bits don't hurt you might as well use them.  Most of the time comes from the explanation, getting the deck, and shuffling it just doesn't make sense to use less cards.  KISS.   Still if you came across a deck which was missing some cards it would still be good enough.   Even 41 cards (11 missing) gives 160 bits of entropy.

Bitcoin addresses don't have more than 160 bits of strength (only 128 bits if the PubKey is known) no matter how much entropy is used to create them.

If you need many good random numbers that would make a difference.

If you have one good random number you have multiple.  An HD wallet is an example of that.

[impulse]

Why don't you just flip a coin 256 times?

[dagi]

Why don't you just flip a coin 256 times?

+1
or dice ODD vs EVEN => 0 vs 1 
or create random photo and calculate hash of this file... easy
 

[jl2012]

Why don't you just flip a coin 256 times?

You could but it's extremely inefficient

[jl2012]

Bitcoin addresses don't have more than 160 bits of strength (only 128 bits if the PubKey is known) no matter how much entropy is used to create them.

For 160bits, you need 41 poker cards, or 29 rectangular cards as described in OP, or 26 square cards, or 23 octagonal cards

The less card you use, the easier to shuffle and thus better randomness.

If you have one good random number you have multiple.  An HD wallet is an example of that.

In some cases you want many independent random numbers.

Let say I am the boss of a company. I want to establish a long term bitcoin saving wallet. I don't want to trust my computer security officer or some black-box hardware wallet with my money. However, I have limited knowledge in computer. What I could do is to generate 10 random sequences by card shuffling, and use a specialized hardware wallet to turn them into 10 HD wallets. I will randomly choose 1 of the 10 wallets and lock it in a vault. I will also lock the hardware wallet in the vault.

I will hire several independent security experts to examine the remaining 9 random sequences and HD wallets. They will make sure the HD wallets are truly derived from the random sequences. Therefore, a malicious hardware wallet would have only 10% of chance to success.

(For more sophisticated users, they may verify the wallets by themselves using several different computers and clients)

Now my wallet is as safe as the vault. I may use multi-sig to further strengthen the security.

If we could standardize the procedure, any moderately educated person could generate a rock solid offline wallet. This is my real goal.

[Relnarien]

[content snipped]

That's such a costly and time-intensive method of generating verifiable randomness. You could achieve the same level of entropy by flipping through the cable channels and hashing the first ten TV shows and/or commercials that you see. I would even prefer just hashing two random pages from a random ebook than going through the trouble afforded by your method. I'm not saying that your method is bad, just that it's unnecessarily cumbersome.

[jl2012]

[content snipped]

That's such a costly and time-intensive method of generating verifiable randomness. You could achieve the same level of entropy by flipping through the cable channels and hashing the first ten TV shows and/or commercials that you see. I would even prefer just hashing two random pages from a random ebook than going through the trouble afforded by your method. I'm not saying that your method is bad, just that it's unnecessarily cumbersome.

No snake oil cryptography, thanks

[DeathAndTaxes]

If we could standardize the procedure, any moderately educated person could generate a rock solid offline wallet. This is my real goal.

If you think a standard will be built around users making a custom deck instead of using a standard deck of playing cards available just about anywhere in the world in order to save a few seconds well it is going to be an empty room.  

I mean your stated goals were:
1. DIY: A 10-year old child should be able to do it
2. High quality: true 256bit randomness
3. Human verifiable: using CCD noise or radioactive decay is not acceptable because it is difficult to verify the randomness
4. Low cost: cheap, not too time-consuming to generate a random number

A deck of playing cards is well understood, easily accessible, hackproof, meets all your criteria, and is the simplest solution to the problem.   Still I think your mind is made up.   I can safely say though that no wallet is going to adopt a system based on custom cards over the simpler more accessible solution.

[jl2012]

If we could standardize the procedure, any moderately educated person could generate a rock solid offline wallet. This is my real goal.

If you think a standard will be built around users making a custom deck instead of using a standard deck of playing cards available just about anywhere in the world in order to save a few cards well it is going to be an empty room.  Still I think your mind is made up so I will leave you to it.

You are possibly right, but the problem of playing cards is the lack of universally recognized name and order of the cards. Arabic number is a truly universal language. You may, of course, write 1-54 on each card, but then why don't you buy a deck of white card as I suggest?

By the way, the most efficient way to use playing cards to generate 160 bit entropy is to pick 31 out of 52. That will give you 160 bit (₅₂P₃₁). It still takes 31 cards with the 2 Jokers are used.

[QuantumQrack]

Or just use this:

http://ubld.it/products/truerng-hardware-random-number-generator/

[jl2012]

Or just use this:

http://ubld.it/products/truerng-hardware-random-number-generator/

It is not possible, at least not easy, to verify its credibility

[QuantumQrack]

Or just use this:

http://ubld.it/products/truerng-hardware-random-number-generator/

It is not possible, at least not easy, to verify its credibility

Its been tested with RNG testing software such as Die Harder. (and others)