•   over 11 years ago

Conceptual question - Preventing Double-Spending Offline

"MintChip works online and offline (...) and enables easy person-to-person payments."

I'm having trouble understanding how MintChip solves the double-spending vulnerability when used for offline person-to-person payments.

Three people:
- Dennis the Menace
- Emily
- Sarah

Suppose Dennis has a rogue MintChip implementation that has been modified to "conveniently skip" the step of decreasing his own balance after sending a payment. The following transactions occur offline, so there is no access to a centralized resource (server) during this scenario.

Emily, in good faith, receives a successful transfer of MintChip currency from Dennis. Dennis does not decrease his MintChip's balance, instead, he meets Sarah, and transfers to her the same funds that were previously sent to Emily.

If neither transaction was done "online", then how does Sarah's MintChip implementation know that Emily has already been transferred the same MintChip balance that she just herself received a duplicate of? There is no opportunity for communication with a central/common record.

  • 10 comments

  •   •   over 11 years ago

    If Dennis has a rogue MintChip implementation, then there's nothing preventing this.

    Your example is the digital equivalent to counterfeiting. The encryption on the MintChip is meant to be the digital equivalent to all of the anti-counterfeiting measures in cash. In theory, with enough resources available to you, you could crack the encryption on MintChip, much like you could successfully counterfeit cash.

    The drive behind anti-counterfeiting measures is to make the process so expensive that it's just not worth it. The state of the MintChip's encryption, and whether it is at that level of expense to break, is unknown to the public; there was an early outcry by security-conscious people regarding this when this contest first started, but it was stated that the system was to remain closed for now. I'm sure (or rather, I sure *hope*!) that before MintChip becomes a released technology, vetting by security professionals will take place, so concerns such as yours are satisfied.

  •   •   over 11 years ago

    Is nobody concerned about this presently? Relying on the belief that a rogue implementation is impossible or too costly to create, is a fundamental mistake. As we've seen from countless examples (DVD encryption, BluRay encryption, etc) in recent history rogue implementations of supposedly secure systems happen, and generally relatively quickly (particularly when there is a motivating factor).

    I gather that this proposed system must at the very least be requiring a physical MintChip IC in every phone/tablet/computer, etc, that is involved in a transaction. That would seem the only way to slow the this process down. I'll grant that it is more difficult to tamper with a hardware system than with a software system, but it's still inevitable that the hardware itself would eventually be cloned and tampered with, potentially even emulated in software.

    For a cash-replacement system to be "better than cash", there shouldn't be such an blatant vulnerability. We certainly shouldn't be relying on the assumption that a hardware chip can't be hacked. This has never, at any point in history, proven to be a valid assumption.

  •   •   over 11 years ago

    I would expect that the Mint is working on this, sure. They're fully aware that trust and reliability in that part of the system is crucial.

    Yes, the physical chip is required, whether on your local device or Hosted remotely. And yes, if that inevitability you speak of is there, the system will fail. But again, it comes down to the cost of that inevitability. Electron microscopes or whathaveyou can be used to peek inside the chip, but the equipment and expertise is the "cost" involved in this counterfeiting. Here's for hoping that cost can be kept prohibitively high.

    This "blatant vulnerability" is the same one that exists for any online transactions: it's breaking public/private key encryption to your remote server, or breaking similar encryption on the chip. We trust SSL certificates to our banks, or to PayPal, because we're either blindly believing it's safe, or we're security experts that have analyzed its encryption methods. The same expectations of users will be made for MintChip.

    For now, though, this contest is for generating proofs-of-concept, seeing what kind of usage the MintChip system would see, what kinds of interfaces people can devise. I'm writing my contest submission, and, if MintChip was to go public, could certainly look to release software that utilizes it. As for being a user of MintChip itself, I would have the same concerns as you, and will wait to see what security experts say.

  •   •   over 11 years ago

    "This 'blatant vulnerability' is the same one that exists for any online transactions: it's breaking public/private key encryption to your remote server, or breaking similar encryption on the chip."

    I'm not sure that this is true. I think it is important to remain conscious of _where_ the security is actually derived from. In many systems of exchange or transfer, the security is entirely derived from cryptography. That is to say it is entirely derived from the known difficulty of doing certain very complicated time-consuming mathematical operations. With security that is derived entirely from cryptography, we can have an extremely high level of confidence in the fact that, if implemented correctly, the system cannot be practically defeated.

    However, in the MintChip system, it sounds like the security is not _entirely_ derived from the security of the underlying encryption. While that's still a big component of the overall security, we're also relying on something much less predictable; the physical/mechanical security that protects the data and code on the MintChip itself. For the MintChip system to remain secure, we're counting on each user's MintChip to "behave properly".

    The important point here:
    You don't need to actually break public/private key encryption in order to leverage the vulnerability. The MintChip would merely need to be modified to "skip" the step of decreasing its own balance.

    Here's an easy way of illustrating why the vulnerability doesn't require breaking any encryption:
    Suppose that a Bad Actor is able to read the contents of the MintChip's memory, bit for bit. We can even stipulate that the Bad Actor has no working knowledge of cryptography. He simply creates a bit-for-bit copy of the MintChip's memory, but understands none of what it means. The Bad Actor then transfer, offline, the entire monetary contents of his MintChip to Person A. Following that, he promptly restores, bit for bit, the state of his MintChip's memory that was backed-up prior to the transfer. He then proceeds to transfer the entire monetary contents of his MintChip to Person B.

    The Bad Actor has double-spent the same money, without any need to break, nor even understand, public/private key cryptography.

    I will grant that hardware is generally more difficult to tamper with, alter, copy, etc than software. I certainly don't mean to suggest that reading the contents of hardware storage is trivial. But "more secure than software" is not the equivilent of "secure". In fact, if we're talking about relative measures of security, history shows that relying on physical or mechanical security is several orders of magnitude LESS secure than relying entirely on cryptographic security

    The problem is straight forward. With physical access to the hardware, "bad actors" will eventually be able to defeat it, alter it, clone it, etc. Whether you draw your examples from hardware DRM systems, satellite decryption boxes, or Trusted Platform Modules in computers, the only constant is that harwdware is eventually compromised by someone. This happens faster when there is a monetary motivation.

    My point in the above, is to highlight the fact that it's misleading to pretend that compromise requires breaking the (provably strong) public/private cryptography. It doesn't. Security here is riding on something much less inherently secure: plastic, silicone, and the difficulty of looking at really small things.

  •   •   over 11 years ago

    I too wonder how exactly how the hardware security works, but I am pretty confident that they won't release a system with huge problems.

    I can see them getting to the point where cloning the chip is the only way to comprise the security, as in your bad actor example. Do you have any idea how much it'd cost to clone a single chip (not mass produced)? It'd be extremely expensive, probably running close to thousands of dollars.

    Your bad actor example is the exact equivalent of copying money. Yes it's possible to copy a $100 bill, but it is by no means easy. The thing preventing counterfeits is the fact that it's a ultra high risk operation, with very little profit (if any) because of the cost to reproduce and print money. If anyone legitimately wants to break they law, they are smarter off getting into profitable things like drug dealing or stealing candy bars from stores (which ultimately would be more profitable).

    Your earlier example of skipping the deduction step might be possible in theory based upon the design of it, but there are many possible ways of catching this. First of all (an idea for an app maybe), stores could subscribe to a counterfeit detection where it can check all sorts of things about the person's chip, and catch people who's chip frequently come get used on the network (people who buy things from stores, namely pretty much everyone). Another way is for the chip to produce transaction keys which have some sort of checksum or relate in some way to the transaction history. Devices can then check the transactions they receive, and verify it with previous ones, making sure that a rouge chip couldn't be used twice with the same chip (unless it cracks the key generation, which would be difficult). And finally one way that could be used is simply by limiting the number of times the device could be used (possibly by physically destroying a part of the device). This would force people to get new chips every so often, (ie when you go to a bank next) that way the chips can constantly be changing, just as our current paper currency is. Yes older versions could still be counterfeited, but the same is true for currency, and it relies on people noticing older currency. If you go the bank with $10 000 in old bills, they are going to get pretty curious.

    Basically any problem in mint chip is most likely already present in our current monetary system, and it's proven to not be much of a problem already.

  •   •   over 11 years ago

    "Do you have any idea how much it'd cost to clone a single chip (not mass produced)? It'd be extremely expensive, probably running close to thousands of dollars."

    Oh gosh, I'm in agreement with you on that point, for certain. In fact, I would be happy to stipulate that the cost could be much higher than thousands of dollars for a single chip. The problem, is that anyone putting in the work to duplicate a single chip, wouldn't just do it once. Once they had invested the time, research, and money into the process of hardware duplication, they would certainly do it many times over, with declining marginal expense, and they would surely use each duplicated chip to double spend the same currency many times over.

    "Your bad actor example is the exact equivalent of copying money."

    That is exactly my point. But unfortunately, fiat currency is not the gold standard of monetary security (I enjoyed writing that). Fiat currency is highly prone to counterfeit, so it's illogical to use paper bills as the bar to measure the security of something new. The whole point to MintChip is surely to create something a lot *more* secure than yesterday's money. Let me now address your proposed solutions to the offline double-spend vulnerability.

    "...stores could subscribe to a counterfeit detection where it can check all sorts of things about the person's chip, and catch people who's chip frequently come get used on the network (people who buy things from stores, namely pretty much everyone). "

    A system like this could have merit, and indeed might give the counterfeiters a relatively short spam of use for each rogue device. However, it wouldn't be effective in offline situations because there would be no way for the data about the multiple duplicate charges to reach the point of data aggregation, nor would there be a way for an alert of any type to be sent to the potential future recipient of duplicate funds.

    Second, I would comment that allowing data about individual chips to be released externally is a double edged sword. The more data you allow to be broadcast from your secure hardware, the greater an opportunity that exists for side channel attacks (deducing information about the internal state of the hardware based on external signals, timing, behaviors, etc).

    Third, it violates a central principal of the direct asset transfer model upon which MintChip is based: that value is moved between trusted stores without the involvement of any intermediary. The insertion of an intermediary into the equation changes the nature of the MintChip. It no longer has the private exchange capabilities of currency. Even if the Mint made peace with this type of massive conceptual change, it would dramatically change the public's reaction to the system. Frankly, you would have a whole lot of people flatly refusing to substitute the MintChip for currency, if purchases and activity was being tracking and provided to stores who subscribed to a service.

    "Another way is for the chip to produce transaction keys which have some sort of checksum or relate in some way to the transaction history. Devices can then check the transactions they receive, and verify (...)"

    There are two problems here. The first, is that you need to have the actual data about transaction history. This implies that there is some sort of centralized repository from which to download the data that you require in order to generate the checksum. This also violates the principal against an intermediary, and has the same implications that I discussed above.

    The second issue, once again, is that this approach doesn't work in an offline scenario where the parties to a transaction have no way of accessing the transaction history to verify the checksum that has been transmitted with a payment.

    "And finally one way that could be used is simply by limiting the number of times the device could be used (possibly by physically destroying a part of the device). This would force people to get new chips every so often, (ie when you go to a bank next) that way the chips can constantly be changing, just as our current paper currency is."

    I see that you're really brainstorming on this issue, and that's a good thing! But there are some critical problems with this solution too. It ignores the fundamental insecurity that is generated by MintChip giving responsibility for security to devices that are under the physical control of potential rogues. Conceptually, it isn't that different from taking something valuable, putting it in a really secure box, and then asking a criminal to transport it. In the present case, a rogue who had modified a MintChip to skip the deduction step, would certainly modify it to skip the use limit or physical self destruction step too. If the rogue was cloning rather than modifying a chip, they would simply fail to duplicate that aspect of the hardware.

    Further, in order for a use-limit to actually be able to meaningfully prevent much "double spending", that limit would have to be exceedingly low. For example, if the use limit was 100, that would still allow someone to double-spend a lot of money, potentially hundreds of thousands of dollars. But even at 100, such a limited life span for a MintChip would make it many times shorter lived than fiat currency. Unfortunately this solution is battling on two fronts. Even at use-limits much higher than you'd need for it to be an effective solution to the offline double-spending flaw, you're already limiting a MintChip's life to being much shorter than would be required for it to be useful (and economically viable) as a replacement for currency.

    "Basically any problem in mint chip is most likely already present in our current monetary system, and it's proven to not be much of a problem already."

    I think a lot of people would disagree with your analysis that it has proven to "not be much of a problem". I remember 5 or so years ago reading that the Bank of Canada was concerned that counterfeiting had reached very dangerous levels in Canada, and that we were among the worst countries for it. There are economic implications associated directly with the counterfeiting itself, not to mention the fact that the funds generated by these enterprises are not generally being funneled back to girl guides and community centers. You can bet on the fact that the money generated through counterfeiting is going somewhere that you wouldn't want it to go, which compounds the issue even further.

    What is needed is a system that is better than currency, not just "on par". Otherwise the MintChip isn't evolutionary, and while it may still be intriguing to technology enthusiasts, it won't gain mainstream adoption of their are major security holes left addressed.

    I'm never fond of criticizing without offering a solution. The offline double-spend weakness has only one truly secure solution that I can see, and that is to remove offline payment capability from the specification.

  •   •   over 11 years ago

    The checksum for the transaction history can easily be used offline. Each device has it's own transaction history, and can therefore calculate a checksum into the generated key. The reciever can then merely check this against checksum's it's already recieved for the device, and alert if the device has an identical checksum. Regardless none of the solutions are amazing solutions in and of themselves, but some combination of them could be employed, and together it'd make life really difficult for the counterfeiter.

    I think we're both on the agreement that at the very least Mintchip is as secure as money, with potential to become more secure.

    You mentioned that counterfeiting was terrible in Canada, which may be true, but if a country is aware of the counterfeiting levels, it can negate the inflation associated with counterfeiting, by simply printing less itself. This solves the problem of counterfeiting hurting our economy, and we're just left with the money being left in the wrong hands, which is a problem true, but it's something where people get caught for.

    You need to realize that the point of mintchip is to replace cash. ie purchases about $10 or so, when you go to McDonalds, or lend your friend $20. There is a limit on how much each chip can hold, and I don't think that limit is very high (I can't seem to find the discussion right now, but I think it's somewhere in the $500 range) so counterfeiting these don't give you a lot of money in a short time, they would give you a little money for a long period of time, which most criminals aren't interested in anyways. What they might do is create thousands of them, which has a pretty big chance of getting caught if your mass producing (since not many people have electron beams, the sale of one would be noticed).

    If there is a better solution to replace cash that I'd love to hear it, but there is no known decentralized solution that can replace cash while remaining offline transactions.

  •   •   over 11 years ago

    "The reciever can then merely check this against checksum's it's already recieved for the device, and alert if the device has an identical checksum."

    Not offline it can't. If the first transaction was done offline, and the second transaction was done offline, there's no way for any sort of feedback from the first transaction to make its way into the shared knowledge of transactions that the second recipient would reference. Therefor, the rogue would simply reuse the same "checksum" that they had used for the first transaction, and the second recipient would consider it to be unique (or it would pass whatever test was being imposed, as if it was the first transfer). The core problem, is that there is no way for knowledge of the first transaction to reach the second potential recipient of duplicate funds, if the transactions both occur offline. The only communication innocent recipient 1 has with innocent recipient 2 is essentially via the potential rogue. As I've stressed earlier, you cannot rely upon the rogue to maintain the security of the system.

    "I think we're both on the agreement that at the very least Mintchip is as secure as money, with potential to become more secure."

    I'm not really sure if I would agree with this point. I'd need to give that some thought. In cryptography, massive failures usually start with very small cracks. A researcher will find a theoretical weakness in some aspect of hashing, or they'll determine that entropy is a bit lower than originally thought, etc. Then these cracks get leveraged a bit further, and a bit further, until they're huge blatant gaps of insecurity, and we eventually have to move way from the underlying technology. The problem with this MintChip vulnerability, is that it's already at that "huge blatant gap of insecurity" stage. It has an obvious weakness that requires (and this is an important point) absolutely no further cryptographic insight or clever math to exploit. The only security against the offline double-spend flaw is security through obscurity (ie, the physical security encasing the hardware that you don't want tampered with).

    "If there is a better solution to replace cash that I'd love to hear it, but there is no known decentralized solution that can replace cash while remaining offline transactions."

    I agree with you on this point.

    I believe that with just the recipient having a data connection, you can make the system secure. You could make a data connection optional for the recipient, with the caveat that until you register receipt of a transfer, that transfer is not indefeasibly yours. IE, it is your money, but it is voidable (but not void) until the point at which you either register the receipt through a data connection, or re-transmit the same money to another party who does.

    Even though it's not a perfect solution, it's the best that can be done, and it's a decent compromise. You get the option of an entirely offline transaction. So if you really trusted the sender, you could still feel comfortable receiving the money, knowing that it wasn't indefeasibly secured by registering the receipt of funds online. Perhaps you're camping out in the wilderness with no data connection, and your brother wants to transfer you some money he owes you for fishing supplies. In that scenario, you wouldn't be concerned that he was a rogue, so you'd trust the transaction without registering receipt. But you'd probably still register receipt once you had a data connection again.

    However, if you're at a folk arts festival in a field somewhere rural with no data, and a travelling snake oil salesman asks to buy your hat, and you agree, you might decide not to use MintChip, or at the very least, to try and get to a data connection as quickly as possible to register receipt of the funds and claim indefeasible title to them.

    Other than that, there really is no safe way to do fully offline transfers, and preclude the possibility of a double-spend attack. You really don't have to think through a lot of complex cryptography to come to that conclusion, and you can't brainstorm anything fancy on the algorithm front to cure. The flaw is basically one emanating from a lack of knowledge. If person A gives something to person B, there's no way for person C to know about it, unless person A, B, or an outsider, tells them. B will long since be out of the picture, and if it's an offline scenario, there won't be anyone else do communicate with C. Since A is the rogue, you can't trust him to do anything he's supposed to, so C is left, at best, with the knowledge C had prior to going dark (loosing data connection). So, assuming the A to B transfer happened after C lost data connection, there is absolutely no way for C to know about A's previous transfer of the "whatever" to B.

    This works equally well with MintChips as it does with Oranges.

  •   •   over 11 years ago

    The checksum I was suggesting was an offline one, where a mintchip kept track of the checksums of all the interactions it's had with other mintchips. Let's say we have A,B,C and A is rogue. If A goes to B, spends money, then C, and spends money, then yes they have double spent. But if A goes back to B, they will be caught, and I'm just using this under the assumption that eventually you might want to go back to the same store again, otherwise you can rip everyone off by a little bit, but you have to be careful.

    Online only transactions definitely can't be the only form of transaction. Like you said, you go to a county fair, or a campground store, or anything, there probably isn't a data connection there, so what are you going to use? Cash? Well then this whole system is moot anyways, since you could have just done that in the first place.

    You need to allow the user to use their mintchip offline by some method. With your proposed method, the vendor is the one that loses the money if the rogue chip is used. Even worse, people might not even know that they are ripping them off (for instance not having enough money). With mintchip's proposed method, offline transactions will go through unless someone cracks the system, and creates their own mintchips with mass production like equipment. Even then you could add online security such as reporting of checksums online as well as the offline method, or some other check, and this additional online security would be enough to catch the majority of rogue mint chips. (If it has some sort of cryptographic hash of the chip ID in it, then that means you'd need to duplicate the hash and the chip ID, which would be an instant red flag if 2 are used at once).

    Both of our solutions have great security when used online, so then we should really only consider the weakest link of our solutions, offline. Your offline solution is basically completely insecure, requiring no modifying of hardware or software to double charge, or overcharge. The only way you could make your offline work securely is by implementing the same system mintchip has.

    With any system you must look at the weakest link, cash's weakest link is older bills, which have less security, and mintchips weakest link is when the mintchips can't be used online (which should only be between two friends, or for stuff like parking meters and vending machines. Any major stores and stuff should be able to do it online).

  •   •   over 11 years ago

    "...if A goes back to B, they will be caught..."

    Then yes, that would work. But it would only prevent a rogue from double-spending with someone they had already transacted with previously. I presume they would just intentionally avoid doing this.

    "Like you said, you go to a county fair, or a campground store, or anything, there probably isn't a data connection there, so what are you going to use?"

    Well, depending on the time horizon for actually implementing MintChip, maybe we've made a flawed assumption in thinking that data connections cannot be taken for granted. Maybe 5 years from now, they can. For the incredibly low amount of data that actually needs to be transmitted (just some text), maybe there would be a way to pop up a couple cheap satellites and cover Canadian with very low bandwidth coverage for specifically this purpose. If we're talking 5 years out, etc, there may actually be cellular connections to more locations, and perhaps to almost all of the locations where commercial activity would be taking place.

    "Your offline solution is basically completely insecure, requiring no modifying of hardware or software to double charge, or overcharge."

    No no, my offline solution was a suggestion for what could be layered on top of the existing MintChip protocol, and it would also presume the introduction of some sort of centralized transaction registry. That alone would be a big concern for a lot of people. You don't have to be a paranoid nutbag to be concerned about every transaction you make getting recorded. I think a lot of people, regular people, would be nervous about any sort of centralized database of activity. For the record, it doesn't bother me. I rarely if ever carry cash, so right now it's my bank and credit card issuer who know me best. But I still know a lot of people who withdraw cash to spend at the drug store and on groceries, instead of putting it on plastic. Those type of people are equally likely to avoid a cash-replacement system that has a centralized component.

    Something eye opening just popped into my head:

    Most of the MintChip literature and publicity talks about the fact that this system does not require any sort of centralized coordination, that it doesn't need to track transactions, etc etc etc. Well, we've just spent a few days brainstorming on practical application issues, and the only way to make the system truly safe, was basically to layer on, whenever possible, a "centralized" or "coordinated" entity that could "track transactions" and prevent duplicates. So while the system could function the way it is being promoted, in practice, it is pretty likely to get a bunch of backend services and verification schemes grafted on to it. The brains behind MintChip must be conscious of this reality too?

Comments are closed.