Denial of service attack on certificate capabilities

[Alan Karp]

Today I learned of something called an algorithmic complexity attack.  Say that you have some algorithm that has a fast path for common cases and a slow path for unusual cases.  An adversary can intentionally trigger the slow path to slow down handling of honest traffic.  The canonical example is a regex, where the slowdown can be arbitrarily large.

Certificate capabilities have an attack point in the caveats, limitations on the use of the resource such only during business hours.  If you need more than something that simple, you may want to express your caveats in a policy language that can prove one policy is a subset of another, such as Cedar, .  My question for the formal methods people is if such an attack is feasible.  If so, does it depend on details of the policy engine, or is such an attack possible on any sufficiently complete policy engine?

We can eliminate an attack by someone not in the delegation chain by checking the signature on the root certificate.  That raises a second question.  Can a malicious delegator create a policy that requires a lot of computation from a policy that does not?  (A completely different policy should be easy to detect.)

--------------
Alan Karp

[Alex Potanin]

Ah. The good old pre-AI days:

https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2017.10

😊

Serialisation was by far the easiest to exploit. 😊

Cheers,

Alex.

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/cap-talk/CANpA1Z0-s91H_iWUet9NqBCrDEDd2z1UOWzi0Z0RvDe5FFUjuw%40mail.gmail.com.