Back to files

coinflip - (C) 2002 HardCore Software

Distributed under the GNU GPL, see the file LICENSE for details.

Uses code from RSA Data Security's Message Digest 5 implementation. Uses code from HardCore Software's Dougnet TCP/IP wrapping library.

What is coinflip?

Coinflip is a client/server based program that can generate random bits for 2 people over the internet. The 2 people don't have to trust each other in order to convince each other that the bit is truly a random bit.

It's called coinflip, of course, because flipping a coin in the real world is the equivalent of generating a random bit on a computer. (It's either heads or tails. It's either a 1 or a 0.)

Why does the problem of flipping coins over the net require cryptography? (1) The net (for better or for worse) provides few trusted arbiters. (2) The net provides no means for simultaneous data exchange.

For example, say you and another sysadmin on your network are talking over the phone, trying to decide who's turn it is to install the latest 50 megs of patches on your IIS server farm. You eventually agree that the only fair way is to flip a coin:

"Ok, I'm flipping the coin now. Look at that. Heads. I guess it's your turn again..."

"No, no. How do I know you actually flipped a heads?"

"Ok, we'll both flip. If we both flip a heads, or we both flip a tails, I win. If we flip opposite sides, you win. Go."

"I flipped a heads."

"Oh, me too. Look at that."

As you can see, neither of these approaches will work if you don't trust the other party. We solve this problem by having the person who flips the coin commit themselves to a particular side without the other party know the result. Read on for details.

How does it work?

Coinflip uses a slightly modified version of the "Coin Flipping Using One-Way Functions" protocol outlined in Bruce Schneier's Applied Cryptography 2nd edition. This is from Schneier's book (page 90):

"
(1) Alice chooses a random number, x. She computes y = f(x), where f(x) is the one way function.

(2) Alice sends y to Bob.

(3) Bob guesses whether x is even or odd and sends his guess to Alice.

(4) If Bob's guess is correct, the result of the coin flip is heads. If Bob's guess is incorrect, the result of the coin flip is tails. Alice announces the result of the coin flip and sends x to Bob.

(5) Bob confirms that y = f(x).
"

While this protocol can theoretically be sound, it would have to rely on Alice using a large enough range of numbers. Consider this attack:

Bob knows that Alice is going to choose a number less than z, so he composes an array of f(1), f(2), ... f(z-1). When Alice sends Bob f(x), he simply checks each element in his array until he finds an element matching f(x). Bob determines what position his match is in to recover x, after which he makes his guess even or odd depending on x (and whether he wants to win or lose).

Naturally, this attack can be defeated by making sure that Alice chooses a number large enough to make any precalculated array attack by Bob infeasable.

Let's consider how much memory would be needed for array attacks on various size unsigned integers that Alice might use (we'll assume Alice is using a 128 bit hash function such as MD5):

16 bit:
2^16 = 65536 different values
65536 * 128 = 8388608 bits of storage required

So, about 1 megabyte of storage is required. An attack against 16 bit integers is not only feasible, but has been feasible for many years, even to hobbiests.

32 bit:
2^32 = 4294967296
4294967296 * 128 = 549755813888

About 70 megs is required. 32 bits is the standard int size on most x86 based platforms, by the way. 70 megs of RAM is substandard on even the most mediocre PCs today.

Clearly, more hash values have to be possible for this protocol to be secure against cheating. We could just increase the range of values even further, but a better solution exists:

We could concatenate random data and the number together before hashing, and we could get away with only using a single bit for the random number that Alice chooses.

There are, again, a few problems with this scheme that we shall now address:

If Bob is the one allowed to choose this random data, the algorithm falls to the same array attack as mentioned above. The array may contain as little as 2 elements if, as suggested above, the scheme used only 1 bit for the random number.

If Alice is the one allowed to choose this random data, she could precompute f(x) = f(z) = y, where x is random data concatenated with an even number and z is random data concatenated with an odd number. If Alice succeeds in calculating this, she can send y to Bob, and depending on what Bob guesses, send either x or z.

This attack would work everytime Alice acted as the server in a coinflip procedure, providing Bob never realized that Alice was sending him the same y value every time. Or she could us it to trick multiple Bobs.

While it is supposed to be computationally infeasible to compute collisions in one-way hash functions, recent papers suggest that if you have enough money and time, collisions can be precalculated. P. van Oorschot and M. Wiener in their paper, "Parallel collision search with application to hash functions and discreet logarithms", estimate that for $10 million (in 1994 US dollars), a collision could be found for MD5 in 24 days on average. (Thank's for the info, defrost).

The solution is actually quite simple: Have both parties choose part of the random data, and use whatever size random number you like. Since Bob is expecting to see x contain his random data, Alice's collision attack is nullified, and since Alice gets to put in her own data, she can make Bob's array attack infeasible.

Ok, I can dig it. What's the exact protocol?

(1) Alice listens on a port (7213 by default) until Bob connects.

(2) Bob connects to this port and he sends the string "coinflip " concatenated with a string of diplayable ASCII characters.

(3) Alice concatenates a space onto Bob's string (not including the "coinflip "), and then concatenates her own string of random data to the string. Next, she concatenates a space, and then she concatenates AN ASCII REPRESENTATION of a random number between 1 and n, where n is an EVEN number. The string now looks like this: "<Bob's data> <Alice's data> <the number>". Alice then saves this string as x.

(4) Alice hashes this string, y = f(x), using RSA's MD5 one-way hash algorithm. She makes sure that the hash is in ASCII hexadecimal representation (with the digits a-f lowercase).

(5) Alice sends y to Bob.

(6) Bob sends Alice either the string "even" or "odd" (he picks this randomly), and remembers his choice.

• Note: Here is an interesting position in the protocol. Alice knows the result

  of the coin flip, but Bob won't know until (7). See the note "Flipping Coins into a Well" below.

(7) Alice sends Bob x.

(8) Bob confirms that the first part of x matches the random data he sent in step 2.

(9) Bob confirms that f(x) = y.

(10) Bob sends either the string "ok" or the string "not ok" depending on whether he was able to confirm the data in steps (8) and (9).

Note: All communications between Alice and bob can have newline and linefeed characters at the end of each statement WITHOUT them affecting the data. (They should be stripped of such chars before being processed.)

Note: The random data chosen by the client and server should not exceed 20 characters, and if it does, the client or the server should truncate it to 20 characters.

Note: When Alice generates a random number in step (3), it's important that she choose a number between 1 and n, where n is an EVEN number (in our implementation n=10) so that there is an equal number of even and odd possibilities, so that either choice (even or odd) is equally likely to be right (or wrong).

Note: In step (10), Alice should NOT take any automatic action based on Bob's ok/not ok response. This is meant for auditing purposes only.

Note: This implementation of the protocol, when acting as a client, starts a "stopwatch" immediatley after it sends it's random data, and stops timing when it recieves the full text string. If the amount of time exceeds SUSPICION_TIME_THRESHOLD (default 5 seconds), it will cry rat. Normally, this would be completely unimaginable, but say you were running this as an automated service and didn't check it for months (years?) at a time. If it means enough to somebody powerful enough, that might give them enough time to find a collision. Because of the intangibility of this attack, it will only include a warning in the output and won't abort the protocol.

Note: Flipping Coins into a Well:
Bruce Schneier explained this better than I could, so here's a quote from page 92 of his Applied Cryptography, 2nd edition:

"
It is interesting to note that in all these protocols, Alice and Bob don't learn the result of the coin flip at the same time. Each protocol has a point where one of the parties [ ... ] knows the result of the coin flip but cannot change it. That party can, however, delay disclosing the result to the other party. This is known as flipping coins into a well. Imagine a well. Alice is next to the well and Bob is far away. Bob throws the coin and it lands in the well. Alice can now look into the well and see the result, but she cannot reach down to change it. Bob cannot see the result until Alice lets him come close enough to look.
"

Cool. How do I use the coinflip program?

If you want to act as a server, run: coinflip -l [port] If you want to act as a client, run: coinflip <server's IP/DNS> [port]

The port is always optional, and will default to 7213 if not specified.

You and the other party should agree on who is going to be the server, then agree on what port to use (the default should usually be fine), then the server should run coinflip, then the server should give the client it's IP/DNS, then the client should run the coinflip program.

Note: After one coinflip, the server and client will exit.

Can I redistribute this?

This software is protected by the GNU GPL. For philosophical details see www.gnu.org. Here's the short answer:

Yes, by all means. There are a few restrictions, however: You must always make the source code available (along with any changes you make), and you may not relicense this software. See the file LICENSE for details.

Who wrote this?

Doug Hoyte (aka Fractal)

How can I get in touch with him?

E-Mail: doug@bearcountry.cjb.net
IRC: As Fractal on irc.h410g3n.com, EFNet, irc.hcsw.org, and Open Projects

Network.
Web: www.hcsw.org