Getting stuck on a problem can hinder productivity. Sometimes, these problems can take hours to solve. Learn how to quickly progress using a rubber ducky....
For the past month I have been preparing to compete in the CSAW19 CTF challenge with a team of 3 other individuals. This month involved studying crypto systems in an attempt to learn as much as possible to solve at least one challenge going into the CTF. CSAW, for those unacquainted, is a highly prestigious cybersecurity event hosted by New York University. The CTF portion of CSAW consists of an online qualifier competition and the finalist competition in Brooklyn, NY. Both events run in standard Jeopardy style over the span of 36 hours. Competing in the event successfully is a mix of past knowledge of known vulnerabilities, ability to deduce vulnerabilities on the fly, time management, and teamwork. In this post I would like to detail my experience during the CSAW finalist CTF, including the challenges, the environment at NYU, and my experience in NYC and Brooklyn.
CSAW19 CTF Finalist Challenges
During the CTF I was able to solve one of the crypto problems and get very close to solving two others. This performance was better than I expected, knowing the caliber of the CSAW challenges and my small pool of experience with crypto CTF challenges. There was an interesting mix of crypto systems utilizing a mixture of known attacks and on-the-fly deduction attacks. I would like to reflect on two of these challenges to make pseudo-write-ups for future reference. In talking to the other competitors after the CTF ended, I was able to learn a lot about crypto systems for the future.
A link to the full repository of challenges can be found at: https://github.com/osirislab/CSAW-CTF-2019-Finals
Challenge #1: Macrypto - 250 points
This challenge absorbed most of my time during the competition. Unfortunately, I spent a lot of time reading and understanding the Rust source code. After reading the code I tried many avenues of solving the problem, most being dead ends. While I eventually solved the problem, the time I spent working on Macrypto would have been valuable for the other challenges. The lesson from this challenge is the requirement to recognize when a potential solution is a dead end.
The vulnerability in this challenge has to do with how the random number array a is generated and used throughout the program. During the execution, the user sends plaintext to the server and encryption is carried out by the program by accessing two values of the a vector using two indices i and j. These indices begin at zero and incremented with the following rule for each byte of the plaintext+flag:
$$i = (i+1) mod(256)$$
$$j = (j+a[i]) mod(256)$$
These indices are then added together, mod 256, to produce a third index k. The program then swaps a[i] and a[j]. Finally, the nth ciphertext byte is computed using the nth plaintext byte XORed with a[k]. This fact allows the attacker to recover values of the a vector by using known plaintext bytes. However, this avenue is a dead end as there is no way to recover the original a vector.
The vulnerability within this program comes from the method of swapping values in the a matrix. The program uses an XOR swap macro to move values of the a vector. The problem with this method of swapping is there are no safeguards for preventing duplicate values within the a vector. This means if the program attempts to swap duplicate values, they will XOR two values in a to 0. Then, the 0 values can create more duplicates due to XOR(b,0) = b. This propagates through the a vector, poisoning the vector. Eventually, the entire a vector will be filled with 0 and the ciphertext will be the plaintext.
For my solution, I waited for the poisoned vector to reduce the values to a point where the matrix state to return to a previous state (n). Knowing that a previous state was achieved, I could feed the n+1 ciphertext to the program to retrieve the flag. I did not check if this previous state was the point at which the a matrix was filled with zeros. Talking to other teams it seems like it may not have been, as my program took ~2400 iterations on average while others reported much higher iteration counts. The script for this challenge is shown below:
from pwn import * target = remote("crypto.chal.csaw.io", 1002) dix = 0 results =  target.sendline("A") ciphertext = target.recvline() results.append(ciphertext) while (len(set(results)) - len(results)) == 0: if(dix % 1000 == 0): print(dix) target.sendline("A") ciphertext = target.recvline() results.append(ciphertext) dix += 1 print("Total Tries") print(dix) for i in range(len(results)): if(results[i] == results[dix] and i != dix): print(results[i+1]) #print(target.recvline())
from pwn import *target = remote("crypto.chal.csaw.io", 1002)dix = 0results = target.sendline("A")ciphertext = target.recvline()results.append(ciphertext)while (len(set(results)) - len(results)) == 0: if(dix % 1000 == 0): print(dix) target.sendline("A") ciphertext = target.recvline() results.append(ciphertext) dix += 1print("Total Tries")print(dix)for i in range(len(results)): if(results[i] == results[dix] and i != dix): print(results[i+1]) #print(target.recvline())
Challenge #2: EZPZ - 400 points
I was close to solving this problem, but my understanding of Elliptic Curve Crypto hindered me from understanding the algebra required to find a solution. With that being said, let's learn some things about ECC!
Elliptic Curves (ECs) are implemented over finite fields of large prime numbers when used for cryptography. The message in this challenge was encrypted by finding the point on the EC which corresponded to the numerical representation of m, E(x = msg). The public key, pub, for this EC was a random point P multiplied by the private key (a large number) priv. The encryption method calculates three points based on a random number k:
$$C = k*P$$
$$cp = k*pub$$
$$pm = E(x = msg)$$
The return value of the function gives the points C and cp+pm. We are also given the result of this function when the flag is passed as the argument. So, the goal of the challenge is to recover pm for the flag's encryption point. Without any other tools, this problem is the discrete log problem for ECC. However, we are given a function sign() which allows us to feed a point from E and the function returns the point multiplied by priv. Again, recovering priv is difficult from this function.
Examining the encryption function more carefully reveals the significance of the sign function. As shown, cp is the public key multiplied by a random value k:
$$cp = k*pub = k*priv*P$$
If we could find the value of cp, we could easily recover pm as ECC has nice algebraic properties:
$$0 = P - P (associative addition)$$
$$(P + Q) + R = (P + R) + Q (associativity) $$
$$P + Q = Q + P (commutative)$$
Thus we can see that to recover pm we would have to compute:
$$pm = (pm + cp) - cp$$
We can see the relationship between cp and c is:
$$cp = k*priv*P = priv*C$$
$$cp = sign(C)$$
Thus, to solve the problem we pass the value of C to the sign function and subtract the resultant value from cp+pm. The x value of this subtraction is the flag. Luckily, sage has easy ECC implementation so these operations are as simple as copy and pasting. In the future I would like to integrate sage with my python environment so I could make a more elegant solution which interacts with the server directly, but here it is for one set of values:
flag = "This_is_a_flag" coeffs = [0, 117050, 0, 1, 0] p = 2**221 - 3 #y^2 = x^3 + 117050*x^2 + x E = EllipticCurve(GF(p), coeffs) P = E((3142760577589204429307878894255534090454457080956303053605542067598, 2319864396820941847175212453445164674982080984508773902236423958847)) priv = 3293914523875781082687119470321915845052513636536719476235872569479 pub = P * priv def sign(x,y): curve = EllipticCurve(GF(p), coeffs) point = priv * curve((x,y)) print(point) def encrypt(msg): msg = Integer(msg.encode('hex'), 16) k = 815457140906696324416168412407434975023895031257895297485569457271 #Random large prime multiplied by random point on curve c = P * k #These are added and printed as the second cp = pub * k #(P * priv * k) pm = E.lift_x(msg) print("Results of encryption") print(c) print(pm) print(cp+pm) #c = (1289065131478610418217201058842455436095941017884328400355875020309 : 3296884812222036438485505564227985132415466667357978332480916865455 : 1) #cp+pm = (2192025821780143835591289784873552328188048988608585578470306945601 : 2323252162642267908654192252647796526701228836621840549204511010410 : 1) #Take c and pass it to sign to get the cp, find the inverse, reverse pm #c*priv = (67117942371104531818134659493793380897566326547209951968341237467 : 2221529868526358781620627632546920040479760559203268326575921537822 : 1) encrypt(flag) c = E((1289065131478610418217201058842455436095941017884328400355875020309, 3296884812222036438485505564227985132415466667357978332480916865455)) cp_pm = E((2192025821780143835591289784873552328188048988608585578470306945601, 2323252162642267908654192252647796526701228836621840549204511010410)) cp = E((67117942371104531818134659493793380897566326547209951968341237467, 2221529868526358781620627632546920040479760559203268326575921537822)) cp_inverse = -cp msg = 1711994771011294341106724187693415 msg_hex = hex(msg) print(msg_hex) print(msg_hex.decode('hex'))
Hopefully next year I can be more prepared for the challenges and get more solves!
The CTF Environment at NYU Tandon
First and foremost I would like to thank all the CSAW organizers for the amazing work they did to run this event. Everything was smooth from the moment we walked into the venue to the award ceremony at the end. As someone who has planned events before, I appreciate the difficulty of running a large-scale event smoothly. Specifically, thank you to everyone who made the CTF competition amazing. The organizers had to deal with a bunch of young, meme-filled students and they did so with flying colors.
The energy at NYU Tandon was something I do not think I have ever experienced before. The competitors were more friendly than any other competition I have participated in. Every CTF finalist was eager to share solutions at the end of the competition, looking to help others grow and to grow themselves. During the competition, the finalists frequently walked around the venue to take breaks and socialize with others.
The NYC Experience
As someone who originated from a small town I am in love with visiting cities and experiencing the change in culture. Every time I go to a new city I am amazed by the variety of people, food, and the architectural design. Prior to coming to NYC, the largest cities I had visited were Los Angeles, Albuquerque, Atlanta, and Dallas. Needless to say, I was excited about visiting one of the largest and most exciting city in the US.
The energy in NYC was amazing. Walking through Manhattan on the last day of competition gave me a inkling of the culture and activities in the Big Apple. We walked through the city, taking a 4.5 hour trip across the Brooklyn Bridge, down to the south tip of Manhattan, then up to Times Square. The first thing I noticed while walking through the city was the massive size of everything in the city. Concrete jungle only begins to describe the experience. In the small moments when you can peek past the close quarters buildings, the view you are greeted with is one of more buildings in the distance.
Another thing which stood out about NYC was the energy and business of every corner of the city. Tourists made up a lot of the buzz of the areas we visited, but there was a constant bustle of people going to and from locations. In areas such as Washington Square Park there were plenty of people skating and socializing in the park. Plus, I almost wandered into a ongoing movie scene because I wasn't paying enough attention.
As a final word about NYC, the food was amazing. Walking through NYC you see the thousands of food joints available in the city. We didn't have much time to explore the food, but I was able to eat some good ramen and pizza while I was in the city. Needless to say this leaves a lot of opportunity to explore further in the future.
Unfortunately, we only had around 10 hours to explore the city and food due to competition obligations. The experience was a good taste of what NYC had to offer, and I definitely plan to return for a vacation.