關于網絡協定，以及網絡資料加密是後期對項目網絡互動務必做的一步，這裡轉一篇較好的文章。
andrew kirmse
most encryption schemes assume that a trusted sender and a trusted recipient want to communicate over an untrusted channel.it seems absurd to suggest that the sender could deliberately try to fool the recipient, yet this is exactly the problem facing designers of online games.some players cannot be trusted, and worse, they have complete access to the encryption algorithm and all communications via the client executable. under such circumstances we cannot hope to provide completely secure communications, but we can make the attacker’s job more trouble than it’s worth. this article presents some pratical techniques for building and application-level communications protocol for online games.
大多數加密方案都假定可信的發送者和接收者會通過一個不可信的通道通信. 雖然假設發送者會故意嘗試愚弄接收者有點荒謬,但這确實是擺在網絡遊戲設計者面前的問題。有些玩家是不可信的, 更糟的是, 他們能夠通過用戶端執行檔案擷取對加密算法和所有通信的了解。在這樣的情況下，我們不可能提供完全安全的通信，但是我們可以為攻擊者制造麻煩。本文着重介 紹一些實用的技術來為網絡遊戲建立一個應用程式級通訊協定。
definitions
定義
protocol design is most interesting in client/server games, where one of more untrusted clients communicate with a trusted central server.(cleating is certainly also a problem in peer-to-peer games, but because no entity is trusted in such games, the situation is hopeless)the consequences of cheating in a client/server game is high because the server, as the only trusted entity, maintains the game state and verifies all client commands.
協定設計在基于用戶端/伺服器的遊戲中是最有趣的，這種遊戲由若幹不可信的用戶端和一個可信的中央伺服器通信。(cheating在點對點的遊戲中 當然也是個問題，不過因為這樣的遊戲中沒有節點是可信的，是以這種情況是沒希望的)在用戶端/伺服器遊戲中cheat的後果是非常嚴重的，因為伺服器作為 唯一的可信實體，維護遊戲狀态并且驗證所有用戶端指令。當遊戲狀态穩定後, 一次成功的cheat能夠使包括上千個玩家的遊戲變得不穩定。
we consider protocol security features in a client/server system.the client and server communicate by sending packets over a network channel, which might be reliable(typically tcp) or unreliable(udp). although clients can also communicate directly with each other, perhaps for chat or voice, we assume that any data that need to be secured are sent only between a client and the server.
考慮在用戶端/伺服器系統中的協定安全性。用戶端和伺服器在網絡通道中發送封包通信，網絡通道或許可信(tcp),或許不可信(udp).盡管用戶端之間也能夠直接通信，比如文字聊天或者聲音，我們假定任何需要安全保證的資料隻在用戶端和伺服器之間發送。
each packet contains two parts: the header, containing administrative information, and the payload, containing the actual data we want to communicate. the goal of the network protocol is to deliver the sender’s original payload to the recipient.any modifications to the sender’s sequence of payloads should be detected.we deal only with delivery of the payload, leaving the details of packet ordering and reliablility to lower levels in the protocol stack.
每個封包由兩部分組成：header，包含管理資訊；payload，包含我們實際要傳輸的資料。網絡協定的目标是把發送者的原始payload傳 給接收者。對發出的任何payloads序列的篡改都應該能夠被檢測到。我們僅處理payload的傳輸，至于保持封包的有序性和完整性則留給協定棧的底 層細節處理。
packet tampering
封包篡改
most protocol hackers are casual: they change bytes in a packet and see what happens. the first line of defense anainst such attacks is a simple checksum. a checksum is a short number produced by combining every byte of the packet.the sender computes the checksum of the packet and sends both the packet and the checksum to the recipient.the recipient takes the packer and recomputes its checksum;if the computed checksum doesn’t match the checksum from the sender, the packet is corrupt and should be rejected.it’s important to include the entire packet, including the header, in the checksum computation, so that the recipient can detect changes to the header as well as the payload.
大多數協定hackers是偶然的：他們改變封包中的數個bytes,看看會發生什麼。抵禦此類攻擊的第一道防線是簡單的校驗和。一個校驗和是一個 由封包所有的byte組合而成的一個短整數。發送者計算出封包的校驗和并連同封包一起發送給接收者。接收者取得封包并重新計算校驗和；如果和發送者的校驗 和不比對，就認為封包被破壞了并抛棄之。在計算校驗和時需要包含整個封包，包括header,這樣接收者才能檢測出header是否被破壞了。
a perfect checksum computation would produce a different value if any byte of the packet were changed to any other value. a perfect checksum would be too long to be useful, of course, but hash functions have the same design goal and make excellent checksums. particularly useful are one-way hash functions, which scramble their input to the extent that reconstructing any part of the input from the hash value is impossible for practical purposes. the md5 algorithm is well tested, publicly available, and fast enough for use in games. a public domain implementation is available online[plumb93].
一個完美的校驗和算法應該能夠對封包中的任何位元組改動産生不同的值。當然完美的校驗和應該too long to be useful，hash函數有着相同的設計目标進而能夠産生完美的校驗和。單向的hash函數尤其有用，能夠b把輸入變為混亂值，并且逆向重建輸入是不可 能的。md5算法經過廣泛的檢測，被認為是足夠快速的并能夠勝任遊戲使用的算法。其源代碼可在網上找到。[plumb93]
there are two weaknesses in this simple checksum mechanism. first, because the client executable contains the checksum computation code, and attacker can reverse engineer the checksum algorithm, and then compute valid checksums for any message. second, and attacker can capture valid packets and resend them later, and attack known as packet replay.
這種簡單的校驗和機制有兩個缺點。第一，因為用戶端執行檔案包含校驗和算法代碼，攻擊者能夠逆向工程出此算法，進而可以為任何消息計算校驗和。第二，攻擊者能夠截獲封包并在稍後重發，這也被稱為封包重發。
packet replay
封包重發
in a packet replay attack, a malicious user captures a packet from the client (typically using a packet sniffer), and sends it multiple times. a common tactic is to use packet replay to perform commands faster than game allows, even if there are timing checks in the client. for example, a client might use a timer to send a certain command to the server at most once per second, no matter how frequently the player issues the command. using packet replay, a single user might issue the same command hundreds of times per second.
所謂封包重發，指的是那些不懷好意的玩家截獲用戶端發出的封包(通常使用某種封包嗅探器)，然後多次發送此包。
雖然用戶端運用定時器檢測機制能夠阻止正常用戶端過快發送指令，比如定時器沒每秒最多發出一個指令，那麼無論用戶端多麼頻繁地截獲玩家的指令(比如玩家瘋 狂地按鍵)，這些指令仍會每秒隻發送一次。使用封包重發則是非正規管道，他是在用戶端控制之外重新發送封包，是以能夠在一秒内發送相同的指令數百次。
a system designer might try to stop this particular attack by putting a similar once-per-second timer check on the server as well. in the face of widely variable network latency,howerer,this defense is impractical.although it detects most packet replay attacks, varying network delays can make packets bunch together by the time they reach the server, causing legal command sequences to be rejected. we certainly do not want our security scheme to mark law-abiding players as cheaters.
系統設計者也許會在伺服器端使用同樣每秒一次的定時器檢測機制防禦這種攻擊。但是由于有網絡延遲，這樣做顯得不切實際。因為雖然能夠檢測出大多數封 包重發攻擊，但是網絡延遲可能會使多個正常封包同時到達伺服器，這樣就會引起合法指令被抛棄。我們當然不想我們的安全方案把合法玩家視為cheater。
to guard against packet replay, each packet should contain some state information, so that even pakcets with identical payloads have different bit pattern. something as simple as a number that increments with each sent packet would do, although that scheme is too easy for an attacker to figure out. a better answer is to use a state machine to produce successive identifying numbers for successive packets. a fast and resonably complicated method is a liner congruential random number generator of the type typically found in system libraries. such generators operate as follows:
state = ( state + a ) * b
where a and b are carefully chosen integers. (for a discussion of this generators, see [knuth98].)
為了防範封包重發,每個封包應該包含一些狀态資訊,以使資料相同的封包也能有不同的位模式。随着發送封包而增長的數字能夠擔當此任，但此法太容易被 攻擊者破解。更好的方案是使用狀态機為連續封包産生連續id數。一個快速可信複雜的方法是使用線性同餘的随機數産生器(通常在系統庫中)。這種産生器工作 如下：
其中a和b都是精心挑選的數字。(關于此産生器的讨論，見[knuth98])
the sender and recipient each keep a liner congruential random number generator for their connections. when sending a packet, the sender produces a random number and adds it to the packet, simultaneously stepping its random number generator. the receiver checks the random number in the incomming packet against its generator; if the numbers don’t match, the packet has been tampered with. if the numbers do match, the receiver steps its random number generator to prepare for the next packet.
發送者和接收者都為連接配接準備一個随機數發生器。發送一個封包時，發送者産生一個随機數并把它加入封包，同時更新随機數産生器。接收者檢查到來封包中的随機數是否和自己随機數發生器比對；如果不比對，可以認為封包有問題；比對則更新随機數發生器以為下一個封包做準備。
there are two complications with this scheme. the first is how the sender and receiver initially synchronize their state machines.they could each start their state machines with same fixed seed, but then the initial stream of packets would always have the same bit patterns and thus would be vulnerable to analysis.instead, the server can initialize its state machine with randomly generated seed values and send these to the client in its first message.
此法有兩個複雜度。第一是發送者和接收者如何同步狀态機，可以用相同的種子開始狀态機，但是然後初始的封包流将一直有相同的位模式并且會很容易被破解。取而代之的是，伺服器用一個随機的種子值初始化他的狀态機并将此值作為第一個消息發給用戶端。
the second complication is how to keep the state machines synchronized during communication. on a reliable connection, packets are never lost, so synchronization is guaranteed. when packets are dropped or reordered, howerver, the situation becomes more complicated. if a message is lost, the sender’s state machine will have advanced one more step than the receiver’s; subsequent packets will be rejected, even though they are legitimate. a simple solution is to rely on a true sequence number sent with each packet (most games include this number with messages anyway, toprovide a reliable connection over an unreliable trasport).given a sequence number, the receiver can determine how many times to step its state machine to catch up to the current packet. if the application allows out-of-order delivery, the old state of the state machine will have to be stored for use when an out-of-order packet arrivers later.
第二個複雜度是如何保持狀态機在通訊過程中同步。在可信連接配接上，封包絕不會丢失，可以保證同步。然而當封包會丢失或重組，狀況有點複雜。如果一個消 息丢失了，發送者狀态機将比接收者快一步；接着的封包将被拒絕，盡管他們是合法的。一個簡單的解決方案是依賴于随每個封包一起發送的一個真正的序列号(大 多數遊戲包含此号碼在消息中，以在不可信transport上提供可信連結)。給定一個序列号，接收者可以判斷他的狀态機跳了多少步以接獲目前封包。如果 程式允許無序delivery,舊的狀态機将不得不儲存給一個無序封包到達時使用。
the rand function provided with most run-time libraries is inappropriate for use as a state machine because of its low precision (many implementations have only 15 bits) and its obvious choice as a source of random numbers. a fast, high-quality random number implementation is given in [booth97].
大多數運作時庫提供的rand函數作為一個狀态機使用都不夠準确因為它的精度太低(許多實作隻有15位)并且它顯然的選擇作為一個源随機數。一個更高品質的随機數實作在[booth97].
additional techniques
其他的技術
ideally, two packets with identical payloads should show as little correlation in their bit patterns as possible, to frustrate analysis of the payload. an easy way to remove all correlation betwen two sets of data is to combine them with a sequence of random bits, using the exclusive-or(xor) operator.assuming the previous described packet replay defense, the sender and receiver already have synchronized random number generators.thus,the sender can generate a sequence of random number for each packet and xor these into the packet payload; the receiver generates the same sequence of numbers and retrieves the original payload in the same way.
理想狀況下，兩個具有相同payloads的封包應該在bit patterns上盡可能少的暴露相關性，以阻止攻擊者對payload進行分析。消除兩組資料所有相關性的一個簡單方法是用一串随機bits組合他們， 使用異或(xor)操作。想象一下前面所描述的防禦封包重發的方案，發送者和接收者已經同步了他們的随機數發生器。是以，發送者能夠為每個封包産生一串随 機數并把他們異或放進封包payload中；接收者産生同樣的一串随機數然後用同樣的方法擷取原始的payload。
even the fact that two packets have the same length can give an attacker a clue that the packets encode similar data. to further frustrate attacks, each packet can contain a variable amout of random “junk” data, meant only to vary the length of the packet. the length of the junk data is determined by yet another synchronized state machine. the sender checks its state machine to determine how much junk to generate and insert that number of random bytes into an outgoing packet. the receiver simply ignores the junk data.increasing the amount of junk data helps to further hide the payload but costs additional bandwidth. in typical applications in which bandwidth is limited, the average length of junk data should be made small compared to the average payload size.
兩個相同長度的封包的會留給給攻擊者一條線索，那就是封包加密了類似的資料。為了進一步阻擋攻擊者，封包可以包含一堆随機的”垃圾”資料，此資料隻 為改變封包長度。垃圾資料的長度通常由另一個狀态機決定。發送者檢查他的狀态機來決定産生多少垃圾資料并将這些随機的bytes插入到即将發送的封包中。 接收者簡單的忽略這些垃圾資料。增加的垃圾資料進一步隐藏了payload但是耗費更多的帶寬。那些受帶寬限制的程式，垃圾資料的長度應該比 payload的平均長度更短。
reverse engineering
逆向工程
the hardest problem to address, and ultimately the downfall of any scheme to stop protocol tampering, is that the client contains the entire encryption algorithm and thus can always be reverse engineered. some steps you can take to make reverse engineering harder are as follows:
* remove all symbols and debugging information from any code released to the public.
* don’t isolate buffer encryption and decryption in their own function; instead, combine there with some other network code. this is one area in which it can be worthwhile to trade maintainability for security.
* compute “magic numbers” (such as initialization seeds) at run time instead of placing their values directly in the executable.
* include a good encryption scheme in every version of the client, even early betas. if any client version lacks encryption, a user can record a stream of unencrypted packets from one client and then use knowledge of the packet payload to help break the encryption in a later version.
* remember that your goal is to make cheating prohibitively expensive, not impossible.
address最困難的問題以及最終任何阻止篡改協定的方法的缺點就是用戶端包含完全的加密算法并且總能夠被逆向工程。下面的步驟能夠用來使逆向工程更困難：
* 釋出的任何代碼都不該包含任何符号和調試資訊。
* 不要把對緩沖區加密和解密分别放在他們自己的函數中；應該把它們和一些其他的網絡代碼放在一起。用可維護性換取安全性這裡是值得考慮的。
* 應該在運作時計算”魔法數”(不如初始化種子),而不要直接把他們的值放在執行檔案中。
* 在每個版本的用戶端中都包含良好的加密方法，就算是早期的測試。如果某個版本用戶端沒有加密，使用者就能夠記錄未加密的封包流，并用對封包payload的了解來破解下一個加密版本。
* 記住你的目标是讓cheating花大代價，而非杜絕cheating。
implementation
實作
the implementation included with this article includes a c++ class securetransport that uses all the previously described techniques. a securetransport object encapsulates a two-way connection between a sender and a recipient. for each direction, the object maintains four linear congruential random number generators as protocol state machines. these are initialized to static values, with the understanding that the server would send random seeds in its first message to the client. the class uses the state machines as follows:
1. it xors the length field at the start of the header. (this is unnecessary if the underlying protocol provides a packet length as in udp.)
2. a message sequence number is used to prevent packet replay.
3. it determines the length of junk data in each packet.
4. it generates random bits to xor the payload.
a separate random number generator is used to generate the actual junk data. during debugging, it is useful to set the junk data to a known constant value.
本文包含一個c++類securetransport,此類使用了所有之前描述過的技術。一個securetransport對象封裝了發送者和接 受者間的一個雙向連接配接。對于每個方向，對象維護4個線性同餘的随機數發生器作為協定狀态機。這些被初始化為static值， with th 了解that伺服器把随機數種子作為第一個消息發給用戶端。此類像下面這樣使用狀态機：
1. 標頭開始異或成員length。(這是不必要的如果底層協定提供封包長度,比如udp)
2. 一個消息序列号被用來防止封包重發。
3. 在每個封包中決定垃圾資料的長度。
4. 産生随機bits來異或payload(加密).
一個獨立的随機數發生器被用來産生實際的垃圾資料。在調試時，把垃圾資料設為一個常量是很有用的。
references
[booth97] booth,rick,inner loops, addison-wesley developers press, 1997.
[knuth98] kunth,donald,the art of computer programming,volume 2: seminnmcrical algorithms, third edition. addision-wesley longman, inc, 1998
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)