Bitcoin Forum

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:


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':



How it works
--------------------------------------------------------------------
After re-reading this old thread (http://bitcointalk.org/index.php?topic=1514.0), 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.

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 .  :)

Awesome!

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

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.

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

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.

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.

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"   :)

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 (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 (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.

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 (http://bitcointalk.org/index.php?topic=4459.msg66810#msg66810) 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.

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.

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

ByteCoin

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.

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.

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...

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


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 ?

I have looked into this, and you do need the public key to break it. (Also I was wrong about Pollard rho being suitable, but the other two are.) Bitcoin does not reveal the public key until the tx is spent; only a hash is revealed until then. However the spending tx is vulnerable while moving through the network on its way to a block. A miner or peer could hold the transaction, break the key in 2^32 work, and substitute their own spend.

As far as the algorithmic details, here is baby step giant step. Public key Y, private key x, and generator G satisfy:

Y = xG

x is of the form s + k, where s is known salt and k is unknown 64 bits. Split k into left and right halves l, r:

k = l*2^32 + r

with l and r 32 bits. Then we have, substituting for x in the first eqn:

Y = (s + l*2^32 + r)G

Y + l(2^32(G_inv)) = (s + r)G

We precompute all 2^32 values of the RHS and store them in a hash table. Then we sequentially try the 2^32 values for l in the LHS and look for a match in the table. That gives us l and r, which gives us the private key x.

Yep, that works.
You still can't tell a scratchoff spend from a normal transaction, so assuming scratchoffs come in 50btc sizes, an attacker has to try that for every 50btc transaction he sees.
Of course attacker can also choose different time/space tradeoff (store 2**40 points, 2**24 add G + lookup ...).
Random idea: what if you make code->secret more costly, let's say pbkdf2-hmac-sha256 with 100k iterations?
that way a simple airthmetic lookup table wont work anymore, you'd have to pretty much create a few arbitrary pubkey->code functions and build rainbow tables.
as the tx really only needs to be secure enough to make it economically uninteresting to break it before it gets into a block (attacker needs to find privkey, create double-spend, get THAt into a block before the orig tx makes it into a block...).

Why is it 2 ^ 32 computations only ?
Shouldn't it be 2 ^ 64, since 64 bits are unknown ?

The scratch-card ECDSA private key generation algorithm is the following:

     password = random 64-1024 bits
     salt = user-supplied string, or "bitcoin" if salt is not supplied/zero-length
     pipe1 = SHA256(password, salt)
     pipe2 = SHA256(salt, password)

     for i = 0 to 108333
          pipe1_out = SHA256(pipe1)
          pipe2_out = SHA256(pipe2)
          pipe3_out = SHA512(pipe1_out + pipe2_out)
          pipe1 = first half of pipe3_out
          pipe2 = second half of pipe3_out

     raw ECDSA private key = pipe1

Patch and git updated with a new 'scratchoff' RPC, which will redeem a 'sendscratchoff' transaction.

The scratchoff system should now be minimally functional.  Because the hash of the public key is what is seen in the block chain, an attack should not better than brute force of the 64-bit random space.

Current limitations:

• scratchoff should immediately create a new transaction to claim the scratchoff, but it does not.  It only adds the initial spend, and the keys, to your wallet.  Internally, this requires selecting coins for the new transaction very specifically, which the current code does not easily support, unless I'm missing something.
• scratchoff requires full 256bit txid, not the truncated 32bit id returned by 'sendscratchoff'.  Operationally this is fine, but from a consumer-friendliness standpoint, we want to be able to lookup a transaction using as few digits as possible.  Internally, bitcoin stores using a btree, so this is possible, just not yet implemented.
• The 'toaccount' parameter is ignored.

The scheme could be further strengthened by adding brute force bits on top of 64.  Unfortunately, any scratch-off scheme is ultimately limited by what a consumer card might be reasonably expected to show.  Credit cards in the US have 4x 4-digit blocks, so I picked 4x 4-hex blocks == 64 bits.  Suggestions for increasing the bit count in a consumer friendly way are welcomed.

Correct. This is the implementation detail I mentioned. One would have to ensure that the public key had never been seen before so that only its hash and not the full public key would be visible.

To prevent precomputation, the 192 (or whatever) bits the user is not expected to type in should not be constant but should be derived from a hash of the user specified bits. I believe the implementation  by jgarzik already handles this.

The man-in-the-middle type attack Hal mentions on redeeming the voucher seems very costly and unreliable for the attacker.

ByteCoin

The modification to repeatedly hash the 64 bit password is a good idea, and should prevent square root attacks. I would probably have used a simpler iterative formula, but that one seems safe enough. SHA512 is notorious for speed variations on different architectures, but compared to the time to type in the password, that should be ok. Where does the magic number 108333 come from?

Largely arbitrary.  8333 is bitcoin's TCP port, and 100,000 was the number of iterations required for a single thread on my 3Ghz CPU to take a noticeable pause during computation.   :)  RFC 2898 suggested at least 1,000, and I thought 1,000 was far too low.

Thinking about some more modifications, though:

• Allow user to specify number of bits in password.  Range 64 - 256, must be divisible by 8.  Or perhaps as low as 57 bits (limit of 16 decimal digits), with some brute force to bring it up to 64.
• Allow user to specify optional plaintext string (salt).  Default is "bitcoin" if not supplied.  If no salt is supplied, due to limitations of what can be presented to the consumer, then the current minimal implementation stands as is, with 64 bits of brute force security.  However, if the scratchoff creator is able to communicate an additional string, be it an order id, or even "bitcoin.example.com", we can hash that at the beginning of key derivation, thereby getting much better security than 64 bits alone.

Can somebody explain to me why in the calculations 2 ^ 32 combinations is used instead of 2 ^ 64 for the unknown 64 bits ?

In jgarzik's original implementation, an attacker can pre-generate a rainbow table with 2^32 entries, and that lets them take a shortcut so they only have to try 2^32 bits for any particular scratch card (algorithm is, essentially, "foreach value in 2^32: do some complicated math, then see if the result matches a value in the 2^32-size rainbow table; if it does, you've found the unknown 2^64 bits").

Ah nice.

So IMHO that actually makes the scratchcards useless.
2 ^ 32 is virtually nothing for a 6990...

Using the algorithm i proposed earlier, all scratchcards can be easily broken in a reasonable time (t < 1 hour) using cluster of 6990's.

With the original algorithm, yes.  Not with the current, totally different algorithm.

This got me thinking. If the length of codes on a scratch-off card wouldn't have a limit, what would you put on it? My guess is: the full private key + the full txhash of the transaction that sends money to it.

This is two times 256 bits of data, plus maybe an 8 bit header and 32 bit crc, totalling 552 bits, or 95 base58 characters. With a bit of error-correction code, this is a 41x41 pixel QR code image. This seems quite reasonable.

In addition to that, a card could contain a shorter password/id combination like suggested in this thread, for those unable to read or type over the 95-character code. Maybe something like a website "Redeem your coins here!" after typing the id/password (since something would still need to do the lookup of the id, and you need to trust the issuer of the card anyway), could be linked to on the card as well.

I think it'd be really nice if it would become possible to physically give bitcoins to someone. It would correspond to what a (traditional) bank note was for gold, for bitcoin.

The patch/git and example at top-of-thread have been updated with several changes.  We are getting closer to a pull request.  Security parameters are now dynamic, offering a range of security modes, depending on available real world UI constraints, or lack thereof:

• Low security: 64 bit random password, no salt
• High security: 1024 bit random password, plus user supplied salt

...or any range of settings in between.  You could generate a 64-bit random password, then supply a 100 gigabyte salt string.

This is accomplished by the following changes:

• Key generation algorithm changed to init pipe1, pipe2 with variable-length password and salt.  See this updated post for details (http://bitcointalk.org/index.php?topic=4555.msg67719#msg67719).
• 'sendscratchoff' RPC now takes a JSON 'options' object, allowing the TX creator to specify range of bits (64-1024) and optionally supply a salt string (default "bitcoin" if not provided).
• 'sendscratchoff' RPC returns full txid (see example in top post).  JSON object return value "id" renamed to "txid".
• 'scratchoff' RPC takes optional salt string
• 'scratchoff' RPC now calls AddKey() to store key (fix for bug noticed by sipa)

The following to-do items remain before this can become a pull request:

• 'scratchoff' must create a transaction to spend the coin, not just store key/TX in wallet
• 'scratchoff' ignores 'toaccount' param
• 'scratchoff' requires full 256-bit txid, even though btree database enables lowering number of bits required to find tx significantly

Nevertheless, it should be working (famous last words).  You should be able to test with an empty wallet (thus guaranteeing you can spend the scratchoff coins), or on testnet.

If we are seriously considering putting this in the client, are there concrete plans to use this? Is someone committed to investing in making and selling scratchoff cards? Or is this patch useful for some other case that doesn't require such specialized equipment?

Once a client with this patch is available for download on bitcoin.org, I plan to sell scratch-off cards through CoinPal and delivered via US mail.  Those sales (glossing over details) are not subject to PayPal chargebacks, so I can remove purchase limits for them.  My cards won't require scratching since they'll just be postcards mailed in a secure envelope.

I think they are generally useful, as the topic of anyone-can-spend transactions comes up repeatedly.

I was thinking it would be useful to make a small service for redeeming scratch-offs, but no concrete plans have been laid.

I was looking into a possibility of giving my friends BTC gift certificates. This would not only be a great present, but also promote a project, since recipient will need to install client and get some understanding how the kitchen works.

I am not very comfortable with a bitcoin source code, but what about this idea: why encrypt private key at all? What needs to be done is: there should be an option that would:

- create a pub/private keypair (pair does not go into the wallet)
- initiate a transaction that sends X BTC to that keypair
- private key is returned inside JSON response

What you do next is: take returned value, make a QR code out of it, and viola, you can give this QR code as a gift certificate. Maybe, if designer is hanging around this forum, donate some gift card designs? Anyway, recipient should:

- scan QR code using a mobile phone
- initiate transaction, that moves the money from scanned key to her wallet.