How resilient is SQRL against users unique IDs by creating multiple identities?


Status
Not open for further replies.

Once set this cannot be

Active member
Jun 27, 2019
42
14
Please forgive me if I misunderstand. Since SQRL generates UNIQUE identifiers for each account created, and since there is a finite number of identifier placeholders, and since a certain proportion of people connected to the internet have nefarious intentions, what is preventing SQRL from exhausting its identifiers if each is to be unique and not repeated or reused and a script is written to automate account creation with the intent to DDoS the SQRL account creation process?
 
  • Like
Reactions: Simon9

Vela Nanashi

Well-known member
May 19, 2018
715
123
Mathematics prevent it.

There are 2^256 different keys that can be generated by SQRL's hmac, these are used to create a private key, and from that a public key is generated, that is used to identify the user. The chance of anyone being able to even with hostile intent find a collision is so small that it is almost (but not quite) impossible.

I am sure someone else can explain just how astronomically small the chance is. Even if every grain of sand on earth was guessing keys at billions per second, it is likely the heat death of the universe would hit first, I think (I did not bother doing the math on that).
 

Vela Nanashi

Well-known member
May 19, 2018
715
123
Now if each atom (estimated to 10^80 ~= 2^266) in the universe got one guess, they would together figure the key out with their first guess (2^10 times over).
 

PHolder

Well-known member
May 19, 2018
1,192
194
The real restriction is that the site is not going to be able to store more than a few trillion accounts at best. (Assuming it were willing to dedicate a 12 disk RAID array of 10TB drives to user information.) Let's call it 2^32 = ‭4,294,967,296‬ accounts because powers of two make the math easier. There are 2^256 possible account identifiers, and we're going to eliminate 2^32 of them... [edit: wrong, see below: so 2^256-2^32 = 2^(256-32) = 2^224]. There would still be 2^224 or approximately 2.7 with 66 zeros after it identifiers left to use. Exhaust of identifiers is not an issue. DoS is an issue, but doing so by exhausting accounts is a huge waste of time given there are other more effective means to do a DoS.
 
Last edited:
  • Like
Reactions: Simon9

Vela Nanashi

Well-known member
May 19, 2018
715
123
If we divided them by 4 billion accounts yes then we would get 2^224, but if it is just subtraction we get something like 2^255.99999etc :)
 

Once set this cannot be

Active member
Jun 27, 2019
42
14
Thanks for the reply, Vela... I am not thinking about collisions with PKI. I am thinking about a site recognizing a 77-digit number to authenticate that user to a website. What if multiple users/bots register/unregister/rekey enough times to exhaust all 77 digit combinations on THAT server? I don't know how big 77 digits is - perhaps larger than a/most database(s) will allow.
 

Vela Nanashi

Well-known member
May 19, 2018
715
123
We could give every atom on earth its own key on a server and still have a lot (most) of them left :)

Obviously it would take more than one atom to store each database entry for each key...

https://www.wolframalpha.com/input/?i=log2(2^256-2^32) hey I was correct about 255.999999999999etc :)

2^256 = 115792089237316195423570985008687907853269984665640564039457584007913129639936 ~= 1.15792 * 10^77 (77-78 digits according to wolfram)
 

shanedk

Well-known member
May 20, 2018
419
112
Here's an analysis I posted awhile back over to the newsgroups:

2^256 is basically 2^32 8 times over, and 2^32 is just under 4.3 billion. Let's call it 4 billion.

Let's say you had a computer capable of creating 4 billion SQRL identities every second. They were small enough that you could have 4 billion of these in your home.

Now give one of these to each of 4 billion people on the planet. That's 3.

We now go off-planet and give each of these to 4 billion people each on 4 billion different planets in the galaxy. That's 4.

We do it all over again in 4 billion other galaxies. That's 5.

All of this is in one second, so we'll do it for 4 billion seconds, or just under 127 years. Let's call that an "era."

We'll do that for 4 billion eras, or over 500 billion years. Let's call that an "epoch."

We still need one more, so we do the same thing in 4 billion different universes. Now we've done it 2^256 times!

Unless something goes mind-bogglingly wrong with a client's random number generator, a collision is not happening!
 

Once set this cannot be

Active member
Jun 27, 2019
42
14
Thanks for taking the time.

Sometimes I am so dumb. It’s easy to just see the number 77. My mind’s logic says 3 digits per thousand, so then thinks there’s 25 multiples; so thinks 25,000. But there are 10 digits, so that’250,000.

IKNOW this is wrong, but we really have so little comprehension of big numbers.
 
  • Like
Reactions: Simon9

ramriot

Well-known member
May 24, 2018
127
14
Unless something goes mind-bogglingly wrong with a client's random number generator, a collision is not happening!
Bad PRNG's is a thing, no mind boggling needed & subtle effects can lead to very bad results. This is why Steve deliberately started building his client around a well put together entropy gathering routine that feeds the PRNG.

There are several such examples on the SN podcast, i.e. the Estonian Identity card problems that were the result of using a low power prime generator for RSA keys. Which they mitigated by switching to ECC keys.

Even then I would strongly advise anyone writing their own software or hardware client to use only well understood & trusted random source generators. Plus instrument their code with sanity checkers to prevent entropy exhaustion or other effects.
 

shanedk

Well-known member
May 20, 2018
419
112
Bad PRNG's is a thing, no mind boggling needed & subtle effects can lead to very bad results. This is why Steve deliberately started building his client around a well put together entropy gathering routine that feeds the PRNG.
Yes, which is why SQRL is made to be very resistant to that. It's one of those things that is well worth overdoing. Also, one of the worst cases that I'm aware of was the flaw in Android's SecureRandom function that resulted in all those Bitcoin wallets being insecure, and even then I still don't think you had any collisions.
 
G

Gristle

Guest
I'm no longer contributing to this community because the moderator (PHolder) is too closed minded to allow differing options to be expressed freely on this forum. I've been harassed too many times by this little person and he's made it clear I'm not welcome here.
 
Last edited by a moderator:
G

Gristle

Guest
I'm no longer contributing to this community because the moderator (PHolder) is too closed minded to allow differing options to be expressed freely on this forum. I've been harassed too many times by this little person and he's made it clear I'm not welcome here.
 
Last edited by a moderator:
  • Like
Reactions: Simon9
G

Gristle

Guest
I'm no longer contributing to this community because the moderator (PHolder) is too closed minded to allow differing options to be expressed freely on this forum. I've been harassed too many times by this little person and he's made it clear I'm not welcome here.
 
Last edited by a moderator:

Vela Nanashi

Well-known member
May 19, 2018
715
123
I think it works like this (still drinking my morning tea, so might be wrong):

After half the ids are used 2^255, we reach 50% chance of collision each time we make a new id at random, if we use 1/(2^128)th of all the ids (that is 2^128 ids) we have a 1/2^128 chance of collision each time we make a new id at random :) We will not use 2^128 ids on Earth, it might become an issue if we convert the entire galaxy into a birch planet, all of it used to run emulated minds as efficiently as possible.

We probably would upgrade to using 512 bit keys (there is already a curve for that) or if quantum computers actually become viable we might be using some other quantum proof cryptography, long before then. I am not sure if any of these things will be an issue in our lifetimes though (quantum computers might).
 

ramriot

Well-known member
May 24, 2018
127
14
It's also worth keeping in mind that that 256-bit SQRL identity itself is not the output of a single PRNG, due to the need to create a cryptographic binding between the SQRL identity and the recovery-code.
Sorry not true, The Recovery Code is the machine generated password that encrypts the stored IUK, the original IUK is what passes through the EnHash function to output the users MK which is then encrypted for storage by the users password ( after strengthening with our PBKDF ).
 

ramriot

Well-known member
May 24, 2018
127
14
Yes, which is why SQRL is made to be very resistant to that. It's one of those things that is well worth overdoing. Also, one of the worst cases that I'm aware of was the flaw in Android's SecureRandom function that resulted in all those Bitcoin wallets being insecure, and even then I still don't think you had any collisions.
As far as I'm aware the only resistance to a bad entropy source for the core IUK is that we use EnHash followed by salting our public keys with the targets realm (FQDN+x). Both these are deterministic in nature, thus a rainbow table could be generated, provided the source weakness allows for it.

If a client implementation were to be found with a bad key generator then it would be feasible, depending upon the nature of the weakness to look for traces of those in the shared site specific public keys. It's not an easy task by any means, and it's a much harder task than with most currently known key issues, but it is not beyond the realm of possibility.

Thus I say again to writers of SQRL clients, make reliable entropy the core of your implementation.
 
Status
Not open for further replies.