csKa blog

Move to WordPress

2008-06-03T01:51:00.000+08:00

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/

document.write()

2008-05-23T13:38:00.019+08:00

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.

Minimum Cut

2008-01-01T00:16:00.000+08:00

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

Answer of yesterday's game

2007-12-19T20:57:00.000+08:00

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

Steganography Study

2007-12-17T22:04:00.000+08:00

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.

Cryptographic Techniques

2007-12-16T21:54:00.000+08:00

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.

Cryptography and Network Security

2007-12-15T23:51:00.000+08:00

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.

Next Topic: Searching

2007-09-27T18:54:00.000+08:00

New ACM Season

2007-09-22T19:34:00.000+08:00

Covering Rectilinear Polygons by Rectangles

2007-05-29T20:56:00.000+08:00

Covering Rectilinear Polygons by Rectangles is a category of problems, the general definition of the problem: A board B is a finite set of unit squares lying in the plane whose corners have integer coordinates. A rectangle of B is a rectangular subset of B. A rectangle cover of B is a collection of rectangles whose union equals B.The rectangles of a cover may overlap, but each of them must be wholly contained in the board.

This problem obviously is NP-Complete, I am still thinking of the proof. The first idea come up is that it is finding maximal cliques on the graph G(B), G(B) is a graph whose nodes represent squares in B. Two square u, v are adjacent in G if Rec(u, v) in B. The other similar NP-complete problem to rectangle covering, is set cover problem.

There are some specialized problems. For example, the given board B must be convex and no hole inside the board.

Since the problem is NP-complete problem, most of the attention is focus on the approximability of the problem. Erdos asked if Theta / Alpha [1] is bounded, but it still cannot be proved yet.

This problem is quite interesting and applicable, one of its application is an operation used by microelectronics industry. A layer of an integrated circuit is to be printed on a photographic plate. The printing is done by flashing rectangles onto the plate and as few rectangles as possible.

[1] Theta is the rectangle of B; Alpha is anti-rectangle of B, ie. a set of squares in B that no two of which are contained in any rectangle.

A report for PC tree

2007-05-05T20:30:00.000+08:00

The beta version of the PC tree report is finished. The topic is "PC tree and its application". This report first discuss the use of PC tree for testing consecutive-ones property of a 0-1 matrix. Then discuss its further application on interval graph recognition and planarity testing.

However, I start writing terribly when describing the application. If you don't understand what they are talking about, please feel free to ask me, I will fix it asap, but not today XD

PC tree and its application

Online judge security problem

2007-04-28T22:22:00.000+08:00

These few days, I am trying to use Python to rewrite the core of a online judging system (I use C to implement it before).
First, let me brief describe what is included in the core system.

Compile program

distinguish what programming language the user is using; (basically it only support Pascal, C and C++)

use the corresponding compiler to compile the source code;

limit the size of the objective program it can generate;

report the compilation is success or not.

Judge program

run the compiled objective program with specific test input;

limit its running time, memory used when it is executing;

restrict its function call (or system call); (more on this later)

compare its output with the test output;

or, special judge if necessary.

I would like to discuss why we need to restrict its function call. Actually, it is both a security issue and prevent on cheating.
Let's discuss the prevention on cheating first. Obviously, if the user know the judge system architecture, one way to cheat is to open the test output file and print it, then he must get an Accept on the task. Or, if the system has stored other users solution, the cheater may hack in and use the solution as his own, even get a copy.

The most serious problem is that, the hacker may write a program which is trying to damage the operating system (OS). He may delete files, change the ownership of files, even get copy of some private files, then he can do some further attack. How horrible it is!

What most commonly use in C is a function ptrace (if I remember correctly, it only available *nix system). How it works is as follow.

ptrace is called in a child process and stating that ptracing on itself;

then parent process keep ptracing on its child process, for each signal the child process send out, parent process is first capture it before it send the signal away;

at this point, the parent process is trying to recognize what child is doing by reading this signal, if its child is a bad guy, parent will kill him immediately;

otherwise, parent will allow the child continue its process.

Actually, ptrace itself is also a very useful tool for hacking program. If the system allow ptrace call, hacker can write a program by using ptrace and stop some of your applications in OS and fetch the private information.

However, I am still trying to figure out how to do the same thing in Python. Actually, I cannot find something in Python which is similar to ptrace.

PC-tree

2007-04-11T22:55:00.000+08:00

Definition:

A circular-arc graph is the intersection graph of a family of arcs of a circle.

Problem definition:

Given a graph G = (V, E), determine whether the graph is a circular-arc graph.

PC-tree is a data structure used to solve the above problem, discovered by Hsu and McConnell. PC-tree is an unrooted tree, its previous version is called PQ-tree which is discovered by Booth and Lueker in 1976. This article will focus on PC-tree only, because PC-tree is generalization of PQ-tree, which means any problem that can be solved by PQ-tree can reduce to PC-tree problems.

Each circular-arc graph can be represented by a clique matrix. Consider circular arc its corresponding circular-arc graph and clique matrix as follow:

By theorem, a graph is circular-arc iff. its clique matrix must a circular-ones property (proof provide later). Now the problem is focusing on how to check a matrix contains circular one property. PC-tree take the place to solve this problem. Let me introduce what is a PC-tree first.

PC-tree has two kinds of internal node, P-node and C-node (that's why it is called PC-tree). The children of P-node can be arranged in any order (ie. all permutations). Other than P-node, the children of C-node can only be arranged in the original order or its reverse (ie. if it's leaves is "ABC", another possible ordering is "CBA"). PC-tree is built by considering the rows of clique matrix one by one. The outline of the algorithm is as follow:

for each row in clique matrix {
assign the value to each row symbol;

find a Terminal Path to separate 0s and 1s;

align all 1s and 0s to the same side;

split each node on the path into two nodes, one connect to the leaves with 1s and one connect to 0s;

delete the edges of the path and replace with a C-node x;

contract all edges from x to C-node neighbors, and any node has only 2 neighbors.

}

The circular-ones ordering can be discovered from the graph by reading the leaves on PC-tree in clockwise or anti-clockwise. Like the following:
img provide later
The time complexity of the O(|E|) (proof provide later).

Further application is: scheduling jobs, minimum coloring, maximum cliques, planarity test, consecutive-ones, ...

Cross-Site Request Forgeries (CSRF/ XSRF)

2007-04-09T21:13:00.000+08:00

Today, I google with the word "XSRF", some of you may know what it is, and it is not new. However, it is very amazing to me, because I did not think of using HTML code like this.

If you don't know what it is, let me introduce to you. If not, please state the mistake if any. XSRF, obviously is a webapp attack method. It is not only applied to HTML, but all markup language.
Let's see an example then you may know what the problem is.

<img src="http://www.bookstore.com/order.php?isbn=817525766-0&quantity=100&submit=yes" height=0 width=0 />

Although img is not including an image, the HTTP request is still send to the server. By setting the height and width of the img or using CSS style, the broken image can be hidden, the user even don't know such request has been sent. XSRF can force the user to updateing their profile, post new message or thread unknowingly. Sounds like not so dangerous, however it is more worse than that.

Difference between XSS and XSRF

Cross-Site Scripting (XSS) and XSRF are quite similar, isn't it? Actually they are not the same. XSS is try to either abuse client-side active scripting holes, or send privileged information to unknown site by inserting active code in HTML document.

XSRF is not rely on client-side active scripting, it try to take unwanted, unapproved actions on a site where the user has some authority.

It is difficult to filter content, because the XSRF attack may look like this:

<img src="http://itisnotanattack.com/logo.jpg" height=0 width=0 />

When your client requests logo.jpg, the file does not exist, but itisnotanattack.com server will redirect you to somewhere it like to show you.

XSRF can also be used to attack servers behind firewalls. It is not just public webapps that are at risk.

<img src="http://intranet/admin/purgeDB?confirm=yes" />

If the attackers knows enough to make a URL and can get the admin open this file, then everything is done. Now you know how funny (dangerous) it is.

Hide disclaimer in CSE personal hp

2007-04-06T20:00:00.000+08:00

The day before yesterday, Billy try to hide the disclaimer in his personal homepage in CSE.
Tom suggested that the html file without "</body></html>" can avoid the disclaimer include in the file.
However, clearly, it is not satisfy the rule of W3C.
The file is obviously not complete.

Actually, I still cannot get the idea how it write the disclaimer in my file.
I think the page has been pass to some program to add the disclaimmer before including in response packet.
What it added to my file is as follow:

<link ... href="/css/disclaimer.css" ... >
<script ... src="/js/disclaimer.js" ... ></script>

and

<div></div><div></div>
<div id="cse-disclaimer">
...
</div>

The .js file has a function disclaimer(), it may called at the end of the page (before </body></html>), this function will enable visibility of the disclaimer block.

What I did to block the disclaimer again is very simple, create a .js file, content is similar to disclaimer.js.
When the body is being loaded, call the block function in my .js file, and it will disable the visibility of the disclaimer.
Is it easy? Yes, it is. However I spend whole day to test it, because I am not familar with JS.

Start this blog for what?

2007-04-06T18:06:00.000+08:00

I am thinking these few day, if I should create this for making note on the interesting thing related to prog or security.
(I expect more on security. it is very new and interesting to me)

Hope I can post something everyday. :D
Please feel free to share your opinion