PowerPoint Presentation
Digital Signature, Digital Certificates/SSL
&
Elliptic Curve
Lecture 5b
1
Overview
Asymmetric algorithms
Digital signatures
Digital certificate
What is a digital certificate?
Scenario of digital certificate
Types of digital certificates
PKI – Public Key Infrastructure and digital certificate
Trust
Certificate Authority
What is CA?
Intermediate CAs
Browsers and CAs
SSL/TLS protocol and SSL certificate
Digital envelope
Stored Data encryption
Elliptic curve
Fundamentals
Bitcoin key generation and ECC
Tor network and ECC
Applications of ECC
Asymmetric Encryption Algorithms
3
RSA One of the first public-key schemes was developed in 1977 by Ron Rivest, Adi
Shamir, and Len Adleman at MIT and first published in 1978 [RIVE78]. The RSA
scheme has since reigned supreme as the most widely accepted and implemented
approach to public-key encryption. RSA is a block cipher in which the plaintext and
ciphertext are integers between 0 and n – 1 for some n.
In 1977, the three inventors of RSA dared Scientific American readers to decode
a cipher they printed in Martin Gardner’s “Mathematical Games” column. They
offered a $100 reward for the return of a plaintext sentence, an event they predicted
might not occur for some 40 quadrillion years. In April of 1994, a group working over
the Internet and using over 1600 computers claimed the prize after only eight months
of work [LEUT94]. This challenge used a public-key size (length of n) of 129 decimal
digits, or around 428 bits. This result does not invalidate the use of RSA; it simply
means that larger key sizes must be used. Currently, a 1024-bit key size (about 300
decimal digits) is considered strong enough for virtually all applications.
DIFFIE-HELLMAN KEY AGREEMENT The first published public-key algorithm
appeared in the seminal paper by Diffie and Hellman that defined public-key
cryptography and is generally referred to as Diffie-Hellman key exchange,
or key agreement. A number of commercial products employ this key exchange
technique.
The purpose of the algorithm is to enable two users to securely reach agreement
about a shared secret that can be used as a secret key for subsequent symmetric
encryption of messages. The algorithm itself is limited to the exchange of the keys.
DIGITAL SIGNATURE STANDARD The National Institute of Standards and Technology
(NIST) has published Federal Information Processing Standard FIPS PUB 186,
known as the Digital Signature Standard (DSS). The DSS makes use of SHA-1
and presents a new digital signature technique, the Digital Signature Algorithm
(DSA). The DSS was originally proposed in
1991 and revised in 1993 in response to public feedback concerning the security of the
scheme. There were further revisions in 1998, 2000, 2009, and most recently in 2013.
The DSS uses an algorithm that is designed to provide only the digital
signature function. Unlike RSA, it cannot be used for encryption or key exchange.
ELLIPTIC CURVE CRYPTOGRAPHY The vast majority of the products and standards
that use public-key cryptography for encryption and digital signatures use RSA.
The bit length for secure RSA use has increased over recent years, and this has put
a heavier processing load on applications using RSA. This burden has ramifications,
especially for electronic commerce sites that conduct large numbers of secure
transactions. Recently, a competing system has begun to challenge RSA: elliptic
curve cryptography (ECC). Already, ECC is showing up in standardization efforts,
including the IEEE (Institute of Electrical and Electronics Engineers) P1363
Standard for Public-Key Cryptography.
The principal attraction of ECC compared to RSA is that it appears to offer
equal security for a far smaller bit size, thereby reducing processing overhead. On
the other hand, although the theory of ECC has been around for some time, it is
only recently that products have begun to appear and that there has been sustained
cryptanalytic interest in probing for weaknesses. Thus, the confidence level in ECC
is not yet as high as that in RSA.
RSA (Rivest, Shamir, Adleman)
Developed in 1977
Most widely accepted and implemented approach to public-key encryption
Block cipher in which the plaintext and ciphertext are integers between 0 and n-1 for some n.
Diffie-Hellman key exchange algorithm
Enables two users to securely reach agreement about a shared secret that can be used as a secret key for subsequent symmetric encryption of messages
Limited to the exchange of the keys
Digital Signature Standard (DSS)
Provides only a digital signature function with SHA-1
Cannot be used for encryption or key exchange
Elliptic curve cryptography (ECC)
Security like RSA, but with much smaller keys
Digital Signatures
NIST defines a digital signature as:
”The result of a cryptographic transformation of data that,
when properly implemented, provides a mechanism for
verifying origin authentication, data integrity and signatory non-repudiation.”
Thus, a digital signature is a data-dependent bit pattern, generated by an agent as a function of a file, message, or other form of data block
three digital signature algorithms:
Digital Signature Algorithm (DSA)
RSA Digital Signature Algorithm
Elliptic Curve Digital Signature Algorithm (ECDSA)
Public-key encryption can be used for authentication with a technique known as the
digital signature. NIST FIPS PUB 186-4 [Digital Signature Standard (DSS) , July 2013]
defines a digital signature as follows: The result of a cryptographic transformation
of data that, when properly implemented, provides a mechanism for verifying origin
authentication, data integrity and signatory non-repudiation.
Thus, a digital signature is a data-dependent bit pattern, generated by an agent
as a function of a file, message, or other form of data block. Another agent can access
the data block and its associated signature and verify (1) the data block has been
signed by the alleged signer, and (2) the data block has not been altered since the
signing. Further, the signer cannot repudiate the signature.
FIPS 186-4 specifies the use of one of three digital signature algorithms:
• Digital Signature Algorithm (DSA): The original NIST-approved algorithm,
which is based on the difficulty of computing discrete logarithms.
• RSA Digital Signature Algorithm: Based on the RSA public-key algorithm.
• Elliptic Curve Digital Signature Algorithm (ECDSA): Based on elliptic-curve
cryptography.
4
5
Figure 2.7 is a generic model of the process of making and using digital signatures.
All of the digital signature schemes have this structure. Suppose
Bob wants to send a message to Alice. Although it is not important that the message
be kept secret, he wants Alice to be certain that the message is indeed from him.
For this purpose, Bob uses a secure hash function, such as SHA-512, to generate a
hash value for the message. That hash value, together with Bob’s private key, serve
as input to a digital signature generation algorithm that produces a short block that
functions as a digital signature. Bob sends the message with the signature attached.
When Alice receives the message plus signature, she (1) calculates a hash value for
the message; (2) provides the hash value and Bob’s public key as inputs to a digital
signature verification algorithm. If the algorithm returns the result that the signature
is valid, Alice is assured that the message must have been signed by Bob. No one else
has Bob’s private key, and therefore no one else could have created a signature that
could be verified for this message with Bob’s public key. In addition, it is impossible to
alter the message without access to Bob’s private key, so the message is authenticated
both in terms of source and in terms of data integrity.
The digital signature does not provide confidentiality. That is, the message being
sent is safe from alteration, but not safe from eavesdropping. This is obvious in the
case of a signature based on a portion of the message, because the rest of the message
is transmitted in the clear. Even in the case of complete encryption, there is no
protection of confidentiality because any observer can decrypt the message by using
the sender’s public key.
Man-in-the-Middle Attack
Attack is:
Darth generates private keys XD1 and XD2, and their public keys YD1 and YD2
Alice transmits YA to Bob
Darth intercepts YA and transmits YD1 to Bob. Darth also calculates K2
Bob receives YD1 and calculates K1
Bob transmits XA to Alice
Darth intercepts XA and transmits YD2 to Alice. Darth calculates K1
Alice receives YD2 and calculates K2
All subsequent communications compromised
6
The protocol depicted in Figure 21.10 is insecure against a man-in-the-middle attack. Suppose Alice and Bob wish to exchange keys, and Darth is attacks as follows:
1. Darth generates two private keys XD1 and XD2, and public keys YD1 & YD2.
2. Alice transmits YA to Bob.
3. Darth intercepts YA and transmits YD1 to Bob. Darth also calculates K2
4. Bob receives YD1 and calculates K1.
5. Bob transmits XA to Alice.
6. Darth intercepts XA and transmits YD2 to Alice. Darth calculates .
7. Alice receives YD2 and calculates .
At this point, Bob and Alice think that they share a secret key, but instead Bob and Darth share secret key K1 and Alice and Darth share secret key K2. All future communication between Bob and Alice is compromised in the following way:
1. Alice sends an encrypted message M: E(K2, M).
2. Darth intercepts the encrypted message and decrypts it, to recover M.
3. Darth sends Bob E(K1, M) or E(K1, M’), where M’ is any message. In the first case, Darth simply wants to eavesdrop on the communication without altering it. In the second case, Darth wants to modify the message going to Bob.
The key exchange protocol is vulnerable to such an attack because it does not authenticate the participants. This vulnerability can be overcome with the use of digital signatures and public-key certificates.
Digital Certificate
A digital certificate is an electronic permit that allows a person, organization or a computer to exchange the information securely over the Internet by using the public key infrastructure (PKI).
Digital certificates help establish the identity of people or electronic assets.
They protect online transactions by providing secure, encrypted, online communication.
Digital Certificate
On the face of it, the point of public-key encryption is that the public key is public. Thus,
if there is some broadly accepted public-key algorithm, such as RSA, any participant
can send his or her public key to any other participant or broadcast the key to the community
at large. Although this approach is convenient, it has a major weakness. Anyone
can forge such a public announcement. That is, some user could pretend to be Bob and
send a public key to another participant or broadcast such a public key. Until such time
as Bob discovers the forgery and alerts other participants, the forger is able to read all
encrypted messages intended for Bob and can use the forged keys for authentication.
The solution to this problem is the public-key certificate. In essence, a certificate
consists of a public key plus a user ID of the key owner, with the whole block
signed by a trusted third party. The certificate also includes some information about
the third party plus an indication of the period of validity of the certificate. Typically,
the third party is a certificate authority (CA) that is trusted by the user community,
such as a government agency or a financial institution. A user can present his or her
public key to the authority in a secure manner and obtain a signed certificate. The
user can then publish the certificate. Anyone needing this user’s public key can obtain
the certificate and verify that it is valid by means of the attached trusted signature.
Figure 2.8 illustrates the process.
The key steps can be summarized as follows:
1. User software (client) creates a pair of keys: one public and one private.
2. Client prepares an unsigned certificate that includes the user ID and user’s
public key.
3. User provides the unsigned certificate to a CA in some secure manner. This might
require a face-to-face meeting, the use of registered e-mail, or happen via a Web
form with e-mail verification.
4. CA creates a signature as follows:
a. CA uses a hash function to calculate the hash code of the unsigned certificate.
A hash function is one that maps a variable-length data block or message
into a fixed-length value called a hash code, such as SHA family that
we will discuss in Sections 2.2 and 21.1.
b. CA generates digital signature using the CA’s private key and a signature
generation algorithm.
5. CA attaches the signature to the unsigned certificate to create a signed certificate.
6. CA returns the signed certificate to client.
7. Client may provide the signed certificate to any other user.
8. Any user may verify that the certificate is valid as follows:
a. User calculates the hash code of certificate (not including signature).
b. User verifies digital signature using CA’s public key and the signature verification
algorithm. The algorithm returns a result of either signature valid
or invalid.
One scheme has become universally accepted for formatting public-key
certificates: the X.509 standard. X.509 certificates are used in most network security
applications, including IP Security (IPsec), Transport Layer Security (TLS), Secure
Shell (SSH), and Secure/Multipurpose Internet Mail Extension (S/MIME). We will
examine most of these applications in Part Five.
8
Types of digital certificates
SSL certificates
Server Certificates : SSL certificate authenticates the server to web browsers
Organization Certificates : self-signed certificates
Codesigning certificates
Personal Certificates
Developer Certificates
“A Code Signing Certificate authenticates the identity of a software developer or publisher and provides assurance that the signed piece of software has not been altered or tampered with. This is done by applying a digital signature and hashing it along with the software itself.”
a user attempts to download a piece of unsigned software the browser or antivirus program they’re running will flag it
Public Key Infrastructure – PKI
Framework for managing digital certificates and public key encryption
Facility the secure electronic transfer of information over the Internet – transactions, sending/receiving personal details etc
Consists of policies and standards Ultimate goal is to build trust
Trust
Trust: Multi-facet complex concept
Trust: Confidence, Benevolence, Reliance
My research on trust – link
Frauds in e-commerce: Trust, Identify and Chargeback
etc
Interpersonal – direct trust between two
External – Third party trust
I trust John, you trust John
I trust you
CA
Certificate Authority
Certificate Authority or certification authority (CA) is an entity that issues digital certificate. A digital certificate certifies the ownership of a public key by the named subject of the certificate.
Ensure trust in e-commerce
Internal to organisation – self signed certificate
External – Verisgin and GlobalSign are most popular Cas
INTERMEDIATE CAs
Check certificate with Google connection
Self-certificate, issue to and issue by same
Certificate Path, to see root CA
Browsers – CA
Firefox: Tools > Options > Advanced > Certificates > View Certificates > Authorities.
SSL/TLS
SSL (Secure Sockets Layer) is a standard security technology for establishing an encrypted link between a server and a client
SSL allows sensitive information such as credit card numbers, social security numbers, and login credentials to be transmitted securely.
More specifically, SSL is a security protocol.
“SSL Certificates are small data files that digitally bind a cryptographic key to an organization’s details. When installed on a web server, it activates the padlock and the https protocol and allows secure connections from a web server to a browser” GlobalSign
18
Another application in which public-key encryption is used to protect a symmetric
key is the digital envelope, which can be used to protect a message without needing
to first arrange for sender and receiver to have the same secret key. The technique
is referred to as a digital envelope, which is the equivalent of a sealed envelope
containing an unsigned letter. The general approach is shown in Figure 2.9. Suppose
Bob wishes to send a confidential message to Alice, but they do not share a symmetric
secret key. Bob does the following:
1. Prepare a message.
2. Generate a random symmetric key that will be used this one time only.
3. Encrypt that message using symmetric encryption the one-time key.
4. Encrypt the one-time key using public-key encryption with Alice’s public key.
5. Attach the encrypted one-time key to the encrypted message and send it to
Alice.
Only Alice is capable of decrypting the one-time key and therefore of recovering
the original message. If Bob obtained Alice’s public key by means of Alice’s
public-key certificate, then Bob is assured that it is a valid key.
Practical Application:
Encryption of Stored Data
19
One of the principal security requirements of a computer system is the protection
of stored data. Security mechanisms to provide such protection include access control,
intrusion detection, and intrusion prevention schemes.
• In December of 2004, Bank of America employees backed up and sent to its
backup data center tapes containing the names, addresses, bank account numbers,
and Social Security numbers of 1.2 million government workers enrolled
in a charge-card account. None of the data were encrypted. The tapes never
arrived and indeed have never been found. Sadly, this method of backing up
and shipping data is all too common. As an another example, in April of 2005,
Ameritrade blamed its shipping vendor for losing a backup tape containing
unencrypted information on 200,000 clients.
• In April of 2005, San Jose Medical group announced that someone had physically
stolen one of its computers and potentially gained access to 185,000
unencrypted patient records.
• There have been countless examples of laptops lost at airports, stolen from a
parked car, or taken while the user is away from his or her desk. If the data on the
laptop’s hard drive are unencrypted, all of the data are available to the thief.
Although it is now routine for businesses to provide a variety of protections,
including encryption, for information that is transmitted across networks, via the
Internet, or via wireless devices, once data are stored locally (referred to as data at
rest), there is often little protection beyond domain authentication and operating
system access controls. Data at rest are often routinely backed up to secondary storage
such as CDROM or tape, archived for indefinite periods. Further, even when
data are erased from a hard disk, until the relevant disk sectors are reused, the data
are recoverable. Thus it becomes attractive, and indeed should be mandatory, to
encrypt data at rest and combine this with an effective encryption key management
scheme.
There are a variety of ways to provide encryption services. A simple approach
available for use on a laptop is to use a commercially available encryption package
such as Pretty Good Privacy (PGP). PGP enables a user to generate a key from a
password and then use that key to encrypt selected files on the hard disk. The PGP
package does not store the password. To recover a file, the user enters the password,
PGP generates the password, and PGP decrypts the file. So long as the user protects
his or her password and does not use an easily guessable password, the files are fully
protected while at rest. Some more recent approaches are listed:
• Back-end appliance: This is a hardware device that sits between servers and
storage systems and encrypts all data going from the server to the storage system
and decrypts data going in the opposite direction. These devices encrypt
data at close to wire speed, with very little latency. In contrast, encryption
software on servers and storage systems slows backups. A system man ager
configures the appliance to accept requests from specified clients, for which
unencrypted data are supplied.
• Library-based tape encryption: This is provided by means of a co-processor board
embedded in the tape drive and tape library hardware. The co-processor encrypts
data using a nonreadable key configured into the board. The tapes can then be sent
off-site to a facility that has the same tape drive hardware. The key can be exported
via secure e-mail or a small flash drive that is transported securely. If the matching
tape drive hardware co-processor is not available at the other site, the target facility
can use the key in a software decryption package to recover the data.
• Background laptop and PC data encryption: A number of vendors offer software
products that provide encryption that is transparent to the application and
the user. Some products encrypt all or designated files and folders. Other
products, such as Windows BitLocker and MacOS FileVault, encrypt an entire
disk or disk image located on either the user’s hard drive or maintained on a
network storage device, with all data on the virtual disk encrypted. Various key
management solutions are offered to restrict access to the owner of the data.
Common to encrypt transmitted data
Much less common for stored data
Data are archived for indefinite periods
Approaches to encrypt stored data:
Back-end appliance
Library based tape encryption
Background laptop/PC data encryption
Use a commercially available encryption package
There is often little protection beyond domain authentication and operating system access controls
Even though erased, until disk sectors are reused data are recoverable
Elliptic Curve
Proposed in 1985 by Neal Koblitz and Victor Miller
Public key cryptography just like RSA
User has two pairs of keys
Discrete logarithm on elliptic curve is more difficult
y = mod p
Challenge : Given y, g and p (g and p very large)
it is not VERY EASY(impossible) to calculate x.
All public-key cryptosystems have some underlying mathematical operation.
– RSA has exponentiation (raising the message or ciphertext to the public or private values)
– ECC has point multiplication (repeated addition of two points).
ELLIPTIC Curve
Consider elliptic curve
E : y 2 = x3 – x + 1
• If P1 and P2 are on E,
we can define R = P1 + P2 as shown in picture
• Addition is all we need
Modulo arithmetic: cycle of numbers around, in ECC it use points
mod n was used in DH which used exponentiation
In ECC it is simply add a point to the, suppose g is our initial point, further points will be 2G, 3G, 4G….. These will be points somewhere on the curve
?G how many multiple points of g is this point
impossible to extract that information – private number
Elliptic curve
Tor
25
Applications
Wireless communication devices
– Smart cards
– Web servers that need to handle many encryption sessions
– Any application where security is needed but lacks the power, storage and computational power that is necessary for our current cryptosystems
https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
Figure 2.7 Simplified Depiction of Essential
Elements of Digital Signature Process
Bob Alice
Cryptographic
hash
function
h
Cryptographic
hash
function
hBob’s
private
key
Digital
signature
generation
algorithm
Bob’s
signature
for M
(a) Bob signs a message (b) Alice verifies the signature
Bob’s
public
key
Digital
signature
verification
algorithm
Return
signature valid
or not valid
Message M S Message M
S Message M
Figure 2.7 Simplified Depiction of Essential
Elements of Digital Signature Process
Bob Alice
Cryptographic
hash
function
h
Cryptographic
hash
function
h
Bob’s
private
key
Digital
signature
generation
algorithm
Bob’s
signature
for M
(a) Bob signs a message (b) Alice verifies the signature
Bob’s
public
key
Digital
signature
verification
algorithm
Return
signature valid
or not valid
Message M S Message M
S Message M
Unsigned certificate:
contains user ID,
user’s public key,
as well as information
concerning the CA
Signed certificate
Figure 2.8 Public-Key Certificate Use
Generate hash
code of unsigned
certificate
Generate hash code
of certificate not
including signature
Generate digital signature
using CA’s private key
H
H
Bob’s ID
information
CA
information
Bob’s public key
SG SV
Verify digital signature
using CA’s public key
Return signature
valid or not valid
Use certificate to
verify Bob’s public key
Create signed
digital certificate
Unsigned certificate:
contains user ID,
user’s public key,
as well as information
concerning the CA
Signed certificate
Figure 2.8 Public-Key Certificate Use
Generate hash
code of unsigned
certificate
Generate hash code
of certificate not
including signature
Generate digital signature
using CA’s private key
H
H
Bob’s ID
information
CA
information
Bob’s public key
SG SV
Verify digital signature
using CA’s public key
Return signature
valid or not valid
Use certificate to
verify Bob’s public key
Create signed
digital certificate
Random
symmetric
key
Receiver’s
public
key
Encrypted
symmetric
key
Encrypted
message
Encrypted
message
Digital
envelope
Figure 2.9 Digital Envelopes
(a) Creation of a digital envelope
E
E
Message
Random
symmetric
key
Receiver’s
private
key
Encrypted
symmetric
key
(b) Opening a digital envelope
D
D
Digital
envelope
Message
Random
symmetric
key
Receiver’s
public
key
Encrypted
symmetric
key
Encrypted
message
Encrypted
message
Digital
envelope
Figure 2.9 Digital Envelopes
(a) Creation of a digital envelope
E
E
Message
Random
symmetric
key
Receiver’s
private
key
Encrypted
symmetric
key
(b) Opening a digital envelope
D
D
Digital
envelope
Message