【13】CS161 Midterm 1 Cheatsheet

  1. Security principles:

    1. Security is economics.
    2. Least privilege.
    3. Use fail-safe defaults.
    4. Separation of responsibility.
    5. Defense in depth.
    6. Psychological acceptability.
    7. Human factors matter.
    8. Ensure complete mediation.
    9. Know your threat model.
    10. Detect if you can’t prevent.
    11. Don’t rely on security through obscurity.
    12. Design security in from the start.
    13. Conservative design.
    14. Kerckhoffs’ principle.
    15. Proactively study attacks.


    Standards often define security

    privilege separation

    Separation of responsibility

    Only as secure as the weakest link

    Trusted path

  2. Trusted Computing Base (TCB)

    TCB is the portion of the system that must operate correctly in order for the security goals of the system to be assured. Requires: • Is correct (Verifiable) • Is complete (Unbypassable) • Is itself secure (Tamper-resistant).

    Best way to assure correctness and security • KISS = Keep It Simple, Stupid! • Simple = Small

  3. Kerckhoff ’s Principle

    A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

  4. Shannon’s Maxim

    The enemy knows the system.

  5. vulnerabilities:

    1. Buffer overflow vulnerabilities (Stack smashing)
    2. Format string vulnerabilities
    3. Integer conversion vulnerabilities
  6. Defenses

    1. memory safe languages
    2. canaries
    3. Non-Executable Stack Space
    4. Data Execution Protection/ W^X (write or execute)
    5. ASLR
  7. Preconditions: what must hold for function to operate correctly

    Postconditions: what holds after function completes

    Invariants: conditions that always hold at a given point in a function

  8. General correctness proof strategy for memory safety: (1) Identify each point of memory access (2) Write down precondition it requires (3) Propagate requirement up to beginning of function

  9. attacker eavesdropper adversary

  10. main goals of Cryptography: Confidentiality, Integrity, Authenticity.


  12. Block Ciphers(AES)

    Three properties: 1. Correctness: EK(M) is a permutation (bijective 双射 / one-to-one function) 2. Efficiency 3. Security

  13. Symmetric Encryption Schemes

    1. ECB Mode (Electronic Code Book)


    2. CBC Mode (Cipher Block Chaining)

      C0 = IV, Ci = EK(Ci-1 xor Mi)

    3. OFB Mode (Output Feedback Mode)

      Z0 = IV, Zi = EK(Zi-1), Ci = Zi xor Mi

    4. Counter Mode (CTR)

      Zi = EK(IV + i), Ci = Zi xor Mi

    5. CFB Mode (Cipher feedback)

      C0=IV, Ci=Ek(Ci-1) Xor Mi

  14. Stream cipher Enc(K, M): C = PRG(K, IV) XOR M, Output (IV, C)

  15. Discrete log problem(DLP) -> One Way Function(OWF)

    f(x) = g^x mod p

    p is large prime (2048bits), random g (1 ~ p-1)

  16. Diffie-Hellman key exchange

    A = g^a mod p, B = g^b mod p.

    Session key: g^ab mod p

  17. Man-In-The-Middle (MITM) Attack

    solutions: certificates, publish pk on a trusted service, display and check if agreed on same key.

  18. El Gamal encryption

    Public key is (pk = g^k mod p ; g ; p). Private key is k. (1 < g < p-1, 0 <= k <= p-2)

    Ciphertext: (R ; S) -> (g^r mod p ; m * pk^r mod p). (random r, 0 <= r <= p-2, 1 <= m <= p-1)

    Decrypt: R^-k * S mod p;

  19. Hybrid encryption:


    C = (Ckey = Enc(pk, k), Cmsg = Enc(k, m))

  20. Hash

    Correctness: deterministic

    Efficiency: fast to compute

    Security: one-way function (preimage resistant); collision resistance(CR)

  21. four particularly significant types of cryptographic primitives:

    Symmetric-key Asymmetric-key
    Con fidentiality Symmetric-key encryption (e.g., AES-CBC) Public-key encryption (e.g., El Gamal, RSA encryption)
    Integrity and authentication MACs (e.g., AES-CBC-MAC) Digital signatures (e.g., RSA signatures)
  22. Message Authentication Codes (MACs):

    T = MAC(K, M)


    Si = AESk1(Si-1 Xor Mi), T = AESK2(Sn)


    key长度不够补0,太长hash一下 o_key_pad = 0x5c5c… ⊕ key i_key_pad = 0x3636… ⊕ key return hash(o_key_pad || hash(i_key_pad || message))

  23. RSA (hard to find prime factors of large integers.)

    n = p*q, φ(n) = (p-1)(q-1)

    random 2 < e < φ(n), d = e^-1 mod φ(n)

    n, e are public, d, p, q, and φ(n) are secret

    c = m^e mod n

    m = c^d mod n

    RSA-OAEP: X = [m,0…] ⨁ G®, Y = H(X) ⨁ r (G and H are hash functions)

  24. RSA Signatures

    s = (H(m))^d mod n

    v = s^e mod n

  25. Prevent MITM:

    Send: E(M,Ksess), E(Ksess,Bpub), S(H(M),Apriv)


720 Words

2019-02-22 09:00 +0800