[PATCH] bitcoin scratch-off cards

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

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

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.

[ArtForz]

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

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

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

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.

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

[jgarzik]

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

[jgarzik]

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.

[ByteCoin]

I have looked into this, and you do need the public key to break it.

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

[Hal]

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?

[jgarzik]

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.

[ShadowOfHarbringer]

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?

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

[Gavin Andresen]

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

[ShadowOfHarbringer]

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.

[jgarzik]

So IMHO that actually makes the scratchcards useless.

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

[Pieter Wuille]

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.

[jgarzik]

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

[Hal]

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?

[mndrix]

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.

[jgarzik]

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.

[coga]

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.