Friday, 28 March 2014

CS Games 2014 - Cryptography Challenge Solutions

Crypto #2


This challenge was  about decrypting value which where encoded using a stream cipher and reused the same key. While the encryption method provided is a custom, it was mostly to simplify the problem and require a smaller subset of value to be able to solve it fast. If you where able to find the solution, the same principale can be used for any stream cipher encryption (ex.: RC4).

The main weakness here is that the same key is reused to encrypt all the value provided. For a stream cipher encryption algorithm what this mean is that all the plaintext will be XORed with the same value (for the first block) and we have a situation called a multiple time pad.

What you can do with a 2-time pad is the following :

plaintext1 XOR key = encrypted1
plaintext2 XOR key = encrypted2

encrypted1 XOR encrypted2 = (plaintext1 XOR key) XOR (plaintext2 XOR key) = plaintext1 XOR plaintext2

Now to find the exact value of the plaintext, what we have to do is the following :

 1 - Compute all combinaison of "caracter XOR caracter" for all caracter of the charset.
 2 - Lookup for all the possible caracter that have a result for "encrypted1[0] XOR encrypted2[0]" in the previous step. This will give a subset of possible caracters for plaintext1[0].
 3 - Repeat step 2 with "encrypted1[0] XOR encryptedX[0]" for all other encrypted value.
 4 - Since the value must be in all the subset you have found, intersect them all and you will have found first caracter of encrypted1.

With this, you should be able to decrypt the first block of the password of "thatguy".

For the other block, what you had to do is instead of using all the other block, you need to use all the block for which the previous block has the same value as the previous block of the plaintext of "thatguy".

Crypto #3


This challenge used AES-ECB. ECB mode is almost always a bad idea for very good reason. One of the reason is that if 2 block have the same plaintext, their output will be the same. If you split the encrypted text in 128 bits long block, you will see that the block where the secret is has the exact same value as an other block. So the result is the value of that other block which is known.

Crypto #4


There is a lot of way to do this challenge and you can find lot's of alternative solution to it on the Internet.

For this solution, I will do it in 2 parts. The first one is finding the length of key and the second one is finding the key.

To find the length of the key, you can use the Hamming distance of the binary representation between each block. Statistically speaking, the Hamming distance will be minimal when you compare 2 blocks that have the same length as the key. The reason this usually works well is that if you have the correct length "enc2 XOR enc1 = plain1 XOR plain2" and if plain1 and plain2 have similar ASCII code, the Hamming distance will be small.

The find the key, you can do it caracter by caracter. What you have to do is simply look for the caracter that when used to decrypt the message will yield caracters that are the closer to an English letter distribution.

And with the key, you can now decrypt the message.

Crypto #5


  - 477cbed015420a1a8923c4ebb68cc646 (MD5)
 - Y3NnYW1lcw== (Base64)
 - %63%73%67%61%6d%65%73 (URL Encode)
 - ca48aca99bf3b952a56305050f86eeb422e90d3e (SHA1)
 - a50aaf14c77970a80565f6d1cc51850d (MD4)
 - *2F5FD2319AE0721EE4A400DAB101B241D8E68D6B (MySQL PASSWORD)
 - pftnzrf (ROT13 or CAESAR CIPHER)

Crypto #7


This challenge was about using the Meet-in-the-middle concept. You first had to notice that for the first block, the plaintext is always known "<message><conten" and you also had access to the encrypted value of it "d09e268648cc0684a2b34c4b87b017da" (first block of the encrypted value). To perform the meet-in-the-middle, store in an hash map the encrypted value of "<message><conten" for all the possibility of the first part of the key. After that decrypt "d09e268648cc0684a2b34c4b87b017da" with all the possibility of the second part of the key and lookup in the previous hash map if the result exists in it. If it exists, it means you have found the 2 parts of the key.

Further read


If you want to see the implementation of the solution or see the challenge again, you can find them here : https://github.com/HoLyVieR/CS-Games-2014-CryptoChallenge.

If you are interested in doing more cryptography, you can take a look at the cryptography course on Coursera or start doing the Matasano crypto challenge.

Monday, 10 February 2014

CTF Olympic - Emdee - An alternate approach

The "Emdee" challenge featured at the Olympic CTF required you to find a secret and salt that was hashed together. To be able to achieve it, you had access to a web API that was hashing for you a message of your choice with the salt and a timestamp. The normal approach to do it was to find the salt by using backspace characters for the message. This would reduce the length of the salt, allowed you to bruteforce smaller part of the salt and progressively get it. However, what I will present is how to get the secret without knowing the salt. One of the reason I find it interesting to talk about it is because it's a good introduction to hash extensions and most people seemed surprise that it was even possible.

First, let's look at how the message are hashed and how MD5 works at a high-level.

MD5


MD5 uses a Merkle-Damgard construction which can be described with the following image that's taken directly from Wikipedia.


In the case of MD5, the IV is static, the function "f" can found in any implementation of MD5 and the padding is constructed by adding 0x80 + (0x00)*(N) + (length of what is hashed). Here N is adjusted so that the length of the last block is exactly 64 bytes long.

The message


The message you have to find is given by MD5(salt+ secret).
The output of the API is given by MD5(salt+ input + timestamp) and the timestamp used is returned to you.

Doing the hash extension


So with that in mind, we now know that the message was evaluated this way:
hashed message = f(PADDING(salt + secret), IV)

And we also know that the output of the API is the following:
output = f(PADDING(salt + input + timestamp), IV)

For the message, it is likely that the length is below 64 bytes, so we will assume it always fit on a single block. For the output however, if the content gets bigger than 64 bytes it will then be hashed the following way:

txt = PADDING(salt + input + timestamp)
output = f(substring(txt, 64, 128), f(substring(txt, 0, 64), IV))

Where it starts to get interesting is that we can make the first 64 bytes equals to PADDING(salt + secret) and this will happen:

txt = PADDING(salt + input + timestamp)
output = f(substring(txt, 64, 128), f(PADDING(SALT + secret), IV))
output = f(timestamp + padding, hashed message)

And this means that we can verify if the secret we have sent to the server is correct if the following holds:

f(timestamp given by the API + padding, hashed message) = output of the API

To have the hash extension work properly, you need to know the length of the salt otherwise the padding will be incorrect. Since it's unknown for the problem we will have to test for both the secret and the length of salt.

Conclusion


When all wrapped up together it gives the following :
https://gist.github.com/HoLyVieR/8920691

This allowed you to find the length of the salt and the secret message. In the case of the challenge the length was 40 and the secret was "cow".




Tuesday, 22 November 2011

Javascript Obfuscation - Properties access

The way we access properties of an object in Javascript is pretty much straight forward with some tiny exceptions. What is interesting for obfuscation though is the way we use it and that's what we will see.

Common object properties access

The most common way to access property of an object is by using the dot notation. It's very simple, but for obfuscation it's not very convenient since we have to explicitly tell what property we want to access. However, there is a second way to access a property that is more convenient for obfuscation and it's with the bracket notation. Example :

var foo = {a : 1};
foo.a // dot notation
foo["a"] // bracket notation


The reason the second one is more convenient for obfuscation is that it takes a string and has we have seen before we can easily use obfuscation technique to produce the string we want. So the previous example can be rewritten has :

var foo = {a : 1};
foo[(!1+"")[1]]


Number properties access 

Numbers do have 2 extra ways to access their properties. Those 2 ways where made up because the dot notation is not adapted for numbers. For that reason we have the "dot-dot" notation and the "space-dot" notation to access properties of a number. They are usually unknown to most of the developer even from experienced Javascript developer. Example :

1..toFixed(2) === "1.00"
(1 .constructor+"")[11] === "m"

Sunday, 20 November 2011

Javascript Obfuscation - The numbers

The numbers

In this section we will explore the different ways we can get number values. The way javascript handles number and operator have a good set of particular behavior that can be surprising and we will see those behavior in detail. Also numbers in javascript only exist in one flavor 64-bit float. Whether we are talking about 1 or 0.5, it's always a 64-bit float.

Number declaration

There are multiple way of declaring a number, most of them are simple, but it can always be interesting to use a variety of them to confuse the reader.

 Notation  Expression 
Decimal100
Octal0144
Hexadecimal0x64

Using parseInt

The "parseInt" function has two particularities that are very interesting for obfuscation. The first one is that if you don't pass a 2nd argument to the function, it won't default to base 10, but it will try to guess the base of your number.

parseInt("10") === 10
parseInt("010") === 8


The second particularity of the function is that you can pass anything as a first argument including object and function. When you pass it something that isn't a string as the first argument, it will internally cast it as a string. Here are few examples that are using this point :

parseInt([].sort, 16) === 15 // function ... with base 16
parseInt([][[]], 31) === 26231474015353 // undefined ... with base 31


Casting anything to number

It's also possible to obtain number with the "+" operator as an unary operator. The result of the operation will be 1 or 0, expect if what you are prefixing is a number or a string. In fact for anything that isn't a string or a number the result of the operation is based on whether what you are trying to cast is truthy of falsy. Here's a good summary of what you can do with it :

Expression Result
+[]0
+""0
+!![]1
+null0
+true1
+false0
+"10"10
+"010"10

Note: I left the last one to point out that the "+" operator will always try to cast a number with base 10.

Sunday, 30 October 2011

Javascript Obfuscation - Getting "window"

In this section, I will show how to get the "window" global variable in an obfuscated way. This section is strongly related to how context works in javascript. If you have no clue what context are in javascript I suggest you take a look at what it is before reading this.

The most common method in javascript obfuscation to access "window" in an obfuscated way is to leak it. In standard mode (non "strict mode"), the global object (window) can leak in some cases. Here's a quick example to show how you can leak it :

function test() {
    return this;
}

a = test();


The variable "a" will now contain "window". This is a simple example, but it's not that great for obfuscation. What is better to use for obfuscation are native method that can leak the "window". One of the native method that is the simplest and most reliable to leak the global object from is "Array.prototype.concat".

Example :

a = [].concat; // We create a reference to Array.prototype.concat
b= a()[0]; // b now contains "window"


If you want to obfuscate this further you can always use the trick learned in the previous blog post and transform it into this :

[_=[][(1+{})[6]+(1+{})[2]+([][0]+"")[1]+(1+{})[6]+(!1+"")[1]+(!0+"")[0]],__=_()[0]]

Now "__" contains the "window" global object.

Javascript Obfuscation - Rewriting block of code

This section is about how to rewrite block of code in an obfuscated way. One of the obvious thing to do to chain your operation is to remove all the extra spacing, but this technique won't get you far since simple tool like jsbeautifier will unobfuscate your code very easily. What will we see is divided in 2 sections, the first one is about block of code that don't use any loop or condition, and the second one is about rewriting code that uses condition.

Simple block of code

Using array declaration

Array declaring are a nice and compact way to rewrite a block of code especially if we are re-using result from previous operation.

Example :

foo = 1;
bar = foo + 2;


Can be rewritten as :

[bar = [foo = 1][0] + 2];


This example is trivial, but there is one interesting thing to note. Most unobfuscator won't be able to rewrite the code in a nice way. If you use this pattern with larger amount of code, it will be a pain for people to understand the code even if they use tools.

Note : You can use the same principle with object declaration, but the syntax is less light and easier to follow.

Comma and parentheses

Using comma in parentheses is an other way to obfuscate code that is very similar to the previous one. It's something that most people don't know about and it's something that can leave most people perplex about the result.

Example :

({a:1},{a:2}).a


What is the result of this expression ? 1, 2 or an error ?

The actual answer is 2, because when you separate multiple operation with a comma in parentheses, the result of the parentheses is the result of the last operation. Once you know it it's simple, but for people that aren't aware of it, it can be puzzling.

Lisp style

This one last trick is interesting just for the look. It's mainly about syntax that use an abusive amount of parentheses.

Example :

(function z(){ return(z); })((foo = (1)))((bar = ((foo) + (2))))((alert((bar))))


If you are using a lot of a specific set of character in general, your code will be harder to read. Parentheses here are just an example, but it could also apply to "{" and "}".

Rewriting conditional block of code

In javascript it's possible to replace block of code that uses if/else statement using the conditional operator (ternary operator), logic operator (&&, ||), parentheses and comma.

Let's first take a look at what we can do with logic operator, parentheses and comma. This technique primarily uses the fact that logic operator are evaluated in a lazy way and that some block of code will only be executed in the cases we want.

Example :

if (test == 2) {
    bob = 1;
    foo = bob + 2;
}


Can be rewritten as :

(test == 2 && (bob = 1, foo = bob + 2))


With this technique we can also transform else statement with a little bit of logic.

Example :

if (test == 2) {
    bob = 1;
    foo = bob + 2;
} else {
    bob = 2;
}


Can be rewritten as :

((test == 2 && (bob = 1, foo = bob + 2, true)) || (bob = 2))


Note : The "true" is added there to make sure the first part of the expression always evaluate to true if test equals 2. This is a good trick to make sure the code will do the exact same thing even if we swap the "bob = 1, foo = bob + 2" part for something else. "true" can also be replaced with "1" or any expression that is truthy.

There is also the conditional operator (often called the ternary operator) that is useful to achieve the same thing. For the 2 previous examples using the conditional operator it would look like this :

(test == 2) ? (bob = 1, foo = bob + 2) : void(0)


and

(test == 2) ? (bob = 1, foo = bob + 2) : (bob = 2)

Friday, 21 October 2011

Javascript Obfuscation - Introduction

Introduction

This is the beginning of a series of blog post about Javascript obfuscation. Obfuscation in Javascript is a very interesting topic, because Javascript has a lot of special syntax and special behavior that can be abuse to produce totally unreadable code. Truly obfuscated code can be so dark that even tools like JS Beautifier won't help you to have a clue about what's going on. The only thing about Javascript obfuscation that is missing is places to find knowledge about it and this is why I am starting a series of blog post about it.

Everything in this series should be working in a modern browser (IE7 is not a modern browser) unless it's noted otherwise. If you see any mistake, you can leave me a comment or send me a message and I will correct it.

Parts