next up previous
Next: DoS Attack on the Up: Security Discussion and Robustness Previous: Security Discussion and Robustness

DoS Attack on the Sender

 

A DoS attack on the sender is not possible if TESLA is used with indirect time synchronization, because the sender does not keep per-receiver state or perform per-receiver operations. In the case of direct time synchronization, a DoS attack is possible, since the sender is required to digitally sign each nonce included in a time synchronization request. An attacker can perform a DoS by flooding the sender with requests.

This response packet needs to be authenticated with a digital signature scheme, such as RSA [28], or DSA [32]. Since public-key signature algorithms are computationally expensive, the signing of the response packet can become a performance bottleneck for the sender. A simple trick can alleviate this situation. The sender can aggregate multiple requests, compute and sign a Merkle hash tree that is generated from all the requester's nonces [20]. Figure 5 shows how such a hash tree is constructed. If Nh is the root of the hash tree, Nh would be included in the signed part of the response packet instead of the receiver's nonce Nr. To verify the digital signature of the response packet, each receiver would reconstruct the hash tree. Since it does not know the other receiver's nonces that are part of the hash tree, the sender would include the nodes of the tree necessary to reconstruct the root node. For the example in figure 5, the packet returned to receiver A would include Nb and Hcd. Receiver A can reconstruct the root node Had from these values and its own nonce Na as follows: Had = H(H(Na,Nb),Hcd). Note that the number of nodes returned in the response packet is logarithmic in the number of receivers whose request arrived in the same time interval. Assuming a 50 ms interval time (the sender would need to compute at most 20 signatures per second) and assuming that 1,000,000 receivers wanted to synchronize their time in that interval, the return packet would only need to contain 20 hash nodes or 200 bytes, assuming an 80 bit hash function. Any cryptographically secure hash function can be used for H(x,y), for example MD5 [27], SHA-1 [17], or RIPEMD-160.

HadHad HabHab HcdHcd NaNa NbNb NcNc NdNd

  figure537
Figure 5: Hash tree over receiver nonces. Node Hab = H(Na, Nb). Had = H(Hab,Hcd).


next up previous
Next: DoS Attack on the Up: Security Discussion and Robustness Previous: Security Discussion and Robustness

Adrian Perrig
Sun Nov 5 19:29:44 PST 2000