5 ms·

We're talking number of URLs, not number of CPU iterations. Exploring 2^56 URLs is not that easy.

by d--b 11y ago

brianwawok 11y ago
Exploring 2^56 URLs is possible. Exploring it with anti-brute force detection from the keeper of said URLs? Good luck. They could easily limit any ip to 10 URLs per hour or something and make it impossible to scan.
- d--b 11y ago
  Really? If you could make 1,000,000 requests per second, exploring 2^56 URLs would take you 2000 years.
- zeveb 11y ago
  > They could easily limit any ip to 10 URLs per hour or something and make it impossible to scan. Then an attacker would just use a botnet. Granted, he can probably get interesting items off of the computers in his botnet too.
zeveb 11y ago
> Exploring 2^56 URLs is not that easy. Not easy, but not impossible. And it's not the case that an attacker is looking for one interesting URL: he's looking for any interesting URLs. Depending on the number of URLs stored in the service, and the fraction which are at all interesting, it may very well be worth the attacker's bother. As an aside, why the heck is my post so heavily downvoted? It's factual: the given lengths are not long enough to be secure from brute-forcing; they probably will be brute-forced.
- rybosome 11y ago
  The article states that Google has deployed defenses against brute forcing, so attempting to do slow at a rate that doesn't trip these defenses may not be worthwhile. I must admit that I don't understand how the number of characters corresponds to bits of entropy. Know of a resource that explains this?
  - dbond 11y ago
    Napkin math incoming... Say you only used a-z in your token, at 1 character long you have 26^1 combinations, at 6 you have 26^6 or 308,915,776 combinations, which could easily be scanned. Increase the length to 26^ or 95,428,956,661,682,180, a big ass number, if we reserve 1,000,000,000,000 for actual items and create them over this range then the odds of guessing a correct token is 0.000000010479, then ban all the hosts which trip more than the average number of 404s.
  - lucb1e 11y ago
    log(num_options)/log(2) So for a 8 character digits-only value, num_options is 10^8, so log(power(10, 8))/log(2) = 30 bits. This means both 30 bits needed to store the value and 30 bits of security. It also works for octal or hexadecimal: just replace log(2) with log(n), like log(16) for hexadecimal.
    - Freaky 11y ago
      You have your arguments swapped. 30 bits for 8^10, 26.6 for 10^8. https://www.google.co.uk/search?q=log2(10%5E8) https://www.google.co.uk/search?q=log2(10%5E8)
  - zeveb 11y ago
    > I must admit that I don't understand how the number of characters corresponds to bits of entropy. Know of a resource that explains this? There are 26 letters; mixed-case doubles that for 52 choices; digits add 10 for a total of 62 possible choices for each character. That means that 2 characters have 62^2 possible configurations, 3 62^3 and so forth. If you take the resulting number and calculate the ceiling of its logarithm in base 2, you get the number of bits needed to represent it: (ceiling (log (expt 62 11) 2)) → 66 -0.5038376
- groby_b 11y ago
  First - assume the URLs use something like base64 encoding. That means 11 chars are 2^66, not 2^56 URLs. In turn, that means the entire space is ~10^20 URLs.(smidgen less, 710^19) Let's assume 1B users, with 1K URLs belonging to them on average. That's 10^12 URLs. Which means, on average, you query 10^8 URLs until you hit the first one. Let's further assume you could actually query 10^5 URLs/s. That means a single* URL requires query rates for 20 minutes. Sure, theoretically that's doable. Except you'd cause query rate and error rate to spike, and the setup to do so would be quite expensive. So, in the best case, after those 20 minutes, you have a random picture of a dog, or a map. Having a network capable of running 10K qps and risking detection to find, maybe, one picture every 20 minutes? There's just not the incentive to do that. There are many more interesting avenues for this. And since it's bandwidth-bound, not CPU bound, that speed is not going to rapidly accelerate.
- groby_b 11y ago
  First - assume the URLs use something like base64 encoding. That means 11 chars are 2^66, not 2^56 URLs. In turn, that means the entire space is ~10^20 URLs.(smidgen less, 7x10^19) Let's assume 1B users, with 1K URLs belonging to them on average. That's 10^12 URLs. Which means, on average, you query 10^8 URLs until you hit the first one. Let's further assume you could actually query 10^5 URLs/s. That means a single URL requires query rates for 20 minutes. Sure, theoretically that's doable. Except you'd cause query rate and error rate to spike, and the setup to do so would be quite expensive. So, in the best case, after those 20 minutes, you have a random picture of a dog, or a map. Having a network capable of running 10K qps and risking detection to find, maybe, one picture every 20 minutes? There's just not the incentive to do that. There are many more interesting avenues for this. And since it's bandwidth-bound, not CPU bound, that speed is not going to rapidly accelerate.

We're talking number of URLs, not number of CPU iterations. Exploring 2^56 URLs is not that easy.

by d--b 11y ago

We're talking number of URLs, not number of CPU iterations. Exploring 2^56 URLs is not that easy.

Exploring 2^56 URLs is possible. Exploring it with anti-brute force detection from the keeper of said URLs? Good luck. They could easily limit any ip to 10 URLs per hour or something and make it impossible to scan.

d--b 11y ago
Really? If you could make 1,000,000 requests per second, exploring 2^56 URLs would take you 2000 years.
zeveb 11y ago
> They could easily limit any ip to 10 URLs per hour or something and make it impossible to scan. Then an attacker would just use a botnet. Granted, he can probably get interesting items off of the computers in his botnet too.

zeveb 11y ago

> Exploring 2^56 URLs is not that easy. Not easy, but not impossible. And it's not the case that an attacker is looking for one interesting URL: he's looking for any interesting URLs. Depending on the number of URLs stored in the service, and the fraction which are at all interesting, it may very well be worth the attacker's bother. As an aside, why the heck is my post so heavily downvoted? It's factual: the given lengths are not long enough to be secure from brute-forcing; they probably will be brute-forced.

rybosome 11y ago
The article states that Google has deployed defenses against brute forcing, so attempting to do slow at a rate that doesn't trip these defenses may not be worthwhile. I must admit that I don't understand how the number of characters corresponds to bits of entropy. Know of a resource that explains this?
- dbond 11y ago
  Napkin math incoming... Say you only used a-z in your token, at 1 character long you have 26^1 combinations, at 6 you have 26^6 or 308,915,776 combinations, which could easily be scanned. Increase the length to 26^ or 95,428,956,661,682,180, a big ass number, if we reserve 1,000,000,000,000 for actual items and create them over this range then the odds of guessing a correct token is 0.000000010479, then ban all the hosts which trip more than the average number of 404s.
- lucb1e 11y ago
  log(num_options)/log(2) So for a 8 character digits-only value, num_options is 10^8, so log(power(10, 8))/log(2) = 30 bits. This means both 30 bits needed to store the value and 30 bits of security. It also works for octal or hexadecimal: just replace log(2) with log(n), like log(16) for hexadecimal.
  - Freaky 11y ago
    You have your arguments swapped. 30 bits for 8^10, 26.6 for 10^8. https://www.google.co.uk/search?q=log2(10%5E8) https://www.google.co.uk/search?q=log2(10%5E8)
- zeveb 11y ago
  > I must admit that I don't understand how the number of characters corresponds to bits of entropy. Know of a resource that explains this? There are 26 letters; mixed-case doubles that for 52 choices; digits add 10 for a total of 62 possible choices for each character. That means that 2 characters have 62^2 possible configurations, 3 62^3 and so forth. If you take the resulting number and calculate the ceiling of its logarithm in base 2, you get the number of bits needed to represent it: (ceiling (log (expt 62 11) 2)) → 66 -0.5038376
groby_b 11y ago
First - assume the URLs use something like base64 encoding. That means 11 chars are 2^66, not 2^56 URLs. In turn, that means the entire space is ~10^20 URLs.(smidgen less, 710^19) Let's assume 1B users, with 1K URLs belonging to them on average. That's 10^12 URLs. Which means, on average, you query 10^8 URLs until you hit the first one. Let's further assume you could actually query 10^5 URLs/s. That means a single* URL requires query rates for 20 minutes. Sure, theoretically that's doable. Except you'd cause query rate and error rate to spike, and the setup to do so would be quite expensive. So, in the best case, after those 20 minutes, you have a random picture of a dog, or a map. Having a network capable of running 10K qps and risking detection to find, maybe, one picture every 20 minutes? There's just not the incentive to do that. There are many more interesting avenues for this. And since it's bandwidth-bound, not CPU bound, that speed is not going to rapidly accelerate.
groby_b 11y ago
First - assume the URLs use something like base64 encoding. That means 11 chars are 2^66, not 2^56 URLs. In turn, that means the entire space is ~10^20 URLs.(smidgen less, 7x10^19) Let's assume 1B users, with 1K URLs belonging to them on average. That's 10^12 URLs. Which means, on average, you query 10^8 URLs until you hit the first one. Let's further assume you could actually query 10^5 URLs/s. That means a single URL requires query rates for 20 minutes. Sure, theoretically that's doable. Except you'd cause query rate and error rate to spike, and the setup to do so would be quite expensive. So, in the best case, after those 20 minutes, you have a random picture of a dog, or a map. Having a network capable of running 10K qps and risking detection to find, maybe, one picture every 20 minutes? There's just not the incentive to do that. There are many more interesting avenues for this. And since it's bandwidth-bound, not CPU bound, that speed is not going to rapidly accelerate.