fixed public key coin transfer (for zero-trust physical coin transfer)

[adam3us]

I have been musing about how to improve physical coin security, because well physical coins are just so cool

Its obvious that the https://www.casascius.com/ reliance on a hologram covering a microSD card held in a recess in the coin has several problems: how do you know there is a private key on a SD card inside it (trust manufacturer).  Also how can you spend it convincingly without wrecking the hologram.  And anyone can get some holograms printed up, remove key.  Now apparently some of the coins have the coin address engraved on the coin rim which is quite cool as you can check if its currently spent.  However it could be spent at anytime if the former owner or manufacturer cheated.

So my variation on this is that you can actually generate a new private key for an existing coin address / coin public key (relative to a new discrete log base).  The effect is that I think you could hold a coin public key constant while convincing someone in zero-trust that you did not retain the effective private key, by changing the base.

Normally P = xG (elliptic curve discrete log notation)

Now you can use different G values and still make a signature.  eg if you could compute P = x'G' (same public key P, different private key x', different base G') you can make an ECDSA signature wrt P, x' and G'.  It will validate against P and G'.

But you have to be careful as anyone can cheaply compute the y-th root of P: if you can choose G' randomly, you can cheat.  ie compute y^-1 mod n and multiply: G' = y^-1P.  Thats because that is an elliptic curve y-th root which is trivial to calculate because G' is arbitrary result (the y-th root) not a pre-chosen discrete log base, even though it looks like a base when you've finished.  (n is the order of the group).

So how could you fairly chose a new base?  One way is to demonstrate you know ECDL of G', ie you know w such that G' = wG.  We can probably do that safely:

recipient gets private key easily from coin, if it has an electrical interface to reveal it on contact.  Computes new random z, and G' = zG and x'=xz^-1 mod n.  x' is the new private key because P=x'G' and P=x'G'=xz^-1zG=xG so P is unchanged.

Recipient publishes multi-signature of P' with old private key x, and second signature of P' with new private key x' relative to new base G' to the bitcoin network.  Once that is hashed after a few blocks they can be sure the previous owner can no longer claim the coin, even though the previous owner has the previous private key.

Its analogous to the current coin transfer (signature from old key to new key as transfer), except the discrete log base is changing, not the public key.  (Currently G is held fixed as a fairly chosen EC parameter which is a constant point on the curve).

This obviously can be repeated: keep original x for calculation purposes and store on the coin the current x.  So long as the new holder of the physical coin can choose their own x' and controls the IO interface to the coin, they can be confident the coin cant be stolen.  They can network verify the coin, which retains its public key (though changing base).

Or maybe you write the first coin private key (and immediately change coin private key) around the rim of the coin, and just dont let people play with your coins up close, then you dont even need an electrical interface, nor any electronics on the coin.  (Or maybe simpler electronics that can just read out a fixed original private key x).  The transfer to new private key has to come via the smart phones on input of the private key manually, or just use the private key or part of it as a checksum to the actual private key sent to the user to check its the right physical coin.  It would be nice to store the current private key into the coin.


In fact simplying slightly you could even allow transfer to a y-th root chosen base, so long as the holder knows the private key from the current base, and they sign the new base, why not.  Then you only need a single signature not a multisig from old and new private key with respective bases.


You can think of this changing private key as a kind of one-use forward secure signature (foward secure signatures are where you can disavow old signatures because the old private keys are published after expiry).  Original signatures are still convincing in this context because of the time-stamping from the period before private key disclosure.


The main advantage of keeping the public key fixed is you can engrave it on a coin (as now) and the main advantage of allowing a DL base to change to represent ownership change is you can safely transfer control of a physical coin without trusting anyone, the coin only needs to store the current private key for convenience.


Maybe there is some advantage to be had for other bitcoin uses of keeping the public key constant.  eg maybe the UTXO set can be smaller (unclear how)?  You could actually do change with a fixed public key, but then you end up with a below par coin.  It could be two coins with the same fixed public key (but different bases and private keys and amounts adding up to the original coin denomination) or two coins one with a fixed public key and one not, or two not breaking the link with the physical coin public key.  An emptied or disassociated coin could still be reloaded by spending to its address/public key with a new chosen base.


Coin addresses are currently somewhat opaque because its a hash of a public key.  The new base on each spend could also be opaque if desired (eg publish hash of public key and base in the transfer message.)

Even if you wanted to go crazy for some esoteric reason (eg maybe someway to leverage for privacy somehow?) all coins could have the same public key (but different bases and private keys).


It strangely also allows you to spend to "current bearer" with a fixed coin address, to add value to a coin, because the coin address doesnt have to change, the network tells you via the UTXO query which is the current base allowed to claim ownership and spend the coin!

Adam

[jackjack]

Wow that's smart...

I see one small drawback:
A client that would want to check if the n-th recipient can do so will have to download and process all the previous base changes to check everything is ok
Forget it, it would be just like a normal transaction: it would be verified change by change, assuming the previous was ok because we validated it

This is really a beautiful possibility

[jl2012]

First of all, the private key is simply printed on the physical coin, no SD card involved.

Anyway, you proposal has no advantage at all, because it is equivalent to transferring bitcoin to another address. You can throw the physical coin away after that.

[jackjack]

First of all, the private key is simply printed on the physical coin, no SD card involved.

This doesn't change anything

Anyway, you proposal has no advantage at all, because it is equivalent to transferring bitcoin to another address. You can throw the physical coin away after that.

You just didn't understand his proposal...

[adam3us]

Anyway, you proposal has no advantage at all, because it is equivalent to transferring bitcoin to another address. You can throw the physical coin away after that.

You just didn't understand his proposal...

So far physical bitcoins sell for a big margin above BTC value, and they are things of beauty is part of the fun, so throwing them away would be undesirable. 

However they are currently security/trust risk because of their design.  Apparently some of them put the private key on the underside of a tamper evident sticker printed with inkjet.

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.

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   Maybe you could have a coin hold a standard usb drive, just pull it in half and plug it in even easier to read.  Unfortunately smart phones dont have usb readers. 

btw it also occurs to me you could safely sell unloaded coins also, just engrave an address on the coin and include the public key on the embedded flash card.  User loads by spending to that public key and some chosen base they chose themselves.


Also another weird thing you can do (unrelated to physical coins) if you allow user computed bases via y-th root, is have a public key which is human readable, without address mining.  (Note address remains unreadable as its a hash of public key).  eg your public key could be your email address.  Possibly a bit dangerous because there is no registration to prove its your address, though I suppose they could email you to check... however you probably wouldnt want to transfer a coin with your address as its public key via a base change.  (Just spend it normally to recipient).

Unfortunately you cant chose both base and public key arbitrarily - you cant do it with out breaking discrete log - you can chose either the base or the public key arbitrarily.  To chose a point arbitrarily you have to use something called hash2curve - strings are not always valid points on the curve, so a simple deterministic algorithm is used to chose closest change from the string to make it into a point on the curve.  eg see 4.1.1 of http://tools.ietf.org/html/draft-harkins-tls-pwd-03.

Adam

[Sergio_Demian_Lerner]

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   Maybe you could have a coin hold a standard usb drive, just pull it in half and plug it in even easier to read.  Unfortunately smart phones dont have usb readers. 

This is what I did: check the new thread: https://bitcointalk.org/index.php?topic=232898.0

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

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.

You can check how this protocol work in : http://firmcoin.com/?page_id=14

And also the firmcoin is rechargeable. You can store some funds, extract them, and store additional funds (the device generates a new private key address each time you load funds, using a hardware random number generator).

Best regards, Sergio.

[bluemeanie1]

Seems you guys aren't familiar with the history of these products and what's currently available.

If you're willing to get into complex hardware, you can always go the Smart Card route which is a very cheap way of printing an IC onto a piece of plastic like a credit card.  This IC is the actual crypto function, and the private key is embedded into it.  In order to get the private key, you need to either get it from the manufacturer or reverse engineer with a electron microscope and an evil genius for hire.

Smart Cards came out many years ago but were never really put into widespread use.  https://en.wikipedia.org/wiki/Smart_card .  I imagine that SCs are even more cheap today with what is available.  Sergio, the issues of tampering with the physical factor have been solved long ago.  Smart Cards caught on more in Europe than the Americas.

Of course you can introduce more factors into the auth process such as passwords or additional keys without modifying or replacing the smart card artifact.  You don't really need much fancy math to give you these basic functions.  Basically all you need is a smart card reader(some laptops have this or you could implement one very cheaply), and some simple software.  It's far more secure than regular credit cards.

I also came up with a way to implement a useful paper wallet using Visual Cryptography.  You can implement this scheme with a simple laser printer.  Adding holographic serial numbers greatly enhances the security though(these can be obtained pre-printed for acceptable prices).

https://bitcointalk.org/index.php?topic=226671.msg2386001#msg2386001

[adam3us]

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  

This is what I did: check the new thread: https://bitcointalk.org/index.php?topic=232898.0

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!

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

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

[bluemeanie1]

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.

[Sergio_Demian_Lerner]

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

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.

[Sergio_Demian_Lerner]

And if a chip manufacturer is caught making counterfeit chips, then it will have a huge legal problem.

[razorfishsl]

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.

[adam3us]

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

[adam3us]

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

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

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

[bluemeanie1]

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

[bluemeanie1]

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

[jackjack]

what's the point of having the physical coin at all?

The answer is already in this thread. First post. First line.

[adam3us]

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:

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

[Sergio_Demian_Lerner]

 

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:

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.

[oakpacific]

I think you have read this before https://bitcointalk.org/index.php?topic=66862.msg776957#msg776957  Adam?