## Intro

So maybe I haven’t written a blog post in a while, but I was able to make time for Nahamcon 2023 where my team got 35th! I managed to full solve the cryptography category, and while it wasn’t terribly difficult, there were a number of math concepts that showed up during the challenges that I thought were good enough for writeups. RSA Intro and Outro covered some RSA basics plus a little bit of algebra. Just One More was a small exercise in solving systems of linear equations. ForgeMe1 and ForgeMe2 were both related to hash length extension attacks. Finally, Signed Jeopardy was about Nintendo trivia and ECDSA nonce reuse.

## RSA Intro

### Description

`What *is* RSA? Really Spicy Applesauce? Ridiculously Smart Alpaca? Random Squirrel Alliance? Nope, not at all. Just some dudes who made a cool public-key cryptosystem!`

Author: Gary

### Challenge

We’re given the output of the below source code.

Usually, when an RSA challenge is structured like this, the parts are usually related by some common relations or variables. However, in this case, we’re basically given three distinct RSA challenge, all of which are classic examples of the misuse of RSA.

- In part 1, we encrypt the message in the normal RSA procedure, but instead of giving the normal public key of $(e,n)$, they give us $p$ and $q$, which is a big no no. Knowing the factors that make up the modulus lets us just make the private key.
- In part 2, we encrypt the message with an exponent of $3$. This is not immediately a
*horrible*thing, but the size of the message is also fairly small, and the size of the modulus is way bigger, which is why we can solve this. - In part 3, we break up the last third of the flag into even smaller pieces and encrypt with a small modulus. On paper, nothing is immediately insecure here, but the actual modulus is so small that a computer can just factor it instantly.

There is not much left to discuss here, this challenge was rated “easy” for good reason.

### Solution

As mentioned earlier, for part 1, we can directly compute the private key. To calculate it, we need to solve the below congruence for $d$:

$\begin{aligned} ed \equiv 1 \pmod{\phi(n)} \end{aligned}$The $\phi(n)$ is actually Euler’s Totient Function, which computes the number of integers less than $n$ that are coprime to $n$. If we know that it’s a product of two primes, we can simply compute $\phi(n) = (p-1)(q-1)$. From there, we can let the Python take over and compute the private key and do the decryption ($m \equiv c^d\pmod{n}$).

For part 2, we don’t have the factors. However, we’re only cubing the input, which is significantly smaller than a 2048-bit modulus. The whole point of using the modulo operation in cryptography is that the inputs wrap around and become hard to traceback. A small exponent means we don’t even wrap around the modulus to begin with.

For the final part, the modulus is only ~48 bits long, which really isn’t that large as far as computers go. For context, the current standard for RSA is to use a 2048-bit, or even a 4096-bit modulus if necessary. We could be extra and use fancy math to factor the number for us, or we could just use good ol’ factordb and get the needed numbers.

All together, our final script looks like this:

**flag:** `flag{361862d054e2a9abe41cc315517cfa31}`

## RSA Outro

### Description

`I didn't feel like fitting this one in the RSA Intro, so here is an RSA Outro!`

Author: Gary

### Challenge

We’re given the output to the below code.

### Solution

This challenge is a pretty standard use of RSA, the key difference being the relationship between $p$ and $q$. The link in the source code has some good background knowledge, but we don’t really need to know it to solve the challenge. Here, we generate random 512-bit primes and only stop generating when $p = 2q + 1$. In secure implementations of RSA, you do not want your primes to have some algebraic relation, because it’s divulging unnecessary information. In this case, recall that $\phi(n) = (p-1)(q-1)$. Knowing a relationship between $p$ and $q$, we can actually construct an equation to solve for $q$.

$\begin{aligned} \phi(n) &= (p-1)(q-1) \\\\ \phi(n) &= pq - p - q + 1 \\\\ \phi(n) &= (2q+1)q - (2q+1) - q + 1 \\\\ 0 &= 2q(q-1)-\phi(n) \end{aligned}$We can solve this equation either using the quadratic formula, or by using a library like sympy to solve this symbolic equation. Once we’ve recovered $q$, finding the other numbers follows a similar pattern to what we discussed in the previous challenge.

**flag**: `flag{8b76b85e7f450c39502e71c215f6f1fe}`

## Just One More

### Description

`Just one more?`

Author: Gary

### Challenge

Once again, a static challenge.

When I solve cryptography challenges, one thing that helps me is translating source code to actual math, so it’s easier to process. Here, we’re generating a list of random numbers as long as the flag, and generating various sums. The corresponding indices of the random numbers and the flag are multiplied together, and then added. Afterwards, the list of random numbers is rotated to the right by one.

Let’s call each element of `arr`

$r_i$, each character of the flag $f_i$, and each resulting sum as $s_i$,
where $i$ is the index. We can then rewrite what this code is generating:

What this is, now, is not some weird for loop, but just a system of linear equations, which we can actually solve.

### Solution

If you’ve only ever taken an algebra or even a calculus course, systems with more than three equations can seem daunting. However, when you study Linear Algebra, finding solutions can feel almost trivial when you have computers. Knowing the random numbers, we can treat those as coefficients, and rewrite this system as a matrix:

$\begin{bmatrix} r_1 & r_2 & r_3 & ... & r_{38} & s_1 \\ r_{38} & r_1 & r_2 & ... & r_{37} & s_2 \\ r_{37} & r_{38} & r_1 & ... & r_{36} & s_3 \\ \vdots & \vdots & \vdots & ... & \vdots & \vdots \\ r_3 & r_4 & r_5 & ... & r_2 & s_{37} \end{bmatrix}$Each column represents a variable, in this case, the unknown values of our flag. From here, we want to transform the matrix into what’s known as reduced row echelon form (RREF) without changing the solution of the system, because that form (ideally) has 1’s along the diagonal and zeroes everywhere else. This means whatever is in the rightmost columns would be the solution to our system.

The primary way we can take a matrix and put it into RREF is through Gaussian Elimination, where we only use **elementary row operations** (i.e. things that don’t change the solution to the system) to slowly work our way to RREF. This could be swapping rows, rescaling a row, or adding rows, all of which preserve the original solutions. This explanation is a little bit of an oversimplification, so reading some of the hyperlinks here might give a fuller explanation.

Regardless, we’re not in math class, and we can do this pretty quickly with computers. Using SageMath, I can build a matrix like we described, and use the `Matrix.rref()`

function to do all of this computation for us.

However, if we check the last column of this matrix, we see that the numbers are a bit bigger than what the flag should be (output omitted because it’s a lot). Doing some further investigation, it appears our matrix was reduced to something along the lines of:

$\begin{bmatrix} 1 & 0 & 0 & ... & k_1 & s'_1 \\ 0 & 1 & 0 & ... & k_2 & s'_2 \\\\ 0 & 0 & 1 & ... & k_3 & s'_3 \\ \vdots & \vdots & \vdots & ... & \vdots & \vdots \\ 0 & 0 & 0 & ... & s'_{37} & s_{37} \end{bmatrix}$(Note that I’m using new variables since the values are different from the original matrix)

The reason that the reduced matrix isn’t as “clean” is because in the original challenge, we only made 37 sums, instead of 38. If we had all 38, this challenge would be over instantly. However, if we rewrite this matrix as a list of equations again, we see that they’re all in the form $f_i + k_if_{38} = s'_i$. However, we know the flag format already, and that the last character is just ’}‘. Knowing this, we can just take the last column, minus the column of k’s times the ASCII code for ’}’, and fully recover the flag.

**flag:** `flag{aad9ba9b3fdfa4cc6f7e2e18d0dcbbab}`

## ForgeMe 1 and 2

### Description

**ForgeMe1**: `Can you break my hashed-based MAC? Below are some resources that may be useful.`

**ForgeMe2**: `Can you break my hashed-based MAC again? Below are some resources that may be useful.`

Author: Gary

### Challenge

These were technically two separate challenges, but ForgeMe1 was just an easier version of ForgeMe2, so I’ll only be talking about ForgeMe2, and you can probably figure out ForgeMe1 instantly. Both challenges were dynamic, so below is the server code for ForgeMe2.

In cryptography, a **Message Authentication Code** (MAC) is a construction that uses a secret key to enable checking the authenticity of a message, that is typically associated with symmetric encryption schemes. The output of a MAC, called a **tag**, is sent with the message. The recipient will then compute the tag themselves, and if the received tag does not match the computed tag, the message is rejected as forgery.

This server is a MAC oracle with 2 main functions:

- Option 1 lets us input a message, and the server will output a tag. In particular, our tag is the output of $\texttt{SHA-1}(K \vert \vert m)$, where $K$ is a key of random length from 10 to 120 bytes.
- Option 2 lets us input a tag and a message, and the server will tell us whether or not that combination of message and tag is valid. That message must contain a phrase generated by the server, and the link to John Hammond’s YouTube challenge.

The third option on the server is the goal of the challenge. Upon connecting to the server, we’re given a random phrase, and we’re supposed to forge a tag that start contains the random phrase, and the link to John Hammond’s channel. This would be as easy as asking the oracle for the tag and then just giving it back, but the server keeps track of our queries, so we cannot give it a message and reuse that tag for getting the flag.

### Solution

The key to this challenge is that the MAC construction is fundamentally flawed with its choice of hash function. Although SHA1 has long been considered insecure due to the discovery of multiple collisions, the issue lies in **iterative hash functions**. SHA-1 is based on the Merkle–Damgård construction, which will break up a message into blocks, apply the compression function to the first block, and then uses the result of that in computing the compression function of the next block, until we’ve gotten through the whole message and produced an output digest. Below is a diagram of this:

^{Courtesy: Wikipedia}

(If this hash talk has you confused, here’s a link on Wikipedia to catch you up to speed: link)

The internals of SHA-1 beyond this are relatively unimportant, what matters is that the output hash is just whatever the internal state of the hash was whenever we ran out of message/padding to use. This is where the **hash length extension** attack originates. We can treat the hash/tag as our new starting state, append some stuff to the message that was hashed, and run the function from there. Recall that MAC was computed by doing $\texttt{SHA-1}(K \vert\vert m)$. Using the hash length extension attack, we can take this result and forge a tag for $\texttt{SHA-1}(K \vert\vert m \vert\vert m')$, where $m'$ is a message that we add.

Normally, writing this yourself is a fun exercise and really helps you understand the concepts. However, iagox86 has already written a pretty solid tool called hash_extender to do most of the heavy lifting for us. As of writing, there’s a weird error in the Makefile having to do with OpenSSL 3.0, but this fork from Michele0303 fixes it. I’ll clone the repository to my machine, and use `make`

to build the program.

At this point, ForgeMe1 has been solved. You just use this tool to forge a hash. In ForgeMe2, however, we have a problem where we don’t know the size of the key that’s been prepended. If we don’t know the size, we can’t accurately compute the padding needed to forge the tag. Luckily, the server gives us 100 queries, so we can just brute force the size of the key until the server returns true, and once we know that size, we can submit a correctly forged tag to get the flag.

**flag (forgeme1):** `flag{4179e0a0f6ddc273a8a18440c979bbb7}`

**flag (forgeme2):** `flag{257843b6ca2a7678857f9caf21dd92f0}`

## Signed Jeopardy

### Description

`Let's play a special form of Jeopardy involving ECDSA!`

Author: awesome10billion

### Challenge

This one was also a dynamic challenge, this time written in SageMath.

Similar to the previous challenge, the goal here is signature forgery. In this case, we are asked questions about Nintendo and their associated franchises, and we’re only given the signature of the answer. We’re allowed as many questions as we want, but ultimately, we need to forge any message to get the flag.

### Solution

We’ve talked about elliptic curves here before, but not necessarily using them to sign messaged. The Elliptic Curve Digital Signature Algorithm (ECDSA) is a variant of the Digital Signature Algorithm that uses elliptic curves, much like how elliptic curve Diffie-Hellman is a variant on the original Diffie-Hellman algorithm. The algorithm is described below:

- Calculate a hash of a message, call it $h = \texttt{hash}(m)$
- Randomly pick a
**nonce**($k$) , in this case, a number from $1$ to $n-1$, where $n$ is the order of the curve - The first part of the signature, $r$ is computed as the x-coordinate of the point $k*G$, where $G$ is the generator point on the curve
- The signature is computed as $s = k^{-1}(h+rd) \pmod{n}$, where $d$ is the private key. The resulting signature is $(r,s)$.

This, assuming the curve is secure, is a very secure way of signing messages. However, as with all CTF challenges, there’s a fatal flaw with the implementation we have in this challenge. A nonce is a *“Number used once”* is meant to “seed” our algorithm, and can absolutely be made public, but should **only ever be used once**. The server in this case is reusing a nonce, and knowing that, it only takes two valid signatures to completely reverse the private key, which will let us sign arbitrary messages.

We can find the nonce like so: $\begin{aligned} s_1 - s_2 &= k^{-1}(h_1 + r_1d) - k^{-1}(h_2 + r_2d) \\\\ s_1 - s_2 &= k^{-1}(h_1 - h_2 + d(r_1 - r_2))\\\\ s_1 - s_2 &= k^{-1}(h_1 - h_2) \\\\ k &= (h_1 - h_2)(s_1-s_2)^{-1} \end{aligned}$

The $d(r_1-r_2)$ disappears because we know $k$ is constant, so $R = kG$ will always be the same thing, making $r_1 - r_2 = 0$. Once we know the nonce, we can then find the private key by rearranging the equation for $s$ to be equivalent to $d$.

$\begin{aligned} s &= k^{-1}(h + rd) \\ ks &= h + rd \\ d &= (ks - h)r^{-1} \end{aligned}$A bit of jumping around with that work, we’re just moving variables back and forth until we’ve isolated $d$. The only challenge, then, is to make sure we’re getting the trivia right so we know what the message is. Luckily, the server gives us the public key, which we can use to verify our solutions, which I put in my script (because the difference between “SEATTLE MARINERS” and “THE SEATTLE MARINERS” killed me for at least an hour). I did steal the actual attack implementation from jvdsn, but that was more for speed and I was a bit lazy.

**flag**: `flag{a8168c41537604546394c13c8f4ef4b8}`

## Conclusion

Overall, had a fun time playing this year’s edition of Nahamcon. Honestly, the cryptography was not that hard, but I hope that for those reading, it was a good introduction to some of these attacks and using math.

Until next time!