CS134 Notes

Lec1 Class Info

Course Description

Terminology

Security Attack: an action (or event) that aims to compromise (undermine) security of information or resource.
- Interruption: attack on availability.
- Interception: attack on confidentiality.
- Modification: attack on integrity.
- Fabrication: attack on authenticity.
Security Mechanism: a measure (technique or method) designed to detect, prevent, or recover from, a security attack.
- Cryptography → confidentiality, authentication, identification, integrity, etc.
- Software Controls (e.g., in databases, operating systems) → protect system from users and users from each other
- Hardware Controls (e.g., smartcards, badges, biometrics) → authenticate holders (users)
- Policies (e.g., frequent password changes, separation of duty rules) → prevent insider attacks
- Physical Controls (doors, guards, moats, etc.) → physical access controls
Security Service: something that enhances security. A “Security Service” makes use of one or more “Security Mechanisms”.

The bold words are Main Security Goals.
- Confidentiality: to assure information privacy and secrecy.
- Authentication: who created or sent data.
- Integrity: data has not been altered.
- Access control: prevent misuse of resources.
- Availability: offer access to resources, permanence, non-erasure.

Examples of attacks on Availability:

Denial of Service (DoS) Attacks.
e.g. Against a DNS name server or Bank Web server.
Malware (ransomware) that deletes or encrypts files.

EXAMPLE:

Security Attack: Eavesdropping (aka Interception)
Security Mechanism: Encryption
Security Service: Confidentiality

Lec 2 Cryptography History & Methods

Crypto Applied in Several Levels

Algorithms: encryption, digital signatures, hashing, Random Number Generators (RNGs), secure erasure.
Protocols: key distribution, authentication, identification, log-in, e-payment, etc.
Systems: electronic cash, secure file-systems, smartcards, VPNs, e-voting, crypto-currencies, etc.
Attacks: on all the above.

Good security must be Effective yet Unobtrusive.

Security is not a service in and of itself, but a burden!

Historical (Primitive) Ciphers

Shift(e.g., Caesar): $Enc_k(x) = x + k \space mod \space 26$
Affine: $Enc_{k1,k2}(x) = k1 * x + k2 \space mod \space 26$
Substitution: $Enc_{perm}(x) = perm(x)$
Vigenere: $Enc_k(x) = (x[0] + k[0], x[1] + k[1], ..., x[n] + k[n])$
- This is simple version of vigenere cipher by just adding every key character; and it is better to mod 26 in order to have a valid character.
- Another method of vigenere cipher. Check the image right above.
Vernam: One-Time Pad (OTP)
- If the One-time pad stream is completely randomized, vernam cipher is the most safe cipher.
- $C = A \oplus B$ , $C \oplus B = A$
- Disadvantages:
  - It is impractical to have an one-time pad stream for a long text.
  - How to exchange the one-time pad stream with two sides?

Crypto Basics

Cryptosystem	Crypto Attacks
`P:` plaintext	Ciphertext Only
`C:` ciphertext	Knownplain Text
`K:` keyspace	Chosen Plaintext
`E:` encryption rules	Chosen Ciphertext
`D:` decryption rules	Brute Force

Lec 3 Encryption Types

Complexity

Cryptosystems

Classified along three dimensions:

Type of operations used for transforming plaintext into ciphertext
1. Binary arithmetic: shifts, XORs, ANDs, etc. Typical for conventional/symmetric encryption.
2. Integer arithmetic. Typical for public key/asymmetric encryption.
Number of keys used
1. Symmetric or conventional (single key used)
2. Asymmetric or public-key (2 keys: 1 to encrypt, 1 to decrypt)
How plaintext is processed
1. One bit at a time – “stream cipher”
2. A block of bits – “block cipher”

Symmetric Encryption

Examples

Substitution
Vernam OTP
DES
AES

Usage

Message transmission (confidentiality):
- Communication over insecure channels.
Secure storage:
- crypt on Unix.
Strong authentication: proving knowledge of a secret without revealing it:
- Eve can obtain <plaintext, ciphertext> pairs (known plaintext attack).
- Challenge should be chosen from a large pool.

Integrity checking: fixed-length checksum for message via symmetric key cryptography:
- Send MAC along with the message MAC=H(K, m)

Cons & Pros

Cons

High data throughput.
Relatively short key size.
Primitives to construct various cryptographic mechanisms.

Pros

Key must remain secret at both ends.
Key must be distributed securely and efficiently.
Relatively short key lifetime.

Asymmetric Encryption

Asymmetric cryptography
Invented in 1974-1978 (Diffie-Hellman, Rivest-Shamir-Adleman) Both win Turing awards (2002, 2015)!
Two keys: private (SK), public (PK)
- Encryption: with the other end’s public key;
- Decryption: with my own private key
- Digital Signatures: Signing by private key; Verification by public key. i.e., “encrypt” message digest/hash – h(m) – with private key
  - Authorship (authentication)
  - Integrity: Similar to MAC
  - Non-repudiation: can’t do with secret/symmetric key cryptography
Much slower (~1000x) than conventional cryptography
- Often used together with conventional cryptography, e.g., to encrypt session keys

Usage

Data transmission (confidentiality):
- Alice encrypts $m_a$ using $PK_B$ , Bob decrypts it to obtain ma using $SK_b$ .
Secure Storage: encrypt with own public key, later decrypt with own private key.
Authentication:
- No need to store secrets, only need public keys.
- Secret/symmetric key cryptography: need to share secret key for every person you want to communicates with
Digital Signatures (authentication, integrity, non-repudiation)

Cons & Pros

Cons

only the private key must be kept secret.
relatively long life time of the key.
more security services.
relatively efficient digital signature verifications.

Pros

low data throughput.
much larger key sizes.
distribution/revocation of public keys.
security based on conjectured hardness of certain computational problems.

Comparison Summary

Public/asymmetric key
- encryption, signatures (esp., non-repudiation), and key
  management
Conventional/symmetric
- encryption and some data integrity applications
Key sizes
- Keys in public key crypto must be larger ( e.g., 2048 bits for RSA) than those in conventional crypto ( e.g., 112 bits for 3-DES or 256 bits for AES )
  - most attacks on “good” conventional cryptosystems are exhaustive key search (brute force)
  - public key cryptosystems are subject to “short-cut” attacks (e.g., factoring large numbers in RSA)

Block Cipher

Feistel Cipher

Block Size: larger block sizes mean greater security
Key Size: larger key size means greater security
Number of Rounds: multiple rounds offer increasing security
Subkey Generation Algorithm: greater complexity leads to greater difficulty of cryptanalysis

DES

Resources

DES History

DES Tutorial

General

Most widely used encryption method in1970s/80s/90s, and AES took over in early 2000s.
Block cipher (in native ECB mode).
Plaintext processed in 64-bit blocks.
Key is 56 bits.

Basic Structure

Details

Key

Breaking DES

2DES

TOTAL COST: O( $2^{56}$ + $2^{56}$ ) operations + O( $2^{56}$ ) storage

DES Variants

Lec 4 AES & Modes of Operation

AES

Resources

AES Tutorial

Rijndael

Each round performs the following operations:

Non-linear Layer: No linear relationship between the input and output of a round.
Linear Mixing Layer: Guarantees high diffusion over multiple rounds.
- Very small correlation between bytes of the round input and the bytes of the output.
Key Addition Layer: Bytes of the input are simply XOR’ed with the expanded round key.