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