Which road do I take?

Oct 09 2011

plinkplonk says:

One day Alice came to a fork in the road and saw a Cheshire cat in a tree. ‘Which road do I take?’ she asked. ‘Where do you want to go?’ was his response. ‘I don’t know’, Alice answered. ‘Then’, said the cat, ‘it doesn’t matter’.

A good (non generic) answer to “What should I learn?” (asked by a self educated programmer here) depends on the answer to the question “What (kind of programmer) do you want to be?” Step 1, answer the Cheshire cat! )

2 responses so far

Steve Jobs on Media and People

Oct 09 2011

When you’re young, you look at television and think, There’s a conspiracy. The networks have conspired to dumb us down. But when you get a little older, you realize that’s not true. The networks are in business to give people exactly what they want. That’s a far more depressing thought. Conspiracy is optimistic! You can shoot the bastards! We can have a revolution! But the networks are really in business to give people what they want. It’s the truth.

- Steve Jobs in WIRED magazine, February 1996

One response so far

Why it is hard to break hash functions

Jan 13 2011

I was going through the skein hash function when one friend asked why it is difficult to break a cryptographic hash function. A comprehensive introduction to hash functions is well beyond the scope of this article, so if you want to refresh your memory, please read it up from elsewhere and comeback.

Any good hash function must have the following features:

  1. Preimage resistance: given a hash h it should be hard to find any message m such that h = hash(m)
  2. Second preimage resistance: given an input m1, it should be hard to find another input, m2 (not equal to m1) such that hash(m1) = hash(m2).
  3. Collision resistance: it should be hard to find two different messages m1 and m2 such that hash(m1) = hash(m2).

When somebody tells you that it is impossible to break a hash function, you ask the question: What does it mean to break a hash function? The short answer is that if you are able to find out a message corresponding to the given message digest, the hash function is said to be broken.

If you are a programmer, you may think:

If hash function is implemented using some algorithm, shouldn’t it be possible to reverse the algorithm and get back the message corresponding to the message digest? If the algorithm runs step-by-step in the CPU, shouldn’t it be possible to trace back through the steps that resulted in the output?

The answer is of course: No.

Why?

The simple answer is that all hash functions can be considered to be one way functions. One-way functions are mathematical functions using which you can compute the output for any input, but extremely difficult to find out the input when any random output value is given. ie., one-way functions cannot be inversed/reversed.

For example, take the integer factorization problem. It is easy to multiply the numbers 101 and 103, but it is very difficult to find the factors of 10403 (If you don’t know the answer in advance, of course). Of course you can find the factors using a computer, but integer factorization becomes harder and harder as the magnitude of the numbers go up. For large enough numbers, even computers find it incredibly difficult to find the prime factors.

Cryptographic hash functions employ some kind of one-way function so that the message digest cannot be easily reversed to form the corresponding message.

Let us examine the Skein hash function and see why it cannot be broken. (Skein is an example of  a hash function that uses a block cipher as a basic building block. Many modern hash functions have similar structure.)

The basic structure of the skein function is shown in the following figure:

The basic block in the Skein hash is a function called UBI. As you can see there are several inputs to the hash function. The only variable input is the message. This means that we can pre-compute the output of the first UBI block. So in essence our problem becomes:

You would have assumed by now that to reverse this hash function, we will have to reverse the UBI blocks. Let us take a peek inside the UBI block.

The Skein hash function uses Threefish encryption function in its UBI blocks. The original message is considered as the plain-text input to the first UBI block and it is encrypted using the precomputed value from the config block as the key. This encrypted value is input as the key to the last UBI block.

If we try to reverse the last UBI block, we will understand that what we have to do in essence is to retrieve the key of the Threefish encryption given the plain-text and the cipher text. Now if you know anything about encryption algorithms, you would know that it is impossible to retrieve the key given a {plain text, cipher text} pair for a good enough encryption algorithm. This is a basic property of encryption algorithms.

All this essentially boils down to one insight:

Skein hash function is hard to break because it is hard to find the key for the encryption algorithm used inside the UBI blocks – In case of Skein the block cipher used is ThreeFish. Many popular hash functions use some type of block cipher inside them and that is what gives them their strength.

So now the question becomes:

Why is it hard to find the key of an encryption algorithm?

To find out the answer, we should look inside the specific encryption algorithm used. More on that, later.

7 responses so far

Collapsible comments for Hacker News

Nov 03 2010

Here is a JavaScript bookmarklet to make the comments in Hacker News collapsible (reddit style) by clicking on the [-] icon next to each comment.

Click here to install the bookmarklet

(WordPress screws up my bookmaklet code. So I have moved the bookmarklet to a new page)

Usage: When the page is loaded, click on the [-] icon in your bookmarks bar. Each comment in the page will show a small handle [-] to collapse the comment and its children. Once you click and collapse the comment, the icon changes to [+] and you can click again to expand the comment (and its children).

This fixes a few issues with the script by Alexander Kirk, like collapsed child comments expanding when the parent is expanded. In addition to these this script will work in the threads page of hacker news. Also this bookmarklet will load faster than the script by Alexander since there is no call to any external JS file from my server. The only file you have to load is the latest jQuery from the jQuery website and chances are good that the file is already present in your browser cache. (The downside is that you will not be able to get the latest version when I update the code).

If you want to play around with the code, head to github: Collapsible comments for Hacker News

You my also want to checkout the no-nonsense URL shortener bookmarklet. It is super-fast and does not redirect you anywhere. It just displays the shortened URL in the corner of your web page.

2 responses so far

3n+1 Conjecture

Aug 29 2010

The 3n+1 conjecture or the Collatz conjecture is an unsolved conjecture in mathematics. So what is 3n+1 conjecture? From wikipedia:

Take any natural number n. If n is even, divide it by 2 to get n/2, if n is odd multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1.

Even though the idea of the conjecture is very easy to understand, it is suppose to be a very hard problem to solve/prove.

I was doing some learning of the 3n+1 conjecture. As naive as I am, I went right ahead trying to prove the conjecture. Now the problem with me trying to solve this hard problem is that I am not even qualified to be called an amateur mathematician. I am just a programmer with a lot of free time. Furthermore, mathematics is an advanced field and I cannot even comprehend the basic literature on the subject. Anyway, working on this was fun and so I thought I would document it here.

First let us start by the assumption that the 3n+1 conjecture is true, i.e, no matter what number you start with, you will reach the number 1 in the end. To prove this, we will use the method of contradiction. This means that we will say that certain conditions should be met if the conjecture is false. By proving that the conditions supplied or intermediate results break down or contradict with the assumptions before it, we can say that the assumption that the conjecture is false, is false.

So now assuming that the conjecture is false, there should be some number(s) that does not reach 1 when the operations are applied to it infinitely. Let us call the smallest of these numbers X.

So X is the smallest number that violates the 3n+1 conjecture.

(1) Assume that X is an even number.

If X is even, the first operation to do would be X/2.

Since X cannot reach 1, X/2 (which is in the same series) cannot reach 1. This means that X is not the smallest number violating the conjecture (X/2 is smaller).

This contradicts our initial assumption and so X cannot be an even number.

(2) Now, assuming X is an odd number.

Odd numbers can be divided into two types (for our convenience).

  1. The numbers that can be represented as 4n+1.
  2. The number that can be represented as 4n+3.

where n = 0,1,2….

(2.a) If X is an odd number of the type 4n+1:

X = 4n + 1

Since X is odd, the first operation to be done on X would be to find 3X + 1.

3X + 1 = 3 (4n +1) + 1
3X + 1 = 12n + 4

Now the resultant number is an even number and so the next operation will be to divide by 2.

(12n + 4 ) / 2 = 6n + 2

This is still an even number and so we divide by 2 again:

(6n + 2) / 2 = 3n + 1

This means that 3n + 1 is also a number that violates 3n+1 conjecture. Now as you can see, 3n + 1 is a smaller number than X (which is equal to 4n + 1).

So again by the method of contradiction we can safely say that the number X will not be of the form 4n + 1.

So finally we are left with odd numbers of the form 4n + 3.

So we know that any number that violate the 3n + 1 conjecture will be of the form 4n + 3.

Proving this last part is left to the reader as an exercise. (I mean, I did try this part for a few days, but it didn’t go anywhere.)

8 responses so far

ReImages – Reload images in web pages

Aug 28 2010

This is a bookmarklet to reload the images in any web page without reloading the web page itself.

ReImages

(Drag the above link to your bookmarks bar or right click and add to your bookmarks.)

You can click the link whenever you want to reload pages in any web page without reloading the page itself. This bookmarklet reloads images in <img> tag as well as background images for any element in the page.

This can be very useful in many cases:

  1. During web development (especially when you are working on an image that appears only after you do some action in the page, like on a pop-up).
  2. When some server (or a stupid firewall or some other device)  serves you old cached version of the images.
  3. When a large image in a page did not load completely and when you try to refresh the page it is still loading the broken version because it gets the image from the browser cache

etc.

This is the initial version. Let us call it v0.9.

I have been using it for a while without any issues, but let me know of any bugs you come across.

If you are a web developer, take a look at the wonderful ReCSS too.

One response so far

Books and Blogs

Aug 04 2010

Rant follows.

Reading is taking up much of my free time these days. Of course I am not talking about the reading online. Spending time online has been a huge time sink for me (and as I can imagine, for millions of other people like me) over the years. I have turned to reading books with more enthusiasm ever since I realized that the stuff that I read online does not stay with me for a long while, while the books I read have a profound way of changing the way I think.

Now don’t get me wrong; I am not blindly implying that all the information out there in the web is a waste of time. I am just saying that for me personally, books give more satisfaction when I finish one compared to hundreds of blog entries I used to devour on a constant basis. Even though I have cut short on the number of blogs I visit and the number of articles I actually read, there are communities like Hacker News where I tend to hang out. Hacker News is a great source of news, information and inspiration for the curious type, but it may also have the effect of wasting a whole lot of your time if you start believing that all of the time you spend on Hacker News is productive.

Reading itself is not a productive activity in the absolute sense of the word (or in any other sense of the word I can imagine), but it is a really fulfilling and satisfying experience (not to mention that it strokes your ego when the height of the books you stacked up in your cupboard grows more than that in your close friends’ room). Even though reading books involves seemingly similar activities as to reading a blog, there are some real differences that make them worlds apart in actual utility.

The first is that your mouse is a constant stream of distraction at your fingertips. Every time I read an article, I try (in vain) not to click on the other tabs to check my email or the traffic stats of my blog; not to mention the advertisements and other outbounds links in the same page itself. Even the hyper-links in the article you read are very distracting, according to some [1]. Now that you have noticed it, that is the reason I am not using any hyper-links in the middle of this article. Many of the links in a typical blog post point to the definition of terms in the Wikipedia anyway, and they are not very useful; but I digress.

The point is that just the act of sitting in front of the computer with the goal of consuming the internet translates into thousands of interesting (or irrelevant) articles, news, stories, pictures and videos fighting for your attention. The problem is that you have only a finite amount of attention. You have only a finite amount of stuff you can process per day.Yes, there is a limit to your cognitive ability. This means that there is a limit to what you can read and assimilate in a given time. And this in turn means that all those distractions are getting the way of you learning something useful. Now I am not advocating that you abandon your fair share of lolcats, but rather wondering whether you are spending a lot more time on them than what can be deemed excusable.

The second difference between books and blogs is that a book is a lot more harder to write than a blog post. You can be sloppy while writing a blog post, knowing that you can later change your words as necessary. Books are very difficult to get published compared to blog posts. Getting a decent publisher to publish your book is not going to be easy for you.  This means that only very few books which are written are actually published and whatever is published goes through a good deal of scrutiny and editing which enhances the quality of the material you get to consume. This does not mean that there are no well-written and well-edited articles out there in the web. I am talking about the typical blog post (By the way, referring to the typical stuff is a great way to say anything you want in an argument). Even given these facts, you can find great articles worth reading in the web by following news aggregators like Reddit or Hacker News, but then again there comes the problem of loads of wasted time with these websites. Even though news aggregators are good at finding the best articles in the web, there is one other fundamental difference between books and essays that makes me go back to good books.

The third difference between a book and essays is that a book has got all the time in the world to convince you of the idea that it is trying to sell. Books are usually hundreds of times longer than your typical blog post and this means that a book author can take his time to establish the basics and build on them and the take the reader through the innards of the subject he wants to write about. The fact that a book takes hundreds of pages to present its plot means that the idea the book tries to sell will stay in the back of my mind for many years, compared to an essay whose central thesis will be forgotten in a matter of minutes when other distractions occupy my brain.

So my request to the dear reader will be to complement what you read in the web with some very good offline reading. Good books can change you life, while blog posts usually are not that powerful. And while we are at it, just keep in mind that producing something useful and making something people wantTM is way more better than reading books 24 hours a day.

That’s it. We are done here. Go away.

[1] Experiments in delinkification

[2] Photo credit: somegeekintn

11 responses so far

« Newer posts Older posts »