Fun with Protocols

 A reason why I made this

So many of us, especially the people who have their faces glued to their computer screens half the time (including me), have wondered at some point why America's voting system isn't mostly electronic, where you could just go to a government website, vote for whoever, click, and be done with it instead of driving to some voting center. (Washington State still does mail-in ballots so I dunno how much of a pain Election season is.) This page is to demonstrate how unbelievably fking hard it is to design the perfect system just for this purpose, by playing with much simpler protocols involving cash exchange.

There are 3 different protocols presented here dealing with cash exchange between spenders, merchants, and the bank. Each protocol is designed to give the spender's money order anonymity to the bank (so it can't tell who's money order it was originally) when he makes a transaction, except possibly when he/she tries to cheat. The higher numbered protocols are more complicated and more secure than the previous one.

Your goal is to get more money into circulation than what you wrote for withdrawal from the bank! It does not count if you get caught later on. Anyone (not everyone) can get more money, including someone you've never met before, and you can be anyone, whether it is a participant in the protocol or an outsider.

And here's a tip: read carefully =P

In all the protocols, assume the following:
--Everyone participating in the protocol cannot be attacked in any shape, way or form, including hydrogen bombs, internet viruses, anthrax, paper cuts, whatever. If someone's getting hurt, then you're not following the rules.
--Everyone is assumed to have unlimited resources; unlimited paper, unlimited computing power (but you still can't violate the first rule), unlimited whatever.
--The bank is infallible. That is, it will always remain operational and does whatever it is suppose to do 100% correctly, given its knowledge and circumstances. It also cannot deliberately cheat for any reason whatsoever; it must be completely honest.
--Since the goal of this challenge is to swindle the bank, we'll assume that it balances its checkbook predictably every week or so. This is the only exception to the above rule.
--In any circumstance where you attempt to subvert the protocol where chance is involved, you automatically fail. Yes, even if you have a 99% chance of succeeding (which will never happen anyways).
--Unless stated otherwise, all and any messages/communications are assumed to be readable and unencrypted, as well as containing minimal information.

 Protocol 1

1. Gregory prepares n amount of money orders for x amount of dollars
2. Gregory seals the money order along with carbon paper in envelopes, and gives them all to the bank.
3. The bank opens n - 1 envelopes at random, and confirms that they're all money orders for x amount of dollars.
4. After verifying the opened money orders, the bank signs the last sealed envelope under the assumption it is also a money order for x amount of dollars, certifying that the money order is valid. The carbon paper Gregory put inside the envelope ensures that the signature gets imprinted on the money order. Then the bank deducts x amount of dollars from Gregory's account.
5. Gregory later opens the sealed envelope and spends the money order with a merchant. (it can be any merchant)
6. The merchant checks the money order to make sure it is signed by the bank and thus legitimate.
7. The merchant takes the money order to the bank.
8. The bank verifies its signature and credits x amount of dollars to the merchant's account.

 Give up?

Either Gregory or the merchant can photocopy the money order. The bank is none the wiser since it cannot tell who's money order it originally was, and it can't zero in on who the possible culprits are since it is also dealing with potentially thousands of other customers. This is the easiest way to subvert the protocol.

 Protocol 2

1. Gregory prepares n amount of money orders with the following information:
   
   1. x amount of dollars
   2. A random, uniqueness sequence of numbers/letters in which all such sequences are different. Such a sequence should have virtually no chance of being randomly generated.
2. Gregory puts the money orders with carbon paper into envelopes and seals them. He gives them all to the bank.
3. The bank opens n - 1 envelopes at random and confirms that each money order is for x amount of dollars, and that each uniqueness sequence is different from each other.
4. The bank signs the last sealed envelope, confident that it is also a money order for x amount of dollars. The signature gets printed onto the money order itself thanks to the carbon paper. Then the bank deducts x amount of dollars from Gregory's account.
5. Gregory later opens the envelope and spends the money order with a merchant.
6. The merchant verifies the signature to make sure the money order is legitimate.
7. The merchant takes the money order to the bank.
8. The bank verifies its signature and checks its database of uniqueness sequences for a sequence matching the one on the money order.
   
   1. If the bank can't find a match, then the new sequence gets recorded, and the bank credits x amount of dollars to the merchant's account.
   2. If the bank finds a match, then the money order is rejected.

 Protocol 3

Welcome to cyberspace, b!tches. If you need technical details on some of the mumbo jumbo, feel free to ask.

1. Gregory prepares n amount of money orders with the following information:
   
   1. x amount of dollars
   2. A random uniqueness string of fixed length, where the chances of the same string being randomly generated are virtually none.
   3. n pairs of identity strings with a left half and a right half. Both halves are unreadable by themselves (it's not as simple as splitting a watermelon in half). The combination of corresponding pairs will reveal whatever identifying information the bank desires, such as the name and address of the person who originally wrote the money order. Compatible identity strings can be identified as compatible with each other with ease. The identity strings are also involved in a separate protocol, later important at step 8.
2. Gregory "blinds" all n money orders using a blind signature protocol (this is basically the same as sticking paper money orders and carbon paper into an envelope). He gives them all to the bank.
3. The bank asks Gregory to "unblind" n - 1 money orders at random and checks that everything is in order. The bank even asks Gregory to reveal all of the identity string pairs.
4. Once the bank is satisfied that nothing suspicious is going on, the bank digitally signs the last "blinded" money order (digital signatures are made such that tampering with the document invalidates the signature, otherwise what's the point?) and deducts x amount of dollars from Gregory's account.
5. Gregory "unblinds" the money order (with math magic, this doesn't affect the signature) and spends it with a merchant.
6. The merchant verifies the bank's signature to make sure the money order is legitimate.
7. The merchant requests that Gregory randomly reveal either the left half or the right half of the pairs of identity strings, by giving Gregory a random n-bit selector string.
8. Gregory complies, using the protocol he committed to earlier at step 1.
9. The merchant takes the money order to the bank.
10. The bank verifies the signature and checks its database for a matching uniqueness string and "revealed" identity strings ("revealed" at step 8).
    
    1. If the bank cannot find a matching uniqueness string, it credits the merchant for x amount of dollars, and records the uniqueness string and all of the "revealed" identity strings.
    2. If the bank finds a matching uniqueness string, and finds a matching series of identity strings, then it rejects the money order. Punishment is meted out to the merchant.
    3. If the bank finds a matching uniqueness string, but finds no matching series of identity strings, then it rejects the money order, and looks at the different series of identity strings. Once it finds a corresponding pair, the bank simply combines them to obtain Gregory's identity. Punishment is meted out to Gregory.

If you can subvert protocol 3 successfully, then you can easily see why security has to be incredibly air-tight, and why No Such Agency is heavily involved in "being in ur compooterz, listenin to ur n3farious pl0tz."

I really can't figure a thing out. *brain asplodes*

Can he double-load envelopes without being detected in the ones they open? (carbon, order, carbon, order) Maybe by having a secret pocket in the envelope...

 #2

He could just write extra digits onto the uniqueness sequence

I remember something similar to the "open n-1" thing from my cybersecurity course.

Can he double-load envelopes without being detected in the ones they open? (carbon, order, carbon, order) Maybe by having a secret pocket in the envelope...

 #2

He could just write extra digits onto the uniqueness sequence

 #2

Haha, nice Stereo. A uniqueness sequence, by default for its purposes, is suppose to be of fixed length, but I neglected to mention that. See if you can do #3 now, that one's by far the hardest one.

As for the secret pocket in the envelope, that's pretty insecure. There's a chance that the bank would notice when opening, say, 99 envelopes, or they might have a precise massing machine. They're the ones that define the screening process after all.

I remember something similar to the "open n-1" thing from my cybersecurity course.

That's the basic "Blind Signature" protocol, meant to prevent malicious cheaters from simply getting the bank to blindly sign a money order saying it's worth x factorial amount, or some other magnanimous number that is far beyond your capacity. The same protocol also includes fancy math that does a document scramble or "encryption", rendering it unreadable until you reverse the process.

In step 3, who decides which to 'unblind' and do they have visible uniqueness identifiers to ensure that Gregory actually opens those ones?

And since it's not stated explicitly, I assume by "checking everything's ok" the bank verifies that each has a unique ID they haven't already got, money values are all the same, and the id pairs all work out to a valid address.



On second thought, Gregory and the merchant just have to collude to fake the identity string half. Even if uniqueness matches, the bank won't know who to punish if it's incorrect.

Having never dealt with anything of the like before, I'm going to ask what is probably a stupid question.

"Gregory prepares n amount of money orders for x amount of dollars" - what is n for? Is it just any number?

In step 3, who decides which to 'unblind' and do they have visible uniqueness identifiers to ensure that Gregory actually opens those ones?

The bank decides which money orders to "unblind", but only Gregory can "unblind" them, unless he told the bank how to.

Ideally, the format of the money orders is under the bank's jurisdiction. If the bank doesn't like how the "unblinded" money orders turned out, they can reject Gregory.

And since it's not stated explicitly, I assume by "checking everything's ok" the bank verifies that each has a unique ID they haven't already got, money values are all the same, and the id pairs all work out to a valid address.

Yes. I'm not sure how the bank would react if they discovered a money order at step 3 that have a matching uniqueness string. I mean, what are they going to do, arrest Gregory? It's most likely a coincidence, and Gregory won't get his money order if there's a matching uniqueness string anyways.

On second thought, Gregory and the merchant just have to collude to fake the identity string half. Even if uniqueness matches, the bank won't know who to punish if it's incorrect.

The merchant wouldn't know in any case whether the identity string stuff is truthful or not unless Gregory showed it all to him at step 1. The bank could try to get the authorities to get the merchant to fess up who he was dealing with though, and all that FBI crap.

But you're not going to get extra money that way.

Having never dealt with anything of the like before, I'm going to ask what is probably a stupid question.

"Gregory prepares n amount of money orders for x amount of dollars" - what is n for? Is it just any number?

Yes, n can be any positive number. In Cryptography, the higher the value of n, the more secure the protocol is. Of course, who wants to deal with 10E56 money orders?

The bank decides which money orders to "unblind", but only Gregory can "unblind" them, unless he told the bank how to.

What if Gregory abuses his position of creating the "blinding" method to set it up in such a way that "unblinding" will always return the amount of money he wants it to.

Like you say unblind(p_x, 200) and it turns out it is a money order for $200
Or you say unblind(p_z, 200) and it is also a money order for $200

And then at step 5, when he "unblinds" for the merchant, he just marks it up however much is necessary.

What if Gregory abuses his position of creating the "blinding" method to set it up in such a way that "unblinding" will always return the amount of money he wants it to.

Like you say unblind(p_x, 200) and it turns out it is a money order for $200
Or you say unblind(p_z, 200) and it is also a money order for $200

And then at step 5, when he "unblinds" for the merchant, he just marks it up however much is necessary.

Ahh, but how "blinding" documents work is that the process is done in such a way that it has a mathematical relationship with the bank's digital signature (the bank must know what "blinding" protocol was used), so that in the process of "unblinding" the document, you preserve the signature. For the most basic "blinding" procedure, you just multiply the document by some random number, rendering it unreadable, but make sure the random number has a commutative property with the bank's signature or else it doesn't work. But something important to remember is that, while Gregory and the bank knows how "blinding" is done between them, the bank doesn't know how to "unblind" Gregory's document because the process requires you to know the "blinding factor", or the key.

Now, the bank would be smart enough to sign with a secure signature scheme that's compatible with a "blinding" protocol that is also secure. Given all this, it'd be extremely hard to find another document, let alone a valid money order, that also has a mathematical relationship that's congruent to the original document.

And here I was wondering why Diebold was having a problem with "VoteCountObama++;". Thanks for shedding light on this.

Alright, since it seems this thread is now dead, I'ma post the solution to #3.

 #3

Gregory and the merchant would be incredibly hard-pressed to cheat the bank, even if hacking was allowed. It is very secure against their cheating, collusion or no, in many levels.

Someone eavesdropping on the communications line between Gregory and the merchant can actually get a copy of the money order. Let's call this person Lloyd. Lloyd isn't part of the protocol; he's an outsider. If the merchant hasn't cashed in his money order yet, Lloyd can come to the bank with his copy of the money order and cash it in. The spender of the money order is anonymous, and thus for all the bank knows (unless they check his background), Lloyd is a merchant. Thus, when the merchant comes up with the "real" money order, he'll be identified as a cheater! So will Gregory, if he tries to back up the merchant. And since Lloyd never wrote a money order, he's getting free cash.

Folks, we have a serious problem here!

Even though we had some assumptions and ground rules in here, we still broke these protocols. Now imagine what would happen if anything were allowed (though obviously in reality you don't have unlimited resources; finding a 128-bit key by brute force is virtually undo-able). What if there was noise along the communication lines, corrupting the money orders? What if the bank were not to be trusted? What if the hardware fails? What if someone hacks into the databases the bank houses? Even worse, what if an employee of the bank were attempting to steal the cash? Yet even worse, what if the president of the bank was plotting to haul off with everyone's deposits and flee?

Moral: Don't use these protocols.

Technically speaking, though, that's using the bank to cheat the merchant, not cheating the bank.

Still not something you'd want to happen, to be sure, but you stated in the stem that "the goal of this challenge is to swindle the bank"