Ok, I would like to understand how you think you're preventing my
attack. I take it this statement:
" In the attack you describe, the client's observation time is assumed
to be delayable by a large amount; it also connects the observation
time with the stamp time."
Was supposed to cover that, but I'm not sure I understood it. What
is the client's "observation time"? How do you determine the stamp
time?
Part of the frustration to me with this discussion has been that the
argument showing that no software-only system can securely level lag
the way you want seems so clear, and yet you haven't said anything yet
that I see as rebutting the argument or even demonstrating that you
understand it. I'll give another rewording of it here:
If you have a 50 ms (round-trip) latency to the server, you can always
have a middleman hold the packet stream for 350ms and you will then
appear to have a 400ms latency to the server. It will appear this way
to both the client and the server, as they don't see the middleman.
If the user can cheat and look at what the middle man is holding, then
at any given time he will see data that's 350ms ahead of the data his
client thinks he's looking at.
> Lag leveling requires the server allow requests stamped on the client with a game time trequest to take effect in the game world some constant period of time dnominal later, at teffective. The server does not receive a request, note the client it came from and the time and then guess the lag to know how long to hold it. It knows exactly when to process the request based on a data field in the request.
Let's ignore cheating the system for the moment and assume both
players have and report the correct 'game time' for their actions.
Assume two players, A and B, with network lags 10 ms and 100 ms
respectively, evenly split in the upstream and downstream, and with
zero variance. Each of A and B receives world-updates from the server
S, and each replies with a command to shoot the other exactly 100 ms
after they see the other player. S has a 'd nominal' set at the
minimal 50ms. At time T, players A and B turn the corner around a 20
meter hallway...
S sends the update message that lets each player see the other at time
T.
player A receives the world update message at T+5ms.
player A sends the shoot-to-kill message at T+105 ms (T requested)
player B receives the world update message at T+50 ms
player B sends the shoot-to-kill message at T+150 ms (T requested)
S receives player A's request at T+110 ms, determines 'T effective' to
be T+155ms
S applies A's shoot-to-kill at T+155ms, creates bullet object
traveling 500 m/s
S determines bullet strikes B at T+195ms and kills player B
S receives player B's request at T+200 ms, determines 'T effective' to
be T+200ms
S annuls B's shoot-to-kill because B is dead.
So, it seems that the advantage of actually having lower lag is still
significant in this system. Indeed, without 'd nominal' the difference
would have been 90 ms (T+110ms and T+200ms) instead of 45ms. All you
did was halve the effective lag difference... at the cost of making
the game less responsive for both players. The lag for A is
effectively 55 ms (5 ms downstream, 50 ms upstream), and the lag for B
is effectively 100 ms (50 ms downstream, 50 ms upstream). A and B are
not 'lag leveled' or 'fair'.
I think you need to solve this issue before you even bother attempting
to: (a) figure out how to avoid forged 't request' for a given
message, (b) figure out how clients even KNOW the correct 't request'
to apply, given that they are neither synchronizing the clocks nor
anything else.
> I require that a variance and a bound (dnominal) be specified for the algorithm to work. The variance informs us how early we need to be with the streaming and allows us to kick clients with large swings in round-trip time.
It is unclear how variance is critical to this algorithm. First get a
solution that works with zero network variance.
> Estimating the lag is not a secure operation. There is no purely algorithmic way to do that. Maintaining a lock-step heartbeat and constant lag is possible, however -- given a bound and a variance.
Not all secure operations are algorithmic. But, yes, attempting to
estimate lag without using secured communications between trusted
devices to synchronize clocks is probably a futile effort. So the
solution is to get some devices, encrypt their communications,
establish their trust with certificates, then synchronize their
clocks.
This set of features is already useful to (a) get clients to 'know'
the 'game time', as well as (b) make timestamps unforgeable, so might
as well go the rest of the way and use it to estimate lag.
> A client whose lag exhibits variance that is too great is just forced to re-establish their local game time.
And they'd do well to establish their local game time as being about
'd nominal' less than it should be. I'd be interested in seeing the
algorithm you think that can 'establish local game time' that doesn't
involve ever estimating lag...
Wouldn't this man-in-middle attack work against a dongle, as well?
I am providing some diagrams in response to your earlier mail, along with a lengthier description. I want to be sure everything is out in the daylight to ease review of the algorithm.
> S sends the update message that lets each player see the other at time > T. > player A receives the world update message at T+5ms. > player A sends the shoot-to-kill message at T+105 ms (T requested) > player B receives the world update message at T+50 ms > player B sends the shoot-to-kill message at T+150 ms (T requested)
Wall clock time or game time? You are confusing them; break them down and you will see it works out.
> Wouldn't this man-in-middle attack work against a dongle, as
> well?
> I am providing some diagrams in response to your earlier mail,
> along with a lengthier description. I want to be sure
> everything is out in the daylight to ease review of the
> algorithm.
Their game time is shifted as a result of their differing round trip times (no clock synchronization!). They both receive the update at T in game time.
Why is their game time shifted? Because the _first_ message they got from the server set the relationship between their clock and the game time and we don't try to correct that -- we don't try clock synchonization.
A man in the middle attack can artificially raise the lag associated
with a dongle's communications, but cannot hack the communications
stream (e.g. if it is established with Diffie Hellman). For selective
attacks against synchronization, communications with other trusted
timing devices (in an encrypted stream) would be able to detect them
through the same inconsistent variances in lag you were attempting to
use.
On Feb 10, 9:05 pm, Jason Dusek <jason.du...@gmail.com> wrote:
Remove the security requirement and the algorithm should work fine.
The simplest way to look at it is that clients tag their requests with
the world time of the frame they are looking at -- in this way you can
smooth over variance and everything still works.
On Feb 10, 11:02 pm, dmbarbour <dmbarb...@gmail.com> wrote:
> Their game time is shifted as a result of their differing
> round trip times (no clock synchronization!). They both
> receive the update at T in game time.
They do not receive the update at T in game time. It is merely that
their 'world view' when they receive that message has (precisely upon
processing the update message) finally reached T in game time.
Perhaps by 'game time' you mean 'client view of world'. I mean 'the
time the server understands to be the game time'.
> Why is their game time shifted? Because the _first_ message
> they got from the server set the relationship between their
> clock and the game time and we don't try to correct that -- we
> don't try clock synchonization.
I'm curious how you plan to prevent the potential attacks associated
with (a) delaying the forwarding of that message to the timestamp
module/device, or (b) (against modules only) reducing the machine's
clock a bit after the synch message but before replying to it. I'd
need to explore it more to verify these to be valid attacks, but they
do seem to be what comes to my mind as breaking the system.
> They do not receive the update at T in game time. It is merely that > their 'world view' when they receive that message has (precisely upon > processing the update message) finally reached T in game time.
> Perhaps by 'game time' you mean 'client view of world'. I mean 'the > time the server understands to be the game time'.
By game time, I mean client view of the world. It would be nonsense for me to claim that server time was shifted for each client. In this, you are critiquing a system I have not described.
A and B would both respond at what they believe to be T+100 ms, the
server would receive A's message at what it believes to be T+110 ms
and B's message at what it believes to be T+200 ms.
With 'd nominal' at 50 ms, B would still die a hideous death at T
+190ms (T+150 A shoots, T+190 bullet strikes).
With 'd nominal' at 100 ms, A and B would both shoot at T+200ms and
hit one another.
So, yeah, guess that works out... though one now must keep A from
stamping the killer bullet with an earlier time. If A is allowed to
process messages in an 'artificial client' as you specified earlier,
then A's 'actual' client (the one that fires the bullet at what
appears, to it, to be empty space... just in time for the bullet to
strike B as B walks around the corner) could be running with
additional latency solely for the purpose of assigning earlier 'T-
request' tags to messages.
Got it.
Dave
On Feb 10, 9:26 pm, Matt M <mitchellson.m...@gmail.com> wrote:
> Remove the security requirement and the algorithm should work fine.
> The simplest way to look at it is that clients tag their requests with
> the world time of the frame they are looking at -- in this way you can
> smooth over variance and everything still works.
> On Feb 10, 11:02 pm, dmbarbour <dmbarb...@gmail.com> wrote:
> > [math that I'm too tired to follow carefully right now ... sorry if I missed a subtle point]
First, I should describe the system. We are coming at this kind of backwards -- me saying it works, you saying here is a problem with it, me saying "no, that's not it!". Thank you for your patience up to this point.
The server pushes data for each world update as soon as it is available. This means that nearer clients see things sooner. That is okay. We stream the data with a little lead time, for lag variance and client processing; but not too much. That lead time does provide an opportunity for cheating but not a large one.
The stamper is a dongle or a (magical?) obfuscated binary. It stamps the request with a special key and its internal time. When the stamper first talked to the server, it communicated its internal time to the server. Through magic (discussed below) we know how the stamper's internal time relates to "game time". The time that a request enters the game is entirely determined by its "game time". No matter when it shows up at the server, we know its "time to happen" because of the "game time" it was signed with by the stamper. We trust the stamper a great deal.
The server provides world updates to the client. It is assumed the client is evil, so we keep it on a short leash with streaming. When the client is ready to do something, it must send the request to the stamper to get a valid signature and time for the request.
Can a change in lag alter the time a stamper will stamp something with? No. Its internal clock is not effected by the lag.
Can we alter its internal clock? With an obfuscated binary, definitely. With a dongle, this could still happen; I will discuss the obfuscated stamper from this point on, as we could apply the solution in both cases.
We have a low variance assumption -- a request with a particular "stamper time" should reach the server close to a particular "server time". If it is too late or too early, we do not correct. We throw it out and send a new stamper and renegotiate the relationship between "game time" and "stamper time".
Changing the lag frequently by any large amount will result in loss of requests and frequent renegotiations.
This "negotiating the offset" business would be time synchronization, wouldn't it? So game over for me.
While the adversary can not upset the stamper's ticker once it is set, they can cause it to be set to the wrong "game time". I overlooked this until just about two hours ago. Why? Well, the insecure version doesn't need to sync clocks because it can use the data it's gotten from the server to know the game time.
The resolution to this does require us to secure the data from the server, as you suggested. The updates from the server can actually help the stamper -- now the "gatekeeper" -- know what the "game time" is. I will need to think about this for some time.
> Part of the frustration to me with this discussion has been > that the argument showing that no software-only system can > securely level lag the way you want seems so clear...
Well, that is not clear at all to me. I grant, though, that I have assumed an almost magical level of obfuscation for my binary. I do not address any tampering with its runtime image -- I just assume that is impossible. Do obfuscaters at present work well enough for that? I honestly don't know. I did not make this assumption to be perverse but rather because there is obviously nothing to say if the runtime image can be tampered with.
I failed to demonstrate a reliable time-stamper but I did demonstrate a reliable ticker -- which is to say, a system that allows me to tell how much time has passed on the far end. That system can not tell me anything I actually care about, I now realize, since I can not correlate the time on its end with time on the server's end without time synchronization -- and time synchronization is vulnerable in all the ways you mention.
Thank you both. Our discussion has allowed me to see that it doesn't work to route only the client requests through the stamper; I need to secure and carefully dole out the server responses.
I am not sure if even that can work, given an obfuscated binary with an unstrustworthy clock. The server responses form a vector clock of sorts -- but what prevents that from being sped forward by speeding up the client machine's clock?
> While the adversary can not upset the stamper's ticker once it is set, they can cause it to be set to the wrong "game time".
Ah, right - the attack needs to be to consistently increase the
latency, not just during an attack. I almost made that point earlier.
> I am not sure if even that can work, given an obfuscated binary with an unstrustworthy clock
If the dongle is in charge of both decrypting the contents of the
server updates, and signing the client requests, then it can enforce
that each request is correctly stamped with the last game time the
client has yet had access.
> If the dongle is in charge of both decrypting the contents of > the server updates, and signing the client requests, then it > can enforce that each request is correctly stamped with the > last game time the client has yet had access.
Yeah, as long as it enforces that, setting the clock forward allows the adversary to fast forward through the queue but then they are stuck signing requests with a later time on them. We have a "no backsliding" rule. Maybe some weird speeding-and-slowing combo attack could be used to cheat a little bit -- and now I have to figure out how much.
You can also prevent 'setting the clock forward' with a dongle, by
making that serviceable only in the decryption of a server message.
I.e. upon decrypting message M with time Tm the time of the dongle is
set to the greater of Tcurrent and Tm. This would keep the 'dongle'
clock in lockstep with what the client views to be the server clock.
"No backsliding" can also be enforced by a dongle, but could not be
prevented for an obfuscated binary... though one would be limited by a
backslide by the amount of lag variance you accept.
On Feb 11, 5:10 am, Jason Dusek <jason.du...@gmail.com> wrote:
> Yeah, as long as it enforces that, setting the clock forward
> allows the adversary to fast forward through the queue but
> then they are stuck signing requests with a later time on
> them. We have a "no backsliding" rule. Maybe some weird
> speeding-and-slowing combo attack could be used to cheat a
> little bit -- and now I have to figure out how much.
> "No backsliding" can also be enforced by a dongle, but could not be > prevented for an obfuscated binary... though one would be limited by a > backslide by the amount of lag variance you accept.
If a binary were sufficiently obfuscated, couldn't it store a "latest game time" to prevent back sliding?
> Maybe some weird
> speeding-and-slowing combo attack could be used to cheat a
> little bit -- and now I have to figure out how much.
I guess it depends what attack you're worried about. The dongle
scheme interleaving response unsealing and request sealing makes sure
that client never uses future information in his requests. But if
we're talking about giving a player a reflex advantage, you can still
cheat this system by e.g. having the game briefly auto-pause (within
the window of latency the former attack buys you) when a "financial
crisis" occurs to let the player position his mouse over the "sell"
icon or something.
I don't know whether it would be hard to put a clock or have a semi-
accurate counter in a dongle, but that seems like the easiest
solution. This would also be a role that could be potentially filled
by your obfuscated counter idea, if you could get that to work.
> If a binary were sufficiently obfuscated, couldn't it store a
> "latest game time" to prevent back sliding?
At the very least, removing dependence on the HW clock would remove
one major vector for attack.
I'm going to continue reading Anderson's paper on secure DFAs (http://
eprint.iacr.org/2008/184) as that seems promising (though seems to
forbid Open Source access to the original code.)
Agreed, this would be an attack against the 'lockstep' approach... one
could indeed pause or slow the game (by queueing up the update
messages) intelligently to gain that sort of reflex advantage in a
frame. This can be stochastically audited, but wouldn't be detectable
if the variance is kept small.
Using an unreliable dongle clock or obfuscated thread counter would
allow a strictly positive estimated game-time offset from the last
time the stamper 'knows' to be valid. An obfuscated binary wouldn't
detect the pausing of a hardware clock, and so probably should not use
it. Any clock could use incoming messages to heuristically discover a
multiplier to reduce drift between messages from the server.
Using a dongle with its own clock has the advantage of allowing one
to, at client side, queue up server messages to be processed only when
the time is right. This isn't necessary for Jason's design, but might
be useful in many systems... especially those that do not have a
'central' server acting as a time authority.
> I don't know whether it would be hard to put a clock or have a semi-
> accurate counter in a dongle, but that seems like the easiest
> solution. This would also be a role that could be potentially filled
> by your obfuscated counter idea, if you could get that to work.
