Solving the key disclosure algorithm weaknesses

I'm starting a new thread to summarize what we've been discussing
and bring things together.  The old thread was getting cluttered :)


I think we've sufficiently demonstrated that a "moving DDoS"
attack can severely cripple the functionality of the key
disclosure mechanism, as presently specified.

What we're currently talking about to remedy this problem 
follows below, with some additional thoughts.

1. The key disclosure interval needs to be randomized to avoid
   "Moving DDoS" attacks.  
   Tomasz suggested 10 secs -- 10 minutes (avg. 5 minutes)
   I think I'd say  20 secs --  3 minutes (avg ~1.7 minutes)

   There are issues with random number generation. See below.

2. It looks like we need to be able to query the router for old 
   keys.  Tomasz suggested pointing to an URL, but I'm not sure 
   that's a good idea. All of a sudden, routers suddenly need lots 
   of smarts and configuration work by admins.

   I think I'd do it with a simple Itrace code 0x01 message: 
   "give me keys!", to which the router responds with a code 0x02
   containing as many keys as it has on hand, up to the ICMP packet 
   size limit.

   To guard against "smart" zombies that try to track when key
   disclosure happens, we should probably NOT disclose the most
   recently used key in this list.  

   This means that the router definately needs to keep track of at 
   least the 2 most recent keys.  However, given the (possibly)
   rapid key changes, I'd say that even more is called for.
   Maybe just say "enough to build a full-size reply packet"?

   (OR: Do we feel that item 1 sufficiently guards against this?
    It definately makes "moving DDoS" harder. Hard enough?)



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?)


A note on public key signatures
(and how they affect on-demand key disclosure)
----------------------------------------------

  I don't know if you've given this any thought, but pubkey 
  signatures are rather large. A 1024-bit one will consume
  128 bytes. A 2048-bit one will consume 256 bytes.
  This is half the available ICMP data size.

  I haven't done the math yet to find out eactly how big a 
  "complete" itrace datagram becomes, but if this becomes a 
  problem, we could just scrap the automatic key disclosure and 
  only go with on-demand disclosure. [1]

  Signature sizes also impact on-demand key disclosure, if we 
  decide to go that way.

  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?

  In such a "blob disclosure", we'd be able to fit about a 
  dozen keys, given a more compact representation than is
  currently specified.  Using the disclosure intervals I
  suggested, this is about 20 minutes worth of history.

  Is that enough? Perhaps not. Should one add functionality
  to query for a key used during a specific time?
  
  Ack, this is rapidly becoming very large.
  Is there a better solution that I'm simply missing?


-- 
Mikael Olsson, Clavister AB
Storgatan 12, Box 393, SE-891 28 ÖRNSKÖLDSVIK, Sweden
Phone: +46 (0)660 29 92 00   Mobile: +46 (0)70 26 222 05
Fax: +46 (0)660 122 50       WWW: http://www.clavister.com

[1] But removing automatic key disclosure also has problems, if 
    you for some reason can't route to the router that sent the 
    traceback.  I have a fuzzy recollection about arguments along 
    this line from 2+ years ago...