Rate-Limiting in an OAuth REST API: per token or per consumer?

Question

I am building a REST API and intent to use rate limiting (using the leaky bucket algorithm) as a way to protect against crawling and enumeration. The API will be consumed by a Mobile/Tablet App (installed on many devices) and server-to-server clients (some in-house, some external).

Allowing users to install the app on their phones (factually rendering the data exposed by the API public knowledge) while still limiting crawling and enumeration by reverse-engineers i've come up with this strategy:

• On first run, the app generates a random ID large enough to be considered unique
• When requesting a token for API access the app authenticates with that ID.
• Any token request for the same app ID is answered with the same token (as long as it hasn't expired)
• Any token request for the same IP address is answered with the same token (as long as it hasn't expired), entirely ignoring the app ID.

This policy does not apply to the server-to-server clients as those will have to set up a contract with my company in order to consume the API.

---

Now, as to rate limiting:

Is one of these strategies preferable? If: what are the pros and con's?

1. assure no consuming entity gets hold of more than one valid token at a time (basically the same as with the APPs). Hook the leaky bucket to the tokens.
2. grant as many tokens to an entity as it requests. Share the leaky bucket across all the tokens granted to an entity.

Also: If option 1 is preferable: How should the 1-token-per-entity policy be applied?

1. Grant new tokens only after previous ones have expired. Provide an interface allowing entities to revoke/invalidate their current token.
2. When a new token is requested revoke all previous tokens.

I am especially worried about race conditions between

• multiple server instances of the same contractor (thus all subject to the same rate-limit)
• multiple app installations running sharing an IP address (public WiFi, multiple users sharing an internet connection, ...)

Answer 1

After a lot of back and forth and discussions with colleagues i have settled with option 2. Here is why:

The strategies are equal functionality-wise. The race conditions are what causes trouble. We anticipate these race conditions to occur:

1. Multiple devices of the same entity initially request a token [in a very small timespan]
2. Multiple devices of the same entity request a new token [in a very small timespan] because earlier ones expired

While in the first case the two strategies are of equal quality, the strategy 2 has several advantages in the second case:

Devices might want to request a new token before the current one expires, just to play safe

• not granting a new token unless previous ones have expired does not allow for this.
• invalidating a previous, still valid token in order to get a new one will very likely cause issues: other devices of the same entity will attempt to use the just invalidated token and thus receive error responses
• If the time setting of client devices is slightly different than the server time (15 seconds is enough), the clients may either
  • receive tokens that appear to them as already expired
  • not request a new token in time (because the token appears as still valid while it actually has expired)
• this issue gets really weired if our server instances are not running at precisely the same time

A per device logout / disconnect is impossible

Single devices might want to "log out" and assure their token is not misued. This is impossible using strategy 1, too.

Some devices might not require all permissions granted to their entity

If a device does not need all potential possible permissions it is desirable that is does not obtain a token with more permissions than required. This, too, is impossible using strategy 1.