1、Introduction to Cryptography and Security Mechanisms,Dr Keith Martin McCrea 349 01784 443099 keith.martinrhul.ac.uk,Before we start,Introduction to Cryptography and Security Mechanisms 2005,3,Quiz 1,If two parties engage in a process that results in mutual entity authentication then at the end of th
2、e process the two parties can be reasonably confident that: A All subsequent messages that they exchange come from one another B The next messages that they exchange come from one another C The messages that they have just exchanged came from one another D Some messages that they recently exchanged
3、were created by one another at some time in the past,Introduction to Cryptography and Security Mechanisms 2005,4,Quiz 2,If an attacker intercepts a response that is issued during a successful challenge/response exchange and then tries to replay it a later date when a fresh challenge is issued, which
4、 of the following is the most likely reason for why the attacker will not succeed in being authenticated? A The attacker does not know the correct PIN B A response is only ever valid once C The response needs to be accompanied by evidence of freshness D The response might match the fresh challenge,
5、but the probability of this happening is low,Introduction to Cryptography and Security Mechanisms 2005,5,Quiz 3,Which of the following is not a problem with logical time-stamps (sequence numbers)? A Synchronising logical time at either end of the communication link B Preventing attackers from workin
6、g out the next logical time-stamp C Maintaining the integrity of logical time-stamps D Deciding on procedures for coping with lost messages,Introduction to Cryptography and Security Mechanisms: Unit 9 Digital Signatures,Dr Keith Martin McCrea 349 01784 443099 keith.martinrhul.ac.uk,Introduction to C
7、ryptography and Security Mechanisms 2005,7,Learning Outcomes,Explain the concept of a digital signature Recognise that not all digital signatures rely on public key cryptography Appreciate the role that hash functions play in creating digital signatures Demonstrate how digital signatures can be crea
8、ted and verified using RSA Differentiate between digital signatures with appendix and digital signatures with message recovery Distinguish between the properties of digital and hand-written signatures Identify some of the main ways in which digital signature schemes can be attacked,Introduction to C
9、ryptography and Security Mechanisms 2005,8,Sections,Digital signature overview Hash functions Digital signature algorithms Security issues,1. Digital signature overview,Introduction to Cryptography and Security Mechanisms 2005,10,Informal definition,Informally, a digital signature is a technique for
10、 establishing the origin of a particular message in order to settle later disputes about what message (if any) was sent. The purpose of a digital signature is thus for an entity to bind its identity to a message. We use the term signer for an entity who creates a digital signature, and the term veri
11、fier for an entity who receives a signed message and attempts to check whether the digital signature is “correct” or not. Digital signatures have many attractive properties and it is very important to understand exactly what assurances they provide and what their limitations are. While data confiden
12、tiality has been the driver behind historical cryptography, digital signatures could be the major application of cryptography in the years to come.,Introduction to Cryptography and Security Mechanisms 2005,11,Electronic signatures,The European Community Directive on electronic signatures refers to t
13、he concept of an electronic signature as:,data in electronic form attached to, or logically connected with, other electronic data and which serves as a method of authentication,What different things can you think of that might satisfy this rather vague notion of an electronic signature?,Introduction
14、 to Cryptography and Security Mechanisms 2005,12,Advanced electronic signatures,The European Community Directive on electronic signatures also refers to the concept of an advanced electronic signature as:,an electronic signature that is: uniquely linked to the signatory capable of identifying the si
15、gnatory created using means under the sole control of the signatory linked to data to which it relates in such a way that subsequent changes in the data is detectable,Introduction to Cryptography and Security Mechanisms 2005,13,Security requirements,Data origin authentication of the signer A digital
16、 signature validates the message in the sense that assurance is provided about the integrity of the message and of the identity of the entity that signed the message. Non-repudiation A digital signature can be stored by anyone who receives the signed message as evidence that the message was sent and
17、 of who sent it. This evidence could later be presented to a third party who could use the evidence to resolve any dispute that relates to the contents and/or origin of the message.,We will define a digital signature on a message to be some data that provides:,Introduction to Cryptography and Securi
18、ty Mechanisms 2005,14,Input to a digital signature,The message Since a digital signature needs to offer data origin authentication (and non-repudiation) it is clear that the digital signature itself must be a piece of data that depends on the message, and cannot be a completely separate identifier.
19、It may be sent as a separate piece of data to the message, but its computation must involve the message. A secret parameter known only by the signer Since a digital signature needs to offer non-repudiation, its calculation must involve a secret parameter that is known only by the signer. The only po
20、ssible exception to this rule is if the other entity is totally trusted by all parties involved in the signing and verifying of digital signatures.,Introduction to Cryptography and Security Mechanisms 2005,15,Properties of a digital signature,Easy for the signer to sign a message There is no point i
21、n having a digital signature scheme that involves the signer needing to use slow and complex operations to compute a digital signature. Easy for anyone to verify a message Similarly we would like the verification of a digital signature to be as efficient as possible. Hard for anyone to forge a digit
22、al signature It should be practically impossible for anyone who is not the legitimate signer to compute a digital signature on a message that appears to be valid. By “appears to be valid” we mean that anyone who attempts to verify the digital signature is led to believe that they have just successfu
23、lly verified a valid digital signature on a message.,Introduction to Cryptography and Security Mechanisms 2005,16,Arbitrated digital signatures,MACKS,Signer,Verifier,Arbitrator,KS,KV,KV,KS,message,message,MACKV,MACKS,1,2,3,4,Introduction to Cryptography and Security Mechanisms 2005,17,Arbitrated dig
24、ital signatures,Explain why arbitrated digital signatures meet the security requirements have the properties that we required for a digital signature. How does the verifier check the first MAC, computed using KS? What is the main (practical) problem with implementing arbitrated signatures?,Introduct
25、ion to Cryptography and Security Mechanisms 2005,18,True digital signatures,The vast majority of digital signature techniques do not involve having to communicate through a trusted arbitrator. A true digital signature is one that can be sent directly from the signer to the verifier. For the rest of
26、this unit when we say “digital signature” we mean “true digital signature”.,Introduction to Cryptography and Security Mechanisms 2005,19,A naive approach,Given the apparent symmetry of the requirements for public key encryption and digital signatures, propose a nave approach to designing a digital s
27、ignature scheme. State two reasons why the above approach is nave.,2. Hash functions,Introduction to Cryptography and Security Mechanisms 2005,21,Hash functions,Condenses arbitrary long inputs into a fixed length output You stuff as much data as you want into the function, and it churns out an outpu
28、t (or hash) that is always the same fixed length. In general this hash is much smaller than the data that was put into the function. Because the hash is a smaller thing that represents a larger thing, it sometimes referred to as a digest, and the hash function as a message digest function.,A hash fu
29、nction is a mathematical function that generally has the following three properties:,Introduction to Cryptography and Security Mechanisms 2005,22,Hash functions,Is one-way The hash function should be easy to compute, but given the hash of some data it should be very hard to recover the original data
30、 from the hash. It is hard to find two inputs with the same output It should be hard to find two different inputs (of any length) that when fed into the hash function result in the same hash (collision free). Note that it is impossible for a hash function not to have collisions. If arbitrarily large
31、 inputs are all being reduced to a fixed length hash then there will be lots of collisions. (For example - it is impossible to give each of 60 million people a different 4 digit PIN.) The point is that these collisions should be hard to find.,Introduction to Cryptography and Security Mechanisms 2005
32、,23,Hash functions?,Consider the following two mathematical functions and explain whether they satisfy each of the properties of a hash function or not:Multiplying two prime numbers together Reducing a number modulo n,Introduction to Cryptography and Security Mechanisms 2005,24,Practical hash functi
33、ons?,There are several hash functions in common use that are believed to be secure enough for general use. Can you name them?,Introduction to Cryptography and Security Mechanisms 2005,25,Hash functions and data integrity,A hash function provides a weak notion of data integrity. If we had a list of M
34、D5 hashes which contained information on all of our operating system files on our home computer you could verify the values of your files in the list and see which files have been changed or have been updated by say a virus. BUT If a virus replaced the system file it could also replace the MD5 value
35、s in your list with new ones and you would not be aware this had happened,Introduction to Cryptography and Security Mechanisms 2005,26,Hash function applications,Digital signatures with appendix: hash-functions are used to bind data together and make the signature process more efficient.Password sto
36、rage: hash-functions are sometimes used to store highly confidential data such as passwords.Cryptographic protocols: hash-functions are often used within cryptographic protocols (including entity authentication protocols) to bind different data items together.Hash-functions can be used as components
37、 from which to construct other cryptographic primitives .,Introduction to Cryptography and Security Mechanisms 2005,27,Is a MAC a hash function?,Have a fixed length output Rely on a symmetric key Provide data origin authentication (and data integrity) Typically constructed from block ciphers or hash
38、 functions,Is a MAC a hash function?,Introduction to Cryptography and Security Mechanisms 2005,28,HMAC,MAC = h( K | h( K | message ) ),3. Digital signature algorithms,Introduction to Cryptography and Security Mechanisms 2005,30,Some caveats,Although we only describe in detail how to implement digita
39、l signatures using RSA, there are many other examples of (true) digital signatures that are not based on RSA The RSA public key cipher system has some special properties that allow it to be used for both encryption and digital signatures not all public key cipher systems can be used to generate digi
40、tal signatures, and neither can all digital signature algorithms be used as public key cipher systems We will see two different methods of implementing true digital signatures using RSA these two techniques can also be used for some other digital signature algorithms The process described here is si
41、mplified please consult relevant standards before making an actual implementation,We will focus this section on describing digital signatures based on RSA. Please note:,Introduction to Cryptography and Security Mechanisms 2005,31,Motivating different types of signature,Suppose that you receive a dig
42、itally signed message that you are expected to be able to verify. Imagine that the message that is being signed is a random binary string. To verify it you apply a publicly known process that does not involve any secret parameters. Remember that an attacker could modify the signature on its way to y
43、ou, changing a few bits here and there. How are you going to know, just by performing a verification of the digital signature, what message the signature applies to and hence whether the signature is valid?,Introduction to Cryptography and Security Mechanisms 2005,32,Creating an RSA signature with a
44、ppendix,message,hash function,hash,Signature algorithm,signature,signature key,message,signature,1,2,3,Introduction to Cryptography and Security Mechanisms 2005,33,Hashing before signing,There are two reasons why a message is hashed before it is signed using RSA.What are they?,Introduction to Crypto
45、graphy and Security Mechanisms 2005,34,Verifying an RSA signature with appendix,message,signature,Verification algorithm,verification key,hash function,= ?,3,Decision,1,2,Introduction to Cryptography and Security Mechanisms 2005,35,RSA is special,You cannot obtain a digital signature scheme by swapp
46、ing the roles of the private and public keys of any public key cipher system,You cannot obtain a public key cipher system by swapping the roles of the signature and verification keys of any digital signature scheme,Optional Task! Express the operations involved in RSA signatures mathematically to ch
47、eck that the process of verifying an RSA signature with appendix does indeed work. Now identify the special property of RSA that allows it to be used as both an encryption and a signature algorithm.,Introduction to Cryptography and Security Mechanisms 2005,36,Key separation,In real applications you
48、should avoid using the same RSA key pair for both encryption and for digital signatures.,The reason is that good key management follows a principle known as key separation, where any cryptographic key has a specific role and is not used for different purposes. Thus, properly implemented versions of
49、RSA that are to be used for both encryption and digital signatures should issue each user with two key pairs:a public / private key pair for encryptiona verification / signature key pair for digital signatures These different key pairs should be carefully managed to ensure that they are only used for the designated purpose.,Introduction to Cryptography and Security Mechanisms 2005,37,RSA signatures with message recovery,add padding / redundancy,signature,signature key,verificationkey,message,Signature algorithm,remove padding / redundancy,
