TOTP Token - Calculated Timestamp Incorrect

[danieldjewell]

Hallo Leute!

I believe there is a problem with the correct calculation of the value for TOTP tokens that is causing intermittent issues with authentication.

The issue appears to originate in the "token time" calculation.

Overview

Specifically, https://github.com/LinOTP/LinOTP/blob/5c7d71634d61d2751fb7de5a02a9fd26ed6c9d87/linotpd/src/linotp/tokens/totptoken.py#L445 which calls https://github.com/LinOTP/LinOTP/blob/5c7d71634d61d2751fb7de5a02a9fd26ed6c9d87/linotpd/src/linotp/tokens/totptoken.py#L320-L323

An example result from this calculation is logged as:

... [checkOTP] timestep: 30, timeWindow: 30, timeShift: -17
... [checkOTP] timestep: 30, timeWindow: 30, timeShift: -17
... [checkOTP] last auth : datetime.datetime(2019, 2, 26, 14, 9, 15)
... [checkOTP] last auth : datetime.datetime(2019, 2, 26, 14, 9, 15)
... [checkOTP] tokentime : datetime.datetime(2019, 2, 26, 14, 26, 45)
... [checkOTP] tokentime : datetime.datetime(2019, 2, 26, 14, 26, 45)
... [checkOTP] now       : datetime.datetime(2019, 2, 26, 14, 27, 5)
... [checkOTP] now       : datetime.datetime(2019, 2, 26, 14, 27, 5)
... [checkOTP] delta     : -20.0
... [checkOTP] delta     : -20.0
... [checkOTP] the counter 51707214 matched. New shift: -20.0
... [checkOTP] the counter 51707214 matched. New shift: -20.0

As you can see, the calculated timestamp for the TOTP token increment is, in this case, showing 45 seconds -- however, this is not aligned with the timestep (e.g. at 14:26:30 or 14:27:00).

The RFC (as quoted in totptoken.py itself) indicates that a default floor function should be used to calculate this value:

https://github.com/LinOTP/LinOTP/blob/5c7d71634d61d2751fb7de5a02a9fd26ed6c9d87/linotpd/src/linotp/tokens/totptoken.py#L82-L84

Where "T" is the number of increments :

https://github.com/LinOTP/LinOTP/blob/5c7d71634d61d2751fb7de5a02a9fd26ed6c9d87/linotpd/src/linotp/tokens/totptoken.py#L74

I believe the "timeShift" calculation is hiding this problem. If my thinking is correct, the most accurate that the timeShift can calculate is +/- timeStep ...

https://github.com/LinOTP/LinOTP/blob/5c7d71634d61d2751fb7de5a02a9fd26ed6c9d87/linotpd/src/linotp/tokens/totptoken.py#L442-L458

RFC6238 - TOTP

RFC6238 Section 6 does call for resynchronization -- and it appears that the timeShift calculation is attempting to implement that. However, if I'm reading the RFC correctly, this should be calculated not in seconds of a difference but in terms of time steps (e.g. Time / timestep). ("Upon successful validation, the validation server can record the detected clock drift for the token in terms of the number of time steps. When a new OTP is received after this step, the validator can validate the OTP with the current timestamp adjusted with the recorded number of time-step clock drifts for the token." [emphasis added])

In other words, this can only correct for gross errors where the client's clock is off by a large amount and yet within the allowable window.

RFC Section 6 - Complications

I believe that this section of the RFC introduces complications/complexities:

• TOTP in itself requires that, at a minimum, the device generating the current TOTP (client) and the server be on a common time base
  • This is similar to protocols like Kerberos - Kerberos authentication will work fine if the client and server are not synchronized with actual UTC (e.g. the server and client can have a time offset of days -- as long as they have the same offset)
  • This is why, for example, in Microsoft Active Directory networks (and other Kerberos-based networks), the most important thing is for the client to be clock synchronized with the servers - and why Microsoft's concept of time on an Active Directory network relies on one server being the "master" for the entire network
• Devices that are calculating the TOTP code are often smartphones -- which are usually synchronized closely with atomic time
• The "resynchronization" as proposed by the RFC discusses the security impacts of this and the challenges.
• In summary, it's not an absolutely requried feature and, to me, it complicates things

Impacts on LinOTP

As currenly implemented, the timeStep calculation breaks tokens: The stored timeStep value allows for a token misalignment.

Consider:

##Taken from Lines ~395-425 of totptoken.py##
#Retrieval of settings, etc.
#shift = getFromTokenInfo.....
timeStepping = 30
shift = -21

## For timestamp fun, let's say the timestamp is 1551228878  =>  2019-02-27 00:54:38 00:00/UTC
## This means that the token timestamp should be: 1551228870  =>  2019-02-27 00:54:30 00:00/UTC

inow = int(time.time()) ## Current Unix Timestamp, pretend 1551228878

T0 = time.time() + shift 
## this will subtract 21 from the timestamp in this case... 
#or 1551228878 - 21 = 1551228857 
##Line 414 would completely override the calculation of the shift if the initTime were different
##if initTime != -1: T0 = int(initTime) 

counter = self._time2counter_(T0, timeStepping=timeStepping) 
## T0 will be 1551228857 and timeStepping is 30 
##
## if T0 is 1551228857
## then the Token Timestamp is = T0 - (T0 % 30)
## or Timestamp = 1551228840 ==> 2019-02-27 00:54:00 00:00/UTC 
#counter = int((T0/timeStepping) + rnd=0.5)
#or
#counter = int((1551228857/30)+0.5) 
#counter = 51707628 or 0x314feec

## HOWEVER, as noted above, 
#this is the incorrect token timestamp. 
#The token counter is 1 behind where it should be 
#because the shift has moved the token timestamp back by 21 seconds. 

## Therefore, if the *actual time* is 1551228878 (00:54:38) 
#and both the smartphone generating this is using that time 
#and the server is also using this time, 
#authentication will fail because shift has 
#interfered with getting the correct token increment

## BUT if the time were just 13 seconds later at 1551228891 (2019-02-27 00:54:51) 
#the counter would increment to the correct value of 51707629 
#Because (1551228891 + shift of -21 ) = 1551228870 = the actual token that was displayed on a phone

Summary

I have been experiencing issues where users are unable to authenticate until well into the token "window". Now, this could be caused by the _time2counter_ and _counter2time_ functions not using the floor. Again, the use of the timeStep and a larger window tends to mask this issue.

I'm thinking that removing any attempt to synchronize/offset the token in the case of a TOTP would be wise. In the least, using the proper floor time to calculate the offset would seem prudent.

(I'm trying to figure out why exactly _time2counter_ and _counter2time_ are using a multiplier of 0.5 which results in, for example, offsets at :15 seconds and :45 seconds instead of at :00 and :30 when using a window of 30 seconds... I can't see why it's doing that.)

[xt-kay]

Hi Daniel,

many thanks for your deep analysis.

I spent the last 1 1/2 days to build test cases into linotp to prove your claim. Please have a look at the latest patches in the master and try to figure out, if this matches your expectations.

But it showed up that what you wrote in your summary, the claim "TOTP Token - Calculated Timestamp Incorrect" does not match. The reason is that LinOTP does not tests a single otp, instead it verifies alway a time range of +/- 5 counters, and thus an off-by-one is okay. In the patch i removed the off-by-one and all test still stayed valid.

the reason for 0.5 is easy to explain: if you have a time this is matching to a counter by deviding the time seconds in slices. But if you start from a counter and try to figure out the seconds, the counter matches a range of 30 or 60 time slice size. Any time in this range of 30 or 60 seconds represents the same counter, thus we took the middle of the range: eg. 15 or 45. This will explain the logoutput you cited above wrt. the token time.

You are right wrt. that we should store the shift counter instead of the timestamp, I adjusted the code to stay compatible by using the reverse time slice mapped timestamp, so that it is always stores timestamps directly fitting the time slice.

While analysing the code I detected an other source for the validity problems which are more likely to cause the timing problems: The problems might be caused be the time.time() method which takes the system time:

time.time()

Return the time in seconds since the epoch as a floating point number. Note that even though
the time is always returned as a floating point number, not all systems provide time with a better precision than 1 second. While this function normally returns non-decreasing values, it can return a lower value than a previous call if the system clock has been set back between the two calls.

This describes that the time.time() method is related to the system time, which could different to the network time datetime.utcnow() which derived from the network time (at least this is my assumption)

So in summary: thanks for your analysis - which inspired me to some tests and patches but which showed that your claim could not be verified. Anyhow the re-reading of the code, which is now mor than 5 years old, inspired for a new idea to tackle the timeshift totp token problem.

Best regards,

    Kay