Facebook CTF Wiretup

fbctf.ascii

LEVEL ONE:
 
Step 0) We deobfuscated the crypto.js file and ran it thru a beautifier to make the code more readable.
 
Step 1) encrypt(form) function:
Upon submitting the form a call is made to encrypt(form) where the value from the textbox is extracted and sent to a function called numerical_value(str) which returns a numerical representation of the input string.
 
function encrypt(form) {
	var res = numerical_value(form.password.value);
	res = res * (3 + 1 + 3 + 3 + 7);
	res = res >>> 6;
	res = res / 4;
	res = res ^ 4153;
	if (res != 0) { alert('Invalid password! ') }
else { alert('Correct password :)')}
	/* -- snip -- */
}
 
After performing a few operations on numerical representation of the input string a product value of 4153 which is then XOR’d with 4153 to produce 0 which indicated a valid key. Now, we simply reverse the operation starting with 4,153:
 
4,153 * 4 = 16612 (decimal) = 01000110 10000001 11001000 00000000 (binary)
<<  6                                     = 10100000 01110010 00000000 00000000 (binary)
/17   			           = 01000111 01110100 01001011 01000000 (binary)
 
NOTE: Since the 6 rightmost bits are getting truncated, the input string can be any number between (01000111 01110100 01001011 01000000) and (01000111 01110100 01001011 01111111) which represent (62539.2562539) and (62539.49609375) in decimal respectively.
A quick study of numerical_value(str)  shows that this function can only return integers therefore we can safely ignore the decimal part.

The objective is now to produce an input string that causes numerical_value(str) to return 62539.
 
Step 2) Analysis of numerical_value(str) and ascii_one(char):
 
A quick look at ascii_one(char) function shows the loop iterates equal to the passed argument’s ascii value and returns i. effectively returning the ascii value of the passed character in decimal.
 
The function body follows:
 
function ascii_one(char) {
	char = char.charAt(0); var i;
	for (i = 0; i < 256; ++i) {
    	var hex_i = i.toString(16);
    	if (hex_i.length == 1) hex_i = "0" + hex_i;
    	hex_i = "%" + hex_i;
    	hex_i = unescape(hex_i);
    	if (hex_i == char) break
	}
	return i
}
 
As for numerical_value(str), a quick study of this function shows that it produces an integer that can be represented using the following formula:
 
returnValue = 1a + 2b + 3c+... + ny + (n+1)z + …
 
where {a,b,c,...} are ascii values of each character in the input string and {1,2,3,...,n,n+1,...} represent the index of those characters in the input string.
 
Deobfuscated numerical_value(str):
 
function numerical_value(str) {
	var i, a = 0, b;
	for (i = 0; i < str.length; ++i) { b = ascii_one(str.charAt(i)); a += b * (i + 1) }
	return a
}
 
Step 3) Calculating the correct key:
 
Possible approach: At this point we can try to brute force our way to the key; however the chances of hitting the right key with the information we currently have is slim to none ! Since the decimal value of characters in ascii_one(char) is limited to 255 and having a key that consists of all printable characters was desirable for me (which puts us in the range of [32,126]) which means the key length is probably way above 20~25 characters ! Pure brute force is out of the question …
 
We’ll start by writing the formula and trying to reach as close as we can to 62539:
 
	62539 - (a + 2b + 3c + 4d + 5e + 6f + 7g + 8h + 9i + 10j) == 0
 
Note that if we assume the higher bound of 126 (printable ascii char: ‘~’) for all the characters (a thru j) we are still 56,590  short ! Now we keep adding characters assuming maximum printable ascii value until we reach a negative output:
NOTE: At this point all variables are maxed out at 126, unless noted otherwise.
 
62539 - (a + 2b + 3c + 4d + 5e + 6f + 7g + 8h + 9i + 10j + 11k + 12l + 13m + 14n + 15o + 16p + 17q + 18r + 19s + 20t + 21u + 22v + 23w + 24x + 25y +26z + 27aa + 28bb +29cc + 30dd + 31ee + 32ff)
 
Gives us -3,989 ! Now all we have to do is adjust the numbers until we reach our goal ! We first start by setting ff to the minimum of 32 (ascii : space) which results in -981 now if we set  a = b = c = d = e  to 32 (ascii: space) which results in 429.
 
After a minute or two of adjusting the first 5 variables we end up with a 0 using the following values:
 
{65, 60, 32, 32, 100, 126, 126, … , 126, 126, 32}
 
And when we convert these values to ASCII, the resulting string will be one of the possible keys that would pass the test:
 
	“A< d~~~~~~~~~~~~~~~~~~~~~~~~~~ “
 
(note the trailing space)
 
And upon entering the calculated key …
 
 “Congrats! you passed the level! Here is the key: 23f8d1cea8d60c5816700892284809a94bd00fe7347645b96a99559749c7b7b8”
 
Note that many other keys can be calculated that would produce the same result; however for the purposes of this challenge one key is enough.
 
@dNetGuru