| Name | Category |
| ------------------------------------ | ------------ |
| The Birds | Cryptography |
| Baby Rsa 1 | Cryptography |
| Baby Rsa 2 | Cryptography |
| Cantor's Pairadox | Cryptography |
| Guess Me If You Can | Cryptography |
| This Pokemon team Is my Roman Empire | Cryptography |
| Jokesmith | Cryptography |
| The MAC FAC | Cryptography |
| The Fractalist | Cryptography |
{% stepper %}
{% step %}
### The Birds
> You think you're being watched, and you see a suspicious flock of birds on the powerlines outside of your house each morning. You think the feds are trying to tell you something. Separate words with underscores and encase in DawgCTF{}. All lowercase.
```
DawgCTF{thereisnoescape}
```
{% endstep %}
{% step %}
### Baby Rsa 1
> You think your Algebra skills are pretty good huh? Well let's test it out.
chall.py
from Crypto.Util.number import *
from sage.all import randint
p = getPrime(512)
q = getPrime(512)
N = p * q
e = 0x10001
m = bytes_to_long(b"DawgCTF{fake_flag}")
c = pow(m, e, N)
print("N =", N)
print("e =", e)
print("ct =", c)
print()
a = randint(0, 2**100)
b = randint(0, 2**100)
c = randint(0, 2**100)
d = randint(0, 2**100)
x = a * p + b * q
y = c * p + d * q
print("a =", a)
print("b =", b)
print("c =", c)
print("d =", d)
print()
print("x =", x)
print("y =", y)
```python
solve.py
from Crypto.Util.number import *
from sympy import mod_inverse
n = 82012538447359821165849738352756467719053530066892750177578020351019136006996881441650616631012602654920370573185549134046659875914860421394782338722082599261391182262036434549525388081948429632803770833590739702562845306267418403878169267641023564108136843672261999376998284926318313315387819024961709097101
p = 6743157372168500256063482560637365574152487940325590507177860664787954181316130485116121883062542995102725009460890756991543596608364763570502665225651511
q = 12162334930199885688769183795689969592410185555679120917249758283834302412858357859449128842077327318557896169674210867635116014075086788310254623347673691
c = 16978597269030388872549064541934623430749704732655891928833779185083334396093332647023718343748730349576361193985691953617733288330780060179716905267988202710452028943623598185277149645724247199640730959820455032298145782015884558972868277752456856802145299858618876838286795962548300080924547387662096543717
e = 65537
phi = (p - 1) * (q - 1)
d = mod_inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
```
{% endstep %}
{% step %}
### Baby Rsa 2
> If all I have to do is keep my factors p and q secret, then I can save computation time by sharing the same modulus between all my friends. I'll give them unique e and d pairs to encrypt and decrypt messages. Sounds secure to me!
```python
chall.py
from Crypto.Util.number import *
from secret import flag
# This is my stuff! Don't look at it
p = getPrime(512)
q = getPrime(512)
N = p * q
e_priv = 0x10001
phi = (p - 1) * (q - 1)
d_priv = inverse(e_priv, phi)
m = bytes_to_long(flag)
c = pow(m, e_priv, N)
# This is your stuff!
e_pub = getPrime(16)
d_pub = inverse(e_pub, phi)
print(f"e = {e_pub}")
print(f"d = {d_pub}")
print(f"N = {N}")
print(f"c = {c}")
```
we were tasked to find the d we were given the epub and dpub which e is a small prime and d is the inverse of e so
epub . dpub = 1 mod phi
epub . dpub - 1 = k . phi
phi = (epub . dpub - 1)/k
phi = N - (p+q) + 1
p + q = N + 1 - phi
we can use the identity \
(p - q)^2 = (p + q)^2 - 4pq
p - q = sqrt((p + q)^2 - 4pq)
2p = (p + q) + (p - q)
p = ((N + 1 - phi) + sqrt((p + q)^2 - 4pq))/2
2q = (p + q) - (p - q)
q = ((N + 1 - phi) - sqrt((p + q)^2 - 4pq))/2
```python
from math import isqrt
from Crypto.Util.number import inverse, long_to_bytes
e_pub = 58271
d_pub = 16314065939355844497428646964774413938010062495984944007868244761330321449198604198404787327825341236658059256072790190934480082681534717838850610633320375625893501985237981407305284860652632590435055933317638416556532857376955427517397962124909869006289022084571993305966362498048396739334756594170449299859
N = 119082667712915497270407702277886743652985638444637188059938681008077058895935345765407160513555112013190751711213523389194925328565164667817570328474785391992857634832562389502866385475392702847788337877472422435555825872297998602400341624700149407637506713864175123267515579305109471947679940924817268027249
c = 107089582154092285354514758987465112016144455480126366962910414293721965682740674205100222823439150990299989680593179350933020427732386716386685052221680274283469481350106415150660410528574034324184318354089504379956162660478769613136499331243363223860893663583161020156316072996007464894397755058410931262938
e_priv = 65537
tmp = e_pub * d_pub - 1
for k in range(1, e_pub + 1):
if tmp % k != 0:
continue
phi_candidate = tmp // k
sum_pq = N + 1 - phi_candidate
discriminant = sum_pq**2 - 4 * N
if discriminant < 0:
continue
sqrt_disc = isqrt(discriminant)
if sqrt_disc * sqrt_disc != discriminant:
continue
p = (sum_pq + sqrt_disc) // 2
q = (sum_pq - sqrt_disc) // 2
if p * q == N:
# print("Found phi:", phi_candidate)
# print("p:", p)
# print("q:", q)
d_priv = inverse(e_priv, phi_candidate)
m = pow(c, d_priv, N)
print(long_to_bytes(m))
break
```
{% endstep %}
{% step %}
### Cantor's Pairadox
> Now that I have encrypted my flag with a new math function I was just researching I can know share it with my friend Cantor and no one will know how to read it except us!
```python
from sage.all import sqrt, floor
from secret import flag
def getTriNumber(n):
return n * (n + 1) // 2 # Ensure integer division
def pair(n1, n2):
S = n1 + n2
return getTriNumber(S) + n2
def pair_array(arr):
result = []
for i in range(0, len(arr), 2):
result.append(pair(arr[i], arr[i + 1]))
return result
def pad_to_power_of_two(arr):
result = arr
n = len(result)
while (n & (n - 1)) != 0:
result.append(0)
n += 1
return result
flag = [ord(f) for f in flag]
flag = pad_to_power_of_two(flag)
temp = flag
for i in range(6):
temp = pair_array(temp)
print("Encoded:", temp)
```
"ABC" = \[65 66 67]
then we pad the arr with 0 until the size is the power of 2
\[65 66 67 0]
then it will combine the numbers in pairs
pair(a, b) = T(a + b) + b
example S = 65 + 66 = 131\
T(131) = (131 \* 132)/2 = 8646\
so pair(65, 66) = 8646 + 66 = 8712
after 6 iterations it will become a single number
remember that
P = T(S) + b
so b = P - T(S)
S = a + b
so a = S - b
T(S) = S^2 / 2 respectively
so S^2 + S - 2P should be 0
we can use the quadratic to find
S = (sqrt(1 + 8P) - 1)/2
```python
from math import isqrt
def T(k):
return k * (k + 1) // 2
def unpair(P):
possible = []
sqrt_val = isqrt(8 * P + 1)
S_approx = (sqrt_val - 1) // 2
for S in [S_approx - 1, S_approx, S_approx + 1, S_approx + 2]:
if S < 0:
continue
T_S = T(S)
n2 = P - T_S
if n2 >= 0:
n1 = S - n2
if n1 >= 0:
possible.append((n1, n2))
return possible
def decode(encoded):
current = encoded.copy()
for _ in range(6):
new_current = []
for num in current:
pairs = unpair(num)
n1, n2 = pairs[0]
new_current.append(n1)
new_current.append(n2)
current = new_current
original_ascii = []
for num in current:
if num != 0:
original_ascii.append(num)
else:
break
flag = ''.join(chr(c) for c in original_ascii)
return flag
encoded_output = [4036872197130975885183239290191447112180924008343518098638033545535893348884348262766810360707383741794721392226291497314826201270847784737584016]
flag = decode(encoded_output)
print(flag)
```
{% endstep %}
{% step %}
### Guess Me If You Can
> Check out the note-taking app I created! I heard users are really bad at picking passwords, so I made a really really secure number generator to give users passwords! Good luck trying to break it now.
```python
#!/usr/local/bin/python3
from Crypto.Util.number import *
from secret import flag, init, N, a, b
seed = init
state = seed
current_user = (None, None)
accounts = []
notes = dict()
menu1 = '''[1] - Register
[2] - Login
[3] - Manage Notes
[4] - List Users
[5] - Exit
'''
menu2 = '''[1] - Register
[2] - Logout
[3] - Manage Notes
[4] - List Users
[5] - Exit
'''
menu3 = '''[1] - Add Note
[2] - Remove Note
[3] - Return to Menu
'''
def getNext(state):
state = (a * state + b) % N
return state
def make_account(name, password):
global accounts
global notes
accounts.append((name, password))
notes[name] = []
def register(name):
for account in accounts:
if name == account[0]:
print("An account with this name already exists")
raise ValueError(f"User '{name}' already exists. Please choose a different username")
global state
state = getNext(state)
make_account(name, state)
return state
def list_users():
print("Here are all list of all users currently registered.")
for i in range(len(accounts)):
print("Account [" + str(i) + "] - ", accounts[i][0])
def login(name, password):
for account in accounts:
if account[0] == name and str(account[1]) == str(password):
global current_user
current_user = account
print()
print(f"Succesfully Logged in as {current_user[0]}")
return
print("Invalid username or password")
def logout():
global current_user
current_user = (None, None)
def get_menu_choice(minimum, maximum, prompt, input_func=input):
choice = ""
while(True):
choice = input_func(prompt)
try:
choice = int(choice)
if (choice < minimum or choice > maximum):
print("Invalid Choice. Try again")
break
except:
print("Error parsing your input. Try again")
return choice
def view_notes(user):
print(f"Here are the notes for user '{user}'")
current_notes = notes[user]
if (len(current_notes) == 0):
print("This user currently has no notes!")
return
i = 1
for value in current_notes:
print(f"Note {i}: {value}")
i += 1
return
def add_note(user, message):
if (len(message) == 0):
print("Can't add note with an empty message")
return
current_notes = notes[user]
current_notes.append(message)
notes[user] = current_notes
return
def remove_note(user, index):
current_notes = notes[user]
del current_notes[index]
return
def is_logged_in():
global current_user
if (current_user[0] == None and current_user[1] == None):
return False
return True
def handle_note(user, input_func=input):
global notes
view_notes(user)
print()
while(True):
print(menu3)
choice = get_menu_choice(1, 3, "> ")
if choice == 1:
msg = input_func("What message do you want to save? ")
add_note(user, msg)
break
elif choice == 2:
num_notes = len(notes[user])
if num_notes == 0:
print("This user currently has no notes to remove.")
else:
note_choice = get_menu_choice(1, num_notes, f"Which note do you want to remove? (1 - {num_notes}) ")
remove_note(user, note_choice - 1)
break
elif choice == 3:
break
def initAdmin():
register("admin")
add_note("admin", flag)
def run(input_func=input):
global notes
global accounts
initAdmin()
print("Welcome to the state of the art secure note taking app, Global Content Library . You can make accounts, see active users, store and view private information. Everything you can ask for. You can rest well knowing your password is securely generated, just make sure you don't lose it. That's the only way to access your account!")
while(True):
print()
if is_logged_in():
print(menu2)
else:
print(menu1)
choice = get_menu_choice(1, 5, "> ")
if choice == 1: # Register
name = input_func("Enter your name: ")
try:
password = register(name)
except:
continue
print("Your secret password is: ", password, "\nPlease don't lose it!!")
if choice == 2:
if (current_user[0] == None and current_user[1] == None):
name = input_func("Enter your name: ")
password = input_func("Enter your password: ")
login(name, password)
else:
logout()
if choice == 3:
if (current_user[0] == None):
print("You must be logged in to use this feature")
else:
handle_note(current_user[0])
if choice == 4:
list_users()
if choice == 5:#Exit
print("See you later!")
exit()
if __name__ == '__main__':
run()
```
the server uses a LCG password generator
where
```python
def getNext(state):
state = (a * state + b) % N
return state
```
the flaw is that it was using a weak pseudo random (LCG) for the password generation where LCG itself is predictable if we can observe several consecutive outputs
strategy
gather 3 LCG outputs like so
```python
s1 = register_user('user1')
s2 = register_user('user2')
s3 = register_user('user3')
```
then we can calculate the parameters
t1 = (s2 - s1) % N
\
t2 = (s3 - s2) % N
we can calculate the a
inv\_t1 = pow(t1, -1, N) # Modular inverse of t1
\
a = (t2 \* inv\_t1) % N
then b = (s2 - a \* s1) % N
inv\_a = pow(a, -1, N)
admin = ((s1 - b) \* inv\_a) % N
{% endstep %}
{% step %}
### This Pokemon team Is my Roman Empire
> I was on a really sleep deprived tumble, so I decided to hide the key string to my bank account in a Pokemon Team. I know nothing about Pokemon, so I asked a friend and he said the movesets "looked really weird". Can you help find my key string? It should consist of unseparated letters, and be in all caps.
from the website it says the pokemon skills is weird thats problably a hint and the chall called roman empire is also a hint
every first letter of the skill then do a caesar bruteforce to gain the text but every pokemon has a different shift so we have to do it one by one
```
DawgCTF{ITSAROCKSOLIDPOKEMONTEAM}
```
{% endstep %}
{% step %}
### Jokesmith
```python
#!/usr/local/bin/python3
from secret import flag
from Crypto.Util.number import *
jokes = [
"Why did the prime break up with the modulus? Because it wasn't factoring in its feelings",
"Why did the cryptographer bring RSA to the dance? Because it had great curves — wait, no, wrong cryptosystem",
"Why did the CTF player cross the road? To get to the " + flag,
]
def hideFlag(message):
hidden = ""
start = False
for c in message:
if (start):
hidden += "X"
else:
hidden += c
if c == "{":
start = True
if (start):
hidden = hidden[:-1] + "}"
return hidden
def run():
print("You think you're funny? I got a few jokes of my own, tell me a joke and I'll tell you mine")
transcript = []
for i in range(3):
joke = input("Tell me a joke: ")
funny = bytes_to_long(joke.encode()) % 2
if (not funny):
print("Really? That's it? Come back with some better material")
exit()
else:
transcript.append(joke)
print("Ha! That was pretty funny! Here's one of my own")
print(hideFlag(jokes[i]))
transcript.append(jokes[i])
print("Here is our jokes! Show it to a friend to make them laugh! I better encrypt it though in case I said something private")
m = "\n".join(transcript)
p = getPrime(512)
q = getPrime(512)
N = p * q
e = 3
c = pow(bytes_to_long(m.encode()), e, N)
print("c =", c)
print("N =", N)
print("e =", e)
if __name__ == '__main__':
run()
```
look at the small e but the m is very large but we can still manage a hastads attack
```python
from pwn import *
from Crypto.Util.number import *
HOST = "connect.umbccd.net"
PORT = 20549
# context.log_level = "debug"
server = remote(HOST, PORT)
for _ in range(3):
server.recvuntil(b"Tell me a joke: ")
server.sendline(long_to_bytes(1))
for _ in range(3):
trashcan = server.recvline()
print(server.recv())
```
{% endstep %}
{% step %}
###
{% endstep %}
{% endstepper %}
