密码学overview.ppt

1、1,曹天杰 Tianjie Cao College of Computer Science and Technology, China University of Mining and Technology, Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.5.12,Overview,2,A. J. Menezes, P. C. van Oorschot and S. A. Vanstone. Handbook of Applied Cryptography, CRC Press, 1997. Bruce Schneier. Applied Cryptography,

2、Second Edition: Protocols, Algorthms, and Source Code in C (cloth) John Wiley provide confidence in the identity of a connecting entity Logging in with a password Gaining access via biological identity verification DNA identification, retinal scan, finger/hand print identification Access via audio v

3、oice identification Data Origin Authentication in a connectionless environment; provide assurance that the source of received data is as claimed Corroborates the source of the data Does not proved assurance against duplicate or modified data,12,Access Control,This service provides protection against

4、 unauthorized use of resources accessible via OSI. These may be OSI or non-OSI resources accessed via OSI protocols. This protection service may be applied to various types of access to a resource or to all accesses to a resource e.g., the use of a communications resource; the reading, the writing,

5、or the deletion of an information resource; the execution of a processing resource,13,Data Confidentiality,Connection Confidentiality Protection of all user data on a connection Connectionless Confidentiality Protection of all data within a single data block Selective-Field Confidentiality Insure co

6、nfidentiality of selected fields with within the user data on a connection or in a single data block connection Traffic-Flow Confidentiality Protection of information that might be derived by observing the traffic flow patterns,14,Data Integrity,Connection Integrity with Recovery Detect any modifica

7、tion of stream data or replay of data and retry; Connection Integrity without Recovery Detect any modification and report it, no retrycontinue on Selective-Field Connection Integrity Same except for selected fields Connectionless Integrity Detect modifications in fixed block connectionless data, may

8、 provide replay detection and protection Selective-Field Connectionless Integrity Same, except for selected fields Total stream protection would encompass all of the above and is probably the best strategy,15,Nonrepudiation,Nonrepudiation, Origin Proof that the message was sent by the specified part

9、y Nonrepudiation, Destination Proof that the message was received by the specified party,16,Security Mechanisms (X.800),Encipherment algorithmic/mathematical conversion Digital Signature appending a secret signature Access Control - Data Integrity Authentication Exchange Traffic Padding appending ex

10、tra chars to foil traffic analysis techniques Routing Control selection of secure routeds through the network Notarization use a trused 3rd party (like a notary public),17,Other Security Mechanisms(non X.800),Trusted Functionality That which is perceived to be true by some criteria (policy) Security

11、 Label The marking of (bound to) a resource that names or designates the security attributes of the resource Event Detection Intrusion detection Detection of specific hacks (detector hardware) Too many log in attempts Security Audit Trail Logging of all system events Security Recovery Recovery based

12、 on requests from security mechanisms and/or event handling.,18,The Compromises of Security,There is no absolute security! Race between attackers and defenders Constant innovation Well-funded, capable, determined attacker succeed Costs Relative to targets value Users inconvenience Users acceptance D

13、etection Rarely possible in real time Works mostly forold threats,Punishment Hard at a distance No international legislation Poor domestic legislation Perceived “unethical” Freedom of expression Intangibility,19,Information security and cryptography,Cryptography is the study of mathematical techniqu

14、es related to aspects of information security Cryptographic goals Confidentiality Data integrity Authentication Non-repudiation ,20,Cryptographical Building Blocks,BlockCiphers,Stream Ciphers,Symmetric KeyCryptography,Authentication,Privacy,Encryption,HashFunctions,ChallengeResponse,IVs,MACsMICs,Mes

15、sageDigests,Nonces,PseudoRandom,RandomSources,Secret Keys,SmartCards,DHRSA,Public KeyCryptography,EllipticCurves,Digital Signatures,DataIntegrity,Secure Network Protocols,Non-Repudiation,21,Is Cryptography the Solution?,Cryptography is not the same as security 85% of all CERT advisories cannot be fi

16、xed by crypto 30-50% of recent security holes from buffer overflow,Computer Security,Cryptography,Law,Operatingsystems,Mathematics,Networking,Programminglanguages,Economics,Psychology,Humancomputerinteraction,22,Is Cryptography the Solution?,The real world offers the attacker a richer menu of option

17、s than mere cryptanalysis. Often more worrisome are protocol attacks, Trojan horses, viruses, electromagnetic monitoring, physical compromise, blackmail and intimidation of key holders, operating system bugs, application program bugs, hardware bugs, user errors, physical eavesdropping, social engine

18、ering, and dumpster diving, to name just a few.,23,Security Standards,Internet - Internet Engineering Task Force (IETF) De Facto (PGP email security system, Kerberos-MIT) ITU (X.509 Certificates) National Institute of Standards and Technology (SHA) IEEE Department of Defense, Nat. Computer Security

19、Center - Tempest (radiation limits) - Orange Book: Class A1, B3, C1, C2, . Export Controls - High Performance Computers - Systems with “Hard” Encryption,24,A Brief History of Cryptography,2000 years ago: Substitution ciphers A few centuries later: Permutation ciphers Renaissance: Polyalphabetic ciph

20、ers Jefferson Cylinder (1790) Wheatstone disc (1870),25,A Brief History of Cryptography,The Enigma Rotor Machine (WW2) 1975: DES 1976: Public-key cryptography 1996-2000 AES,26,Cryptosystem,A cryptosystem is a five -tuple (P, C, K, E, D), where the following conditions are satisfied: 1. P is a finite

21、 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 plaint

22、ext x P.,27,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,Unke

23、yed Primitives,Symmetric-key Primitives,Public-key Primitives,Security Primitives,Block ciphers,Stream ciphers,28,Cryptography - Terminology I,Cryptology is a branch of mathematics,29,Cipher,Cryptography - Terminology II,30,Crypto tools,one-way function Encryption/decryption to hide info Key exchang

24、e- to establish shared key Authentication to establish shared key with the party you really meant to public private Signatures Hashing Certificates, PKI,31,Background on Functions,Function f : X Y is called a function f from set X to set Y. X: domain; Y: codomain. for y = f(x) where x X and y Y y: i

25、mage of x x: preimage of y Im(f), image of f the set that all y Y have at least one preimage 1 1 function if each element in Y is the image of at most one element in X. onto function if Im(f) =Y bijection function if f is 11 and onto.,32,Background on Functions (ctd),one-way function if f(x) is easy

26、 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.,33,Encryption / Decryption,encoder,decoder,(plaintext in - ciphertext out),ciphertext msg,(c

27、iphertext in - plaintext out),(should understand nothing about the msg),eavesdropper,cmb-cmb,Shared Key,34,Key exchange,Alice and Bob want to establish a shared secret (key) when other people (eavesdroppers) are listening Passive just looking Active may change msgs,Alice,Bob,35,Key exchange: man-in-

28、the-middle,Key exchange without Authentication Subject to Man-in-the-Middle attack Attacker translates between the keys, reading and/or modifying the messages Authentication afterwards will not help!,Alice,Bob,Shared w/Alice,Shared w/Bob,36,Authentication,M,Alice,Bob,Alice sends a msg to Bob Bob wan

29、ts to be sure the msg is really from Alice,the problem of proving that a user is who he says he is,37,Signatures,Alice,Bob,SAlice,SigM= Sign(M, SAlice ),= (M, SigM),38,Authentication: “public”,checks contracts,39,Public Key Signatures,PAlice,Verify(M, SigM, PAlice ),Public Key Secret Key,40,Certific

30、ates,“This public key PAlice really belongs to Alice. Signed by Charlie, Certification Authority” Certificates can be public! Whos Charlie?!?,Alice,Charlie, CA,SAlice,Public Key Secret Key,PAlice,41,Public Key Infrastructures (PKI),Root CA public key Obtained out-of-band Certifies other Public Keys

31、(of CAs, or users) Certification Chains Grain of salt: so, you have a certificate To be continued,42,Signatures,Alice,Bob,SAlice,SigM= Sign(M, SAlice ),= (M, SigM),43,Authentication: “private”,SAlice,Verify(M, SigM, SAlice ) : Check SigM= Sign(M, SAlice ),Message Authentication Code (MAC) Sign(M, SA

32、lice )=Hash(M, SAlice ),MAC = “Shared Secret Sig” = Symmetric Sig (Sign=Verify),44,Hashing,Crypto Hash: collisions may exist, but are hard to find Given y hard to find x, s.t. Hash(x)=y Used for: Symmetric signatures “Fingerprint” for Public Key signatures,x1,Hash,y,x2,collision,45,Cryptanalysis - F

33、undamental Assumptions,Attacker knows every detail of the cryptographical algorithm Attacker is in possession of encryption / decryption equipment (HW machine or SW implementation) Attacker has access to an arbitrary number of plaintext / ciphertext pairs generated with the same (unknown) key. Stron

34、g cipher: Best attack should be brute force key search!,46,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 key

35、s) 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

36、(P2),.Pi, Ci = Ek(Pi) Deduce: Either k, or an algorithm to infer Pi+1 from Ci+1 = Ek(Pi+1),47,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(

37、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! Chos

38、en-ciphertext attack Given: C1, P1 = Dk(C1), C2, P2 = Dk(C2),.Ci, Pi = Dk(Ci) Deduce: k,48,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 Com

39、plexity-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

40、,49,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

41、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

42、 computational security unforeseen attacks may remain,50,Cipher = Encoder; or Encryption/Decryption scheme Stream cipher encodes/decodes char by char Block cipher encodes/decodes block by block Stream cipher Block cipher with block size of 1 char (+state) Chaining (Modes of Operation) make block enc

43、ryption depend on the past blocks “make block ciphers more like stream ciphers”,Block vs. Stream Ciphers,51,Symmetric hard = exponential Easy problems: Finding max of n numbers - O(n) Sorting n elements- O(n lg n) Hard problems: Factoring N=pq (n bits long)- current best (?),67,Other hard problems,L

44、et N=pq, where p,q are large primes Square root mod N given x,N find y= mod N, i.e. y2=x mod N (equivalent to factoring N) Discrete log given b,N and x, find y = How hard are these problems really? One-way functions: easy to compute hard to invert Trap-door: a secret making inverting a owf easy,68,P

45、seudo-Random Bit Generators,Deterministic functions RNG : 0,1n 0,1 Stretch fixed-size seedto an unbounded sequencethat looks random Computable approximationof one-time pad Example: RC4,Example: i := 0 i := 0 do forever i := i+1 mod 256 j := j+sI mod 256 swap si,sj t := si+sj mod 256 output st Seed:

46、initial value of s Size of state: (2256)256,69,Symmetric Algorithms: Stream Ciphers,One-time pad using a RNG Ek(m) = m RNG(k),70,Stream CiphersLinear Feedback Shift Registers (LFSRs),Maximum possible sequence length is 2n - 1 with n registers LFSRs are often used as building blocks for stream cipher

47、s GSM A5 is a cipher with 3 LFSRs of lengths 19, 22, and 23,71,Integrity of Documents and Messages,Detection of corrupted documents and messages Detection of bit errors caused by unreliable transmission links or faulty storage media. Solution: Message Digest acting as a unique fingerprint for the do

48、cument (similar function as CRC). Protection against unauthorized modification Without protection a forger could create both an alternative document and its corresponding correct message digest. Symmetric Key Solution: Message Authentication Code (MAC) formed by using a keyed message digest function

49、. Asymmetric Key Solution: Digital Signature formed by encrypting the message digest with the document authors private key.,72,Message Digests based onOne-Way Hash Functions,A single bit change in a document should cause about 50% of the bits in the digest to change their value !,73,Popular Hash Fun

50、ctions,SHA - Secure Hash Algorithm, NIST / NSA,MD5 - Message Digest #5, Ron Rivest, RSA,74,Basic Structure of the MD5 / SHA One-Way Hash Functions,N x 512 bits,Document,75,Message Authentication Codes based onKeyed One-Way Hash Functions,76,Basic Structure of a Keyed One-Way Hash Function,Key Length

51、 Hash Length,RFC 2104,77,Digital Signatures based onPublic Key Cryptosystems,78,Forging Documents,On average 2m trials are required to find a document having the same hash value as a given one !,79,The Birthday Paradox,What is the probability of another person having the same birthday as you ? Proba

52、bility p = 1/365 How many people must be a in a room so that the probability of at least another person having the same birthday as you is greater than 0.5 ?, n = 253 people,How many people must be in a room so that the probability of at least two of them having the same birthday is greater than 0.5 ?, n = 23 people,80,Birthday Attacks against Hash Functions,Only about 2m/2 trials are required to find two documents having the same hash value MD5 might be insecure !,L