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 otherHardware Controls
(e.g., smartcards, badges, biometrics) → authenticate holders (users)Policies
(e.g., frequent password changes, separation of duty rules) → prevent insider attacksPhysical 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”.
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, nonerasure.
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, login, epayment, etc.Systems:
electronic cash, secure filesystems, smartcards, VPNs, evoting, cryptocurrencies, etc.Attacks:
on all the above.
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.
 This is simple version of

Vernam:
OneTime Pad (OTP
)
If the Onetime 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
onetime pad stream
for a long text.  How to exchange the
onetime pad stream
with two sides?
 It is impractical to have an

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
 Binary arithmetic: shifts, XORs, ANDs, etc. Typical for conventional/symmetric encryption.
 Integer arithmetic. Typical for public key/asymmetric encryption.
 Number of keys used
 Symmetric or conventional (single key used)
 Asymmetric or publickey (2 keys: 1 to encrypt, 1 to decrypt)
 How plaintext is processed
 One bit at a time – “stream cipher”
 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.
 Eve can obtain
 Integrity checking: fixedlength 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 19741978 (DiffieHellman, RivestShamirAdleman) 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
 Nonrepudiation: 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, nonrepudiation)
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., nonrepudiation), and key
management
 encryption, signatures (esp., nonrepudiation), and key

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 3DES or 256 bits for AES )
 most attacks on “good” conventional cryptosystems are exhaustive key search (brute force)
 public key cryptosystems are subject to “shortcut” attacks (e.g., factoring large numbers in RSA)
 Keys in public key crypto must be larger ( e.g., 2048 bits for RSA) than those in conventional crypto ( e.g., 112 bits for 3DES or 256 bits for AES )
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
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 64bit 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
Rijndael
Each round performs the following operations:

Nonlinear 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.