RSA oracle guide
Challenge Description
See the challenge here
Name: rsa_oracle
Description:
Can you abuse the oracle?
An attacker was able to intercept communications between a bank and a fintech company. They managed to get the message (ciphertext) and the password that was used to encrypt the message.
After some intensive reconassainance they found out that the bank has an oracle that was used to encrypt the password and can be found here nc titan.picoctf.net 65008. Decrypt the password and use it to decrypt the message. The oracle can decrypt anything except the password.
See the challenge here
Name: rsa_oracle
Description:
Can you abuse the oracle?
An attacker was able to intercept communications between a bank and a fintech company. They managed to get the message (ciphertext) and the password that was used to encrypt the message.
After some intensive reconassainance they found out that the bank has an oracle that was used to encrypt the password and can be found here nc titan.picoctf.net 65008. Decrypt the password and use it to decrypt the message. The oracle can decrypt anything except the password.
Initial thoughts (prep)
Gathering the information we get from the challenge
We get a file called password.txt and secret.enc
Since we know that RSA doesn’t use a password file for encryption, the flag is likely encrypted with:
Since we know that RSA doesn’t use a password file for encryption, the flag is likely encrypted with:
some_encryption_function(flag.txt,password.txt) = secret.enc
We will take a look at what the specific encryption function is later
Before we decrypt secret.enc, the challenge says that we have to decrypt the password first, likely using the provided RSA oracle
Looking at the function, we can just test out how the encryption function works:
Looking at the function, we can just test out how the encryption function works:
gabbage-picoctf@webshell:~$ nc titan.picoctf.net 65008
*****************************************
****************THE ORACLE***************
*****************************************
what should we do for you?
E → encrypt D → decrypt.
E
enter text to encrypt (encoded length must be less than keysize): z
z
encoded cleartext as Hex m: 7a
ciphertext (m ^ e mod n) 4588102403163489123428120224636410617147594689738894402835294478618392742891286573829226143625251019198809190373464518693469406364535800791926759826248951
what should we do for you?
E → encrypt D → decrypt.
E
enter text to encrypt (encoded length must be less than keysize): a
a
encoded cleartext as Hex m: 61
ciphertext (m ^ e mod n) 1894792376935242028465556366618011019548511575881945413668351305441716829547731248120542989065588556431978903597240454296152579184569578379625520200356186
what should we do for you?
E → encrypt D → decrypt.
*****************************************
****************THE ORACLE***************
*****************************************
what should we do for you?
E → encrypt D → decrypt.
E
enter text to encrypt (encoded length must be less than keysize): z
z
encoded cleartext as Hex m: 7a
ciphertext (m ^ e mod n) 4588102403163489123428120224636410617147594689738894402835294478618392742891286573829226143625251019198809190373464518693469406364535800791926759826248951
what should we do for you?
E → encrypt D → decrypt.
E
enter text to encrypt (encoded length must be less than keysize): a
a
encoded cleartext as Hex m: 61
ciphertext (m ^ e mod n) 1894792376935242028465556366618011019548511575881945413668351305441716829547731248120542989065588556431978903597240454296152579184569578379625520200356186
what should we do for you?
E → encrypt D → decrypt.
Thus, we can infer the encoding function something along the lines of:
1. Get a string ‘a’
2. Get the hex value of that string
3. Retrieve the cipher text as (m ^ e mod n)
Wait a second. At step 2, you can’t get the hex value of a string!
When we attempt it in python…
1. Get a string ‘a’
2. Get the hex value of that string
3. Retrieve the cipher text as (m ^ e mod n)
Wait a second. At step 2, you can’t get the hex value of a string!
When we attempt it in python…
>>> hex('a')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'str' object cannot be interpreted as an integer br
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'str' object cannot be interpreted as an integer br
It appears like hex() function takes only integers. Hmm… are there any ways that we can convert a string to integer? We can use the ord() function to take its ASCII value!
Testing our hypothesis…
Testing our hypothesis…
>>> hex(ord('a'))
'0x61'
'0x61'
Comparing with what we got from the oracle:
…
enter text to encrypt (encoded length must be less than keysize): a
a
encoded cleartext as Hex m: 61
…
enter text to encrypt (encoded length must be less than keysize): a
a
encoded cleartext as Hex m: 61
…
Our hypothesis is correct!
But wait a second, we can’t do (m ^ e mod n) with m being a hex value! If we just assume that it is an integer (by stripping the ‘0x’, which is what I tried doing in the first place), it wouldn’t work for values like z where hex(ord(‘z’)) = 0x7a.
Therefore, it likely uses m as its integer value by changing it using m = int(hex_value_of_m,16) in order for step 3 to work. So, when it displays the value of hex(m), it doesn’t realistically use hex(m) anywhere else along its encoding, but uses hex_to_int(hex(m)) for the encryption. Basically its just for display :P
Also, ord(string) only works for one character. What happens when we input multiple characters, like ‘aa’? We can test this:
But wait a second, we can’t do (m ^ e mod n) with m being a hex value! If we just assume that it is an integer (by stripping the ‘0x’, which is what I tried doing in the first place), it wouldn’t work for values like z where hex(ord(‘z’)) = 0x7a.
Therefore, it likely uses m as its integer value by changing it using m = int(hex_value_of_m,16) in order for step 3 to work. So, when it displays the value of hex(m), it doesn’t realistically use hex(m) anywhere else along its encoding, but uses hex_to_int(hex(m)) for the encryption. Basically its just for display :P
Also, ord(string) only works for one character. What happens when we input multiple characters, like ‘aa’? We can test this:
enter text to encrypt (encoded length must be less than keysize): aa
aa
encoded cleartext as Hex m: 6161
ciphertext (m ^ e mod n) 147950756392740340992280723067817265404539599062830301436102936024455313930941827738306883508646622646362182255686930438410358121461463360508403968595919
aa
encoded cleartext as Hex m: 6161
ciphertext (m ^ e mod n) 147950756392740340992280723067817265404539599062830301436102936024455313930941827738306883508646622646362182255686930438410358121461463360508403968595919
It encoded our cleartext as 6161, and from our deduction, it uses hex_to_int(hex(‘aa’)), which is hex_to_int(0x6161)
We can visualise multi-character encoding with this:
We can visualise multi-character encoding with this:
h e l l o #split by character
68 65 6c 6c 6f #combine each character into their hex representation
0x68656c6c6f #combine them as one big hex value
448378203247 #convert into int using int("0x68656c6c6f",16)
68 65 6c 6c 6f #combine each character into their hex representation
0x68656c6c6f #combine them as one big hex value
448378203247 #convert into int using int("0x68656c6c6f",16)
With this we can update our encoding function to:
1. Get a string ‘a’
2. Display the hex value of ‘a’ with hex(‘a’)
3. Calculate ciphertext as hex_to_int(hex(‘a’))^e % n
1. Get a string ‘a’
2. Display the hex value of ‘a’ with hex(‘a’)
3. Calculate ciphertext as hex_to_int(hex(‘a’))^e % n
Looking at RSA decryption techniques
We’ll be using a bit of math syntax to illustrate how the decryption is derived, so if you find that yucky, you can skip ahead to the layman explanation.
We first define a bunch of parameters:
We first define a bunch of parameters:
Where Enc() is the encoding function, Dec() is the decryption function
Note: #3 is very important! If you want to read up more on how #3 is derived, see
here
here
We want to take advantage of #3 to somehow get the plaintext password, so we define our own value called ourValue
From this, we know these values:
1. Enc(secret)
2. ourValue
3. Enc(ourValue)
The real challenge is finding secret without doing Dec(Enc(secret)) directly, as it is disallowed.
We can find secret by following these steps:
From this, we know these values:
1. Enc(secret)
2. ourValue
3. Enc(ourValue)
The real challenge is finding secret without doing Dec(Enc(secret)) directly, as it is disallowed.
We can find secret by following these steps:
Alright, that’s a lot of math, but what did we learn?
These are the steps that we need to get our secret:
1. Determine a value to be set as ourValue
2. Encrypt ourValue with the oracle to get Enc(ourValue)
3. Multiply our encrypted secret with Enc(ourValue)
4. Decrypt result from step 3 using the oracle
5. Divide the result from step 4 to get secret
These are the steps that we need to get our secret:
1. Determine a value to be set as ourValue
2. Encrypt ourValue with the oracle to get Enc(ourValue)
3. Multiply our encrypted secret with Enc(ourValue)
4. Decrypt result from step 3 using the oracle
5. Divide the result from step 4 to get secret
By ourValue, we mean hex_to_int(hex(the string we input)) as it uses the hex_to_int() in the encryption process not the string itself. After all, you cant divide a number by say ‘a’.
But wait! There’s a secret 5th step. When we divide that by ourValue, we do get the decrypted form of secret, but its an integer, not a string. Recall from our encoding process that the main encoding process uses the hex_to_int(hex((value)) for encryption.
Full process for gettig the final, string version of our password
Full process for gettig the final, string version of our password
hex_string = format(secret, 'x') #Converts secret from integer to hex
secret = bytes.fromhex(hex_string).decode() #Converts secret from hex to a readable string
secret = bytes.fromhex(hex_string).decode() #Converts secret from hex to a readable string
Python doesn’t have a direct hex to string function. Instead, we have to convert our hex value to bytes, and then decode to the bytes to a readable string
Decrypting secret.enc
Even after decrypting password, how do we get the flag back?
If we look at secret.enc we get:
If we look at secret.enc we get:
Salted__g���0' ^� l��h��i���p2Έ�?�Lc}5ڧ��H�|UV;��h@�=��
Depending on what you use, you might need to convert secret.enc to secret.txt to view
If we search up how to decrypt .enc files, the most common answer is to use openssl
The thing is, openssl takes in different encryption types, so which encryption type do we use? According to online the most common encryption types are:
1. aes-128-cbc
2. aes-256-ecb
So we will keep these in mind when getting the flag
The thing is, openssl takes in different encryption types, so which encryption type do we use? According to online the most common encryption types are:
1. aes-128-cbc
2. aes-256-ecb
So we will keep these in mind when getting the flag
Combining the steps
Alright, let’s finalise our plan.
1. Determine a value to be set as ourValue
2. Encrypt ourValue with the oracle to get Enc(ourValue)
3. Multiply our encrypted secret with Enc(ourValue)
4. Divide that by ourValue
5. Get the plaintext password as the result from step 4 from int to hex then hex to string
6. Use openssl enc -d aes-256-dcb -in secret.enc -pass pass:”” with our plaintext password to recover our flag
1. Determine a value to be set as ourValue
2. Encrypt ourValue with the oracle to get Enc(ourValue)
3. Multiply our encrypted secret with Enc(ourValue)
4. Divide that by ourValue
5. Get the plaintext password as the result from step 4 from int to hex then hex to string
6. Use openssl enc -d aes-256-dcb -in secret.enc -pass pass:”
from pwn import *
from subprocess import run, PIPE
p = remote("titan.picoctf.net",64808)
with open('./password.txt') as f:
global password
password = f.read()
#Get Banner plus options menu
print(p.recvuntil(b'decrypt.').decode())
p.sendline('E'.encode()) #Give the 'Encode' option
p.recvuntil(b':').decode() #Gets until "Enter text to encrypt:"
ourValue = 'a'
p.sendline(ourValue.encode()) #Sends ourValue ('a') to be encoded
data = p.recvuntil(b'decrypt.').decode() #Gets all program output until "…D → decrypt."
data = int(data.split(' ')[12][:-6]) #Gets Enc('a') with string splicing
log.info(f'data = {data}')
toDecrypt = int(password)*data
log.info(toDecrypt)
#Decrypts toDecrypt
p.sendline('D'.encode()) #Sends 'Decode' option
p.recvuntil(b':').decode() #Gets "Enter text to encrypt:"
p.sendline(str(toDecrypt).encode()) #Sends our payload
res = p.recvuntil(b'decrypt.').decode() #Gets all program output until "…D → decrypt."
res = res.split(' ')[10].split('\n')[0]
secret = int(res,16) // ord(bytes('a','utf-8'))
log.success(f'secret = {secret}')
secret = secret.to_bytes(len(str(secret)), "big").decode("utf-8").lstrip("\x00")
log.success(f'secret = {secret}')
p.close()
#Now we have our plaintext password, time to crack secret.enc!
res = run(["openssl", "enc", "-aes-256-cbc", "-d", "-in", "/Users/spareaccount/Downloads/secret.enc", "-pass",
f"pass:{secret}"], stdout=PIPE, stderr=PIPE, text=True)
print(res.stdout)
print('exit'
from subprocess import run, PIPE
p = remote("titan.picoctf.net",64808)
with open('./password.txt') as f:
global password
password = f.read()
#Get Banner plus options menu
print(p.recvuntil(b'decrypt.').decode())
p.sendline('E'.encode()) #Give the 'Encode' option
p.recvuntil(b':').decode() #Gets until "Enter text to encrypt:"
ourValue = 'a'
p.sendline(ourValue.encode()) #Sends ourValue ('a') to be encoded
data = p.recvuntil(b'decrypt.').decode() #Gets all program output until "…D → decrypt."
data = int(data.split(' ')[12][:-6]) #Gets Enc('a') with string splicing
log.info(f'data = {data}')
toDecrypt = int(password)*data
log.info(toDecrypt)
#Decrypts toDecrypt
p.sendline('D'.encode()) #Sends 'Decode' option
p.recvuntil(b':').decode() #Gets "Enter text to encrypt:"
p.sendline(str(toDecrypt).encode()) #Sends our payload
res = p.recvuntil(b'decrypt.').decode() #Gets all program output until "…D → decrypt."
res = res.split(' ')[10].split('\n')[0]
secret = int(res,16) // ord(bytes('a','utf-8'))
log.success(f'secret = {secret}')
secret = secret.to_bytes(len(str(secret)), "big").decode("utf-8").lstrip("\x00")
log.success(f'secret = {secret}')
p.close()
#Now we have our plaintext password, time to crack secret.enc!
res = run(["openssl", "enc", "-aes-256-cbc", "-d", "-in", "/Users/spareaccount/Downloads/secret.enc", "-pass",
f"pass:{secret}"], stdout=PIPE, stderr=PIPE, text=True)
print(res.stdout)
print('exit'
(venv) (base) gabbage@Gab-2 rsa_oracle % python rsa_oracle-decrypt.py
[+] Opening connection to titan.picoctf.net on port 64808: Done
*****************************************
****************THE ORACLE***************
*****************************************
what should we do for you?
E → encrypt D → decrypt.
[*] data = 1894792376935242028465556366618011019548511575881945413668351305441716829547731248120542989065588556431978903597240454296152579184569578379625520200356186
[*] 4879347969494695763992079257309920962956235340071608197771324952441750870022564003875958517877187374665821306399293178559399723408243829615035132429286786526803773011124941819240588649086684776588479763949051499637834997128787647253068836995761445652838138074231225267441000841604830001446657688224597433724
[+] secret = 215627228002
[+] secret = 24bcb
[*] Closed connection to titan.picoctf.net port 64808
picoCTF{yeah-im-not-telling-you-the-flag}
exit
[+] Opening connection to titan.picoctf.net on port 64808: Done
*****************************************
****************THE ORACLE***************
*****************************************
what should we do for you?
E → encrypt D → decrypt.
[*] data = 1894792376935242028465556366618011019548511575881945413668351305441716829547731248120542989065588556431978903597240454296152579184569578379625520200356186
[*] 4879347969494695763992079257309920962956235340071608197771324952441750870022564003875958517877187374665821306399293178559399723408243829615035132429286786526803773011124941819240588649086684776588479763949051499637834997128787647253068836995761445652838138074231225267441000841604830001446657688224597433724
[+] secret = 215627228002
[+] secret = 24bcb
[*] Closed connection to titan.picoctf.net port 64808
picoCTF{yeah-im-not-telling-you-the-flag}
exit
Thanks for reading!