Proposal to address the question raised during Gothenburg, Sweden Meetup about preventing a DDOS from computationally cheap SQRL clients

  • New Wordpress Plug-In Forum
    Guest:

    Just a note that we have a new forum to contain discussions relating to the Wordpress plug-in which Daniel Persson originated and has been making great progress on. You'll find it under "Server-Side Solutions."

    /Steve.

dmalenic

New member
Oct 11, 2019
2
2
About 2 hours and 16 minutes in Gothenburg, Sweden presentation recording, someone form the audience asked if there is a solution to defend against DDOS attack by a botnet of malicious and computationally cheap SQRL clients creating a huge number of fake accounts.

A small addition to the SQRL protocol could allow servers to enforce the minimal computations complexity on clients. This proposal is a straight forward adoption of ideas coming from Hashcash, Bitcoin and similar systems that use Proof of work (PoW).

Proposal:
1. With every SQRL request a client must provide a PoW which is a 128 byte number whose SHA256 ends with n zero bits (difficulty). The difficulty is defined by the server and can be dynamically changed by the server.
2. To prevent clients from using a pre-computed PoW, the first 64 bytes of the PoW are provide by the server (nonce randomly generated by the server). SQRL servers already have a mean of computationally efficient generation of 64 byte random number (Steve's adaptation of Blowfish algorithm).
3. Client must find the trailing 64 bytes of PoW (response) such that SHA256 of nonce concatenated with the response satisfies the difficulty i.e. ends with n zeros.
3. Client sends 64 bytes it has computed.
4. Server validates if PoW satisfies the difficulty i.e. computes SHA256 over concatenation of 64 byte nonce with 64 byte response. It accepts the client request only if SHA256 ends with n zeros (difficulty defined in step 1).

The difficulty can be dynamically adjusted by the server based on the current load. Also, the difficulty can be changed based on the use-case. The login use-case may require the difficulty n1, while the establishment of the SQRL identity may require difficulty n2, and finally resetting the SQRL identity may require difficulty n3; where n1 < n2 < n3. This would enable server to prioritize serving existing users (the smallest difficulty n1), while making the life much harder for bots (difficulties n2 and n3).
 
  • Like
Reactions: TechLiam
@dmalenic it's a good idea I can see the benifits of it how ever SQRL v1 was an attempt to remove users needing password not to stop a bot creating lots of account.

If i was to get picky as well, as a adversary trying to creating lots of accounts I could just rent/own a large number of bots (IoT device comes to mind) and request them to asyncranesly create new SQRL identities although yes your solution would slow thaat down it would not stop it from happening aspeshally with bitcoin mining macheans out there that could do a hash very quickly (maybe you would even centralise this so your small IoT device didn't need to PoW anything). I feel treditional methods for slowing down account creation such as rate limits are good enough and the sites implomentation could just stop account creation if they notice an uptick in account creation untill other protections can be put in place.

This subject is my next point of fouse for the ASP.net Core Middleware so i have done some thinking about what we can do today with the SQRL protocol as it is today.

This is somthing for v2 of SQRL I think for sure as it helps but don't think it would solve all the problems and would make servers and clients more complex for little gain.

Anyway that my thoughts :)
 

Vela Nanashi

Well-known member
May 19, 2018
633
107
Yeah I have been thinking that a proof of work thing would be useful too, but only for registering a new account, not for logging in, however most places can combine some sort of captcha in the registration process like they can for login and password, and that will prevent automated filling of the database. We do want to avoid adding email as a requirement for SQRL accounts, but sites are free to require email loop if they want to. Also if we do add a proof of work thing, we should probably not use anything that is already easy to accelerate like SHA2 in its plainest form, so that the already existing hardware accelerators can't be used. Perhaps we can reuse the code for hashing the password that is included in the SQRL client already, Scrypt, only refactored a bit to work similar to the other proof of work things.
 

AlanD

Well-known member
May 20, 2018
93
16
Rutland, UK
IIRC this was discussed some time ago, and the answer was that SQRL is only about proving your identity, it is not designed to solve other problems that websites already have, like botnets creating multiple accounts. The solution to that is what exists already, by requiring Captcha or similar devices that require human intervention.
 

dmalenic

New member
Oct 11, 2019
2
2
Thanks for a feedback.

The actual hashing algorithm can also be a parameter. The aim is to raise a bar on the effort in form of time/power/money an adversary would need to spend, sort of deterrence.

The only reason to start with SHA2 would be to keep it as cheap as possible for a defender i.e. server side. SHA2 can be accelerated with the specialized hardware, but this is still very expensive. Most bot-nets are add-hock collection of non-patched commodity hardware (home routers, video cameras or "smart" TVs, laptops, desktops).

The proposal is not aimed to protect against adversary with resources of a nations state, or a bitcoin mining pool looking for a supplementary income :). This would probably require adding some form of a second factor. If a potential adversary is so motivated to look into a specialized hardware, SQRL has already been an success, so resources should be available to enter into the arms race with such adversaries.

As of my understanding, SQRL eliminates most attacks targeting server-side of an authentication protocol. Brute-forcing an identity is not feasible assuming that quantum computers are not round the corner, or at least much more expensive than ASIC chips built to crack any classical crypto. And, there is no identity related information on a server worth stealing. My proposal is just an attempt to address the only attack against the server-side of SQRL protocol, mentioned on Gothenburg meetup, that actually looked feasible.

Anyhow, as @TechLiam mentioned SQRL v1.0 is out. There is a time till SQRL v2.0, to properly asses possible threats and find the most valuable improvements. I'd just like to provide my small contribution.
 
  • Like
Reactions: TechLiam

PHolder

Well-known member
May 19, 2018
918
124
My two cents worth would be that there could be an eventual extension to the protocol, or even outside of it that the server could optionally challenge the client with a proof of work to continue. That way, if the server doesn't feel under attack of any kind, then it can proceed as it always has. If the server feels the client is a problem in any way, it could challenge the client to "pay" for the server's time on a case by case basis. Maybe this could even be fitted into the existing ASK as a special question.
 

shanedk

Well-known member
May 20, 2018
317
86
You could extend the protocol to do this fairly easily. Just make it an optional parameter the server can issue at its discretion. For example:

Code:
pow="<base64URLnonce;difficulty"
where base64URLnonce is a random string created by the server, and difficulty is the number of zeroes the hash needs to start with. So the server might give:

Code:
pow="H3OEONTFy6u;24"
So the client would create strings to append to it, hash the result, and see if the hash started with 24 zeroes when expressed in binary. In other words, the client has a 50-50 chance of finding a match after 8 million or so tries.

The client could simply use a counter, starting at 0 and counting up, convert it to Base64URL, and append it to the string. So it would start off with 0 which encodes to AA (drop the equal signs as per normal in SQRL), 1 would be AQ, etc.

So let's say the client gets to B42eid and gets a hash with 24 leading zeroes in binary when hashing the appended challenge (in other words, the SHA256 hash of H3OEONTFy6uB42eid). The client then sends:

Code:
powr="B42eid"
to the server. ("powr" = "Proof of Work Response") The server then appends the response to the challenge (getting H3OEONTFy6uB42eid just like the user and hashes it. If its hash begins with 24 zeroes, it knows the challenge has been met and can proceed. (Note: I have no idea if this does or not; I didn't run the challenge, just randomly generated a couple of strings.)

As an extension to the protocol, this can be done without breaking compatibility, so clients could go ahead and support it. Servers could then decide what to do about clients that don't respond to the "pow=" challenge.

You'd probably want the difficulty to be based on what a low-end user's device would be able to do in half a second. Don't make the individual user pay too much; the idea is to make it hard for an attacker to do a cumulative attack.
 

PHolder

Well-known member
May 19, 2018
918
124
Don't make the individual user pay too much
I think the answer here is up to the server, if it believes a client is being too big of pain in the buttocks then it can penalize that client more and more. At some point it would stick it on a list of bad actors, which it could eventually expire out of. If the bad actor keeps moving to additional IPs through a DDoS then it will eventually have all the bad client IPs in a list.
 

ramriot

Well-known member
May 24, 2018
73
9
My 2c is that this is not something SQRL needs to address. Don't get me wrong, bad actors on the net are a real problem but addressing their actions is something many other well established methods can deal with.

For the servers I maintain I use fail2ban to monitor system logs. This demon uses selectable heuristics of bad activity to take action on those doing it. Make 9 failed attempts to guess an account password your IP is blocked for 6 hours. Try & flood an API with requests above a certain rate & you get every N requests dropped, & so on. Do this repeatedly over a month & your IP gets perma-blocked.
 

shanedk

Well-known member
May 20, 2018
317
86
The problem is when they use botnets to launch the attack from hundreds of IP addresses, or just spoof the IP address outright.
 

PHolder

Well-known member
May 19, 2018
918
124
I think the problem is that, from a front facing view, there is no way to know if a SQRL message is valid or not without attempting to validate it, and the cryptographic effort to do so is not without cost. This can lead to someone using it as a DoS. This may well just be "the cost of business" but I can see where people might want to add to the client/server exchange some way to hinder it, if possible.
 

ramriot

Well-known member
May 24, 2018
73
9
The problem is when they use botnets to launch the attack from hundreds of IP addresses, or just spoof the IP address outright.
OK, so first this is not a problem IP blocking still works & note as SQRL is a TCP protocol you cannot spoof the IP address
 

ramriot

Well-known member
May 24, 2018
73
9
I think the problem is that, from a front facing view, there is no way to know if a SQRL message is valid or not without attempting to validate it, and the cryptographic effort to do so is not without cost. This can lead to someone using it as a DoS. This may well just be "the cost of business" but I can see where people might want to add to the client/server exchange some way to hinder it, if possible.
The problem here is what any API that incurs resource requirements has & is addressed by initially throttling the API to limit responses to what can be resourced & block those that abuse it
 

PHolder

Well-known member
May 19, 2018
918
124
I know what you're saying @ramriot, but I think the argument is that it is possible to use asymmetry of effort against a mal-actor. You make an action expensive for them and cheap for the server, and that should cause the attacker to have to expend too much effort to be worth the attack. I'm not advocating for any particular approach or design, just noting I can understand where there is concern. If the concern elevates to action, I think it will require a clever design that penalizes bad actors but not good (and that all initial connections should generally be assumed good until proven counter.)
 

Vela Nanashi

Well-known member
May 19, 2018
633
107
Yeah spoofed IP won't work, but a botnet with a lot of fake clients, all creating accounts as fast as possible can mess things up. It might be partially mitigated by making the SQRL protocol stateless until the time when registration is actually done, but all of that can also be automated, just is a bit slower, so making a proof of work be part of it would slow it down a lot more (not that work matters to a botnet owner, but it does slow down their effectiveness). Also limiting how many accounts a single IP can create (in some time frame) might help. Also having a method to perhaps clean out inactive* accounts could help too.

* any account that has not done anything worth while for the server to keep their database entry around for.
 

Alan M Cameron

Well-known member
Feb 7, 2019
92
6
alancameron.net
. . . limiting how many accounts a single IP can create (in some time frame) might help. Also having a method to perhaps clean out inactive accounts could help too.
This sounds like a step towards censorship. If a site is permitting anonymous SQRL users to view the content but not comment or contribute then the number of 'fake' accounts is irrelevant. They would take up processing time viewing the existing content but that is what the site owner allows.
On the other hand contributing anything a comment or some more extensive contribution is the function that the site owner encourages by allowing the contributor immediate access on next reconnection.

It all depends on what the site owner set up the site for.
 

Vela Nanashi

Well-known member
May 19, 2018
633
107
Alan, I am not looking for censorship, I am very much against censorship. Also what you quoted of me is not in any way about that. But I will try to explain a bit more:

Let's say you have a site that allows anonymous viewing of content, without registering, also that registering does not give you any special alterations of viewing things (such as access to hidden things, or theme remembering (these can be done in separate cookies without an account)), but you do require someone create an account to be allowed to post, then if they create an account, and do not post, and never even log in for a long time, you can safely forget them, since you are not storing anything special with their anonymous registration (it can be recreated fully by following the registration steps again). If they do attach something special to their account, such as email, you can round trip check the email, and thus elevate that account to a more likely not a resource exhaustion attack account.

Also limiting how many accounts that can be made in a specific time frame I meant something like 100 accounts per day per ip, or something like that, maybe less than 100, but still enough of them so that a whole highrise building of people could create accounts from behind one NAT/IP, and as soon as one of them posts or otherwise uses the account for something useful you can remove the account from the list of possible accounts used to just eat server database space.

Then again the data needed for a SQRL account is kind of tiny, and you can probably keep a lot of those around on hard disk, without impacting a server much, and just keep active accounts in faster memory or something, however if the account is only ever created, and never logged into or used in some way, then it is a waste of space, and if a single IP makes hundreds of accounts that are never used, then why keep those around?

Adding a proof of work thing is better, as that gives a cost to the attacker, again botnet owners would not care though.

There are also much simpler ways to bring a server to its knees, than SQRL, so I don't really think SQRL will be used in that fashion, but then what do I know?
 

davidsix

New member
Oct 17, 2019
1
0
I agree with @ramriot and @AlanD - preventing Denial of Service attacks seems to be out-of-scope for SQRL. The cost to the server is not significantly different from password-based registration/login systems (as @Vela Nanashi mentions) so existing methods of DoS protection should be sufficient.

-----
Now, in the context of generically rate-limiting registrations with proof-of-work rather than something like CAPTCHA, this has been discussed several times elsewhere and the general conclusion seems to be that it is not significantly better than existing systems. However, if a site administrator wants to implement this, the code exists to do it in the browser - extending SQRL to do it is unnecessary. Alternatively, you could use one or more of the methods mentioned above or used around the web:
  1. (re)CAPTCHA
  2. Email validation
  3. Phone/SMS validation (e.g. Google)
  4. Making $0.01 charge/deposit (e.g. PayPal)
  5. Manual approval by moderators
  6. Invite-only