Pages:
Author

Topic: fixed public key coin transfer (for zero-trust physical coin transfer) (Read 9857 times)

hero member
Activity: 555
Merit: 654
Also in a firmcoin there are two methods to reload coins:

1. You send the the pubkey to a Firmcoin server, and he server returns you a signed message that your Firmcoin verifies to and enters the "funded" state.

Why do you involve a firmcoin server?  Does that mean a firmcoin server retains the technical authority to falsely trigger a firmcoin to think its loaded?
Good point. But it doesn't work like that.
Anyone can load a certificate to the firmcoin tho prove the coins are valid, and the firmcoin will gladly accept it.
The coin can have (currently) up to 8 user provided certificates.
So if you don't trust the manufacturer, you can reject a coin that has only the certification of the manufacturer.
Maybe The Bitcoin Foundation in the future can be generating its own certificates to put into the firmcoins.

Anyway, why we are providing the method 2, that is exactly what you say in your post. The firmcoin tells you which method was used to load the coins.


edit: I guess you're concerned that proper validation is too expensive for the coin,

Yes, it requires much computation, but the nice fact is that it can be done incrementally with little memory.


sr. member
Activity: 404
Merit: 360
in bitcoin we trust
Also in a firmcoin there are two methods to reload coins:

1. You send the the pubkey to a Firmcoin server, and he server returns you a signed message that your Firmcoin verifies to and enters the "funded" state.

Why do you involve a firmcoin server?  Does that mean a firmcoin server retains the technical authority to falsely trigger a firmcoin to think its loaded?

Why not just pay to the address of the coin (which it knows), and then present it with a merkle tree containing the coin and a block with reasonable difficulty containing it.  As the coin knows it has sole control of the private key, it knows that the coin can not have been re-spent.

A verifier can then check the information against its view of the block-chain and validate for itself the merkle tree?

edit: I guess you're concerned that proper validation is too expensive for the coin, and you want some transferable representation of the fact a full node server (or even an SPV client) has validated the load transaction.   May also want to ideally avoid the need for the continued availability of the firmcoin server.  What happens if firmcoin goes out of business?  No more ability to re-load firmcoins?  Not obvious how to retain the loaded/empty distinction without a more powerful coin, or some entity to semi-trust.  You probably want to have the coin still check the block collision and merkle tree even with a firmcoin server signature.  (Firmcoin server could get hacked itself, and abused to load non-existing balance onto coins for offline spending).

Adam
sr. member
Activity: 404
Merit: 360
in bitcoin we trust
btw As you have a funded state on the coin, and passive accumulated stray RF power possibility you could flash a light on button push to indicate green or red status even.

Passive displays are very expensive. I found that the smallest eInk display costs 8 USD.
And a capacitor with a LED will hold the status not long enough.

But arent there possibility to accumulate small amounts of power continuously from stray / background EM emission?  Perhaps not for $3?

A solar cell may work, but still they are expensive. I want the firmcoin to be under 3 USD.

Maybe I can shake the coin a bit and a led glows red or green Wink  Not sure what linear micro generators cost.

Any thoughts about suggestion to make the private key recoverable by combination of users retained (but not block chain published) y values (or other new value) and manufacturer on receipt of broken hardware?

One  possibility is that when the firmcoin generates a key pair X, and you generate another key pair Y.
You print the keypair Y in a QR code and stick QR code in the firmcoin. To load funds, you load them to a 2-2 multisig (a transaction that requires both private keys to sign the input).
The the firmcoin cannot by himself do anything to steal the coins, even leaking its private key is useless. The worst thing it can do is just stop working (which will make you loose your coins, but the attacker gains nothing).

No what I was meaning is I am not worried about the manufacturer stealing coins (as the user controls the public address, and the coin not computing signatures has no subliminal channel other than NFC).

More worried that the coin dies when I drop it with 10BTC on it.  I do prefer the QR code to be embedded in the coin as you have it, stickers can rub off etc.

So eg say the coin encrypts x' with the manufacturers public key, preferably in a way verifiable to the user (user can verify if coin encrypted x' not x), sends E(x') to user.  User retains E(x') and y.  If the coin dies, the user sends the physical coin back to the manufacturer who computes x' and sends it to the user.  The manufacturer still doesnt know y so cant spend the coin.  The manufacturer only accepts physical coins so no one can easily trick the manfacturer into helping them recover coins from other users that they dont have physical possession of.  Manufacturer also cant remote invalidate coins.

Adam
hero member
Activity: 555
Merit: 654
Also in a firmcoin there are two methods to reload coins:

1. You send the the pubkey to a Firmcoin server, and he server returns you a signed message that your Firmcoin verifies to and enters the "funded" state.

2. You provide the firmcoin with a block-chain branch of at least 144 blocks with the current difficulty, where the first block contains a transaction that funds the firmcoin, along with the merkle tree. If each block reward is 12 BTC, when you can fund upto N*12/2 BTC, where N is the size of the supplied chain, an N is at least 144. This can be done privately, and anonymously.

None of this methods has any security problem: if you receive a firmcoin, it's either authentic or not authentic (you check by eye inspection, and some other methods).
If it's authentic, either it has funded coins or it does not, and you can query the device for this information.

Sergio.
hero member
Activity: 555
Merit: 654


Your use of x=yx' (y chosen by user) makes more sense in that context also, as then attacker cant mark coin public keys for transfers to coins (which will appear on the block chain).

btw As you have a funded state on the coin, and passive accumulated stray RF power possibility you could flash a light on button push to indicate green or red status even.

Passive displays are very expensive. I found that the smallest eInk display costs 8 USD.
And a capacitor with a LED will hold the status not long enough.
A solar cell may work, but still they are expensive. I want the firmcoin to be under 3 USD.


Any thoughts about suggestion to make the private key recoverable by combination of users retained (but not block chain published) y values (or other new value) and manufacturer on receipt of broken hardware?  May make it more attractive for bigger balances - otherwise I can see people being scared to put bigger amounts on it in case of hardware failure.  As is I could take the value off the card (empty state) for safe storage/backup/paper-wallet, but as soon as I reload the coin it chooses a new private key that I dont know, and cant easily know without resetting it back to empty state.


One  possibility is that when the firmcoin generates a key pair X, and you generate another key pair Y.
You print the keypair Y in a QR code and stick QR code in the firmcoin. To load funds, you load them to a 2-2 multisig (a transaction that requires both private keys to sign the input).
The the firmcoin cannot by himself do anything to steal the coins, even leaking its private key is useless. The worst thing it can do is just stop working (which will make you loose your coins, but the attacker gains nothing).

The person who stamped the QR code must collude with the hardware manufacturer in order to create a firmcoin that can leak usefull information to stole the coins.
So if you stamp the QR code yourself, then the fircoin manufacturer still cannot steal your coins.
sr. member
Activity: 404
Merit: 360
in bitcoin we trust
Maybe to the limited extent of the tamper resistance, tamper evidence, an holograms etc that some people may want to trust that, we could have both objectives in one coin (moderately safe for offline transfer AND new owner chooses part of the key).  And Sergio Lerner said something like this:

Because I knew about side channel attacks, I preferred that the firmcoin do not sign anything that goes out to the Internet. The firmware just gives you the private key whenever you want, but at the same time it enters  a special "empty" state, where it no longer advertises as a funded device.

Alright - sounds like you know what you're doing - you went for the plan A.

Quote from: adam3us
You either need to not trust the hardware to make the signature, or you need the DSA subliminal channel to be plugged.

That aspect was unclear from your description before, but that is a consistent and reasonable design.

Quote from: Sergio_Demian_Lerner link=topic=232787.msg2462734#msg2462734
Also the day a counterfeit device appears on the market, from that day on the firmcoins will no longer be able to be verified off-line, but that doesn´t mean they are useless. They still can be extracted their private keys. They can be reloaded and uses as BTC storage. So the incentive to an attacker is very low: he can just steal some very few BTC until everybody knows there are counterfeit devices in the market. Who will invest in manufacturing a special chip for such a crappy attack?

Your use of x=yx' (y chosen by user) makes more sense in that context also, as then attacker cant mark coin public keys for transfers to coins (which will appear on the block chain).

btw As you have a funded state on the coin, and passive accumulated stray RF power possibility you could flash a light on button push to indicate green or red status even.

Any thoughts about suggestion to make the private key recoverable by combination of users retained (but not block chain published) y values (or other new value) and manufacturer on receipt of broken hardware?  May make it more attractive for bigger balances - otherwise I can see people being scared to put bigger amounts on it in case of hardware failure.  As is I could take the value off the card (empty state) for safe storage/backup/paper-wallet, but as soon as I reload the coin it chooses a new private key that I dont know, and cant easily know without resetting it back to empty state.

Adam
hero member
Activity: 555
Merit: 654
Anyway, if you ask the firmcoin to sign a transaction, then it doesn't matter if it leaks all the private key, probably your transaction will get into a block before the attacker extracts the private-key, and creates his own competing transaction, which will be regarded as a double-spend attempt.
hero member
Activity: 784
Merit: 1000
hero member
Activity: 555
Merit: 654
 

However it seems that the same people want the coin to be online spendable (emptyable) and reloadable.  Those objectives seem in conflict as any non-technical guy can follow the online spendable procedure, and end up with a coin that within protocol has no bitcoins in it!  So then you see the defense that the coin is somewhat offline verifiable in that it reports itself over local hardware link (eg NFC in case of firmcoin) as empty.  (eg it deletes its private key when spent).

Maybe to the limited extent of the tamper resistance, tamper evidence, an holograms etc that some people may want to trust that, we could have both objectives in one coin (moderately safe for offline transfer AND new owner chooses part of the key).  And Sergio Lerner said something like this:


Quote from: Sergio_Demian_Lerner
What I actually do is to create the private-key in the hardware, then the hardware tell the user the public key. Then the user provides a user-chosen random multiplication factor to the hardware and then the hardware multiplies both the private and the public key.
Then the hardware manufacturer cannot know the private key.

So that means device computes P1=x'G, then user chooses y such that P=x'P1=x'yG so the final key is x=x'y mod n.  So while its true that the device didnt chose all of the private key bits, it still knows the full private key, could leak it over NFC, or more subtly send it in k when making the ECDSA signature via the big fat 256-bit DSA subliminal channel, so the user or manufacturer or criminal buyer of hostile hardware can later harvest coins from the signatures published to the network by examining the signatures.

Because I knew about side channel attacks, I preferred that the firmcoin do not sign anything that goes out to the Internet. The firmware jusr gives you the private key whenever you want, but at the same time it enters  a special "empty" state, where it no longer advertises as a funded device.

Also I like the idea that you have to give the physical device to the other party, because if you have manufactured a counterfeit device, then you´re giving the proof of your criminal act to the other party, so the other party could go legally against you.

Also the day a counterfeit device appears on the market, from that day on the firmcoins will no longer be able to be verified off-line, but that doesn´t mean they are useless. They still can be extracted their private keys. They can be reloaded and uses as BTC storage. So the incentive to an attacker is very low: he can just steal some very few BTC until everybody knows there are counterfeit devices in the market. Who will invest in manufacturing a special chip for such a crappy attack?

Best regards, Sergio.
sr. member
Activity: 404
Merit: 360
in bitcoin we trust
what's the point of having the physical coin at all?
The answer is already in this thread. First post. First line.

I think there are people who like to work with the limited trust you can place in a piece of hardware made by a third party and given to you by a person hostile to your interests (or to just pretend thats secure, or secure enough for the low value transfer and social face loss of cheating).

Under this argument they want to make the coin somewhat safe to transfer offline, eg to the extent that the coin makes it hard to take the private key out of it.  

However it seems that the same people want the coin to be online spendable (emptyable) and reloadable.  Those objectives seem in conflict as any non-technical guy can follow the online spendable procedure, and end up with a coin that within protocol has no bitcoins in it!  So then you see the defense that the coin is somewhat offline verifiable in that it reports itself over local hardware link (eg NFC in case of firmcoin) as empty.  (eg it deletes its private key when spent).

Maybe to the limited extent of the tamper resistance, tamper evidence, an holograms etc that some people may want to trust that, we could have both objectives in one coin (moderately safe for offline transfer AND new owner chooses part of the key).  And Sergio Lerner said something like this:

Quote from: Sergio_Demian_Lerner
What I actually do is to create the private-key in the hardware, then the hardware tell the user the public key. Then the user provides a user-chosen random multiplication factor to the hardware and then the hardware multiplies both the private and the public key.
Then the hardware manufacturer cannot know the private key.

So that means device computes P1=x'G, then user chooses y such that P=x'P1=x'yG so the final key is x=x'y mod n.  So while its true that the device didnt chose all of the private key bits, it still knows the full private key, could leak it over NFC, or more subtly send it in k when making the ECDSA signature via the big fat 256-bit DSA subliminal channel, so the user or manufacturer or criminal buyer of hostile hardware can later harvest coins from the signatures published to the network by examining the signatures.

Concretely lets say you have some hostile hardware, here's how you leak x=x'y mod n.  key is some key buried in the hardware, loaded into its firmware etc and know to the attacker.  

Compute k=H(key||H(m)||P)

Now the normal DSA signture:
(r=[kG]x, s=k-1(H(m)+rx)

syntax [G]x indicates the x coordinate of point g.

in this case x=x'y because of the way firmcoin generates x' on the coin and allows the user to generate y and pass it in.

Now the attacker can recover the coin private key seeing only the signture (r,s) on message m (the transaction details) published on the bitcoin block chain, and then pre-spend your coin.

that is because:

s=k-1(H(m)+rx)
=> sk^-1=H(m)+rx
=> sk^-1-H(m)=rx
=> x=r^-1(sk^-1-H(m))

and notice that the user generate x where x=x'y didnt help a bit.

You either need to not trust the hardware to make the signature, or you need the DSA subliminal channel to be plugged.

So you might imagine doing the same trick again, hardware chooses R=k'G and sends the user R, users chooses z so that r=[yR]x=[yk'G]x.  ie k=yk', and verifies that r=[yR]x.  Now the attacker cant set k arbitrarily.  You have to do the current x=x'y defense as well otherwise the hardware can set x to H(key||counter).

Now there is no subliminal channel so you can safely have the coin make a signature (modulo NFC leaking).

You better check R is on the curve, and that it generates the same subgroup (or that the card knows the discrete log of R in base G, eg with a schnorr proof in such a way that protects the card from private key extraction).

You might want to arrange things so the hardware manufacturer can help the user recover x when mailed back the coin, and with y and z.  (eg from serial number on outside of coin package plus a secret key known to manufacturer).  Otherwise people are going to pretty annoyed if the hardware fails).  You can probably do that such that the manufacturer still cant do anything useful by itself with out the users knowledge of y and z.

Adam
legendary
Activity: 1176
Merit: 1280
May Bitcoin be touched by his Noodly Appendage
what's the point of having the physical coin at all?
The answer is already in this thread. First post. First line.
sr. member
Activity: 280
Merit: 257
bluemeanie
Adam,

  btw- this app does something related to your idea: https://bitcoinvanity.appspot.com

  it generates a key pair, but doesn't know it completely.  Part of it is generated in your browser.  So I think some aspects of your system have already been demonstrated to work.

-bm
sr. member
Activity: 280
Merit: 257
bluemeanie
Hi Adam,

  Consider though that your system relies on an internet connection- so what's the point of having the physical coin at all?

  My paper wallet idea does give you this ability to carry a secret without knowing what it is.  When combined with a un-counterfeitable item (hologram or kinegram serial code), you have something very useful to represent a bitcoin.  In my system(linked above) the only person who knows the private key is the one who prints out the two VC factors.  Its' also very easy to do- only requires a laser printer and optimally some hologram serial numbers(these are widely available http://www.amazon.com/Security-Hologram-Stickers-Consecutive-Authentication/dp/B002KHVHK8 ) - better would be the hologram is embedded into the paper somehow, but the sticker offers your basic anti-counterfeit.

-bm

sr. member
Activity: 404
Merit: 360
in bitcoin we trust
Yes but you cant prove the key was generated in a way not computable by the hardware manufacturer.  I was thinking it would be safer to have the key chosen by the software system under the currrent owners control (the person loading the coins).  (Or maybe verifiably half the private key bits by the owner and half by hardware).   In that way the hardware does not actually have to be trusted.  Also if the hardware fails you dont lose the coins (you could back them up).

what would that do that 2(or N) factor auth can't?

Perhaps my objectives are different to other people but I am assuming a relatively online world where you check your coins with a smart phone, so the coin is more of a convenient physical representation and nice physical container for one bitcoin denomination.

The problem with a coin is its a piece of hardware made by your enemy.  So you cant trust it with generating secrets, nor signatures.   (DSA signatures have a subliminal channel in the choice of k and hostile hardware can intentionally and undetectably leak the private key in the signature).

Quote
so to elaborate, one factor is the Smart Card or similar device, and the software creates a NEW factor in the Bitcoin transaction(perhaps with a old-fashioned private key).

I just mean you cant trust hardware given to you (the coin) to have interests aligned with yourself.  Its less dangerous to have it passively store a secret.  But you do generally want to be able to just hand it to someone, have them easily able to double-check what the block chain thinks about its balance, and to have them without trusting the hardware much take control of the coin (ie not have to trust you the previous owner to have retained a private key).

Quote
if it's possible to get at the coins without the hardware, then you obviously lose some security aspects.

My idea of coin security is that you want security against the coin - the coin is some hostile, third party hardware.  You cant check coin hardware authenticity, and if it gets interesting, counterfeit, hostile, secret leaking coins will come flooding onto the market.

I avoid the new holder needing to worry about there being a second copy of the previous private key, by the act of transferring the coin enabling the recipient to set a new private key, and verify eg with 1 confirmation or some independent confirmation from a miner or tracking site that his spend to his own chosen key has gone through ahead of a potential double-spend by the previous owner.

Adam
sr. member
Activity: 404
Merit: 360
in bitcoin we trust
You want the info on the outside of the coin to be unchanging and yet easily verifiable as to its spent state, and you want to fix the trust issues with transferring them in physical form, so the thing that has to change instead is the private key and base.

Maybe there's another way to get a similar effect without having the same public key be reused with different bases.

Lets say we create an initial bitcoin address for each physical coin, and engrave the initial address on the outside of the coin.  We'll also refer to this initial address as the coin serial number.  We want bitcoin to prevent reuse of the serial number, as it does for double-spent payments.  (Maybe we can trick bitcoin into doing that for us with appropriate formatting).

The current coin private key is stored on the flash storage in the coin.  (And the public key can be computed from it).

Lets say each bitcoin transaction optionally includes a serial number (eg via some auxilliary signed data).  Now when taking ownership of a physical coin the recipient would expect (demand) the serial number to be present on the current ownership transaction, and would include the serial number in the signature transferring ownership to a new key.  The new key would be stored on the coin flash storage.

The main point of the serial number would be to correspond with the coin markings, and to allow convenient static locator to look up the state of the coin.  Tools like block chain would be needed to index by serial number.  (Alternatively if the serial number were implemented as a demonstrably invalid optional second signing address added to a multisig, on each physical coin, probably tools could already index it; though invalid addresses are frowned on for frustrating compaction.)

Adam
sr. member
Activity: 399
Merit: 250
And if a chip manufacturer is caught making counterfeit chips, then it will have a huge legal problem.


Sorry to rain on your parade, but there is a multitude of fabs in China doing just this.... and they operate with complete impunity.
hero member
Activity: 555
Merit: 654
And if a chip manufacturer is caught making counterfeit chips, then it will have a huge legal problem.
hero member
Activity: 555
Merit: 654

Quote
You can prove that you have a certain private key by simply signing an arbitrary message with it (but the message to be signed must be chosen such as neither of the parties can force it).

Yes but you cant prove the key was generated in a way not computable by the hardware manufacturer.  I was thinking it would be safer to have the key chosen by the software system under the currrent owners control (the person loading the coins).  (Or maybe verifiably half the private key bits by the owner and half by hardware).   In that way the hardware does not actually have to be trusted.  Also if the hardware fails you dont lose the coins (you could back them up).


What I actually do is to create the private-key in the hardware, then the hardware tell the user the public key. Then the user provides a user-chosen random multiplication factor to the hardware and then the hardware multiplies both the private and the public key.
Then the hardware manufacturer cannot know the private key. This is not new and some other people have posted about similar methods (like adding two keys).

Quote
I've also added a new method to verify the FIRMWARE authenticity by using "practically incompressible" firmware. And challenging the firmcoin to dump the firmware in a very short time.

Its probably fine for modest value but in principle it seems that the manufacturer you use could make another coin with a different bigger firmware that contains both a standard firmware for responses and a hostile firmware for generating trap-door predictable private keys (eg)

Adam

The idea is not bullet-proof. But you can inspect the hardware and check that the chips are the ones with the right amount of memory.
If I use a chip from a manufacturer with the highest amount of memory, then you know I cannot add more, without adding additional chips.

That's why I think firmcoins work best for low valued denominations.

Sergio.

sr. member
Activity: 280
Merit: 257
bluemeanie


Yes but you cant prove the key was generated in a way not computable by the hardware manufacturer.  I was thinking it would be safer to have the key chosen by the software system under the currrent owners control (the person loading the coins).  (Or maybe verifiably half the private key bits by the owner and half by hardware).   In that way the hardware does not actually have to be trusted.  Also if the hardware fails you dont lose the coins (you could back them up).



what would that do that 2(or N) factor auth can't?

so to elaborate, one factor is the Smart Card or similar device, and the software creates a NEW factor in the Bitcoin transaction(perhaps with a old-fashioned private key).

if it's possible to get at the coins without the hardware, then you obviously lose some security aspects.

sr. member
Activity: 404
Merit: 360
in bitcoin we trust

Now all we need is a kick starter for someone with a bit of hardware expertise to put an unpowered 1kB contact readable serial readable flash drive inside a coin Smiley  

This is what I did: check the new thread: https://bitcointalksearch.org/topic/firmcoins-a-new-kind-of-bitcoin-physical-bill-ready-for-off-line-transactions-232898

Very cool.  Like the 2-way NFC and button combination as an interface.  Coincidentally your first post on firmcoin just a few hours ago too!

Quote
You can prove that you have a certain private key by simply signing an arbitrary message with it (but the message to be signed must be chosen such as neither of the parties can force it).

Yes but you cant prove the key was generated in a way not computable by the hardware manufacturer.  I was thinking it would be safer to have the key chosen by the software system under the currrent owners control (the person loading the coins).  (Or maybe verifiably half the private key bits by the owner and half by hardware).   In that way the hardware does not actually have to be trusted.  Also if the hardware fails you dont lose the coins (you could back them up).

Quote
I've also added a new method to verify the FIRMWARE authenticity by using "practically incompressible" firmware. And challenging the firmcoin to dump the firmware in a very short time.

Its probably fine for modest value but in principle it seems that the manufacturer you use could make another coin with a different bigger firmware that contains both a standard firmware for responses and a hostile firmware for generating trap-door predictable private keys (eg)

Adam
Pages:
Jump to: