Behind the 6-digit code: Building HOTP and TOTP from scratch | Hacker News Reader

Behind the 6-digit code: Building HOTP and TOTP from scratch

blog.dogac.dev

250 pointsdogacel74 comments

Six-digit verification codes for something like a "forgot password" flow are OTPs -- they're only good for one login -- but they are not HOTP/TOTPs. HOTP/TOTP has a registration step, where you copy a server-generated secret to your phone through a QR-code-encoded otpauth:// URI (https://github.com/google/google-authenticator/wiki/Key-Uri-...). That doesn't happen in a "forgot password" flow.

Incidentally, if you think of TOTP as being HMAC(unix mod 30, secret), one idea would be to do public key crypto instead of symmetric HMAC stuff. That's basically what a security key is.

If you additionally made it so that you couldn't phish the security key -- by having the OS + web browser know which apps can ask for which security keys -- you'd have reinvented WebAuthn.

P.S.: Make you sure you have stuffing protection in place against these kinds of six-digit-code auth schemes. A million possibilities is often acceptable for a secondary factor, but it's useless if attackers can just try all million codes.

Since they're in the thread, nice article 'dogacel! I've never seen an article on this that also took the time to dig into HMAC internals and that gnarly DT function.

All very valuable comments! Actually I had a small edit on the "forget password" flow.

I agree that an asymmetric key makes much sense. Secret key can be left at the user device while server only contains the public key. That sounds much more secure. I will dig deeper!

True about the stuffing proteciton, I actually want to do further reading on how TOTP is secured from random attacks. Statistically you are expected to crack 1 account in every 1 million attempts in 6 digits codes. Those numbers look pretty huge in the context of security, and a bot-net can potentially brute force couple hundred accounts every day.

> HOTP/TOTP has a registration step, where you copy a server-generated secret to your phone through a QR-code-encoded otpauth:// URI

RFC4226 and RFC6238 do not specify anything but the actual algorithm(s), which is exactly what OP implemented.

And many actual implementations work the other way around. Which opens the user to credential compromise but is much better user experience (and only one possible with several kinds of hardware tokens).

Doing similar idea with asymetric cryptography is problematic due to the size of messages involved that are not exactly convenient to type. Lower bound for the signature size is going to be something on the order of 128bits if we include "weird" signature algorithms (ie. string that looks like MS Product Key), 240b for Schnorr with safe-ish parameters, at least 512b for anything widely accepted.

You can probably come up with something related to S/KEY (which was kind of a precursor to HOTP) that can be made to work with arbitrary sized one time passwords and is technically asymetric (and quantum resistant at that), but the security trade-offs involved in that and somewhat wild user registration step of S/KEY make HOTP/TOTP more sane choice.

Incidentally, if you think of TOTP as being HMAC(unix mod 30, secret), one idea would be to do public key crypto instead of symmetric HMAC stuff. That's basically what a security key is.

If you additionally made it so that you couldn't phish the security key -- by having the OS + web browser know which apps can ask for which security keys -- you'd have reinvented WebAuthn.

Another key part of FIDO2 phishing protection is challenge-response. The relying party sends some random material/nonce that the authenticator has to sign. This avoids replay attacks that e.g. a time-based method would have, since when a phisher tries to authenticate, the RP will send a different nonce and the phisher cannot sign it.

It is a bit terse, but there is a 20-line Python implementation which cleared up the ideas for me: https://github.com/susam/mintotp

I love this one. The neat thing about TOTP is that while the algorithm itself is simple, the algorithms it depends on are also relatively simple, at least for cryptography. For HMAC you just need SHA1, and that can be implemented relatively easily without much more code. As a learning exercise it's quite good.

It is even shorter without boilerplates:

    def hotp(key, counter, digits=6, digest='sha1'):
        key = base64.b32decode(key.upper() + '=' * ((8 - len(key)) % 8))
        counter = struct.pack('>Q', counter)
        mac = hmac.new(key, counter, digest).digest()
        offset = mac[-1] & 0x0f
        binary = struct.unpack('>L', mac[offset:offset+4])[0] & 0x7fffffff
        return str(binary)[-digits:].zfill(digits)
    
    def totp(key, time_step=30, digits=6, digest='sha1'):
        return hotp(key, int(time.time() / time_step), digits, digest)

Ever so slightly easier to read (IMO) if you inline arguments:

    def hotp(key: bytes, counter: int, digits: int = 6, digest: Literal["sha1", "sha256", "sha512"] = "sha1"):
        mac = hmac.digest(
            key=base64.b32decode(key.upper() + "=" * ((8 - len(key)) % 8)),
            msg=struct.pack(">Q", counter),
            digest=digest,
        )
        offset = mac[-1] & 0x0F
        binary: int = struct.unpack(">L", mac[offset : offset + 4])[0] & 0x7FFFFFFF
        return str(binary)[-digits:].zfill(digits)

And Pyright doesn’t yell at this version because no type-changing variables here: https://basedpyright.com/?typeCheckingMode=all&code=JYWwDg9g...

---

This is actually really helpful. I’m using Pass [1], which requires oathtool for OTP support [2]. I’m currently on a Mac without admin rights (so no Homebrew for me), and compiling oathtool is a PITA. I’ve wanted to put together a pure Python replacement for a while now, but with this it can be a single-file script: https://gist.github.com/notpushkin/7ac32ddf35a0c73bc6f181a1b...

[1]: https://www.passwordstore.org/

[2]: https://github.com/tadfisher/pass-otp#requirements

Why not do an integer division?

Those `>Q` and `>L` just make it more confusing for me, they just feel like a different language in the language...

Perhaps you could contribute a version in a language that uses more descriptive names, something like BitPacker.WriteInt64 for >Q if I'm guessing correctly what that means (I'd equally need to check the docs to know what format these letters represent, but I don't find it too confusing when you know it's simply some binary / byte array version of the same thing)

They are well documented and essentially are a DSL with the Python struct module for specifying memory representations of packed structures.

https://docs.python.org/3/library/struct.html#format-charact...

I adapted code for Java back in the day from here: https://github.com/j256/two-factor-auth/blob/master/src/main...

A bit longer but most of it is just boilerplate Java stuff to deal with polymorphism and a base32 implementation. I recall, stripping most of that away in our internal adapted version of that.

Key points:

- generate a 16 character base32 secret and stuff it in a totp link. otpauth://totp/Alice:alice@example.com?secret=JBSWY3DPEHPK3PXP&issuer=Alice

- stuff that in a QR code and show it to the user so they point their phone authenticator app at it to store the secret. We used a js library for this.

- store the secret with the user account in a secure way (we used aes encryption for this)

- when verifying, use the secret, a timestamp in seconds after the epoch divided by 30 (simple normalization step applied on the client as well) and use the user provided number to construct a sha1 hmac and grab the last digits and prepend with zeros. The calculated string should be the same as what the user typed from their token app as long as their clock is in sync.

- we actually implemented a grace period by calculating the before and after code as well so the user isn't screwed over if the number rotates while they were tapping out the code.

While relatively easy to implement, we ran into a lot of friction rolling this out to normal users. Basically non technical people find this stuff super confusing and we had to hand hold quite a few people through the process and we also had to deal with people that lost their secret, or kept on using the wrong code (for a different account). The UX of this stuff is just terrible. Be prepared to deal with a lot of support overhead if you choose to roll this out. A non trivial percentage of users will manage to lock themselves out of their accounts.

> Also in some examples like Facebook's password recovery, this secret clock is not shared with the user directly but rather server's generated one-time password is sent via a trusted medium, such as an email to the user.

I’m pretty sure Facebook just makes up a random number and stores it?

Yes if you’re sending the number to the user, might as well just be random that’s a lot easier.

Clocks and secrets only needed if the user is providing a number generated on the remote side.

Good catch. In my mind storing that random number is similar to storing a plain-text password, thus I thought they were generating TOTPs. Let's hear from others how they implemented it.

It would be, but you could still store an expiration time, and limit the number of attempts to use the code. Considering you're probably sending it to the user insecurely anyway (via email or text message), that's probably safe enough.

Thanks for all your insights, I have updated the post to outline this as a "theoretical" use-case rather than a practical one. I also revised it to include random number approach.

Perhaps you could also highlight how in usual TOTP implementations (“scan this code with your authenticator app”) there’s no channel to MITM? I think it’s one of the key pros of TOTP vs, say, SMS as a second factor.

I haven't mentioned MITM attacks in this article thoroughly. Can you give some examples on what authentication implementations carry a MITM risk?

I thought anything carried over SSL doesn't have a _significant_ MITM risk.

Not sure about emails (probably reasonably secure, I think most MTAs use TLS now).

For text message codes though, there’s plenty of attacks. In authoritarian regimes, government can monitor your text messages directly – I think some protestors in Belarus have lost their Telegram accounts due to this. There’s also the SIM swapping attack, where an attacker pretends to be you and ports out your number: https://en.wikipedia.org/wiki/SIM_swap_scam

> > storing that random number is similar to storing a plain-text password

> you could still store an expiration time, and limit the number of attempts to use the code

Storing plain-text passwords is bad because:

1. Users re-use passwords

2. An attacker can read the access token from the database (as with SQL injection) or capture it in transit (as on insecure connections) and log in directly (if that is still useful when having, e.g., SQL-injection-based database access)

I do not understand what threat limiting the number of attempts protects against. Even if you have that limit implemented on a hardware level, the attacker either knows the right code or can crack the hash if it's a hash of just a few digits. With something like PAKE you can protect against capturing in transit but on secure channels (e.g., if you already use TLS) that's typically overkill

(Of course, you absolutely need to have rate limiting on OTPs, but that is not to protect against the correct code being read straight from disk by the attacker; it's to protect from guessing the digits, a surprisingly common flaw)

> you're probably sending it to the user insecurely anyway (via email or text message)

(I kind of want to remark about this assumed insecurity: the user needs to be targeted for these to not be adequate. Attackers very rarely go after people to the point where they first compromise an email inbox and then look for your specific service, or drive up to the person with cell tower spoofing equipment. It surely happens in red teaming exercises, spy scenarios, if you have a stalker, and probably more, but it's not the common case. Anyway...)

I don't see how rate limiting and expiration helps against sending it via moderately-secure media either. This is necessarily plain text for random codes because the user would otherwise need a decryption key and then you're basically back at the TOTP scenario makes a difference for at-rest storage security. So with them being plain text, if someone is intercepting your SMSes or sitting in your inbox, they'll either manually trigger the code sending or wait for the legitimate user to do this and then log in. Similar to the previous bit: sure, the security of the transport method is relevant, but not for the security of token storage on the server

So you are right that the random number becomes "password-like", but of course if you really care about that you don't need to store the exact random number, just as you don't have to store a raw password.

However, if your random login code is easily typable then it's usually drawn from a small enough keyspace that any such code is trivially brute-forceable. Like if it's decimal digits you need more than ten.

So in practice people just trust that you are on good terms with your email provider and anyone else with access to your email, and use other mechanisms to limit access to these codes from insiders.

I have to pull a number from Google Authenticator to log into my FB account so I can only assume they're not simply generating random numbers.

But they’re not sending you this number via email.

Correct. Before they killed mbasic the prompt said they would text me a code, but in reality they were prompting for a TOTP code.

Two different flows, an online and an offline.

TOTP devices can be powered offline, which makes it extra secure, as you don't transfer any data around, possibility of leaking it is extremely low.

Random numbers could only work in online flow, where server sends you a one-time code using a secure communication method, such as a trusted phone number or email address.

What's the difference between storing a random number and storing the OTP secret? It's all ones and zeroes in a database

If you store the OTP secret in an HSM, then you can do the same when generating a random number. I'm not aware of anyone actually doing that though (I surely won't have seen even 1% of what's out there, but as a security consultant I get around at least a little bit)

The number is random, so there's no need to worry about plain storage.

Facebook's login/account recovery codes are not TOTP/HOTP, but are random numbers. Also, the author struggled to check their implementation. One can easily compare an implementation of many websites by grabbing the QR codes they use for login and importing into your favorite authenticator app and also decoding the QR code to get the secret. In theory your code should produce the same codes at the same time as the app.

Hi,

> Also, the author struggled to check their implementation. One can easily compare an implementation of many websites by grabbing the QR codes they use for login and importing into your favorite authenticator app and also decoding the QR code to get the secret.

Can you clarify this? It's been some time since I have written the code, AFAIK it was working fine. Did you see any discrepencies when you tested the implementation against a real authenticator app?

I was responding to the statement at the bottom of the article: "however I have struggled to find a website that help me check my implementation as their secret-key representations were not standardized. Thus, I have published my own short demo app to showcase." The Google Authenticator QR codes end up being a fairly standardized secret key representation.

Even though QR codes are standardized, the original RFCs do not use QR codes. That's what I tried to mean, you can't find apps that use plain-text secrets.

Both RFC:s have test vectors you can use to write tests as well.

Well I started reading, but then the page was blurred and blocked by a popup, so I only made it about a third down.

A simple click on a random place on screen should discard it. I wanted to connect with my readers so I have added that subscribe popup recently. As I have figured nobody subscribed to my newsletter yet :(

Let me know if it doesn't work. Also would be glad if you can give browser / platform.

I figured it out, but why not at least put an x to close in a corner so it behaves something like a normal popup?

Personally, I'm never going to subscribe to any newsletter ever. If I like someones content enough, I might bookmark the page or subscribe via RSS. However, currently the page rudely interrupts before I've even finished reading. I've (probably) never visited your site before. I don't know if I like the content or not. If I reach the bottom of the page, there's fair chance I might. A notice at the bottom like "If you liked this, maybe you'll like my newsletter". It's far less disruptive and way more polite.

I hated popups in the 90's, same as I do now. It's an immediate bounce for me.

>browser / platform

Vivaldi / Linux (Debian)

I see, I have removed the popup.

I also don't use email subscriptions, unless it is my favorite person. But I don't know how many of them are subscribed via RSS.

Very helpful article. I recently went down the TOTP rabbit hole and this article would have been great.

I run a suite of servers and setup scripts that go with them. I can create users and secret keys easily enough using our APIs, but I needed a way to generate TOTP codes on the fly. I got it working on my machine, but sharing it with others was a bit difficult because really the only "logic" was generating the secrets while everything else was static data and storing responses from the APIs.

I ended up making my own API to generate TOTP codes from secrets, <https://totpapi.com>. I try to make it clear it should only be used for testing, but it makes this kind of thing much easier for me. Maybe it will help someone else as well. :)

Another post which describes the TOTP concisely - https://drewdevault.com/2022/10/18/TOTP-is-easy.html

Nice. I recommend RFC 4226 and RFC 6238 for those wanting to get their feet wet in reading RFCs and other specifications; they were the first RFCs I implemented (with others), and one of the first Rust projects I worked on.

I always thought it odd that companies would spend so much money on services like Symantec VIP, with their proprietary BS and high costs, when someone could implement TOTP in 15 minutes as an internal service.

It's a little more complicated now with push notifications and more complex flows, but for generic TOTP?

Agree and disagree,

Deciding on how to store the credentials is still a hard task. Even storing the secret. Ideally it shouldn't stay as a plain text in your database. If you use cloud, something like KMS can be used for additional security. Also you should still consider replay attacks, rate limits etc.

I agree in the sense that TOTP is hard to implement, no it is not. I hope this article helped people understand how TOTP works.

A while back I created a fallback for use from my dotfiles that can be used from the command line: https://github.com/gbraad-dotfiles/upstream/blob/02deb3ef922... using zsh, openssl and xxd

This is not the first attempt I made. That was about 11 years ago with https://github.com/gbraad-apps/gauth using JavaScript as an application that would work on a Nokia Symbian/Maemo phone and as a webapp.

And I put it like this https://medium.com/@thatkid02/javascript-2-factor-authentica...

It's often a good idea to set up TOTP on accounts just because they may treat you differently due to having 2FA enabled. It would be harder to lose a gmail account to their "security" systems if you add TOTP to it for example. In the case of gmail adding it is a hassle involving devtools to emulate a hardware key first then add TOTP and then delete the hardware 2FA.

Some password managers such as KeepassXC have TOTP incorporated into them and you can have it available right next to the password. It may defeat the purpose of 2FA under some assumptions.

I personally use 1Password with hardware keys where possible.

> It may defeat the purpose of 2FA

True, I think this as a mid-step of smooth transition from plain-text passwords to secure keys. You kinda get the benefit of both.

Also those apps are secured much better than a traditional password manager as browser auto-fill for example.

> I think this as a mid-step of smooth transition from plain-text passwords to secure keys.

This is not what I meant. Storing the TOTP next to the password means you don't really have 2FA as it's a single point of failure. Still better than nothing especially when the objective is what I stated in the first paragraph.

I implemented TOTP as a command line app doing lookup and generation by pulling secrets from a locally encrypted password file.

And before someone asks, the decrypt key is only stored in my head and the app fails silently after a significant delay if the decrypt fails.

What I don't get is how HOTP is anything but a fail waiting to happen if used across an unreliable network. Maybe this explains why I have yet to encounter a real world deployment of HOTP.

In my experience HOTP works fine, why not. The real world deployment is a replacement for sms otp.

https://github.com/pcarrier/gauth

Thanks for the read, I learnt something about HOTP/TOTP today.

I would like to know why the clocks are all weird though - the numbers aren't in the right places. Were the images in this blog post "AI" generated?

Nope not AI generated, I have used excalidraw. Only the cover page is AI generated.

Clock drawing was an asset, I didn't really spent time trying to match the time on clock to the time mentioned by the actors.

> Like the traditional password authentication approach, the user and the authority (server) still needs to agree on a common secret key.

Not sure what you mean by this, the server checks the hashed version of the password.

Hashing is done before storing the secret on the server side. Therefore they still need to communicate regarding the intial secret.

On a side note, does anyone know why banks still rely on sms 2fa codes instead of TOTP? Is there some regulatory issue that makes it more difficult?

Everybody with a phone has SMS baked in. SMS also has a recovery process if you drop your phone in the toilet. Ultimately, this improved user experience outweighs the security benefit to TOTP for many organizations.

TOTP also doesn't stop the biggest threat that SMS faces: phishing. Saving you from sim-swap attacks is just not a particular huge increase in security posture.

My bank at least offers TOTP as an option, but the huge majority of people are going to enroll with SMS.

My two banks require additional approval via push notification to the phone app. No SMS involved.

(In France.)

Some banks in Switzerland give customers a device that generates TOTP codes.

What is it with modern web design... can't even read a third of the page, and they already want my email to subscribe...

Clicking anywhere else discards it.

I have removed the popup anyway, seems like most people don't like it.

here's my small totp generator i use written in perl

https://git.ceux.org/totp-perl.git/tree/totp.pl

What is HMAC i still dont understand this part? Is it RSA encrytion?

No, RSA is asymetric, where it has a public/private key pair.

HMAC is symetric, it only has a secret and it can be used to hash values one-way.

yep, it is just couple lines of code and nice math behind it

Reply on news.ycombinator.com