1
Q
cryptography and cryptanalysis
A
- Cryptography is the science and study of secret writing
- Cryptoanalysis is the science and study of methods of breaking ciphers
Today:
- cryptography is the study of mathematical techniques related to aspects of information security, such as confidentiality, data integrity, entity authentication, and data origin authentication
Cryptography does not solve security problems; it just transforms them into other problems, which are hopefully easier to handle.
2
Q
Law enforcement Key recovery Key escrow
A
- In many countries laws regulate how a law enforcement agency (LEA) can intercept traffic.
- Key recovery makes cryptographic keys available to their owner.
- Key escrow makes keys available to a LEA
3
Q
cryptographic security
A
Cryptographic Security
- Unconditional Security
- Conditional Security
4
Q
Unconditional Security
A
- Unconditional Security: System is secure even if adversary has unbounded computing power.
→ Security can be measured using information theory
5
Q
Conditional Security
A
- Conditional Security: System can be broken in principle, but this requires more computing power than a realistic adversary would have.
→ Security can be measured using complexity theory
6
Q
Cryptographic security services
A
- Data confidentiality: encryption hides the content of messages → only authorized users get the content
- Data integrity: integrity check functions (hash functions) detect changes to data → verify that data is correct & complete, or detect that this is not the case
- DOA: digital signatures and message MACs verify the source and integrity of data → verify that data is original and comes from a specific source, or detect that this is not the case
7
Q
cryptographic hash functions
A
- often used for integrity checks
- apply hash function h to a document x and store the result h(x) in a secure place
- result h(x) is called “hash value”, “message digest” or “checksum”
- changes to x can be detected by re-computing the hash of x and comparing the result with the stored value
8
Q
Definition hash function
A
hash function is a function h which has, as a minimum, following two properties
- Ease of computation: Given h and an input x, it is easy to compute h(x)
- Compression: the hash function maps inputs of arbitrary length to fixed length results
Note: hash function usually implies an unkeyed hash function.
a keyed hash function is a function h(x,k) that takes some arbitrary-length input x and a fixed-length key k as input
9
Q
Manipulation detection codes (MDCs)
A
Used to detect changes to a document; unkeyed hash
Two types of MDCs:
- One-way hash function (OWHF): finding an input which hashes to a pre-specified hash-value is difficult
- Collision resistant hash function (CRHF): finding any two inputs having the same hash value is difficult
10
Q
Message authentication codes (MACs)
A
Used to assure both the source of a message and its integrity; keyed hash function
11
Q
Security properties of hash functions (see HAC)
A
- Pre-image resistance (one-way): for any given y, it is computationally infeasible to find x so that h(x)=y
- 2nd pre-image resistance: given x, it is computationally infeasible to find x’, x ≠ x’, so that h(x)=h(x’)
- Collision resistance: it is computationally infeasible to find x and x’, x ≠ x’, so that h(x)=h(x’)
12
Q
Properties of one-way functions
A
13
Q
Hash functions
A
OWHF:
- ease-of-computation, compression,
pre-image resistance, 2nd-preimage resistance - One-way functions can e.g. be used for storing passwords
CRHF:
- ease-of-computation, compression, 2nd-preimage resistance, collision resistance
- Collision resistance implies 2nd-preimage resistance
- In practice, CRHF usually are preimage resistant as well
- Some pathological examples are collision resistant but not preimage resistant
Well known hash functions: SHA-1, RIPEMD-160, MD5
14
Q
Properties of cryptographic hash functions
A
15
Q
Checksums
A
The result of applying a hash function is called hash value, message digest, or checksum.
The last term creates frequent confusion:
- In communications, checksums often refer to error correcting codes, typically a cyclic redundancy check (CRC).
- Checksums used by anti-virus products, on the other hand, must not be computed with a CRC but with a cryptographic hash function.
Note: A cyclic redundancy check (CRC) is not a cryptographic hash function: CRC’s are designed for detecting transmission errors
16
Q
Some use cases of crytographic hashes (OWHF, CRHF)
A
CRHF:
- Verification of data integrity, signatures
- File identification (P2P, git)
OWHF:
- Password Storage
- Key derivation
17
Q
Birthday paradox
A
- Given an n-bit hash y, the expected number of tries before an x with h(x)=y is found is 2n.
- Given n-bit hash values, a set of 2n/2 inputs is likely to contain a pair causing a collision
- Birthday paradox: put m balls numbered 1 to m into an urn; draw a ball, list its number, and put it back; repeat; for m → ∞, the expected number of draws before a previously drawn number appears is
√0.5*π*m
18
Q
Complexity of brute-force attacks
A
Output size of hash function: n bit Pre-image and 2nd pre-image:
- Average complexity: O(2n)
Collision: birthday „attack“:
- Average complexity: O(20.5n)
Illustration of complexity:
1 Gops/s, 100 parallel ops/unit, 1000 units:
264 ops in about 50 hours
280 ops in about 380 years
2128 ops in about 1017 years
19
Q
Construction Hash function
A
Pattern for the design of fast hash functions:
- The core of the hash function is a compression function f that works on fixed size input blocks.
- An input x of arbitrary length is broken up into blocks x1,…, xm of the given block size; the last block has to be padded.
- Compute the hash of x by repeatedly applying the compression function: with a (fixed) initial value h0, compute hi = f(xi||hi-1) for i=1,…, m and take hm as the hash value of x.
The symbol “||” denotes concatenation.
20
Q
Hash Functions: A Typical Architecture
A
21
Q
Hash function constructions examples
A
Current generation: SHA-512
- Whirlpool, …
SHA-3 (Keccak)
22
Q
What if input data is not a multiple of compress function input data size n?
A
Trivial padding: add as many 0-bit as necessary to obtain a multiple of n (Example: n=64)
- „0x45“ => „0x4500000000000000“
- „0x4500“ => „0x4500000000000000“
- Result: H(„0x45“) = H(„0x4500“)
Improved padding: add 1 single 1-bit and, after that, as many 0-bit as necessary to obtain a multiple of n
- „0x45“ => „0x4580000000000000“ „0x4500“ => „0x4500800000000000“ Result: H(„0x45“) ≠ H(„0x4500“)
23
Q
MD-Strengthening:
A
MD-Strengthening:
- Add as many 0-bit as necessary to obtain a multiple of n
- Add another block that encodes the full message length
- Avoids simple 2nd preimage attack
Some additional benefits
- Avoids long message attacks
Avoids fixed-point attacks
Avoids trivial collisions for free choice of IV
24
Q
Input Message Size: Padding
A
Padding as defined for MD5, SHA-1, SHA-224, SHA-256
- Add a single 1-bit, then as many 0-bit as necessary to obtain input size congruent 448 (mod 512)
- Add a 64-bit word indicating total input data size (mod 264)
SHA-384/SHA-512:
- Same idea, but 1024 bit blocks and 128 bit for length
25
Message Authentication Codes
**Cryptographic Hash:**
* Do not depend on any secret key
* I.e., anyone key calculate the hash
* **For integrity checks, hash values have to be protected!**
**Message Authentication Code (MAC)**
* Similar to cryptographic hash
* But: dependent on a secret key
* Knowledge of key necessary for calculating (or verifying) the message authentication code
* keyed hash function for data origin authentication
26
Message authentication codes (2)
**Simple constructions:**
* "secret prefix”: calculate h(k || m)
* “secret suffix”: calculate h(m || k)
* “secret envelope”: calculate h(k1 || m || k2)
27
Message authentication codes (3)
HMAC construction: take a hash function h, for a key k and a document x, compute
**HMAC(x) = h(k** **×** **o\_pad || h(k** **×** **i\_pad || x))**
(i\_pad, o\_pad are padding fields, “||“ means concatentation)
28
Encryption
Encryption algorithms (ciphers) protect the confidentiality of data
Some encryption algorithms can also be used for integrity checks
A plaintext (clear text) x is converted into a ciphertext under the control of a key K
* we write eK(x)
Decryption with an appropriate key computes the plaintext from the ciphertext
* we write dK(x)
29
Symmetric key encryption
30
Symmetric key encription
31
Cryptoanalysis
Cryptanalysis: science of recovering the plaintext from ciphertext without the key.
Always assume attackers know the algorithms used
* Algorithms can be published to facilitate the evaluation of their security
* Security should depend on secrecy of the key, not the algorithm
Contrast with security by obscurity.
* Analogy: Hide a letter under your mattress versus lock it in a safe, whose design has been published and whose locking mechanism has withstood attacks from the world’s best safecrackers.
32
Defining Security with Games
Games are frequently used to model formal security properties!
* Cryptosystem is considered secure if no adversary can win the game with significantly greater probability than an adversary who just guesses randomly
33
Model of Attack
We can think of the adversary as playing a game:
* Input: Whatever adversary necessarily knows from the beginning, e.g., public key, distribution of plain texts, etc.
* Oracle: Models information adversary can obtain during an attack. Different kinds of information characterise different types of attacks.
* Output: Whatever the adversary wants to compute, e.g., secret key, partial information on plain text, etc. He wins if he succeeds.
34
Attacks
1. Cyphertext Attack
Given: eK(x1), eK(x2) ...
Goal: deduce x1, x2 ,..., or K
2. Known Plaintext Attack
Given: (x1, eK(x1)), x2, eK(x2)), ... Goal: deduce K
3. Chosen Plaintext Attack
like 2, but the attacker can choose xi
4. Adaptive Chosen Plaintext Attack
can not only choose plaintext, but can modify the plaintext based on encryption results
5. Chosen ciphertext
Attacker can chose different ciphertexts to be decrypted and gets access to the decrypted plaintext.
34
Attacks
1. Cyphertext Attack
Given: eK(x1), eK(x2) ...
Goal: deduce x1, x2 ,..., or K
2. Known Plaintext Attack
Given: (x1, eK(x1)), x2, eK(x2)), ... Goal: deduce K
3. Chosen Plaintext Attack
like 2, but the attacker can choose xi
4. Adaptive Chosen Plaintext Attack
can not only choose plaintext, but can modify the plaintext based on encryption results
5. Chosen ciphertext
Attacker can chose different ciphertexts to be decrypted and gets access to the decrypted plaintext.
35
Cryptographic Security
1. Specify an oracle (a type of attack).
2. Define what the adversary needs to do to win the game, i.e., a condition on his output.
3. The system is secure under this definition, if any efficient adversary wins the game with only negligible probability.
35
Cryptographic Security
1. Specify an oracle (a type of attack).
2. Define what the adversary needs to do to win the game, i.e., a condition on his output.
3. The system is secure under this definition, if any efficient adversary wins the game with only negligible probability.
36
Symmetric Key Cryptography
An encryption scheme({eK1 :K1 ∈K},{dK2 :K2 ∈K})is symmetric if for each pair (eK1, dK2) it is computationally “easy” to determine dK2 knowing only eK1 (and vice versa).
```
In practice: eK1 = dK2
Symmetric ciphers (secret key cryptography): same key is used for encryption & decryption
```
* Encryption protects e.g. documents on the way from A to B
* A and B have to share a key and keep their keys secret
* A procedure is required for A and B to obtain their shared key
* For n parties to communicate directly, about n2 keys are needed (serious drawback in practice...)
37
Block Ciphers vs. Stream Ciphers
A block cipher is an encryption scheme that breaks up the plaintext message into strings (blocks) of a fixed length l and encrypts one block at a time.
A stream cipher is one where the block-length is 1
38
Caesar Cipher (n=3)
If we use the algorithm of simply moving each letter nplaces down the alphabet then the original alphabet we were using, or the plain text becomes a cipher text as follows:
a →d
b→e
c→f
39
Mono-alphabetic substitution ciphers
Let K be the set of all permutations on the alphabet A. Define for each K ∈ K an encryption transformation eK on
strings x = x1x2...xn ∈. M as
eK(x) = K(x1)K(x2) · · · K(xn) = c1c2...cn = c
To decrypt c, compute the inverse permutation dK(c) = (eK(x))-1
eK is a mono-alphabetic substitution cipher.
Example: ROT13: shift each letter by 13 places. In Unix: „tr a-zA-Z n-za-mN-ZA-M“
40
Security of such substitution
Huge key space: 26 letters = 26! Keys, but:
* Easily broken by analysing the frequency of letters in texts written in a certain language
* Tables can be used for pairs of letters, or forbidden pairs...
* Computers can break such „encryption“ in real time.
41
Improvement: Homophonic Substitutions
Idea:
* Map groups of letters into new groups
* Expand the alphabet (numbers, special characters)
Important:
* Try to find a mapping that results in an equal distribution of characters; this reduces the risks of attacks based on a letter frequency analysis
Problem:
* If an attacker gets access to plain and cipher text of one message: Game Over....
* N.B.: The plain text is in many cases partly known
42
Vigenère-Cyphers
43
* Attacking Vigenère
If the length of the key is known, split text accordingly; then:
* Each block uses a Caesar Cipher.
Example: length = 4
* take 1., 5., 9., etc. character and attack with a letter frequency analysis
* Continue with 2., 6., 10., ..
If the length is unknown: try to guess it and attack it as above
* Computers were built for stupid tasks like this...
44
One-time pad
45
Transposition Ciphers
* Transposition does not change the letters itself, but their position in a text
* Example: Write text in groups of 5 letters, and read it in columns
46
Composite Ciphers
Ciphers based on just substitutions or transpositions are in general not secure
* Ciphers need to be combined.
But:
* Two substitutions are actually only another substitution,
* Two transpositions are actually only one transposition,
A substitution followed by a transposition makes a new and (presumably) more secure cipher.
* Difficult to do by hand → invention of cipher machines
47
Properties of the Enigma
A letter never maps to itself
Encryption and decryption works with identical settings
2x1020 different keys
Code books were used to transport the keys:
* A distinct setting of rotors for each day to encrypt a message („session“) key
* Individual message keys were used to encrypt transmissions
* The Enigma was believed to be very secure
* this was in fact true, compared to the state of the art in encryption at that time
* However, the scheme was broken...
47
Properties of the Enigma
A letter never maps to itself
Encryption and decryption works with identical settings
2x1020 different keys
Code books were used to transport the keys:
* A distinct setting of rotors for each day to encrypt a message („session“) key
* Individual message keys were used to encrypt transmissions
* The Enigma was believed to be very secure
* this was in fact true, compared to the state of the art in encryption at that time
* However, the scheme was broken...
48
Weaknesses of the Enigma scheme
* The machine (or parts of it) became accessible to the adversary
* Certain specifics of the ciphering scheme
plus:
* The adversary spend enormous effort on breaking the scheme (Bletchley Park, Polish Scientists)
* Lots of cipher text was available
Plaintext Attack : If a certain word of the plain text is known, one can determine the positions in the cipher text, where this word possibly appears.
49
Block ciphers & stream ciphers
**Block ciphers****: encrypt sequences of “long” data blocks without changing the key**
* **security relies on design of encryption function**
* **typical block length: 64 bits, 128 bits**
**Stream ciphers****: encrypt sequences of “short” data blocks under a changing key stream**
* **security relies on design of key stream generator**
* **encryption can be quite simple, often XOR**
* **typical block length: 1 bit, 1 byte, 8-bit word**
* *-\> Example: WEP encryption in IEEE802.11b**
50
WLAN Security Threat Model
* *Four main threats:**
* *1. Intruder (user authentication)**
**2. Evesdropping**
**3. Man in the middle attack (fake AP)**
**4. Back door (rogue AP)**
51
Wired Equivalence Privacy
**Shared key between**
* **Stations.**
* **An Access Point.**
**Extended Service Set**
* **All Access Points will have same shared key.**
**No key management**
* **Shared key entered manually into**
**Stations**
**Access points**
**Key management nightmare in large wireless LANs**
52
Properties of Vernam Ciphers
The WEP encryption algorithm RC4 is a Vernam Cipher:
53
Block cipher modes
**Block ciphers modes offer different security and error propagation characteristics**
**Electronic code book (ECB):** **blocks are encrypted independently under the same key**
**Cipher block chaining (CBC):** **cipher block** **Ci** **depends on the previous block** **Ci-1**
**Output feedback (OFB):** **block cipher used as a key stream generator**
**Cipher feedback (CFB):** **block cipher used as a data dependent key stream generator**
53
Block cipher modes
**Block ciphers modes offer different security and error propagation characteristics**
**Electronic code book (ECB):** **blocks are encrypted independently under the same key**
**Cipher block chaining (CBC):** **cipher block** **Ci** **depends on the previous block** **Ci-1**
**Output feedback (OFB):** **block cipher used as a key stream generator**
**Cipher feedback (CFB):** **block cipher used as a data dependent key stream generator**
54
ECB vs. CBC
55
CBC
56
Advantages and Limitations of CBC
57
OFB
58
OFB Advantages and Limitations
59
CTR (Counter)
60
CTR: Advantages and Limitations
61
Product Ciphers
**A** **product cipher** **or** **composite cipher** **is built from simple operations offering complementary protection.**
**Example: a substitution-permutation network**
* **“****S-Boxes****” confuse input bits.**
* **“****P-Boxes****” diffuse bits across S-box inputs**
62
Properties Prdouct Ciphers
**Important Properties :**
* **Completeness (dependence): Each output bit depends on every input bits.**
* **Avalanche effect: flipping one input bit changes approx. half the output bits.**
63
DES
64
3DES/2, 2DES and 3DES/3
56 Bit DES is vulnerable to brute force attacks
**We can use multiple DES**
* *Take** ***X*** **keys and apply DES** ***y*** **times: 2DES/2, 3DES/2, 3DES/3**
* *We can effectively extend the length of encryption keys using existing**
**DES**
* **Using two keys to extend the key length to 112 bits, making DES much more secure against brute-force attacks**
**Notes on 2DES/2:**
* **2DES/2 uses just as many keys as 3DES/2, extending the key length to 112**
* **However, 2DES/2 is vulnerable to the meet-in-the-middle attack**
65
2DES
66
3DES/2
67
Feistel Cipher
68
AES
69
AES 2
70
Random Numbers
Cryptography uses random numbers for:
* * Generating symmetric keys
* initailizing values
* nounces
BUT: Deterministic machines can never produce true statistically random numbers
70
Random Numbers
Cryptography uses random numbers for:
* * Generating symmetric keys
* initailizing values
* nounces
BUT: Deterministic machines can never produce true statistically random numbers
71
Natural sources for random generators
Thermal Nouse, e,g, agitation of electrons inside an electrical conductor
radioactive decay
cosmic radiation
72
PRNGS
Pure random numbers often too hard to get
* numbers that are unpredictable and cannot be reproduces are acceptable
* a PRNG is deterministic algorithm which given a truly random binary sequence of length k, outputs a binary sequence of length k, outputs a binary seq. of length I \>\> k, which appears to be random.
Polynomial time statistical tests:
* no Pat can distinguish an output seq. of the PRNG and a truly random seq.
Next-bit test:
* there is no polynomial time algorithm which on input of the first/bits of an output seq. s , ca predict the I+1 st bit of s with a prob. greater than 0.5
73
CSPRNGs
Cryptographically secure PRNGs (CSPRNGs)
* A CSPRNG is a PRNG which passes the next bit test under hypothesis such as intractability of factoring integers.
Security of many systems critically depends on the quality of a PRNG/CSPRNG
74
RND Sources in Computers
* Mouse movement (coordinates)
* Combination of: Process id, clock ticks since boot, username, time, internal system counters, page fault counts, etc.
* Bits from (compressed) sound card input
Algorithmic Schemes (linear congruential Generators)
Xn+1 = (a . xn+c) mod m
problem if alg. is known and the seed can be guessed, then the seq. can be reproduces
* seed must be kept secret and must be long enough to defeat brute force attacks
75
Linear Congruential Generators
Xn+1 = (a . xn+c) mod m
x0=0 a=1=c m = 20
* if m is prime then carefully chosen values of a can be good enough
* x0 should be sufficiently large and random
* algorithm should be restarted once in a while
76
Blum Blum Shub
xn+1= (xn)2 mod m
where m=p\*q is the product of two large primes p and q
plus:
* a few more req
* a mapping of the output
it can be shown that this is a csprng by relating the prediction of values to integer factorization
77
Other methods for RGN
* use of ciphers as DES to produce random numbers from seeds: a good cipher produces an output independent of the input
* ciphers in off ort car-mode based on an initial seed
78
cryptographic keys
**Most cryptographic algorithms take a** **key** **as one of their inputs**
**Kerckhoffs’ principle****: do not rely on the secrecy of cryptographic algorithms; only the keys have to be kept secret**
**State of the art: standardized algorithms that have been examined quite intensively and are often the strongest part in a security architecture**
**Good key management practices are required to reap the benefits of strong cryptography**
79
Problem with sending secret key in symmetric key encryption
* **we can send the keys on a different communications channel, e.g. by courier**
* **We can also shift the problem in time and exchange keys at a more convenient moment**
* **We can combine both methods and meet in person to exchange keys for future use**
80
Key exchange without secrets
