Bug 1196928 - (CVE-2016-20013) VUL-0: CVE-2016-20013: glibc: denial of service through sha256crypt and sha512crypt because of algorithm complexity
VUL-0: CVE-2016-20013: glibc: denial of service through sha256crypt and sha51...
Status: NEW
Classification: Novell Products
Product: SUSE Security Incidents
Classification: Novell Products
Component: Incidents
Other Other
: P3 - Medium : Normal
: ---
Assigned To: Andreas Schwab
Security Team bot
Depends on:
  Show dependency treegraph
Reported: 2022-03-09 14:24 UTC by Thomas Leroy
Modified: 2022-03-10 17:02 UTC (History)
3 users (show)

See Also:
Found By: Security Response Team
Services Priority:
Business Priority:
Blocker: ---
Marketing QA Status: ---
IT Deployment: ---


Note You need to log in before you can comment on or make changes to this bug.
Description Thomas Leroy 2022-03-09 14:24:30 UTC

sha256crypt and sha512crypt through 0.6 allow attackers to cause a denial of
service (CPU consumption) because the algorithm's runtime is proportional to the
square of the length of the password.

Comment 1 Thomas Leroy 2022-03-09 14:34:30 UTC
If I understand the blog article [0] correctly, the researcher found that the implementation of the GLIBC crypt() using sha256 and sha512 is vulnerable to a DoS because of the implementation's algorithm complexity. It seems that those hashing functions have been added in 2007 [1] to replace the insecure MD5.
In conclusion of the article, the author advise to use Argon2 or scryp, or, crypt or PBKDF2, instead of md5, and sha*.
I am trying to find how upstream reacted to the article, but I can't find anything for the moment.

[0] https://pthree.org/2018/05/23/do-not-use-sha256crypt-sha512crypt-theyre-dangerous/
[1] https://www.akkadia.org/drepper/sha-crypt.html
Comment 2 Marcus Meissner 2022-03-10 15:14:03 UTC
Reporter has a valid point, but not sure if the glibc will consider this wontfix.
Comment 3 Michael Matz 2022-03-10 17:02:33 UTC
There is a minor valid point.  As the blog correctly calculates the complexity
of the functions in question is O(pw_length^2 + pw_length*iteration_count).
It further goes on to claim polynomial complexity in pw_length.  For this
to be true the pw_length needs to be _considerably_ larger than the iteration
count, otherwise the above collapses to O(pw_length*iteration_count).
The default iteration count in glibc's implementation is 5000.  So for passwords
up to length (say) 4096, the complexity behaviour is similar to the older
md5crypt: namely linear in password length and iteration count.

I would agree that this isn't ideal, and the fix is to limit the password length
on input.  The algorithm itself can't be changed, it would invalidate all
existing hashes and hence be an incompatible change.  If that's acceptable
a switch to a different method is better anyway, as some other implementations
do the pw_length-depening calculation only once, and then only do constant-time
calculations per round.

Either way: this can't be changed in glibc, it's the algorithm itself that
has the stated properties, not the specific implementation.