[PATCH] bitcoin scratch-off cards

[jgarzik]

This patch adds the "sendscratchoff" RPC call, which creates transactions that are an electronic attempt at scratch-off cards:

     http://yyz.us/bitcoin/patch.bitcoin-scratch-card
     or git://github.com/jgarzik/bitcoin.git#scratch-card

To create a scratch-off card for 0.82 BTC from the 'master' account via JSON-RPC:

Code:

$ bitcoind sendscratchoff master 0.82 '{ "bits" : 64, "salt" : "myawesome.com" }' 1 "my awesome scratch-off"
{
    "txid" : "4a16969aa4764dd7507fc1de7f0baa4850a246de90c45e59a3207f9a26b5036f",
    "password" : "719d17195638f937"
}

And presumably you will have a fancy print-out or display saying

     Redeem this card for 0.82 bitcoins!
     card# 4a16 969a
     presented by: myawesome.com
     password 719d 1719 5638 f937

Some time later, the holder of this card may redeem their 0.82 BTC with another new RPC 'scratchoff':

Code:

$ bitcoind scratchoff 4a16969a 719d17195638f937 "myawesome.com"
994dd0219f6dea648a6d5f8d33850114a2a0787e136a36e8b24ccafcd6ff0e59
               ^^^ transaction that "claims" the scratch-off card

How it works
--------------------------------------------------------------------
After re-reading this old thread, a discussion on IRC led ArtForz to note that ByteCoin suggested a way to create bitcoin scratch-off cards within a standard transaction.  Unless I've totally bollock's up the works, which is entirely possible, here's how it works:

• Our EC private keys are 256 bits
• Generate 64-1024 random bits (def. 64) -- this is your scratch-off password
• Perform a great many rounds of hashing the password, and a user-supplied salt string (default "bitcoin"), to produce 256 bits of data
• Create EC keypair with the resultant 256 bits of post-hash data
• Create transaction, sending n.nn BTC to the hash of the EC public key
• Return 32 bits of transaction hash ("id") and scratch-off password ("password") via JSON-RPC

To redeem a scratch-off,

• Retrieve transaction by looking up N bits of the transaction hash ("txid")
• Build raw 256-bit private key, through many rounds of hashing the password ("password") and salt ("salt")
• Create EC keypair from raw private key
• Verify transaction output's pubkey hash matches EC pubkey hash
• Add EC keypair and scratch-off TX to local wallet
• Create transaction that sends bitcoins from scratch-off TX to a new key in your own wallet, thereby "claiming" the card.
• You may now spend those bitcoins, once your claim is confirmed (requires at least 1 confirmation by default)

Because this is an entirely normal transaction, willingly relayed by all existing clients, no outside observer will know that this spend is a scratch-off card, rather than a regular spend to a regular bitcoin address.

Variations:

(1) Use decimal digits instead of hexidecimal, for id and password.  More consumer friendly.  Requires a small amount of brute forcing, if one limits the password to 16 digits, to recover the lost bits.

(2) If you have a full block chain, and EC pub/private keys, the transaction hash ("txid") is optional.  One could simply scan the block chain for an unspent transaction to the given bitcoin address (derived from the password).

Credit for all bugs goes to me.  Credit for the ideas goes to bytecoin, art, theymos and the authors of RFC 2898.

EDIT: Updated to reflect changes through March 23.

[Anonymous]

Im thinking this could be  the most awesome iphone or android  app.

Someone sends you a card or you purchase one.

Using a touch screen you simply swipe your finger like you are rubbing a physical scratch card . 

[theymos]

Awesome!

How long does it take to break an ECDSA key with only 64 bits of unknown key?

[mndrix]

This is excellent and very clever!  I'm not competent to speak to the implementation details, but I'd love to use this feature at CoinPal.  I could eliminate purchase limits for customers choosing scratch-off card delivery in the mail.

[ByteCoin]

How long does it take to break an ECDSA key with only 64 bits of unknown key?

As very nearly every 256bit number is a valid secp256k1 private key, there's no reason to imagine (off the top of my head) why there should be any attack faster than brute force.

Note to self: I have thought of a possible implementation detail that would need to be taken care of in order to stop a birthday paradox attack. Details when I have time.

ByteCoin

[theymos]

When I mentioned the idea of exposing part the private key to the people on ##crypto on Freenode (at the time when I wrote my scratch-off thread), they were very opposed to the idea.  They seemed to think that security would be significantly decreased.

Probably the cost of performing any attack would be higher than the actual value of the scratch-off transaction, though.

[Hal]

It's not safe to have only 64 bits of the private key be unknown. This can be broken in 2^32 work using such algorithms as baby step giant step, Pollard rho, or the kangaroo.

[jgarzik]

When I mentioned the idea of exposing part the private key to the people on ##crypto on Freenode (at the time when I wrote my scratch-off thread), they were very opposed to the idea.  They seemed to think that security would be significantly decreased.

Would be interesting to have more specific criticisms, now that code's out there.  The main question, as ByteCoin indicated, is whether or not there is an attack that is faster than brute force, if you know a portion of the private key.

As the Variations section hints, the implementation presented was the most simple to implement, not necessarily the most consumer friendly or the most secure.  When deploying this into production, should it make it into the bitcoin client, I would do a couple things, such as

• require some level of brute forcing for all redemptions (have bits neither in well-known private key subset, or the password)
• ship 1,000 well-known 192-bit private key subsets

Each valid redemption would therefore require some amount of brute forcing, while an attacker has a lot of work to do comparatively -- they have to first recognize a scratch-off from a normal spend, in the block chain.  Then they would have to find the remaining ~64+ bits of private key, having only the public key (or a hash thereof) as a starting point.

I readily admit I am no cryptographer or math genius, though!   Hopefully the future will bring more substantive criticisms from #crypto than "exposing part of private key leaves me vaguely unsettled"  

[Stephen Gornick]

I learned of the publication: "Organic Electronics on Banknotes" from the following article:
  http://www.newscientist.com/article/mg20827915.200-banknotes-go-electric-to-outwit-counterfeiters.html


The publication is at:
  http://onlinelibrary.wiley.com/doi/10.1002/adma.201003374/abstract
  To purchase a 24 hour pass for reading the PDF is $50.


I wrote one of the authors asking if the technology is rewritable, ... thus a note could be re-used after it was spent.  I'll share here if I learn any more on it.  It is not used yet anywhere, however, as far as I know so this is not something that would likely be rolled out anytime soon but I wanted to share what I had come across.

[theymos]

It's not safe to have only 64 bits of the private key be unknown. This can be broken in 2^32 work using such algorithms as baby step giant step, Pollard rho, or the kangaroo.

Too bad. I guess OP_DROPing an AES-encrypted private key is the safest method.

[jgarzik]

It's not safe to have only 64 bits of the private key be unknown. This can be broken in 2^32 work using such algorithms as baby step giant step, Pollard rho, or the kangaroo.

Too bad. I guess OP_DROPing an AES-encrypted private key is the safest method.

If we are creating new transaction types, a far more elegant approach can be had...  a new 'anybody can claim' transaction added to the client could be made more secure and elegant, but at the disadvantage of being easy to spot in the block chain, and therefore a more likely target for attack.

[ShadowOfHarbringer]

It's not safe to have only 64 bits of the private key be unknown. This can be broken in 2^32 work using such algorithms as baby step giant step, Pollard rho, or the kangaroo.

So if i understand correctly, in the original scenario, 192 bits of private key would be publicly known, and only 64bit would stay secret ?

[jgarzik]

It's not safe to have only 64 bits of the private key be unknown. This can be broken in 2^32 work using such algorithms as baby step giant step, Pollard rho, or the kangaroo.

So if i understand correctly, in the original scenario, 192 bits of private key would be publicly known, and only 64bit would stay secret ?

That's how my patch is implemented, yes.

You can make it stronger by, say, having 1000x 176 bits of well known private key, 64 bit password, and 16 bits of brute force required to redeem.

[ByteCoin]

It's not safe to have only 64 bits of the private key be unknown. This can be broken in 2^32 work using such algorithms as baby step giant step, Pollard rho, or the kangaroo.

It's not immediately obvious to me that this is possible. Please go into details about how it would be done.

ByteCoin

[ShadowOfHarbringer]

It's not safe to have only 64 bits of the private key be unknown. This can be broken in 2^32 work using such algorithms as baby step giant step, Pollard rho, or the kangaroo.

So if i understand correctly, in the original scenario, 192 bits of private key would be publicly known, and only 64bit would stay secret ?

That's how my patch is implemented, yes.

You can make it stronger by, say, having 1000x 176 bits of well known private key, 64 bit password, and 16 bits of brute force required to redeem.

OK, but the potential attacker would still have to brute force the private key based on the public key... Hmmm seems fairly easy to do, if you know which of the keys it is.

So i'm thinking..... to perform an attack, we need to do the following:

1. Get all receiving addresses (public keys) [PK] used in last hour on the network.
2. Foreach of [PK] (public keys), do
      - Perform 2 ^ 64 tries to generate [PRK] (private keys) starting with the first 192 bits
      - Foreach [PRK], do
             - Generate public key (BTC address) [GPK] from [PRK]
             - Check if the [GPK] matches [PK]

So it seems that as long as there isn't many transactions on the network to check, this should be fairly computable opreration by perhaps.... few 5Tflop-Radeon 6990's ?.

Somebody correct me if I am reasoning wrong.

[ShadowOfHarbringer]

The total number of possible private keys is:
2 ^ 64 = 18 446 744 073 709 551 616 = ~1,84 x 10 ^ 19

Assuming we can check trillion combinations in one second, we have :
18 446 744 073 709 551 616 / 1 000 000 000 000 = 18 446 744,074 seconds , which makes 5124 hours = 213 days (to check a single receiving address / pubkey).

I would say this is not safe enough. A Radeon6990 - based supercomputer or cluster (doing millions of trillions operations per sec) could possibly do it in a reasonable time.
Unless, the scratch cards would only be guaranteed to work for a limited time, and would only be used for small amount of cash, like under $10000.

Perhaps number of unknown bits should be increased to 72 or 96 - that would make this method safer.

[jgarzik]

Assuming we can check trillion combinations in one second, we have :
18 446 744 073 709 551 616 / 1 000 000 000 000 = 18 446 744,074 seconds , which makes 5124 hours = 213 days (to check a single receiving address / pubkey).

I seriously doubt you can get anything close to checking a trillion combinations per second on any modern GPU.

[ShadowOfHarbringer]

Assuming we can check trillion combinations in one second, we have :
18 446 744 073 709 551 616 / 1 000 000 000 000 = 18 446 744,074 seconds , which makes 5124 hours = 213 days (to check a single receiving address / pubkey).

I seriously doubt you can get anything close to checking a trillion combinations per second on any modern GPU.

Obviously, not on a single one....
But what about 1000, 5000 or 10000 ?

Anyway, that seems still too dangerous to me... I would not dare to use scratch cards for a bigger sum of money.

EDIT:
But have you though about what will happen if they generate raninbow tables for it ?
For a such small amount of computations, rainbow tables could be created (using a botnet for example), and then every combination could be broken within seconds...

[jgarzik]

Assuming we can check trillion combinations in one second, we have :
18 446 744 073 709 551 616 / 1 000 000 000 000 = 18 446 744,074 seconds , which makes 5124 hours = 213 days (to check a single receiving address / pubkey).

I seriously doubt you can get anything close to checking a trillion combinations per second on any modern GPU.

Obviously, not on a single one....
But what about 1000, 5000 or 10000 ?

Anyway, that seems still too dangerous to me... I would not dare to use scratch cards for a bigger sum of money.

I doubt anyone would use a scratch card for a large sum of money.

But have you though about what will happen if they generate raninbow tables for it ?

Think of this as a 192-bit salt.  It is well known how to use multiple salts.

[ShadowOfHarbringer]

But have you though about what will happen if they generate raninbow tables for it ?

Think of this as a 192-bit salt.  It is well known how to use multiple salts.

But how can salt work if it is publicly known ?
Or am i understanding something incorrectly ?