Category: Algorithm Score: 100pt Solved By AD1024
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.
Pure simulation programming problem. So EZ.
#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;
}
Category: Cyptography Score: 100pt Solved By AD1024
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)$.
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)$
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)
Category: Cryptography Score: 100pt Solved By AD1024
Too many hashes. Help Keith get to the flag!
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
Category: Exploitation Score: 100pt Solved By Mr.Tareen
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.
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.
Category: Forensics Score: 200pt Solved By Mr.Tareen
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?
Use “compare” command to compare the differences between two images and then output those differences to a new image, the flag will show up.
Category: Reversal Score: 200pt Solved By AD1024
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.
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();
} catch (BadPaddingException e) {
e.printStackTrace();
}
} catch (InvalidKeyException | InvalidAlgorithmParameterException e) {
e.printStackTrace();
}
return "";
}
Category: Cryptography Score: 200pt Solved By AD1024
=================================================================================================== NOTE- Do Keith and Dawg 1 first. =================================================================================================== The next day. Keith was walking down the street, still shaken up about the events of the previous day, when a white unmarked van driving at about 80 miles per hour drove by and stopped right in front of them. Suddenly, the door slid open and five men wearing suits jumped out, grabbed Keith, and dragged them back into the van. “Who are you?!” Keith asked. “I’m Agent Roshan Mahanth, of the NSA,” one man replied. “And we know what you’ve been up to.” “I…I don’t know what you’re talking about,” Keith replied, but the sweat pouring out of their forehead gave them away. “We also know that Jakob Degen, or Shady J Dawg, as you call him, is your ‘employer’, and that you two have been very busy lately. We know about the secret files Degen has. I’ve been undercover as Jazz Money Roshan Cash for the past two months, but I have been unable to gain access. Now, you have two options. Your first option is to cooperate with us and help us find a way to hack Degen’s security measures and recover evidence that we can use against him…” “Ok, I’ll do it.” “Good. You’ll hear from us soon.” Keith was then tossed out of the van. They got up and walked home, wondering how they could possibly get past Degen’s security measures. A few days later, Keith received a mysterious phone call from an unknown number. They hesitantly picked up the phone, “Mr. Keith. We have your first assignment. Go to the intersection between Quiche Street and Keif Afenue. You will find an envelope underneath the trash can. In it, you will find a flash drive with a hash we extracted associated with Jakob Degen’s account on a website he frequents. Unfortunately, we do not know his password, as only the md5 hash is stored on the database. We do know, however, that Degen’s keyboard is broken and only the q, w, e, r, t, and y keys are functioning. Report back when you find his password. Jazz Money out.” Keith immediately grabbed their coat and ran down Keif Afenue to the intersection with Quiche Street. Sure enough, they found an envelope with a flash drive underneath the trash can. They walked home and began work. Find the password. To be continued…
hash- b81b28baa97b04cf3508394d9a58caae letters- q w e r t y
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.
from hashlib import md5
global chaList
global tar
def search(dep, upper, password):
if dep == upper :
global tar
res = md5(password.encode()).hexdigest()
if res == tar :
print(password)
exit()
else :
global chaList
for i in chaList :
search(dep+1, upper, password+i)
if __name__ == '__main__':
chaList = ['q','w','e','r','t','y']
tar = 'b81b28baa97b04cf3508394d9a58caae'
for i in range(1,50) :
search(0,i,'')
Category: Algorithm Score: 300pt Solved By AD1024
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.
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$
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;
}
}
Category: Algorithm Score: 300pt Solved By AD1024
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$.
#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)<<" ";
}
}
Category: Algorithm Score: 400pt Solved By AD1024
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).
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
#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;
}
Category: Reversal Score: 400pt Solved By AD1024
===================================================================================================
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
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.
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$
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.