TeleTAN length should be sufficiently long to prevent brute-force attack (guessing an active TeleTAN)

[cascremers]

At the moment, the TeleTAN length seems to be flexible. However, it is important this is long enough to prevent brute-force guessing attacks on active (Tele)TANs. Computing the attack probability involves determining the likelihood of success of each guess (where failure is defined as the guess being different from all the currently active TeleTANs), and then considering the number of guesses an attacker can perform per second. Note that it may be very hard to do effective rate limiting on guesses in this deployment scenario, which gives the attacker more power.

[MalteJ]

+1

[tklingbeil]

Currently, the teleTAN is configured to be 7 characters long, the 55 possible characters are configured here. This gives us 1,522,435,234,375 possible teleTANs.

• Our teleTANs will be short-lived (currently configure to one hour here).
• We only expect a limited amount of them being active (as the teleTAN approach is only a fallback) at any given time - my current guess is something ~200 teleTANs being active at the same time
• The service will be protected against brute force attacks, so even 100 tries per seconds is probably a number that cannot be achieved by an attacker

Let's say our protection would let all of those requests through (which it shouldn't), within an hour (the validity of our teleTAN), the attacker would be able to make 360,000 guesses.

Our 200 active teleTANs only make up 0.000000013136848% of the possible teleTANs, meaning the probability that all of those requests within an hour are incorrect is 99,995%.

Would you consider that sufficient? Or do you think an attacker might be able to achieve a higher number of guesses per second?

[MalteJ]

The App only accepts upper case letters. Imho this makes sense as it will be very hard to communicate all those upper-case, lower-case letters via the phone. I think we should use the TELE_TAN_ALLOWED_CHARS minus lower-case letters. Further we may increase the TAN length a little bit (e.g. 12 letters).

[alstiefel]

As per specification only upper case letters are allowed (see https://github.com/corona-warn-app/cwa-verification-server/blob/master/docs/architecture-overview.md#core-entities)

[MalteJ]

Without upper case letters I count 31 different chars. 55^7 = 1.2 * 10^12

31^7 = 27,5 10^9 31^8 = 853 10^9 31^9 = 26.5 * 10^12

I recommend to add two more characters to the TeleTAN. Imho we should have a length of 9 chars.

[alstiefel]

The complexity of teleTANs is still under review, we consider measures to increase complexity.

[janrueth]

I do not think that 100 tries per second is a sufficiently high nor realistic number.

According to the architecture document (Step 8, Fig 4 in solution_architecture.md), we are looking at a singular POST with some bytes of data, including HTTP+TLS+TCP this boils down to roughly 11 packets that an attacker needs to send, summing up to roughly 1400 byte (this can be lower if you omit a lot HTTP headers, but lets stay conservative). Of course, sending these packets depends on latency as this is a request/response model (on all layers) but when an attacker parallelizes, this is no longer a concern. Assuming 1400 byte, 100 tries per second translate to 140kB/s which is not a lot, given today's connections. You would be able to reach ~8-9 times these bandwidths with a low-end vDSL connection (10Mbit/s upload). So more realistically you should assume something like 1k tries per second.

While I suppose that rate-limiting this API becomes necessary, it becomes more difficult when an attack is distributed and a service should still be guaranteed as:

1) the tries per second can be arbitrarily high, 2) correlating a distributed attack and dividing a group into attackers and benign users is hard.

As there seems to be no prerequisites to performing a POST to /registrationToken using a TeleTan, I can't see how a server can effectively protect against a distributed attack while not denying the service itself.

A common way to solve this problem is to shift load from the server to the client. For example, you could require the client to solve a cryptographic puzzle (see HIP DEX, or see bitcoin mining (specifically pooled mining) for a more recent/buzzwordy example) before being eligible to post a TeleTAN + the puzzle's solution (that the server can validate easily). This would also allow to dynamically react to increasing load (distributed attack) by adjusting the puzzle's difficulty when facing increased request volumes while significantly lowering the per user throughput. There are also other ways to ensure this if captchas or push notifications are an option (which I'm uncertain about).

This has close to no impact for an honest user but significantly challenges the ability to bruteforce the TeleTan for a single user, and with proper adjustments will also be able to challenge distributed attacks assuming that there is not infinite computational capabilities at the attacker's end.

[tklingbeil]

Thank you for your input!

We have changed the length of the teleTAN to 10 characters (9 + 1 "checksum") - uppercase characters (minus O,I,L) and digits (minus 0,1).

With 10,000 tries per second and 1,000 concurrently active teleTANs in the system (which is most likely way too high, as the teleTANs are only valid for one hour and most users will probably enter them right away), we get a probability of 0.14% that an attacker is able to guess a valid TAN.

In reality this number is probably lower.

[corneliusroemer]

I'm not sure @tklingbeil's number stack up against @janrueth's scenario of parallelised attack.

With 10,000 tries per second and 1,000 concurrently active teleTANs in the system (which is most likely way too high, as the teleTANs are only valid for one hour and most users will probably enter them right away), we get a probability of 0.14% that an attacker is able to guess a valid TAN.

That means one attacker needs only 1000 parallel instances and 1 hour to get a registration token. Or 1 instance and 1000 hours (that is a month). That's not as hard as it sounds. A few raspberry Pi's and you're done in a week - enough to quarantine anyone you want in conjunction with the abuser story #306.

Have you implemented rate limiting and brute force detection on the server side now?

I'm not sure it was a good idea to close this immediately without further discussion. A similar but less well reasoned issue has been opened again #275. It would be better to continue the discussion here where there's all the information.

[janrueth]

Thanks for digging this up again.

Recent news reports (sorry I don't have a source at hand, I believe I heard it on the radio (DLF)) also suggested that the technical readiness of some players (Gesundheitsamt) causes them not to be able to hand out QR-codes (yet?). Does this change the assumption of the number of tele tans in use? Is there a publicly accessible view on the system state, i.e., number of people tested positive vs. number of people having entered it in the system via QR-code vs. number of people having entered it via tele-tan vs. number of QR-codes issued vs. number of tele TANs issued? This should likely not be a live view such that an attacker does not gain information when an attack is feasible.

Such a view would certainly enable to better judge the attack surface and also provide a neutral source of information how the system is actually used :)

Coming back to the rate-limiting: Since the app is a national app, limiting the API access to people with an IP from Germany or the European Union might further limit the attack surface (even though I'm personally not a fan of geoblocking and it's limitations).

To reiterate on the attack model that I had in mind writing the comment:

1. To have a meaningful impact, it requires a large number of key that can be marked infected that have been in proximity of many users. Those could be obtained by placing BLE microcontrollers in heavily frequented areas and polluting nearby devices with these identifiers from these keys or by hacking users using the app and stealing their keys.
2. In the next step, the attacker needs to obtain a large set of IP addresses to perform the attack to circumvent simple rate limiting approaches, botnets can be rented for such purpose (however, the availability of botnets in certain geographical regions of course might challenge a geoblocked API, see above).
3. One must brute-force a TeleTan which one might actually be able to do when 1. and 2. were taken and no additional measures are in place.

Such an attack certainly requires a high level of power, e.g., a state's security agency. In my personal opinion this is not an attack that "some" random person would be able to do. Given such a powerful attacker, also my recommended crypto-puzzle approach starts falling apart as those can be solved by other computers not actually performing the requests.

However, given the type of attacker, it seems to me to be more likely that they take other attack vectors to compromise the system (e.g., social engineering of direct access to the systems, 0-day exploits, ...).

In my personal opinion: There should be sane rate-limits There should be a sane limit as to how many keys can be marked infected. Are the temporal keys linked, i.e., would it be possible to know that two keys belong to the same person given another input that is only shared with the system but then not made public? then one could make further checks regarding hacked phones...

If this is given, I personally would think the attack surface here is so limited that there is not really much that needs to be done.

[rec0de]

Let's try throwing some math at this to get a hopefully more realistic estimate of brute-force cost:

At the height of the first wave of infections in Germany, there were ~6.000 new cases per day. Assuming 80% adoption of the CWA in the entire population (this, unfortunately, is unrealistic since smartphone adoption alone is at ~80% in Germany as of 2018) and a 50/50 split between QR-code and TeleTAN usage (this is pure speculation on my end), we get 2.400 TeleTANs per day.

Now let's assume the average user enters their TAN 30 minutes after receiving it and that TAN generations spread out evenly over a 10 hour period every day (not entirely realistic but should be the right ballpark). This gives us an estimate of (2.400 TANs / day) / (20 half-hour time slots) = 120 TANs active at any given time.

With 31^9 possible TANs as given above, every brute-force request succeeds with probability 120/31^9 (there is no fixed keyspace to be exhausted because TANs are constantly created and invalidated), which means the first success can be expected after about 2 * 10^11 requests.

Now I don't know how many requests per second you can churn out using a single client, but more than 1.000 seems excessive, so let's go with that for 2 * 10^8 machine-seconds to first TAN (~56.000 hours).

All of this is assuming zero rate-limiting or DDoS protection - I'd be surprised if you could actually send thousands of requests per second over a prolonged period to an API that expects a daily (!) load of ~2.400 requests without being blocked / detected.