Subject: [sidr] Replay protection in RPKI provisioning protocol

From: Rob Austein <[email-masked]>
Date: Mon, 26 Apr 2010 23:34:21 -0400

As has been discussed on the mailing list and in several recent WG
meetings, even with TLS (which I'm proposing we drop), we do not
currently have effective replay protection in the RPKI up-down
protocol (expired draft-ietf-sidr-rescerts-provisioning).  The
solutions for this are relatively straightforward, we just have to
update the spec to include them.

The first level of replay protection would be just to check the
timestamp in the CMS message, and enforce a rule that any new message
from a particular peer (protocol, not routing sense of "peer") must
have a newer timestamp than any we've seen until now.   The CMS
profile we're using already includes timestamps, so we get this for
free, and we don't need synchronized clocks, we just need to know that
the timestamp as viewed by the sending party has increased.  This, by
itself, should be enough to detect replay attempts.

The second level of protection would be if we also need to detect
messages being dropped out of the protocol exchange (ie, this one is
about selective message blocking, not replay per se).  A timestamp
won't suffice for this, but a counter will.  So if we're concerned
about this we should add a serial number to the XML header.  Geoff
proposed something like this back in 2007, although his proposed
mechanism was a bit more complicated than I think we'd really need for
this threat.  All we'd really need would be an XML attribute
containing a simple nonnegative integer serial number: the client
would increment this to the next value when sending a new message, the
server would just echo back the client's value.

I'm reasonably certain that we need the first rule (timestamp check),
as there is at least one known attack (replay of an old issuance
request) without it.  I'm not sure we need the serial number, but
Steve Bellovin recommended that we at least think about it.

For both of these, there is the little issue of what an implementation
is meant to do if the rule is violated.  Log something, almost
certainly, but should it reject the message?  Probably, for timestamp
violation, similarly for serial number repeating or going backwards.
Not quite so obvious for a gap in the serial number sequence, seems
like rejecting the message in this case would invite a cheap denial of
service attack, so my inclination would be to raise an alert but allow
the message in this case.

At minimum, I propose that we add the timestamp check rule.  This
requires no change to the message format.

---

From: Geoff Huston <[email-masked]>
Date: Tue, 27 Apr 2010 14:07:30 +1000

Hi Rob,

> Geoff
> this threat.  

I dug out the original exchange from 3 June 2007 and I think you were
proposing some complications to the mechanism at the time....

"1) RobK is correct that the msg_ref checking algorithm as now
  specified is more complicated than it needs to be.  This is at
  least partly my fault, for not having backed us fully out of an
  interim conversation in which we were thinking about just using CMS
  timestamps for replay protection and dropping msg_ref entirely."

and on the 5th June:

"1) On the replay protection thing: Randy and I have been talking to
  Steve Bellovin, and while we haven't quite converged yet it looks
  like the simplest answer is to follow RobK's earlier suggestion:
  just make the msg_ref a monotonically increasing integer, no CMS
  timestamp required, no reset mechanism required, done, full stop.
  The likely implementation would be to generate the msg_ref value
  from a clock on the sender side, eg, nanoseconds since epoch, but
  it really doesn't matter so long as it's monotonically increasing.
  The CMS timestamp doesn't isn't fine enough for this, and combining
  CMS timestamp with an additional value has timing screws, so let's
  just keep this simple and go with the counter."

Steve Bellovin's comments at the time (6th June) were:

"The whole point of something that's purely clock-driven is to avoid the
need for non-volatile client state.  We're talking about secured
objects, rather than secured transmission, which means that things like
nonces are very much harder to use.  (Exception: we probably could use
hash chains, though I haven't worked this out in detail.  Apart from
complexity, see your local IPR lawyer.)

"The point where I currently disagree with Rob and Randy is on the
granularity of the timer.  Whatever granularity is chosen bounds the
maximum signing rate.  Thus, if you use a 1-second clock, you can't
sign more than 1 object/sec.  (Well, you can cheat and "borrow" from
future seconds, up to the actual clock skew, but that does cut your
margin.)  If we go with a nanosecond timer, we're limited to 10^9
objects/sec, ever.  I'm not convinced we can predict the future well
enough to know that that's reasonable, so I've suggested that the spec
support fractional seconds -- we can always extend the number of
significant digits to the right of the radix point without a protocol
change.

"That said, I think that a fixed-granularity timer is fine if someone
will do the quantitative analysis to show what the bound should be.  I
don't know the subject area quite well enough to do that, I suspect."

I haven't looked further to see where it got to but the high order bits
for me from from that exchange appears to be that there is a timer 
granularity issue that appears to affect the maximum message rate.

    Geoff

---

From: Robert Kisteleki <[email-masked]>
Date: Tue, 27 Apr 2010 09:26:09 +0200

> significant digits to the right of the radix point without a protocol

I could live with a 10^9 message/sec limitation (it's not a system global, 
but per client/server relation)... If that's not enough, the <timestamp 
seconds>.<sequence-within-the-same-second> tuple solves all issues, I think.

Robert(K)

---

From: Rob Austein <[email-masked]>
Date: Wed, 28 Apr 2010 00:16:52 -0400

Hi, Geoff

> proposing some complications to the mechanism at the time....

No doubt.  Thanks for the archives, I had forgotten some of the
details, but I still think that we (for some definition of "we") went
a bit overboard at the time.

You're correct that perfect avoidance of all possible replay would
require a counter or clock that increments at least as fast as the
signing rate, whatever that might be.

On the other hand, for the one attack I know of at the moment (replay
of an old issuance request with a compromised key after that key has
been revoked), a clock check with one-second granularity is almost
certainly good enough: for this attack to work in this case, the
revocation request would have to come less than a second after the
initial issuance request, which seems unlikely.

The nanosecond timer isn't quite the same thing as the sequence number
I was talking about yesterday: the sequence number would be intended
to catch dropped messages, a timer wouldn't do that.  Interesting that
Steve Bellovin seems to have been advocating the clock-based approach
back when as a way of avoiding state; he was correct about that, of
course, but he's also the person who suggested the sequence number
this time, so I may need to get him into an argument with himself to
find out who wins that one.

In any case: I still suspect that the trivial timer check I proposed
yesterday would suffice for the one attack we know about today.