Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present 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.

DeleteCancel

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.

No, thanks

Data Security & Cryptography

No description
by

Prathyusha Mandadapu

on 2 April 2013

Comments (0)

Please log in to add your comment.

Report abuse

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 transcript