RFC6238 TOTP implementation in pure PostgreSQL(github.com)
github.com
RFC6238 TOTP implementation in pure PostgreSQL
https://github.com/pyramation/totp
7 comments
Yeah, timing attacks on string comparison are surprisingly easy, at least if the token/MAC has password-like entropy, not passphrase-like.
To clarify:
The boundary is somewhere around 70 bits where a significant financial incentive or considerable discretionary spending will be required to mount a successful attack.
To clarify:
The boundary is somewhere around 70 bits where a significant financial incentive or considerable discretionary spending will be required to mount a successful attack.
Thanks of the tips!
the random() seems easily addressable with pgcrypto, but do you have any information or practical examples of how a timing attack would be mitigated here? It seems that speakeasy (a JS lib) or any TOTP that uses '=' to compare would have this issue... what else are you supposed to do?
the random() seems easily addressable with pgcrypto, but do you have any information or practical examples of how a timing attack would be mitigated here? It seems that speakeasy (a JS lib) or any TOTP that uses '=' to compare would have this issue... what else are you supposed to do?
Yes, using '=' for comparing secrets is a common mistake in many implementations. The right thing to do would be to implement a string comparison function that always takes the same amount of time to complete regardless of whether the two input strings match or do not match or where they mismatch.
See https://security.stackexchange.com/a/83671 for some code examples that accomplish this by using the bitwise XOR operator to compare two corresponding bytes from both inputs and bitwise OR operator to accumulate the comparison results. As per my professional experience, this is a common pattern used in security-related code.
See https://security.stackexchange.com/a/83671 for some code examples that accomplish this by using the bitwise XOR operator to compare two corresponding bytes from both inputs and bitwise OR operator to accumulate the comparison results. As per my professional experience, this is a common pattern used in security-related code.
ok thank you! I just saw this. Adding a reference to the issue. Thanks ;)
I'm not an expert in timing attacks, but isn't this if we were doing equality on something like the secret? Not the TOTP value (which changes every interval)?
The TOTP too is a secret between the client (usually a human user) and the server. After all, it is used to gain access to another system, so if an attacker can guess the TOTP then the security of the system is compromised.
Consider the following example. The TOTP value to log into a system at a given time is 27182. Only the client and the server know this because they share the same secret key from which the TOTP values are generated. Now assume an attacker that can send arbitrary TOTPs to the system and has access to reliable timing information about how long it takes the server to compare the received TOTP value with the expected TOTP value. Now in practice, it is hard to get access to reliable timing information, especially when the communication is over a network where random network latency can make any timing measurements reliable. Regardless, good security requires that an attacker should not be able to deduce any information about the secret or the TOTP value despite the possibility of having reliable timing information.
With the assumption of reliable timing information being available to the attacker, here is how an attacker would carry out the attack. Brute force the first digit of the TOTP by sending TOTP values 100000, 200000, etc. The observation that it takes slightly longer for the validation to fail for 200000 helps the attacker deduce that the first digit is 2. The attacker can perform this recursively for other digits and deduce all the digits within a maximum of 60 attempts. This is a great reduction in the security of the scheme which required 1000000 attempts originally.
Of course, one can mitigate an attack like this by locking out the user's account after 5 failed attempts or so but that would be an additional layer of security. Each layer of security should be sound on its own. Therefore even if there is an account lockout facility, the TOTP validation algorithm should be secure on its own and should not be vulnerable to timing attacks.
Consider the following example. The TOTP value to log into a system at a given time is 27182. Only the client and the server know this because they share the same secret key from which the TOTP values are generated. Now assume an attacker that can send arbitrary TOTPs to the system and has access to reliable timing information about how long it takes the server to compare the received TOTP value with the expected TOTP value. Now in practice, it is hard to get access to reliable timing information, especially when the communication is over a network where random network latency can make any timing measurements reliable. Regardless, good security requires that an attacker should not be able to deduce any information about the secret or the TOTP value despite the possibility of having reliable timing information.
With the assumption of reliable timing information being available to the attacker, here is how an attacker would carry out the attack. Brute force the first digit of the TOTP by sending TOTP values 100000, 200000, etc. The observation that it takes slightly longer for the validation to fail for 200000 helps the attacker deduce that the first digit is 2. The attacker can perform this recursively for other digits and deduce all the digits within a maximum of 60 attempts. This is a great reduction in the security of the scheme which required 1000000 attempts originally.
Of course, one can mitigate an attack like this by locking out the user's account after 5 failed attempts or so but that would be an additional layer of security. Each layer of security should be sound on its own. Therefore even if there is an account lockout facility, the TOTP validation algorithm should be secure on its own and should not be vulnerable to timing attacks.
Thanks for the in depth explanation. So it seems that, during the interval (which defaults to 30s) they could possibly determine the TOTP value.
It seems possible to brute force, however as soon as the interval changes, by default every 30 seconds, the TOTP is now new because time has passed.
But assuming they could do some crazy thing like attempt 10,000 times within that interval, I suppose it's arguable that it should still be secure...
So upon research looks like it's quite easily fixed by comparing all digits individually, and then aggregating if all all true, but continuing the iteration and checks even if a false value has been found. I suppose that would cover this case.
Thanks for pointing this out! Will be adding an issue ;)
It seems possible to brute force, however as soon as the interval changes, by default every 30 seconds, the TOTP is now new because time has passed.
But assuming they could do some crazy thing like attempt 10,000 times within that interval, I suppose it's arguable that it should still be secure...
So upon research looks like it's quite easily fixed by comparing all digits individually, and then aggregating if all all true, but continuing the iteration and checks even if a false value has been found. I suppose that would cover this case.
Thanks for pointing this out! Will be adding an issue ;)
The author's main SQL code seems to be in this file: https://github.com/pyramation/totp/blob/master/packages/totp...
For comparison, these are my relatively short TOTP implementations in {TypeScript, Python, Java, Rust, C++}: https://www.nayuki.io/page/time-based-one-time-password-tool... . I even have a 6-line Python function.
For comparison, these are my relatively short TOTP implementations in {TypeScript, Python, Java, Rust, C++}: https://www.nayuki.io/page/time-based-one-time-password-tool... . I even have a 6-line Python function.
The file you're pointing to is not the full extension, here it is:
https://github.com/pyramation/totp/blob/master/packages/totp...
https://github.com/pyramation/totp/blob/master/packages/totp...
> I even have a 6-line Python function.
In case, anyone is curious what that might look like, I have a 30-line Python code here (TOTP generation only, no verification): https://github.com/susam/mintotp. Indeed the core function (the HOTP function) contains only 6 lines, thanks to Python's extensive standard library.
In case, anyone is curious what that might look like, I have a 30-line Python code here (TOTP generation only, no verification): https://github.com/susam/mintotp. Indeed the core function (the HOTP function) contains only 6 lines, thanks to Python's extensive standard library.
Cool. If I had to choose I'd wrap the simple py implementation in a PL/Python UDF.
Why? Implementation-wise, it's far better to have a pure plpgsql function than a Python UDF if you have a choice between the two. A Python UDF would be useful if you need to do more Python stuff in the db in general.
agree, this is exactly why the code was written. I had originally tried to use plv8 or others, but as my postgres experience matured and I built testing harnesses, I decided to throw away any non-standard code (plv8, etc).
I think often times folks who come to postgres often don't know PL/pgsql (as I also didn't) and prefer to user their language of choice. I truly think if our postgres dev environments were better, we'd find more people writing code this way, so I can empathize with why people would prefer python or JS in the db, but at this stage I can't get myself to use those extensions.
FWIW, at one point, AWS didn't support a lot of these (sometimes unsafe) language extensions. So going pure PL/pgsql was the only true path forward. I think now for AWS users, they do support plv8 now, but as you pointed out somewhere in this thread, they are much slower... also I remember plv8 specifically had memory leaks.
I think often times folks who come to postgres often don't know PL/pgsql (as I also didn't) and prefer to user their language of choice. I truly think if our postgres dev environments were better, we'd find more people writing code this way, so I can empathize with why people would prefer python or JS in the db, but at this stage I can't get myself to use those extensions.
FWIW, at one point, AWS didn't support a lot of these (sometimes unsafe) language extensions. So going pure PL/pgsql was the only true path forward. I think now for AWS users, they do support plv8 now, but as you pointed out somewhere in this thread, they are much slower... also I remember plv8 specifically had memory leaks.
I mean, why though? I haven't played around much with other languages within Postgres, and mainly stick to pl/pgsql, so real question.
Is it performance related? Not requiring another language to be installed?
Is it performance related? Not requiring another language to be installed?
Yes and yes; all other things equal, performance will be a lot worse when using Python. And you'll need Python installed.
Maybe this is the case in general, but a while back we did something that required flipping an array and when we did it with python inside Postgres it was several magnitudes faster.
This would make for a super interesting blog post / case study IMO, you should write about it even if it's just to showcase the two algorithms / comparisons.
Sorry, but late back but I’ve just found the code.
It’s a bit of a weird case where I needed to reverse arrays inside a big json blob (millions of big json blobs). Trying to explode the structures out and rebuild them was a bit of a no-go. Instead I did a nasty little regex replace on the json string:
Since then I've always installed the python extension whenever I set up a new postgres, just in case.
It’s a bit of a weird case where I needed to reverse arrays inside a big json blob (millions of big json blobs). Trying to explode the structures out and rebuild them was a bit of a no-go. Instead I did a nasty little regex replace on the json string:
re.sub('"key": \[([^\\]]+)\]', lambda match: '"key": [' + ', '.join(reversed(match.group(1).split(', '))) + "]", els)
Since then I've always installed the python extension whenever I set up a new postgres, just in case.
for sure there are all sorts of postgres regex tools... You can likely do everything. The main limitations I found in plpgsql were in base encodings (that were missing), which is why I had to implement base32 from scratch. Besides that, it's pretty much a super powerful language
Author here. Here is the full code if anyone is interested: https://github.com/pyramation/totp/blob/master/packages/totp...
I can't be the only [UK] person who sees 'TOTP' and immediately thinks 'Top of the Pops'! XD
Cool! I remember seeing a pg TOTP implementation in this gist[1] before. Seems this extension was based off that?
[1]: https://gist.github.com/bwbroersma/676d0de32263ed554584ab132...
[1]: https://gist.github.com/bwbroersma/676d0de32263ed554584ab132...
https://github.com/pyramation/totp/blob/master/packages/totp... yes in the notes of the source here
The first TOTP implementation I wrote was here was much less efficient, literally the algorithm in steps: https://github.com/pyramation/learn-totp/blob/master/package...
That gist is essentially the pure TOTP algo, but it was missing what we use in industry practice that the RFC was missing... base32 encode/decode.
So I implemented a base32 encode/decode so that the TOTP algo actually works with google authenticator and authy https://github.com/pyramation/totp/blob/master/extensions/%4...
When I found the gist, while the original code worked, the gist was much smaller (used more efficient bitwise operations) and the gist author I collaborated briefly and decided to combine the gist and the code for OSS
The first TOTP implementation I wrote was here was much less efficient, literally the algorithm in steps: https://github.com/pyramation/learn-totp/blob/master/package...
That gist is essentially the pure TOTP algo, but it was missing what we use in industry practice that the RFC was missing... base32 encode/decode.
So I implemented a base32 encode/decode so that the TOTP algo actually works with google authenticator and authy https://github.com/pyramation/totp/blob/master/extensions/%4...
When I found the gist, while the original code worked, the gist was much smaller (used more efficient bitwise operations) and the gist author I collaborated briefly and decided to combine the gist and the code for OSS
Can someone explain where/why this might be used? Or is it just for fun?
First thing that came to mind was in one of the "Postgres-backend" projects like Hasura[1], Postgraphile[2], or PostgREST[3].
[1]: https://github.com/hasura/graphql-engine/
[2]: https://www.graphile.org/postgraphile/
[3]: https://postgrest.org
[1]: https://github.com/hasura/graphql-engine/
[2]: https://www.graphile.org/postgraphile/
[3]: https://postgrest.org
Benjie, one of the PostGraphile creators, has a good talk [1] advocating for database-driven development.
OTOH, having dug into PostGraphile a bit, I personally wouldn't advocate for pushing so much backend logic into the DB.
Like, if you decide to do auth and TOTP in the DB, you'll end up implementing it in PL/pgSQL. Writing core security logic in a less-familiar language feels like it adds risk.
Also, for smaller projects your backend is often just a single server, so moving auth in into the DB doesn't save you from managing distributed state.
[1] https://www.youtube.com/watch?v=XDOrhTXd4pE
OTOH, having dug into PostGraphile a bit, I personally wouldn't advocate for pushing so much backend logic into the DB.
Like, if you decide to do auth and TOTP in the DB, you'll end up implementing it in PL/pgSQL. Writing core security logic in a less-familiar language feels like it adds risk.
Also, for smaller projects your backend is often just a single server, so moving auth in into the DB doesn't save you from managing distributed state.
[1] https://www.youtube.com/watch?v=XDOrhTXd4pE
> Like, if you decide to do auth and TOTP in the DB, you'll end up implementing it in PL/pgSQL.
Not really? Postgres (as well as other rdbms) support many other languages - I don't see many good reasons to insist on pl/pgSQL for uses like these?
Both python, perl and TCL are part of the standard distribution in addition to pl/pgSQL.
https://www.postgresql.org/docs/13/xplang.html
https://www.postgresql.org/docs/13/external-pl.html
Not really? Postgres (as well as other rdbms) support many other languages - I don't see many good reasons to insist on pl/pgSQL for uses like these?
Both python, perl and TCL are part of the standard distribution in addition to pl/pgSQL.
https://www.postgresql.org/docs/13/xplang.html
https://www.postgresql.org/docs/13/external-pl.html
Right, except if my backend is in JS, there's a cognitive cost to adding another language to the stack.
I could use plv8, but there's a more subtle preference here for JS to wrap SQL, rather than the reverse (plus tooling is less convenient, e.g. if you're writing Typescript).
My rule of thumb is: SQL great, PL not so much.
I could use plv8, but there's a more subtle preference here for JS to wrap SQL, rather than the reverse (plus tooling is less convenient, e.g. if you're writing Typescript).
My rule of thumb is: SQL great, PL not so much.
> except if my backend is in JS, there's a cognitive cost to adding another language to the stack.
Agreed.
However, I don't see why not use one of the other mature "real" extension languages other than pl/pgSQL.
As for typescript, maybe there's (distant) hope:
https://github.com/supabase/postgres-deno
Agreed.
However, I don't see why not use one of the other mature "real" extension languages other than pl/pgSQL.
As for typescript, maybe there's (distant) hope:
https://github.com/supabase/postgres-deno
exactly! this is the ecosystem that I'm a part of that inspired me to build this :)
I do agree about making sure you have experience writing PL/pgSQL and would also add that you should make sure you have a good test-driven environment when writing code in the db.
I do agree about making sure you have experience writing PL/pgSQL and would also add that you should make sure you have a good test-driven environment when writing code in the db.
exactly! https://www.graphile.org/postgraphile/ is the system I'm using on and wanted to avoid writing a resolver in JS
Incrementing the counter, and generating the next HOTP code in a single UPDATE statement could be useful.
Hi! It was a bit of both fun and work ;)
I use graphile and didn't want to have to implement a resolver in JavaScript, keeping logic and integrity of auth systems in the database.
I use graphile and didn't want to have to implement a resolver in JavaScript, keeping logic and integrity of auth systems in the database.
On the other hand, one could also write js in postgres:
https://www.postgresql.org/docs/13/external-pl.html
https://github.com/plv8/plv8
https://www.postgresql.org/docs/13/external-pl.html
https://github.com/plv8/plv8
yea totally! I love plv8... it's actually how I got started with postgres functions.
I ultimately switched to native PG. There were known memory leaks in plv8 and eventually after learning pl/pgsql it became more natural and clean, plus AWS at the time didn't support plv8 which was another incentive not to use language extensions
I ultimately switched to native PG. There were known memory leaks in plv8 and eventually after learning pl/pgsql it became more natural and clean, plus AWS at the time didn't support plv8 which was another incentive not to use language extensions
nice to see sqitch[1] in use here
1: https://sqitch.org/
1: https://sqitch.org/
yea! I LOVE sqitch. As a person who likes to write pure sql with no ORM, sqitch is the absolute best choice
- Using '=' for comparing TOTPs in the totp.verify function[1] is not safe from timing attacks.
- The function random() used in the totp.random_base32 function[2] is not a cryptographically secure random number generator.
[1]: https://github.com/pyramation/totp/blob/7ec3104/packages/tot...
[2]: https://github.com/pyramation/totp/blob/7ec3104/packages/tot...