Introduction to
Cryptography
Joe McCarthy
Outline
2. Introduction to
Cryptography.
What Is Cryptography?
Breaking an Encryption
Scheme.
Types of Cryptographic
Functions.
Secret Key Cryptography.
Public Key Cryptography.
Hash Algorithms.
Network Security: Private
Communication
in a Public World, 2/E
Charlie Kaufman
Radia Perlman
Mike Speciner
CSS 432: Introduction to
Cryptography
Cryptography
The art of secret writing.
The art of mangling information into apparent unintelligibility
in a manner allowing a secret method of unmangling.
CSS 432: Introduction to
Cryptography
Cryptography Definitions
Messages:
Plaintext
Ciphertext
Ingredients:
Algorithm(s)
Key(s)
Players:
Cryptographer: invents clever algorithms
Cryptanalyst: breaks clever algorithms
CSS 432: Introduction to
Cryptography
Cryptography
Algorithm
Key(s) = secret value(s)
OK for good algorithm to be public
Not OK to use bad algorithm
Sunlight is the best disinfectant
Algorithm without key does not help
unmangle the information
CSS 432: Introduction to
Cryptography
Computational Issues
Algorithm should be reasonably
efficient
Security depends on how hard it is to
break
Combination lock
3 number sequence (2R, 1L, 0R), #s
between 1-40
Possible combinations:
CSS 432: Introduction to
Cryptography
Computational Issues
Algorithm should be reasonably
efficient
Security depends on how hard it is to
break
Combination lock
3 number sequence (2R, 1L, 0R), #s
between 1-40
Possible combinations: 403 = 64,000
10 seconds per sequence: 178 hours (/ 2 = 89)
CSS 432: Introduction to
Cryptography
Computational Issues
Algorithm should be reasonably
efficient
Security depends on how hard it is to
break
Combination lock
3 number sequence (2R, 1L, 0R), #s
between 1-40
Possible combinations: 403 = 64,000
10 seconds per sequence: 178 hours (/ 2 = 89)
CSS 432: Introduction to
Cryptography
Computational Issues
Algorithm should be reasonably efficient
Security depends on how hard it is to
break
Combination lock
3 number sequence (2R, 1L, 0R), #s between
1-40
Possible combinations: 403 = 64,000
10 seconds per sequence: 178 hours (/ 2 = 89)
4 number sequence, 13 seconds per
sequence
CSS 432: Introduction to
Cryptography
Computational Issues
Algorithm should be reasonably efficient
Security depends on how hard it is to break
Combination lock
3 number sequence (2R, 1L, 0R), #s between
1-40
Possible combinations: 403 = 64,000
10 seconds per sequence: 178 hours (/ 2 = 89)
4 number sequence, 13 seconds per sequence
404 = 2,560,000
9,244 hours
CSS 432: Introduction to
Cryptography
Computational Issues
Algorithm should be reasonably efficient
Security depends on how hard it is to break
Combination lock
3 number sequence (2R, 1L, 0R), #s between
1-40
Possible combinations: 403 = 64,000
10 seconds per sequence: 178 hours (/ 2 = 89)
4 number sequence, 13 seconds per sequence
404 = 2,560,000
9,244 hours
CSS 432: Introduction to
Cryptography
Publication Issues
Public or secret algorithms?
CSS 432: Introduction to
Cryptography
Publication Issues
Public or secret algorithms:
OK for good algorithm to be public
Sunlight is the best disinfectant
Reverse engineering, leaks
Free consulting by cryptanalysts
Generally:
Commercial: public
Military: secret
CSS 432: Introduction to
Cryptography
Secret Codes
Caesar cipher
Substitute letter 3 letters further on
DOZEN GRCHQ
CSS 432: Introduction to
Cryptography
Secret Codes
Caesar cipher
Substitute letter 3 letters further on
DOZEN GRCHQ
Captain Midnight Secret Decoder
Rings
Substitute letter n letters further on (n =
1..25)
HAL IBM (n = 1)
CSS 432: Introduction to
Cryptography
Secret Codes
Caesar cipher
Substitute letter 3 letters further on
DOZEN GRCHQ
Captain Midnight Secret Decoder Rings
Substitute letter n letters further on (n = 1..25)
HAL IBM (n = 1)
Monoalphabetic cipher
Arbitrary mappings (26! = 4.03291461 10 26)
1 ms / try 10M years but: letter frequencies
CSS 432: Introduction to
Cryptography
[from Stallings, Cryptography & Network Security]
CSS 432: Introduction to
Cryptography
Breaking an Encryption
Scheme
Ciphertext only
Try all possible keys, look for intelligibility
Need sufficiently long ciphertext
XYZ = ?
Known plaintext
(plaintext, ciphertext) pair(s)
Chosen plaintext
Have plaintext encrypted, compare expected
values
CSS 432: Introduction to
Cryptography
Types of Cryptography
Public Key
Two keys: public & private
Symmetric Key (aka Secret Key)
One key: secret (but possibly shared)
Hash Functions
No keys
CSS 432: Introduction to
Cryptography
Symmetric Key
Cryptography
AKA secret key cryptography
AKA conventional cryptography
CSS 432: Introduction to
Cryptography
Symmetric Key Applications
Transmission over insecure channel
Shared secret (transmitter, receiver)
Secure storage on insecure media
Authentication
Strong authentication: prove knowledge
without revealing key
CSS 432: Introduction to
Cryptography
A simple example
KAB = +3 (Caesar cipher), known by
Alice & Bob
rA = marco
rA encrypted with KAB:
rB = polo
rA encrypted with KAB:
CSS 432: Introduction to
Cryptography
A simple example
KAB = +3 (Caesar cipher), known by
Alice & Bob
rA = marco
rA encrypted with KAB: pdufr
rB = polo
rA encrypted with KAB: sror
CSS 432: Introduction to
Cryptography
A simple example
KAB = +3 (Caesar cipher), known by
Alice & Bob
rA = marco
rA encrypted with KAB: pdufr
rB = polo
rA encrypted with KAB: sror
(marco, pdufr), (polo, sror)
CSS 432: Introduction to
Cryptography
Public Key Cryptography
AKA asymmetric cryptography
AKA unconventional cryptography (?)
Public key: published, ideally known widely
Private key (NOT secret key): not published
CSS 432: Introduction to
Cryptography
Public Key Cryptography
[Link]
ography
CSS 432: Introduction to
Cryptography
Public Key Cryptography
Issues
Efficiency
Public key cryptographic algorithms are
orders of magnitude slower than
symmetric key algorithms
Hybrid model
Public key used to establish temporary
shared key
Symmetric key used for remainder of
communication
CSS 432: Introduction to
Cryptography
SSL / TLS
CLIENT_HELLO:
Available crypto &
compression algorithms
Highest SSL/TLS protocol
version
SSL Session ID
Random data
SERVER_HELLO
Specific crypto &
compression
Specific SSL version
SSL Session ID
Random data
CERTIFICATE
Servers public encryption
key
Session Key
Servers public encryption
CSS 432: Introduction to key + random data
Cryptography
Secure Storage on Insecure
Media
Option 1:
Encrypt with public key
Decrypt with private key
CSS 432: Introduction to
Cryptography
Secure Storage on Insecure
Media
Option 1:
Encrypt with public key
Decrypt with private key
Option 2:
Generate random secret key
Encrypt with that secret key
Encrypt secret key with public key
CSS 432: Introduction to
Cryptography
Digital Signatures
Asymmetry:
Signature can only be generated by owner/knower of private key
Signature can be verified by anyone via public key
Non-repudiation:
Sender cannot prove message (signature) was not sent
Key may have been stolen
CSS 432: Introduction to
Cryptography
Message Integrity
Keyed hash, shared secret
CSS 432: Introduction to
Cryptography
Hash Algorithms
Message digests / one-way
transformations
easy to compute a hash value for any given
message
infeasible to find a message that has a
given hash
infeasible to modify a message without
hash being changed
infeasible to find two different messages
with [Link]
the same hash
unction
CSS 432: Introduction to
Cryptography
Hash Algorithms
[Link]
unction
CSS 432: Introduction to
Cryptography
An example
This example uses the common unix utility "md5sum", which hashes the data on stdin
to a 128 bit hash, displayed as 32 hex digits.
Assume the password is "mysecretpass" and both the client and the server know this.
The client connects to the server.
The server makes up some random data, say "sldkfjdslfkjweifj.
The server sends this data to client.
The client concatenates the random data with the password, resulting in
"sldkfjdslfkjweifjmysecretpass"
The client computes the MD5 hash of this value:
$ echo sldkfjdslfkjweifjmysecretpass | md5sum
4fab7ebffd7ef35d88494edb647bac37
The client sends "4fab7ebffd7ef35d88494edb647bac37" to the server.
[The server confirms that it gets the same value when it runs echo
"sldkfjdslfkjweifjmysecretpass | md5sum]
[Link]
CSS 432: Introduction to
Cryptography
md5sum on Linux
[joemcc@uw1-320-17 ~]$ cat > [Link]
Testing 1, 2, 3
[joemcc@uw1-320-17 ~]$ md5sum [Link]
6a8c5c1973dd8ed2df1260297964cd64 [Link]
[joemcc@uw1-320-17 ~]$ cp [Link] [Link]
[joemcc@uw1-320-17 ~]$ md5sum [Link]
6a8c5c1973dd8ed2df1260297964cd64 [Link]
[joemcc@uw1-320-17 ~]$ cat > [Link]
Testing 1, 2, 4
[joemcc@uw1-320-17 ~]$ md5sum [Link]
5e361a608a1f63b154f259dba0f452dc [Link]
[joemcc@uw1-320-17 ~]$ echo "Testing 1, 2, 3" | md5sum
6a8c5c1973dd8ed2df1260297964cd64 [joemcc@uw1-320-17 ~]$
CSS 432: Introduction to
Cryptography
Cryptographic Hash
Lifecycle
[Link]
[via [Link]
CSS 432: Introduction to
Cryptography
Password Hashing
Only hashes (not passwords) are
stored
Passwords can still be guessed
(dictionary)
[Link]
edin-confirms-hack-over-60-of-stolen-passwordsalready-cracked/
CSS 432: Introduction to
Cryptography
Message Fingerprint
Compute h(message)t1
Compare to h(message)t2
Message can be a program (e.g., ssh)
shv4
CSS 432: Introduction to
Cryptography
