Number Theory Attack On Two factor Authentication research

What you are about to read is research that at this point has only been proven on paper repeatedly over a thousand times and has had the support of being peer reviewed countless times, with no one being able to disprove it in the last two years. Why did we make this research public? What are we claiming? We made it public to see if people can take it from paper to proof of concept or if they can take it from paper to disproven or a proven proof of concept.  So what we are claiming is simple, we were able to know which  TOTP token would be generated, because of a flaw in the TOTP, which seems to originate in the underlying sha-1 with a potential number theory attack. This has been peer reviewed  by Mr. Edwards, also known as @Lojikil, who came to that conclusion.  We are adding in more clarification to help those reviewing it.

Our TOTP  research that lead to a potential number theory attack. Our research  has been wanted to be seen by the information security community for sometime and has passed all peer reviews it’s been through, so we are confident in sharing it. We are more focused on the accuracy of this article, then trying to make it easy to understand for the average user in this post.

If you pass data through sha-1 you are hashing that data, so by design you aren’t supposed to be able to accurately guess or discover what the actual message is by tampering with the hash. 2fa uses TOTP which if you dig deep enough into TOTP it uses sha-1 and TOTP only uses the last four bytes of each hash plus the time of the users computer.  We haven’t been able to get enough power to automate the process to prove the number theory attack that leads to being able to crack 2fa and we have to account for the possibility that Google may have patched without informing or paying us, but this effects all 2fa implementations, so please take Google 2fa responses with a grain of salt. The reason we say this is because we reported the bug to Google and they’ve patched issues while saying they won’t in the past, so we currently distrust their public bounty program.

Since our research passed peer review, we are now putting out for the entire information security community to review, so without any further delay, let’s get to it. Please note, that we will be explaining everything that took place.

 

when researching the TOTP tokens in two factor authentication,  their are only six digits long and only consists of numeric values, except for one rare instance where it was alphanumeric.

We  figured out what  the next TOTP  token would most likely be before it is ever sent and doesn’t require any user interaction nor does it require having access to any device. When analyzing the numbers  generated  by the TOTP token we noticed they weren’t even  close to random.  Per our research, the  TOTP generator numbers  can be cracked because, while they may take a lot of code to generate a TOTP token,  it only takes  0,1,2, and 3 and is also allowed to use one decimal that is either .1 .2 or .3 using our number theory attack against it.

The above statement has been misinterpeted by a researcher who thought we were claiming a 1 can’t be followed by an eight. That is indeed possible in two different ways. One we do not claim that the last number is used to create the next number, our claim is pretty clear. You could use 2.333 * 3.333 to get roughly to eight, which then appears to be rounded up to 8 by the code.

When 2fa is enabled one code is given per minute in google authenticator which google says to use. This means you  have 60 seconds to create a collision , so the computational power needed to crack it within sixty seconds is a lot. If you would like to peer review a bunch  of very old TOTP tokens , you can at the bottom of this post along with an explanation on the math formula used to generate each number.

 

We do not know if our research expands into all sha-1, since this is still on paper research, despite the extensive review of it.  This is a number theory  attack that in this instance is targeting the TOTP and the underlying sha-1, thus making 2fa tokens insecure if this is indeed proven to be correct in a working proof of concept. Currently in theory, it hasn’t been disproven. It would take a lot of  power to generate an accurate 2fa token in under sixty seconds, which is the amount of time you have with Google’s utilization of the TOTP.  Google believes their security is good enough and negated the severity of our research due to the amount of computational power it would take to create a number theory attack with a six digit 2fa number in under sixty seconds.

 

So, what does this mean to the average person? If this is proven, 2fa is indeed broken and anyone can create their own valid 2fa tokens. The reason we are going public with this, is because we want security improvements to sha-1 to better protect the end user, and we are doing our best to be transparent with the information security community.

Here are just a few tokens that we’ve proven the math to, but we’ve repeated this process a thousand times.
672704

Now let’s break down the math to recreate the token 672704

6+1=7

7 divided by 3.3 2

2 times 3.3 = 7

7 times 0 = 0

2+2 = 4 or you could also do 7 – 3 = 4

Now you are going to have noticed that there is an abnormality in the math for the 4? What is that abnormality? It doesn’t use the last number to generate the new number and the reasoning behind this seems straight forward to us, but for those who are looking at this for the first time, here is the explanation. Once you hit 0, you can’t create the next number, unless you use the number, in this case 7 that created the 0 or it potentially may have to start from scratch, however we have yet to encounter that. We provided the math for 4 using 2+2 which jumps back two numbers to the 2 before the 7  or simply reusing the number that created the 0, which in this case is 7.

Now let’s do this one more time before you just go through all the math on your own. Here is the token 433034

4-1=3

3-0=3

3-3=0

0+3=3

3+1=4

It follows the same pattern as the last token, so let’s do it again for redundancy sake with 500349

3 + 2 = 5

5 * 0= 0

0 * 0 = 0

Now, we go back to the only valid number like before, which is 5.

5 – 2 = 3

3 + 1 = 4

4 * 2.3 = 9.2 which is rounded down to 9.

Now, let’s look at the underlying math that can be applied to each number to crack it.  We look forward to any type of criticism.

Now, let’s break down our math, so it’s easier to digest. 2*3 equals six 3*2.3 =  a rounded down 7  7+1=8 6+3=9 and so on. We were exhausted by all our research and in very rare instances we use x as a place holder, since we didn’t spend much time on that number. You can do all the work on this research as you want. What follows are tokens broken down into the math uses to create them

2*3=6 3*2.3=7 7+1=8 6+3=9 9*0=0
8 / 2.3 = 3 2+2=4 5+0=5 2 *3.3=7 4*2=8 3*3=9

1+2=3 4+0=4 5/1=5 5*1.3=8 4*2.3=9
5-2=3 8/2=4 6+2=8

7 / 3 = 2 7 divided by 2.3=3 9/2.2=4 9-1=8

0+1=1 9/3.3=2 6-3=3

1+1=2 4-1=3
3-2=1 2+0=2 1+2=3
2-1=1 8/3.3=2 9 divided by 3=3

9 modulo 2=1 3+0=3

9-3.3=5
446055 4+0=4 4+2=6 6*0=0 5 5+0=5
278888 2 * 3.3=7 7+1=8 8+0=8 8+0=8 8+0=8
410106 4-3=1 1*0=0 0+1=1 1*0=0 6
793700 7+2=9 9 divided by 3=3 3 times 2.3=7 7*0=0 0*0=0
208789 2*0=0 x=8 7+1=8 8+1=9
012124 0+1=1 1+1=2 2-1=1 1+1=2 2+2=4
768646 7-1=6 6+2=8 8-2=6 6-2=4 4+2=6
269109 2*3=6 6+3=9 8 modulo 2=1 1-1=0 9
182458 8/3.3=2 2+2=4 4+1=5 5+3=8
505491 5*0=0 5-1=4 4*2.3=9 9 modulo 2=1
770653 7+0=7 7*0=0 6-1=5 5-2=3
795155 7+2=9 9-3.3=5 5/1=5 5+0=5
657034 6-1=5 5+2=7 7*0=0 0+3=3 3+1=4
533718 5-2=3 3+0=3 3 3*2.3=7 modulo 2=1 8
854176 8-3=5 5-1=4 4-3=1 x=7 7-1=6
831309 8 divided by 2.3 = 3 3-2=1 1+2=3 3*0=0 9
320686 3-1=2 2*0=0 6+2=8 8-2=6
069834 6+3=9 9-1=8 8 divided by 2.3 = 3 3+1=4
343546 3+1=4 4-1=3 3+2=5 5-1=4 4+2=6
671395 6+1=7 7 divided by 2.2=3 3 times 3=9 9*0=0
730796 7 divided by 2.3=3 3*0=0 7+2=9 9-3=6
445720 4+0=4 4+1=5 5+2=7 7 divided by 3=2 22=0
739794 7 divided by 2.3 = 3 3*3=9 9-2=7 7+2=9 9 divided by 2.2=4
085745 8-3=5 5+2=7 7-3=4 4+1=5

Don’t miss out on our security tips!

We don’t spam! Read our privacy policy for more info.