Security & Cryptography
Computer Science and Engineering College of Engineering The Ohio State University
Some High-Level Goals
Copyright By PowCoder代写 加微信 powcoder
Computer Science and Engineering The Ohio State University
Confidentiality
Non-authorized users have limited access
Integrity Accuracy/correctness/validity of data
Availability
No down-time or disruptions
Authenticity
Agents are who they claim to be
Non-repudiation
A party to a transaction can not later deny their participation
Methods of Attack
Target people (“social engineering”)
Target software (“exploits”)
Target channel (“man-in-the-middle”)
Phishing: email, phone, surveys, …
Baiting: click & install, physical media, …
Unpatched OS, browser, programs
Buffer overflow
Code injection and cross-site scripting
Eavesdropping
Masquerading, tampering, replay
Computer Science and Engineering The Ohio State University
Cryptography
Etymology (Greek)
Basic problem:
2 agents (traditionally “Alice” and “Bob”)
Solution has other applications too Protect stored data (e.g. on disk, or in cloud)
Digital signatures for non-repudiation Secure passwords for authentication
Computer Science and Engineering The Ohio State University
kryptos: hidden or secret
grapho: write
A & B want to exchange private messages Channel between A & B is not secure (“Eve” is eavesdropping)
Core Idea: The Secret
Computer Science and Engineering The Ohio State University
Alice & Bob share some secret
Crude analogy: a padlock
But real channels are bit streams
Secret can not be the message itself Secret used to protect arbitrary messages
Copies of the physical key are the secret Alice puts message in box and locks it Bob unlocks box and reads message
Eve can see the bits!
Message must be garbled in some way
Secret is strategy for garbling/degarbling
Protecting Messages
Alice garbles (encrypts) the message
Sends the encrypted cipher-text
Bob knows how to degarble (decrypt)
cipher-text back into plain-text
Computer Science and Engineering The Ohio State University
Image: www.devx.com
Encryption/Decryption Function
Computer Science and Engineering The Ohio State University
“fwspdaad”
Plaintext messages (P)
Ciphertext Messages (Q)
E: P -> Q D: Q -> P
E(m) = c D(c) = m i.e. D = E-1
Note: often P = Q
So E is a permutation
Families of Encryption Functions
Computer Science and Engineering The Ohio State University
Each pair of agents needs their own E Many E’s (& corresponding D’s) needed
But good E’s are hard to invent
Solution: design one (good) E, which is
parameterized by a number
Secret: which Ei is used (i is the key)
That is, have a huge family of E’s: E0, E1, E2, … EK
Classic Example:
Computer Science and Engineering The Ohio State University
Shift each letter by x positions in alphabet
E.g. x = 3 a->d,b->e,c->f,d->g,e->h, …
Encode a string character-by-character
The key is x
For m = “hello world”, E3(m) = “khoor zruog”
Questions:
What is P (set of plaintext messages)? What is Q (set of ciphertext messages)? How many different ciphers?
Is this a strong or weak cipher?
Generalized
Computer Science and Engineering The Ohio State University
Generalization: arbitrary mapping E.g. The qwerty shift
a->s,b->n,c->v,d->f,e->r, … For m = “hello world”,
E(m) = “jraap eptaf”
There are ~1018 nanoseconds/century Weakness?
Approximately 4 x 1026
26! possible ciphers… that’s a lot!
Generalized
Computer Science and Engineering The Ohio State University
Generalization: arbitrary mapping E.g. The qwerty shift
a->s,b->n,c->v,d->f,e->r, … For m = “hello world”,
E(m) = “jraap eptaf”
Approximately 4 x 1026
26! possible ciphers… that’s a lot!
There are ~1018 nanoseconds/century Weakness?
In English text, letters appear in predictable ratios
From enough ciphertext, can infer E
Frequency Analysis
Computer Science and Engineering The Ohio State University
Computer Science and Engineering The Ohio State University
WW II: Enigma Machine
Computer Science and Engineering The Ohio State University
Polyalphabetic Cipher
Computer Science and Engineering The Ohio State University
Alberti’s idea: Use different Ei’s
within the same message
Alice & Bob need to agree on the sequence of E’s to use
proved that this method
is perfectly secure (1949)
E(“hello world”) = Ea(“h”)Eb(“e”)Ec(“l”)Ed(“l”)Ee
Precise information-theoretic meaning Known as a one-time pad
One-Time Pad
Computer Science and Engineering The Ohio State University
Message is a sequence of bits
m0 m1 m2 m3 m4 m5 m6…
One-time pad is random bit sequence
x0 x1 x2 x3 x4 x5 x6…
E is bit-wise XOR operation, ⊕ Cipher text is
m0⊕x0 m1⊕x1 m2⊕x2 m3⊕x3 m4⊕x4 m5⊕x5 m6⊕x6… Problem: Pad is long and cannot be re-used (hence
cumbersome to share)
“Solution”: pseudo-random sequence, generated from a seed (the key)
Comparison: Stream vs Block
Stream Cipher
Encrypts bit-by-bit
Computer Science and Engineering The Ohio State University
Block Cipher
|P| = |Q| = 2
Few choices for E
(roughly 2)
Message can have any
Encrypts a fixed-length (k-bit) sequence
|P| = |Q| = 2k
Many choices for E (roughly 2k!)
Padding added s.t.
|m| mod k = 0
Limitation of Fixed Block Size
Computer Science and Engineering The Ohio State University
Message can be longer than block size
Reuse same E for each block?
Danger: Frequency analysis vulnerability Don’t do this (for multiblock messages)!
https://en.wikipedia.org/wiki/Image:Tux_ecb.jpg
Solution: Initialization Vector
Computer Science and Engineering The Ohio State University
Add a random block to start
Combine adjacent blocks to make
ciphertext block
Many combination strategies
Advanced Encryption Standard (2001) Replaced DES (1977)
Block size always 128 bits (4×4 bytes)
Key size is 128, 192, or 256 bits
Multi-step algorithm, many rounds
Computer Science and Engineering The Ohio State University
Security: Cryptography
Computer Science and Engineering College of Engineering The Ohio State University
Symmetric Key
If you know how to encrypt, you can decrypt too
Known as a symmetric key cipher
Example: Caesar cipher
If E(m) = m + 3, D(m) = m – 3
Example: One-time pad
Use same pad and same operation (xor)
Example: AES
Use same key, reverse rounds and steps
Computer Science and Engineering The Ohio State University
For ciphers (so far): Knowing E is
enough to figure out D (its inverse)
One-Way Functions
Computer Science and Engineering The Ohio State University
For some functions, the inverse is hard
to calculate
Given a puzzle solution, easy to design a puzzle with that solution (the “forward” direction)
One direction (P->Q) is easy, but opposite direction (Q->P) is hard/expensive/slow
Intuition:
Given the puzzle, hard to come up with the solution (the “inverse” direction)
Example: Dominating Set
Computer Science and Engineering The Ohio State University
Hard direction: Find a dominating set of size at most 6 in the following graph…
Example: Dominating Set
Computer Science and Engineering The Ohio State University
Easy direction: Create a graph with a dominating set of size 6 from this forest…
Example: Factoring
Multiplying numbers is easy (i.e. fast) Can multiply 2 n-bit numbers in n2 steps
Computer Science and Engineering The Ohio State University
Factoring a number is hard (i.e. slow) To factor an n-bit number, need 2n steps (approximately the number’s value)
Primality testing is fast (recall lab activity in Software I and Fermat’s Little Theorem)
But this fast test doesn’t reveal the factors of a composite number
Cryptographic Hash Functions
Computer Science and Engineering The Ohio State University
Fixed-Length Digests
Computer Science and Engineering The Ohio State University
Crypto. Hash as Fingerprint
Computer Science and Engineering The Ohio State University
Common Cryptographic Hashes
Computer Science and Engineering The Ohio State University
Flaws discovered: “cryptographically broken”
Do not use!
SHA-1: deprecated
Windows, Chrome, Firefox reject (2017)
160-bit digests (i.e. 40 hex digits)
Replaced by SHA-2 (still common)
A family of 6 different hash functions
Digest sizes: 224, 256, 384, or 512 bits Names: SHA-224, SHA-256, SHA-512, etc
Currently SHA-3
Entirely different algorithm
Names: SHA3-224, SHA3-256, SHA3-512, etc
Utility of Crypto. Hashes
Computer Science and Engineering The Ohio State University
Integrity verification (super-checksum) File download, check digest matches
Password protection
Server stores the hash of user’s password Check entered password by computing its hash and comparing hash to the stored value Benefit: Passwords are not stored (directly) in the database! If server is compromised, intruder finds hashes but not passwords
See md5decrypt.net/en/Sha256/ c023d5796452ad1d80263a05d11dc2a42b8c19c5d7c88c0e84ae3731b73a3d34
Role of Salt
Intruder pre-computes hashes for many (common)
passwords: aka a rainbow table
Protects the fingerprint, by making it not
mass pre-computable
Scan stolen hashes for matches Solution: salt
Server prepends text to password before
Text must be unique to user
Text does not need to be secret
Ok: Deterministic value based on user name Better: Random value, stored in the table
Computer Science and Engineering The Ohio State University
One-Way Function with Trapdoor
Computer Science and Engineering The Ohio State University
Function appears to be one-way
But, in reality, the inverse is easy if one knows a secret (the “trapdoor”)
There are two very different functions:
Knowing E is not enough to infer D
Creates an asymmetry:
The one-way-seeming function, E
The trapdoor for its inverse, D
Alice knows E
Bob (and only Bob) knows D
Asymmetry: Alice vs Science and Engineering The Ohio State University
Public-Key Encryption
Computer Science and Engineering The Ohio State University
Algorithms for E and D known by all But parameterized by matched keys
Anyone can encrypt messages for Bob can decrypt these messages
Important consequences
Key for Bob’s E is public Key for Bob’s D is private
Each agent needs only 1 public key No pre-existing shared secret needed
Public and Private Keys
Computer Science and Engineering The Ohio State University
Computer Science and Engineering The Ohio State University
E and D are actually the same function
Parameterized by pair , i.e. the key Private key:
Public key:
Choice of e & d is based on factoring
Choose 2 large prime numbers, p and q Calculate their product, n = pq
Pick any d relatively prime with (p-1)(q-1) Find an e s.t. ed = 1 mod (p-1)(q-1)
Digital Signature
Usual direction for encryption: D(E(m)) = (me)d = med = m, mod n
One-to-one, so backwards works too! E(D(m)) = (md)e = mde = m, mod n
Bob “encrypts” m using his private key, d
Bob sends both m and D(m)
Anyone can undo the “encrypted” part using Bob’s
public key, e Result will be m
D(m) serves as a digital signature of m Only Bob could have created this signature
Use: non-repudiation
Computer Science and Engineering The Ohio State University
Performance Considerations
Computer Science and Engineering The Ohio State University
Symmetric key algorithms are faster
than public key algorithms
Optimization for encryption (RSA)
Optimization for digital signatures
Create a fresh symmetric key, k
Use symmetric algorithm to encrypt m
Use recipient’s public key to encrypt k
Calculate the digest for m (always short) Use sender’s private key to encrypt digest
TLS 1.3: Handshake
Certificate
Get server’s public key
Make new (symmetric) session key
Sends this key to server (encrypted with public key)
Computer Science and Engineering The Ohio State University
Connects public key to identity
Take Home Message
Don’t try to roll your own crypto/security implementation Use (trusted) libraries
Recognize role and importance of (eg):
Initialization vector
Cryptographic hash/digest
Private key vs public key
Computer Science and Engineering The Ohio State University
Symmetric-key encryption
Sender and receiver share (same) secret key
Stream ciphers work one bit at a time (e.g., one-time pad)
Block ciphers work on larger blocks of bits (e.g., SHA-2)
One-way functions: Hard to invert Cryptographic hash produces fixed-size digest
Digest serves as a fingerprint
Public key encryption Matching keys: kprivate, kpublic
Anyone can use public key to encrypt
Only holder of private key can decrypt
Use private key to create a digital signature
Computer Science and Engineering The Ohio State University
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com