### Present Remotely

Send the link below via email or IM

CopyPresent to your audience

Start remote presentation- Invited audience members
**will follow you**as you navigate and present - People invited to a presentation
**do not need a Prezi account** - This link expires
**10 minutes**after you close the presentation - A maximum of
**30 users**can follow your presentation - Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

### Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.

You can change this under Settings & Account at any time.

# Data Security & Cryptography

No description

by

Tweet## Prathyusha Mandadapu

on 2 April 2013#### Transcript of Data Security & Cryptography

Outline Security Requirements in DS

Designing Secure Systems

Threats

Attacks

Infiltration

Cryptography

Access Control

Authentication

Authorization

Questions Secure against Eavesdropping

Servers should verify the identity of their Clients

Clients should verify the authenticity of Servers

Use of Digital Signatures Security Policies - Ensure appropriate levels of security for the

activities that are performed

Security Mechanisms - Helps to implement the security policies Designing Secure Systems Leakage - The acquisition of information by unauthorized recipients

Tampering - The unauthorized alteration of information

Resource Stealing - The use of facilities without authorization

Vandalism - The interference with the proper operation of a system

without gain to the perpetrator Threats Methods of Attack Eavesdropping - Obtaining copies of messages without authority

Masquerading - Assuming the identity of another user

Message Tampering - Altering the content of messages in transit

Replaying - Storing secure messages and sending them at a later date Infiltration Virus - Malicious software programs, a form of malware

Worm - Malicious software applications designed to spread

via computer networks

Trojan Horse - Network software application designed to

remain hidden on an installed computer Techniques in Security Mechanisms

for Distributed Systems Cryptography

Access Control

Authentication

Authorization Secrecy Scenario: Alice wants to send a message (plain text p) to Bob. The communication channel is insecure and can be eavesdropped by Trudy. If Alice and Bob have previously agreed on an encryption scheme (cipher), the message can be sent encrypted (cipher text c) Issues:

What is a good cipher?

What is the complexity of encrypting/decrypting?

What is the size of the cipher text, relative to the plain text?

If Alice and Bob have never interacted before, how can they agree on a cipher? Cryptography Secrecy

Ciphers

Computer Encryption Techniques

Key Exchange

Digital Signatures Traditional Cryptography Ciphers were already studied in ancient times

Caesar’s cipher:

replace a with d

replace b with e

...

replace z with c

A more general mono alphabetic substitution cipher maps each letter to some other letter. Breaking Traditional Cryptography Armed with simple statistical knowledge, Trudy can easily break a monalphabetic substitution cypher

most frequent letters in English: e, t, o, a, n, i, ...

most frequent diagrams: th, in, er, re, an, ...

most frequent trigrams: the, ing, and, ion, ...

Example Ciphertext

PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL, QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: 'DJOXL EYPD, ICJ X LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU?'OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK

Any Guesses??? Frequency Analysis Identifying common letters, digrams and trigrams...

PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL, QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: 'DJOXL EYPD, X LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU? OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK

First guess: LBO is THE Frequency Analysis Assuming LBO represents THE we replace L with T, B with H, and O with E and get

PCQ VMJYPD THYK TYSE KHXHJXWXV HXV ZCJPE EYPD KHXHJYUXJ THJEE KCPK. CP THE THCMKXPV XPV IYJKT PYDHT, QHEP KHO HXV EPVEV THE LXRE CI SX'XJMI, KHE JCKE XPV EYKKOV THE DJCMPV ZEICJE HYS, KXUYPD: 'DJEXT EYPD, ICJ X LHCMKXPV XPV CPE PYDHLK Y HXNE ZEEP JEACMPTYPD TC UCM THE IXZREK CI FXKL XDEK XPV THE REDEPVK CI XPAYEPT EYPDK. SXU Y SXEE KC ZCRV XK TC AJXNE X IXNCMJ CI UCMJ SXGEKTU?'EFYRCDME, TXREK IJCS THE LHCMKXPV XPV CPE PYDBTK

More guesses…? The Solution

Code

X Z A V O I D B Y G E R S P C F H J K L M N Q T U W

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Plain text Now during this time Shahrazad had borne King Shahriyar three sons. On the thousand and first night, when she had ended the tale of Ma'aruf, she rose and kissed the ground before him, saying: 'Great King, for a thousand and one nights I have been recounting to you the fables of past ages and the legends of ancient kings. May I make so bold as to crave a favour of your majesty?’ Epilogue, Tales from the Thousand and One Nights Security Attributes (CIA) Confidentiality - prevent unauthorized reading of information

Integrity - prevent unauthorized writing of information

Availability - Data is available in a timely manner when needed Other Traditional Cryptography Techniques Double transposition

Caesar's Cipher

One Time Pad

Codebook Symmetric Key Crypto Stream cipher

Key is relatively short

Key is stretched into a long keystream

Block cipher

Block cipher key determines a concept called code book

Each key yields a different code book

Employ both “confusion” and “diffusion” Claude Shannon The founder of Information Theory

Confusion and Diffusion

Confusion - Obscure relationship between plaintext and ciphertext

Diffusion - Spread plaintext statistics throughthe ciphertext Block Ciphers Data Encryption Standard DES developed in 1970’s

Based on IBM Lucifer cipher

U.S. government standard

DES development was controversial

NSA was secretly involved

Design process not open

Key length was reduced

Subtle changes to Lucifer algorithm DES Numerology DES

64 bit block length

56 bit key length

16 rounds

48 bits of key used each round (sub key)

Each round is simple (for a block cipher)

Security depends primarily on “S-boxes”

Each S-boxes maps 6 bits to 4 bits Security of DES Security of DES depends a lot on S-boxes

Everything else in DES is linear

Thirty years of intense analysis has revealed no “back door”

Attacks today use exhaustive key search

Block Cipher Notation P = plaintext block

C = ciphertext block

Encrypt P with key K to get ciphertext C

C = E(P, K)

Decrypt C with key K to get plaintext P

P = D(C, K)

Note that

P = D(E(P, K), K) and C = E(D(C, K), K) Public Key Crptography Plain text and Cipher text consists of fixed sized blocks

Ciphertext obtained from plaintext by iterating a round function

Input to round function consists of key and the output of previous round

Usually implemented in software Two keys

Sender uses recipient’s public key to encrypt

Receiver uses his private key to decrypt

Based on trap door, one way function

Easy to compute in one direction

Hard to compute in other direction

“Trap door” used to create keys – public info does not help to recover the private info (key)

Example: Given p and q, product N=pq is easy to compute, but given N, it is hard to find p and q Public Key Cryptography Contd. Encryption

Suppose we encrypt M with Bob’s public key

Only Bob’s private key can decrypt to find M

Digital Signature

Sign by “encrypting” with private key

Anyone can verify signature by “decrypting”

with public key

But only private key holder could have signed

RSA Invented by Cocks (GCHQ), independently,

by Rivest, Shamir and Adleman (MIT)

Let p and q be two large prime numbers

Let N = pq be the modulus

Choose e relatively prime to (p-1)(q-1)

Find d s.t. ed = 1 mod (p-1)(q-1)

Public key is (N,e)

Private key is d RSA Contd. To encrypt message M compute

C = M^e mod N

To decrypt C compute

M = C^d mod N

Recall that e and N are public

If attacker can factor N, he can use e to easily find d since ed = 1 mod (p-1)(q-1)

Factoring the modulus breaks RSA Simple RSA Example Example of RSA

Select “large” primes p = 11, q = 3

Then N = pq = 33 and (p-1)(q-1) = 20

Choose e = 3 (relatively prime to 20)

Find d such that ed = 1 mod 20, we find that d = 7 works

Public key: (N, e) = (33, 3)

Private key: d = 7 Simple RSA Example Public key: (N, e) = (33, 3)

Private key: d = 7

Suppose message M = 8

Ciphertext C is computed as

C = M^e mod N = 8 ^3 = 512 = 17 mod 33

Decrypt C to recover the message M by

M = C^d mod N = 17^7 = 410,338,673 =

12,434,505 * 33 + 8 = 8 mod 33 Contd. Security Requirements in Distributed Systems Diffie - Hellman Invented by Williamson (GCHQ) and, independently, by D and H (Stanford)

A “key exchange” algorithm

Used to establish a shared symmetric key

Not for encrypting or signing

Security rests on difficulty of discrete log

problem: given g, p, and g^k mod p find k 6/48 7/48 8/48 9/48 10/48 11/48 12/48 13/48 14/48 15/48 16/48 17/48 18/48 19/48 20/48 21/48 22/48 23/48 24/48 25/48 26/48 27/48 28/48 29/48 30/48 31/48 32/48 34/48 35/48 36/48 37/48 38/48 39/48 40/48 41/48 42/48 43/48 44/48

Full transcriptDesigning Secure Systems

Threats

Attacks

Infiltration

Cryptography

Access Control

Authentication

Authorization

Questions Secure against Eavesdropping

Servers should verify the identity of their Clients

Clients should verify the authenticity of Servers

Use of Digital Signatures Security Policies - Ensure appropriate levels of security for the

activities that are performed

Security Mechanisms - Helps to implement the security policies Designing Secure Systems Leakage - The acquisition of information by unauthorized recipients

Tampering - The unauthorized alteration of information

Resource Stealing - The use of facilities without authorization

Vandalism - The interference with the proper operation of a system

without gain to the perpetrator Threats Methods of Attack Eavesdropping - Obtaining copies of messages without authority

Masquerading - Assuming the identity of another user

Message Tampering - Altering the content of messages in transit

Replaying - Storing secure messages and sending them at a later date Infiltration Virus - Malicious software programs, a form of malware

Worm - Malicious software applications designed to spread

via computer networks

Trojan Horse - Network software application designed to

remain hidden on an installed computer Techniques in Security Mechanisms

for Distributed Systems Cryptography

Access Control

Authentication

Authorization Secrecy Scenario: Alice wants to send a message (plain text p) to Bob. The communication channel is insecure and can be eavesdropped by Trudy. If Alice and Bob have previously agreed on an encryption scheme (cipher), the message can be sent encrypted (cipher text c) Issues:

What is a good cipher?

What is the complexity of encrypting/decrypting?

What is the size of the cipher text, relative to the plain text?

If Alice and Bob have never interacted before, how can they agree on a cipher? Cryptography Secrecy

Ciphers

Computer Encryption Techniques

Key Exchange

Digital Signatures Traditional Cryptography Ciphers were already studied in ancient times

Caesar’s cipher:

replace a with d

replace b with e

...

replace z with c

A more general mono alphabetic substitution cipher maps each letter to some other letter. Breaking Traditional Cryptography Armed with simple statistical knowledge, Trudy can easily break a monalphabetic substitution cypher

most frequent letters in English: e, t, o, a, n, i, ...

most frequent diagrams: th, in, er, re, an, ...

most frequent trigrams: the, ing, and, ion, ...

Example Ciphertext

PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL, QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: 'DJOXL EYPD, ICJ X LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU?'OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK

Any Guesses??? Frequency Analysis Identifying common letters, digrams and trigrams...

PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL, QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: 'DJOXL EYPD, X LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU? OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK

First guess: LBO is THE Frequency Analysis Assuming LBO represents THE we replace L with T, B with H, and O with E and get

PCQ VMJYPD THYK TYSE KHXHJXWXV HXV ZCJPE EYPD KHXHJYUXJ THJEE KCPK. CP THE THCMKXPV XPV IYJKT PYDHT, QHEP KHO HXV EPVEV THE LXRE CI SX'XJMI, KHE JCKE XPV EYKKOV THE DJCMPV ZEICJE HYS, KXUYPD: 'DJEXT EYPD, ICJ X LHCMKXPV XPV CPE PYDHLK Y HXNE ZEEP JEACMPTYPD TC UCM THE IXZREK CI FXKL XDEK XPV THE REDEPVK CI XPAYEPT EYPDK. SXU Y SXEE KC ZCRV XK TC AJXNE X IXNCMJ CI UCMJ SXGEKTU?'EFYRCDME, TXREK IJCS THE LHCMKXPV XPV CPE PYDBTK

More guesses…? The Solution

Code

X Z A V O I D B Y G E R S P C F H J K L M N Q T U W

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Plain text Now during this time Shahrazad had borne King Shahriyar three sons. On the thousand and first night, when she had ended the tale of Ma'aruf, she rose and kissed the ground before him, saying: 'Great King, for a thousand and one nights I have been recounting to you the fables of past ages and the legends of ancient kings. May I make so bold as to crave a favour of your majesty?’ Epilogue, Tales from the Thousand and One Nights Security Attributes (CIA) Confidentiality - prevent unauthorized reading of information

Integrity - prevent unauthorized writing of information

Availability - Data is available in a timely manner when needed Other Traditional Cryptography Techniques Double transposition

Caesar's Cipher

One Time Pad

Codebook Symmetric Key Crypto Stream cipher

Key is relatively short

Key is stretched into a long keystream

Block cipher

Block cipher key determines a concept called code book

Each key yields a different code book

Employ both “confusion” and “diffusion” Claude Shannon The founder of Information Theory

Confusion and Diffusion

Confusion - Obscure relationship between plaintext and ciphertext

Diffusion - Spread plaintext statistics throughthe ciphertext Block Ciphers Data Encryption Standard DES developed in 1970’s

Based on IBM Lucifer cipher

U.S. government standard

DES development was controversial

NSA was secretly involved

Design process not open

Key length was reduced

Subtle changes to Lucifer algorithm DES Numerology DES

64 bit block length

56 bit key length

16 rounds

48 bits of key used each round (sub key)

Each round is simple (for a block cipher)

Security depends primarily on “S-boxes”

Each S-boxes maps 6 bits to 4 bits Security of DES Security of DES depends a lot on S-boxes

Everything else in DES is linear

Thirty years of intense analysis has revealed no “back door”

Attacks today use exhaustive key search

Block Cipher Notation P = plaintext block

C = ciphertext block

Encrypt P with key K to get ciphertext C

C = E(P, K)

Decrypt C with key K to get plaintext P

P = D(C, K)

Note that

P = D(E(P, K), K) and C = E(D(C, K), K) Public Key Crptography Plain text and Cipher text consists of fixed sized blocks

Ciphertext obtained from plaintext by iterating a round function

Input to round function consists of key and the output of previous round

Usually implemented in software Two keys

Sender uses recipient’s public key to encrypt

Receiver uses his private key to decrypt

Based on trap door, one way function

Easy to compute in one direction

Hard to compute in other direction

“Trap door” used to create keys – public info does not help to recover the private info (key)

Example: Given p and q, product N=pq is easy to compute, but given N, it is hard to find p and q Public Key Cryptography Contd. Encryption

Suppose we encrypt M with Bob’s public key

Only Bob’s private key can decrypt to find M

Digital Signature

Sign by “encrypting” with private key

Anyone can verify signature by “decrypting”

with public key

But only private key holder could have signed

RSA Invented by Cocks (GCHQ), independently,

by Rivest, Shamir and Adleman (MIT)

Let p and q be two large prime numbers

Let N = pq be the modulus

Choose e relatively prime to (p-1)(q-1)

Find d s.t. ed = 1 mod (p-1)(q-1)

Public key is (N,e)

Private key is d RSA Contd. To encrypt message M compute

C = M^e mod N

To decrypt C compute

M = C^d mod N

Recall that e and N are public

If attacker can factor N, he can use e to easily find d since ed = 1 mod (p-1)(q-1)

Factoring the modulus breaks RSA Simple RSA Example Example of RSA

Select “large” primes p = 11, q = 3

Then N = pq = 33 and (p-1)(q-1) = 20

Choose e = 3 (relatively prime to 20)

Find d such that ed = 1 mod 20, we find that d = 7 works

Public key: (N, e) = (33, 3)

Private key: d = 7 Simple RSA Example Public key: (N, e) = (33, 3)

Private key: d = 7

Suppose message M = 8

Ciphertext C is computed as

C = M^e mod N = 8 ^3 = 512 = 17 mod 33

Decrypt C to recover the message M by

M = C^d mod N = 17^7 = 410,338,673 =

12,434,505 * 33 + 8 = 8 mod 33 Contd. Security Requirements in Distributed Systems Diffie - Hellman Invented by Williamson (GCHQ) and, independently, by D and H (Stanford)

A “key exchange” algorithm

Used to establish a shared symmetric key

Not for encrypting or signing

Security rests on difficulty of discrete log

problem: given g, p, and g^k mod p find k 6/48 7/48 8/48 9/48 10/48 11/48 12/48 13/48 14/48 15/48 16/48 17/48 18/48 19/48 20/48 21/48 22/48 23/48 24/48 25/48 26/48 27/48 28/48 29/48 30/48 31/48 32/48 34/48 35/48 36/48 37/48 38/48 39/48 40/48 41/48 42/48 43/48 44/48