CodeGate 2010 Challenge 15 – SHA1 padding attack

March 16, 2010 by RD · 13 Comments 

Summary

This is a web based crypto challenge vulnerable to padding/length extension attack in its sha1 based authentication scheme.

Analysis

Challenge URL: http://ctf1.codegate.org/03c1e338b6445c0f127319f5cb69920a/web1.php

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.

Solution

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
\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xf8|0′
base64: YWFhYXwxgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAD4fDA=
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!!!!!

Source Codes

References

Keywords: sha1, padding, length extension attack, codegate 2010

Share and Enjoy:
  • Digg
  • del.icio.us
  • Facebook
  • Google Bookmarks
  • Add to favorites
  • Reddit
  • Technorati
  • Tumblr
  • Twitter
  • Slashdot
  • Identi.ca

About RD
The man behind the scene

Comments

13 Responses to “CodeGate 2010 Challenge 15 – SHA1 padding attack”
  1. hellman says:

    how do we now that keylen = 25?

    • RD says:

      There was a hint from the organizer about the keylen. We can bruteforce the keylen also.

  2. hellman says:

    no short info about the attack :(

 

Tweetbacks

Check out what others are saying about this post...
  1. Good sha1 length extension exploit – CodeGate 2010 Challenge 15 -http://bit.ly/aKE893 (via @vnsec)

  2. RT @vnsec: CodeGate 2010 Challenge 15 – SHA1 padding attack http://bit.ly/aKE893

  3. RT @vnsec: CodeGate 2010 Challenge 15 – SHA1 padding attack http://bit.ly/aKE893

  4. iamyeh (yeh) says:

    RT @vnsec: CodeGate 2010 Challenge 15 – SHA1 padding attack http://bit.ly/aKE893

  5. RT @phr0nak: @wzzx More about Codegate 2010 write-up’s (Challenge 15) http://tinyurl.com/ygdl77a #codegate2010

  6. RT @vnsec: CodeGate 2010 Challenge 15 – SHA1 padding attack http://bit.ly/aKE893

  7. RT @vnsec: CodeGate 2010 Challenge 15 – SHA1 padding attack http://bit.ly/aKE893

  8. CodeGate 2010 Challenge 15 – SHA1 padding attack http://bit.ly/aKE893

  9. @wzzx More about Codegate 2010 write-up’s (Challenge 15) http://tinyurl.com/ygdl77a #codegate2010