DSO-NUS CTF 2021 Writeup

This blog post contains writeup for problem Three Trials and Login. Since this is for verification purpose as well, the writeups are in English.

这篇文章是DSO-NUS CTF 2021 比赛的Writeup。因为这也是组委会要求的验证过程的一部分,所以这篇博文是以英文书写。

Background

The DSO-NUS CTF 2021 was held online from 27 Feb 2021 9am to 28 Feb 9pm.

This competition consists of problems from different categories: Mobile, Web & Crypto, Pwn, and Reverse Engineering. Each question has different number of points allocated. Lowest one is 150 and the highest one is 500 (if I am not wrong?). There is an initial score of 1000. Some questions, as more people solve them, gets reduced points.

Cut off for top-48 is around 1700 points. Top 3 teams' score are around 5700, 5450 and 5300 respectively.

All flags are of format DSO-NUS{<sha256 hash>}. If a non-standard flag is found, you need to hash it yourself.

Problem: Three Trials

Category: Reverse Engineering

Description: There is a binary file given. It ask for 3 passwords. If all password are correct, it will tell you the format of the flag, then you can hash it yourself.

Initial points allocated: 150

Program Screenshot

First open the binary with a disassembler (and pseudocode generator/decompiler). You will be able to see that main starts at .text:000000000000169A . It use C++ << to print out a welcome message, then call the function at .text:0000000000001586 . This is what the pseudocode generator gives:

__int64 __fastcall sub_1586(__int64 a1, __int64 a2, __int64 a3)
{
  char v4; // [rsp+1h] [rbp-6Fh]
  char v5; // [rsp+2h] [rbp-6Eh]
  char v6; // [rsp+3h] [rbp-6Dh]
  unsigned int v7; // [rsp+4h] [rbp-6Ch] BYREF
  unsigned int v8; // [rsp+8h] [rbp-68h] BYREF
  unsigned int v9; // [rsp+Ch] [rbp-64h] BYREF
  char v10; // [rsp+10h] [rbp-60h] BYREF
  int v11; // [rsp+14h] [rbp-5Ch]
  int v12; // [rsp+18h] [rbp-58h]
  int v13; // [rsp+1Ch] [rbp-54h]
  time_t timer; // [rsp+20h] [rbp-50h] BYREF
  struct tm *v15; // [rsp+28h] [rbp-48h]
  char v16[56]; // [rsp+30h] [rbp-40h] BYREF
  unsigned __int64 v17; // [rsp+68h] [rbp-8h]

  v17 = __readfsqword(0x28u);
  std::operator<<<std::char_traits<char>>(&std::cout, "Insert password: ", a3);
  std::istream::getline((std::istream *)&std::cin, v16, 50LL);
  v11 = __isoc99_sscanf(v16, "%d %d %d %d", &v7, &v8, &v9, &v10);
  if ( v11 != 3 )
    ((void (*)(void))((char *)&sub_1288 + 1))();
  v4 = ((__int64 (__fastcall *)(_QWORD))((char *)&sub_1324 + 1))(v7);
  v5 = sub_13E8(v8);
  v6 = sub_14E6(v9);
  timer = time(0LL);
  v15 = localtime(&timer);
  v12 = v15->tm_mon;
  v13 = v15->tm_hour;
  if ( v4 && v5 && v6 )
    ((void (*)(void))loc_12C3)();
  else
    ((void (*)(void))((char *)&sub_1288 + 1))();
  return 0LL;
}

Notice that it use %d to read and store integer. So the passwords are integers. Moreover, if that sscanf returns a value not 3 , it dies (at function near .text:0000000000001288). Basically, at this point, we know it is 3 integers. We also know that function near 1324 , function at 13E8 and function at 14E6 checks each of them.

We go see the first function near 1324. I am not sure what these two instructions at 1324 and 1326 do. I tried to include them and exclude them in the function, it turns out that excluding them gives a more accurate pseudocode.

.text:0000000000001324 push    rbx             ; CODE XREF: sub_1586+87↓p
.text:0000000000001326 nop     edx

.text:0000000000001329 push    rbp             ; standard begin of function
...

Setting the start and end of function to be 1329 and 13E8 respectively, we get this piece of pseudocode:

_BOOL8 __fastcall sub_1329(int a1)
{
  int v2; // [rsp+14h] [rbp-Ch]
  int i; // [rsp+18h] [rbp-8h]

  v2 = 0;
  for ( i = a1; i > 0; i /= 10 )
    v2 = (int)(sub_173C((unsigned int)(i % 10), 3LL) + (double)v2);
  return v2 == a1 && a1 > 400 && a1 <= 999;
}

Take note of the function at 173C . That is the pow function. Here it means pow((unsigned int)(i % 10), 3) . What this piece of code means is, for a number n, all its digits' cubes' sum equals to n which is the number itself. Consider this password range is very small (401~999, all integers), we do a brute-force. By translating it to python script, we have:

for i in range(400, 1000):
    print(i)
    x = i
    s = 0
    while x > 0:
        s += (x % 10) ** 3
        x = int(x / 10)
    if i == s:
        print(i)
        break

We get 407 at the end. This is our first password.

Let's take a look the second function at 13E8. We have a pseudo code look like this:

bool __fastcall sub_13E8(unsigned int a1)
{
  int v2; // [rsp+18h] [rbp-18h]
  int i; // [rsp+1Ch] [rbp-14h]
  int j; // [rsp+20h] [rbp-10h]
  int v5; // [rsp+24h] [rbp-Ch]
  int v6; // [rsp+28h] [rbp-8h]

  v5 = (int)sub_173C(a1, 2LL);
  v2 = 0;
  for ( i = (int)sub_173C(a1, 2LL); i > 0; i /= 10 )
    ++v2;
  if ( v2 % 2 == 1 )
    return 0;
  for ( j = 1; j < v2; ++j )
  {
    v6 = (int)sub_173C(10LL, (unsigned int)j);
    if ( v5 / v6 + v5 % v6 == a1 )
      return (double)v5 > sub_173C(10LL, 9LL);
  }
  return 0;
}

Let the number be n, we have v5 = n * n. The first for loop counts how many digits in this v5 and store it in v2. This must be an even number, or the program dies by the first if check. Then it will loop j from 1 to v2, and split the number into two halves - one half of j digits and one half of v2-j digits. It will return true if the sum of these two halves equals to n, and v5 is at least a 10-digit number.

Take the example of the answer I found initially by equally split the square into two 5-digit numbers. Say n = 77778. We have v5 = 77778*77778 = 6049417284. When j=5, we have two halves 60494 and 17284, which have the sum of 77778.

However, this is not the answer. This confuses me for a long time as when I debug and set break point at the line v5 = (int)sub_173C(a1, 2LL);, the result assigned to v5 is 0x80000000(which is actually 0). Then I suddenly realized that there is a type casting of double (return type of pow) to int here. If I use 77778, the product will be far greater than MAX_INT which lead to overflow.

On the other hand, if the exact 10-digit number v5 is not 5/5 split, say 4/6 split, a square of a 6-digit number must be greater than MAX_INT. Thinking for some time, I found that this kind of splitting does not always give a 6-digit number when there is 0 in the original number. For example, if 1234012345 do 4/6 split, it will actually be 1234 and 12345 and the sum will still be a 5-digit number. In this way, I wrote a python script to compute:

import math
max_sq = 2147483647
i = 31620
done = False
while not done:
    print(i)
    sq = i**2
    if sq > max_sq:
        print("MAX HIT")
        break
    for x in range(1, len(str(sq))):
        divisor = 10**x
        first = int(sq / divisor)
        second = sq % divisor
        if first + second == i:
            print(i)
            done = True
            break
    i += 1

This gives me the correct answer of n = 38962. 38962 * 38962 = 1518037444 - a 4/6 split just gives 1518 + 37444 = 38962. This is the second number.

For the third checking function, we have:

_BOOL8 __fastcall sub_14E6(int a1)
{
  int v2; // [rsp+18h] [rbp-8h]
  int i; // [rsp+1Ch] [rbp-4h]

  v2 = 0;
  for ( i = 1; i <= a1; ++i )
  {
    if ( !(a1 % i) && i != a1 )
      v2 += i;
  }
  return v2 == a1 && (double)v2 > sub_173C(10LL, 5LL) && sub_173C(10LL, 8LL) > (double)v2;
}

Pretty obvious, this ask for a number between 6 digit to 9 digit, which has all of its proper factors having a sum equal to itself. Googling gives the name of this kind of number - "perfect number". According to Wikipedia's list, the only one falls in this range is 33550336. This is hence the 3rd number.

At this point, the answer is solved: 407 38962 33550336. Do the hashing based on the format given, we have the flag DSO-NUS{5137e2ead70710512aa82dfca8727c4eb6803637143a9c2f0c7596ab00352a69}.

Problem: Login

Category: Mobile

Description: There is an Android apk given. Launching it gives a simple login interface requesting for a username and a password. Flag is generated after correct credential is entered.

Initial points allocated: 150

I first decompiled it using online decompiler here. By following from the default activity com.ctf.level1.ui.login.LoginActivity, I end up in com.ctf.level1.data.LoginDataSource which manages the credential. Here is the code:

package com.ctf.level1.data;

import android.util.Log;
import com.ctf.level1.data.Result;
import com.ctf.level1.data.model.LoggedInUser;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.util.UUID;
import kotlin.UByte;

public class LoginDataSource {
    private final char[] HEX_ARRAY = "0123456789ABCDEF".toCharArray();
    private String TAG = "ctflevel1";
    private String m_password = "7470CB2F2412053D0A3CEC3D07CAE4A4";

    public native String getNativePassword();

    public void logout() {
    }

    static {
        System.loadLibrary("ddea");
    }

    public String toHex(byte[] bArr) {
        char[] cArr = new char[(bArr.length * 2)];
        for (int i = 0; i < bArr.length; i++) {
            int i2 = bArr[i] & UByte.MAX_VALUE;
            int i3 = i * 2;
            char[] cArr2 = this.HEX_ARRAY;
            cArr[i3] = cArr2[i2 >>> 4];
            cArr[i3 + 1] = cArr2[i2 & 15];
        }
        return new String(cArr);
    }

    public byte[] hexStringToByte(String str) {
        int length = str.length() / 2;
        byte[] bArr = new byte[length];
        for (int i = 0; i < length; i++) {
            int i2 = i * 2;
            bArr[i] = Integer.valueOf(str.substring(i2, i2 + 2), 16).byteValue();
        }
        return bArr;
    }

    public String hexStringToString(String str) {
        return new String(hexStringToByte(str), StandardCharsets.UTF_8);
    }

    public String getJavaPassword() {
        try {
            return AESTools.decrypt(this.m_password);
        } catch (Exception e) {
            e.printStackTrace();
            return "";
        }
    }

    public Result<LoggedInUser> login(String str, String str2) {
        if (!str.equals(hexStringToString("5573657231333337"))) {
            Log.d(this.TAG, "Wrong userid!");
            return new Result.Error(new Exception("wrong credentials"));
        }
        String substring = str2.substring(0, 4);
        if (!substring.equals(getJavaPassword())) {
            Log.d(this.TAG, "Wrong password");
            return new Result.Error(new Exception("wrong credentials"));
        }
        String substring2 = str2.substring(4);
        if (!substring2.equals(getNativePassword())) {
            Log.d(this.TAG, "Wrong password!");
            return new Result.Error(new Exception("wrong credentials"));
        }
        try {
            MessageDigest instance = MessageDigest.getInstance("SHA-256");
            instance.update((substring + substring2).getBytes());
            Log.d(this.TAG, "The flag is " + toHex(instance.digest()));
            return new Result.Success(new LoggedInUser(UUID.randomUUID().toString(), "The flag is printed to logcat!"));
        } catch (Exception e) {
            return new Result.Error(new IOException("Error logging in", e));
        }
    }
}

At the login function, it checks for both username and password. Username, after convert to hex, has 5573657231333337. Using a online converter, we found that username is User1337. Then, the password consists of two parts. First 4 digits are compared with getJavaPassword(), while the remaining ones are compared with getNativePassword(). Obvious, this is a native function provided by libddea.so located in lib folder.

I first want to add a main function to this class and compiles it like a normal Java program to just print out the two passwords. However, as libddea.so links to liblog.so, which presents only on Android device, this does not work.

Then, I tried to make sense of the code itself to deduce the password. However, I get something like this when I decompile:

__int64 __fastcall Java_com_ctf_level1_data_LoginDataSource_getNativePassword(__int64 a1)
{
  __m128 v2[16]; // [rsp+0h] [rbp-108h] BYREF
  unsigned __int64 v3; // [rsp+100h] [rbp-8h]

  v3 = __readfsqword(0x28u);
  v2[0] = _mm_xor_ps(*(__m128 *)off_2008, *(__m128 *)off_2000);
  return (*(__int64 (__fastcall **)(__int64, __m128 *))(*(_QWORD *)a1 + 1336LL))(a1, v2);
}

I was not able to make sense of this. Since this program is not compiled with debuggable set to true, I could not attach a debugger to it directly as well. The files from decompilation also cannot be compile back to an Android app after modification.

At the end, I chose a 'shortcut'. I created a new Android application with default templates (empty activity) from Android Studio, copy over the original source files (and libddea.so), and use it to call the two methods in the original package. Since we only utilize this LoginDataSource class, all other things prevent from compilation can be safely deleted (such as com.ctf.level1.ui.login.LoginViewModelFactory).

package com.example.myapplication;

import androidx.appcompat.app.AppCompatActivity;

import android.os.Bundle;
import android.widget.TextView;

import com.ctf.level1.data.LoginDataSource;

public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        LoginDataSource s = new LoginDataSource();
        String p1 = s.getJavaPassword();
        String p2 = s.getNativePassword();
        ((TextView) findViewById(R.id.p1)).setText("P1 is " + p1);
        ((TextView) findViewById(R.id.p2)).setText("P2 is " + p2);
    }
}

Then, we add this section to app/build.gradle to include the libddea.so in our APK built (library files are copied to app/libs):

// Ref: https://stackoverflow.com/questions/29414950/how-to-include-so-file-in-android-gradle-application
android{
    ....
    sourceSets {
        //noinspection GroovyAssignabilityCheck
        main {
            jni {
                srcDirs = []
            }

            jniLibs {
                srcDir 'libs'
            }
        }
    }
}

When we run it, we will see the password printed out.

So the password is L1v3p2Zzw0rD. We enter it in the original login app (see screenshot above), we see this in our logcat:

So this is the flag, which is the sha256 hash of the password. DSO-NUS{71bcade1b51d529ad5c9d23657662901a4be6eb7296c76fecee1e892a2d8af3e}.

Conclusion

That's all about the steps to solve these two questions. As I am not very familiar with many of these techniques, it took me much time to solve each of them. The question of babyNote is also interesting (though it took me entire afternoon ~5 hours to solve it). The challenge website has been closed so I can't introduce it.

I have attached files for Three Trials and Login. If you are interested, you can also try to solve it yourself.

Archive for Three Trials: Click Here (both original binary and python scripts included)

Archive for Login: Click Here (contains original apk, decompiled apk and the source for the new application - apk for the new app can be found at login.apk-repack/app/build/outputs/apk/debug.

Disclaimer: The blog image (that Earth picture) is obtained from DSO-NUS CTF's website. If copyright is infringed, please email me immediately to take it down.
All the contents in this blog (including but not limited to text and images), unless explicitly specified, are licensed under CC BY-NC-SA 4.0.