owned this note
owned this note
Published
Linked with GitHub
# Scratch Passcode 2
From: HKCERT22
Solved by: chemistrying (aka DarkChemist)
## Personal thoughts:
Honestly I really like this problem, I personally really enjoy doing this problem. \
It is quite interesting to solve. \
So, if you haven't solved it yet, I recommend you to solve it on your own first, before checking out the write-ups!
## Problem 1
> Of course, the problem is so similar to Scratch Passcode in [https://training.hkcert22.pwnable.hk]. \
The problem requires you to find the passcode and get the flag. \
In Scratch Passcode, I indeed brute force the passcode, trying the find the patterns in it, and obtain the flag. \
So I did this at first when I saw this problem. \
But after several tries (possibly 50), it still failed. \
What can we do?
## Insight 1
We can brute force the passcode in fact. \
Since the possible passcode combinations is $10 * 10 * 10 * 10 = 10000$, it is fast enough to brute force all possible combinations. \
In fact, for a normal computer, $1$ second can possibly run $10^9$ instructions. \
With this in mind, $10000$ tries is fast enough to obtain the results in at most $5$ seconds. \
Note: It depends on your implementation, plus which platform you are using. \
Personally, I can't withstand Scratch (sorry scratch but moving code blocks is so disgusting), so I code a translation of Python script of the input decryption code. \
(Sorry for the disgusting python code, I am not quite used to coding elegantly in Python).
## Solution to Problem 1
Since we are translating Scratch to Python, we need to learn both the ~~weird~~ mechanics of Scratch and Python. \
The following code will explain the reason of why I am implementing the script like this.
```py
'''
Since Scratch uses one-based arrays / lists while Python uses zero-based arrays / lists,
Placing an useless element at index 0 of the arrays / lists is very important.
'''
# The memory obtained from `memory` variable in the Scratch code since it is hardcoded
memory = [
0, # Placing an useless element to make this one-based
6, 126, 330, 225,
6, 77, 297, 230,
28, 49, 440, 80,
2, 329, 528, 245,
100, 133, 209, 15,
72, 28, 55, 195,
102, 7, 22, 5,
28, 364, 583, 20,
72, 98, 55, 20,
108, 280, 121, 25,
50, 112, 330, 20,
110, 392
]
# During the competition, I didn't bother formatting this memory thing, I just do it just to make the code look nicer
# Characters mapped by the Scratch code
'''
Original code:
characters = [chr(x) for x in range(ord('a'), ord('z') + 1)]
for i in range(1, 11):
characters.append(str(i % 10))
characters.insert(0, ' ')
characters.append('{')
characters.append('}')
characters.append('-')
characters.append('_')
'''
# First put the lowercase letters
characters = [0] + [chr(x) for x in range(ord('a'), ord('z') + 1)]
# Then the numbers
characters = characters + [str(x) for x in range(1, 11)]
# Lastly the remaining symbols
characters = characters + ['{', '}', '-', '_']
'''
This is a passcode attempt function.
It crafts into a passcode and obtain the decrypted string.
'''
def hello(attempt):
'''
Original code:
craft = attempt
craft.insert(0, ' ')
'''
craft = [0] + attempt
# Initiate the decrypted string with an empty string
decrypted = ""
# We don't have to initiate i in this scope, so I commented it
# i = 0
# Initiate j, which is the last index of memory
j = len(memory) - 1
# Loop the memory from i = 1 to size of memory
# Python uses inclusive as lower bound and exclusive as upper bound
for i in range(1, len(memory)):
# Implement this like how the Scratch code did
j = (j + 2) % 4 + 1
'''
Below is an attempt to obtain a mapped character.
If you pay attention to the Scratch code, you will find out that
there is divide-by-0.
We can handle this carefully by using try-except keyword.
In Scratch, divide-by-0 will return infinity.
When the (infinity)th item is accessed, it returns nothing.
Therefore, we can neglect any divide-by-0 cases.
Also, according to the Scratch documentation, their division is float division instead.
After some testing and deubgging, the value should be rounded down.
Therefore, integer division is used to obtain the index of character array / list
we have to access.
'''
temp = ""
try:
temp = characters[memory[i] // int(craft[j])]
except:
pass # basically do nothing
# Also implement this like how the Scratch code did
i += 1
# Ignore index 0 since they return nothing in Scratch
# In this case, I mapped space character to index 0 of the Character array / list
# So I use the space character to check if we have to add this character to the decrypted string
if temp != ' ':
decrypted += temp
print(decrypted)
for i in range(10):
for j in range(10):
for k in range(10):
for z in range(10):
attempt = [i, j, k, z]
hello(attempt)
```
## Result 1
> The program took me some time to code and debug, but not so long. \
When I run this code, the code correctly decrypts the input, but neither of them contains string "pass" mentioned in the Scratch code. \
What should we do next?
## Problem 2
> I read the problem statement once again: \
"They have just upgraded the security system - you can't enter the correct passcode **using the keypad** this time!"
That means keypad can't obtain the correct passcode? \
If so, what input is possible? \
## Insight 2
Check back the Scratch code. The program directly takes the value of input to compute the index. \
Letters are not possible. \
That means numbers larger than 9 can be possible. \
Let's try looping the combinations with larger bounds. \
How should we choose this bound? \
1000? \
Recall that $1$ second can possibly run $10^9$ instructions. \
Using $1000$ as the bound results at least roughly $1000^4 = 10^{12}$ instructions, \
plus python is slow as hell and other operations are not even counted, \
This is not fast enough. \
Small bounds should be selected.
## Insight 3
Pay attention to the index calculation when obating a character from the character array / list.
```py
temp = characters[memory[i] // int(craft[j])]
```
If the input number is too large, there will be less characters in the decrypted message. \
The flag won't be small, so large input number is not possible. \
How about the average values of the numbers in the memory?
```py
>>> sum(memory) / (len(memory) - 1)
146.2826086956522
>>>
```
The bound is therefore should be at least smaller than this above value.
## Solution to Problem 2
Let's change the bound to something larger. \
Since if we do $100^4 = 10^8$ operations is also slow experimentally (and from my experience, since running $10^8$ operations in C++ is also slow), I tried $36$ as the bound first, since this question might be related to base-36 that kind of stuff.
```py
for i in range(36):
for j in range(36):
for k in range(36):
for z in range(36):
attempt = [i, j, k, z]
hello(attempt)
```
The code ran for around 30 seconds (Which is slower than what I have expected). \
(Note: I redirected the standard output to a file, so it is faster than outputting this to the terminal). \
Now, let's use any text editor you like to find text with word "pass". \
(Note: I realised that I should have done this checking in my program, so the input-output time can be hugely minimized.) \
(Change it like this:)
```py
if "pass" in decrypted:
print(decrypted)
```
We got the below output.
```
crlckkngpassg0dbanu0nb_dypl
cglcdknbpassgg0abnuu0ebpdyflw
crlckkngpassgo0dbaenut0nbt_dyyplt
cglcdknbpassggo0abenuut0ebtpdyyfltw
cr4ck1ng_passc0de-aband0ned_keyp4d
crlckkngppassgc0db-aanud0nbd_deypld
cglcdknbppassggc0ab-anuud0ebdpdeyfldw
a5vpasspgl3e9qy7margcmyaag}arxca1hal2va1
a5vpasspel3e9qt7mangcmtaae}anxcauhaj2vav
a5vpasspdl3e9qp7malgcmqaad}alxcarhah2var
```
Using human brain, we can notice that the fifth output is most likely the flag. \
Done!
Google Drive
Gist
Clipboard
Sign in with Wallet
