R3

Going Down the Rabbit Hole: Using Statistics to Brute Force Multi-Factor Authentication

What do cybersecurity experts chat about while most people are texting about the latest Monday Night Football game, or which shows are worth watching on Netflix this month? Well, naturally they discuss how statistically possible it is to brute force hack into multi-factor authentication security protocols.

In this blog post, we recap a recent engaging discussion between our former Director of Cybersecurity at R3, Alex Shanteau, and his peers in the cybersecurity industry, as they give-in to their morbid curiosities and dive down the rabbit hole of determining the statistic probability of brute force hacking MFA.

Will Young – Owner/Operator, Dozekar Security

Multi-factor authentication or MFA is often seen as the panacea to all authentication security concerns. However, not all MFA implementations are created equal. Many services and applications use code-based MFA that theoretically could be guessed by an attacker trying to get unauthorized access and rely on the statistical improbability of this event happening for security.

Will Young, Owner/Operator at Dozekar Security, recently found himself conducting a web application penetration test for a client and as he tested the password reset functionality of the application, he had a thought.  The password reset service asked you to supply a valid username and then would load a new page asking you for a 6-digit MFA code along with the new password you wanted to use. He noticed that the application allowed him to attempt this seemingly indefinitely.  The codes themselves would invalidate after 10 guesses, but he could simply repeat the process and request a new code and try again.

This got him thinking and, thus, Pandora’s Box was opened.

His first thought was that the potential number of combinations of a 6-digit code with digits 0-9 would be 10^6, or 10 million.  One would have 3 chances at guessing the code before it changes, then have a 10 out of 10 million chance at guessing the MFA code. While it is unlikely, one could guess the correct code, the application lets the user have infinite retries by allowing him/her to request a new code. At what point are the odds of success statistically significant that this would be considered a vulnerability in this MFA implementation?

To Wills’ own admission, it has been many years since he took a statistics class but nevertheless, he began rationalizing the numbers by considering that if he had a 10 in 10 million chance, this could also be thought of as a 1 in 1 million chances. Again, to his own admission, he “ignorantly rationalized” that if he were to attempt to guess the MFA code 1 million times it would result in at least one success. As he would find out, this is a very popular, but also very wrong way of thinking about the problem.

It was then that Will decided it was time to call in reinforcements. He reached out to former colleagues Alex Shanteau, R3, and Blake Tilghman to explain the scenario and posed the question; at what point is the probability of guessing a MFA code statistically significant enough to warrant a concern or finding?

At this point, we turn to our Director of Cybersecurity, Alex Shanteau, to explain the math in the way that only he can.

Alex Shanteau – Former Director of Cyber Security, R3

When Will posed his question to our group chat, it reminded me of when I was grinding for Baron’s mount in World of Warcraft, an obscure reference – basically, this would be tedious. There were lots of discussions about drop rates vs how many actual attempts it would take to guarantee that you would get the drop.  When I went down the rabbit hole, what I discovered was that the truth is not as straightforward as one might think, and I found the math behind it really interesting.

It’s well understood that you have a 50% chance of getting heads if you flip a coin, but how many times do you need to flip the coin to be 100% confident that you have end up with heads as a result. I referenced a bunch of work produced by people far better than my decade old knowledge of statistics me to show the guys how it works (Shoutout to this article).

At a basic level we are attempting to get the odds that you haven’t landed on heads as low as possible.  If you flip the coin twice, you have 50% chance of getting heads both times, ½ * ½ = 1/4 or a 25% chance you haven’t landed on heads, if you subtract that from 100% you end up with a 75% chance you HAVE landed on heads.  If you play that out for a few iterations:

  • 3 times (1/2*1/2*1/2 = 1/8 (12.5%) or 87.5% chance of success
  • 4 times (1/2*1/2*1/2*1/2 = 1/16 (6.25%) or 93.75% chance of success
  • And so on…

What I realized was that this concept could be applied to brute forcing MFA, what is brute forcing other than rolling a big die with hundreds of thousands of sides?

To take a more realistic data set for brute forcing, how likely is that a one in a million chance is successful within one million tries?

If those are the odds, then 999,999 times out of a million you would be wrong. If you take those odds and put them to the power of 100,000 you get the odds of it not happening at all or (999,999/1000000) ^1000000 = 0.3678, meaning that from there you can subtract that from one to get the odds of it happening at least once and you get 0.6321, or a 63.21% chance of it succeeding at least once.

The baseline formula for this is probability of an event never happening in a given and attempt set = (1- 1/n)^n. We then must take it one step further, most MFA codes aren’t invalidated after a single attempt but instead usually allow you to try some number of them before you have to do another reset.

What all of that boils down to is this formula:

1 – ((1 -( 1 / c )) ^ a*b )

  • A = number of times you attempt to guess a code
  • B = number of tries you get before the code resets
  • C = the number of outcomes in the dataset (for example 000000 to 999999 would have a million possible combinations.

With me being pretty sure I had convinced the guys that I wasn’t crazy, our good friend Blake decided that wasn’t good enough and took it to the next level.

Blake Tilghman – Security Consultant

As much as this idea had already evolved, manually doing the math each time didn’t seem very fun or intuitive. I decided to use my limited knowledge of creating web applications in personal projects to make a web interface to help with this. The site has three inputs, one for each variable in the formula above. Once the submit button is clicked, the server will return the result back to the user in the form of the chance of the attack succeeding in percentage. The goal of this web application is to enable people to test these probabilities against their own applications and MFA implementations.

Ultimately, the decision of levels of security is up to individual companies to decide what restrictions make sense for business needs. Notably, MFA is not the only option for security. Other controls such as IP filtering, rate limiting, etc. are not discussed in this article. The best solution will always be a combination of controls. No one control will, or should, be an “end-all be-all” solution. This should simply be considered as another data point for decision making. Our hope is that this project will make these decisions easier and more tangible to those who oversee them.

Going Down the Rabbit Hole: Using Statistics to Brute Force Multi-Factor Authentication