csKa blog

20080603

Move to WordPress

I was writing blog about interesting security stuff before in blogspot.

However, it seems that WordPress is a more interesting place to writing on

(Mostly because its beautiful themes)

I just start writing there, enjoy and feel free to visit my new blog.

New blog:
http://cskane.wordpress.com/

20080523

These days I am working on Ajax, learning how to do simple HTTP request through Ajax.
Accidentally, I found an interesting property that js has: document.write(). Some of you may already know how to use it to do evil thing, but it is really new to me and I would like to share it with you.

document.write() is a function in js going to write data into the browsing page. The interesting point of this function is that it will overwrite the original HTML file. Let see an example using it with HTTP request.
Let say we have a evil.html containing a piece of code as follow.

<html>
<script type="text/javascript">
function fetch() {
var xmlHttp;
  try {
    xmlHttp = new XMLHttpRequest();
} catch (e) {
  try {
    xmlHttp = new ActiveXObject("Msxml2.XMLHTTP");
  } catch (e) {
    try {
      xmlHttp = new ActiveXObject("Microsoft.XMLHTTP");
    } catch (e) {
      alert("You Win!");
      return false;
    }
  }
}
xmlHttp.onreadystatechange = function() {
  if (xmlHttp.readyState == 4) {
    document.write(xmlHttp.responseText);
    document.close();
  }
}
xmlHttp.open("GET", "index.html", true);
xmlHttp.send(null);
return true;
}
</script>
<body onload="javascript:fetch()">

</body>
</html>

The index.html file that evil.html want to get is a normal page. Once a user going to browse evil.html, the script will replace evil.html as index.html. The code above is no harm at all. It tried to request the index.html under the same directory. However, it can easily be used to do malicious thing. Consider we add some code before getting the index.html, eg.

userInfoRequest = new XMLHttpRequest();
userInfoRequest.onreadystatechange = function() {
if (xmlHttp.readyState == 4) {
  var content = userInfoRequest.responseText;
  /* send the content to somewhere hacker want to store it */
}
}userInfoRequest.open("GET", "user_info.html", true);
userInfoRequest.send(null);

You can imagine what's going on with this piece of code. I am going to find a vulnerable site that allow me to demo this malicious code. I will back on this topic soon.

Should you have any comment or idea or whatever interesting stuff, please feel free to share with me.

20080101

Minimum Cut

Minimum cut problem usually refer to s-t minimum cut, which can be solved by using maximum flow algorithm (eg. Ford-Fulkerson, Edmonds-Karp, relabel-to-front, ... etc.). The problem discuss in this article is general minimum cut problem. Given an undirected graph G = (V, E), a cut is to split the nodes of the graph into two set S and T. Any edge (u, v) in E with either u in S and v in T or u in T and v in S is a cut edge, which is belongs to the cut set. In weighted undirected graph, a cut is minimum if the sum of weight of its set is the smallest among all possible cut set.

Gomory-Hu tree. This algorithm is used to construct a general graph into a tree, weight of edges of the tree correspond to the weight of the cut set to disconnect adjacent vertices. The idea of this algorithm is very simple. At the beginning, pick two vertices arbitrarily, and compute the minimum cut between them. Then separate the graph into two groups, contract the edges in the cut set into a new edge e', and the weight of e' is the weight of the cut set. After that, in each iteration, pick two vertices from the same group, and find the minimum cut between them, then separate the group into two and contract the edges as before. It is obvious that this algorithm only need O(n) iterations of computing minimum cut. There are many variations of this algorithm to get a better time complexity, you can google it if you are interested in.

Stoer-Wagner's min-cut algorithm. This is the algorithm I implemented these days. The algorithm is based on a theorem. Let s and t be two vertices of graph G = (V, E). Let G/{s, t} be the graph obtained by contracting s and t. Then, a minimum cut of G can be obtained by taking the smaller of minimum s-t cut and minimum cut of G/{s, t}. By this theorem, Stoer and Wagner comes up an algorithm. In each iteration of the algorithm, get two vertices which have a minimum cut to separate them, then contract these two vertices. This algorithm follows the theorem stated above. If the minimum cut is not current s-t cut, then it should be in the graph G/{s, t}. The following is the pseudo code of this algorithm.

MinCutPhase(G, w, a):
 A <- {a}
 while (A != V)
  x <- Most Tightly Connected Vertex
  if (|A| == |V| - 2)
   s <- x
  if (|A| == |V| - 1)
   t <- x
   CurrentCut <- (A, complement of A)
  add x to A
 Contract(s, t)
 return CurrentCut

MinCut (G, w, a):
 while (|V| > 1)
  CurrentCut <- MinCutPhase(G, w, a)
  if (w(CurrentCut) < w(MinimumCut))
   MinimumCut <- CurrentCut

In the pseudo code above, the definition of most tightly connected vertex x is:

x not in A s.t.

w(A, x) = max { w(A, y) | y not in A }

The only thing that we need to care is the correctness of the MinCutPhase function, and it can be proved by induction. This algorithm also need O(n) iterations to compute MinCutPhase(). If priority queue is used for getting the most tightly connected vertex in each iteration in MinCutPhase, in total it needs O(nlogn) time. For updating the weights of all the edges from the selected vertex to any vertices not in A, in overall it takes O(m) time. As a result, this algorithm run in O(nm + n²logn) time.

Related Problems:

Minimum Cut (from acm.pku.edu.cn)
Bomb, Divide and Conquer (from acm.uva.es)

Reference:

Stoer, M. and Wagner, F. 1997. A simple min-cut algorithm. J. ACM 44, 4 (Jul. 1997), 585-591. DOI= http://doi.acm.org/10.1145/263867.263872
Anne Loomis, Min cut, CS 105 (Winter 2005), Computer Science, Dartmouth College

20071219

Answer of yesterday's game

Although it is not 24 hours yet, I still want to give the answer and solution to you.
As some of you may know, what I did is to hide the most significant 4-bits/ 3-bits of an image to the least significant bits of each pixel of the photo. It is the reason why the photo did not change much after this modification. The reverse is also very intuitive, I will leave it to you.

Here is the image hidden in each photo.

Encode	Decode

photos taken by Sam Rohn - Location Scout

Here is my source code, which is written in python. If you want to run this code, you need to have the package Python Imaging Library (PIL).

Reference:
http://en.wikipedia.org/wiki/Steganography
http://www.pythonware.com/products/pil/
http://petitcolas.net/fabien/steganography/
http://utilitymill.com/utility/Steganography_Encode

20071217

Steganography Study

I have promised to give a funny game yesterday. However, actually, it is not that easy to make the game. This game does not have a very strict rule, and it is not really a game. This game just want to give an opportunity for me and you to get more familiar with steganography. I will provide three photos below, and what you need to do is try to get back the images hidden in these photos. I will give the solutions and the program to fetch the hidden images tomorrow.

photos taken by Sam Rohn - Location Scout
Hint: 4-bit/ 3-bit pixels of the hidden image is inside the given photos.

20071216

Cryptographic Techniques

Today, I would like to discuss some technical terms which are related to cryptography. Cryptography is the art of achieving security by encoding messages to make them non-readable. In general, we say that a message need to be encode is called plain text, while the encoded message is called cipher text. There are two primary ways to encode a plain text message, Substitution and Transposition.

The earliest substitution scheme is called Caesar Cipher, proposed by Julius Caesar. This encryption algorithm is to replace each alphabet in the message with the alphabet three places down the line. (ie. A replaced by D, B replaced by E, ... Z replaced by C).
For further information about substitution techniques, please visit Substitution cipher.

Rail Fence Technique is an example of transposition. This algorithm first write down the plain text message as a sequence of diagonals, then read the plain text written as a sequence of rows. eg. Original plain text message: what the hell you are doing
Ｗ　Ａ　Ｔ　Ｅ　Ｅ　Ｌ　Ｏ　Ａ　Ｅ　Ｏ　Ｎ
　Ｈ　Ｔ　Ｈ　Ｈ　Ｌ　Ｙ　Ｕ　Ｒ　Ｄ　Ｉ　Ｇ
and the result cipher text is "wateeloaeonhthhlyurdig". Other transposition technique is quite similar to Rail Fence Technique, here is more examples of Transposition cipher.

Every encryption and decryption process has two aspects, the algorithm and the key used for encryption and decryption. There are two cryptographic mechanisms, depending on what keys are used. Symmetric Key Cryptography, is the mechanisms that using the same key for both encryption and decryption. In opposite, the mechanisms use different keys for encryption and decryption is called Asymmetric Key Cryptography.

In symmetric key cryptography, the problem is key distribution. Since the key is to decrypt the message in the receiver side, how can the key distributed securely to receiver? Whitefield Diffie and Martin Hellman developed an amazing solution for key distribution problem in 1976. The solution is called Diffie-Hellman key exchange algorithm. The algorithm is very easy to understand, here is how it works. First, if A and B want to exchange message, they first come up with two large prime numbers, n and g. These two numbers need not be kept secret. Then A and B choose two large random number x and y respectively, then calculate two numbers v_A = g^x mod n, v_B = g^y mod n respectively. After that, A and B exchange v_A and v_B. At last, A will get the secret K1 = v_B^x mod n, B will get the secret K2 = v_A^y mod n. At last, K1 is equal to K2, and the key has been exchanged. However, this algorithm raises another problem, it is caused by the first step. If the third party, user C, intercept the message and get the value n and g. then C can continue the whole process to get further data exchange between A and B, because C holds the keys to communicate to A and B. However, A and B will never know that their data has been hijacked. This problem is called man-in-the-middle attack.

In asymmetric key cryptography, the problems mentioned above will not exist. When A try to communicate with others, it can ask the trusted third party T, to get a pair of key, one is called public key, which will be distributed to those who want to send data A. The other is called private key, which is held by A to decrypt the message. The other name of this cryptography mechanism is called Public-key cryptography.

Another message encoding technique is called steganography. This technique is to hide the message that is to be kept secret inside other messages.

ps. I will provide a fun game tomorrow.

20071215

Cryptography and Network Security

I am reading this book "Cryptography and Network Security" (Seems Amazon does not have this book, please tell me if you find it in Amazon). Seriously, I want to learn network security, and that's why I resume this blog for making notes when I am reading it.
Hope you enjoy and rise questions or comments if you have any.

Chapter 1: Introduction
In chapter 1, it describes some basic principles of security, and attacks related to each principle. There are mainly five principles of security, they are confidentiality, authentication, integrity, availability and non-repudiation.

The principle of confidentiality specifies that only the sender and the intended recipents should be able to access the contents of a message. Confidentiality gets compromised if an unauthorized person is able to get the message. The simple example is, if user A want to send a message to user B, another user C capture the message without permission or knowledge of A and B. This type of attack is called interception.

Authentication mechanisms help establish proof of identities. The authentication ensures that the sender of a message is correctly identified. If user C sends a message to B. However, C has posed as user A when he sent this message to B. User B would not know that the message is come from C, but not A. This kind of attack is called fabrication.

When the contents of a message is changed after the sender sends it, but before it reaches the receiver, then the integrity of this message is lost. For example, user A transfers HKD $100 dollars to user B through the online Banking System. Unfortunately, user C capture the message and edit the content as "Transfer HKD $1000", both user A and B has no way of knowing that the contents were changed during the message was transferring. This attack is called modification.

Non-repudiation does not allow the sender of a message to refute the claim of not sending that message.

The principle of availability states that resources should be available to authorized parties at all times. Due to the intentional actions of an unauthorized user C, an authorized user A may not be able to contact a server B, this is an attack called interruption.

Theoretically, attacks can be divided into two categories, passive attack and active attack. passive attack is not easy to detect because attacker does not attempt to perform any modification to the data. Obviously, active attack is the opposite of passive attack, it is based on modification of the original message, and this kind of attack is easy to detect but difficult to prevent. The following two are examples of each attack.

IP Sniffing is a passive attack on an ongoing conversation. An attacker can simply observe packets they pass by. There are two ways to prevent attackers from sniffing packets. The first is encode the data before sending it, second is the transmission link itself can be encoded.

In IP Spoofing, an attacker sends packets with an incorrect source address. When this happens, the receiver has no way to know that the sender is fake, and he send replies back to the forged address, and not to the attacker. However the attacker can intercept the reply to get information he needs for hijacking attacks, or just want to cause the Denial of Service by these messages.