Issue 53, Computational complexity of delegation

[Erik Rissanen <mirty@sics.se>]

All,

I talked with Olav Bandmann (who made the proof of NP-completeness). He
had not come up with any workaround to the problem with
IndirectDelegates making delegation NP-complete.

I am leaning towards that we should drop indirect delegates. Here are my
motivations:

- They make delegation NP-complete. (Or actually, it is the
IndirectDelegatesCondition, or its generalization, which makes XACML 3.0
NP-comlete.) This opens up XACML 3.0 for very easy denial of service
attacks.

- Allowing several Attributes elements in the request with the same
attribute category makes matching of the target more complex. (What
happens if there are multiple “action” categories for instance?)
Depending on how we do it, everything may become NP-complete. In any
case, having multiple Attributes elements collides with a generalization
of the Multiple Resources profile.

- Although there are use cases for indirect delegates, such as to make
sure administration stays within an approved group of people, indirect
delegation cannot be enforced in the strict sense. “Delegation” is
always possible offline: someone can simply give instructions to
authorized issuers, who then issue the policies.

Has anyone else thought about this?

Regards,
Erik