[E-Lang] Security Breach: Nominee for the Stock Exchange Prize

[Marc Stiegler]

This email documents a proposed winner of the 10-gram e-gold prize offered
for a
security breach of the weekend Stock Exchange published at FC'00. A
description of the prize and source code for the system to be breached can
be found at

http://www.skyhunter.com/marcs/securityprize/

Three people made critical contributions to the identification of this
breach. The original idea which led to development of this "delayed
delivery" attack was proposed by Zooko. David Wagner asked several critical
questions that enabled me to work all the way through to a successful
breach.

The attack is as follows:

2 offers are posted that are "identical" inside the context of the exchange:
for example,

Offer 1: 100 shares of IBM for $1000
Offer 2: 100 shares of IBM for $1000

A man in the middle (MITM) is engaged in a guessed-plaintext-attack, and at
some
statistical rate (possibly a very low rate) identifies bids on one of these
two
offers. When a bid transaction comes in, the MITM captures the bid message
and makes the bidder's machine detect a broken connection as swiftly as
possible, while delaying detection of a broken connection on the marketplace
server side as long as possible (by allowing messages including keepalives
to traverse from bidder to server but not vice versa).

The bidder, upon seeing his broken connection, will sometimes immediately
bring up a new client, reconnect, and look to see if his last transaction
(for 100 shares of IBM) completed (by looking at his refreshed new view of
the marketplace and at his own portfolio under his account). Since this
implementation of the Stock Exchange is persistence-less, the bidder always
starts up a new vat, so the old bidder-agent on the exchange is still live.

The bidder, upon seeing that his last transaction has not yet gone through,
and erroneously interpreting this as meaning that it will never go through,
initiates a "duplicate" bid--except that this time he happens to bid on
Offer 2 rather than Offer 1 (they look the same to him).

When the bidder makes this bid immediately, before the old agent times out
because it is no longer receiving a keep-alive from the old bidder client,
and the MITM successfully guesses that the transaction has been initiated,
the MITM finally transmits the old bid to the old agent. Both transactions
are processed, and the bidder winds up purchasing 200 shares of IBM rather
than the 100 shares he had intended.

Solution: One solution would be to disallow multiple agents for a single
account at the same time. The rule to follow to avoid this problem would be
something like, "If you are about to assume that an object will receive no
more messages, revoke its capabilities before making the assumption." When a
new agent is created for an account, the old agent should be terminated in
the same vat game turn (or an earlier turn).

Mark Miller, you are the arbitrator for the Stock Exchange Prize. Does this
proposal win the prize, and how should the prize be allocated?

--marcs