Prevent subscription ID guessing

Question

I am working on a service which offers information on the road traffic situation.

Users can subscribe to the service via an API, indicating the area and road classes they are interested in, and are assigned a subscription ID. With the subscription ID they can then poll the service for information. The first poll will return any messages from that area, subsequent polls will only return messages that have been added, withdrawn or updated since the last poll operation. (Edit: All these operations are part of an app.)

Users also change their subscription at any time, i.e. change the area and/or road class; this will leave the subscription ID unchanged. They can also unsubscribe at any time. There is no operation for “show me what I have subscribed to”, other than by inferring that from message updates.

Users are generally anonymous, i.e. the system does not collect any user information and does not even have a mechanism to determine if two subscriptions were from the same user. Specifically, there are no user accounts (edit: other than the subscription ID, which can be seen as part of an ephemeral user ID). The expected use case is that users subscribe to traffic news when they start on a trip, change their subscription if they change their destination, and unsubscribe upon arrival. Thus, subscriptions “live” for anything from minutes to hours, but typically less than 24 hours. Edit: Session expiration is still TBD. For practical considerations, poll intervals could be as long as 15 minutes, but there might be longer periods of inactivity. For “forgotten” subscriptions, expiration intervals would likely be several hours after the last operation.

The scenario I am mostly worried about is ID guessing, i.e. an attacker trying a random subscription ID to poll the service and/or change subscriptions. For the attacker profile, this suggests a script kiddie: an individual with the skill level of an advanced user who thinks it’s fun to annoy random strangers.

As for protection requirements:

• Confidentiality: traffic messages are by definition public (anyone can see them), but a user’s subscription data (which can be inferred from the messages received) may disclose their whereabouts and travel plans, and as such is non-public. However, an attacker would need to take extra steps to identify the user.
• Availability: if messages are “lost”, the user will miss new traffic messages and end up in a traffic jam they had hoped to avoid, or taking a long detour to avoid a traffic jam which no longer exists.
• Integrity:
  • An attacker could unsubscribe a user (violating availability), though that would be apparent on the next poll: the service would reply “susbscription unknown” and the user could simply re-subscribe, at the cost of getting a full feed rather than a differential one (along with the related bandwidth usage).
  • An attacker could poll the service: the related update feed would be delivered to the attacker (violating confidentiality) and the victim would not see the changes (violating availablility), unless the affected messages change again before the victim polls the service.
  • An attacker could alter a user’s subscription: either to a much smaller area, which is equivalent to suppression of messages (confidentiality) but harder to detect than a rogue unsubscribe operation, or to the whole world, causing the user to be flooded with messages, consuming the user’s bandwidth and processing capacities. Depending on what the attacker has subscribed to, this may be much harder to detect than a rogue unsubscribe operation.

I would assume that the best defense here is to keep the IDs as random as possible (i.e. any two possible IDs are equally likely to occur) and above a certain length.

Questions:

• How long would a subscription ID have to be in order to make guessing a valid (though random) subscription ID unfeasible for the kind of attacker profile I have in mind?
• Have I missed anything (that you would be able to name)?

Answer 1

If you have space to store it, consider a standard data structure like a UUID4. These are generated randomly and are 128 bits, or 2^128 different possibilities.

That’s enough for your app to generate a unique reference for every gram of mass that makes up planet Earth, for every person currently alive on earth (2^128 / 2^92 / 6 billion).

Brute forcing the UUID4 space is impractical, and offers sensible security with the benefit of widespread support in programming languages and databases.

It should be noted though that using UUID4 is only as strong as its underlying random number generator, you can see a discussion on that in this question. You should take care when choosing an implementation for your project, if you are going to use UUID4 for this use case.

If you need a slightly shorter value, or something that uses can type, consider a secure random generator that provides URL safe output, such as Python’s secrets.token_*.

Answer 2

You ask the wrong question.

^{Source: Randall Munroe, xkcd/1567, licensed under CC-BY-NC 2.5}

Right now, the problem you are facing is that you try to make ice by spraying a hose into your freezer and then slamming it shut. The question you ask is "What kind of hose attachment is recommended when making ice?"

How to prevent vulnerabilities by design

Right now, when a user registers and subscribes to your service, they receive a subscription ID. A much better system was to give your user a way to authenticate to the API, such as OpenID.

This way, the user can provide a token, which would authenticate the user to you. If you implement the system correctly, using short-lived authentication tokens and long-lived refresh tokens, then your user only needs to authenticate once to keep using the API.

In your API, instead of making an endpoint like /subscription/<id>, make an endpoint like /subscription/me.

The API would receive the user's authentication token, and would be able to see which user was subscribed to which services. The endpoint can't be abused by an attacker to gain information about individual people and their subscriptions.

Answer 3

Without going into possible design or architecture changes, here are some thoughts:

• How many simultaneous subscriptions do you expect to have on average, and at peak times? Are subscriptions instantly destroyed after they're no longer used (i.e. is there a process for this?) or do they expire/timeout after a while? This will suggest how likely it is that a random guess hits a valid subscription ID;
• The risk of someone guessing a valid ID is inversely proportional to the key space as you rightly pointed out. A simple string can carry an immense key space, and depending on the service and type of client side code, it won't be do difficult to make them very very long (works if generated automatically and not required to be typed manually);
• The impact of someone guessing a valid subscription ID is limited to the user that subscribed originally. There are ways to detect this happening (which are not guaranteed to work). In addition, even with anonymous access you could use server side session identifiers to check how many clients are accessing each subscription - this may or may not work depending on the use case;
• The interest of an attacker spending effort into guessing valid subscription IDs is also relative - essentially limited to causing denial of service to the user, considering that all the information available in a subscription is public;

I'd estimate the likelihood of attack is low and so is the impact of a successful attack.

With all this in mind, an UUID4 will give you a key space roughly equivalent to a 24 character string, which is ~10³⁶ combinations.

Does this answer your question? Maybe not if you were hoping for a number, although that number though it's up to you to estimate.

Answer 4

Your remark "there are no user accounts" is a misconception.

When you rewrite your question and replace each occurence of the phrase "Subscription ID" with "username + password" you will understand that your subscription is in fact an user account generated by your system.
Just because you combine the "username + password" into one string and name it "Subscription ID" and you generate it in stead of ask the user for it does not change anything.

This way your question reduces to 'how can I create an unguessable password" which is discussed in many other places.