Bugzilla – Bug 1196928
VUL-0: CVE-2016-20013: glibc: denial of service through sha256crypt and sha512crypt because of algorithm complexity
Last modified: 2022-03-10 17:02:33 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.
If I understand the blog article  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  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.
Reporter has a valid point, but not sure if the glibc will consider this wontfix.
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.