International Cybersecurity Challenge 2022 - Trademark

If you can read Japanese, you can also check out this writeup by my teammate @xrekkusu.

Admins: “Like the demo days, all attack/defense services will be hosted on a linux machine as docker services.”

Player: “How many services are there going to be?”

Admin: “Four services total.”

Other admin grabs microphone “and this includes one windows service.”

Player: “Windows service running on a docker host??”

Admin: “Yes.”

Some time before September 2021 my friends @Lord_idiot and @daniao poked me to play a capture the flag competition where the winners would qualify for a trip to Athens, Greece to play even more CTF. After a few months of delays due to COVID, in June 2022 the three of us finally went down as part of the ACSC team to play in the International Cybersecurity Challenge 2022. It was a lot of fun to travel for the first time since the pandemic started and making friends with the rest of the Asian team. The competition itself was also exciting to boot.

One of my highlights was the Attack/Defense day where the ACSC team pulled together to come out tops for that day. There were four services on our vulnbox and I was working on the service “Trademark” together with @xrekkusu and @sin3point14, plus some help from @Moriarty who was on traffic analysis duty. It turns out that this service would become the most hotly contested service of the day.

Challenge source is available here if you want to try it out for yourself.

Investigating the “Windows” service

Competition day came and we get access to our vulnbox for 1 hour before the network is fully opened, after that comes 8 hours of A/D. The vulnbox is indeed running linux but one Dockerfile stands out among the rest:

# trademark/Dockerfile
FROM mcr.microsoft.com/dotnet/sdk:6.0-alpine3.15 AS builder
# ...
FROM mcr.microsoft.com/dotnet/aspnet:6.0-alpine3.15

Haha, so that’s what they meant by a “windows” service. We have source code for a .NET web service written in C#. Though .NET is often used with windows, the runtime is still cross-platform which lets us run these programs on a linux host. Thankfully it wasn’t some windows binary running in wine.

We can do some recon on the service by manually interacting with it:

• Trademark is a web application used to handle product licensing.
• Unauthenticated users can register a new user or sign in as an existing user.
• Authenticated users can “create” products which comprise of a product name and some secret value to be stored. Each created product has a “product ID” and 5 “license keys” made of 28 uppercase alphabets and some spacing characters.
• Authenticated users can “redeem” products created by someone else and read the secret value if they have the product ID and a valid license key

We get some more insight on the internals by looking at the HTTP requests made by the web client, either through browser devtools or a HTTP proxy:

• Authentication is done with an access token and Authorization: Bearer headers.
• When creating a product, the API request returns parameters for a “public key” in addition to the 5 “license keys”. The public key is made of a large integer mod and a list of integers poly (which should already start ringing some alarm bells).
• When viewing a product owned by a different user, we can read the same parameters mod and poly before a “license key” is redeemed.

With this surface-level analysis, it looks like we have a web / crypto service to exploit and harden.

Rolling someone else’s crypto …

The crypto logic of the service is mostly contained within trademark/Services/LicenseService.cs.

The function GenerateLicenses() looks interesting:

public async Task<Tuple<Polynomial, BigInteger, List<string>>> GenerateLicenses(string seeder, int n)
{
    var module = await _openssl.Prime(1024);
    var poly = MultiplyPoly(
        new Polynomial { BigInteger.Zero, BigInteger.One },
        new Polynomial { BigInteger.Abs(new BigInteger(_sha512.ComputeHash(Encoding.ASCII.GetBytes(_secret + seeder)))), BigInteger.One },
        module
    );

    var licences = Enumerable.Repeat(0, n).Select(_ => RandomBigInteger(128)).ToList();
    poly = licences.Aggregate(poly, (current, licence) => MultiplyPoly(current, new Polynomial { -licence, BigInteger.One }, module));

    return new Tuple<Polynomial, BigInteger, List<string>>(
        poly,
        module,
        licences.Select(LicenseToString).ToList()
    );
}

Translated to math, the license system is backed by a polynomial in a prime field.

We can also take a look at VerifyLicense() in the same file:

public bool VerifyLicense(Polynomial poly, BigInteger mod, string key)
{
    if (!Regex.Match(key, "^([A-Z]{7})-([A-Z]{7})-([A-Z]{7})-([A-Z]{7})$").Success)
    {
        return false;
    }

    var n = key.Replace("-", "")
        .ToCharArray()
        .Select((ch, i) => BigInteger.Pow(26, i) * (ch - 0x41))
        .Aggregate(BigInteger.Zero, (current, n) => current + n);

    return EvaluatePoly(poly, n, mod) == BigInteger.Zero;
}

A valid “license key” for some public $f(x)$ is any string in a license format that when parsed as a base-26 integer evaluates $f(x)=0$. $f(x)$ is determined by coefficients poly and the modulus mod of the “public key”.

… is a bad idea

Once the network opened at 1:00 game time, we see that the game system /flags endpoint provides a list of product IDs. We can make an educated guess that we need to leak the secrets of judge-planted products without knowing the original license keys.

The first crypto vulnerability the team discovered was found by @xrekkusu at 1:14. After understanding the polynomial cryptosystem he found that the license key AAAAAAA-AAAAAAA-AAAAAAA-AAAAAAA would always be valid!

@sin3point14 rushed out a patch by 1:25 by adding a regex check which rejects the license key. Thankfully he was working on a windows host machine with visual studio (the C++/C# one, not VSCode) already set up, so patching went very smoothly.

diff --git a/Services/LicenseService.cs b/Services/LicenseService.cs
index 08b6aa5..73ccdec 100755
--- a/Services/LicenseService.cs
+++ b/Services/LicenseService.cs
@@ -107,6 +107,11 @@ public bool VerifyLicense(Polynomial poly, BigInteger mod, string key)
             return false;
         }

+        if (Regex.Match(key, "^AAAAAAA-AAAAAAA-AAAAAAA-AAAAAAA$").Success)
+        {
+            return false;
+        }
+
         var n = key.Replace("-", "")
             .ToCharArray()

We eventually made a working exploit script by 1:34 game time. Though the exploit itself is simple, the 20 minutes from discovery to exploit was spent understanding the auth system and making the script work with the team’s ExploitFarm exploit scheduler. This gave us our first flags of the A/D game.

Why did this exploit work? One line of GenerateLicenses() looks very suspicious:

public async Task<Tuple<Polynomial, BigInteger, List<string>>> GenerateLicenses(string seeder, int n)
{
    // ...
    var poly = MultiplyPoly(
        new Polynomial { BigInteger.Zero, BigInteger.One }, // !!!
        // ...
    );
    // ...
}

The license generation function makes a polynomial with $(x+0)$ as a factor, so $x=0$ is a trivial root. The license AAAAAAA-... when converted from license key to integer is $0$, which means the validation function will confirm that this license is indeed a root of the polynomial and give us the flag. Though the “most correct” way to patch this would be to remove the backdoor from the key generation function, a regex filter was the simplest and fastest patch against the attack given the information we knew at the time.

Depending on how familiar you are with CTF crypto, you might have already spotted the other vulnerabilities in the cryptosystem from the snippet. However, actually grokking the service from source code alone takes much more time (especially under competition pressure). For myself it took until the 2:23 mark to understand the polynomial system and realize that you can actually solve the roots of polynomial in prime ring problem quickly with sagemath .roots(), which is probably backed by Cantor-Zassenhaus or some similar algorithm.

A working exploit backed by sagemath .roots() was ready by 2:44 and more flags were being captured. However, the script itself was occasionally timing out. One reason is because ExploitFarm’s automatic script runner spawns a new script instance for each game tick and each target vulnbox, which means a lot of time is wasted by starting so many instances of the sagemath interpreter. The math itself also requires a decent amount of compute power, taking up to 5 seconds per .roots() call. My solution was to horizontally scale the exploit to my teammate’s spare laptop (thanks @sqrtrev 🙏). Installing sagemath from scratch took some time¹, but eventually we were taking flags from all other teams within the hour.

Though our team didn’t discover it during competition time, it turns out that the polynomial was also vulnerable to sagemath .small_roots(). 5 licenses would produce a 7 degree polynomial taken 1024 bit modulus; Coppersmith’s small roots would leak the 128-bit roots easily, well below the algorithm’s limit of $N^{\frac{1}{d}}$, around 140 bits.²

The best offense is a good defense

Though we had progress on both attacking and defending crypto vulnerabilities, we were still bleeding flags from trademark very early on. Once our vulnbox packet capture was set up and stable³, at 2:27 @xrekkusu found more suspicious traffic:

A request with a malformed request path and without any Authorization header seems to be leaking flag. This sounds like a failed permissions check somewhere in the service. We can look at the authorization code in the web service, specifically in trademark/Middleware/AuthMiddleware.cs.

private readonly List<string> _blacklist = new()
{
    "/api/login",
    "/api/register",
};

public async Task InvokeAsync(HttpContext context, ApplicationDbContext db)
{
    if (_blacklist.Any(context.Request.FullPath().Contains))
    {
        await _next(context);
        return;
    }

    var user = await FetchUser(context.Request, db);
    if (user == null)
    {
        context.Response.StatusCode = StatusCodes.Status401Unauthorized;
        return;
    }

    context.Items["user"] = user;

    await _next(context);
}

Any call to await _next(context) means the request is passed onto the rest of the web service. This happens either if (A) the request path contains one of /api/login / /api/register which should be accessible to unauthenticated users, or (B) if the user is already logged in.

The issue here is that the string is checked for if it contains one of the two paths from before. The exploit request from earlier smuggles the /api/login string in the URL query string. Once the /api/login substring is found the request is allowed to skip authentication, but the request is eventually handled by the /api/products/${productId}/download endpoint which leaks flag.

@xrekkusu wrote an exploit script at 2:35 which replayed this attack to other teams at and then made another patch at 2:47 which ensures that only whole string matches for the register and login endpoints are exempted for login checks, fixing this vulnerability. @sin3point14 also wrote a WAF filter into the auth middleware for good measure which was deployed by 3:31.

diff --git a/Middlewares/AuthMiddleware.cs b/Middlewares/AuthMiddleware.cs
index a73d6ee..4e10fb9 100755
--- a/Middlewares/AuthMiddleware.cs
+++ b/Middlewares/AuthMiddleware.cs
@@ -74,11 +74,16 @@ public AuthMiddleware(RequestDelegate next, HMacSigner signer)
     public async Task InvokeAsync(HttpContext context, ApplicationDbContext db)
     {
-        if (_blacklist.Any(context.Request.FullPath().Contains))
+        if (_blacklist.Any(context.Request.FullPath().Equals))
         {
             await _next(context);

Cherry-picking a patch

The earlier two defense patches deployed disallowed interactions with the service which were clearly malicious. Patching the licensing cryptosystem was going to be more difficult. Considering how the rest of our services were losing many points to uptime from denial of service exploits and bad patches, we wanted to be very careful when deciding what to change.

We made a few assumptions on the uptime checker script:

• Public key parameters (mod and poly) of products need to be available
• License keys when parsed should be a root of the public key polynomial
• We need at least five valid licenses

I came up with an idea within these requirements: what if we make the polynomial bigger? If we generate more licenses, the degree of the public key polynomial also increases and this may defend against math-based exploits. We made the following patch at 3:16 game time.

diff --git a/Controllers/ProductsController.cs b/Controllers/ProductsController.cs
index fba4580..9227aaf 100755
--- a/Controllers/ProductsController.cs
+++ b/Controllers/ProductsController.cs
@@ -14,7 +14,7 @@ namespace service.Controllers;
 [Route("api/[controller]")]
 public class ProductsController : BaseController
 {
-    private const int LicensesToGenerate = 5;
+    private const int LicensesToGenerate = 40;

     private readonly LicenseService _licenses;

This actually defends against the .small_roots() exploit which Team Europe had deployed by this point in the game, but we were not completely aware of it. The upper bound for solutions leaked by small roots would drop to an unusable $N^{\frac{1}{41}}$ of around 24 bits, preventing license keys from being recovered. Our stolen flag count stopped decreasing, the uptime check passed and both stayed that way into scoreboard freeze, so we were happy that this patch worked.

However, this was actually a poorly executed patch. Though we had already discovered the sagemath .roots() exploit, but this patch actually does not protect against it, and we did not verify it with our own exploit script. Surely enough, Team Oceania eventually discovered the .roots() exploit and they saved it until the scoreboard was frozen to deploy it against us. We had no idea our flags were being stolen until after the competition was over!⁴

One thing that surprised me was that no other team copied our fix for this exploit despite it being live for more than half of the game. Unlike the previous patches that makes requests silently fail, this modification to our key generation program is actually very visible. It would have been very easy for opponent teams to manually interact with our vulnbox and notice that what used to be an 8 element array is now more than 40 elements long, yet our uptime check still passes. Thankfully for us, nobody else noticed in time.

Arms race against a packet filter

For most of the first half of the game, Team Europe was in the lead for this service, which also made them a high value target with their flags worth effectively double that of other teams. We really wanted to make sure their flags were streaming in, but it turns out it would take a lot of effort.

We noticed early on that some of our scripts were successful for the first 10 to 20 minutes after deploy, then eventually report timeouts when run against the Team Europe vulnbox. It appears that they had set up packet filtering for suspicious incoming HTTP requests, which means we have one more layer of protection to circumvent. I forked the .roots() exploit to a special version just for the Team Europe vulnbox with modifications for avoiding their packet filter. Each time I got pinged by my teammates that the flags stopped coming in, I had to fix the exploit by:

• 1:35: Overwriting User-Agent from my installed python-requests/2.26.0 to match the uptime checker’s python-requests/2.28.0
• 5:39: 20 character username and passwords was blocked, change to 24 characters instead (in reality the uptime checker systems uses anywhere from 16 to 24?)
• 5:??: Bulk copying headers from my Chrome devtools and replaying them for any request
• 6:40: Removed invalid Content-Type: application/x-www-form-urlencoded headers from GET requests that I accidentally added with the previous change
• 8:30: Detached the exploit script from the ExploitFarm scheduler and started manually running the script every 10 minutes to make sure the traffic signature was always changing
• 8:37: Chrome headers were blocked, did a fresh install of Firefox and copied request headers from there instead with a known working access token

Look what you made me do :|

For the last two ticks of the competition I also took the liberty to share a bit of my team’s writeup with the Europe vulnbox. Since I knew their traffic capture players were keeping close watch on request headers, I added some flavour text to the User-Agent string in my exploit script. Unfortunately I think these got filtered as well.

After everything was over, I could tell that this game of cat-and-mouse really made some people mad ;). But credit to Team Europe and their traffic analysis players where it’s due, they put up a tough fight.

A few of the Team Europe members shared their strategy with me after the competition. Their filter had rules which:

• Disallows HTTP headers User-Agent, Accept-Language, Accept-Encoding if requests indicated a different HTTP client / language preference (! sneaky) / compression schemes compared to the uptime checker
• Disallows requests based on order of headers
• Disallows requests based on application behaviour not observed by the uptime checker (e.g. uptime checker would use an access token from /api/login, not from /api/register, see above image)
• Disallows “too human” behaviour such as keyboard mash (“asdf”) or player handles for usernames and other form data

Some of these ideas are really creative and surprisingly effective. They have since open sourced their traffic analysis tool which looks really cool. I’m looking forward to trying it out for myself.

I brought the receipts

Here’s a play-by-play summary of what happened, reconstructed from the packet dump released after the competition.^{5 6}

Time	Team	Vuln
0:00:00	Vulnboxes online
?:??:??	Team Europe	🛡️ fix zero license key
1:00:00	Network open
1:07:26	Team Europe	⚔️ 🩸 pwn auth bypass
1:15:55	Team Oceania	⚔️ pwn auth bypass
1:16:05	Team Europe	🛡️ fix auth bypass
1:18:48	US Cyber Games	⚔️ pwn auth bypass
1:20:09	US Cyber Games	🛡️ fix auth bypass
1:25:04	CyberSci Team Canada	⚔️ pwn auth bypass
1:25:36	ACSC Team	🛡️ fix zero license key
1:34:43	ACSC Team	⚔️ 🩸 pwn zero license key
1:42:47	US Cyber Games	🛡️ fix zero license key
1:44:58	CyberSci Team Canada	🛡️ fix auth bypass
1:55:37	CyberSci Team Canada	🛡️ fix zero license key
2:14:36	Latam Team	⚔️ pwn zero license key
2:26:41	Team Europe	⚔️ 🩸 pwn small roots
2:35:11	ACSC Team	⚔️ pwn auth bypass
2:40:08	Team Oceania	⚔️ pwn zero license key
2:44:40	ACSC Team	⚔️ 🩸 pwn roots
2:54:47	CyberSci Team Canada	⚔️ pwn zero license key
2:57:02	US Cyber Games	⚔️ pwn zero license key
2:57:04	Team Europe	⚔️ pwn zero license key
2:58:07	ACSC Team	🛡️ fix auth bypass
3:26:27	ACSC Team	🛡️ fix small roots
4:20:08	Team Oceania	🛡️ fix zero license key
7:01:33	Latam Team	🛡️ fix zero license key
8:04:21	Team Oceania	⚔️ pwn roots
8:26:02	US Cyber Games	🛡️ fix roots
8:42:07	Team Oceania	🛡️ fix roots
8:48:09	US Cyber Games	🛡️ fix small roots
9:00:00	Game ends

The final attack/defence scoreboard can be found here.

Bloopers

• Team Europe discovered the auth bypass vulnerability at 0:51:56 game time, even before the network was open, but it took a bit longer until 1:07:26 to steal the first flag because understanding the game system /flags index and locating where the flags were planted takes time.
• There is evidence in the traffic capture that Team Europe were first to deploy an exploit script for the zero license key vulnerability at 1:18:05 game time. Unfortunately, they hardcoded their access token instead of deriving it from the login handshake, so they only got a bunch of permission denied errors instead of flag. That said, flags were probably coming in from the auth bypass script so it didn’t alarm them at the time.
• CyberSci Team Canada straight out deleted the public key from responses at the 4:20 game tick and reverted the change soon after.
• US Cyber Games came up with the idea to use a random number as modulus at the 4:22 game tick which would have patched the roots vulnerability, but their patch also produced invalid licenses. They eventually reverted their changes by the 04:38 tick.
• US Cyber Games’s fix for small roots was cheese. They made the modulus a 4096 bit prime which made the usual sagemath scripts solving for small roots / roots of polynomial modulo prime timeout due to the sheer size. However, the modulus is so large the polynomial can be solved over the integers instead and you still get the roots and the license key!

Lessons learnt

• Don’t overburden your vulnbox. Leave packet analysis / heavy lifting to your own hardware or even a cloud machine if possible.
• Prep your local environments. Waiting to install tools isn’t a good way to spend your time.
• Double and triple check your patches, especially if you already have working exploits.
• Get to know the uptime checker well. It’s the only way you can really avoid getting packet filtered, especially if you’re playing against someone who came prepared.

Retrospective

I was not expecting the A/D CTF to be this intense, but it was very fun to play. Somehow the ACSC team not only managed to come out top for this service, but we were able to top the leaderboard and come in 1st place for the Attack/Defense CTF. This made us 2nd overall after adding in the first day’s jeopardy CTF, which was way beyond my expectations coming into this.

Thanks to all my teammates from the ACSC team for being amazing to play with, as well as our coaches and sponsors for making the event possible. Same goes to the rest of the teams who played in the ICC and the organisers, it was a good game!

Lastly, if you are based in Asia and are interested in CTF, look out for the next edition of the ACSC qualifiers. You might get to go to the USA to play in the next ICC!