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

[Bill Frantz]

At 9:02 AM -0700 4/20/01, Marc Stiegler wrote:
>Ralph Hartley said:
>
>> > Suppose the market price for IBM is $100/share. The attacker (Eve)
>> > buys 100 shares and makes an offer to sell 100 shares, both at that
>price.
>> >
>> > If she can determine that a message from Bob (to the brokerage Alice)
>> > is an order to accept that offer, she delays the message as long as
>> > possible. Lets say 1 day (even minutes might be enough).
>> >
>> > If one day latter IBM is worth LESS than $100, she lets the message be
>> > delivered. Bob buys her shares at $100, and takes the loss that Eve
>> > would have taken.
>> >
>> > If IBM is worth MORE than $100, she deep sixes the message, and
>> > cancels her offer (If you can't cancel offers, buyers could cheat
>> > sellers, anyway she can presumably  block all other attempts to accept
>> > it). Eve can now keep the profit on her shares, and makes the gain
>> > that Bob was entitled to.
>> >
>> > If IBM is worth EXACTLY $100 (rare), she also may discard the message,
>> > and both Bob and Eve avoid paying any transaction fees that Alice may
>> > charge. By picking a volitile stock, this possibility can be avoided,
>> > also for larger transactions, fees are usually negligible anyway.
>> > (This case might be the basis for an attack in which Bob and Eve
>> > cooperate cheat Alice out of transaction fees, but that's another
>matter)
>>
>> Heads Eve wins, tails Bob loses.
>>
>> In either case, Bob may never know he has been robbed, but he has.
>>
>> It looks at first sight like Bob is getting exactly what he asked for,
>> "100 shares of IBM at $100/share", but that is NOT what he is getting.
>> He is getting "100 shares of IBM at $100/share IF IBM is worth less than
>> $100/share", which is very different. No rational person would accept
>> the latter as a substitute for the former.
>>
>> This attack works on any system in which messages can be selectively
>> delayed, and still have effect when eventually delivered, and the value
>> of a message can vary with time. The obvious fixes are to use a protocol
>> that doesn't allow messages to be selectively delayed (hard, but maybe
>> doable), or to have each buy order contain a short deadline. Orders not
>> recieved within a few seconds of when they were sent (as recorded in the
>> message), are rejected.
>>
>> Of course that opens up the posibility of cheating by Alice, she could
>> selectively claim that some messages were recieved late, but I think
>> some trust in (or at least auditability of) the broker is required
>> anyway. Correct me if you aren't assuming this, things are much worse if
>> you aren't.
>
>This is a deliciously more-vicious variant of the original attack. Alas, as
>you noted, the prize has already been claimed :-)
>
>I observe philosophically that this attack has a similar statistical nature
>to the original, in that the MITM must succeed at picking the right message
>to hold, and it must be replayed inside the time window during which the
>server is willing to accept this delayed message. However, since the
>connection does not have to appear broken to the client for this attack to
>work, the server may be willing to accept the message for a longer period of
>time. If I understand the E protocol correctly--an enormous if), this window
>of opportunity will last until the next message is delivered...so perhaps it
>will last no longer than in the original, the MITM may have a longer window
>if he breaks the bidder's connection. Either way, the solution to the
>original attack has no effect on this attack.

For better or worse, he current E comm protocol puts a strict limit on this
delay.  If there is a message outstanding, as there is when Eve (who is
more of an active attacker than the traditional Eve, the passive listener)
grabs and holds the message, then the underling TCP resend, and timeout
logic comes into play.

When there are no messages for a certain period of time, the VatTP ping
logic forces a message to be outstanding.  It also applies its own timeout.
The broker's vat will be sending pings because of the lack of traffic on
the connection.  Even the slow timeouts in the currently released code
should keep Eve's window under 5 to 10 minutes.

In highly volatile markets, the normal communication delays, even without
Eve's interference, may make the "obsolete price information" effect strong
enough to require a completely different approach to the application,
although today's VatTP protocol times out sooner than the traditional "call
your broker" information path.


And in a different message, MarkS wrote:
>It is certainly the case that one needs to be able to implement impatience
>policies other than (or in addition to) the keepalive stream. That is why I
>posted the code that enables one to construct such policies easily. In my
>experiences to date, however, the keepalive stream has been both necessary
>and sufficient most of the time. In other words, my experiences suggest it
>makes a reasonable default policy.

I am particularly interested in requirements for impatience policies which
are longer than the impatience policy imbedded in TCP and VatTP.  If there
exists an important class of applications with these long timeouts, then it
may be worth while build mechanisms to allow these relations to survive the
failure of TCP connections.  Even in the current E, these policies can be
built at the application level with sturdy refs (and a bunch of code for
ordering, retransmission, and all the other stuff the comm system is
supposed to be doing).

Some of the

At 8:45 AM -0700 4/20/01, Karp, Alan wrote:
>Zooko wrote:

>>(Anyway, it is a rare situation in which your counterparty fails to send
>>a message that you are expecting, but keeps sending fresh keepalives.)

>This situation is rare if you are thinking of "connection" failures, but
>it is a common symptom of logic errors in the sending program. Normally
>keepalives are sent by the low-level messaging code, while the message
>you're expecting is coming from the application. If the application gets
>stuck in a loop, or misinterprets the request as something that needs no
>reply, you'll get your keepalives but not your message. Maybe I write
>particularly bad code, but I see this behavior much more frequently than
>an undetected lost connection.

It seems to me that in the case where the application classifies the
request as "no reply needed", that the application would continue to
respond to application level keep alives.  There is probably no solution
short of application level timeouts, and getting those right is hard, as
Zooko notes.  (The development history of TCP shows quite a bit to timeout
tuning too.)



At 8:23 AM -0700 4/20/01, zooko@zooko.com wrote:
>Okay, this has rambled a bit, but my point is that the "steady stream of
>unforgeable keepalives" impatience policy gets used where it probably wasn't
>required and causes occasional spurious failures when mispredicting one
>way, but
>I guess MarcS's thought experiment has convinced me that it rarely causes
>problems when mispredicting the other way.

How much of the problems in Mojo Nation were due to "too short" timeouts?
TCP went to a system of measuring round trip times and including that
measurement (and a measurement of the variance) in the timeout calculations.

Cheers - Bill


-------------------------------------------------------------------------
Bill Frantz       | Microsoft Outlook, the     | Periwinkle -- Consulting
(408)356-8506     | hacker's path to your      | 16345 Englewood Ave.
frantz@netcom.com | hard disk.                 | Los Gatos, CA 95032, USA