trusted timestamps
jsnx
on untrusted machines:
http://lambda-the-ultimate.org/node/3208#comment-47098
Such a discussion is probably more appropriate on a
distributed systems list.
Matt M
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?
Matt M
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.
dmbarbour
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...
Jason Dusek
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.
--
Jason Dusek
Jason Dusek
> 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.
--
Jason Dusek
dmbarbour
> Wall clock time or game time? You are confusing them; break
> them down and you will see it works out.
Matt M
"non-dongled" client to interpret the data stream.
Jason Dusek
> Those are all in game time.
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.
--
Jason Dusek
dmbarbour
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:
> Wouldn't this man-in-middle attack work against a dongle, as
> well?
>
> Jason Dusek
Matt M
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]
dmbarbour
>
> 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.
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.
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.
Jason Dusek
> 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.
--
Jason Dusek
dmbarbour
Ah, I suppose so.
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
Jason Dusek
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.
Diagram
--------------------------------------------------------------
Here is how the data flows from piece to piece:
+------------------------> server ----------------------+
| |
| |
stamper <---------------------------------- client <-------+
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.
Low Variance
--------------------------------------------------------------
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.
Is there any vulnerability in the negotiations?
Ooops!
--------------------------------------------------------------
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.
--
Jason Dusek
Jason Dusek
> Part of the frustration to me with this discussion has been
> that the argument showing that no software-only system can
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.
--
Jason Dusek
Jason Dusek
> I'd be interested in seeing the algorithm you think that can
> 'establish local game time' that doesn't involve ever
> estimating lag...
I hope Matt's response clarified how that works in the
insecure case.
--
Jason Dusek
Jason Dusek
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?
--
Jason Dusek
Matt M
No problem, glad to help.
> 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".
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
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.
Good luck!
Jason Dusek
> 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.
--
Jason Dusek
dmbarbour
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.
Jason Dusek
> "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?
--
Jason Dusek
Matt M
> speeding-and-slowing combo attack could be used to cheat a
> little bit -- and now I have to figure out how much.
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.
dmbarbour
> "latest game time" to prevent back sliding?
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.)
dmbarbour
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.
Matt M
of preventing generic client-side cheating here, where theory is not
on your side. In theory, an attacker can always just build a robot
that uses image processing and controls the mouse with a robotic arm
to play with super-human ability.
In practice, robots are expensive and so you can end up trying to
fight the practical / inexpensive attacks, maybe adopting a strategy
of just trying to keep the system free of known cheats, like steam and
punk-buster do. Having certain capabilities like a clock on a trusted
piece of hardware might be of some assistance in your battles against
the cheaters, but you're probably always going to be plugging holes.
Jason Dusek
> In theory, an attacker can always just build a robot
> that uses image processing and controls the mouse with a robotic arm
> to play with super-human ability.
In games with a fixed reaction time of 400ms, would this
matter much? Bots are (entirely?) for games that really are
tests of reaction time and accuracy; such a bot would be
little help in Dawn of War.
What about a super tactics bot? A computer chess program is
probably stronger than most human players; the AIs in most
games are able to pound human players. Are RTS bots an
unexplored (or invisible) kind of cheating?
More generally, I can not argue against your point -- with
successful lag levelling, I close but one door of a large
house.
--
Jason Dusek
dmbarbour
On Feb 11, 10:54 am, Jason Dusek <jason.du...@gmail.com> wrote:
> In games with a fixed reaction time of 400ms, would this
> matter much? Bots are (entirely?) for games that really are
> tests of reaction time and accuracy; such a bot would be
> little help in Dawn of War.
plus another 125 ms for a skilled human. Cutting the 125 ms is a big
deal. This is what would be done by 'freezing' the game long enough to
fire at an opponent. Of course, it could also be done by a bot-script,
especially if you allow 3rd party clients.
> What about a super tactics bot? A computer chess program is
> probably stronger than most human players; the AIs in most
> games are able to pound human players. Are RTS bots an
> unexplored (or invisible) kind of cheating?
It allows humans to spend less time worrying about the small stuff.