Topic: Off-chain anonymous transactions by secure transfer of private keys - page 2. (Read 17282 times)

No, Eternity's right, we could theoretically look at our proxy to see the (encrypted) traffic between parties. We could see who's transferring to whom. However, the actual transaction is encrypted with a negotiated key (Diffie Hellman exchange), so we can't see that.

So yes, using our proxy makes things a little less private - but remember, you're coming from Bitcoin transactions where _everything is public_. In a Bitcoin transaction _everybody_ knows who you're paying, in a proxied OtherCoin transaction we could theoretically know who you're paying (but not to what address and how much). And in OtherCoin you have the option to just pay in person using NFC or QR codes or SMS (although you could say SMS goes through the wireless operator, so they would know that you're paying someone).

The proxy is there for convenience and is optional, it doesn't automatically push the data through us - there's a button that you need to press to upload the data to our proxy. It makes things easier for transactions with remote users if you choose to use it.

I don't understand what you mean.  Which server are you talking about?   Drazvan's system doesn't rely on a 3rd party server,  it is a private key exchange between two people.

Perhaps you could use denominations based on binary,  ie: 10uBTC, 20uBTC, 40uBTC, 80uBTC,.... .  To cover the 10e6 fold range from 10uBTC to 10BTC you only need a maximum of 20 keys if you sum it the most efficient way.  (I started at 10uBTC to allow for transactions such as paying for reading an item of news from a web-site, or paying to get change from an internet change site , etc.)

Is twenty keys too many for a QR code?

Of course most people would have trouble working out how to represent arbitrary amounts in binary but the phone/computer would do this behind the scenes anyway.  All they would really need to know is the total amount they hold while the computer handles using the correct change in a transaction.   By default you could just have their total displayed with a option to display a summary of the holdings of each denomination and a further option to show the details of each individual coin's key/wallet.

Each time a person engages in a transaction their phones could automatically negotiate with each other to top-up with any coins they need if one has excess in some denominations but shortage in others  (the phone could even monitor the owner's usage pattern over time and determine their most commonly used denominations and build up a store of them).  This would lessen the need for people to use 3rd party online change services.

Ok, I have a little bit of a dilemma: if we move to multiple OtherCoin denominations, each transaction would mean a transfer of multiple private keys (each key being 32 bytes secret on-card part and another 32 bytes known by the Android app). So it's 64 bytes/key. If we go all the way down to 0.1mBTC and assume people won't pay more than 10 BTC through the system (probably a safe bet at first), the maximum number of coins would be transferred when you pay 9.9999 BTC (45 keys, that's about 3 kilobytes including protocol overhead). That's a little too much for QR codes and could become a problem even for SMS chaining. It could be sent over NFC and over the Internet.

We could go with animated QR codes but I've used those before (I wrote this: www.visualbtc.com) and they're not exactly easy to use. So I wonder if I should drop QR codes altogether and keep SMS and Internet and NFC comms. SMS might be tricky (or expensive) for large transfers, it already uses concatenated messages but still, those are up to 140 bytes (160 characters) each, so you would need 20 or more to send a 45 key transfer. I've already implemented a small server that OtherCoin apps can send the info through (it's just a relay type of system, nothing fancy). Of course, QR codes and SMS have the advantage of not requiring and Internet connection, but we're going to need one anyway to split coins and do BTC transfers anyway.

Any thoughts would be appreciated. Thank you!
Razvan

That sounds like a good idea - although I'm not sure a web service is needed to do the change. If you want to split 1 BTC into 10 * 100mBTC or 100 * 10mBTC you can always go through Bitcoin (that is redeem a 1 BTC OtherCoin, then feed the balance into 10 or 100 smaller OtherCoins).

A web service could be useful though for premium services - that is the ability to split a larger coin into smaller ones without advertising this on the Bitcoin network and also getting confirmed or balance certified coins in return. So you would give the service your 1 BTC OtherCoin and it would give you 10 * 0.1BTC OtherCoins with more than 6 confirmations on their balance (or simply with a signed balance - regardless of the number of confirmations).

I plan to spend the next couple of weeks redesigning the user interface of the app a bit - that is way overdue! Right now it displays a list of the coins and their balances and you can long click on each to access the available options (Spend, Redeem, Delete, etc). This doesn't make much sense for the average user and looks downright weird when you have more than a few coins, so I plan to aggregate the view and just display a count of coins in each bucket (1 BTC, 100mBTC, 10mBTC, 1mBTC, etc) as well as keep a "floating" BTC balance (that is a pure Bitcoin balance that is not stored on the card but available to the Android app as a buffer to either create new coins or split existing ones or as an intermediate buffer for redeemed values). This way, if you want to split a larger coin or aggregate a few smaller ones you simply select them and it internally moves them to the floating BTC balance first (gets the private key and sweeps their value), then funds the coins you want to create. This would get rid of the requirement to have the Bitcoin client on board (you can still have it installed if you want to fund the floating balance externally or want to get some of the floating balance out).

To ease the use the smartcard key exchange for purchases I envision that it would be best if people had many wallet keys (from now on I will call them coins) with balances of standard denominations (example denominations: 1 uBTC, 10uBTC, 100uBTC, 1mBTC, 10mBTC, 100mBTC, 1BTC, 10BTC, etc) so that they can give the exact amount or be given return change by totalling multiple coins in the manner similar to normal fiat eg: to give 0.8253BTC use 8x100mBTC + 2x10mBTC + 5x1mBTC + 3x100uBTC.   You could quickly top-up your smartcard with more coins by asking other people directly for change or using a change service over the internet.

By-the-way Drazvan,  this is what I was going to write an email about to you a couple of months ago.  I am now sending a PM with some further details that you may be interested in.

"Fractions of the wallet" - yes. "Fractions of a key" - no. Keys (and their associated balances) are transferred altogether, so you cannot transfer less than a key (that would effectively mean you are sharing it with someone else and the whole point is to make sure the key is only held by a single person at any given time). If you need to "break" a key into smaller amounts, you can easily do so through the Bitcoin network - transfer the key you want to split to the Bitcoin wallet, then fund two (or more) OtherCoin addresses from it with any values you need. This is also how you can pay the exact amount requested = you pay the majority in OtherCoin, then if the merchant wants to receive _exactly_ what he's asked for, you either pay the rest via Bitcoin or you break an OtherCoin key into two smaller ones, then transfer one to the merchant (for the remaining amount to pay).

Can it transfer fractions of the wallet? If not can it have multiple addresses of small amounts?

BTW, over the Easter holidays I tried to get away from the OtherCoin project and clear my mind a little bit, so I wrote this: https://bitcointalksearch.org/topic/show-me-the-bitcoin-use-plain-images-as-bitcoin-keys-send-btc-via-email-586830 . Now I'm back to the serious stuff.

Hey beeblebrox, good to have you back!

Right now, each key takes 32 bytes (the private key) + another 32 bytes stored as an encrypted blob (that is actually the half of the key that the phone knows, encrypted with AES by the phone). That blob is used to be able to move the smartcard between phones and re-build the OtherCoin key database if you only have the card (and a master password). The blob is not mandatory, but the current Android OtherCoin implementation uses it, so let's assume 64 bytes/key.

The current microSD smartcards we use have about 144K of storage (chip is NXP J5C145_M3) and the OtherCoin app itself is probably around 4K or so (haven't checked exactly). So 140000/64 = 2187.5. So you can safely assume that you can store about 2000 keys in the app - that would prove to be a bit unwieldy at this point with the current OtherCoin Android app since it shows them all to you and you choose the ones to transfer. Once we automate the process it will become easier. I think most people will have 100 keys or less in the system at any given time though.

As a status report, we're waiting for all 3 (yes three ) hardware manufacturers we use to fix their products. There will be 3 form factors for the OtherCoin product - a microSD card, a Bluetooth Low Energy keychain-style dongle and an actual Android device with a real (SIM-sized) smartcard inside. We're waiting for a new firmware from the microSD manufacturer to support Android 4.4 KitKat (current version does not work with KitKat and units cannot be upgraded in the field, so we would have had to recall them for an update or mail everyone new units). The Bluetooth Low Energy dongle will be available mid-May (around May 20th or so we've been told). The Android device has a bug with long-running smartcard operations (it times out too soon) and the manufacturer is supposed to send us an updated firmware next week.

I'm trying to make sure everything works on the smartcard side since that's very hard (if possible at all) to upgrade in the field. On the Android side we can always push an update through the Play Store if we find any issues. The app itself appears to be rock-solid, it's just these last minute interface bugs that drive me crazy. They have nothing to do with OtherCoin itself but with the way smartcards are read by the OS.

Hello Drazvan,

How are you going and how is the project coming along?

I'm curious to know what are the limits regarding how many keys the card can hold at once,  could you please tell me?

Thanks
Beeblebrox

Heh, I certainly do recommend you consider seriously that option! I've got a lot more ideas than there are hours in the day.


Sounds good.


You can put me down for a pre-order BTW.

Thanks Peter! In all honesty, I haven't had the time to look into the timestamping issue yet, thanks for the suggestions! I'm trying to keep the initial release as simple and as "blockchain agnostic" as possible. All it does for now is secure private keys, it has no notion of blockchain/transactions/ECDSA/etc, so it can be easily reapplied to just about any other altcoin that uses private keys (are there any that don't? ).

I need to get the marketing materials done so I will probably stop adding features for a few weeks and focus on getting it launched. There's always room for a version 2 .

Regarding the PIN, it's 4 digits / 3 tries. It's sent encrypted together with the private key and stored as an OwnerPIN JavaCard object (those are especially protected by the JavaCard runtime). You get 3 attempts to unlock the key - if you fail, the key is permanently blocked (I should probably make it delete it at that point to save space and prevent further attacks).

Sorry! I must have read your reply and forgotten about it.

The blockchain itself can be used as a clock in a few ways. The most obvious way is to process the block headers and just use the latest one lower bound on what time it is. However then you have to ask how does the card get the blockchain? You can add to the protocol an encrypted field that essentially lets anyone feed the card with block headers within any transaction going to it - if I'm sending you money I can inform your card about what time it is against your will.

However, all the block headers are kinda large for a Java card, so you really want to only send a subset. When you think about it every header the card gets is essentially making a kind of statement that some amount of work was done claiming the current time at least blockHeader.nTime Every header the card gets pushes the likely current time in some direction, usually forward. Making a bunch of fake block headers with high difficulty is very expensive, so you can probably come up with some rule that makes faking headers to lie to the card about the current time unprofitable. You can be a bit more clever with this by using interactive or non-interactive proofs, but long story short, Bitcoin doesn't support that yet.

You can also force the owner of the card to provide recent block headers via timestamping and merkle paths. The card would generate a nonce and and the card owner would be required to timestamp that nonce in the Bitcoin blockchain and provide the card with a merkle path from the nonce to the block header. The user is forced to keep providing the card with new blocks; with a minimum difficulty the cost of compromise is well defined, almost. Unfortunately it is possible for a group of card owners to collude and have some fake block headers generated so as to let them all benefit, driving the per-card cost of faking the time down. (possible without timestamping too I might add)

Timestamping infrastructure doesn't exist yet, but creating it isn't hard. I have a project called OpenTimestamps that was doing just that - I'd be happy to put some time into it again.

As for centralized time services personally I'd be very hesitant to use any kind of centralized service simply because it'd be temping for a court to order them to either shutdown, change keys, or sign fake timestamps as a way of disrupting OtherCoin users.



Good idea! How long will this pin be? What will you do to prevent brute-forcing it?

A quick status update: OtherCoin is progressing nicely, I have cleaned up the protocol a bit and added the ability to send PIN-locked keys. A locked key is transferred just like any other Bitcoin key in the OtherCoin system but it's also protected by a PIN. Without the PIN, the recipient is unable to spend it or transfer it to another user. This allows a primitive type of escrow - once a key is transferred, the sender no longer has it but without the PIN, the recipient cannot do anything with it (other than verify that it exists and has funds on it). So the two parties have to agree in order for the recipient to obtain the necessary PIN to unlock the key.

I'm still working on the final packaging for the cards and their associated microSD readers (we will include a reader in the package for each card - for phones that do not have a microSD slot). On the Android side we've hit a bit of a problem with Android 4.4 KitKat - https://code.google.com/p/android/issues/detail?id=67406 . This prevents OtherCoin from working on Android 4.4 since the phone can no longer talk to the card. The miniature Bluetooth card readers that we plan to offer as an alternative (see http://www.certgate.com/products/cgcard/ ) will only be available in May, so one way or another we'll have a working solution for Android 4.4 by mid-May.

Finally, another important part of the OtherCoin ecosystem has been prototyped - the Card2Coin system I described here: https://bitcointalksearch.org/topic/distributed-btcusd-exchange-using-regular-chip-and-pin-credit-cards-339389 now has a prototype and a demo movie at https://www.youtube.com/watch?v=ZsOzeELdjxM . It's a distributed BTC/fiat exchange based on the idea of remotely charging someone else's credit card in exchange for your Bitcoins. This will eventually be integrated with the OtherCoin system, allowing you to buy Bitcoins, transfer them and sell them for USD _within_ the system, without ever touching the blockchain or any of the centralized exchanges, while still preserving your ability to go through the blockchain at any time.

Thank you Peter, I'll look into those paywords, I wasn't aware of that system. Smartcards do not have an internal clock, so I was initially thinking of using a certified time source (that is a web service that accepts a nonce and returns a signed time+nonce packet indicating the current time), but if this could be done in a distributed fashion it could be interesting. I'm not sure how that would work though, how would you limit the amount being transacted or do you only suggest limiting the number of transactions that a card can do in a given time interval?

I am trying to keep the on-card system as simple as possible and only use cryptographic primitives that the chip manufacturer (NXP) has certified against various attacks (SPA/DPA). They have an entire document that describes how those primitives must be used in order to maintain security.

Adding on-card processing in JavaCard can be extremely slow and can leak information, that's the main reason why I haven't implemented Adam Back's suggestion to change the private key halves every time they are exchanged by adding a random value on the smartphone and subtracting the same value on the card to make sure that previous owners of a key cannot steal your smartcard and use the key half they used to know to reconstruct the Bitcoin key. JavaCard has no native BigInteger implementation and rolling our own would require careful testing against timing and power analysis attacks.

I am also trying to make this as independent of third party Internet services as possible. Certified balances (like btchip suggested) are going to be there, but they will be optional (you will always be able to just lookup the balance on the blockchain).

And yes, you are right about the granularity problem, you could either have smaller amounts on different keys or just send _most_ of the amount over OtherCoin and then post a transaction on the Blockchain to "split" a certain key into two (a remainder to pay and a change, sent to another OtherCoin address). I expect wallets to manage this the same way people manage their cash in large denominations. Merchants could also calculate a change amount and return it to the payer via OtherCoin (they don't care as much about their anonymity, so they can easily post to the Bitcoin network to split large OtherCoin keys into smaller ones or fund new keys with small change amounts).

Thanks for the feedback!
Razvan

Oh, and FWIW, the paywords stuff doesn't need specific support by the cards themselves beyond the ability to calculate an arbitrary paywords chain; the software talking to the cards can handle the rest.

With regard to history, I think there's an interesting attack-countermeasure possible without it, but first, a bit about how you'd actually use the card.

If the card is purely a secret key storage device, we have a practical problem of granularity: If Alice has 1BTC stored on one secret key, how can she send Bob 0.5BTC? Now, bi-directional transfers help here - if Bob happens to have 0.5BTC in one or more secret keys, he can give those keys to Alice in exchange for her secret key to make for the correct net amount transferred. Ideally you'd just fill your wallet with secret keys loaded with powers of two outputs, however that runs into the problem of minimum cost to spend a txout - at some point even if you had an output worth x BTC it'd cost you a significant fraction of that x BTC to spend in on-chain, so for the smallest amounts you'll want outputs along the lines of, say, 1.01BTC, so you can exchange it for Bob's 1BTC txout efficiently.

This is relevant to attacks when you consider the financial model of an attack. The attacker might spend, say, $50,000 worth of lab time to take apart one of these cards and extract the private keys on it. Once that is done the attacker can then create a fake software emulator and intercept the secret keys. However to actually profit from the attack the attacker needs to get something of value in exchange for pretending to delete secret keys, and the total value of on-chain txouts spendable minus the transaction costs to obtain them needs to be >$50,000 to break even.

Now suppose we limit the lifetime of a secret key to 1 year; after that year is up cards won't accept it. We can easily prove the creation date of a key by using the blockchain as a timestamped random beacon and committing a recent blockhash with ECC key derivation. Next we limit the total value of the secret keys that the card has access to per year. We can do this with Rivest's paywords scheme: the card calculates a chain of nonces derived from a root secret with w_i=H(w_{i+1}), revealing an additional step in the chain at each step. If peers expect a new, signed, nonce with every secret key exchange they can limit the total number of exchanges in a given time period by publishing those nonces. This can be a central server or decentralized p2p network; the requirements for consensus are very loose and not all nonces need to be published. Publishing two separate signatures for the same nonce - or overlapping range of nonces - is of course considered fraud and is easily proven. Storing the nonces isn't onerous, as they can be expired over time.

So long as the cost to attack a card is high compared to the cost of the card itself the economics work out. If a $5 card lasts two years and can move $25,000 worth of private keys per year, the cost to do so was 0.01% of the value of those keys. Meanwhile the attacker needs to keep the cost of the attack to <$25,000 to break even. I think the main question is what kind of economies of scale an attacker might get, and what kind of per-transaction cost users are willing to accept.

I agree with your analysis; given the use-case is low-value payments, better to have a solid privacy guarantee and slightly weaker loss reistance than the other way around. After all, this thing could be useful for privacy too.

Reminds me: it'd be good to add some features to make it possible to to secure trades on a blockchain. Right now your OtherCoin.pdf whitepaper suggests two functions, generate key, and securely transfer key to another card. I think you actually need a third function that does bi-directional key transfer atomically.

Suppose Alice has 50LTC and Bob has 1BTC. They want to trade like for like. They can do this by first transferring the currency into an address that their respective OtherCoin card has control of and letting the transaction confirm. Next they tell their cards the transaction they want to make, Alice: "Give up secret key Alice_LTC in exchange for secret key Bob_BTC" and Bob: "Give up sec key Bob_BTC in exchange for Alice_LTC"

Now the two cards can communicate with each other securely. (being fully atomic and non-jam-proof will be tricky) When they're finished either party can repeat the process, or potentially just reveal the secret keys entirely so the coins can be spend normally. Interestingly the cards themselves don't have to have any concept of trust; all the cards care about was that they got a signed ACK from the other side. Whether or not that signature was from a trustworthy card can be left up to the user to evaluate.

Speaking of, you forgot to include "Reveal a secret key" in your list of basic operations. In fact, what you actually want to do is a bit more subtle than in your whitepaper: you should always be able to get your OtherCoin device to produce an encrypted and then signed message containing a given secret key. What key the message is encrypted to is irrelevant: under all circumstances once this message has been produced the OtherCoin device is guaranteed to securely delete the key from memory and never produce another such message. At the same time the device is also guaranteed to only accept a new secret key if the key is encrypted and signed by a trusted sender.

What's neat about this is it gives a one-sided upgrade path: new devices can still accept secret keys from old, but still trusted, device. For instance if the master secret keys are ever lost, you can create a new set and issue new devices that can still accept secret keys from the old devices, even if the old won't accept keys from the new.

Hello everyone,

Just a quick update on the software side: the initial plan was to have each OtherCoin keep track of the history of each received Bitcoin private key in order to be able to help with identifying a potential attacker that had managed to crack one of the cards and extracted its private key, allowing him/her to attempt double-spends (either simultaneous spends in the OtherCoin system or spending a key in OtherCoin and immediately spending the same key in the Bitcoin network).

After careful consideration, I've decided _not_ to implement this. Allow me to explain:

1. The main purpose of OtherCoin is to allow a way to _privately_ transact Bitcoins, without any traces in the blockchain or anywhere else. If we would be able to recover the history of a certain private key, someone else could do it too (or they could force us to do it for them). The easiest way to make sure the payment history cannot be recovered is to simply _not_ record it anywhere.

2. Provided that we don't make any stupid mistakes in the actual protocol (and we're going to make extra sure we don't), OtherCoin would only be vulnerable to physical attacks to the smartcard chip. Those are extremely expensive and require very specialized equipment and labs, not something your average script kiddie would have. The estimates I've seen were in the range of a few hundred thousand dollars in costs to attack / recover keys from a single card.

An attacker that manages to defeat one of our cards would only find his/her own private key, essentially allowing him to attempt double spends. However, to recover the high cost of the key recovery process, they would either have to attempt to double-spend a huge amount ($100k for instance) or a lot of smaller amounts (let's say 1000 payments of $100 each). As much as I'd like to see OtherCoin used for payments of hundreds of thousands of dollars, most recipients would probably immediately drop the transaction onto the blockchain to get it confirmed, so the attacker would no longer be able to double spend. For the 1000 * $100 scenario, the attacker must have 1000 people to transact with and hope that all of them do _not_ attempt to spend the OtherCoin Bitcoins on the blockchain before he's done (and none of the 1000 can identify him).

3. I suspect that if someone would ever attempt to crack an OtherCoin card (in the physical, expensive way), it would be the NSA or a similar govt funded entity. These entities would most certainly not do it in order to double spend anything, they would do it in an attempt to trace payments or identify persons/entities behind the OtherCoin addresses. However, if the cards do not contain any history information, an attacker would have nothing to gain by cracking a user's OtherCoin card (other than gaining access to his/her private keys and possibly spend the funds associated with those keys - something they can probably obtain with a $5 wrench - http://xkcd.com/538/ ).

I would be happy to hear your pro/con arguments. I realize that not implementing this makes us "deaf" in case of a successful crack of an OtherCoin card. We would know it has happened (the double-spend would be visible), but we would not know who has done it (unless we work our way backwards from the current owner of the key and count on them knowing/remembering who they got the key from, then rinse and repeat). But the upside is that there is no payment history, not in the blockchain, not on the card and not anywhere else. There's nothing for us or anyone else to extract, the info is just not there.

Let me know what you think.