Don't Play With The Odds: How The Birthday Paradox Hit Us While Coding Solid - Solid

-->

Imagine a classroom full of students. How many students does it take so that we reach a 50% probability that 2 of them share the same birthday? There are 365 days in a year, and we’re looking for a 50% probability, then it must be 365/2 = ~182 students, right? Not even close! It actually only takes 23 students. This is known as the birthday paradox. The principle extends further: when considering a class of 70, the probability jumps to 99.9% for two students to share the same birthday.

While coding Solid, we faced the same paradox. Only, instead of 23 students, we were hosting 150k meetings. Shortened SHA1s hashes were the culprit. If you’re using hashes too in your code, you may find yourself in the same situation. Let’s dig a little deeper for you…

The setup - How and why we use SHA1s on Wisembly and Solid

Wisembly is an app to plan, manage and follow up on large-scale meetings. Typically, these don’t happen every day for our clients, so we deal with significantly less meetings than with Solid, which connects to each users’ calendar and manages a lot more meetings per users.

For Wisembly, we use hashes with 7 alphanumeric characters ([a-zA-Z0-9]{7}) for every object we handle through our API, and they are unique inside a meeting namespace (unicity constraint for the couple {meeting, hash} meaning that we could handle having two similar hashes but in different meetings)

As for us, we have unique auto-increment IDs that we use internally. These hashes are used externally by our app and our api to obfuscate internal incremental IDs and so have to be unique inside each meeting we manage. They’re generated by our javascript application and given to our API that has strong MySQL unicity constraint behind it.

We never had a single collision in 5 years of running with this system, mainly because these hashes live among others hashes in small series (we handle 3k to 5k objects maximum by meeting for the largest data sets). This leads to a 0.000001 % chance to have a collision

Solid is a new product, built on a new javascript framework for us. Yet, it shares its API and its backend with Wisembly. There’s only one main difference: because this time we handled remote objects we did not directly create and have already an ID in their own referential (which differs between a provider to another and are not consistent), we decided to normalize them by doing an injective SHA1 hashing pass on them and take the 7 first characters as hash, like git does with its short commit hashes. We ended then with hashes for Solid meetings that were 7 hexadecimal characters ([a-f0-9]{7}).

Doing so, these hashes would fit our backend API requirement which expects them to be 7 alphanumeric digits, and the world was pretty happy with it.

Meetings are referred to by these hashes in the URL, but we strictly check under our applicative security firewall that you are logged in and figure in the attendees list to show you the sensitive content. So, if you’re trying to access a meeting you don’t belong to, for example if a friend directly gave you the link, we’ll show you an error instead, and we’ll keep you out of the meeting.

Keep out, creeper, this meeting isn’t yours!<br>To sum up, the main differences with Wisembly are:

- Like we saw just before, hexadecimal hashes offer a way smaller number of possibilities than with alphanumeric hashes.

- All the meetings’ hashes lives in the same dataset, not namespaced by meeting anymore like we could do in Wisembly

=> The dataset is much, much bigger

- All the meetings are persisted into Redis’ cache to minimize API exchanges with Google and Office 365, before being persisted definitely into MySQL in a relational state when content / modification is done on the Solid side. Indeed, there’s no need to overload our databases with meetings that didn’t go through Solid.

=> We did not perform a unicity constraint check on hashes in Redis keys, unlike we did for MySQL.

It means that if two users have a different meeting on their respective calendar that share the same 7 first digits of their “unique” HMAC-SHA1 generated hash, when Solid syncs with one user’s calendar, it stores the data into Redis, overwriting the other user’s already synced meeting. And it does so over and over again each time one syncs his or her calendar with Solid and put it in Redis’ cache. Which happens a lot.

Never having had a single collision on Wisembly, we were pretty confident this would never happen on Solid either. We also looked at our git repositories. Like you probably do, we have an awful lot of commits, which means we have tons of 7-char short hashes. And we never had any problem with it. There are ([a-f, 0-9]) 16^6) = 17 Million possibilities for our meetings’ hashes. Surely, it would be a long time before we handled so many meetings on Solid! So we thought we were fine…

SPOILER ALERT: WE WEREN’T FINE. Soon enough,...