Re: Solving the key disclosure algorithm weaknesses

Mikael Olsson wrote:
> 

> Random number generation for key intervals
> ------------------------------------------
> 
>   Unfortunately, we can't just pick any dumb LCPRNG for generating
>   rekeying intervals.
>   Dumb LCPRNGs work just fine for itrace packet generation, since
>   we never really reveal the LCPRNG state.
> 
>   However, with key disclosure intervals, we reveal exact (partial)
>   state for the world to see; all they need to do is make note of
>   the intervals reported in the key disclosure timestamps.
>   For "rand()%52", one needs seven samples to learn the exact state,
>   as some on-line poker game servers learned a few years ago.
>   I don't how many is needed for e.g. "rand()%(200-20)", but I'd
>   venture a guess that it is about four.
> 
>   If the router doesn't already have a high-quality RNG at hand
>   (not necessarily 'crypto-grade RNG'), one can do:
> 
>   - Keep a separate LCPRNG for key interval generation, preferably
>     with different multiplication and addition constants.
> 
>   - Whenever the itrace generation LCPRNG is used, add about a
>     quarter of its output to the state of the "rekey" LCPRNG.
>     (This adds "hard"-to-predict entropy to the state)
> 
>   - Use the HIGH BITS of the "rekey" LCPRNG output. They reveal
>     less state. E.g. don't do "rand()%(200-20)". Do
>     "rand()/(RAND_MAX*(200-20))" instead.
> 
>   (Igh, yeah, I know, this isn't the type of stuff that one really
>    wants in RFCs, but... well, I just expect people to do the
>    Wrong Thing without it!  Appendix?)
>
The router will already have MD5 or SHA-1 lying around, which it can use in
  feedback mode as a quite good random number generator.   This isn't hard.


> 
>   If we present each HMAC key individually signed, we'll only
>   be able to fit ONE key disclosure in a response if we're
>   using 2048-bit signatures. (And recent advances do indicate
>   that 2048-bit keys will be the minimum length in the not too
>   distant future.)
> 
>   So... what to do?  Assume that the router is capable of
>   combining a bunch of HMAC keys in a single blob and sign
>   that blob?
>
I can't remember the reason for signing individual keys, rather than signing
  a "blob" of them.  Either way, you only need to do one signature every time
  the "blob" changes.
 

-- 
----------------------------------------------------------------------
Marcus Leech                             Mail:   Dept 8M70, MS 012, FITZ
Advisor                                  Phone: (ESN) 393-9145  +1 613 763 9145
Security Architecture and Planning       Fax:   (ESN) 393-9435  +1 613 763 9435
Nortel Networks                          [email protected]
-----------------Expressed opinions are my own, not my employer's------