Re: [sidr] sidrKeys and algorithms for Updates - feasibility analysis? (was Re: RPKI and private keys)

[Wes Hardaker <[e-mail]>]

Brian Dickson <[e-mail]> writes:

Hi Brian,

I believe I understand your system as functionally creating an
BGPSEC_Path_Signatures attribute with a algorithm/signature set that is
based off of adding random numbers to the signature field(s) instead of
adding cryptographically generated hashes.  IE, we end up with something
like this being received by a RP:

  |----------------------|
  | AS Number 1          |
  | Random Bytes from #1 |
  |----------------------|
  | AS Number 2          |
  | Random Bytes from #2 |
  |----------------------|
  | ...                  |

This obviously greatly simplifies the diagram from the -protocol
document section 3, but is sufficient for the discussion.  The point
being is that the BGPSEC_Path_Signatures is a list of ASes that the
update has gone through.  Roughly.

Now, I'm all for updating the signature field to the fastest
cryptography that meets the goals.  We just need to agree on what the
goals are, and how the resulting system is subject to attacks against
those goals.

So, lets consider a few things first:

1) A random number generation using a PRF is an interesting concept.
   And you're right, that if you assume a OOB cache that can verify the
   results is available, it'll offload much of the computation from the
   RP router.  It's a worthy goal.  [However, I'd argue that you could
   do that without changing the crypto as well; though it may still be a
   goal to lower the crypto cost of the OOB cache machine anyway]

2) A random number generator can only be compared against an existing
   system in turns of speed if it provides a similar amount of security,
   or the reduced security is an acceptable trade off for the speed
   gain.  So, let me start with the concept of generating a nonce from a
   32 bit generating PRF (or, as you stated, N instances of a 32 bit
   PRF).  

   The problem with a 32 bit PRF and repeating it N times is that you
   don't get 32*N bits of entropy.  You only get 32 bits.  Specifically,
   if I'm given M random number Rs that were concatenated into a nonce,
   what do I have to do in order to predict the next 32*N bit field?
   Functionally, I need to figure out the original seed so that I can
   calculate the next 32*N bit field.  But to calculate all the N
   fields, I really only need to sweep through the entire 32 bits
   looking for each of the N values, and work backward to the seed.

   Using a single 2.4GHz i7 core, I calculate it would take me 1.4 hours
   to search the entire 32bit space of random numbers looking backward
   for a seed.  And much of that time is devoted just to initializing
   the random number generator, as producing 4 random numbers from a
   single seed (say you want to drop the first bunch of random numbers
   so it's harder for me to work backward) doesn't really help much, as
   the time needed only jumps to 1.5 hours to calculate 4 times the
   number of random numbers per seed.  Then, you have to think about
   dictionary attacks.  Storing an entire 32 bit set of random numbers
   generated from any 32-bit PRF requires only 16GB of storage, which is
   probably about the same as your ram limit without even going into
   disk-storage.

   The other problem with a simple PRF implementation (such as random()
   on most systems) is that it's not designed to be unreversable.  IE,
   it's not designed to be cryptographically random and a random
   generator should be picked with care if you're using it for "proof"
   points of view.

   The end result of this, is that if you want to compare the speed of
   using random numbers against the speed of a real crypto function, you
   probably want to use a random number generator that won't let me
   predict the next one so easily.  You need a random number generator
   that can output a much larger set of bits (IE, returns an number much
   bigger than a 32-bit int and requires a random seed (if any) much
   bigger than a 32-bit int).

But lets say you come up with a random number generator that is
strong enough to do what you want, and we agree the OOB problem can
be solved in a way that everyone can be happy with (which I know is
one of your statements: worry about it later; I'm not sure we can
meet that goal either, but I'm even willing to worry about it later
for the time being).

IE, let us say that an architecture is found that allows an OOB or
the router itself to authoritatively say "AS A really did use random
number R a while ago".  What does the resulting algorithm really let you
say?

3) It lets you say that "AS A really did use random number R a while
   ago".  IE, if you see this:

   |------|
   | AS A |
   | R    |
   |------|
   | AS B |
   | Q    |
   |------|
   | ...  |

   Then you can say "yep, R was generated by A".

4) But.... does it really tell you that R was generated by A for that
   particular update path?  It doesn't, right?  All you know is that at
   some point in the past that AS A really did issue R.  And possibly,
   assuming you keep a running memory cache to avoid replay, that it
   hasn't been seen yet so you should trust it.  But, it may have been
   monitored/stolen from a different path instead, etc.  EG, consider
   two trust caches that neither of which has seen AS R yet.  They could
   both vouch for completely different paths advertised.

5) And in fact, there is no assurance that the random number generated
   matches anything.  Thus any of the following paths would be treated
   the same:

   |------|   |------|   |------|   |------|   |------|
   | AS A |   | AS A |   | AS C |   | AS A |   | AS B |
   | R    |   | R    |   | N    |   | R    |   | Q    |
   |------|   |------|   |------|   |------|   |------|
   | AS B |   | AS C |   | AS A |              
   | Q    |   | Q    |   | R    |              
   |------|   |------|   |------|              
   | ...  |   | ...  |   | ...  |              


   IE, any update with AS A/num=R in it will verify, but it won't matter
   if the order is added-to, reversed, deleted, dropped, etc.

   In the end, it doesn't really provide any of the protection services
   that the original cryptographically-chained algorithm provides: proof
   that the path wasn't modified.

So, as I said, I'm all for a system that is equally secure, or provides
the minimal security properties that we need at a much faster speed.
But I fail to see how your system provides any security.  At least as
you've defined it to date.  And even a 50,000x potential improvement you
claimed doesn't seem to make me happier if we're getting nothing out of
it.

Even if we had a more secure random number generator in use (which would
be likely slower than the existing one you were testing but still
faster than a ECDSA signing system), I fail to see how the designed
system with any random number generator will help out because we're
loosing all the path binding properties that BGPSEC is trying to secure
in the first place.

-- 
Wes Hardaker
SPARTA, Inc.