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
CVE-2016-20013 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. References: http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2016-20013 http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2016-20013 http://www.cvedetails.com/cve/CVE-2016-20013/ https://twitter.com/solardiz/status/795601240151457793 https://pthree.org/2018/05/23/do-not-use-sha256crypt-sha512crypt-theyre-dangerous/ https://akkadia.org/drepper/SHA-crypt.txt
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
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.