Darius Bacon has translated this example from Original-E as represented in this document, to modern E. Here is the translation.
A virtual die is a software device which produces a uniform stream of random numbers in the range of 1 through 6. A virtual die can be used in games of chance.
The formula for rolling a virtual die is pretty simple:
(randomGenerator.nextLong() % 6) + 1
Depending on the quality of the source of random numbers, you can get a good, unpredictable stream of numbers.
Suppose we want to have a game in which two players play together using two computers connected via the Internet. One way of doing that is to have one of the computers have a special role. In addition to representing one of the players, it is also the Game Master (or Dealer, or Bank, or House), which is the keeper of privileged knowledge about the state of the game.
Just to make this scenario a little more interesting, imagine that you are one of the players, and that Satan is the other, and you are playing a dice game for your immortal soul. When Satan suggests that his computer (a 666-GHz Pentium XIII) run the Game Master, you become concerned about the fairness of the game. You don't want Satan telling you what you rolled.
Satan suggests that a trusted third party's computer run the Game Master and roll the die, but you are pretty sure that Satan would try to corrupt or intimidate the third party and hack his computer.
You insist, in the interest of fairness, that the Game Master be distributed, that it run in both computers, so that you can roll your die on your machine. Now Satan objects. He doesn't trust your computer to roll your die honestly, not when your immortal soul is at stake.
You both agree that you need a fully distributed Game Master that would have both computers cooperate in every roll of the die in order to keep the results fair. You further agree that the new Game Master will be implemented using E, because E is well suited to the development of secure, distributed applications.
Satan proposes that two eobjects cooperate in the rolling of the die. Eobjects are objects which communicate by message passing. Message passing is a very effective communications and concurrency model for network programming.
The protocol is very simple. The two eobjects both do the following:
Select a random number X.Send X to the other.
Receive the other's X.
Combine the Xs to form the random number that is used to determine the final result.
It appears that neither player can force the result of the roll.
The program has two parts: main, which sets up the eobjects and starts the protocol, and DieRoller, which actually implements the die rolling protocol. main contains the minimum structure necessary to test DieRoller. We will test DieRoller on a single machine now, and later replace main with the Game Master framework that will instantiate the eobjects on different machines.
// Dicing with the Devil: Act I
public class DieRolling {
/*1*/ public static void main(String argv[ ]) {
DieRoller first = new DieRoller();
DieRoller second = new DieRoller();
/*2*/ first <- dieRollStart (second);
second <- dieRollStart (first);
}
}
public eclass DieRoller {
Random randomGenerator = new Random();
/*3*/ long X = randomGenerator.nextLong();
/*4 6*/ emethod dieRollStart (DieRoller otherRoller) {
/*5 7*/ otherRoller <- dieRollFinish (X);
}
/*10 8*/ emethod dieRollFinish (long otherX) {
/*11 9*/ long finalResult = combine(otherX, X);
System.out.println("Roll result = " + finalResult);
}
long combine(long a, long b) {
return (((a ^ b) % 6) + 1); /*1..6*/
}
}
The Walkthrough:
The emethods very closely resemble the protocol, so you are confident that DieRoller accurately implements the protocol. The protocol itself is very simple and effective. Also, the E security model gives you confidence that Satan cannot use E to hack your computer over the network.
Unfortunately, it is not possible to guarantee that Satan is running this code on his computer. Because his computer is under his infernal control, he can hack it. There is no way to prevent someone from hacking his own machine, and there is no way to prove absolutely that a machine has not been hacked. Therefore, it is bad practice to place too much trust in any computer.
If Satan does hack his machine, then he could corrupt the protocol. An evil version of DieRoller might look like this:
evilclass DieRoller {
DieRoller other;
evilmethod dieRollStart (DieRoller otherRoller) {
other = otherRoller;
}
evilmethod dieRollFinish (long otherX) {
other <- dieRollFinish (cheat(X, desiredResult));
}
}
(Note: evilclass and evilmethod are not legal keywords in E or Java. Satan has his own custom programming tools.)
In the evilmethod dieRollStart, Satan doesn't send his X. Instead, he just remembers the other's reference. When dieRollFinish arrives, he knows your random number and you don't know his. He now has enough information to compute an X that will force the result to be what he desires.
If you choose to hack your machine in the same way, then the game will stall because both machines will be waiting for the other to send its X first. Only the player going last can benefit from cheating.
Satan is offended when you ask for design changes in DieRoller to correct the potential insecurity found in Act I, but he very quickly produces a new version with a tighter protocol. The new version of DieRoller makes use of two additional features of E: channels and ewhen.
A channel is a special eobject which stores and forwards messages. Every channel has a distributor associated with it. Forwarding a distributor to an eobject will cause all of the messages sent to the associated channel to be forwarded to that eobject. Channels make it possible to send a message to an eobject that doesn't exist yet. Uninitialized eobjects are channels by default.
ewhen is an E statement which creates a new object (called a closure) which will execute a block of code when a particular eobject has a value.
Satan's new protocol uses a one-way hash which will prevent the changing of X. A one-way hash is a function that is extremely difficult to reverse. The protocol can be divided into two halves: The half that first runs, and the half that second runs. This is first's half:
Select a random number X.Send the one-way function of X to second.
After receiving the second's X, reveal X.
The X s are combined to produce the final result.
This is second's half:
Select a random number X.After receiving the hash of first's X, reveal X.
The Xs are combined to produce the final result.
Recompute the one-way hash of first's X to verify that first did not change its X when it learned second's X.
Shuffling the halves together, we can see the complete protocol:
The two eobjects, first and second, each select a random number X.first reveals a one-way hash of its X.
Then second reveals its X.
Then first reveals its X.
The Xs are combined to produce the finalResult.
Second recomputes the one-way hash of first's X to verify that first did not change its X after it learned second's X. That would be cheating.
Satan assures you that if he attempts to cheat, you will be able to detect it. Once again, you are invited to observe that the emethods closely resemble the protocol.
// Dicing with the Devil: Act II
public class DieRolling {
/*1*/ public static void main(String argv[ ]) {
DieRoller first = new DieRoller();
DieRoller second = new DieRoller();
/*2*/ first <- dieRollFirst (second);
}
}
public eclass DieRoller {
Random randomGenerator = new Random();
/*3*/ emethod dieRollFirst (DieRoller otherRoller) {
/*4*/ long X = randomGenerator.nextLong();
/*5*/ ELong concealedX, hisX;
otherRoller <- dieRollSecond (oneWayHash(X),
concealedX, &hisX);
/*6 11*/ ewhen hisX (long otherX) {
/*12*/ &concealedX <- forward (new ELong(X));
/*13*/ long finalResult = combine(X, otherX);
System.out.println("Roll result = " + finalResult);
}
}
/*7*/ emethod dieRollSecond (long otherHash,
ELong firstX, EDistributor myX) {
/*8*/ long X = randomGenerator.nextLong();
/*9*/ myX <- forward (new ELong(X));
/*10 14*/ ewhen firstX (long otherX) {
/*15*/ long finalResult = combine(otherX, X);
System.out.println("Roll result = " + finalResult);
/*16*/ if (oneWayHash(otherX) != otherHash) {
System.out.println("There was cheating.");
}
}
}
long oneWayHash(long a) {
long h = a >>> 32;
return ((a*a) ^ ((a ^ 0xDEADBEAD) *
(h ^ 0xFADBEBAD)) ^ (h*h) ^ a);
}
long combine(long a, long b) {
return (((a ^ b) % 6) + 1); /*1..6*/
}
}
The Walkthrough:
One nice feature of this version is that second can't cheat. Unfortunately, first can still cheat in a number of ways.
First knows the result before second does, and if first is unhappy about the result it could cause a network failure to prevent the conclusion of the protocol. This attack doesn't help him to win, but it does allow him to avoid losing.
evilmethod dieRollFirst (DieRoller otherRoller) {
long X = randomGenerator.nextLong();
ELong concealedX, hisX;
otherRoller <- dieRollSecond (oneWayHash(X),
concealedX, &hisX);
ewhen hisX (long otherX) {
if (combine(X, otherX) == desiredResult) {
&concealedX <- forward (new ELong(X));
} else {
simulate_network_failure();
}
}
}
This sort of attack is difficult to avoid without the use of a trusted intermediary. You might want to deal with this contractually: If there is a network failure during the final die roll of the game, then you win. This way you won't be risking your immortal soul on a bug in a socket manager.
There may also be a more serious attack on the one-way hash. There may be two or more inputs that will produce the same output. These are called collisions. If Satan has a set of candidate Xs that all produce the same hash, then he can freely select among them, defeating the cheating-detection feature. In preparation, Satan may have done an exhaustive search for collisions. He can then use this knowledge to change his choice of X without detection:
&concealedX <- forward (new ELong(cheat
(desiredResult, otherX)));
This is similar to having Satan write his X on a piece of paper. When he sees your guess, he reveals the paper. If he would have lost on 666, he turns it over and says it's 999.
"The third time's the charm," says Satan as he whips out his latest protocol, intended to fix the weakness discovered in Act II.
Both sides use this protocol:
Select two random numbers, X and R. R will be used to prevent a precomputed attack on the one-way function.Reveal R.
After learning the other's R, reveal the one-way hash of X mixed with R. The R mixture defeats the hash collision attack from Act II.
After learning the other's hash, reveal X.
After learning the other's X, combine the Xs to produce the finalResult.
Verify that there was no cheating.
This version uses nested ewhen statements. Using ewhen with channels allows for an interactive protocol without having to have many emethods. It also prevents attacks which alter the proper sequencing of messages.
// Dicing with the Devil: Act III
public class DieRolling {
/*1*/ public static void main(String argv[ ]) {
DieRoller first = new DieRoller();
DieRoller second = new DieRoller();
ELong firstHash, firstX, firstR;
ELong secondHash, secondX, secondR;
/*2*/ first <- doDieRoll (&firstHash, &firstX, &firstR,
secondHash, secondX, secondR);
second <- doDieRoll (&secondHash, &secondX, &secondR,
firstHash, firstX, firstR);
}
}
public eclass DieRoller {
Random randomGenerator = new Random();
/*3 7*/ emethod doDieRoll (EDistributor myHash,
EDistributor myX, EDistributor myR,
ELong hisHash, ELong hisX, ELong hisR) {
/*4 8*/ long X = randomGenerator.nextLong();
long R = randomGenerator.nextLong();
/*5 9*/ myR <- forward (new ELong(R));
/*6 10*/ ewhen hisR (long otherR) {
/*13 11*/ myHash <- forward (new
ELong(oneWayHash(otherR ^ X)));
/*14 12*/ ewhen hisHash (long otherHash) {
/*15 17*/ myX <- forward(new ELong(X));
/*16 18*/ ewhen hisX (long otherX) {
/*21 19*/ long finalResult = combine(X, otherX);
System.out.println("Roll result = " +
finalResult);
/*22 20*/ if (oneWayHash(R ^ otherX) != otherHash) {
System.out.println("There was cheating.");
}
}
}
}
}
long oneWayHash(long a) {
long h = a >>> 32;
return ((a*a) ^ ((a ^ 0xDEADBEAD) *
(h ^ 0xFADBEBAD)) ^ (h*h) ^ a);
}
long combine(long a, long b) {
return (((a ^ b) % 6) + 1);
}
}
The Walkthrough:
This version is much stronger than Act II, but it is also more expensive. The program passes many more messages, so it is measurably, if not noticeably, slower. Is it safe? It is certainly safer. Is it safe enough? Would you bet your immortal soul on it?
One possible attack is on the Java Random function. The protocol requires that each side draw two random numbers, X and R, immediately revealing R. If knowledge of weakness in the design and implementation of Java Random makes it possible to predict X from R, then it may still be insecure.
You might be wondering, "How far must we go in order to prevent an extremely unlikely attack?" These attacks are difficult and time consuming. In fact, the attack suggested in Act I has never occurred, but we believe that it is possible. The situations to watch for are the ones in which it might be worth the trouble. As the Internet grows in size and importance, there will be more and more situations which are worth the trouble.
One benefit of E is that it can make the attacks more difficult and time consuming, but E cannot by itself repel all possible attacks. Nothing can. E makes it possible to write secure, distributed applications, for some practical definition of the word "secure." Use of E does not automatically assure that programs will be secure.
For some purposes, the solution in Act I may be completely adequate, but with this caution:
It is not unusual for the purpose or use or scope of software to change over its life. Rarely are the security properties of software systems reexamined in the context of new or evolving missions. This leads to insecure systems.
If you design systems as though your immortal soul depended on them, then you will tend to build more reliable systems.