URL shortening services had experienced a big push in the age of social networks rising, such as Twitter, where big urls collide with the 140 characters user input restriction.

So there was this need of magically transform URLs like this one http://raduboncea.ro/2009/04/01/twitter-autofollow-and-dm-using-python-twitter-imaplib-and-gmail/ into something like this http://tinyurl.com/cralfk.

Many would be tempted to think there is some kind of compression algorithm that would shorten a big URL and make it fit into a unique combination of 4,5 or 6 characters and then decompressed upon user request. Well it doesn”t work like this, mathematics prohibit it.

So how does it actually work?
A URL shortening service takes the big URL and saves it into a database along with an auto incremented numerical value, an id or sequence, so we would have the first big URL saved with ID=1, the second with ID=2 and so on. When someone would ask for http://tinyurl.com/1/ we would get from the database the big URL identified by ID=1 and redirect the user to that URL.

But there is a problem: having numerical ids does not shorten urls too much. For the URL number 1 million we would have 7 numerical characters. So the next step is to change base numerotation from 10 to a bigger one, lets say 36, so we include all a-z small latin letters or, why note, 62 which includes also the capital chars A-Z.
In 36 base we can save as much as 1.679.615 URLs into 4 characters. On base 62 we have 14.776.335 URLs fit into 4 chars, almost 10 times as much as base32 and 14.776 times base10.

Some security issues.
Many shortening services stopped to the algorithm above without digging into a very important security issue which is related to how redirects work. It is critical, before redirecting users to the URL they requested to check what’s behind that URL, to check if the URL is not yet another redirect which may result into a recursive loop and may disrupt the service.

A malicious user may save a URL to a page which will later modify to redirect back to the service URL and thus attempting to generate an infinite loop which could make the interpreter to hang.

To avoid this kind of DoS vulnerability, we must not allow redirects to our own links and to limit redirects to outside to a smaller finite number of depths analysis.

Beneath a small model-view example in django, using also urllib to check for redirects and the base10-base62 conversion algorithm similar to the base36 which is included in django.





Articole asemanatoare: