Poor time complexity of Cron.parse

[personnumber3377]

Issue description

Hi!

I fuzzed this library with afl and found that the program hangs with a crafted input. I originally reported this privately, but it was later decided to create a public issue. I am going to paste my email text here:

Hi!

I decided to report this to you privately, because this has possible security
implications. I will open a public issue in fugit in a week from now
(19.8.2024), if you do not respond by then. When parsing a long cron job, an
attacker can cause denial of service through uncontrolled resource
consumption. Here is a program which demonstrates the vulnerability

require 'fugit'
c = 10000
pwn = '0 0' + ' 0' * c + ' 1 jan * UTC'
puts 'Parsing...'
Fugit.parse(pwn)
puts 'Done!'

The vulnerability stems from the fact that the Fugit.parse function has poor
time complexity. (I have also attached this program as poc.rb) If an attacker
can supply malicious input to Fugit.parse, then they are able to cause
uncontrolled resource consumption and possible denial of service. I think a
security policy would be good for this project
(https://github.com/floraison/fugit/security) (for a more coordinated
disclosure).

I look forward to hearing from you!

How to reproduce

The simplest piece of code that reproduces the issue, for example:

require 'fugit'
c = 10000
pwn = '0 0' + ' 0' * c + ' 1 jan * UTC'
puts 'Parsing...'
Fugit.parse(pwn)
puts 'Done!'

Error and error backtrace (if any)

Program hangs (no backtrace).

Expected behaviour

The program should execute within a reasonable timeframe.

Context

Linux oof-h8-1440eo 5.15.0-112-generic #122-Ubuntu SMP Thu May 23 07:48:21 UTC
  2024 x86_64 x86_64 x86_64 GNU/Linux
ruby 3.4.0dev (2024-02-09T12:28:26Z master 08b77dd682) [x86_64-linux]
[:env_tz, nil]
(secs:1723619463.6601787,utc~:"2024-08-14 07:11:03.6601786613464355",ltz~:"EEST")
(etz:nil,tnz:"EEST",tziv:"2.0.6",tzidv:nil,rv:"3.4.0",rp:"x86_64-linux",
  win:false,rorv:nil,astz:nil,eov:"1.2.11",eotnz:#<TZInfo::DataTimezone:
  Europe/Helsinki>,eotnfz:"+0300",eotlzn:"Europe/Helsinki",eotnfZ:"EEST",
  debian:"Europe/Helsinki",centos:nil,osx:"Europe/Helsinki")
[:et_orbi, "1.2.11"]
[:fugit, "1.11.0"]
[:now, 2024-08-14 10:11:05.290534123 +0300, :zone, "EEST"]

Additional context

I don't really know how to implement a reasonable security policy (https://github.com/floraison/fugit/security) , because of lack of experience, but I think maybe something similar to what golang has would be good???? (https://go.dev/doc/security/policy)

[jmettraux]

Many thanks!

[jmettraux]

Closing this issue now. I will release 1.11.1 now.

If there is anything I missed, please tell me. Thanks again!

[jmettraux]

https://rubygems.org/gems/fugit/versions/1.11.1