CodeGate 2010 Challenge 15 – SHA1 padding attack
This is a web based crypto challenge vulnerable to padding/length extension attack in its sha1 based authentication scheme.
This page will ask for submitting a username for the first time. Once a username is submited ( ‘aaaa’ for example), the script will set a cookie as the following:
web1_auth = YWFhYXwx|8f5c14cc7c1cd461f35b190af57927d1c377997e
The first part YWFhYXwx is the base64 encoded string of ‘aaaa|1′ (username|role). The second part 8f5c14cc7c1cd461f35b190af57927d1c377997e is the sha1(unknown_secretkey + username + role).
In the next visit, the web1.php script will check for the cookie and return the following message
“Welcome back, aaaa! You are not the administrator.”
We can guest that 1 is the role value for normal user and 0 for administrator.
If we try to modify to first part of the web1_auth cookie to something like base64_encode(’aaaa|0′), the script will return an error message saying that the data has been tampered due to the wrong signature.
As we know that popular hash functions including sha1 are vulnerable to length extension (or padding) attacks. This can be used to break naive authentication schemes based on hash functions.
I will not write the detail on how to do sha1 length extension attack, you can read papers in the References section below for more information. Basically, with padding attack, we can append arbitrary data to the cookie and generate a valid signature for it without knowing the secret key. In this challenge, we want to have ‘|0′ (administrator role) at the end of the first part of the cookie.
$ python sha-padding.py
usage: sha-padding.py <keylen> <original_message> <original_signature> <text_to_append>
$ python sha-padding.py 25 ‘aaaa|1′ 8f5c14cc7c1cd461f35b190af57927d1c377997e ‘|0′
new msg: ‘aaaa|1\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
new sig: 70f8bf57aa6d7faaa70ef17e763ef2578cb8d839
And here is what we got with the web1_auth cookie using YWFhYXwxgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAD4fDA= and signature 70f8bf57aa6d7faaa70ef17e763ef2578cb8d839
Welcome back, aaaa! Congratulations! You did it! Here is your flag: CryptoNinjaCertified!!!!!
- http://force.vnsecurity.net/download/rd/sha.py (this one taken from pypy lib)
- Flickr’s API Signature Forgery Vulnerability
- G. Tsudik, “Message authentication with one-way hash functions,” Proceedings of Info-com 92.
Keywords: sha1, padding, length extension attack, codegate 2010