NSEC 2021 - Choir of Infinite Verses

Introduction

Choir of "Infinite" Verses was an interesting cryptography challenge part of NSEC 2021's CTF. Once we gathered an initial understanding of how the code work it was a matter of realizing the insecure implementation of RC4, specifically with nonce reuse, then abusing this configuration to craft and encrypt our own malicious cookie.

Challenges like this are nice in that they very quickly highlight the criticality of properly configuring cryptographic implemantions as the smallest mistake can completely break down the system.

Let's jump right in to the challenge details.

Code Analysis

Going the main page we are presented with captcha style challenge page. Apparently the monks of North Sectoria believe that if they solve enough captchas (seemingly over 10000000000000000!) they can achieve sainthood.

We also notice an interesting cookie value. The first portion is Base64 encoded, delimited by a | and then some form of counter. Unfortunately Base64 decoding the first portion did not provide anything immediately usable so went back to the page and explored the functions.

Sure enough entering a proper captcha increases the counter by 1. The other interesting aspect was that regardless of good or bad submission the second portion of the cookie would increase by 1. Even when refreshing the page (which also generated a new captcha) the counter increases by 1.

A thought crossed my mind that we would need to automate some form of captcha solver to finish this challenge. Thankfully before I started down this route I noticed at the bottom of the page a link to an interesting zip file.

Sure enough this ended up being the source code of the app! Excellent let's take a poke at how this works.

I had to sit down and go over the logic a few times to make sure I understood what was happening here.

Essentially when you load the page it is checking if you have a cookie set. If you don't have one it goes through make_struct to create a cookie and pass it back to you. The code passes three pieces of information to this function:

• letters, which seems to be a set of 10 random letters (captcha anyone?)
• 0, which gets zero filled to 24 character length, and finally
• cache['foo'], an internal variable representing the counter

The cookie has a form of:

base64(encrypted(hex(<letters>|<zerofilled-tries>|cache['foo']))|cache['foo']

Which means our initial cookie would have a value of:

base64(encrypted(hex(ettyrqtamc|000000000000000000000000|1))|1

When a cookie is set the app breaks down the values and attempts to check whether we have acheived sainthood yet or not. If so, it should gives us our flag recognizing our saintly status.

RC4 Theory

Now that we have a better understanding of what the app is doing, we need to dive a bit further into the encryption/decryption components. Unfortunately because this encryption component we will not be able to arbitrarily modify the values of the cookie... or so it currently seems...

Alright we are working with RC4 encryption.

Stepping through the configuration we assume (although I never actually tested!) that the key has been changed to something more appropriate for the event, and generates a nonce for the RC4 keystream by taking the current counter, modulus 2048. Oh ho... so essentially a Keystream reuse every 2048 values of the counter. Interesting...

Before we go straight into the solution we need to understand how a keystream reuse is bad news in RC4. In this case we know the plaintext structure and value, and we know the ciphertext.

This stackexchange post does a great job going over how keystream reuse can be leveraged.

The RC4 keystream is generated by a "key" - \(KS = RC4(k)\)

Where in this case our key is both the encryption key and nonce concatenated together and SHA'd. Once the keystream is generated our ciphertext is created by XOR'ing our original message with the keystream.

\(C = M ⊕ KS\)

Since we already know the full plaintext and the final ciphertext we can XOR ciphertext by our plaintext and get our Keystream for this specific nonce.

\(KS = C ⊕ M\)

We do not have a way to extract the exact key from this setup, but do we need to?

In theory for any given page refresh we can take presented captcha text, our current tries amount, and the ctr and craft our own malicious cookie. Since we have the keystream that would be used at the ctr+2048 attempt we can craft the plaintext to include a value of tries higher than the threshold, pass along the provided captcha letters at that point, and encrypt the result using the previously captured keystream.

Injecting Crafted Cookie

By this point we were around the 3577 range of counters. With the plan ready I captured the information required, computed the keystream, and prepped the malicious cookie structure. All that remained was refreshing the page 2048 times to get us back to the same keystream.

The most stressful part of this process was making sure I didn't accidentally go over 2048 refreshes and have to start the entire process over. Carefully I refreshed until the 5625'th counter and took note of the new letters that were generated - qavlgsmniv. With this I went through the cookie generation using our keystream.

All that is left at this point is to modify our cookie in Firefox and either refresh or submit a captcha.

Summary

This was definitely a fun challenge that illustrates the sensitivity of cryptographic solution implementation. By incorrectly configuring the nonce, and ultimately reusing the same keystream every 2048 iterations we did not even need the encryption key to arbitrarily control cookie values. Maybe next time they can hire use North Sectoria magicians to configure their systems!

As always thanks folks, until next time!