← Back to all posts

Foundations of Cybersecurity, Notes

April 15, 2020

This past semester, I have taken CY2550: Foundations of Cybersecurity, taught by Dr. Abhi Shelat. Throughout the course of the semester, I’ve transcribed my in-class scribbles to a cohesive outline of the major topics and takeaways from the course. I’ve decided to omit complex equations in favor of capturing the concepts at an intuitive level, in an easily searchable and reference-able format.

CY2550: Introduction to Cybersecurity

There are four primary types of failures of computer systems:

  1. Failures of Operation: error in human use of the system
  2. Failures of Implementation: programming errors, such as buffer overread
  3. Failures of Design: error in how a system of designed, such as sha1 hash collisions
  4. Failures of Abstraction: error in thinking about threat model

Modern cryptography is built upon mathematical principles, which implicate precise mathematical definitions. We build our proof of security upon the condition that if a security scheme can be broken, then these mathematical assumptions are false.

For example, we assume that factoring is difficult. We will then build a cryptographical scheme such that if the scheme can be defeated, then our assumption that factoring is difficult, is shown to be false.

Expectations of Computer Systems

We have certain expectations of our computer systems:

In the Battle of Midway, US Naval forces knew that the Japanese navy was plotting to attack one of their island bases in the Pacific, but the US was unable to decrypt the Japanese radio communication.. The US Navy sent out an unencrypted message that “Midway’s water generator is broken,” and then discovered what the Japanese used to send the message “Midway” over the radio. Through this, the US was able to successfully predict that the Japanese navy would attack Midway.

One of the fundamental security games in cybersecurity is that of private communication. Alice seeks to send a message to Bob, while making sure that an eavesdropper, Eve, does not know what the message is. We will return to this idea of “not knowing what the message is” means later.

In ancient Rome, generals would send each other messages through a form of cryptography. Before going into battle, the generals would meet and find a uniform stick. They would cut this stick in two parts, each keeping half of it. When one general wished to send a message to another, they would wrap a strip of leather around this stick, inscribe their message on it, then unwrap it before sending the leather message via a courier to the other general. Upon receiving this leather strip, the other general would wrap it around his identical stick, and read off the message.

Julius Caesar devised the Caesar Cipher, which maps each letter of the alphabet to a corresponding letter shifted by a set number of places. The failure in design of this system is that the keyspace is too small, with only 26 possible keys. Attackers can simply try all 26 possible keys. With similar substitution ciphers, attackers can use frequency analysis of common letters in the English language to decipher the message.

In 1883, Kerckhoff, a French military communication scholar, published a paper outlining the basis for cryptographical communication. A cryptography system should have three properties, he argued:

  1. The system should be mathematically indecipherable
  2. The system should not be kept a secret
  3. The system should use a key that is kept secret

Cryptographic systems are created in a four part process. Vulnerabilities can arise in all parts of this process.

Abstraction ⇒ Design ⇒ Implementation ⇒ Operation

Private Key Encryption

Computer networks are a public resource. How can we add privacy (confidentiality) to such systems?

Private Key Encryption is composed of three algorithms:

  1. Generate key and provide this key to Alice and Bob
  2. Alice encodes a message with this key, sends this ciphertext to Bob
  3. Bob decodes the ciphertext received from Alice, and reads the message

Shannon Secret

Eve should not learn any more information about the message than she knew before she saw the ciphertext. Eve may have some a priori knowledge about the type of message, its contents, or its distribution, but seeing the ciphertext should not add any new knowledge.

Perfect Secrecy

Given functions (gen, enc, dec) and sets of messages and keys (M, K), an encryption scheme is said to have perfect secrecy with respect to a distribution D over M if:

For any pair of messages m1, m2 in M, Eve cannot tell whether ciphertext c is an encryption of m1 or of m2.

Perfect Secrecy is equivalent to Shannon Secrecy.

One-Time Pad

The one-time pad is a perfect encryption scheme. It achieves perfect secrecy and of course Shannon secrecy. It is also called the Vernam Cipher.

Given a message space as an n-bit binary, we begin by creating a secret key that is the same length as our message by randomly sampling bits. We then XOR each bit of our message by its corresponding bit in our key. We now get a ciphertext that could be the encryption of any n-bit message.

The one-time pad is perfect, but has a significant limitation: the key has to be the same size as our message, and reusing keys will break our perfect security. We would like to have a fixed-size key that is small.

Pseudo-Random Generators (PRG)

Against an adversary who has unlimited computational power, only the one-time pad is safe. This is unfeasible, so we look at adversaries who usually don’t have unlimited computational power.

We would like to use the one-time-pad, so we have a new goal of taking one short key and using that short key to create many long keys. This long, generated key should be indistinguishable from a truly random key.

Ultimately, our concept of pseudorandomness is not absolute, but is based on computational power of our adversary. This is analogous to the set of problems for which the ability to answer correctly depends on computation power. As the size of the parameterized problem increases, the difficulty of answering increases.

Computational Indistinguishability: Given two parameterized experiments, X and Y, as experiment size increases, no probabilistic polynomial time (efficient) algorithm can succeed in distinguishing X from Y.

Discrete Logarithm Problem

We can build pseudo-random generators by using functions that have the property of being computationally easy in one direction, but computationally intensive to reverse. For example, f(x) = 7x mod p. It is easy to compute the solution y for any x, but given a solution y, it is computationally very difficult to figure out what x produces that y. This is a function for which f(x) is easy, but f-1(x) is difficult.

Blum-Micali PRG

The Blum-Micali pseudo-random generator takes in an input of length n and outputs a result that is of length n+1. It works by taking an input s, taking gs mod p, and then outputting the result and concatenating the first bit of s. Predicting the next bit of the output of this pseudo-random generator is as hard as solving the discrete logarithm problem, which is accepted as just being hard.

We’ve given up our concept of perfect security in favor of computational security. We rely on how hard it is to solve the reverse logarithm problem, trusting that thousands of years of mathematical study on cracking the reverse logarithm problem indicates that this is indeed a very difficult problem.


Our previous game for perfect security can be described as such

  1. Key is generated and given to both Alice and Bob
  2. Eve picks two messages, m1 and m2 from Alice, with |m1| = |m2|.
  3. Alice picks either m1 or m2, encrypts it, and then sends it to Eve.
  4. Eve guesses whether the ciphertext was of m1 or m2. The probability that Eve guesses correctly should be equal to ½.

This game doesn’t quite encapsulate what happened at the Battle of Midway, however. The US was able to convince the Japanese navy to send a certain message – essentially the US was able to control the message that was encrypted. We can model this with the Indistinguishability under Chosen Plaintext Attack game.

IND-CPA involves a query phase, where Eve is able to send multiple plaintexts to Alice, who will encrypt them and show them to Eve. Only after Eve is satisfied, will Eve send two messages to Alice to encrypt and then guess.

IND-CPA immediately rules out the Caesar cipher, as encrypting the same message twice gives the same ciphertext. If we use the one-time pad and never reuse our keys (perhaps by keeping track of how much key material has been used), we can satisfy this stronger game.

Authentication: MACs

We turn our attention now to authentication: making sure that whoever sent us the message is who they claim to be. “Did Alice or Eve send me this message?” The solution lies in MACs, Message Authentication Codes. People have tried to solve this age-old problem through approaches such as signatures and special coins. These approaches aren’t quite good enough.

MACs have three functions:

  1. Gen(1n) creates a key
  2. Signk(m) generates a tag/signature for a message
  3. Verk(m) verifies a message and tag given a key

Here is how MACs are used:

  1. A key is generated and shared between Alice and Bob
  2. Alice signs her message as a function of both the key and the message
  3. Alice sends both the message and signature to Bob
  4. Bob will verify the message and signature pair using the key shared with Alice

Our goal is to make sure that an adversary cannot forge a tag for a given message, even when given a tag oracle. Eve should be able to see examples of tags, and Eve should be able to forge any message of his/her choosing.

We can derive a game for Eve for MACs:

  1. A key is generated and shared with Alice and Bob
  2. Eve asks Alice to sign a bunch of messages (Eve is given a tag oracle)
  3. Eve produces a message, tag pair that is different from any previous queries.
  4. Eve wins if Bob verifies that this message, tag pair is actually from Alice

Pseudo-Random Functions

To achieve this functionality of MACs, we need to have random functions. A random function is a length-preserving mapping between inputs and outputs. Two outputs can be the same, but due to the random nature of the function, this will be unlikely.

A pseudo-random function is a function family that is computationally indistinguishable from true random functions. A pseudo-random function must be able to compute outputs in probabilistic polynomial time.

A distinguisher is given a pseudorandom function or a true random function. The distinguisher can query the mystery function as many times as it likes. It must then produce a verdict if it was querying a pseudorandom or true random function.

We can construct a pseudorandom function from pseudorandom generators. Given a PRG that doubles its input every time, we can construct 2n possible outputs with only n calls to the PRG.

AES is one popular PRF that is very fast. It is complicated. There are a number of PRFs that exist, including ChaCha20.

Public Key Crypto

The problem with the symmetric cryptography model is that you need to have and exchange different keys for everyone you talk with. The solution is public key crypto.

Instead of generating the same key for both parties, key generation creates a public and private key. The public key is distributed publicly, and is what other people use to encrypt messages for the recipient. The recipient then uses their secret key to decrypt these messages. Given only the public key, it should be computationally impossible to figure out the secret key.

  1. gen(1n) ⇒ (pk, sk)
  2. c = Encpk(m)
  3. m’ = Decsk(c)

IND-CPA for Public Key Encryption

  1. A key pair is generated, with Bob receiving a secret key and Alice and Eve receiving the public key
  2. Eve sends Alice two distinct messages, m1 and m2 for her to encrypt
  3. Alice picks one of the messages, encrypts it with Bob’s public key, and sends it to Eve
  4. Eve wins if she can tell which of the two messages Alice encrypted

El-Gamal Encryption

Key generation

A key is generated for Bob like so:

  1. Find a generator g for the group G of order q and identity e. This means that (g • n) mod q will give all elements 1, … G for sufficient n.
  2. Choose a random integer x between 1 and q
  3. Compute h = gx mod q so that h is inside G
  4. Public key = (G, q, g, h) Secret key = x


Alice can encrypt messages for Bob using his public key like so:

  1. Choose a random integer y between 1 and q
  2. Calculate the shared secret s = hy
  3. c1 = gy c2 = m • s
  4. Bob sends ciphertext (c1, c2) to Alice


Bob can decrypt messages he receives like so:

  1. Calculate the shared secret s = c1x = gyx = hy
  2. Compute s-1, the inverse of s in the group G (perhaps by extended Euclidean Algorithm)
  3. Compute m = c2 • s-1 since c2 • s-1 = (m • s) • s-1 = m • e = m where e is the identity element of the group

Euler’s Totient

Euler’s totient function returns the number of positive integers up to n that are relatively prime to n

Euler’s Theorem

Euler’s theorem is a method of taking the modulo of numbers raised to large exponents.

Textbook RSA

Key generation

  1. Pick n = p • q where p and q are prime numbers
  2. Pick e such that e is relatively prime to ɸ(n)
  3. Pick d, the modular inverse of e in the group of order ɸ(n)
  4. (e, n) is the public key, and (d, n) is the private key


c = me mod n


m = cd mod n

Note: Textbook RSA is not IND-CPA secure

Hash Functions

Hash functions are used in RSA signing functions. We pad the message, hash it, and then raise it to the power of a secret key.

A hash function maps many bits into fewer bits. Collisions are guaranteed due to the pigeonhole principle, but they should be rare. Hashes are usually computable in O(1) time, and often used in lookup tables.

Hash functions have the property that they are easy to compute, but difficult to find the original message from the hash. Originally, md4 and md5 hashes were used that have 128 bits, but were found to be too weak due to the birthday paradox. If you have a hash collision, you can send two messages with the same signature despite the messages being different.

We consider SHA256 to be the standard hash function, as it is indistinguishable from a random oracle (a random function on arbitrary length messages).


Examine the problem: Alice wants to authenticate herself to Bob through some human-usable method. MACs don’t work in this case. Passwords have many problems. Passwords are also known as natural authenticators, and can take on several forms:

  1. Something you know – a shared secret you can reproduce

  2. Something you have – a physical key

  3. Something you are – a unique property of you that is difficult to reproduce

Attacks against the password model can take two approaches: an online brute force attack of just trying many passwords, and password file theft.

Hashing Passwords

You should never store passwords in plaintext, since when an attacker steals this file, they will have access to all the passwords in usable form. Instead, we hash passwords and only store and compare the hashed versions of passwords.

Offline Brute Force Attacks – Dictionary Attacks

Simple hashing of passwords is vulnerable to offline brute force attacks. When an attacker steals a password file containing hashed passwords, he can generate hashes for common passwords that he suspects people are using. He can then compare this list of potential hashes with the list of known hashes, and figure out what people’s passwords are. He may also group all passwords by the same hash, using the power of many combined hints to help him guess what the password may be.

Salting Passwords

To mitigate dictionary attacks and other offline attacks, we can add a random salt to each password before hashing it. Salts are stored alongside the password, but are of no use to an attacker trying to un-hash the password. The effect of salting is now that two passwords with the same text will not have the same hashes. Dictionary attacks will no longer work at scale either, since the attacker has no idea what the salt is.

Hashing is Getting Faster

Stored passwords should always be salted and hashed. Unfortunately, password hashing is getting much faster due to faster computers. This opens up more vulnerabilities to both offline and online attacks.

While an old solution would be to hash the password multiple times, a new better solution is to design slower hash functions – hash functions that take longer to compute.

Password Security Games

In our password security game, we must assume that an attacker Mallory can steal the list of all passwords. Hashed passwords are of no direct use to Mallory. However, Mallory can still use this information for malicious purposes. One significant vulnerability is that two identical passwords hash to the same thing – this means that we can still determine some information about the password from its hash. Simple hashing also allows for offline attacks since people pick common, simple, predictable passwords.

Dictionary Attacks

An attacker performing a dictionary attack will use dictionary words, common passwords, and individual data to generate possible passwords for each individual. The attacker then hashes these possible passwords. When the attacker steals a list of hashed passwords, he simply compares all of the stolen hashes to the possible hashes, and can recover the plaintext passwords.

Brute Force Attacks: Rainbow Tables

Given 95 possible characters, and a password of length 8, the total number of possible passwords is 958. This is a lot, but still feasible. We can do better, however, if we find a way to match hashes back to passwords. This way, we can store less and compute more.

We begin with a starting password string p, and hash it. We take that hash, and apply a mapping function that maps from the domain of hashes to the range of possible passwords. We hash that password, and continue in this fashion to build a chain. Ultimately, we only store the beginning password plaintext, and the final hash.

When an attacker has stolen a hash, we repeat the process of mapping that hash to a password and hashing that password. We perform this a large number of times. If the hash we ever get is equal to the final hash we stored when building our chain, then we will know that the stolen password is somewhere within the chain we precomputed. Then, it is trivial to start at the beginning of the chain and hash until we uncover the plaintext that hashes to the stolen hash.

An attacker can make many of these chains with different ending hashes, covering all or most of the entire dictionary.

Best Practices

Using salted hashing renders rainbow tables useless, as you will need to guess the right salt when pregenerating your passwords. It will take much longer, and attackers will have to guess each password individually.

  1. Hash passwords
  2. Salt hashes
  3. Use slow crypto (i.e. bcrypt)

Dealing With Breaches

A breach of security should be considered inevitable. We can use honeywords and honeyservers to discover when a breach has occurred. In our password database, we store honeywords: a number of fake passwords for every user that are created to look exactly like human-generated passwords. On a separate machine, we operate a honeyserver: a database that stores which passwords are the actual user-created password.

If Mallory steals and cracks the password database, it is likely Mallory will use a honey password instead of the real user-created password. If anyone tries to log in using a honey password, we can be almost certain that our system is compromised.

Defense in depth means that password information should be split up into multiple places, such that if an attacker only compromises one machine they should not have any useful data.

Among the biggest security vulnerabilities of passwords come from people forgetting their passwords. Password reset requires some form of secondary authentication, and knowledge-based authentication is extremely insecure (mother’s maiden name, birthplace, etc.).


Two-factor authentication is based on two of these categories: something you know, have, or are.


Fingerprints, handwriting, voice, typing patterns, gait, face, and voice can all be used to authenticate. Biometrics suffer from weaknesses that they are immutable, since you are the password, and once compromised, there is no way to reset it. Passwords and tokens can be exchanged, but physical biological attributes cannot. High value applications should avoid using biometrics.

SMS Two-Factor

SMS two-factor authentication is based on the assumption that only your phone will get a message that is intended for it. Unfortunately, this should be considered deprecated due to sim swapping attacks where another phone now gets messages intended for yours. Social engineering can be used to convince the phone company to cancel your sim or to send a new sim to someone else, thereby routing all messages to their phone.

One-Time Passwords

Google Authenticator or Duo are two common one-time password applications. They are initialized with a QR code, which is a shared secret for a pseudorandom function. This sets up a time-based one-time password generator, the results of which should be the same as that on the server.

One-time passwords have the vulnerability that someone who steals the secret key can just go and generate all the verification codes.

Hardware Two-Factor

A USB dongle contains a secret key for public key encryption. The dongle is built to resist key extraction, such as through electron tunneling microscopy. These dongles can also store SSH, PGP, and other keys.

Hardware two-factor authentication is vulnerable to a simple phishing attack. Phishing attacks are a failure of abstraction because we don’t expect the human to give the password to an attacker.

Authentication & Authorization

Authentication is the process of verifying an identity assertion about a subject on behalf of a principle. We’ve studied many methods of making an identity assertion: passwords, 2FA, biometrics, etc.


Authorization is the determination on what resources a subject can access. These are defined through an authorization policy.

Discretionary Access Control (DAC)

Under the Discretionary Access Control model, rights to access a resource can be transferred to users. Users control sharing, and a subject with certain permissions can pass on those permissions to another user.

Access Control Matrices/Lists

The DAC model can be represented by an Access Control Matrix, where rows contain subjects and columns contain objects. Each cell contains the permissions that a certain subject has on a certain object. Within an Access Control Matrix, each column is the Access Control List for this subject.

Access Control Lists/Matrices are flexible and easy to configure for an object, but the downsides are that every object is different, leading to difficulties in maintaining large systems.

Unix Style Permissions

All objects have an owner and a group, and permissions are assigned to three things: the owner, a certain group, and the universe (everyone else).

drwxr-xr-- marc coolPeople

The first character means that this is a directory, rwx means that the owner marc can read, write, and execute this file, the second triple of characters r-x means that the group coolPeople can read and execute, and the third triple of characters r-- means that everyone else can only read.

The unix style of permissions is simple to manage and understand, but has the downside that not all policies can be encoded.

Capability Based Systems

Instead of taking each column of an access control matrix, we here use each row of the access control matrix. A common example of such a system is in mobile devices, where applications ask the users for permissions based on individual actions they wish to perform: use the microphone, access files, access location services, etc.

Failures of Discretionary Access Controls

Any user can give their own permission to others, and in many systems this is unacceptable. Users with access to top secret files can simply give this permission to another person. A malicious program can read sensitive data and export it to a not-so-secret place, compromising security. If any subject is compromised, you lose confidentiality.

Mandatory Access Control

Under a mandatory access control system, system policy determines access control. Subjects and users cannot give, share, or modify permissions of other subjects. In essence, mandatory access control restricts the access of subjects to objects based on system policy.

Bell-Lapadula Model: “No read up, no write down”

Under this model, you cannot read above your security level, and you cannot write data below your security level. A user cannot access information that is at a higher level than they are, and they cannot write sensitive data to a lower level than themselves, preventing leaks.

Under the Bell-Lapadula system model, every subject has a clearance, and every object has a classification. Subjects may operate at any clearance less than or equal to their top clearance.

A computer operating under the Bell-Lapadula system model has a state, and the computer undergoes state transitions whenever an operation occurs. Such a system is secure if all transitions satisfy these properties:

The Bell-Lapadula Model does not cover other attacks that are still possible, such as covert channel attacks that make use of side channels.

Biba Integrity Policy: “No read down, no write up”

The Biba Integrity Policy can be considered the opposite of the Bell-Lapadula model. Biba is built on the paradigm that we should not rely on information that is below our security threshold, nor write information above our threshold. For example, a system deciding whether or not missiles are coming from Nebraska should only use information above a certain threshold of quality, and should be able to write its findings at its same level and that below it.

Bell-Lapadula Biba
Confidentiality as main principle Integrity as main principle
Read down, write up Read up, write down
Control of reads Control of writes
Subjects don’t need to be trusted Subjects must be trusted
Malicious programs can’t leak secrets that they don’t know Malicious programs can write bad information

Security Lattices

Security lattices are another way to consider security levels. Security lattices are made of clearances and compartments, such as “Secret Nuclear”, “Secret Crypto”, “Top Secret”, “Top Secret Nuclear”, “Top Secret Crypto”, “Top Secret Nuclear, Crypto”. Security lattices ensure that subjects have access to resources on a need-to-know policy. Subjects are only given access to objects necessary for functionality.

Hybrid Systems

Numerous systems combine both Discretionary Access Control and Mandatory Access Control, such as SELinux and TrustedBSD, which both use a DAC and MAC.

Social Engineering

Social engineering attacks are failures of operation. Some common attack categories include:

Cognitive Biases

In our everyday lives, we rely on heuristics to handle a surplus of information. These pattern-matching behaviors often lead to cognitive biases, which are tricks our minds play on us in an attempt to simplify our world.

Using these biases, successful attacks rely on three attributes:

  1. Information Asymmetry: attacker has more information than the victim, or information the victim doesn’t expect anyone else to have

  2. Context Construction: attacker builds a context for the victim to receive the information

  3. Elicitation and Persuasion: attacker persuades the victim to do something in response to this information

Behavioral Biases

Social Biases

Memory Biases

Threat Modeling

We use threat modeling to systematically identify threats faced by a system.

  1. Identify assets to protect
    • Passwords, credentials, 2FA authentication tokens
    • Contacts, pictures, addresses, and other private data
  2. Enumerate attack surface: what are the access points that an attacker can exploit?
    • Device ports: USB, power, microphone, wifi, bluetooth, other IO devices
    • Laptops and computers can be stolen
    • Web services, network ports, network itself
    • Vulnerabilities of operating system or vulnerabilities in dependencies
    • Social engineering attacks and application-specific surfaces
  3. Define adversary: what powers does the adversary have, what kinds of attacks can they mount, and what are their motives?
    • Cybercriminals are motivated to make money somehow
    • Powers can vary
      • Social engineering attacks
      • IO/USB access, physical access to device
      • Zero day vulnerabilities
    • Goal is often to run an arbitrary process on your computer
      • Ransomware is easily monetized
      • Botnets: private cloud services using your computers
      • Spyware: steal browsing information or other data, used for phishing or selling
      • Adware: force people to view advertisements
      • Mining: use computational power to join mining pools and mine cryptocurrencies
  4. Survey and choose mitigations
    • Authentication: restrict both physical and remote access
    • Access controls: discretionary and mandatory
    • Firewalls and intrusion detection systems
    • Malware and antivirus scanners
    • Secure logging with non-repudiation
  5. Balance costs and risks

Systems Security

Systems security deals with failures of implementation and failures of design. Previously, we discussed failures of operation (social engineering), as well as failures of abstraction (cryptography).

Systems Security Principles

Defense in Depth

Modern operating systems have a variety of security features that all work together to make sure that even if certain features are breached, still more layers offer security.

Separation of Privilege

Separation of Privilege dictates that privilege, or authority, should only be distributed to subjects that require it. Some components will have less privilege than others. For example, on mobile devices, every app runs as a specific user, and no app can access the data of other apps.

Principle of Least Privilege

Subjects have only the authorities required to operate successfully in the way they were designed. For example, within a Docker image, chroot only shows the processes within the environment of the sandbox. Modern operating systems separate unprivileged processes from the higher level privileges that the operating system may have.

Compromise Recording

Assume that attacks will occur, but always record how they occurred. Logging that is tamper-evident or tamper-proof will ensure that attackers cannot simply remove traces of themselves from a system.

Work Factor

Increasing the difficulty of mounting attacks makes systems more secure. Increasing the entropy time, ASLR, and recompilation with randomness factor can make it difficult for attackers to mount attacks since more variables are unknown. Authentication rate limiting, and usage of slow crypto are other useful techniques.

Systems Security Heuristics

Systems Architecture

Many of the decisions made during the 1980s in PC architecture still plague us today. Systems are comprised of a core and a chipset. The core handles computation, memory, and graphics, while the chipset handles IO, memory, and interfacing with all other hardware components.


Memory can be thought about as a spreadsheet with a single column, and where each row has an address and holds 1 byte of data. Memory addresses are in 32 bits and 64 bits, depending on the system, and memory locations can hold either data or instructions. Instructions are assembly language commands that the CPU understands.

Boot Process

  1. CPU loads BIOS into cache. BIOS is stored on a piece of ROM or EPROM, Electronically Programmable Read Only Memory.
  2. BIOS sits at very top of memory, and CPU begins executing
  3. BIOS instructions begins hardware initialization
  4. BIOS applies microcode patches: certain CPU operations may have bugs in them, which are first corrected using these patches that the Intel Management Engine may have fetched.
  5. Firmware support packages are loaded, which are basic drivers that set up RAM and some firmware. Now we can use more than the CPU cache – everything in the BIOS before here could not do function calls, as there is no stack.
  6. CPU copies firmware to RAM and starts executing in RAM
  7. Sets up interrupts, timers, clocks, other cores, PCI, ACPI tables
  8. Executes OS loader
  9. Kernel initialization begins
  10. Kernel begins user mode once entire kernel is brought up

How Processes Run

The operating system first loads itself into memory, usually towards the very top of the memory. The role of the operating system is to allow the user to abstract on top of the hardware, allowing users to easily run processes and managing the resources of the hardware to allow access for all users.

Monolithic architectures have these issues, but were how operating systems worked for 15 years or so. The problem with this architecture is it does not protect memory or devices: any process could access any memory or device. It becomes impossible to maintain any form of security, as it is impossible to enforce access controls on users or devices. Processes can steal data from each other, destroy each other, or even modify and destroy the operating system itself.

Memory Unsafety

If memory is a commonly accessible resource, any process would be able to read or write any memory. One process would then be able to read some other process’s memory, or read/write into the OS memory. This would mean that no process could rely on safe memory semantics – what was written in the past will be what will be read in the future.

Device Unsafety

If devices such as IO are commonly accessible resources, then any process would be able to access any hardware device directly, and any process could read/write data meant for another process.

Hardware Security Primitives

Rings (Protected Mode Execution)

Processes must run in certain security rings that limit what access and powers the process can have.

Most operating systems only use rings 0 and 3, for the kernel and userland respectively. Rings -1, -2, and -3 exist, and things like the Intel Management Engine (MNIX) run below ring 0 in order to modify ring 0 code. For example, the Intel Management Engine runs a web server at ring -3 even when the computer is powered off, letting system administrators patch code for machines even when powered off.

Within the ring structure, system boot sequences look like:

  1. CPU starts in 16 bit “real” mode. Protected mode is disabled, and any process can access any device.
  2. BIOS executes, finds, and loads operating system.
  3. OS switches CPU to 32 bit “protected” mode, with the OS running in ring 0 and deciding what ring to put other programs in
  4. Shell is executed, and the user can run programs in ring 3

Ring 3 processes cannot:

If a ring 3 process tries any of this, the process immediately crashes.

System calls are ways for user-level processes to communicate with the OS, or do something that requires hardware access or otherwise a lower ring number. System calls cause a mode transfer from ring 3 to ring 0.

Still, however, this system does not protect against memory unsafe attacks. Malicious processes could overwrite OS memory to remove access control checks, change the kernel, and more. We need to provide memory isolation.

Virtual Memory

The operating system manages virtual memory to look like physical memory for each individual process, allowing for proper separation of memory. This requires the CPU to perform operations that map between virtual and physical memory addresses. This is done by the Page Table, which is built into the hardware and operating system, and requires a special set of registers to perform these mappings very quickly. Whenever a process asks for a page of memory, the CPU must first perform the lookup in the page table, and return the data at the physical memory address.

More Advanced Protections

Atop these hardware security primitives, we can build more advanced protections.

File Access Control

All disk access is mediated first by the operating system. Since the operating system runs in ring 0 but all userland processes run in ring 3, the operating system has the power to enforce mandatory and discretionary access control systems. Nevertheless, malware can still cause damage by opening files while unintended by the user. Discretionary access control means that isolation will never be truly complete.

Antivirus Systems

Antivirus software often runs in a privileged state, or in ring 0 since it needs to be able to access all files and system internals. Antivirus software scans files looking for signatures of viruses, which can include names, strings, and other material that uniquely identifies files as malware. However, it is difficult to be completely accurate with the use of signatures. Signatures are difficult to define, and loose signature definitions will result in many unuseful false positives. Virus polymorphism means that malicious software can present in many different ways while accomplishing the same malicious goal. Similarly, virus authors can simply encrypt their viruses, making them even more difficult to detect.


Firewalls run in ring 0, and inspect incoming and outgoing connections. Firewalls can selectively block network traffic by process, port, IP, or other in hopes of protecting against malicious connections.

Network Intrusion Detection Systems (NIDS)

NIDS use heuristic rules to detect attacks depending on system actions. These systems depend on the policy and quality of rules, and rely on analyzing monitoring and logging systems in place.


Insecure logging is simply writing to an unprotected log file, which leaves the file open to malware manipulating or destroying the log. Secure operating system logs use the operating system’s API calls to add entries to read-only, secure logs that cannot be tampered with. These are often found in /var/log.

System Exploits

System exploits are failures of implementation.

Attack: Buffer Overflow

Attacker’s Goal
  • Inject malicious code into a program and execute it
  • Gain all privileges and capabilities of the target program
Attacker’s Capabilities
  • Environment parameters of process
  • Control command line parameters
  • Inject network data
System Goal
  • Prevent these attacks
  • Gracefully handle program failures
Attacker Win Event Attacker opens a shell with the same privileges as the attacked subject

Buffer overflows work by causing memory corruption to the stack, occurring when a program reads input from an attacker that is too large than the memory space allocated for it. Usually, this only causes a program to crash through a segfault, but attackers can try to modify the stack memory data to take over execution. Low level, non-memory safe languages like C are susceptible to attacks like this.

When a function is called, the stack contains the arguments to the function, the next instruction pointer, the previous stack function, and then the local variables of the function and the function body itself. By sending more data than is allotted for the arguments of the function, this data can overflow into and overwrite the next instruction pointer. This can be hijacked to make the function execute some unintended code after returning. Usually this other code is a shellcode, whose goal is to open a shell program using some already assembled assembly code placed as the payload for the buffer.

Zero-clean Codes: Since the strcopy command is commonly used but will stop copying when it sees a 00 (since strings are null-terminated on most systems), attackers are forced to use zero-clean shell codes. Zero-clean shell codes do not contain a single 00, so that strcopy will be forced to copy the entire code.

NOP Sleds: Reliably guessing the start of our payload when sending an instruction pointer is difficult. Fortunately, CPUs support a no-op command (NOP), which tells the CPU to not do anything for a cycle. By putting a bunch of these no-op commands in front of our shellcode, our shellcode will execute even if the instruction pointer is placed anywhere within this NOP sled.

Mitigation: NX

The buffer overflow attack requires execution on the stack. One way that operating systems mitigate this attack is by using NX, which requires that every page on the stack is either read/execute or read/write. This prevents any code from being executed which was not put there intentionally. Often code libraries will be set to read/execute, while all data segments will be read/write or just read. This is a simple mitigation that simply requires the compiler to properly define what type each memory page will take on.

Attack: Return-to-Libc

While NX prevents executable code from being injected into the system, an attacker can still use existing memory pages that are executable to create their own attack. Specifically, an attacker can use the standard C library to control program flow. Libc is a very large library, and since it is a library, it is stored in read/execute memory pages. Libraries are often stored in a certain location in memory, and one can easily guess where it is.

The compiled Libc library has many commands, but each command consists of several CPU instructions. Interestingly, when the instruction pointer is set to the middle of a command, the resulting instructions that get executed can be very different from the intended behavior. An instruction is ended by a C3 instruction. Within the standard C library, there are several thousand C3 instructions, whose previous instructions can be strung together to create an attack.

The return-to-libc attack sets each value on the stack to either a constant or to a pointer that points to a gadget, a piece of code in the C standard library that ends in C3. The goal is to string together enough of these to execute /bin/bash or a similar attack. This attack circumvents NX.

Mitigation: ASLR (Address Space Layout Randomization)

ASLR mitigates the return-to-libc attack by randomly placing various segments of the program at different locations in a virtual address space. Unfortunately, this is not too random, since there are only certain places where systems can put libraries like the C standard library.

Attack: Memory Guessing

In response to ASLR, attackers can simply guess where the C standard library is residing. Since the entropy for placing large libraries is usually not very large, sufficient number of guesses may reveal where it is.

Mitigation: Stack Canaries

As a compiler option, a special block of values (the canary) is inserted between the instruction pointer and local variables. When the function returns, the execution checks that the canary is still intact. If these values are not present or corrupted from when they were written, the program is halted, since that signifies some tampering of memory. This is a further mitigation for buffer overflows and return to libc.

There are many other memory corruption techniques and bugs that can be taken advantage of, including saved function pointers, vulnerable format strings, exception handlers in C, heap data structures, and virtual tables in C++.


Network attacks primarily attack privacy, authenticity, and availability. Networks were originally designed for convenience in a closed, honest environment. At the time, security was an afterthought.

An ethernet packet contains metadata about the receiver, sender, MAC address, and size, alongside the IP packet.

An IP packet contains metadata about many flags, as well as the sender and receiver IP addresses. It contains the TCP packet data.

A TCP/UDP packet contains the sender and receiver port number, a bunch of flags, as well as the actual data inside.

The problem with this protocol is that there is no authentication who the packet is from. Senders of packets can simply spoof the sender address.

Amplification Attacks

An attacker can set a ping’s source address to the victim’s IP, and then send this ping via broadcast to many machines or a network. All the computers on this network will then return this ping, and all send it back to the victim’s computer, which will get overwhelmed. In this attack, the attacker need only send one ping and get hundreds or thousands of pings sent to a target.

TCP Handshake Overflow Attacks

The TCP protocol begins when a computer A sends a syn request to a computer B. Computer B will store this request, and send back an ack and another syn. Since networks can be slow, computer B will store this data for a while while waiting for an ack from computer A. The attack is to send thousands of syn requests to a machine, who will keep storing these requests until kernel memory is used up. Each 132kb packet causes a 1024kb allocation, and so by sending thousands of these syn requests to a machine, the attacker can use up kernel memory.

Ping of Death

While a normal ping contains and only requires 32 bytes, an attacker can send a 65kb ping request, causing a buffer overflow. This could allow an attacker to gain control of a kernel in early networking implementations.

DNS Traffic Amplification

DNS servers provide lookup services, and map names to IP addresses. When querying a DNS server, a 50 byte UDP request can get back a 506 byte response, which is 10x amplification or more. By creating many DNS queries with the sender address the victim’s IP address, the victim’s computer will get bombarded with a large amount of data.


Firewalls control traffic between networks. They can block incoming traffic based on certain techniques:


Tradeoffs are always made between security and convenience, and especially in the case of the design of the browser. This means that there are many attacks that are possible against the browser model.

We expect a safe browser to have certain properties:

HTTP Protocol

HTTP is the message exchange format used by browsers. HTTP is a stateless protocol, unlike TCP which keeps track of connection info (see TCP handshake overflow attacks). This means that each request is independent of the other requests, making it highly efficient for servers to handle requests. HTTP supports a number of operations, including GET, POST, PUT, and DELETE. Each response to a request is followed by a response code, a 3 digit code that indicates the status of the request response.

Browser Execution Model

  1. Load the resource
  2. Render: interpret the HTML and display the content
  3. Respond: handle user events, network events, OS events, and browser events
    • User / UX events: onClick, onMouseOver, onKeyPress
    • Browser events: onLoad, onBeforeUnload, setTimeout, clearTimeout

Document Object Model (DOM)

The DOM is an abstraction over the HTML components of the page. Every element on the page has a set of properties, and being able to interface with these elements and properties allows web pages to modify themselves by editing their DOM using JavaScript. This DOM may include private information, and a malicious page could potentially send your private data from the DOM to another server.

Browsers are incredibly complex, and they allow the execution of arbitrary code from multiple different origins. How can we isolate code and data from different origins?

Image Attacks

A very basic attack utilizes the fact that images are often automatically loaded, making a request to a server without the user’s consent. By encoding some private page data in the URL request, the server that the request is sent to will now learn that private data.

Malicious web pages can use this tactic to query other computers from inside a local network, by making request such as Measuring the time for a response can yield insight into the internal structure of a network, such as which machines have servers running, what are the IP addresses, where are the firewalls, etc. This page can then send all this data back to a malicious server.


The principle that we want to achieve with our browser model is complete isolation. This means that malicious sites should not be able to do anything to your computer, and that two sites should not be able to interact when you visit them at the same time. It should also be safe to delegate part of one site to another, through iframes.

Same Origin Policy (SOP)

Every page in a browser has a frame, which has a property of the origin. For isolation, frames should only be able to access resources from their own origin. An origin consists of a scheme + host + port.

Pages with different origins should be isolated. For example, JavaScript in a frame A.com should not see anything in B.com frame.

Exceptions to Same Origin Policy

There are many exceptions to the Same Origin Policy, however. Web pages are allowed to:

People soon found that the Same Origin Policy was a bit of a pain, and became annoying to companies who maintained many servers. Pre-flighted queries to a server can allow other origins to be approved. This requires HTTPS.


HTTP is a stateless protocol, but many applications require some form of application state or user data to be shared between the user and the server. State data could be kept in the URL, but this is not secure as the URL is publicly visible. Data could also be kept in hidden forms, but this meant that all operations had to be POST operations and this became cumbersome.

Cookies were developed to add some information to every HTTP request, effectively creating a shared state between the browser and the server. When the server sends back a “set-cookie” command, the browser will store that data, and a “get-cookie” can be used to retrieve the data of a cookie.

Objects from embedded resources are also allowed to set cookies. Facebook’s Pixel can send back the Facebook’s user cookie ID when it is embedded on another page’s website, providing data to the website as well as Facebook.

Different web pages have different cookie jars, and these cookie jars are isolated. One web page cannot read or write cookies belonging to another web page.

Browser Attacks

A significant amount of sensitive information is stored in the browser, including data such as the user’s browsing history, usernames and passwords, and any saved information in forms and cookies: credit card information, addresses, etc. Browsers do their best to secure this information, but of course tradeoffs are made between security and convenience/usability. Cookies are persistent data, and as such are a common target of attacks.

Threat Model

We make some assumptions about the threat model, to focus our attacks on the browser itself:

Attacker’s goal: steal information from the browser

Attacker’s capabilities: trick the user into clicking a link, directing the user to a site the attacker controls

CSRF Attack

The CSRF attack tricks the browser into making a request the user did not initiate. It relies on delegation and the Same Origin Policy. A malicious web page can make a request to another origin, and when that request is created, the browser automatically will include the relevant cookies from the cookie jar. This allows a malicious site to create requests on behalf of the user’s identity, but without the user knowing.

CSRF attacks can be defended against by utilizing secure tokens on every form that gets submitted. This secure token is hidden and preferably unguessable, with a set expiration and verifiable contents that are related to the session. This makes it impossible for an attacker to create a valid request including this token. Server referer validation, custom HTTP headers, and the use of HTTPS make this attack less commonplace.

XSS Scripting

The Cross Site Scripting attack relies on data that is dynamically written into a web page being interpreted as valid JavaScript and then run without the user’s knowledge. Of course, this code can be used for malicious motives, such as extracting a user’s private information from cookies. There are three primary ways to run code from an untrusted origin:

  1. Reflection: content in the URL is reflected back, by being written blindly into the body of a web page without validation or escaping it. The browser rendering engine interprets this as a block of code, and runs it without checking. This code can be used to access cookies or other data.
  2. Storing: an attacker submits malicious code to a web server, which then persists this malicious input. Users who then access this server resource will get this malicious code written to their page, and executed in their browser.
  3. DOM based: purely client-side injection, by modifying the DOM directly.

XSS can be mitigated by only storing cookies coming through valid HTTP headers, client-side filters such as X-XSS-Protection, and server side defenses. These include input validation and sanitation to prevent reflection and storing, and output sanitation to ensure that all strings sent to clients are HTML safe.


Structured Query Language is a popular way for web servers to access databases, for persisting user information. SQL databases enable concurrency, handling multiple queries in parallel; and transactions, which consist of complex updates.

Summary of Exploits

Exploits are failures of implementation, and are weaponized program bugs. Attackers create exploits by violating the programmers’ expectations of data, including size, structure, frequency, or unexpected characters and delimiters. These violations can cause programs to behave unexpectedly or maliciously, bypassing authentication and authorization, executing arbitrary code, and violating integrity and confidentiality.

Five key principles of exploit prevention and mitigation:

0-Day Vulnerabilities are a large concern, as they are hard to prevent and detect. These vulnerabilities are very valuable to attackers and state-level actors.

Exploit Kits contain many common attacks, bundled together. These are usable by unskilled hackers, and may be effective against old or unpatched systems.


Trojan Horses

Trojan Horses are software that appears to be useful and offer some helpful functionality. It is in reality a mask for a malicious program, running without the user knowing and harming the system or performing unwanted tasks.


Backdoors are malware that opens a secret entry point into the system, for a malicious actor. Combined, a Trojan Horse and a Backdoor are a RAT: Remote Access Trojan. For example, Cisco routers for a long time contained undocumented backdoors enabling an attacker to gain access to resources in networks using Cisco hardware.


Rootkits allow an attacker to maintain privilege once escalating privilege in a compromised system. For example, following a buffer overflow attack on the kernel, a rootkit may be installed at the operating system level to make this privilege escalation permanent for the attacker. In this case, the operating system can no longer be trusted. This makes rootkits very difficult to detect and remove.

User-level rootkits often replace system utilities such as ps, ls, ifconfig, etc. or key libraries with malicious programs. This is annoying but often detectable through simple utilities such as debsums.

Kernel-level rootkits modify or replace core operating system functionality, such as through overwriting a driver or kernel module. This can be mitigated by kernel-driver signing, a security feature that is required by some operating systems such as new versions of Windows.

Bootkits target the bootloader or Master Boot Record. By inserting themselves in those places, the malware is able to load before the operating system, and modify it as the system boots and the operating system boots.

Viruses and Worms

Viruses and worms are self-replicating code that infects other machines as it runs. These have somehow fallen out of favor in recent times.


The goal of spyware is to gather information about the user or the computer without the user knowing. This can be in the form of keyloggers that steal credentials, accounts, and other private information. The goal of collecting this information is often to sell it on a secondary market.


Botnets are the core of the underground internet. Botnets are networks of infected computers, often used to run attacks. Infected machines are a resource, much like cloud services are. Botnets enable attackers to have access to a lot of compute resources, while remaining anonymous. Botnets can be used for bitcoin mining, spam, DDOS attacks, and hosting for illicit websites. There are many ways to monetize botnets.

Computers can be infected and acquired for a botnet by infecting them through social engineering techniques, such as infected email attachments. An attachment may be malware in disguise, leveraging exploits in another piece of software such as a PDF viewer. PDFS, for example, can contain code that creates a buffer overflow attack on the PDF viewer, spawning processes that can take over the machine. An infected computer can be used to scan other computers within the network, potentially infecting them as well.

Command & Control Architecture (C&C)

Old botnet systems used a Command and Control architecture, where a botmaster had a few trusted control nodes, which would disseminate the malicious botmaster’s orders to the many infected devices. However, this creates a single point of failure, being the control nodes tasked with disseminating orders. It became easy for governments to take down such botnets.

Peer-to-peer, Distributed Hash Table Architecture (P2P, DHT)

Instead of all infected bots talking to control nodes, the distributed architecture for botnets has the bots linked to each other, and able to send and receive messages from other bots in the network. Instead of giving orders to all bots through control nodes, a botmaster only needs to disseminate orders to a few bots, who will relay the orders to the rest of the nodes. Control nodes can be usually offline, and only send messages when necessary. This makes these modern botnets much more difficult to take down, and ensures higher uptime.

Is My Machine Part of a Botnet?

NIDS, or network intrusion detection systems, can help detect if a machine is infected and engaged in botnet-like activity. NIDS use heuristics and rulesets to analyze traffic coming to and from a computer, and suspicious activities like connecting to unusual ports, bizarre DNS queries, and sending and receiving strange messages are often giveaway tells for computers engaged in a botnet. These rules can be defeated, however, by using normal ports such as 80 and 433.

Denial of Service

Attacks on availability, preventing users from accessing a service or resource, have been common since the first computers. The most common ways to deny service is to exploit bugs leading to crashes, or to exhaust the resources of the target. The attacker’s goal is to take a server offline, and the attacker can use an amplification attack.

Amplification attacks are used when the attacker only controls a small amount of bandwidth, but the internet services that the attacker has access to have a lot of bandwidth. This is the case with a botnet, for example. A common amplification attack is the Smurf attack, where the sender address of a ping is forged to be the IP address of the victim. By sending a ping to a broadcast address, the attacker can have the entire network send ping responses, overwhelming a victim’s machine, by only sending a single packet. Other amplification techniques use DNS lookups, memcached services, and CDNs, which offer much higher amplification ratios than just ping.

A computer can avoid being an amplifier by filtering incoming traffic to not allow pings from outside the network, disabling response to pings, and authenticating all requests.