HSCTF #4 WriteUp

Algorithms

Coin Flips

Category: Algorithm Score: 100pt Solved By AD1024

Statement

Keith has been very bored with their job as an industrial couponer lately, and so they have decided to spend their time flipping coins. The results of their coin flips are in this file. Keith now wants to know how many runs of flips they found. A run is any consecutive sequence of the same flip. For example, the flips 001111101011 have three runs of length one, two runs of length two, and one run of length five. Can you help Keith count runs? The flag is the number of runs of length one, the number of runs of length two, the number of runs of length three, etc. up to the longest run in the sequence, each separated by a comma and a space.

Solution

Pure simulation programming problem. So EZ.

Code

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

ifstream fin("coin.txt");
ofstream fout("coin.out");
int idx[1010000];
string x;
int main(){
fin>>x;
int maxn = -0x3f3f3f;
for(int i=0;i<x.length();){
int k = 0;
char t = x[i];
while(t == x[i]){
++k;++i;
}
maxn = max(maxn, k);
idx[k]++;
}
for(int i=0;i<=maxn;++i){
if(idx[i]){
fout<<idx[i]<<", ";
}
}
return 0;
}


Hidden Polynomial

Category: Cyptography Score: 100pt Solved By AD1024

Statement

Alice is sending a top secret polynomial, $P(x)$, to Bob. You want to know the equation of $P(x)$. In your attempts to intercept their message, you discover only two facts about P(x):

It’s coefficients are in the set ${0, 1, 2, …, 1000}$. $P(2017) = 49189926321482294101673925793095$

The flag will be $P(1)$.

Solution

Because $P(2017) = 49189926321482294101673925793095$.Therefore, we modulus it with 2017 and we get 1. This means that there is a constant of 1 in the polynomial. Second, we minus the result with 2 and then modulus it with 2017 again. We get 2. This means that the coefficient of $x$ is 2. After several trial, we can find the coefficients are: $1,2,3,5,8,13,\cdots$ which is the Fibonacci sequence.Then we just use brute force search to calculate $P(1)$

Code

fib = [0]*1000
fib[1]=1
fib[2]=1
cur = 2;
for i in range(3,101):
fib[i]=fib[i-1]+fib[i-2]

ans = 0
ans2 = 0;
while fib[cur]<=1000:
if ans == 49189926321482294101673925793095:
print(str(fib[cur]) + " " + str(cur-2))
break
ans = ans + (2017**(cur-2))*fib[cur]
ans2 = ans2 + (1**(cur-2))*fib[cur]
print(str(fib[cur]) + " " + str(cur-2))
cur+=1
print(ans2)


Keithor

Category: Cryptography Score: 100pt Solved By AD1024

Statement

Too many hashes. Help Keith get to the flag!

Solution

The program we need to cope with is: OriginalSrc.py

We find that the comparison is in base63 encrypted form. Thus first we decrypt the base64 string. Then we get a sequence of hashes: 4f79807a7c47f697bd5f06beef955cfdf4fdaef8ade8edf707858fe4294d780d69d4d6a897d8598ce3142d207640ca51d8215d0d6c693873fd32c1f6e468750027b5db34b7d9ce0a79753ecc73da664a995889e0d36db4bfc68df9fc8da3d369b266e617a6158d16ccad4189f0a3dcae62d9b103b50b0d4337c96163471b423fc28f3cda29417b7280eb9321492075c5890dc033471cf91781a07001cea6696b32cdf56b2129bc76a83218bee52c830a8bfc09ec55ae372110c0cc8950ef577d32ed211d40307c3fd6684113341e603c We know that MD5 encryption will return a hash string with a length of 32 and sha1 encryption will return a hash string with a length of 40. Therefore, we put the first 32 characters to some MD5 crack websites. We can get the string: NVL7OA The flag is base64 encrypted form of this string: TlZMN09BCg

Python Exploitation 1

Category: Exploitation Score: 100pt Solved By Mr.Tareen

Statment

Seeing a non-web exploitation problem Keith prepared their binary and c knowledge, but to their surprise, it was a .py! Help Keith learn to exploit python programs.

Netcat to 104.131.90.29:8005.

Note- The flag can be mistaken for an error message.

Solution

We notice that the input statment:

inp = input("Enter the password: ")


dose not cast the input to any data type. Therefore, we diretctly input “thisisthepassword” and then we can get the flag.

Easy Stegosaurus

Category: Forensics Score: 200pt Solved By Mr.Tareen

Statement

Keith infiltrated the scary evil organization ZORE, and had to fight a cloned stegosaurus!

After killing the evil beast, they started to dissect the body for potential information. They found a usb containing two similar looking image files: one called logo.png, and one called changed.png.

What secret information could be contained in these strange files?

Solution

Use “compare” command to compare the differences between two images and then output those differences to a new image, the flag will show up.

KE1TH

Category: Reversal Score: 200pt Solved By AD1024

Statement

Keith recently coded a small authorization software for their computer to hide personal files. Unfortunately, they hit their head and forgot their password. Now they must reverse engineer their software to regain their password.

Solution

This actually is pretty easy. We can use Android Studio to decompile A.class and then we can get:decomp.java

We can see that in the Constructor, the SecretKey has been initialized.

this.aes_cbc_pkcs5.init(1, this.key, new IvParameterSpec(this.iv));


And this line of code set the cipher to MODE_ENCRYPT. According to the documentation on the Internet, we can use Cipher to decrypt if we have the key and the byte array that is encrypted. Therefore, we use the string in Check() method and decrypt it:

public String decrypt(byte[] en){
try {
this.aes_cbc_pkcs5.init(Cipher.DECRYPT_MODE, this.key,new IvParameterSpec(this.iv));
try {
return new String(this.aes_cbc_pkcs5.doFinal(en));
} catch (IllegalBlockSizeException e) {
e.printStackTrace();
e.printStackTrace();
}
} catch (InvalidKeyException | InvalidAlgorithmParameterException e) {
e.printStackTrace();
}
return "";
}


Keith and Dawg 2

Category: Cryptography Score: 200pt Solved By AD1024

Statment

hash- b81b28baa97b04cf3508394d9a58caae letters- q w e r t y

Solution

The story is pretty long and helpless. Actually, we solved this problem in the last day of the contest. We doubted that why there were so many teams solved it but we did not… Because we thought too much on the statment. In fact, we can simplely enmumerate the length of the password and the data was too weak. If we run python program, we can get the flag in about 10 seconds.

Code

from hashlib import md5

global chaList
global tar

if dep == upper :
global tar
if res == tar :
exit()
else :
global chaList
for i in chaList :

if __name__ == '__main__':
chaList = ['q','w','e','r','t','y']
tar = 'b81b28baa97b04cf3508394d9a58caae'
for i in range(1,50) :
search(0,i,'')


Digital Digits

Category: Algorithm Score: 300pt Solved By AD1024

Statment

Keith has found a long list of digits, and as is usual for algo problems in HSCTF, they would like to perform some arbitrary computations upon the list for no apparent reason. Keith’s favorite number is 5, so in the attached list of 500,000 digits, please find the number of subsequences for which the digital root is 5. Report your answer modulo 1,000,000,003.

Some terms: Subsequence: any (not necessarily consecutive) sequence of digits from the original list where the digits are in their original order. For example, 135, 134, 123, and 25 are all subsequences of 12345. Digital root: The function defined as

Where the function dsum(x) is the sum of the digits of x. For example, droot(12345) = droot(dsum(12345)) = droot(15) = droot(dsum(15)) = droot(6) = 6

Example: For the sequence 12345, the subsequences 5, 14, 23, and 2345 all have a digital root of 5. Therefore, the flag if 12345 were the list would be 4.

Solution

It’s a little bit hard. We can convert droot(x) to x%9. Then use dynamic programming: Let dp[i][j] stands for the different ways such that sum=j by using first ith numbers. Therefore: $dp[i][s[i]]=1$ $dp[i][(j+s[i])%9]=(dp[i][(j+s[i])%9] + dp[i-1][j]) % MOD$ Then we need to transit all information in i-1: $dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD$

Code

int d(int x){
return x % 9==0?9:x % 9;
}

for(int i=1;i<=N;++i){
f[i][s[i]] += 1;
for(int j=0;j<=9;++j){
f[i][d(j+s[i])] = (f[i][d(j+s[i])] + f[i-1][j]) % MOD;
}
for(int j=0;j<=9;++j){
f[i][j] = (f[i][j] + f[i-1][j]) % MOD;
}
}


Pascal’s Triangle

Category: Algorithm Score: 300pt Solved By AD1024

Statement

Find problem’s PDF Here~

Solution

The second easiest algorithm problem in this contest. We just need to preprocess the Pascal’s triangle and then simulate the function. We note that the maximum row number is $8000$, which is $2*p$ in the second input case. Thus we only need to preprocess first 8000 lines of the triangle. Also, the termination condtion is $n\leq p+k$ and $2\times p > k$.

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <algorithm>
using namespace std;

int C[10001][10001];

const int mod = 1000000007;

inline void init(){
C[1][0]=C[1][1]=1;
C[0][0]=1;
for(int i=2;i<=8010;++i){
C[i][0]=1;
C[i][i]=1;
for(int j=1;j<i;++j){
C[i][j]=(C[i-1][j]%mod+C[i-1][j-1]%mod) % mod;
}
}
}

inline long long f(int n,int k){
return n>=k?(C[n][k]):0;
}

inline long long mathth(int n,int p){
int k=0;
int ans = 0;
while(k+p<=n or 2*p >= k){
ans += ((f(n,p+k)%mod)*(f(p*2,k)%mod))%mod;
ans %= mod;
++k;
}
return ans%mod;
}

int main(){
init();
int T;
cin>>T;
while(T--){
int n,p;cin>>n>>p;
cout<<mathth(n,p)<<" ";
}
}


Grid

Category: Algorithm Score: 400pt Solved By AD1024

Statement

Keith starts at square (0,0) of a grid and wants to travel to (m, n) (where m,n are nonnegative integers) by moving either right or up by one unit. However, there are special circumstances - 1) there are certain points they cannot travel to, and 2) they is able to move down one unit, either once or never during their path, even if they have already reached (m, n). How many ways can they reach (m, n), mod 10000?

The input file is in the format: m n K x1 y1 x2 y2 . . . xk yk where m, n are as specified, and K is the positive integer that equals the number of points he cannot travel to. The next K lines below it describe the list of the points he cannot travel to. Clarification- Keith cannot move to negative coordinates and their movement is confined to the rectangle with diagonal (0,0) to (m,n).

Solution

A dynamic programming problem. Note: Regard the index $(0,0)$ as the origin of the grid. Define that $f[i][j]$ stands for different paths from $(0,0)$ to $(i,j)$ and $d[i][j]$ stands for different paths from$(i,j)$ to $(M,N)$ Therefore, the total number of different ways contain the down movement is ($f[i][j] \times d[i][j-1])%MOD$. And the total different ways that don’t contain any down movement is $f[M][N]$.Add them together to get the answer. Note: Be careful when dealing with the direct

Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int mod = 10000;
typedef long long ll;

ll f[4010][4010];
ll d[4010][4010];
bool ban[4010][4010];

int N,M;
int K;

int main(){
freopen("in.txt","r",stdin);
cin>>M>>N;
cin>>K;
++M,++N;
while(K--){
int x,y;
cin>>x>>y;
ban[x+1][y+1]=1;
}
/*
^
|
N   |               (M,N)
|
|
|
+-------------------->
(0,0)               (M,0)
*/
f[1][1]=1;
for(int i=1;i<=M;++i){
for(int j=i==1?2:1;j<=N;++j){
if(!ban[i][j]){
f[i][j] = (f[i-1][j] % mod + f[i][j-1] % mod) % mod;
}
}
}
d[M][N]=1;
for(int i=M;i>=1;--i){
for(int j=i==M?N-1:N;j>=1;--j){
if(!ban[i][j]){
d[i][j] = (d[i+1][j] % mod + d[i][j+1] % mod) % mod;
}
}
}
ll ans = 0;
for(int i=1;i<=M;++i){
for(int j=2;j<=N;++j){
if(!ban[i][j-1])
ans += (f[i][j] % mod * d[i][j-1] % mod) % mod;
}
}
cout<<(ans + f[M][N])%mod<<endl;
return 0;
}



Keith And Dawg 4

Category: Reversal Score: 400pt Solved By AD1024

Statement

===================================================================================================

NOTE: Do Keith and Dawg 2 first.

=================================================================================================== Three days passed without incident or contact from the mysterious agents of the NSA or Roshan Cash. Then, suddenly, Keith received an envelope by mail containing a flash drive and a note: Using the hash you reversed, we have accessed several of Degen’s accounts. We recovered several files, but they seem to consist of only random words that make no sense. It appears to be some sort of program. -Jazz Money Roshan Cash

Solution

If we search “O HAI” or some other segments of codes on the Internet, we can find that the language actually called “LOLCODE”. But the lastest version of LOLCODE is 1.2 and this version is 1.4. Therefore we cannot use online pareser to cope with this problem. But we can use the references on Wikipeida. And there is a more detailed reference:Escolang. And we can get this translation:Translation.txt Therefore we can translate the program into a readable code. Or we can directly analyze the program.

O HAI IM TABLE
I HAS A DAWG ITZ A YARN
I HAS A CAT2 ITZ A NUMBR
I HAS A DOG ITZ A NUMBR
I HAS A KAT ITZ A NUMBAR
I HAS A FELINE ITZ A YARN
I HAS A KIT ITZ A NUMBAR

DAWG R "CAT"
DOG R 17
CAT2 R 672
FELINE R "A"
KIT R 92
KAT R 7

HOW IZ I CAT YR NUM
I HAS A CAT3864 ITZ MAEK QUOSHUNT OF ME'Z CAT2 AN NUM A NUMBR
I HAS A A59CAT0 ITZ SRS SMOOSH ME'Z DAWG AN MAEK PRODUKT OF ME'Z KIT AN NUM A NUMBR MKAY
FOUND YR SRS SMOOSH ME'Z FELINE AN MAEK SUM OF NUM AN ME'Z DOG A YARN AN ME'Z DAWG AN MAEK MOD OF NUM AN ME'Z KAT A YARN MKAY
IF U SAY SO
KTHX


In this class, we can identify 6 member variables and one memeber method. And the initial values of member variables are assigned. So the major problem is the method called “CAT”. By using the translation text file, we can find that:

I HAS A CAT3864 ITZ MAEK QUOSHUNT OF ME'Z CAT2 AN NUM A NUMBR


can be converted to:

CAT3864 = self.CAT2 // NUM


and

I HAS A A59CAT0 ITZ SRS SMOOSH ME'Z DAWG AN MAEK PRODUKT OF ME'Z KIT AN NUM A NUMBR MKAY


can be translated to:

A59CAT0 = eval(self.DAWG + str(self.KIT * NUM))


In order to correctly run the program, the result of eval() should have assigned a value. We notice that the value of DAWG is “CAT”, therefore the only possibility is to assgin the value of CAT3864 to A59CAT0. So we can assum the code might be:

CAT3864 = self.CAT2 // NUM
A59CAT0 = CAT3864


In this case, we can know that the value of NUM must be 42.

Keep going, the next line is:

FOUND YR SRS SMOOSH ME'Z FELINE AN MAEK SUM OF NUM AN ME'Z DOG A YARN AN ME'Z DAWG AN MAEK MOD OF NUM AN ME'Z KAT A YARN MKAY


First we parse the result of SMOOSH

result = self.FELINE + str(NUM + self.DOG) + self.DAWG + str(NUM % self.CAT)


We can find that the result is:A59CAT0. So the method can be simplified to:

def CAT(self, NUM) :
return self.CAT2 // NUM


Move on next class:

O HAI IM MATH
HOW IZ I POWERIN YR ABC AN YR DEF
BOTH SAEM DEF AN MAEK DEF A NUMBR, O RLY?
YA RLY
NO WAI
FOUND YR FAIL
OIC
I HAS A INDEX ITZ 0
I HAS A NUM ITZ ABC
IM IN YR HOUSE UPPIN YR INDEX TIL BOTH SAEM INDEX AN DEF
NUM R PRODUKT OF NUM AN SUM OF INDEX AN 1
IM OUTTA YR HOUSE
FOUND YR NUM
IF U SAY SO
KTHX
I HAS A MATHS ITZ LIEK A MATH


We find that there is only a memeber method in this class and it is called “POWERIN”. Then we can get:

class MATH:
def POWERIN(self, ABC, DEF) :
if DEF != int(DEF) :
return -1
NUM = ABC
INDEX = 0
while DEF != INDEX :
NUM = NUM * (INDEX + 1)
INDEX += 1
return NUM


We can translate the rest of code in this way.

Code

class Table:
def __init__(self):
self.DAWG = "CAT"
self.CAT2 = 672
self.DOG = 17
self.FELINE = "A"
self.KIT = 92.0
self.KAT = 7.0

def CAT(self, NUM):
return self.CAT2 // NUM

global TABLES
global MATHS
class MATH:
def POWERIN(self, ABC, DEF) :
if DEF != int(DEF) :
return -1
NUM = ABC
INDEX = 0
while DEF != INDEX :
NUM = NUM * (INDEX + 1)
INDEX += 1
return NUM

class PILE :
def __init__(self):
self.LENGTH = 0
self.MAX = -1
self.ITEMS = [0] * 1000
def PUSHIN(self, ITEM) :
if self.MAX != max(self.MAX, self.LENGTH) :
self.ITEMS[self.LENGTH] = ITEM
self.MAX += 1
else:
self.ITEMS[self.LENGTH] = ITEM
self.LENGTH += 1

def POPPIN(self) :
if self.LENGTH != 0:
self.LENGTH -= 1
ITEM = self.ITEMS[self.LENGTH]
return ITEM
def GETTIN(self, INDEX) :
if INDEX == min(INDEX, self.LENGTH) :
return self.ITEMS[INDEX]

def SIZIN(self) :
return self.LENGTH

def CHECKIN(p) :
C = True
global MATHS
if p.LENGTH == 3 :
if ((p.GETTIN(0)-3)*15)+43 != 16807/7/7 :
C = False
if MATHS.POWERIN(p.GETTIN(0), p.GETTIN(1) / p.GETTIN(0)) != 16560 :
C = False
if TABLES.CAT(p.GETTIN(2)) != 16 :
C = False
return C

if __name__ == '__main__' :
global TABLES
global MATHS
PIN = PILE()
TABLES = Table()
MATHS = MATH()
NUMA = int(input())
PIN.PUSHIN(NUMA)
NUMB = int(input())
PIN.PUSHIN(NUMB)
NUMC = int(input())
PIN.PUSHIN(NUMC)

LOCK = CHECKIN(PIN)
if LOCK :
print('Correct Flag')
else:
print('Not Correct')



Therefore, we can calculate the value of $NUMA$ and we have already known the value of $NUMC$; therefore, we can calculate the value of $NUMB$. The flag will be the concatenation of $NUMA$, $NUMB$ and $NUMC$

Summary

Our team, “Digital Dragons”, got 3950 points in total in this contest. (Actually I could have solved Keith and Dawg 5 but there was no time…) I think it’s pretty good. We got international ranking 33 and rank 23 if we were in America.(BTW: we got the same score of Princeton High School). And the competition was really interesting and worth to play.