CVE-2021-42836: Uncontrolled Resource Consumption (CWE-400)
value: GJSON before 1.9.3 allows a ReDoS (regular expression denial of service) attack.
CWE description: The product does not properly control the allocation and maintenance of a limited resource, thereby enabling an actor to influence the amount of resources consumed, eventually leading to the exhaustion of available resources.
CVSS v3 base score: 7.5
Published: 2021-10-22T18:15Z
Repository: https://github.com/tidwall/gjson
Language: Go
Files changed: gjson.go, gjson_test.go, go.mod, go.sum
Commit date: 2021-10-08 07:42:49 -0700
Commit message: Limit the complexity of "like" queries that match on a pattern.

This commit adds the uses the MatchLimit function, which it the
same as Match but will limit the complexity of the input pattern.
This is to avoid long running matches, specifically to avoid ReDos
attacks from arbritary inputs.

Diff: diff --git a/gjson.go b/gjson.go
index 973c8af..95d210b 100644
--- a/gjson.go
+++ b/gjson.go
@@ -1087,13 +1087,13 @@ func parseObject(c *parseContext, i int, path string) (int, bool) {
 		if !ok {
 			return i, false
 		}
 		if rp.wild {
 			if kesc {
-				pmatch = match.Match(unescape(key), rp.part)
+				pmatch = matchLimit(unescape(key), rp.part)
 			} else {
-				pmatch = match.Match(key, rp.part)
+				pmatch = matchLimit(key, rp.part)
 			}
 		} else {
 			if kesc {
 				pmatch = rp.part == unescape(key)
 			} else {
@@ -1174,10 +1174,19 @@ func parseObject(c *parseContext, i int, path string) (int, bool) {
 			break
 		}
 	}
 	return i, false
 }
+
+// matchLimit will limit the complexity of the match operation to avoid ReDos
+// attacks from arbritary inputs.
+// See the github.com/tidwall/match.MatchLimit function for more information.
+func matchLimit(str, pattern string) bool {
+	matched, _ := match.MatchLimit(str, pattern, 10000)
+	return matched
+}
+
 func queryMatches(rp *arrayPathResult, value Result) bool {
 	rpv := rp.query.value
 	if len(rpv) > 0 && rpv[0] == '~' {
 		// convert to bool
 		rpv = rpv[1:]
@@ -1211,13 +1220,13 @@ func queryMatches(rp *arrayPathResult, value Result) bool {
 		case ">":
 			return value.Str > rpv
 		case ">=":
 			return value.Str >= rpv
 		case "%":
-			return match.Match(value.Str, rpv)
+			return matchLimit(value.Str, rpv)
 		case "!%":
-			return !match.Match(value.Str, rpv)
+			return !matchLimit(value.Str, rpv)
 		}
 	case Number:
 		rpvn, _ := strconv.ParseFloat(rpv, 64)
 		switch rp.query.op {
 		case "=":
diff --git a/gjson_test.go b/gjson_test.go
index 1ec68a4..fb74d50 100644
--- a/gjson_test.go
+++ b/gjson_test.go
@@ -2022,10 +2022,15 @@ func TestVariousFuzz(t *testing.T) {
 
 	// Issue #196
 	testJSON = `[#.@pretty.@join:{""[]""preserve"3,"][{]]]`
 	Get(testJSON, testJSON)
 
+	// Issue #237
+	testJSON1 := `["*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,,,,,,"]`
+	testJSON2 := `#[%"*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,,,,,,""*,*"]`
+	Get(testJSON1, testJSON2)
+
 }
 
 func TestSubpathsWithMultipaths(t *testing.T) {
 	const json = `
 [
diff --git a/go.mod b/go.mod
index 30ed7f0..6f64083 100644
--- a/go.mod
+++ b/go.mod
@@ -1,8 +1,8 @@
 module github.com/tidwall/gjson
 
 go 1.12
 
 require (
-	github.com/tidwall/match v1.1.0
+	github.com/tidwall/match v1.1.1
 	github.com/tidwall/pretty v1.2.0
 )
diff --git a/go.sum b/go.sum
index f4dcaab..be39c8c 100644
--- a/go.sum
+++ b/go.sum
@@ -1,4 +1,4 @@
-github.com/tidwall/match v1.1.0 h1:VfI2e2aXLvytih7WUVyO9uvRC+RcXlaTrMbHuQWnFmk=
-github.com/tidwall/match v1.1.0/go.mod h1:eRSPERbgtNPcGhD8UCthc6PmLEQXEWd3PRB5JTxsfmM=
+github.com/tidwall/match v1.1.1 h1:+Ho715JplO36QYgwN9PGYNhgZvoUSc9X2c80KVTi+GA=
+github.com/tidwall/match v1.1.1/go.mod h1:eRSPERbgtNPcGhD8UCthc6PmLEQXEWd3PRB5JTxsfmM=
 github.com/tidwall/pretty v1.2.0 h1:RWIZEg2iJ8/g6fDDYzMpobmaoGh5OLl4AXtGUGPcqCs=
 github.com/tidwall/pretty v1.2.0/go.mod h1:ITEVvHYasfjBbM0u2Pg8T2nJnzm8xPwvNhhsoaGGjNU=

Vulnerable code: 				pmatch = match.Match(unescape(key), rp.part)
				pmatch = match.Match(key, rp.part)
			return match.Match(value.Str, rpv)
			return !match.Match(value.Str, rpv)
	github.com/tidwall/match v1.1.0
github.com/tidwall/match v1.1.0 h1:VfI2e2aXLvytih7WUVyO9uvRC+RcXlaTrMbHuQWnFmk=
github.com/tidwall/match v1.1.0/go.mod h1:eRSPERbgtNPcGhD8UCthc6PmLEQXEWd3PRB5JTxsfmM=
Fixed code: 				pmatch = matchLimit(unescape(key), rp.part)
				pmatch = matchLimit(key, rp.part)

// matchLimit will limit the complexity of the match operation to avoid ReDos
// attacks from arbritary inputs.
// See the github.com/tidwall/match.MatchLimit function for more information.
func matchLimit(str, pattern string) bool {
	matched, _ := match.MatchLimit(str, pattern, 10000)
	return matched
}

			return matchLimit(value.Str, rpv)
			return !matchLimit(value.Str, rpv)
	// Issue #237
	testJSON1 := `["*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,,,,,,"]`
	testJSON2 := `#[%"*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,,,,,,""*,*"]`
	Get(testJSON1, testJSON2)

	github.com/tidwall/match v1.1.1
github.com/tidwall/match v1.1.1 h1:+Ho715JplO36QYgwN9PGYNhgZvoUSc9X2c80KVTi+GA=
github.com/tidwall/match v1.1.1/go.mod h1:eRSPERbgtNPcGhD8UCthc6PmLEQXEWd3PRB5JTxsfmM=