Outline 曹天杰 Tianjie Cao ticao@cumt.edu.cn College of Computer Science and echnology china University of Mining and Technology Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.6.16
曹天杰 Tianjie Cao tjcao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.6.16 Outline
Attacks. Services, and mechanisms Security attack: Any action that compromises the securi of information Security Mechanism: A mechanism that is designed to detect, prevent, or recover from a security attack Security service: a service that enhances the security of data processing systems and information transfers. A security service makes use of one or more security mechanisms
Attacks, Services, and Mechanisms * Security Attack: Any action that compromises the security of information. * Security Mechanism: A mechanism that is designed to detect, prevent, or recover from a security attack. * Security Service: A service that enhances the security of data processing systems and information transfers. A security service makes use of one or more security mechanisms
Cryptosystem A cryptosystem is a five -tuple(P, C, K, E,D), where the following conditions are satisfied 1. P is a finite set of possible plain teXts 2. C is a finite set of possible ciphertexts 3. K, the keyspace, is a finite set of possible keys 4. For each kEK, there is an encryption rule eK E E and a corresponding decryption rule dk∈D. Each ek:P> C and d,:C→Pare functions such that dex( x )=x for every plaintext X∈P
Cryptosystem • A cryptosystem is a five -tuple (P, C, K, E, D), where the following conditions are satisfied: • 1. P is a finite set of possible plain texts • 2. C is a finite set of possible ciphertexts • 3. K, the keyspace, is a finite set of possible keys • 4. For each kK, there is an encryption rule eK E. and a corresponding decryption rule dK D). Each eK : P → C and dK : C → P are functions such that dK(eK(x)) = x for every plaintext x P
Taxonomy of cryptographic primitives Arbitrary length hash functions Unkeyed Primitives One-way permutations Random sequences Block ciphers Symmetric-key ciphers Stream Arbitrary length hash functions(MACs) ciphers Security Symmetric-keyl Primitives Primitives Signatures Pseudorandom sequences Identification primitives Public-key ciphers Public-key Primitives Signatures Identification primitives
Taxonomy of cryptographic primitives. Arbitrary length hash functions One-way permutations Random sequences Symmetric-key ciphers Arbitrary length hash functions(MACs) Signatures Pseudorandom sequences Identification primitives Public-key ciphers Signatures Identification primitives Unkeyed Primitives Symmetric-key Primitives Public-key Primitives Security Primitives Block ciphers Stream ciphers
Background on Functions(ctd) one-way function if f(x)is easy to compute for all XE X, but it is computationally infeasible to find any XE X such that f(x)=y trapdoor one-way function if given trapdoor information, it becomes feasible to find an x E X such that f(x)y
Background on Functions (ctd) • one-way function if – f(x) is easy to compute for all x X, but – it is computationally infeasible to find any x X such that f(x) =y. • trapdoor one-way function if – given trapdoor information, it becomes feasible to find an x X such that f(x) =y
Cryptanalysis Types of Attacks Ciphertext-Only Attack Attacker knows ciphertext of several messages encrypted with the same key and/or several keys Recover the plaintext of as many messages as possible or even better deduce the key ( or keys) G Iven EK(P1, C2=EK(P2)CEk(P Deduce: EitherP, P2,P k; or an algorithm to infer Pi+from C+=Ek(Pi+v Known-Plaintext attack Known ciphertext/plaintext pair of several messages Deduce the key or an algorithm to decrypt further messages Given: P, C- Ek(P, P2, C2=Ek(P2)Pi, Ci-Ek(P) Deduce: Either k, or an algorithm to infer Pi from 1=E(P1+)
Cryptanalysis - Types of Attacks • Ciphertext-Only Attack – Attacker knows ciphertext of several messages encrypted with the same key and/or several keys – Recover the plaintext of as many messages as possible or even better deduce the key (or keys) – Given: C1 = Ek (P1 ), C2 = Ek (P2 ),...Ci = Ek (Pi ) Deduce: Either P1 , P2 ,...Pi ; k; or an algorithm to infer Pi+1 from Ci+1 = Ek (Pi+1) • Known-Plaintext Attack – Known ciphertext / plaintext pair of several messages – Deduce the key or an algorithm to decrypt further messages – Given: P1 , C1 = Ek (P1 ), P2 , C2 = Ek (P2 ),...Pi , Ci = Ek (Pi ) – Deduce: Either k, or an algorithm to infer Pi+1 from Ci+1 = Ek (Pi+1)
Cryptanalysis Types of Attacks Chosen-Plaintext Attack Attacker can choose the plaintext that gets encrypted thereby potentially getting more information about the key Given P C- Ek(PD, P2, C2-Ek(P2,- Ek(P), where the cryptanalyst gets to choose P,, P,, .P Deduce: Either k, or an algorithm to infer Pi from Ci+I=Ek(P Adaptive Chosen-Plaintext Attack Attacker can choose a series of plaintexts, basing choice on the result of previous encryption >differential cryptanalysis Chosen-ciphertext attack Given: C1, PI= DK (C1, C2, P2=Dk( C2). Ci P=DK(C Deduce: k
Cryptanalysis - Types of Attacks • Chosen-Plaintext Attack – Attacker can choose the plaintext that gets encrypted thereby potentially getting more information about the key – Given: P1 , C1 = Ek (P1 ), P2 , C2 = Ek (P2 ),...Pi , Ci = Ek (Pi ), where the cryptanalyst gets to choose P1 , P2 ,...Pi Deduce: Either k, or an algorithm to infer Pi+1 from Ci+1 = Ek (Pi+1) • Adaptive Chosen-Plaintext Attack – Attacker can choose a series of plaintexts, basing choice on the result of previous encryption → differential cryptanalysis! • Chosen-ciphertext attack – Given: C1 , P1 = Dk (C1 ), C2 , P2 = Dk (C2 ),...Ci , Pi = Dk (Ci ) – Deduce: k
Models for evaluating security Unconditional security(perfect secrecy) Adversaries have unlimited computational resources Observation of the ciphertext provides no information to an adversary One time pad Complexity-theoretic security Adversaries have polynomial computational power Asymptotic analysis and usually also worst-case analysis is used Provable security provably secure if the difficulty of defeating crypto system can be shown to be as difficult as solving a well-known number-theoretic problem
Models for evaluating security • Unconditional security (perfect secrecy) – Adversaries have unlimited computational resources – Observation of the ciphertext provides no information to an adversary – One time pad • Complexity-theoretic security – Adversaries have polynomial computational power. – Asymptotic analysis and usually also worst-case analysis is used • Provable security – provably secure if the difficulty of defeating crypto system can be shown to be as difficult as solving a well-known number-theoretic problem
Models for evaluating security(ctd) Computational security(Practical security) We might define a cryptosystem to be computationally secure if the best algorithm for breaking it requires at least N operations, where N is some specified, very large number The problem is that no known practical cryptosystem can be proved to be secure under this definition neither the Shift Cipher, the Substitution Cipher nor the Vigenke Cipher is computationally secure against a ciphertext-only attack(given a sufficient amount of ciphertext) Ad hoc security(heuristic security) any variety of convincing computational security unforeseen attacks may remain
Models for evaluating security (ctd) • Computational security (Practical security) – We might define a cryptosystem to be computationally secure if the best algorithm for breaking it requires at least N operations, where N is some specified, very large number. – The problem is that no known practical cryptosystem can be proved to be secure under this definition. – neither the Shift Cipher, the Substitution Cipher nor the Vigenke Cipher is computationally secure against a ciphertext-only attack (given a sufficient amount of ciphertext). • Ad hoc security (heuristic security) – any variety of convincing computational security – unforeseen attacks may remain
Shannons Definition of perfect Secrecy The One-Time pad E(m)=m⊕k ciphertext c One-Time pad k bits of random key K use random key sequence 9111011911 only once and then discard it 1001101010 1101000111
Shannon‘s Definition of Perfect Secrecy m ciphertext C One-Time Pad k bits of random key K 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 use random key sequence only once and then discard it ! The One-Time Pad Ek (m) = m k k