cs161 su23 mid-term cheat sheet

期中考试可以自带的合法小抄，亦可作为供索引的笔记

stack layout and vulnerabilities

内存和寄存器

C memory layout

• Code section: Machine code (raw bits) to be executed

• Static section: Static variables

• Heap section: Dynamically allocated memory (e.g. from malloc)

• Stack section: Local variables and stack frames

x86 registers

• EBP register points to the top of the current stack frame

• ESP register points to the bottom of the stack

• EIP register points to the next instruction to be executed

x86 calling convention

• When calling a function, the old EIP (RIP) is saved on the stack

• When calling a function, the old EBP (SFP) is saved on the stack

• When the function returns, the old EBP and EIP are restored from the stack

calling convention

1. Push arguments on the stack

2. Push old eip (rip) on the stack

3. Move eip

4. Push old ebp (sfp) on the stack

5. Move ebp

6. Move esp

7. Execute the function

8. Move esp

9. Restore old ebp (sfp)

10. Restore old eip (rip)

11. Remove arguments from stack

TIPS

struct/function arguement are in reversed order

exploit memory

• stack smashing

• format string

  • leak the value

  • write:

  • useful tips:

    • %s → Treat the argument as an address and print the string at that address up until the first null byte

    • %n → Treat the argument as an address and write the number of characters that have been printed so far to that address

    • %c → Treat the argument as a value and print it out as a character

    • %x → Look at the stack and read the first variable after the format string

    • %[b]u → Print out [b] bytes starting from the argument

• interger conversion:signed to unsigned

• off-by-one/faked frame

• other:vtable in C++

defense

• Memory-safe languages

  • Using a memory-safe language (e.g. Python, Java) stops all memory safety vulnerabilities.

  • Why use a non-memory-safe language?

    • Commonly-cited reason, but mostly a myth: Performance

    • Real reason: Legacy, existing code

• Writing memory-safe code

  • Carefully write and reason about your code to ensure memory safety in a non-memory-safe language

  • Requires programmer discipline, and can be tedious sometimes

• Building secure software

  • Use tools for analyzing and patching insecure code

  • Test your code for memory safety vulnerabilities

  • Keep any external libraries updated for security patches

• Mitigation: Non-executable pages

  • Make portions of memory either executable or writable, but not both

  • Defeats attacker writing shellcode to memory and executing it

  • Subversions

    • Return-to-libc: Execute an existing function in the C library

    • Return-oriented programming (ROP): Create your own code by chaining together small gadgets in existing library code

• Mitigation: Stack canaries

  • Add a sacrificial value on the stack. If the canary has been changed, someone’s probably attacking our system

  • Defeats attacker overwriting the RIP with address of shellcode

  • Subversions

    • An attacker can write around the canary

    • The canary can be leaked by another vulnerability (e.g. format string vulnerability)

    • The canary can be brute-forced by the attacker

• Mitigation: Pointer authentication

  • When storing a pointer in memory, replace the unused bits with a pointer authentication code (PAC). Before using the pointer in memory, check if the PAC is still valid

  • Defeats attacker overwriting the RIP (or any pointer) with address of shellcode

• Mitigation: Address space layout randomization (ASLR)

  • Put each segment of memory in a different location each time the program is run

  • Defeats attacker knowing the address of shellcode

  • Subversions

    • Leak addresses with another vulnerability

    • Brute-force attack to guess the addresses

• Combining mitigations

  • Using multiple mitigations usually forces the attacker to find multiple vulnerabilities to exploit the program (defense-in-depth)

Heap vulnerabilities

• Heap overflow

  • Objects are allocated in the heap (using malloc in C or new in C++)

  • A write to a buffer in the heap is not checked

  • The attacker overflows the buffer and overwrites the vtable pointer of the next object to point to a malicious vtable, with pointers to malicious code

  • The next object’s function is called, accessing the vtable pointer

• Use-after-free

  • An object is deallocated too early (using free in C or delete in C++)

  • The attacker allocates memory, which returns the memory freed by the object

  • The attacker overwrites a vtable pointer under the attacker’s control to point to a malicious vtable, with pointers to malicious code

  • The deallocated object’s function is called, accessing the vtable pointer

Cryptograph

三大性质

• confidentiality

• intergrity

• authenticity

Roadmap

​​

IND-CPA

1. Eve may choose plaintexts to send to Alice and receives their ciphertexts

2. Eve issues a pair of plaintexts M0 and M1 to Alice

3. Alice randomly chooses either M0 or M1 to encrypt and sends the encryption back

   • Alice does not tell Eve which one was encrypted!

4. Eve may again choose plaintexts to send to Alice and receives their ciphertexts

5. Eventually, Eve outputs a guess as to whether Alice encrypted M0 or M1

An encryption scheme is IND-CPA secure if for all polynomial time attackers Eve:

• Eve can win with probability ≤ 1/2 + Ɛ, where Ɛ is negligible.

1-1

One-time pad + block cipher

ECB

​​

CBC (IV, C1, …, Cm)

​

padding-PKCS #7 : Pad with the number of padding bytes

CTR (Nonce, C1, …, Cm) no padding

​​

2-1

hash:

• Map arbitrary-length input to fixed-length output

• Output is deterministic and unpredictable

• Security properties

  • One way: Given an output y, it is infeasible to find any input x such that H(x) = y.

  • Second preimage resistant: Given an input x, it is infeasible to find another input x' ≠ x such that H(x) = H(x').

  • Collision resistant: It is infeasible to find another any pair of inputs x' ≠ x such that H(x) = H(x').

• Some hashes are vulnerable to length extension attacks

• Application: Lowest hash scheme

• Hashes don’t provide integrity (unless you can publish the hash securely)

Length extension attack: Given H(x) and the length of x, but not x, an attacker can create H(x || m) for any m of the attacker’s choosing

MAC;EU-CPA:existentially unforgeable: without the key, an attacker cannot create a valid tag on a message NMAC:NMAC(K1, K2, M)=H(K1 || H(K2 || M)) HMAC:H((K' ⊕ opad) || H((K' ⊕ ipad) || M))

Authenticated encryption (AE): A scheme that simultaneously guarantees confidentiality and integrity (and authenticity, depending on your threat model) on a message Encrypt-then-MAC:Enc(K1, M)+MAC(K2, Enc(K1, M)) or AEAD encryption modes designed to provide confidentiality, integrity, and authenticity

PRNG

Randomness is essential for symmetric-key encryption,for eg random key or random IV

• rue randomness requires sampling a physical process

  • Slow, expensive, and biased (low entropy)

• PRNG: An algorithm that uses a little bit of true randomness to generate a lot of random-looking output

  • Seed(entropy): Initialize internal state

  • Generate(n): Generate n bits of pseudorandom output

• Security: computationally indistinguishable from truly random bits

  • NOTE:if attacker know it's initial state so he can predict it

• Example using AES in CTR mode

• Application: UUIDs

1-2

• Public key: Known to everybody

• Private key: Only known by that person

• Keys come in pairs: every public key corresponds to one private key

D-F key exchange

D-F problem:give g, p, g^a^ mod p, g^b^ mod p ; R and g^ab^ mod p Indistinguishable from the perspective of a polynomial time attacker

• Algorithm:

  • Alice chooses a and sends ga mod p to Bob

  • Bob chooses b and sends gb mod p to Alice

  • Their shared secret is (ga)b = (gb)a = gab mod p

• Diffie-Hellman provides forwards secrecy: Nothing is saved or can be recorded that can ever recover the key

• Diffie-Hellman can be performed over other mathematical groups, such as elliptic-curve Diffie-Hellman (ECDH)

• Issues

  • Not secure against MITM

  • Both parties must be online

  • Does not provide authenticity

Semantic security (IND-CPA for public-key encryption)

El Gamal​​

RSA​​

Hybrid encryption: Encrypt data under a randomly generated key K using symmetric encryption, and encrypt K using asymmetric encryption

2-2

digital signatures

• KeyGen() → PK, SK: Generate a public/private keypair, where PK is the verify (public) key, and SK is the signing (secret) key

• Sign(SK, M) → sig: Sign the message M using the signing key SK to produce the signature sig

• Verify(PK, M, sig) → {0, 1}: Verify the signature sig on message M using the verify key PK and output 1 if valid and 0 if invalid

RSA sig​

​​​

certificates

• Certificates: A signed attestation of identity

• Trusted directory: One server holds all the keys, and everyone has the TD’s public key

  • Not scalable: Doesn’t work for billions of keys

  • Single point of failure: If the TD is hacked or is down, cryptography is broken

• Certificate authorities: Delegated trust from a pool of multiple root CAs

  • Root CAs can sign certificates for intermediate CAs

  • Revocation: Certificates contain an expiration date

  • Revocation: CAs sign a list of revoked certificates

password hashing

• Store hashes of passwords so that you can verify a user’s identity without storing their password

• Attackers can use brute-force attacks to learn passwords (especially when users use weak passwords)

  • Defense: Add a different salt for each user: A random, public value designed to make brute-force attacks harder

• Offline attack: The attacker performs all the computation themselves

  • Defense: Use salted, slow hashes instead of unsalted, fast hashes

• Online attack: The attacker interacts with the service

  • Defense: Use timeouts

other hashing applications

​​