CRYPTOGRAPHY

Developed and Presented By Dr. Mehrdad Sepehri SharbafCSUDHComputer Science Department

http://csc.csudh.edu/

The some of the materials are excerpted from Firouz Forouzan’s Book, and Jorge Ramió Aguirre’s Book

CRYPTOGRAPHY

Initial branch of Mathematics and currently of Computer Science and Telematics, which makes use of methods and technics with the main purpose of encrypting and/or protecting a message or file through an algorithm, using one or more keys. This gives rise to different types of cipher systems, denominated cryptosystems, that let us to assure any of these four aspects of information security: confidentiality or secret, integrity, availability and non repudiation of sender and receiver.

CRYPTOGRAPHY

Cryptography, a word with Greek origins, means “secret writing.” However, we use the term to refer to the science and art of transforming messages to make them secure and immune to attacks.

Cryptanalysis: the art and science of decrypting messages.

Cryptology: cryptography + cryptanalysis

CRYPTOGRAPHIC STRENGTH

DEFINITIONS

ATTACKS

The three goals of security¾confidentiality, integrity, and availability¾can be threatened by security attacks.

Taxonomy of attacks with relation to security goals

ATTACKS THREATENING CONFIDENTIALITY

Snooping refers to unauthorized access to or interception of data.

Traffic analysis refers to obtaining some other type of information by monitoring online traffic.

e.g. IP spoofing: send packet with false source address

A

B

C

src:B dest:A payload

ATTACKS THREATENING INTEGRITY

A

B

C

src:B dest:A user: B; password: foo

Masquerading or spoofing happens when the attacker impersonates somebody else.

Replaying means the attacker obtains a copy of a message sent by a user and later tries to replay it.

ATTACKS THREATENING INTEGRITY

A

B

later …..

C

src:B dest:A user: B; password: foo

Masquerading or spoofing happens when the attacker impersonates somebody else.

Replaying means the attacker obtains a copy of a message sent by a user and later tries to replay it.

ATTACKS THREATENING INTEGRITY

Repudiation means that sender of the message might later deny that she has sent the message; the receiver of the message might later deny that he has received the message.

Modification means that the attacker intercepts the message and changes it.

ATTACKS THREATENING AVAILABILITY

Denial of service (DoS) is a very common attack. It may slow down or totally interrupt the service of a system.

• attackers make resources (server, bandwidth) unavailable to legitimate traffic by overwhelming resource with bogus traffic

target

PASSIVE VERSUS ACTIVE ATTACKS

Categorization of passive and active attacks

• a passive attack, the attacker’s goal is just to obtain information. The attack does not modify data or harm the system, and the system continues with its normal operation.
• active attack may change the data or harm the system.

SERVICES AND MECHANISMS

SECURITY SERVICES

Data confidentiality protects data from disclosure attack.

Data integrity protect data from modification, insertion, deletion, and replaying attacks.

Authentication provides proof of sender, or receiver, or source of the data.

Nonrepudiation protects against repudiation by either the sender to the reveiver.

Access control provides protection again unauthorized access to data.

SECURITY MECHANISM

Appends to data a short check value

Hiding or covering data

Sender signs data, receiver verifies data

Two entities exchange msg to prove their identity to each other

Insert bogus data into the data traffic to thwart traffic analysis

Continuously change routes b/w sender and receiver to prevent eavesddropping

A third trusted party controls communication

Prove and verify that a user has access right to resources

Security mechanisms

Relation between Services and Mechanisms

Relation between security services and mechanisms

TECHNIQUES

Mechanisms discussed in the previous sections are only theoretical recipes to implement security. The actual implementation of security goals needs some techniques. Two techniques are prevalent today: cryptography and steganography.

Cryptography Steganography

STEGANOGRAPHY

STEGANOGRAPHY

STEGANOGRAPHY

The image in which we want to hide another image

The image extracted from the stego-image

The image we wish to hide: ‘F15’

The stego-image (i.e., after the hiding process)

STEGANOGRAPHY

CONFIDENTIALITY AND INTEGRITY

Cryptosystem

Transmission

Sender

Media

Receiver

M

C

Cipher

Encrypted message

Decrypter

T

R

TM

C

M

Identity usurpation

by an intruder (I)

Message intercepting

by an intruder (I)

Every transmision method is unsafe

Integrity

Confidentiality

These two basic aspects of information security, confidentiality and integrity, (besides system disponibility and non repudiation) will be very important in an environment of a safe information exchange through Internet.

TYPE OF CRYPTOSYSTEMS

Classification of Cryptosystems

According to the treatment of the message they are:

Block cipher (IDEA, AES, RSA* ...) 64-128 bits

Stream cipher (A5, RC4, SEAL ...) encryption bit by bit

According the type of keys they can be:

Secret key cipher

Public key cipher

Symmetric Systems

Asymmetric Systems

(*) As we'll see in another chapter, actually systems like RSA do not encrypt by blocks: they encrypt a single number.

SYMMETRIC & ASYMMETRIC CRYPTOSYSTEMS

Symmetric Cryptosystems :

There will be a unique key (secret) that sender and receiver must share. Same key is used to encrypt and decrypt so the security just resides in maintaining the secret of the key.

Asymmetric Cryptosystems :

Every user creates a pair of keys, one private and other public, inverses of a finite field. What is encrypted in transmission with a key, is decrypted when receiving with the inverse key. The system security resides in the computing difficulty of discovering the private key through the public. For that, they use mathematical one-way functions.

Symmetric Key

The original message from Alice to Bob is called plaintext; the message that is sent through the channel is called the ciphertext. To create the ciphertext from the plaintext, Alice uses an encryption algorithm and a shared secret key. To create the plaintext from ciphertext, Bob uses a decryption algorithm and the same secret key.

General idea of symmetric-key cipher

Encryption Algorithm

If P is the plaintext, C is the ciphertext, and K is the key,

We assume that Bob creates P1; we prove that P1 = P:

Encryption Algorithm

Locking and unlocking with the same key

KERCKHOFF’S PRINCIPLE

CRYPTANALYSIS

CIPHERTEXT-ONLY ATTACK

Ciphertext + algorithm  key and the plaintext

• Brute-Force attack: exhaustive key search attack
• Statistical attack: benefit from inherent characteristics of the plaintext language. E.g. E is the most frequently used letter.
• Pattern attack: discover pattern in ciphertext.

KNOWN-PLAINTEXT ATTACK

Eve has access to some plaintext/ciphertext pairs in addition to the intercepted ciphertext.

Eve uses the relationship b/w the previous pair to analyze the current ciphertext.

CHOSEN-PLAINTEXT ATTACK

The plaintext/ciphertext pairs have been chosen by the attacker herself.

CHOSEN-CIPHERTEXT ATTACK

Eve chooses some ciphertext and decrypts to form a ciphertext/plaintext pair. This can happen if Eve has access to Bob’s computer.

SIMPLE IDEA: ONE-TIME PAD

• ----

Key is a never-repeating bit

sequence as long as plaintext

Encrypt by bitwise XOR of

plaintext and key:

ciphertext = plaintext  key

Decrypt by bitwise XOR of

ciphertext and key:

ciphertext  key =

(plaintext  key)  key =

plaintext  (key  key) =

plaintext

Cipher achieves perfect secrecy if and only if

there are as many possible keys as possible plaintexts, and

every key is equally likely (Claude Shannon’s result)

= 10111101…

• ----
• ----
• ----

= 00110010…

10001111…



00110010…



10111101…

ADVANTAGES OF ONE-TIME PAD

PROBLEMS WITH ONE-TIME PAD

SYMMETRIC CRYPTOSYSTEMS

Encryption with secret key cryptosystems

Transmission

k

Media

k

M

C

Plain

Plain

Text

Cryptogram

Text

EK

TM

DK

M

C

protected

Integrity

C’ not allowed

Intruder

EK

Confidentiality

protected

M not allowed

DK

Confidentiality and integrity will be reached if the keys are protected in the encryption and decryption. This is, they are simultaneously obtained if the secret key is protected.

DES, TDES, IDEA, CAST, AES...

STREAM AND BLOCK CIPHERS

The literature divides the symmetric ciphers into two broad categories: stream ciphers and block ciphers. Although the definitions are normally applied to modern ciphers, this categorization also applies to traditional ciphers.

Stream CiphersBlock Ciphers

Combination

SYMMETRIC KEY CRYPTOSYSTEMS

SYMMETRIC KEY CRYPTOSYSTEMS

SYMMETRIC KEY CRYPTOSYSTEMS

SYMMETRIC KEY CRYPTOSYSTEMS

STREAM CIPHERS

Call the plaintext stream P, the ciphertext stream C, and the key stream K.

Stream cipher

STREAM CIPHERS

Additive ciphers can be categorized as stream ciphers in which the key stream is the repeated value of the key. In other words, the key stream is considered as a predetermined stream of keys or K = (k, k, …, k). In this cipher, however, each character in the ciphertext depends only on the corresponding character in the plaintext, because the key stream is generated independently.

Example

The monoalphabetic substitution ciphers discussed in this chapter are also stream ciphers. However, each value of the key stream in this case is the mapping of the current plaintext character to the corresponding ciphertext character in the mapping table.

Example

STREAM CIPHERS

Vigenere ciphers are also stream ciphers according to the definition. In this case, the key stream is a repetition of m values, where m is the size of the keyword. In other words,

Example

We can establish a criterion to divide stream ciphers based on their key streams. We can say that a stream cipher is a monoalphabetic cipher if the value of ki does not depend on the position of the plaintext character in the plaintext stream; otherwise, the cipher is polyalphabetic.

Example

STREAM CIPHERS

• Additive ciphers are definitely monoalphabetic because ki in the key stream is fixed; it does not depend on the position of the character in the plaintext.

• Monoalphabetic substitution ciphers are monoalphabetic because ki does not depend on the position of the corresponding character in the plaintext stream; it depends only on the value of the plaintext character.

• Vigenere ciphers are polyalphabetic ciphers because ki definitely depends on the position of the plaintext character. However, the dependency is cyclic. The key is the same for two characters m positions apart.

Example

BLOCK CIPHERS

In a block cipher, a group of plaintext symbols of size m (m > 1) are encrypted together creating a group of ciphertext of the same size. A single key is used to encrypt the whole block even if the key is made of multiple values. Figure 3.27 shows the concept of a block cipher.

Block cipher

ASYMMETRIC CRYPTOSYSTEMS

Receiver Public Key Cipher

RSA Keys exchange

Intruder

Transmision

Public key

From user B

Media

M

C

User A

Cryptogram

EB

TM

DB

M

C

Private key

From user B

User B

protected

Confidentiality

M not allowed

DB

Notice that the encryption is trough the public key of receiver.

Encryptions EB and DB (keys) are inverses of a field

A similar system is Diffie & Hellman (DH) key agreement

ASYMMETRIC CRYPTOSYSTEMS

Encryption with private key of sender

Digital signature RSA

Intruder

Cryptogram

C

Transmission

Private key

of user A

Media

M

User A

DA

TM

EA

M

C

Public key

of user A

User B

DA

protected

Integrity

C’ not allowed

Notice that the encryption is made thru private key of sender.

The encryption is made upon a hash H(M) of the message, for example MD5 or SHA-1

Signatures: RSA and DSS

Signature DSS is based in ElGamal cipher algorithm

Encryptions DA and EA (keys) are inverses of a field

TYPES OF CIPHER WITH ASYMMETRIC SYSTEMS

Public key Cryptosystems

Integrity

confidentiality

Confidentiality and integrity are obtained separately

Digital

signature

Encrypted Information

Authentication

of user A;

integrity of M

EB

DB

DA

M

EA

M

User B

11. private
12. f A
13. public
14. f A

11. public
12. f B
13. private
14. f B

DA

DB

C

User A

SYMMETRIC OR ASYMMETRIC CIPHER?

Public key systems are very slow but they have digital signature.

Secret key systems are very fast but they do not have digital signature.

Information encryption:

- We´ll use secret key systems

Signature and session key exchange:

- We´ll use public key systems

What should we do?

HYBRID SYSTEM OF CIPHER AND SIGNATURE

Digital

signature

• ver
• M)

Symmetric cipher

Session key k exchange using

EB(k) in transmission and DB(k) in reception

Authentication

of the user and

integrity

k

k

M

EA

M

User A

11. private
12. f A

User B

11. public
12. f A

Asymmetric cipher

k secret

k

DA

k

C

k secret

COMPARATIVE: SENDER'S AUTHENTICATION

Regarding authentication, symmetric systems have a heavier authentication and with only a third part of trust. Asymmetric ones allow a real digital signature, efficient and simple, where the third part of trust is just presential.

COMPARATIVE: CIPHER SPEED

Regarding cipher speed, symmetric systems are from 100 to 1.000 times faster than asymmetrics. In SW cipher speed is lower.

Hundreds of

M Bytes/seg

in HW

Hundreds of

K Bytes/seg

in HW

Symmetric Cipher

Asymmetric Cipher

Summary symmetric cipher v/s asymmetric

BLOCK CIPHER OPERATION (SIMPLIFIED)

S

S

S

S

Add some secret key bits

to provide confusion

Each S-box permutes

its input bits in a

“random-looking” way

to provide diffusion

(spread plaintext bits

throughout ciphertext)

Block of ciphertext

Procedure must be reversible

(for decryption)

Block of plaintext

S

S

S

S

S

S

S

S

Key

repeat for several rounds

DESIGN PRINCIPLES

DATA ENCRYPTION STANDARDS

DES OVERVIEW

AES STRUCTURE

DIGITAL SIGNATURES

MESSAGE DIGESTS

PICKING A CODE

PGP

WEB OF TRUST

PUBLIC KEY INFRASTRUCTURE