Not all the Redis values are strings...

Working with a Redis database we discovered a very strange behavior after a refactor on one of the services.
Before the refactor we have been storing on Redis sets with only integer values, but we decided to add some information as a suffix of a couple of chars, something like: 12312412 -> 12312412:b after this refactor, the memory usage of the instances of the cluster, was increased from ~2GB to ~10GB, this was something unexpected for us, according to the Redis documentation, the sets only store "binary-safe strings" values: "Redis data types"
And after check how Redis handles the strings (Hacking Strings), the relative memory increase should to be directly proportional to the increase of characters of the values. According to the increase of the values lengths after the refactor we expected an increase of the 20% but it was of the 500% :( .

I decided to do a little proof of code:


Well, as you can see, we test two kind of values, the integer sets will contain numbers from 10000 to 10030 with a zero at the end, then the result will be integers: 100000, 100010, 100020, ..., 100300 , and the string sets will contain the same number but with the zero before the number, this will force to Redis to store this values as strings: 010000, 010001, 010002, ..., 010030 .
The expected behavior, if Redis stores the values as strings, is that after create all the sets, the memory usage will be the same for both test cases... but:



This unexpected behavior is caused by the next lines of the Redis source code: t_set.c
Redis checks if the value can be represented as "long long", and in that case stores the value as its integer representation, a clever behavior, but I didn't find it documented.

New Spotify Puzzles - Reversed Binary, Zipf's song, Cat vs. Dog - solutions

I discovered some months ago that Spotify has published some new puzzles. I love the puzzles, and was impossible to me resist the tentation to solve all of them :)

Reversed Binary Numbers

https://www.spotify.com/es/jobs/tech/reversed-binary/

Solution:
 - https://github.com/alonsovidales/spotify-puzzles-v2/blob/master/reversed_binary/reversed_binary.py

This is the simplest problem, I used less than ten minutes to solve it.
The steps to solve it are:

1. Get the string representation of the number in binary using the bin() Python function
2. Remove the first two characters, that Python adds to identify the string as a binary representation using the [:] notation
3. Using [::-1] Python will reverse the array (-1 is the step)
4. Convert the reversed array to an integer again using the int() call and specifying as second parameter the base 2

Zipf's song

http://www.spotify.com/es/jobs/tech/zipfsong/
Solution:
 - https://github.com/alonsovidales/spotify-puzzles-v2/blob/master/zipfsong/zipfsong.py

This puzzle was a little more complicated, not for the problem, is only to apply a simple formula, was because the team who did the puzzles made a little mistake and the platform always was returning a "Run Time Error" each time that I tried to send the answer, I wasted around two hours trying to found the error on my code, and when all the hope was left, one of the persons in charge of the puzzles sent me an e-mail:

Was really nice discover that was a concerned team behind the puzzles, and that I was not in a mistake :)

The steps to solve this puzzle are:

1. Calculate the quality of each song applying the formula: number of times plus the song position
2. Sort the array of tracks by quality
3. Split the array to get only the necessary song names
4. Return the list of tracks as a string

Cat vs. Dog

https://www.spotify.com/es/jobs/tech/catvsdog/
Solution:
 - https://github.com/alonsovidales/spotify-puzzles-v2/blob/master/catvsdog/catvsdog.py

This is the most complicated of the three problems, but if you remember the old puzzle "Bilateral":
 - http://alonso-vidales.blogspot.com.es/2012/03/spotify-bilateral-projects-puzzle.html
is much more simple :)
Reading the puzzle was easy to discover some clues:

1. Also, based on the universal fact that everyone is either a cat lover (i.e. a dog hater) or a dog lover (i.e. a cat hater), it has been decided that each vote must name exactly one cat and exactly one dog. -> Is a bipartite graph
2. procedure which guarantees that as many viewers as possible will continue watching the show -> Is a maximun cardinality problem :)

Then we have a bipartite graph:

 - http://en.wikipedia.org/wiki/Bipartite_graph

Now we have a reduced number of algorithms to apply with a small complexity. 

We have two options, study the compatible or the incompatible graphs of voters. If we build the bipartite graph of the incompatible voters, we can obtain the maximun matching on this graph, and a full coverage of all the vertex.

The minimun number of edges who cover all the vertexes of the incompatibles graph are equal to the minimun number of voters to be discarded in order to obtain the maximun number of happy voters :)

To obtain this we found an old friend, one of the most beautiful algorithms, the Hopcroft-Karp algorithm (the same to be used in order to solve the old puzzle):

 - http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

The steps to solve the problem are:

1. Create the bipartite graph of incompatible voters, I used sets to do it as fast as possible
2. Apply the Hopcroft-Karp algorith to obtain the min number of edges who cover all the graph
3. Subtract the number of edges who cover the graph of the total number of voters, this will give us the max number of happy voters that we can obtain :)

Thanks Spotify for this puzzles :)

Spoofed links on Facebook

This bug allows to share links on Facebook that will seems absolutely legit, but linking to a different location than the location who Facebook show.
The problem is the flow who Facebook uses when a user share a link:

1. Connect with the linked site
2. Download the site information
3. Check that all is correct, sanitize all in order to ensure that the user don't send something that can harm to the other users, etc
4. Put all the information in a form that the user will send to publish the link
5. And, this is the problem, trust on the information that the user send on this form

All the developers knows that  is dangerous to trust on the information that the users send, If the user want, him can send a spoofed form altering the information contained into the form values.

I reported this bug the past 30 of december (more than a month ago), but I didn't receive any response, and they didn't watch or download the demonstration video (I uploaded the video to one of my servers, and I can't find any access on the access_log file to the video):

Non persistence XSS on the Spanish Senate site

The last week, when I was visiting the senator web site, I discovered something stupid, when you add some GET params to the URL this params are included directly without escape on the links used to share the current page on the different social networks (Facebook, Tuenti and Twitter).
On the next example I add a new attribute with name "aaabbb" and value "hello" to the social links:

Ok, I can add attributes to the links, now the problem is that if I try to use any of this characters: ', <, >, (, ) , the page redirect us to a 404 page:

Well, we have a problem, we can insert JavaScript code inside the attributes, but we can't execute anything without the ( or ) characters... or not...

If insert an attribute, for example onmouse over, you can insert assignations, for example:

   var aux1 = this.parentNode.parentNode.innerHTML;

We didn't use any of the forbidden characters, and we have a very interesting string like:

    <link type="text/css" href="/web/css/jquery-ui.css" rel="stylesheet"><a href="#" title="Enviar"><img src="/web/images/enviar.png" alt="Enviar" onclick="MostrarDialog();" title="Enviar"></a><a href="#" onclick="$(&quot;#menu_buscador&quot;).hide();

Ok, what can we do with variable assignations and this string on JavaScript to execute code out of the jail....

We can for example do the next:

    this.innerHTML = "<img onload=\"code_to_execute();\">";

But... as you can see I'm using the <, (, ) and " characters and I can't use this characters on the URL. Then, for create the "<img..." string I can use the string that I get on the aux1 assignation.

For example for the < character I can do aux1[0], that concatenated with the aux1[2] will give me the sting "<i"and I don't need to use eny of the forbidden characters. Then doing:

    this.innerHTML = aux1[0] + aux1[2] ....

I can obtain any string to be used as innerHTML, then I'm out of the jail :)

Is really tedious try to create complex strings concatenating characters one by one, to do this easy I did a very simple PHP script:

Inside the "buildInjection" call parameter you can put the code what you want. For this example, I use the system to using jQuery load a Script from a external server, then you can include more complex code on this script.

The code that I inject modify the art gallery by another more sophisticated :) :

In resume, yes, we don't have a permanent XSS, but, we have the control of the site using the social links, then we can, for example, share this URL instead of the correct one by the social networks as a "XSS Worm":

    http://en.wikipedia.org/wiki/XSS_worm

I reported this bug a week ago to the official senate twitter account, and by e-mail but I didn't receive any answer: 

    https://twitter.com/alonsovidales/status/274329835646615552

A video that show all the process:

HTML5 Guitar Simulator app rejected by Spotify

A video of the proof of concept:

I sent an application to create a Spotify App, but it was rejected due to:

"That’s because you have a Guitar hero feature in the app."

The App is a simple Guitar simulator as another Guitar simulators, ex:

• Guitar Freaks: http://en.wikipedia.org/wiki/Guitar_Freaks (was released in 1998 seven years before than the first Guitar Hero)
• Rock Band: http://en.wikipedia.org/wiki/Rockband
• Frets on Fire: http://en.wikipedia.org/wiki/Frets_on_fire (an open source version)

I sent an e-mail trying to show the error to the Spoify team, because I want to do a Guitar simulator, not a Guitar Hero copy :( , and now they told me:

 "It is not the fact that it is similar to Guitar Hero per sé it is the fact that we cannot have games with these concept in Spotify."

Ok, then I don't know why the app was rejected :( , the reason "we cannot have games with these concept in Spotify" is stupid, I don't know what kind of apps they want to have in the store...

You can find the source code of the proof of concept here:

    https://github.com/alonsovidales/Sons-Of-Rock/

And the specifications document here:

    https://github.com/downloads/alonsovidales/Sons-Of-Rock/specs_doc.pdf

The e-mails:

Tuenti Programming Challenge 2 - 2012

I had a bit of free time, and I uploaded my solutons to GitHub of the Tuenti Challenge of this year. 
https://github.com/alonsovidales/Tuenti-Programming-Challenge-2

Spotify - Bilateral Projects: Final Puzzle solution

Ok, I finally created a correct solution for the Bilateral puzzle of Spotify.
I wrote a previously article about this:
    http://alonso-vidales.blogspot.com.es/2012/03/spotify-bilateral-projects-puzzle.html


The problem is that the previous solution first calculates the max-cardinality, but to calculate the max vertex cover I used a permutation to calculate all the possibilities.
I spent a bit more time reading about bipartitie graphs, and how to find the min vertex coverage with the smallest complexity, and I found the "König's theorem":

    http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory)


This theorem can be combined with the Hopcroft-Karp to solve the problem in the smallest complexity.
The problem is that I didn't find any implementation of the König's algorithm that I can use, and I decided to read the Algorithm definition, and create one. Is really simple to do it after understand how the algorithm works.
And at the end....

You can find the solution code here:

    https://github.com/alonsovidales/Spotify-Puzzles/tree/master/bilateral