Birthday Paradox

There's a million places the birthday paradox has been explained. I always forget it. So this time, I decided to write it down for my own reference, keeping just the salient points in mind.

To start, a year has 365 days (forget leap years for now). The chances your birthday is on say Jan 28th is 1/365. Hence the probability of it not being on Jan 28th is (1 - 1/365 = 364/365). Let's add your friend now. The chances of both of you not having a birthday on Jan 28th is (364/365)^2 (exponential). So for 253 people the chances of all of them not having a birthday on Jan 28th is (364/365)^253. Makes sense? If not, maybe read a bit of probability from some source you like and come back. There's zero shame in this btw, I needed to do it for what it's worth :).

Anyway, so now you think why did I pick 253 above? Well let's do a little math here. If there's 2 people in a room, how many pairs can we form where order doesn't matter? Just 1 pair right? What about 3 people (a,b,c)? How many pairs? 3 pairs (ab, bc, ac). With 4 people (a, b, c, d) it is (ab, ac, ad, bc, bd, cd). Right? So let's generalize this now so we can calculate it for a larger number, instead of 2, 3 or 4. That's where combinations come in - scroll down the link (just above) to get the formula - (23!) / ( 2!) * (23 - 2)! [It's 2! because a pair has 2 people and you're forming a group of 2]. Doing the math on that it becomes:

23 * 22 * 21! / 2! * 21! = 23 * 22 /2 = 23 * 11 = 253. See that number before? :)

Tying stuff back in, it means that if I have 23 people (including me) in a room, there are 253 ways in which pairs can be formed. And remember, the chances of any of them NOT sharing a birthday are (364/365)^253. It's not (364/365)^23. It's the probability ^ no_of_possible_pairs. Again, if this is going over your head - step back and read a bit of probability theory and come back once you're comfortable.

So if the number of ways there CANNOT be pairs is (364/365)^253 = 0.4995 by the way, the number of ways there CAN CAN be a match somewhere - meaning someone in the room shares a birthday is 1 - 0.4995 = 50.05. Meaning, there is just about a 50% chance that someone in a room will share a birthday if there's at least 23 people in a room. Not share a birthday with you - just share a birthday with anyone in that room. Make sense?

Now all that's fine but how does that matter in real life, keeping security in mind? I'm thinking of a couple of examples:

- If I use a 64 bit key to create a MAC, I'm thinking that there's 2^64 possibilities which is correct. But that doesn't mean someone needs to try all of them before a match is found. Because of the birthday paradox, it means the real number is sqrt(2^64) which is a number in the order of 2^32 which is way lesser.

- Digital signatures are another area. If I use an algorithm that is susceptible to collisions to create a signature, it means that an attacker can find a collision for my signature more easily and spoof it. Meaning they could change the message, fake a signature that looks the same as the original one, attach it to the message and no one will detect it.

The fix to all this is to ensure that you use hashing algorithms who give you a larger number of possibilities even after the square root is taken. Meaning for a SHA1 hash, which has a 160 bit output - after 2^80 possibilities one will start to see collisions. It looks like SHA 256 is safe for now :)

Salt your passwords = Existing accounts password reset

This one is just a simple conclusion that I drew when a customer had MD5 hashed passwords in his database and we recommended them to salt them instead and use PBKDF as the algorithm of choice.

Now the customer added code in, but left the old code in as well which did the simple hash comparisons. So I asked them why and they said..for old users. I started thinking about it and it made sense. Here's why:

Think of it. I have a MD5 password in the database. Say I add a new column for 'salt' , generate 1000 random hashes..one for each user..and add a new column. I then change the code to query the DB for the 'salt' as well, when a person logs in and run the user's password through the PBKDF function before comparing it with the hash. Looks good?

Sure. Except that no one will be able to login. Why? It's super secure now :). No one can find any more vulnerabilities inside. Jokes apart, what's happening here? Lets say the user's original password was abc123 and it had a 32 bit MD5 hash XYZ. Now when the user logs in something like MD5(user entered password) runs..hashes what he entered and compares it to the stored hash. Match? Login successful.

Now there's the salt. So when the user logs in, the new 'salt+pbkdf' code is triggered. So PBKDF(userpwd + salt) is calculated and compared to ..what? The stored MD5 hash. Is there ever going to be a match? Largely no. Because..there is no way you can predict the salt for a particular hash..BEFORE you store it in the DB. Remember those 1000 salts you generated? All random? Did you check if they'd give you the user's password after "decryption"? Nope.

So since there's no way to get the "right salt" for each user ID, the easiest solution is to force a password reset across users. The next time they login everything will automatically fall into place.

Incremental code review - MD5 hashes

This one is a reasonably obvious tip to be frank. I was recently doing a code review retest for a Java app. Now I don't know too much Java so I was finding it hard stepping through code.

One thing I knew though was that if you have the previous code base and the current one and are "re-testing" it's helpful to see which files have changed. Now anyone with a little Linux experience or programming experience will immediately say 'diff'. And yeah..diff is fine..but that will give you a very detailed listing in a slightly cryptic form. Its readable enough if you go slow, but it's not the first step IMO. I'd like a slightly more high level view first. That's how I stumpled upon md5deep.

So I go into the first root directory of the old code and run md5deep -rl > old_list there. Then I change directories to the new code and run md5deep -rl -X old_list > changes over here. Basically all it means is that I compared the new list against the old. Once I have my changes, I know that any fixes they made MUST be in some of those files.

Now I can run diff on each of those file combinations to search a little bit slowly. It's the same really..but it gives me a little more control over the process.

A tip here to further reduce changes is to use md5deep with grep to filter your results out. So I knew I was looking only for java file changes...so I could either do something like:

md5deep -rl -X old_list| egrep -i '.java$'

OR

md5deep -rl * -X ~/list_md5_old |egrep -v ".doc$|.DS_Store|.js|xml|changed_files|hibernate" > changed_files;wc -l changed_files

I used the 2nd one :) coz I knew what all I didn't want. If you don't know that..start with what you know and filter on from there.

There's a million ways of doing this of course; I just dropped in what I did :). Here's the blog post which saved me some time..

http://linhost.info/2010/02/checksum-a-directory-with-md5deep/