Subject: RE: [Tsvwg] draft-ietf-tsvwg-quickstart-00: A new contruction of RRNonce

From: "Amit Jain" <[email-masked]>
Date: Mon, 26 Sep 2005 21:09:34 -0700

Hi lguohan,

Thanks very much for the proposal. 

As you already noticed, one of the main limitations of combining
multiple request rates into one level is not being able to protect
receiver from bumping up the rate to the highest request rate in a
specific level.

Since the rate requests increase exponentially, allowing receiver to lie
at a particular level itself can be a considerable at higher levels.

By having one bit for each rate request offers better protection, but at
a high cost, as it takes away the 4 byte alignment of QS request option.

We've been thinking of some of the nonces schemes on the similar lines
as the one you suggested, but none of them seems sufficient enough
yet...

Thanks again,
-Amit

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf
Of lguohan
Sent: Friday, September 23, 2005 12:30 AM
To: [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: [Tsvwg] draft-ietf-tsvwg-quickstart-00: A new contruction of
RRNonce

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

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