How computationally expensive is an ECDSA and signature calculation?

[Sword Smith]

I do not know how much a bitcoin credit card has been discussed on this forum. By a bitcoin credit card I mean a credit card containing the private key (encrypted of course) capable of making and signing bitcoin transactions to the network such that the chip itself calculates the writes the transaction and signature and the transmits it to a credit card terminal (POS) into which the credit card has been inserted. A search on this did not reveal anything.

A transaction needs to be signed in order to be valid. The signature is calculated from the private key and some kind of hash(?) of the transaction using the ECDSA (Elliptic Curve Digital Signature Algorithm). My question is: How computationally expensive is it to sign a transaction and specifically, do you think that a chip on a credit card would be able to perform this calculation? I am thinking about normal credit card chips which follow the ISO standard 7816 and a standard called EMV. I believe that this is the chip being used in most credit cards:
http://www.maximintegrated.com/datasheet/index.mvp/id/2949
As far as I understand, these chips already perform other kinds of encryption calculations like triple DES and RSA:
http://en.wikipedia.org/wiki/Smart_card


More information on the interface can be found here:
http://www.maximintegrated.com/app-notes/index.mvp/id/4029

tl;dr: Can a DS5002 Secure Microprocessor Chip calculate 256 bit ECDSA?

[Realpra]

A card chip can do it.

The card I use however uses a cryptographic co-processor to do the signatures so the cheapest cards usually cant do it.

It takes less than a second, though I did not time it more exactly than that.

[Sword Smith]

A card chip can do it.

The card I use however uses a cryptographic co-processor to do the signatures so the cheapest cards usually cant do it.

It takes less than a second, though I did not time it more exactly than that.

Thank you for your answer. That sounds very exciting! Do you have a link to a report or some numbers where I can read more about it?

Edit: Just found your thread on this. Will be reading up on it.

[Mike Hearn]

Visa and Mastercard are upgrading EMV to use an ECDHE handshake between card and terminal. So regular credit cards will be able to do at least some EC crypto soon.

However those card chips are proprietary and cannot be programmed.

It's the wrong model for Bitcoin anyway. Look at the Trezor instead.

[Sword Smith]

Visa and Mastercard are upgrading EMV to use an ECDHE handshake between card and terminal. So regular credit cards will be able to do at least some EC crypto soon.

However those card chips are proprietary and cannot be programmed.

It's the wrong model for Bitcoin anyway. Look at the Trezor instead.

Why is it the wrong model for Bitcoin? The good thing about is that customers are used to smart cards and POSs. And a correctly designed smart card can, in the POS, do exactly what Trezor does.

[riplin]

Visa and Mastercard are upgrading EMV to use an ECDHE handshake between card and terminal. So regular credit cards will be able to do at least some EC crypto soon.

However those card chips are proprietary and cannot be programmed.

It's the wrong model for Bitcoin anyway. Look at the Trezor instead.

Why is it the wrong model for Bitcoin? The good thing about is that customers are used to smart cards and POSs. And a correctly designed smart card can, in the POS, do exactly what Trezor does.

No it can't. The POS could show you a transaction for 1 BTC, but have your card sign a transaction for 10 BTC.

[Realpra]

No it can't. The POS could show you a transaction for 1 BTC, but have your card sign a transaction for 10 BTC.

I solved that ages ago. The card encrypts the amount with a "passphrase" the card owner knows and sends this to the terminal, hence the terminal cannot fake the amount actually sent to the card.

As for the cards programmability both Java cards and BasicCards can be programmed at will and bought by largely anyone.

[Mike Hearn]

You're expecting people to do mental arithmetic to check for bogus terminals?

Everyone walks around with a portable computer in their pocket these days. People will just use phones instead.

[Realpra]

You're expecting people to do mental arithmetic to check for bogus terminals?

Everyone walks around with a portable computer in their pocket these days. People will just use phones instead.

If by "everyone" you mean half or less than half the world's population sure:
http://www.go-gulf.com/blog/smartphone/
Of those only 29% have mobile internet:
http://en.wikipedia.org/wiki/List_of_countries_by_number_of_broadband_Internet_subscriptions

The mental arithmetic is not required, you can just put your PIN. There are also other safe guards so the 10 BTC charge can not happen.

My grandmother has trouble enabling her phone's USB storage device connection type - so good luck with a complex app that requires constant internet connection to function and will crash her phone if she installs the wrong non-light app.

I consider my potential market share very decent

[EmperorBob]

The mental arithmetic is not required, you can just put your PIN. There are also other safe guards so the 10 BTC charge can not happen.

You do understand that that's impossible right? If the terminal is bogus, and the terminal is the only thing that can communicate with the card, then you can't make this secure.
It's not a problem for credit cards, because you can just do a chargeback, but they do have the same vulnerability.

[Realpra]

You do understand that that's impossible right? If the terminal is bogus, and the terminal is the only thing that can communicate with the card, then you can't make this secure.
It's not a problem for credit cards, because you can just do a chargeback, but they do have the same vulnerability.

Just saying things don't make them true and you clearly have no idea what you are talking about.

Its all about protocol, if it is secure it doesn't matter if the terminal is trusted or not - much like Bitcoin client communication.

[EmperorBob]

Just saying things don't make them true and you clearly have no idea what you are talking about.

Its all about protocol, if it is secure it doesn't matter if the terminal is trusted or not - much like Bitcoin client communication.

Ok, let me justify my statement:

1. You have a credit card style terminal.
2. You have a small device with a chip (and no user-facing interface).
3. The terminal is actually built/compromised by an attacker.
4. The terminal shows you a transaction for 0.1 BTC. You press ok, enter your PIN, yadda yadda yadda.
5. The terminal sends your pin, and a transaction for 10 BTC.

How does the card know this isn't valid?

Some solutions that would work:

1. The device does have an interface in the form of a small screen and a yes/no button (No MITM possible).
2. The payment request must be cryptographically signed by the user in order for the device to process it.
3. The device can communicate back to the user in a tamper proof manner (cryptographic signature?), so the terminal can't alter the message displayed on the screen.

Your response so far seems to indicate you're using #3, but unless

You're expecting people to do mental arithmetic to check for bogus terminals?

Then I can't see how you make this work. At all. You could try a weaker form of either inbound or outbound signature, like different pins for each order of magnitude of spending, but any solution that offers a modicum of security is going to be brainpower-expensive.

Not trying to be an asshole here, it's just that a lot of people come here with half-baked ideas, and it's the nice thing to do to point out flaws before they get a chance to hurt themselves or others.

[callem]

Sometimes taking a step back to look at the trust models already common in retail transactions might be valuable.

For a $3 purchase, we hand over a $20 bill and expect to get correct change. The risk that the cashier runs out with our money or otherwise cheats us is a small, acceptable one. Similarly, most people at least in EU and US choose the convenience of credit- or bank cards despite the risks of skimming and other fraud.

The point is that risk will always exist in a trade-off with convenience and ease of use. A retail system based on fidgeting with small hardware wallets or requiring users to program special smart cards will never see wide adoption, especially in a world where instant NFC payments are quickly becoming standard.

Having seen bitcoin payments in cafes, etc. and done a few transactions myself - it's actually pretty surprising that retail shops accept bitcoin at all considering what a clumsy, time consuming process it can be with current solutions, compared to cash or cards.


 

[Realpra]

Just saying things don't make them true and you clearly have no idea what you are talking about.

Its all about protocol, if it is secure it doesn't matter if the terminal is trusted or not - much like Bitcoin client communication.

Ok, let me justify my statement:

1. You have a credit card style terminal.
2. You have a small device with a chip (and no user-facing interface).
3. The terminal is actually built/compromised by an attacker.
4. The terminal shows you a transaction for 0.1 BTC. You press ok, enter your PIN, yadda yadda yadda.
5. The terminal sends your pin, and a transaction for 10 BTC.

How does the card know this isn't valid?

Since you seem genuinely interested there are 3 major safe guards:

1. The card does not know, however it tracks your average spending and will block amounts too much over that normal.

2. The card will convert the charge to say "0004e00" or 4 BTC. It will then substitute the characters like so: "AKGAePO" and send this to the terminal. Since the first and last parts of this are usually the same it will be faily easy for the user to remember that AKG=000 and PO=00. If the terminal were to cheat however the result would be say AKHBePO and by looking at only the first 3 chars the user can tell he is being over charged.
This is called the Vignere cipher and it is faily easy to break - but impossible without some amount of data and a random untrusted terminal only gets to try once.

... or he can just put his PIN and rely on the charge maximum to protect him.

3. If the terminal immediately attempts to charge the card again after having received the PIN it will fail because the card locks itself for a few seconds after each spending. It cannot tell time so the locking works by the terminal polling the card say 1000 times.

[EmperorBob]

That's a decent set of mitigation measures. Having a per transaction spending limit is probably the most important one.
I'll point out one possible attack that still quite feasible:

1. Terminal sends the actual requested amount to the card
2. Terminal shows the response code and displays it to the user. (So far so good)
3. Terminal immediately cancels the transaction and tries to unlock the card. During that time, the user enters his PIN, oblivious to what is going on.
4. The user presses OK. The terminal now knows the PIN.
5. By now the card has unlocked itself. The terminal sends a larger amount for payment, ignores the response code, and sends back the PIN.
6. Card authorizes a larger payment.

Of course this requires that the lockout period be not much longer than the time taken by the user to enter the PIN. But the terminal can nicely slow down the user in a variety of ways, without looking too suspicious:

1. Add a "confirm amount?" screen to check the payment quantity, after having sent the payment request to the card.
2. Mild delay after pressing each key/hard to press keyboard.
3. Pretending the PIN was mistyped the first time and asking to try again.
4. "Connecting to network... please wait..."

You could try to increase the delay to be closer to a minute, but it looks like you can't track time when you're not plugged into a terminal. Tricky.