[PYTHON] I tried to summarize Cpaw Level 3 Write Up in an easy-to-understand manner

Hello. I haven't been able to do CTF since I got a job, so I solved all the remaining Cpaw CTF problems that I couldn't do recently. This time I will summarize a simple WriteUp for those problems. That said, the problem this time is Level 3, so it's quite difficult without thorough research. When tackling a problem, it is recommended to search with as many keywords as possible or to solve it from multiple perspectives.

Execution environment

Windows10 The prerequisites are the same as those described in WriteUp of Level1 & Level2. Last Write Up

Before reading this article

Please try to solve this problem with your own hands. By solving it yourself, you can accumulate know-how and make different discoveries.

WriteUp

Level3

Q23. [Reversing] I did it again!

You will be given some executable file. It looks like a file that doesn't have printf written in the problem statement. I will try to get the flag using IDA in the same way this time. I thought so, but when I solved this problem, I couldn't understand the assembly statement well, so I thought there might be a tool that could bring me closer to the answer, so I gave up IDA and used another reverse engineering tool [Ghidra]. I decided to solve it using (https://ghidra-sre.org/). (Of course, IDA is not bad. Please be assured that IDA alone will give you a sufficient answer.) Click here to install Ghidra

Now, after installing Ghidra, load the JDK and start Ghidra. After starting, check Non-Shared Project and open a new project.

If the project can be created normally, the following screen will be displayed.

Select [File] on the screen, select Inport File, and import the given executable file.

If the import is successful, double-click the executable file and you will see a screen like this. You can see the assembly and decompiled results here. (It is a function called CodeBrowser in Ghidra.)

And before that, you'll probably see a popup like the one below, so select Yes. Here you can view various information about the executable file. This time, leave the check box as it is and select [Analyze]. It also shows the format information and what it was compiled with. Amazing NSA.

You'll be back to the previous screen, so pay attention to the window called Symbol Tree there. I think that the functions in the program are summarized as to what the program is reading. Let's select main (probably the core of this program) from [Functions] in this.

Then you should see the generated pseudocode in the Decompiler window on the left. (It is displayed thanks to the Decompiler Switch Analysis specified in the Analyze option earlier.)

I see, it's kind of like C language. I will transcribe it for the time being.

undefined4 main(void)

{
  int iVar1;
  uint *puVar2;
  int local_84;
  uint local_7c [14];
  uint local_44 [14];
  
  local_7c[0] = 0x7a;← Probably a hexadecimal number?
  local_7c[1] = 0x69;
  local_7c[2] = 0x78;
  local_7c[3] = 0x6e;
  local_7c[4] = 0x62;
  local_7c[5] = 0x6f;
  local_7c[6] = 0x7c;
  local_7c[7] = 0x6b;
  local_7c[8] = 0x77;
  local_7c[9] = 0x78;
  local_7c[10] = 0x74;
  local_7c[11] = 0x38;
  local_7c[12] = 0x38;
  local_7c[13] = 100;
  iVar1 = 0xe;← 14 in hexadecimal
  puVar2 = local_44;
  while (iVar1 != 0) {
    iVar1 = iVar1 + -1;
    *puVar2 = 0;
    puVar2 = puVar2 + 1;
  }
  local_84 = 0;
  while (local_84 < 0xe) {
    local_44[local_84] = local_7c[local_84] ^ 0x19;← Exclusive OR of the assigned value and 0x19(XOR)Is taking(^Operator that calculates xor)
    local_84 = local_84 + 1;
  }
  return 0;
}

Apparently, it seems that the result of calculating the numerical values ​​in the array by exclusive ORing is put in another array. It seems that there is no printf, so I will rewrite it as follows and implement it.

Q23.c

#include <stdio.h>
int main(void){

    int var;
    unsigned int *var1;
    int local_84 = 0;
    unsigned int local_7c[14];
    unsigned int local_44[14];
    
    local_7c[0]=0x7a;
    local_7c[1]=0x69;
    local_7c[2]=0x78;
    local_7c[3]=0x6e;
    local_7c[4]=0x62;
    local_7c[5]=0x6f;
    local_7c[6]=0x7c;
    local_7c[7]=0x6b;
    local_7c[8]=0x77;
    local_7c[9]=0x78;
    local_7c[10]=0x74;
    local_7c[11]=0x38;
    local_7c[12]=0x38;
    local_7c[13]=100;
    var1 = local_44;
    var=14;
    while(var!=0){
        var = var + -1;
        *var1=0;
        var1=var1+1;
    }
    local_84 = 0;
    while (local_84 < 0xe) {
        local_44[local_84] = local_7c[local_84] ^ 0x19;
        local_84 = local_84 + 1;
    }
    //add to
    for(int i =0;i<14;i++){
        printf("%c", local_44[i]);
    }
    return 0;
}

You can get the flag by executing the above code.

bonus Burnam Cryptography

Q24.[Web]Baby's SQLi - Stage 2- It looks like a continuation of Baby's SQLi. It seems that the problem is not completely solved, so when I type in the select statement again, You can see a dubious URL in the second table, it seems that this is stage 2, so let's jump to this site. Then There seems to be a flag on the other side of the login form. However, I don't know the password, and everyone has no idea.

So, remember, in the previous problem, it was a form in which SQL statements could be typed. There were many attack methods for SQL injection.

Based on this information, we can derive ... ** "Isn't it possible to get the flag by typing some SQL statement in the password input part?" **. If you look up "SQL password" properly, you will find various information.

Therefore, if you enter the following SQL statement in the password input part, you can get the flag.

' OR 1=1--

This SQL statement, horribly, has the following meanings:

「'」

Pair with the previous "'" to end the string constant

OR 1=1

Make the search condition true regardless of the table value

「--」

Ignore the content after that as a comment

Reference site: https://www.ipa.go.jp/security/awareness/vendor/programmingv2/contents/502.html

** * Doing this in the real world is really a crime, so don't do it. I don't think it's okay, but if there is a site where you can log in by typing this SQL statement, please tell the site administrator secretly. ** **

Q26.[PPC]Remainder theorem It's a matter of multiple congruence formulas. The congruence formula is an equation that focuses only on the division, for example, 8 and 2 both have a remainder of 2 divided by 3. This is expressed in the congruence formula as follows.

8 ≡ 2 (mod 3)

This congruence formula means that 8 and 2 are the same if you focus only on the remainder of dividing by 3.

Let's look at the problem statement.

x ≡ 32134 (mod 1584891)

x ≡ 193127 (mod 3438478)

To see the problem statement, ① 32134 and x are equal to the remainder divided by 1584891 (2) 193127 and x have the same remainder after dividing by 3438478. All you have to do is find x that satisfies these two conditions. It looks like this when written programmatically.

x%1584891 == 32134%1584891 && x%3438478 == 193127%3438478

Let's write a program using this conditional expression. (Since you can imagine that the number of digits of x will increase, I think that the execution time can be shortened a little by making the start large.)

Q26.c

#include<stdio.h>
int main(){
    long long int x;
    for(x=100000000;;x++){
        if(x%1584891 == 32134%1584891 && x%3438478 == 193127%3438478){
            printf("%lld",x);
            break;
        }
    }
    return 0;
}

Now you can get the flag. I think it can be solved a little smarter. (I could only come up with a solution for this ... I regret it because I lacked technical skills)

Q29.[Crypto] Common World RSA cryptography is one of the public key cryptography that utilizes the property that it takes an extremely long time to factor a composite number with a large number of digits into prime factors. Reference site

To put it simply, it is the one that Kenji Koiso, the main character of cv. Ryunosuke Kamiki, solved by mental arithmetic in Summer Wars. (** It's not a problem that can be solved by mental arithmetic in a normal way. ** If you can break the RSA code with nosebleeds, I would be happy to have nosebleeds and mess up the system in the world. Maybe he died after this ...)

The problem statement gives the positive integer e used to encrypt the RSA cipher, the product n of huge prime numbers, and the encrypted statement c. Also, from the hint, another set of e, n, c is given. (c is different)

At first glance, RSA ciphers look invincible, but if you make them vulnerable, they can be decrypted fairly easily. In fact, there are some things to keep in mind when creating RSA ciphers, and there are various attack methods. Reference site 1 Reference site 2

If you look at these sites and look at this issue again, you can see that the RSA ciphers this time have the same n, so an attack method called Common Modulo Attack can be used. This site explains Common Modules Attack in an easy-to-understand manner

This time, I will borrow the code described in this site and perform Common modules Attack. If you have a Python execution environment, you can solve it on your computer as it is, but I'm tired of it, so I used Google Colaboratory officially provided by Google. Great for running Python code on the web. You can also import the library using pip, which is quite convenient.

After opening Google Colaboratory, click [File] → [New Notebook].

Then a new screen will be displayed. Click [Code] on this screen and enter the code.

I want to execute the code of this site, but since gmpy2 cannot be used by default, I tried to install gmpy2 on my notebook, but I got an error.

After a lot of research and looking at this site, it seems that the dependency library has not been installed, so I will fill in the installation statement that was written in the solution and execute it.

After the installation is completed normally, try installing gmpy2 with pip again. This time it should work.

Finally, you can get the flag by executing the code of this site.

Q29.py

import gmpy2,binascii

n = 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577
e1 = 13
e2 = 11
c1 = 14451037575679461333658489727928902053807202350950440400755535465672646289383249206721118279217195146247129636809289035793102103248547070620691905918862697416910065303500798664102685376006097589955370023822867897020714767877873664
c2 = 80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904


val = gmpy2.gcdext(e1,e2)

print("[+] gcd(e1,e2) : {}".format(val[0]))
print("[+] a:{}, b:{}".format(val[1],val[2]))
print("[+] e1*a + e2*b == gcd(e1,e2)? : {}".format((e1*val[1]+e2*val[2]) == val[0]))

if val[1] < 0:
    a = -val[1]
    b = val[2]
    c1_inv = gmpy2.invert(c1,n)
    c1a = pow(c1_inv, a, n)
    c2b = pow(c2, b, n)
else:
    a = val[1]
    b = -val[2]
    c2_inv = gmpy2.invert(c2,n)
    c1a = pow(c1, a, n)
    c2b = pow(c2_inv, b, n)

m = (c1a * c2b)%n

m,result = gmpy2.iroot(m,val[0])
print("[+] gmpy2.iroot(m,gcd(e1,e2)) : {}".format(result))
print("[+] m^e1(mod n) == c1? : {}".format(pow(m,e1,n) == c1))
print("[+] m^e2(mod n) == c2? : {}".format(pow(m,e2,n) == c2))

try:
    flag = binascii.unhexlify(format(m, 'x')).decode()
except Exception as e:
    flag = m

print("FLAG: {}".format(flag))

bonus If you put the decrypted value here ...? Polybius Square

Digression RSA cryptography also has various vulnerabilities. In the real world, it seems that the RSA encryption method is not the only one used for encryption, but is used with padding. Example: OAEP

At the end

Thank you for browsing so far. If you find something difficult to understand, please let us know in the comments.

Well, as anyone who has seen WriteUp up to this point will understand, these problems are difficult to deal with. However, it turned out that it can be solved quite flexibly due to technological advances. It's normal, but the technology is amazing, isn't it? In particular, security technology supports our lives behind the scenes. However, it is also a fact that these technologies can be easily abused if they are not used correctly. It can be called a double-edged sword. If you can handle the technology easily, you can be a great developer, but you can also use it to be a criminal. I would like to convey to those who have seen so far that if you use technology, you also need to take responsibility accordingly. ** I don't think it is, but never commit a criminal act using the technology introduced so far. ** **

You know? To be honest, I started CTF from the idea of ​​a dangerous person such as ** "I can legally commit a crime ...!" **, and handling various data is just like a hacker, so I can understand my feelings. But ** Don't just commit crimes? ** Technology is basically only effective when used correctly. It's a promise with me.

If you think "CTF may be!" In this article, it will be a human benefit. See you somewhere in the next article.

Writer: Yuyu Yuta Twitter Hatebu