make sort/ro commands validate external keys access patterns (#10106) by ranshid · Pull Request #10340 · redis/redis

ranshid · 2022-02-24T11:38:44Z

TL;DR
Currently the sort and sort_ro can access external keys via GET and BY
in order to make sure the user cannot violate the authorization ACL
rules, the decision is to reject external keys access patterns unless ACL allows SORT full access to all keys.
I.e. for backwards compatibility, SORT with GET/BY keeps working, but if ACL has restrictions to certain keys, these features get permission denied.
see issue: #10106

Implemented solution

We have discussed several potential solutions and decided to only allow the GET and BY arguments when the user has all key permissions with the SORT command. The reasons being that SORT with GET or BY is problematic anyway, for instance it is not supported in cluster mode since it doesn't declare keys, and we're not sure the combination of that feature with ACL key restriction is really required.
HOWEVER If in the fullness of time we will identify a real need for fine grain access support for SORT, we would implement the complete solution which is Option [3]

Proposed solutions

1. (this PR) Only allow use of "GET" and "BY" patterns in sort in case the user has full key access

In the scope of this solution we will only allow sort and sort_ro to use "get" and "by" key patterns ('get #' is NOT considered key access pattern, as it does not access any key)

USER FOO (+sort ~* ~mylist) 
#FOO> sort mylist by w* get v*  - is O.K since ~* provides full key access

USER FOO (+sort %R~* ~mylist) 
#FOO> sort mylist by w* get v*  - is O.K since %R~* provides full key READ access**

USER FOO (+sort %W~* ~mylist)
#FOO> sort mylist by w* get v*  - will fail since $W~* only provides full key WRITE access

USER FOO (+sort ~v* ~mylist)
#FOO> sort mylist by w* get v*  - will fail since ~v* only provides partial key access

2. treat restricted keys as "not-exist"

In the scope of this solution we will have to "keep" the selector which was matched to validate the sort command, and use it to verify every key access during the actual sort execution. in case of an unauthorized access to a key, the command will NOT fail, but treat that key as "not exist" and null be be used for the value.
example:

USER FOO (+sort ~v1[0-9]* ~w[0-9]* ~mylist)
mset w1 1 w2 2 w3 3 w4 4 w5 5 w6 6 w7 7 w8 8 w9 9 w10 10 w11 11
mset v1 1 v2 2 v3 3 v4 4 v5 5 v6 6 v7 7 v8 8 v9 9 v10 10 v11 11
lpush mylist 1 2 3 4 5 6 7 8 9 10 11

calling sort mylist by w* get v* will return:

 1) "10"
 2) "11"
 3) (nil)
 4) (nil)
 5) (nil)
 6) (nil)
 7) (nil)
 8) (nil)
 9) (nil)
10) (nil)
11) (nil)

the downside of this solution is that the first selector matching the sort command might not be the optimal selector.
for example in case in the above scenario:

USER FOO (+sort ~mylist) (+sort ~v1[0-9]* ~w[0-9]* ~mylist)

calling sort mylist by w* get v* will return:

 1) (nil)
 2) (nil)
 3) (nil)
 4) (nil)
 5) (nil)
 6) (nil)
 7) (nil)
 8) (nil)
 9) (nil)
10) (nil)
11) (nil)

which is sub-optimal.

3. Check sort ACL rules after executing it and before commiting output (either via store or to COB)

This is the most complicated of the 3 solutions. it would require making several changes to the sort command itself. and would potentially cause performance degradation since we will have to collect all the get keys instead of just applying them to a temp array and then scan the access keys against the ACL selectors.
This solution can include an optimization to avoid the overheads of collecting the key names, in case the ACL rules grant SORT full key-access, or if the ACL key pattern literal matches the one used in GET/BY (see option 1).
It would also mean that authorization would be O(nlogn) since we will have to complete most of the command execution before we can perform verification
Suggested implementation (still needs some refactoring): https://github.com/ranshid/redis/tree/oss-sort-acl-option3

todo:

Documentation describing the change. (Maybe this should be in the history?)

…redis#10106) Currently the sort and sort_ro can access external keys via 'get' and 'by' in order to make sure the user cannot violate the authorization ACL rules, the decision is to match the external keys access patterns as literals to the acl key patterns. redis#10106

ranshid · 2022-02-24T11:41:55Z

@madolson - as discussed. this is the PR for #10106
Please let me know what you think

madolson

@oranagra Want to get your opinion on this approach over the original one discussed in the PR. This draws inspiration from how we handle channel patterns to have a simpler ACL check that happens before command execution as opposed to during.

src/acl.c

src/db.c

src/acl.c

oranagra · 2022-02-25T09:28:12Z

@madolson I did't read the code, but after reading the top comment, i must say i don't like option [1].
I'd like to suggest some mix between [2] and [3], but first let me share my view on this.

I think of SORT BY as being the same as EVAL which didn't declare all the key-names it accessed.
In which case, the command will start, and run into an error during execution and get aborted.

I.e I think that during the collection of the data when processing the GET and BY argument, we should call some ACL function that will take the command name ("SORT" in this case), and the key name as argument, run though all the selectors and call ACLSelectorCheckKey (on the ones that are allowed to use the command given), if the check fails, it'll return an error which will cause the rest of the sorting operation to abort and fail (replying with a standard ACL permission error reply).

In some sense it's similar to option [3], but i think it's slightly simpler to implement (multiple calls to ACL instead of collecting the key names).
I don't care about the added complexity when it fails ACL (i.e. if they user pays for the full latency price of SORT even when it fails, that's fine with me). what we should try to make optimal is the ACL overhead when SORT succeeds, and specifically, try to avoid high price when ACL is either not used (full permissions are granted).

@yossigo @itamarhaber please share your thoughts too.

ranshid · 2022-02-25T15:23:51Z

@madolson I did't read the code, but after reading the top comment, i must say i don't like option [1]. I'd like to suggest some mix between [2] and [3], but first let me share my view on this.

I think of SORT BY as being the same as EVAL which didn't declare all the key-names it accessed. In which case, the command will start, and run into an error during execution and get aborted.

I.e I think that during the collection of the data when processing the GET and BY argument, we should call some ACL function that will take the command name ("SORT" in this case), and the key name as argument, run though all the selectors and call ACLSelectorCheckKey (on the ones that are allowed to use the command given), if the check fails, it'll return an error which will cause the rest of the sorting operation to abort and fail (replying with a standard ACL permission error reply).

In some sense it's similar to option [3], but i think it's slightly simpler to implement (multiple calls to ACL instead of collecting the key names). I don't care about the added complexity when it fails ACL (i.e. if they user pays for the full latency price of SORT even when it fails, that's fine with me). what we should try to make optimal is the ACL overhead when SORT succeeds, and specifically, try to avoid high price when ACL is either not used (full permissions are granted).

@yossigo @itamarhaber please share your thoughts too.

@oranagra Just to support Option 1 - it is does have the less effect over SORT performance.
Regarding your suggestion - I also considered it and even provided a POC to @madolson to review. the problem is that if we match against all selectors for each key encountered, that will be a breakage of the selectors separation.
In example think of the following ACL:

USER FOO (+sort ~v1* ~mylist) (+sort ~v2* ~mylist)

So while sorting the list some keys will fall in the first selector, while others in the second one.
I think that a selector is a complete independent unit during command authorization check so I think in the solution you described there is a need to stick with the first selector match (which is why I proposed the #2 option). this has the downside of choosing the less optimal selector for the sort

madolson · 2022-02-25T16:16:39Z

I think of SORT BY as being the same as EVAL which didn't declare all the key-names it accessed.
In which case, the command will start, and run into an error during execution and get aborted.

I think this isn't quite correct, because EVAL generates fully formed commands to execute which is what ACLs match against anyways. These commands can be arbitrary, so you have to fully validate everything. Here we can actually declare most of what we're actually interacting with ahead of time.

oranagra · 2022-02-25T16:22:00Z

[edit, this is a response to Ran's last post]

I disagree about the desired outcome of the example you gave. I do think it should pass.
Selectors give the user the flexibility to let some commands access some keys and others access others.
But I don't think that means a certain command must be matched by one selector.

I'll use the analogy of scripts, imagine an ACL rule that grants full permission to EVAL for all keys (since we don't know how it'll use them, if for read or for write), and then restricts SET to use some keys and GET to use others.
I view SORT GET, BY as the same thing.

I'd even argue that if we have one selector allowing SUNION to access some keys, and another selector allowing SUNION to access other keys, when we block an SUNION that attempts to access both, I might consider it a bug.

madolson · 2022-02-25T18:34:59Z

I'd even argue that if we have one selector allowing SUNION to access some keys, and another selector allowing SUNION to access other keys, when we block an SUNION that attempts to access both, I might consider it a bug.

We DO BLOCK this SUNION example though. ACLs work by having independent sets of rules verifying a command and keys as a unit. We have sort of hijacked them in a couple of places like the modules code, which allows viewing of keys in isolation. Saying that SORT is basically eval that does a GET + sort in an EVAL is fairly inconsistent with the rest of Redis.

My opinion is that there are two consistent options:

Once we have fetched all of the keys within SORT, we execute a single check for all the keys (option 3).
We use patterns, as indicated in option 1.

oranagra · 2022-02-25T19:17:03Z

I know we block my SUNION example, but I think from a certain respective it's odd.
I think option 1 is odd and inconsistent with other parts of Redis.
Considering SORT (and this pattern) is not a very important part of Redis, I'm willing to go with option 3 as long as e can avoid overheads when the user Has full access to all keys.

I guess we must wait for other team members opinion..

yossigo · 2022-02-27T14:20:13Z

I agree with @madolson about [3] being consistent.

I don't consider [1] a consistent option though, because we only applied it as a specific workaround for channels, but not for key access. I also think it will be pretty odd and unexpected for users. That said, given that SORT is already a blunder, I can accept [1] as a compromise if we choose to avoid [3].

Also, if we're willing to make a big compromises here, another option is to completely reject BY and GET unless the user has at least %R~* access. This too will be awkward, but I'm not sure it's worse than [1].

ranshid · 2022-02-28T04:50:33Z

Thank you @yossigo and @oranagra for your feedback!
I also agree that option 3 is the most consistent with the current ACL.
the main drawback is that it would be intrusive in the sort code and will require some special code to handle the sort/sort_ro in ACL implementation. Also the ACL dryrun will need special handling in order to support and will probably require running the sort command to a certain point.
This is why I suggested Option 2 which IMO is less intrusive.
In case of Option 2 we can also replace the 'null' in this option to some fixed string indicating access denied like 'UNAUTHORIZED'. I feel Option 2 was the most intuitive solution when I addressed this issue. but I agree it creates a new type of ACL handling.

oranagra · 2022-02-28T06:40:16Z

I'm willing to leave DRYRUN outside the scope (will also not do the right thing for certain scripts).
I think that if we implement [3] in a way that it doesn't have an overhead on the happy path when used when ACL doesn't have any key restrictions, it could be ok.

madolson · 2022-02-28T07:44:37Z

Also, if we're willing to make a big compromises here, another option is to completely reject BY and GET unless the user has at least %R~* access. This too will be awkward, but I'm not sure it's worse than [1].

I am also personally totally okay with this, FWIW. I would like to call attention to the fact that in cluster mode, these options are already disallowed since we didn't know the keys ahead of time.

ranshid · 2022-02-28T10:22:03Z

I think the majority supports the idea of restricting sort to require all keys read access (or allkeys) as was suggested by @yossigo.
If no objections I will make an alteration to this PR to introduce this option

oranagra · 2022-02-28T10:41:34Z

i don't like it that much.
i'd rather have proper (consistent behavior) at the expense of perforce ([3]), with an optimization when all keys are granted.
the only down sides of such an approach compared to what Yossi proposed is the code complexity, but maybe that's not that bad? is it?

i'll be willing let it go. but we didn't hear from other team members, so i think you should wait before implementing.

madolson · 2022-03-01T08:01:17Z

@ranshid The core group met. We decided to go with the option that Yossi proposed, to only allow the GET and BY arguments when the user has all key permissions with the SORT command. The reason being that it is not supported in cluster mode since it doesn't declare keys. If in the fullness of time someone comes and complains about wanting fine grain access support for SORT, we would implement 3.

If you can, please post the temp code you had so that it's available for if we decide to with option 3.

oranagra · 2022-03-01T09:33:12Z

please also mention this plan and reasoning in the top comment.
i.e. edit it so that it first describes what's decided to do and why, then decides the plan for fallback which we may choose to do in the future (these are important for the purpose of release notes and future readers).
and then lists the other alternatives to serve as a context for the discussion below it.

…ions with the SORT command.

ranshid · 2022-03-01T13:45:47Z

@madolson I uploaded a fix according to @yossigo suggestion. please take a look and tell me what you think.
@oranagra - I made some fixes to the PR description - take a look and tell me if that is clear.

Thank you all for the feedback!

oranagra · 2022-03-01T19:30:00Z

haven't reviewed the code yet, but the top comment seems off, the TLDR part mentioned matching patterns as literals (option 1), but the text below it said we'll completely block it when ACL has key restrictions.

I edited the top comment (modifying the TLDR part, the justification, and mentioning an optimization in option 3).
please review my edits.

src/db.c

Co-authored-by: Madelyn Olson <[email protected]>

src/db.c

src/server.h

madolson

minor comments, lgtm otherwise.

Co-authored-by: Madelyn Olson <[email protected]>

madolson

LGTM @redis/core-team Need your approval.

This is a POC implementation for Option 3 as suggested in redis#10340. Please note: 1. Code still might need refactoring 2. Need to add tests as this implementation does not support Dryrun acl 3. Need to run prformance tests on sort in order to verify potential performance degradation

src/commands/sort.json

src/acl.c

tests/unit/acl-v2.tcl

This reverts commit 79e7d8f.

This reverts commit 5025434.

This reverts commit 7fa2f40.

This reverts commit 8cfb89a.

… permissions with the SORT command." This reverts commit c96e930.

This reverts commit ab35a73.

… changes" This reverts commit cfa6a0f.

This reverts commit 3852f8e.

This reverts commit a97e8cd.

…patterns (redis#10106)" This reverts commit 45f651e.

'by'

ranshid · 2022-03-10T15:15:38Z

@oranagra / @madolson can you please take a look at the latest fix?
(will fix the test ASAP)

madolson

lgtm

oranagra

LGTM. (what we decided, which is a bad solution but with low complexity and impact on common use cases, and limitations on uncommon ones)
merging.

madolson reviewed Feb 25, 2022

View reviewed changes

src/acl.c Outdated Show resolved Hide resolved

src/acl.c Outdated Show resolved Hide resolved

src/db.c Outdated Show resolved Hide resolved

src/acl.c Outdated Show resolved Hide resolved

ranshid added 2 commits February 25, 2022 06:00

CR comments fix + avoid allocating new string for hash case

a97e8cd

CR fix - unify handling of sort get keys and patterns

3852f8e

madolson added release-notes indication that this issue needs to be mentioned in the release notes state:major-decision Requires core team consensus state:needs-doc-pr requires a PR to redis-doc repository approval-needed Waiting for core team approval to be merged labels Feb 25, 2022

madolson linked an issue Feb 25, 2022 that may be closed by this pull request

SORT and SORT_RO circumvent ACLs when sorting by external keys #10106

Closed

madolson added 2 commits February 24, 2022 21:41

Added a little more documentation and removed some unecessary changes

cfa6a0f

Two other small documentation fixes

ab35a73

madolson approved these changes Feb 25, 2022

View reviewed changes

only allow the GET and BY arguments when the user has all key permiss…

c96e930

…ions with the SORT command.

madolson reviewed Mar 3, 2022

View reviewed changes

src/db.c Outdated Show resolved Hide resolved

ranshid and others added 2 commits March 3, 2022 08:52

Update tests/unit/acl-v2.tcl

8cfb89a

Co-authored-by: Madelyn Olson <[email protected]>

Update src/db.c

7fa2f40

Co-authored-by: Madelyn Olson <[email protected]>

madolson reviewed Mar 3, 2022

View reviewed changes

src/db.c Outdated Show resolved Hide resolved

madolson reviewed Mar 3, 2022

View reviewed changes

src/server.h Outdated Show resolved Hide resolved

madolson reviewed Mar 3, 2022

View reviewed changes

Apply suggestions from code review

5025434

Co-authored-by: Madelyn Olson <[email protected]>

madolson approved these changes Mar 3, 2022

View reviewed changes

Add history to sort.json

79e7d8f

oranagra reviewed Mar 8, 2022

View reviewed changes

src/commands/sort.json Outdated Show resolved Hide resolved

src/acl.c Outdated Show resolved Hide resolved

src/acl.c Outdated Show resolved Hide resolved

tests/unit/acl-v2.tcl Outdated Show resolved Hide resolved

ranshid and others added 12 commits March 9, 2022 09:53

Revert "Add history to sort.json"

5613aee

This reverts commit 79e7d8f.

Revert "Apply suggestions from code review"

1c99712

This reverts commit 5025434.

Revert "Update src/db.c"

59ae78c

This reverts commit 7fa2f40.

Revert "Update tests/unit/acl-v2.tcl"

fee8b20

This reverts commit 8cfb89a.

Revert "only allow the GET and BY arguments when the user has all key…

cd815f9

… permissions with the SORT command." This reverts commit c96e930.

Revert "Two other small documentation fixes"

acadd5f

This reverts commit ab35a73.

Revert "Added a little more documentation and removed some unecessary…

5ec0de2

… changes" This reverts commit cfa6a0f.

Revert "CR fix - unify handling of sort get keys and patterns"

1dc5feb

This reverts commit 3852f8e.

Revert "CR comments fix + avoid allocating new string for hash case"

0a45d7e

This reverts commit a97e8cd.

Revert "make sort and sort_ro commands validate external keys access …

3bd2a9b

…patterns (redis#10106)" This reverts commit 45f651e.

make sort explicitly check for ACL full access permissions on 'get' and

e118b2a

'by'

Merge branch 'unstable' into oss-sort-acl

8cd50af

ranshid and others added 2 commits March 10, 2022 17:22

fix test acl-v2 after merge

e2c327c

Updated some wording and fixed some typos

395da01

madolson approved these changes Mar 13, 2022

View reviewed changes

oranagra approved these changes Mar 15, 2022

View reviewed changes

oranagra merged commit 1078e30 into redis:unstable Mar 15, 2022

oranagra mentioned this pull request Apr 5, 2022

Release 7.0 rc3 #10532

Merged

Conversation

ranshid commented Feb 24, 2022 • edited by oranagra Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Implemented solution

Proposed solutions

1. (this PR) Only allow use of "GET" and "BY" patterns in sort in case the user has full key access

2. treat restricted keys as "not-exist"

3. Check sort ACL rules after executing it and before commiting output (either via store or to COB)

Uh oh!

ranshid commented Feb 24, 2022

Uh oh!

madolson left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

oranagra commented Feb 25, 2022

Uh oh!

ranshid commented Feb 25, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

madolson commented Feb 25, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

oranagra commented Feb 25, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

madolson commented Feb 25, 2022

Uh oh!

oranagra commented Feb 25, 2022

Uh oh!

yossigo commented Feb 27, 2022

Uh oh!

ranshid commented Feb 28, 2022

Uh oh!

oranagra commented Feb 28, 2022

Uh oh!

madolson commented Feb 28, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ranshid commented Feb 28, 2022

Uh oh!

oranagra commented Feb 28, 2022

Uh oh!

madolson commented Mar 1, 2022

Uh oh!

oranagra commented Mar 1, 2022

Uh oh!

ranshid commented Mar 1, 2022

Uh oh!

oranagra commented Mar 1, 2022

Uh oh!

Uh oh!

Uh oh!

Uh oh!

madolson left a comment

Choose a reason for hiding this comment

Uh oh!

madolson left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

ranshid commented Mar 10, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

madolson left a comment

Choose a reason for hiding this comment

Uh oh!

oranagra left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

ranshid commented Feb 24, 2022 •

edited by oranagra

Loading

ranshid commented Feb 25, 2022 •

edited

Loading

madolson commented Feb 25, 2022 •

edited

Loading

oranagra commented Feb 25, 2022 •

edited

Loading

madolson commented Feb 28, 2022 •

edited

Loading

ranshid commented Mar 10, 2022 •

edited

Loading