Subject: [Tsvwg] draft-ietf-tsvwg-quickstart-00: A new contruction of RR Nonce

From: lguohan <[email-masked]>
Date: Fri, 23 Sep 2005 15:30:01 +0800

This email proposes a new way construct the RR Nonce which provides a 
different kind of protection as the current one. The current one use 
4-bits nonce as a whole. So when the nonce is reported back from the 
receiver, the sender cannot identify a lying receiver as long as the 
reported R' is one step below the original R. The new method overcomes 
this limitation.

     The main idea of the new method is to divide the Request Rates into 
several levels and use one bit in the nonce to protect one level. The 
bits in the nonce are not replaced (or zeroed) once for all when a 
router decreases the Request Rate, but are zeroed bit-by-bit by the 
routers depending how many levels they decrease the Request Rate. In 
this way, if a lying receiver wants to raise the rate to one level 
higher, it has to guess one bits in nonce, 1/2 chance to succeed. If it 
wants to raise the rate to two levels higher, it has to guess two bits 
in nonce. The more it wants to raise, the less probability it can succeed.

     I don't know if this idea has been explored before, as I've never 
attended an IETF meeting. :( So, I apologize if this mail bothers. Below 
is a description of the new method.

     For example, we can divide the 16 Request Rates into five levels as 
follows. For each of the the first levels we assign one bit in the nonce 
to it.

level -- rates -- bit position in the nonce
5 -- 15,14,13 --  1
4 -- 12,11,10,9 -- 2
3 -- 8,7,6,5 -- 3
2 -- 4,3,2,1 -- 4
1 -- 0       -- null

     The four-bit nonce is initialized by the sender to a random value. 
However, when the router reduces the Rate Request field, it does not 
zero all the bits in the nonce. It only zeros those which correspond to 
the levels higher than that of the reduced rate. For example, when the 
rate is reduced from 15 (level 5) to 7 (level 3), the 1st and 2nd bits 
in the nonce are zeroed. When the rate is reduced from 7 to 6, no bit in 
the nonce is zeroed.

     When the Request Rate and the Nonce are reported back from the 
receiver, the bits in nonce which protect the reported rate must match 
exactly with the original sent value. Otherwise, it's an invalid 
response. For example, when the reported rate is 15, 14 or 13, all four 
bits in the Nonce must be matched. When the rate is 8, 7, 6 or 5, only 
the 3rd and 4th bits in the Nonce need to be matched.

    For a lying receiver, when it wants to raise the rate to one level
higher, it needs to guess the original bit in the nonce that protects 
that level. Thus, it has 50-50 chance to succeed. When it wants to raise 
the rate to two levels higher, it has 1/4 chance to succeed. The more it 
wants to raise, the less probability it can succeed. In the following 
figure, if the receiver wants to increase rate 7 to rate 15, it has to 
guess the first two bits (11) in the original nonce, that's 1/4 chance.

sender           router1           router2           receiver
15|1101  --->--- 12|0101   --->---- 7|0001   --->--- 7|0001
    |----------------<-----------------------------------|

    As we only have 4 bits for the nonce, the new method has no 
protection for the rates in the same level. The lying receiver can 
always succeed in reporting the largest rate in the level they receive, 
as long as the largest rate is less or equal than the rate initiated by 
the sender. If we can have more bits (15 bits are enough, using one bit 
to protect one rate), we can solve this problem.

    More discussion about this method can be found at 
http://www.net-glyph.org/~lgh/nonce-usage.pdf . It also documents an 
improved method than this one, a little more complex.

cheers,

Guohan Lu
Dept. of Electronic Engineering
Tsinghua University
P.R.China
[email-masked]

_______________________________________________
tsvwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tsvwg

---

From: Sally Floyd <[email-masked]>
Date: Thu, 29 Sep 2005 11:57:45 -0700

Guohan 

>different kind of protection as the current one. 

Many thanks for the feedback.  We have been thinking about alternatives
for the nonce over the last few weeks with Gorry Fairhurst, who
volunteered at the last IETF to give us feedback, and your email
has encouraged me to rethink my preference for keeping the QS option
at four bytes instead of eight.  I now think that an eight-byte QS
option would be fine, with simplicity of the option valued over
space-efficiency.

So here is the current version of the QS nonce that some of us
are thinking about, based in part on your email, and in part
on earlier suggestions from Gorry.  Your feedback would be
welcome.

One open issue is whether there is any reason to strongly prefer a
four-byte IP option over an eight-byte IP option.  If anyone has
any feedback on this, that would be appreciated as well.

Many thanks!

- Sally
http://www.icir.org/tmrg/
--------------------------------------------------------------------
The modified Lu proposal (also proposed by Gorry):

              0              1              2              3
       +--------------+--------------+--------------+--------------+
       | Option       | Length=4     |  QS TTL      |Resv. |Rate   |
       |              |              |              |      |Request|
       +--------------+--------------+--------------+--------------+
       |  |                       QS Nonce                         |
       |  |                                                        |
       +--------------+--------------+--------------+--------------+

       QS Nonce:
         Bits 0-1:  Reserved
         Bits 2-3:  rate 15 -> rate 14
         Bits 4-5:  rate 14 -> rate 13
         Bits 6-7:  rate 13 -> rate 12
         Bits 8-9:  rate 12 -> rate 11
         Bits 10-11:  rate 11 -> rate 10
         Bits 12-13:  rate 10 -> rate 9
         Bits 14-15:  rate 9 -> rate 8 
         Bits 16-17:  rate 8 -> rate 7
         Bits 18-19:  rate 7 -> rate 6
         Bits 20-21:  rate 6 -> rate 5
         Bits 22-23:  rate 5 -> rate 4
         Bits 24-25:  rate 4 -> rate 3
         Bits 26-27:  rate 3 -> rate 2
         Bits 28-29:  rate 2 -> rate 1
         Bits 30-31:  rate 1 -> rate 0

The sender initializes the 29-bit nonce to a random value.  If the
router reduces the rate request from rate K to rate K-1, then the
router sets the two bits in the nonce for "rate K -> rate K-1" to
a new random value.  (Almost any form of pseudo-randomness would
do - it doesn't need to be fancy.) So if the receiver reduces the
rate request by N steps, the receiver rewrites 2N bits in the nonce.
The receiver reports the nonce back to the sender.

The receiver has a 1/4 chance of cleating about each step change
in the rate request.  If the rate request was reduced by two or
more steps in the network, the receiver has at most a 1/16 chance
of reporting that the original request was approved.

The protection is the same whether one router makes all of the
decrements in the rate request, or whether they are made at
different routers along the path.

The reason for routers to enter new bits in the nonce rather than
setting those bits to zero is to make it harder for the
receiver to know the original rate request.  If the receiver
doesn't know if the rate request was reduced in the network
or not, then it is harder for the receiver to cheat.

There are six bits left as Reserved.  
E.g., for new forms of rate request in the future.

The only issue would be whether there is some reason to strongly
prefer a four-byte IP option over an eight-byte IP option.