• Author / Uploaded
• Alex P S

Citation preview

Information security principles and practice, 2nd edition, by mark stamp

Chapter 1  Introduction

1

Chapter 1: Introduction “Begin at the beginning,” the King said, very gravely, “and go on till you come to the end: then stop.”  Lewis Carroll, Alice in Wonderland

Chapter 1  Introduction

2

The Cast of Characters  Alice

and Bob are the good guys

 Trudy

is the bad “guy”

 Trudy

is our generic “intruder”

Chapter 1  Introduction

3

Alice’s Online Bank  Alice  What

opens Alice’s Online Bank (AOB)

are Alice’s security concerns?

 If

Bob is a customer of AOB, what are his security concerns?

 How

are Alice’s and Bob’s concerns similar? How are they different?

 How

does Trudy view the situation?

Chapter 1  Introduction

4

CIA  CIA

== Confidentiality, Integrity, and Availability

 AOB

must prevent Trudy from learning Bob’s account balance

 Confidentiality:

prevent unauthorized reading of information o Cryptography used for confidentiality

Chapter 1  Introduction

5

CIA  Trudy

must not be able to change Bob’s account balance

 Bob

must not be able to improperly change his own account balance

 Integrity:

detect unauthorized writing of information o Cryptography used for integrity

Chapter 1  Introduction

6

CIA  

AOB’s information must be available whenever it’s needed Alice must be able to make transaction o If not, she’ll take her business elsewhere

 

Availability: Data is available in a timely manner when needed Availability a relatively new security issue o Denial of service (DoS) attacks

Chapter 1  Introduction

7

Beyond CIA: Crypto  How

does Bob’s computer know that “Bob” is really Bob and not Trudy?

 Bob’s

password must be verified

o This requires some clever cryptography  What

 Are

are security concerns of pwds?

there alternatives to passwords?

Chapter 1  Introduction

8

Beyond CIA: Protocols    

When Bob logs into AOB, how does AOB know that “Bob” is really Bob? As before, Bob’s password is verified Unlike the previous case, network security issues arise How do we secure network transactions? o Protocols are critically important

o Crypto plays a major role in security protocols Chapter 1  Introduction

9

Beyond CIA: Access Control 

Once Bob is authenticated by AOB, then AOB must restrict actions of Bob o Bob can’t view Charlie’s account info o Bob can’t install new software, and so on…

 

Enforcing such restrictions: authorization Access control includes both authentication and authorization

Chapter 1  Introduction

10

Beyond CIA: Software 

Cryptography, protocols, and access control are all implemented in software o Software is foundation on which security rests



What are security issues of software? o Real-world software is complex and buggy o Software flaws lead to security flaws o How does Trudy attack software?

o How to reduce flaws in software development? o And what about malware? Chapter 1  Introduction

11

Your Textbook  The

text consists of four major parts

o Cryptography o Access control

o Protocols o Software  We’ll  But,

focus on technical issues

people cause lots of problems…

Chapter 1  Introduction

12

The People Problem  People

often break security

o Both intentionally and unintentionally o Here, we consider an unintentional case  For

example, suppose you want to buy something online o Say, Information Security: Principles and

Practice, 3rd edition from amazon.com

Chapter 1  Introduction

13

The People Problem  To

buy from amazon.com…

o Your browser uses the SSL protocol o SSL relies on cryptography o Many access control issues arise o All security mechanisms are in software  Suppose

all of this security stuff works perfectly o Then you would be safe, right?

Chapter 1  Introduction

14

The People Problem  What

could go wrong?  Trudy tries man-in-the-middle attack o SSL is secure, so attack does not “work” o But, Web browser warns of problem o What do you, the user, do?  If

user ignores warning, attack works!

o None of the security mechanisms failed o But user unintentionally broke security Chapter 1  Introduction

15

Cryptography  “Secret  The

codes”

book covers

o Classic cryptography o Symmetric ciphers o Public key cryptography o Hash functions++ o Advanced cryptanalysis Chapter 1  Introduction

16

Access Control 

Authentication o Passwords

o Biometrics o Other methods of authentication 

Authorization o Access Control Lists and Capabilities o Multilevel security (MLS), security modeling,

covert channel, inference control

o Firewalls, intrusion detection (IDS) Chapter 1  Introduction

17

Protocols  “Simple”

authentication protocols

o Focus on basics of security protocols o Lots of applied cryptography in protocols  Real-world

security protocols

o SSH, SSL, IPSec, Kerberos o Wireless: WEP, GSM

Chapter 1  Introduction

18

Software  Security-critical

flaws in software

o Buffer overflow o Race conditions, etc.  Malware

o Examples of viruses and worms o Prevention and detection o Future of malware? Chapter 1  Introduction

19

Software  Software

reverse engineering (SRE)

o How hackers “dissect” software  Digital

rights management (DRM)

o Shows difficulty of security in software o Also raises OS security issues  Software

and testing

o Open source, closed source, other topics Chapter 1  Introduction

20

Software 

Operating systems o Basic OS security issues o “Trusted OS” requirements o NGSCB: Microsoft’s trusted OS for the PC



Software is a BIG security topic o Lots of material to cover o Lots of security problems to consider o But not nearly enough time…

Chapter 1  Introduction

21

Think Like Trudy  In

the past, no respectable sources talked about “hacking” in detail o After all, such info might help Trudy

 Recently,

this has changed

o Lots of info on network hacking, malware, how to hack software, and more o Classes taught on virus writing, SRE, … Chapter 1  Introduction

22

Think Like Trudy  Good A

guys must think like bad guys!

police detective…

o …must study and understand criminals  In

information security

o We want to understand Trudy’s methods o We might think about Trudy’s motives o We’ll often pretend to be Trudy Chapter 1  Introduction

23

Think Like Trudy  Is

it a good idea to discuss security problems and attacks?

 Bruce

Schneier, referring to Security Engineering, by Ross Anderson: o “It’s about time somebody wrote a book to teach the good guys what the bad

guys already know.”

Chapter 1  Introduction

24

Think Like Trudy We must try to think like Trudy  We must study Trudy’s methods  We can admire Trudy’s cleverness  Often, we can’t help but laugh at Alice’s and/or Bob’s stupidity  But, we cannot act like Trudy 

o Except in this class … o … and even then, there are limits Chapter 1  Introduction

25

In This Course…  Think

like the bad guy  Always look for weaknesses o Find the weak link before Trudy does  It’s

OK to break the rules

o What rules?  Think

like Trudy  But don’t do anything illegal! Chapter 1  Introduction

26

Part I: Crypto

Part 1  Cryptography

27

Chapter 2: Crypto Basics MXDXBVTZWVMXNSPBQXLIMSCCSGXSCJXBOVQXCJZMOJZCVC TVWJCZAAXZBCSSCJXBQCJZCOJZCNSPOXBXSBTVWJC JZDXGXXMOZQMSCSCJXBOVQXCJZMOJZCNSPJZHGXXMOSPLH JZDXZAAXZBXHCSCJXTCSGXSCJXBOVQX

 plaintext from Lewis Carroll, Alice in Wonderland

The solution is by no means so difficult as you might be led to imagine from the first hasty inspection of the characters. These characters, as any one might readily guess, form a cipher  that is to say, they convey a meaning…  Edgar Allan Poe, The Gold Bug Part 1  Cryptography

28

Crypto  Cryptology

 The art and science of making and breaking “secret codes”  Cryptography  making “secret codes”  Cryptanalysis  breaking “secret codes”  Crypto  all of the above (and more) Part 1  Cryptography

29

How to Speak Crypto A cipher or cryptosystem is used to encrypt the plaintext  The result of encryption is ciphertext  We decrypt ciphertext to recover plaintext  A key is used to configure a cryptosystem  A symmetric key cryptosystem uses the same key to encrypt as to decrypt  A public key cryptosystem uses a public key to encrypt and a private key to decrypt 

Part 1  Cryptography

30

Crypto 

Basic assumptions o The system is completely known to the attacker o Only the key is secret o That is, crypto algorithms are not secret



This is known as Kerckhoffs’ Principle



Why do we make such an assumption? o Experience has shown that secret algorithms

tend to be weak when exposed

o Secret algorithms never remain secret o Better to find weaknesses beforehand Part 1  Cryptography

31

Crypto as Black Box

plaintext

key

key

encrypt

decrypt

plaintext

ciphertext

A generic view of symmetric key crypto Part 1  Cryptography

32

Simple Substitution  Plaintext:

fourscoreandsevenyearsago

 Key:

Plaintext 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 Ciphertext D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

 Ciphertext:

IRXUVFRUHDQGVHYHQBHDUVDJR  Shift by 3 is “Caesar’s cipher” Part 1  Cryptography

33

Ceasar’s Cipher Decryption  Suppose

we know a Caesar’s cipher is being used:

Plaintext 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 Ciphertext D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

 Given

ciphertext: VSRQJHEREVTXDUHSDQWV  Plaintext: spongebobsquarepants Part 1  Cryptography

34

Not-so-Simple Substitution  Shift

by n for some n  {0,1,2,…,25}

 Then

key is n

 Example: Plaintext

key n = 7

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

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

Part 1  Cryptography

35

Cryptanalysis I: Try Them All 

A simple substitution (shift by n) is used o But the key is unknown



Given ciphertext: CSYEVIXIVQMREXIH



How to find the key?



Only 26 possible keys  try them all!



Exhaustive key search



Solution: key is n = 4

Part 1  Cryptography

36

Simple Substitution: General Case 

In general, simple substitution key can be any permutation of letters o Not necessarily a shift of the alphabet



For example

Plaintext 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

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



Then 26! > 288 possible keys

Part 1  Cryptography

37

Cryptanalysis II: Be Clever 

We know that a simple substitution is used



But not necessarily a shift by n



Find the key given the ciphertext: PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOX BTFXQWAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQ WAEBIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGD PEQVPQGVPPBFTIXPFHXZHVFAGFOTHFEFBQUFTDHZBQPOTHXTY FTODXQHFTDPTOGHFQPBQWAQJJTODXQHFOQPWTBDHHIXQV APBFZQHCFWPFHPBFIPBQWKFABVYYDZBOTHPBQPQJTQOTOGHF QAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWF LQHGFXVAFXQHFUFHILTTAVWAFFAWTEVOITDHFHFQAITIXPFH XAFQHEFZQWGFLVWPTOFFA

Part 1  Cryptography

38

Cryptanalysis II Cannot try all 288 simple substitution keys  Can we be more clever?  English letter frequency counts… 

0.14 0.12 0.10 0.08 0.06 0.04 0.02 0.00

A

C

Part 1  Cryptography

E

G

I

K

M

O

Q

S

U

W

Y

39

Cryptanalysis II 

Ciphertext:

PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQ WAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQ VXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQGVPPBFTIXPFH XZHVFAGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFTDPTOGHFQPBQW AQJJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIPBQWKFABVYY DZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFF ACFCCFHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAFFAWTEVOITDHFH FQAITIXPFHXAFQHEFZQWGFLVWPTOFFA



Analyze this message using statistics below

Ciphertext frequency counts: 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 21 26 6 10 12 51 10 25 10 9 Part 1  Cryptography

3 10 0

1 15 28 42 0

0 27 4 24 22 28 6

40

8

Cryptanalysis: Terminology  Cryptosystem

is secure if best know attack is to try all keys o Exhaustive key search, that is

 Cryptosystem

is insecure if any shortcut attack is known

 But

then insecure cipher might be harder to break than a secure cipher! o What the … ?

Part 1  Cryptography

41

Double Transposition  Plaintext:

attackxatxdawn Permute rows and columns



 Ciphertext:

xtawxnattxadakc  Key is matrix size and permutations: (3,5,1,4,2) and (1,3,2) Part 1  Cryptography

42

One-Time Pad: Encryption e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

Encryption: Plaintext  Key = Ciphertext

h

e

i

l

h

i

t

l

e

r

Plaintext: 001 000 010 100 001 010 111 100 000 101 Key: 111 101 110 101 111 100 000 101 110 000 Ciphertext: 110 101 100 001 110 110 111 001 110 101

s Part 1  Cryptography

r

l

h

s

s

t

h

s

r 43

One-Time Pad: Decryption e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

Decryption: Ciphertext  Key = Plaintext

s

r

l

h

s

s

t

h

s

r

Ciphertext: 110 101 100 001 110 110 111 001 110 101 Key: 111 101 110 101 111 100 000 101 110 000 Plaintext: 001 000 010 100 001 010 111 100 000 101

h Part 1  Cryptography

e

i

l

h

i

t

l

e

r 44

One-Time Pad Double agent claims following “key” was used: s

r

l

h

s

s

t

h

s

r

Ciphertext: 110 101 100 001 110 110 111 001 110 101 “key”: 101 111 000 101 111 100 000 101 110 000

“Plaintext”: 011 010 100 100 001 010 111 100 000 101

k

i

l

l

h

i

t

l

e

r

e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

Part 1  Cryptography

45

One-Time Pad Or claims the key is… s

r

l

h

s

s

t

h

s

r

Ciphertext: 110 101 100 001 110 110 111 001 110 101 “key”: 111 101 000 011 101 110 001 011 101 101

“Plaintext”: 001 000 100 010 011 000 110 010 011 000

h

e

l

i

k

e

s

i

k

e

e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

Part 1  Cryptography

46

One-Time Pad Summary 

Provably secure o Ciphertext gives no useful info about plaintext o All plaintexts are equally likely



BUT, only when be used correctly o Pad must be random, used only once o Pad is known only to sender and receiver

Note: pad (key) is same size as message  So, why not distribute msg instead of pad? 

Part 1  Cryptography

47

Real-World One-Time Pad 

Project VENONA o Soviet spies encrypted messages from U.S. to

Moscow in 30’s, 40’s, and 50’s

o Nuclear espionage, etc. o Thousands of messages 

Spy carried one-time pad into U.S.



Spy used pad to encrypt secret messages



Repeats within the “one-time” pads made cryptanalysis possible

Part 1  Cryptography

48

VENONA Decrypt (1944) [C% Ruth] learned that her husband [v] was called up by the army but he was not sent to the front. He is a mechanical engineer and is now working at the ENORMOUS [ENORMOZ] [vi] plant in SANTA FE, New Mexico. [45 groups unrecoverable] detain VOLOK [vii] who is working in a plant on ENORMOUS. He is a FELLOWCOUNTRYMAN [ZEMLYaK] [viii]. Yesterday he learned that they had dismissed him from his work. His active work in progressive organizations in the past was cause of his dismissal. In the FELLOWCOUNTRYMAN line LIBERAL is in touch with CHESTER [ix]. They meet once a month for the payment of dues. CHESTER is interested in whether we are satisfied with the collaboration and whether there are not any misunderstandings. He does not inquire about specific items of work [KONKRETNAYa RABOTA]. In as much as CHESTER knows about the role of LIBERAL's group we beg consent to ask C. through LIBERAL about leads from among people who are working on ENOURMOUS and in other technical fields.

  

“Ruth” == Ruth Greenglass “Liberal” == Julius Rosenberg “Enormous” == the atomic bomb

Part 1  Cryptography

49

Codebook Cipher 

Literally, a book filled with “codewords”



Zimmerman Telegram encrypted via codebook Februar

13605

fest

13732

finanzielle

13850

folgender

13918

Frieden

17142

Friedenschluss

17149

:

:



Modern block ciphers are codebooks!



More about this later…

Part 1  Cryptography

50

Codebook Cipher: Additive  Codebooks

also (usually) use additive  Additive  book of “random” numbers o Encrypt message with codebook o Then choose position in additive book o Add in additives to get ciphertext o Send ciphertext and additive position (MI) o Recipient subtracts additives before

decrypting

 Why

use an additive sequence?

Part 1  Cryptography

51

Zimmerman Telegram Perhaps most famous codebook ciphertext ever  A major factor in U.S. entry into World War I 

Part 1  Cryptography

52

Zimmerman Telegram Decrypted British had recovered partial codebook  Then able to fill in missing parts 

Part 1  Cryptography

53

Random Historical Items  Crypto

timeline  Spartan Scytale  transposition cipher  Caesar’s cipher  Poe’s short story: The Gold Bug  Election of 1876 Part 1  Cryptography

54

Election of 1876 

“Rutherfraud” Hayes vs “Swindling” Tilden o Popular vote was virtual tie





Electoral college delegations for 4 states (including Florida) in dispute Commission gave all 4 states to Hayes o Voted on straight party lines



Tilden accused Hayes of bribery o Was it true?

Part 1  Cryptography

55

Election of 1876 Encrypted messages by Tilden supporters later emerged  Cipher: Partial codebook, plus transposition  Codebook substitution for important words 

ciphertext Copenhagen Greece Rochester Russia Warsaw : Part 1  Cryptography

plaintext Greenbacks Hayes votes Tilden telegram :

56

Election of 1876   

 

Apply codebook to original message Pad message to multiple of 5 words (total length, 10,15,20,25 or 30 words) For each length, a fixed permutation applied to resulting message

Permutations found by comparing several messages of same length Note that the same key is applied to all messages of a given length

Part 1  Cryptography

57

Election of 1876 

Ciphertext: Warsaw they read all unchanged last are idiots can’t situation



Codebook: Warsaw  telegram



Transposition: 9,3,6,1,10,5,2,7,4,8



Plaintext: Can’t read last telegram. Situation unchanged. They are all idiots.



A weak cipher made worse by reuse of key



Lesson? Don’t overuse keys!

Part 1  Cryptography

58

Early 20th Century 

WWI  Zimmerman Telegram



“Gentlemen do not read each other’s mail” o Henry L. Stimson, Secretary of State, 1929



WWII  golden age of cryptanalysis o Midway/Coral Sea o Japanese Purple (codename MAGIC) o German Enigma (codename ULTRA)

Part 1  Cryptography

59

Post-WWII History 

Claude Shannon  father of the science of information theory



Computer revolution  lots of data to protect



Data Encryption Standard (DES), 70’s



Public Key cryptography, 70’s



CRYPTO conferences, 80’s



Advanced Encryption Standard (AES), 90’s



The crypto genie is out of the bottle…

Part 1  Cryptography

60

Claude Shannon 

The founder of Information Theory



1949 paper: Comm. Thy. of Secrecy Systems



Fundamental concepts o Confusion  obscure relationship between

plaintext and ciphertext

o Diffusion  spread plaintext statistics through

the ciphertext

 

Proved one-time pad is secure One-time pad is confusion-only, while double transposition is diffusion-only

Part 1  Cryptography

61

Taxonomy of Cryptography 

Symmetric Key o Same key for encryption and decryption o Modern types: Stream ciphers, Block ciphers



Public Key (or “asymmetric” crypto) o Two keys, one for encryption (public), and one

for decryption (private) o And digital signatures  nothing comparable in symmetric key crypto 

Hash algorithms o Can be viewed as “one way” crypto

Part 1  Cryptography

62

Taxonomy of Cryptanalysis 

From perspective of info available to Trudy… o Ciphertext only  Trudy’s worst case scenario o Known plaintext o Chosen plaintext

 “Lunchtime attack”

 Some protocols will encrypt chosen data o Adaptively chosen plaintext o Related key

o Forward search (public key crypto) o And others… Part 1  Cryptography

63

Chapter 3: Symmetric Key Crypto The chief forms of beauty are order and symmetry…  Aristotle

“You boil it in sawdust: you salt it in glue: You condense it with locusts and tape: Still keeping one principal object in view  To preserve its symmetrical shape.”  Lewis Carroll, The Hunting of the Snark Part 1  Cryptography

64

Symmetric Key Crypto 

Stream cipher  generalize one-time pad o Except that key is relatively short o Key is stretched into a long keystream o Keystream is used just like a one-time pad



Block cipher  generalized codebook o Block cipher key determines a codebook o Each key yields a different codebook o Employs both “confusion” and “diffusion”

Part 1  Cryptography

65

Stream Ciphers

Part 1  Cryptography

66

Stream Ciphers Once upon a time, not so very long ago… stream ciphers were the king of crypto  Today, not as popular as block ciphers  We’ll discuss two stream ciphers:  A5/1 

o Based on shift registers o Used in GSM mobile phone system



RC4

o Based on a changing lookup table o Used many places

Part 1  Cryptography

67

A5/1: Shift Registers  A5/1

uses 3 shift registers

o X: 19 bits (x0,x1,x2, …,x18)

o Y: 22 bits (y0,y1,y2, …,y21) o Z: 23 bits (z0,z1,z2, …,z22)

Part 1  Cryptography

68

A5/1: Keystream 

At each iteration: m = maj(x8, y10, z10)



If x8 = m then X steps

o Examples: maj(0,1,0) = 0 and maj(1,1,0) = 1

o t = x13  x16  x17  x18 o xi = xi1 for i = 18,17,…,1 and x0 = t



If y10 = m then Y steps

o t = y20  y21 o yi = yi1 for i = 21,20,…,1 and y0 = t



If z10 = m then Z steps

o t = z7  z20  z21  z22 o zi = zi1 for i = 22,21,…,1 and z0 = t



Keystream bit is x18  y21  z22

Part 1  Cryptography

69

A5/1 X

x0

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x12 x13 x14 x15 x16 x17 x18



Y

y0

y1

y2

y3

y4

y5

y6

y7

y8

y9 y10 y11 y12 y13 y14 y15 y16 y17 y18 y19 y20 y21





Z

z0

z1

z2

z3

z4

z5

z6

z7

z8

z9

z10 z11 z12 z13 z14 z15 z16 z17 z18 z19 z20 z21 z22

    

Each variable here is a single bit Key is used as initial fill of registers Each register steps (or not) based on maj(x8, y10, z10) Keystream bit is XOR of rightmost bits of registers

Part 1  Cryptography

70

A5/1 X

1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1



Y

1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1





Z

1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1



   

In this example, m = maj(x8, y10, z10) = maj(1,0,1) = 1 Register X steps, Y does not step, and Z steps Keystream bit is XOR of right bits of registers Here, keystream bit will be 0  1  0 = 1

Part 1  Cryptography

71

Shift Register Crypto 

Shift register crypto efficient in hardware



Often, slow if implemented in software



In the past, very, very popular

 

Today, more is done in software due to fast processors Shift register crypto still used some o Especially in resource-constrained devices

Part 1  Cryptography

72

RC4 A self-modifying lookup table  Table always contains a permutation of the byte values 0,1,…,255  Initialize the permutation using key  At each step, RC4 does the following 

o Swaps elements in current lookup table

o Selects a keystream byte from table 

Each step of RC4 produces a byte o Efficient in software



Each step of A5/1 produces only a bit o Efficient in hardware

Part 1  Cryptography

73

RC4 Initialization  

S[] is permutation of 0,1,...,255 key[] contains N bytes of key for i = 0 to 255 S[i] = i K[i] = key[i (mod N)] next i j = 0 for i = 0 to 255 j = (j + S[i] + K[i]) mod 256 swap(S[i], S[j]) next i i = j = 0

Part 1  Cryptography

74

RC4 Keystream 

At each step, swap elements in table and select keystream byte i = (i + 1) mod 256 j = (j + S[i]) mod 256 swap(S[i], S[j]) t = (S[i] + S[j]) mod 256 keystreamByte = S[t]



Use keystream bytes like a one-time pad



Note: first 256 bytes should be discarded o Otherwise, related key attack exists

Part 1  Cryptography

75

Stream Ciphers 

Stream ciphers were popular in the past o Efficient in hardware o Speed was needed to keep up with voice, etc. o Today, processors are fast, so software-based

crypto is usually more than fast enough



Future of stream ciphers? o Shamir declared “the death of stream ciphers” o May be greatly exaggerated…

Part 1  Cryptography

76

Block Ciphers

Part 1  Cryptography

77

(Iterated) Block Cipher  Plaintext

and ciphertext consist of fixed-sized blocks

 Ciphertext

obtained from plaintext by iterating a round function

 Input

to round function consists of key and output of previous round

 Usually

implemented in software

Part 1  Cryptography

78

Feistel Cipher: Encryption 

Feistel cipher is a type of block cipher o Not a specific block cipher

 

Split plaintext block into left and right halves: P = (L0, R0) For each round i = 1, 2, ..., n, compute Li = Ri1 Ri = Li1  F(Ri1, Ki) where F is round function and Ki is subkey



Ciphertext: C = (Ln, Rn)

Part 1  Cryptography

79

Feistel Cipher: Decryption 

Start with ciphertext C = (Ln, Rn)



For each round i = n, n1, …, 1, compute Ri1 = Li Li1 = Ri  F(Ri1, Ki) where F is round function and Ki is subkey



Plaintext: P = (L0, R0)



Decryption works for any function F o But only secure for certain functions F

Part 1  Cryptography

80

Data Encryption Standard 

DES developed in 1970’s



Based on IBM’s Lucifer cipher



DES was U.S. government standard



Development of DES was controversial o NSA secretly involved o Design process was secret

o Key length reduced from 128 to 56 bits o Subtle changes to Lucifer algorithm Part 1  Cryptography

81

DES Numerology 

DES is a Feistel cipher with… o 64 bit block length

o 56 bit key length o 16 rounds o 48 bits of key used each round (subkey) 

Round function is simple (for block cipher)



Security depends heavily on “S-boxes” o Each S-box maps 6 bits to 4 bits

Part 1  Cryptography

82

L

key

R 32

28

expand 48

32



48

S-boxes

28

shift

shift 28

Ki 48

28

compress

28

28

32 32

P box

32

 L

One Round of DES

R

32

Part 1  Cryptography

key 83

DES Expansion Permutation  Input

32 bits

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

 Output

48 bits

31 0 1 2 3 4 3 4 5 6 7 8 7 8 9 10 11 12 11 12 13 14 15 16 15 16 17 18 19 20 19 20 21 22 23 24 23 24 25 26 27 28 27 28 29 30 31 0

Part 1  Cryptography

84

DES S-box 8

“substitution boxes” or S-boxes  Each S-box maps 6 bits to 4 bits  Here is S-box number 1 input bits (0,5) 

input bits (1,2,3,4)

| 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 -----------------------------------------------------------------------------------00 | 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111 01 | 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000 10 | 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000 11 | 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101

Part 1  Cryptography

85

DES P-box  Input

32 bits

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

 Output 15 1

32 bits

6 19 20 28 11 27 16 0 14 22 25 4 17 30 9 7 23 13 31 26 2 8 18 12 29 5 21 10 3 24

Part 1  Cryptography

86

DES Subkey 56 bit DES key, numbered 0,1,2,…,55  Left half key bits, LK 

49 42 35 28 21 0 50 43 36 29 8 1 51 44 37 16 9 2 52 45



14 7 22 15 30 23 38 31

Right half key bits, RK 55 48 41 34 27 6 54 47 40 33 12 5 53 46 39 18 11 4 24 17

Part 1  Cryptography

20 13 26 19 32 25 10 3 87

DES Subkey 

For rounds i=1,2,...,16 o Let LK = (LK circular shift left by ri) o Let RK = (RK circular shift left by ri) o Left half of subkey Ki is of LK bits 13 16 10 23 0 22 18 11 3 25

4 2 27 14 5 20 7 15 6 26 19 12

9 1

o Right half of subkey Ki is RK bits 12 23 2 8 18 26 1 11 22 16 15 20 10 27 5 24 17 13 21 7 Part 1  Cryptography

4 19 0 3 88

DES Subkey 

For rounds 1, 2, 9 and 16 the shift ri is 1, and in all other rounds ri is 2



Bits 8,17,21,24 of LK omitted each round



Bits 6,9,14,25 of RK omitted each round

 

Compression permutation yields 48 bit subkey Ki from 56 bits of LK and RK

Key schedule generates subkey

Part 1  Cryptography

89

DES Last Word (Almost)  An

initial permutation before round 1

 Halves

are swapped after last round

A

final permutation (inverse of initial perm) applied to (R16, L16)

 None

of this serves any security purpose

Part 1  Cryptography

90

Security of DES 

Security depends heavily on S-boxes o Everything else in DES is linear



35+ years of intense analysis has revealed no back door



Attacks, essentially exhaustive key search



Inescapable conclusions o Designers of DES knew what they were doing o Designers of DES were way ahead of their time

(at least wrt certain cryptanalytic techniques)

Part 1  Cryptography

91

Block Cipher Notation 

P = plaintext block



C = ciphertext block



Encrypt P with key K to get ciphertext C o C = E(P, K)



Decrypt C with key K to get plaintext P o P = D(C, K)



Note: P = D(E(P, K), K) and C = E(D(C, K), K) o But P  D(E(P, K1), K2) and C  E(D(C, K1), K2) when

K1  K2

Part 1  Cryptography

92

Triple DES 

Today, 56 bit DES key is too small o Exhaustive key search is feasible



But DES is everywhere, so what to do?



Triple DES or 3DES (112 bit key) o C = E(D(E(P,K1),K2),K1) o P = D(E(D(C,K1),K2),K1)



Why Encrypt-Decrypt-Encrypt with 2 keys? o Backward compatible: E(D(E(P,K),K),K) = E(P,K) o And 112 is a lot of bits

Part 1  Cryptography

93

3DES 

Why not C = E(E(P,K),K) instead? o Trick question  still just 56 bit key



Why not C = E(E(P,K1),K2) instead?



A (semi-practical) known plaintext attack o Pre-compute table of E(P,K1) for every possible

key K1 (resulting table has 256 entries)

o Then for each possible K2 compute D(C,K2) until

a match in table is found

o When match is found, have E(P,K1) = D(C,K2) o Result gives us keys: C = E(E(P,K1),K2) Part 1  Cryptography

94

Advanced Encryption Standard 

Replacement for DES



AES competition (late 90’s) o NSA openly involved o Transparent selection process

o Many strong algorithms proposed o Rijndael Algorithm ultimately selected

(pronounced like “Rain Doll” or “Rhine Doll”)



Iterated block cipher (like DES)



Not a Feistel cipher (unlike DES)

Part 1  Cryptography

95

AES: Executive Summary  Block

size: 128 bits (others in Rijndael)  Key length: 128, 192 or 256 bits (independent of block size in Rijndael)  10 to 14 rounds (depends on key length)  Each round uses 4 functions (3 “layers”) o o o o

ByteSub (nonlinear layer) ShiftRow (linear mixing layer) MixColumn (nonlinear layer) AddRoundKey (key addition layer)

Part 1  Cryptography

96

AES ByteSub 

Treat 128 bit block as 4x4 byte array

ByteSub is AES’s “S-box”  Can be viewed as nonlinear (but invertible) composition of two math operations 

Part 1  Cryptography

97

AES “S-box” Last 4 bits of input

First 4 bits of input

Part 1  Cryptography

98

AES ShiftRow  Cyclic

shift rows

Part 1  Cryptography

99

AES MixColumn  Invertible,

linear operation applied to each column

 Implemented Part 1  Cryptography

as a (big) lookup table 100

AES AddRoundKey  XOR

subkey with block

Block

Subkey

 RoundKey

(subkey) determined by key schedule algorithm

Part 1  Cryptography

101

AES Decryption    



To decrypt, process must be invertible Inverse of MixAddRoundKey is easy, since “” is its own inverse MixColumn is invertible (inverse is also implemented as a lookup table) Inverse of ShiftRow is easy (cyclic shift the other direction)

ByteSub is invertible (inverse is also implemented as a lookup table)

Part 1  Cryptography

102

A Few Other Block Ciphers  Briefly…

o IDEA o Blowfish o RC6  More

detailed…

o TEA

Part 1  Cryptography

103

IDEA  Invented

by James Massey

o One of the giants of modern crypto  IDEA

has 64-bit block, 128-bit key

 IDEA

uses mixed-mode arithmetic

 Combine

different math operations

o IDEA the first to use this approach o Frequently used today Part 1  Cryptography

104

Blowfish Blowfish encrypts 64-bit blocks  Key is variable length, up to 448 bits  Invented by Bruce Schneier  Almost a Feistel cipher 

Ri = Li1  Ki Li = Ri1  F(Li1  Ki)



The round function F uses 4 S-boxes o Each S-box maps 8 bits to 32 bits



Key-dependent S-boxes o S-boxes determined by the key

Part 1  Cryptography

105

RC6 

Invented by Ron Rivest



Variables o Block size o Key size

o Number of rounds 

An AES finalist



Uses data dependent rotations o Unusual for algorithm to depend on plaintext

Part 1  Cryptography

106

Time for TEA…  Tiny

Encryption Algorithm (TEA)  64 bit block, 128 bit key  Assumes 32-bit arithmetic  Number of rounds is variable (32 is considered secure)  Uses “weak” round function, so large number of rounds required Part 1  Cryptography

107

TEA Encryption Assuming 32 rounds: (K[0], K[1], K[2], K[3]) = 128 bit key (L,R) = plaintext (64-bit block) delta = 0x9e3779b9 sum = 0 for i = 1 to 32 sum += delta L += ((R5)+K[1]) R += ((L5)+K[3]) next i ciphertext = (L,R) Part 1  Cryptography

108

TEA Decryption Assuming 32 rounds: (K[0], K[1], K[2], K[3]) = 128 bit key (L,R) = ciphertext (64-bit block) delta = 0x9e3779b9 sum = delta (xx2xy+yy)){…} o The if() conditional is always false 

Attacker wastes time analyzing dead code

Part 4  Software

815

Code Obfuscation Code obfuscation sometimes promoted as a powerful security technique  Diffie and Hellman’s original idea for public key crypto was based on code obfuscation 

o But public key crypto didn’t work out that way 

It has been shown that obfuscation probably cannot provide strong, crypto-like security o On the (im)possibility of obfuscating programs



Obfuscation might still have practical uses o Even if it can never be as strong as crypto

Part 4  Software

816

Authentication Example 

Software used to determine authentication



Ultimately, authentication is 1-bit decision o Regardless of method used (pwd, biometric, …) o Somewhere in authentication software, a single

bit determines success/failure

 

If Trudy can find this bit, she can force authentication to always succeed

Obfuscation makes it more difficult for attacker to find this all-important bit

Part 4  Software

817

Obfuscation Obfuscation forces attacker to analyze larger amounts of code  Method could be combined with 

o Anti-disassembly techniques o Anti-debugging techniques o Code tamper-checking

All of these increase work/pain for attacker  But a persistent attacker can ultimately win 

Part 4  Software

818

Software Cloning Suppose we write a piece of software  We then distribute an identical copy (or clone) to each customers  If an attack is found on one copy, the same attack works on all copies  This approach has no resistance to “break once, break everywhere” (BOBE)  This is the usual situation in software development 

Part 4  Software

819

Metamorphic Software 

Metamorphism sometimes used in malware

Can metamorphism also be used for good?  Suppose we write a piece of software  Each copy we distribute is different 

o This is an example of metamorphic software 

Two levels of metamorphism are possible o All instances are functionally distinct (only possible

in certain application) o All instances are functionally identical but differ internally (always possible) o We consider the latter case Part 4  Software

820

Metamorphic Software 

If we distribute N copies of cloned software o One successful attack breaks all N



If we distribute N metamorphic copies, where each of N instances is functionally identical, but they differ internally… o An attack on one instance does not necessarily

work against other instances

o In the best case, N times as much work is required

to break all N instances

Part 4  Software

821

Metamorphic Software 

We cannot prevent SRE attacks



The best we can hope for is BOBE resistance



Metamorphism can improve BOBE resistance



Consider the analogy to genetic diversity o If all plants in a field are genetically identical,

one disease can rapidly kill all of the plants

o If the plants in a field are genetically diverse,

one disease can only kill some of the plants

Part 4  Software

822

Cloning vs Metamorphism Spse our software has a buffer overflow  Cloned software 

o Same buffer overflow attack will work against

all cloned copies of the software



Metamorphic software o Unique instances  all are functionally the

same, but they differ in internal structure

o Buffer overflow likely exists in all instances o But a specific buffer overflow attack will only

work against some instances

o Buffer overflow attacks are delicate! Part 4  Software

823

Metamorphic Software Metamorphic software is intriguing concept  But raises concerns regarding… 

o Software development, upgrades, etc.

Metamorphism does not prevent SRE, but could make it infeasible on a large scale  Metamorphism might be a practical tool for increasing BOBE resistance  Metamorphism currently used in malware  So, metamorphism is not just for evil! 

Part 4  Software

824

Digital Rights Management

Part 4  Software

825

Digital Rights Management  DRM

is a good example of limitations of doing security in software  We’ll discuss o o o o o

What is DRM? A PDF document protection system DRM for streaming media DRM in P2P application DRM within an enterprise

Part 4  Software

826

What is DRM? 

“Remote control” problem

o Distribute digital content o Retain some control on its use, after delivery



Digital book example o o o o



Digital book sold online could have huge market But might only sell 1 copy! Trivial to make perfect digital copies A fundamental change from pre-digital era

Similar comments for digital music, video, etc.

Part 4  Software

827

Persistent Protection 

“Persistent protection” is the fundamental problem in DRM o How to enforce restrictions on use of content

after delivery?



Examples of such restrictions o o o o

No copying Limited number of reads/plays Time limits No forwarding, etc.

Part 4  Software

828

What Can be Done? 

The honor system?



Give up?



Lame software-based DRM?



Better software-based DRM?



Tamper-resistant hardware?

o Example: Stephen King’s, The Plant o Internet sales? Regulatory compliance? etc. o The standard DRM system today

o MediaSnap’s goal

o Closed systems: Game Cube, etc. o Open systems: TCG/NGSCB for PCs

Part 4  Software

829

Is Crypto the Answer?





Attacker’s goal is to recover the key In standard crypto scenario, attacker has

o Ciphertext, some plaintext, side-channel info, etc.



In DRM scenario, attacker has o Everything in the box (at least)



Crypto was not designed for this problem!

Part 4  Software

830

Is Crypto the Answer? 

But crypto is necessary o To securely deliver the bits

o To prevent trivial attacks

Then attacker will not try to directly attack crypto  Attacker will try to find keys in software 

o DRM is “hide and seek” with keys in software!

Part 4  Software

831

Current State of DRM 

At best, security by obscurity o A derogatory term in security



Secret designs

o In violation of Kerckhoffs Principle



Over-reliance on crypto

o “Whoever thinks his problem can be solved using cryptography, doesn’t understand his problem and doesn’t understand cryptography.”  Attributed by Roger Needham and Butler Lampson to each other

Part 4  Software

832

DRM Limitations 

The analog hole

o When content is rendered, it can be captured in

analog form o DRM cannot prevent such an attack



Human nature matters

o Absolute DRM security is impossible o Want something that “works” in practice o What works depends on context



DRM is not strictly a technical problem!

Part 4  Software

833

Software-based DRM Strong software-based DRM is impossible  Why? 

o We can’t really hide a secret in software o We cannot prevent SRE o User with full admin privilege can eventually

break any anti-SRE protection



Bottom line: The killer attack on softwarebased DRM is SRE

Part 4  Software

834

DRM for PDF Documents  Based

on design of MediaSnap, Inc., a small Silicon Valley startup company  Developed a DRM system o Designed to protect PDF documents

 Two

parts to the system

o Server  Secure Document Server (SDS) o Client  PDF Reader “plugin” software

Part 4  Software

835

Protecting a Document persistent protection

encrypt

Alice

SDS

Bob

Alice creates PDF document  Document encrypted and sent to SDS  SDS applies desired “persistent protection”  Document sent to Bob 

Part 4  Software

836

Accessing a Document Request key

key Alice

SDS

Bob

Bob authenticates to SDS  Bob requests key from SDS  Bob can then access document, but only thru special DRM software 

Part 4  Software

837

Security Issues 

Server side (SDS)

o Protect keys, authentication data, etc. o Apply persistent protection 

Client side (PDF plugin)

o Protect keys, authenticate user, etc. o Enforce persistent protection 

Remaining discussion concerns client

Part 4  Software

838

Security Overview Tamper-resistance Obfuscation

A tamper-resistant outer layer  Software obfuscation applied within 

Part 4  Software

839

Tamper-Resistance Anti-debugger

Encrypted code

Encrypted code will prevent static analysis of PDF plugin software  Anti-debugging to prevent dynamic analysis of PDF plugin software  These two designed to protect each other  But the persistent attacker will get thru! 

Part 4  Software

840

Obfuscation 

Obfuscation can be used for o o o o o o

Key management Authentication Caching (keys and authentication info) Encryption and “scrambling” Key parts (data and/or code) Multiple keys/key parts

Obfuscation can only slow the attacker  The persistent attacker still wins! 

Part 4  Software

841

Other Security Features 

Code tamper checking (hashing)

o To validate all code executing on system



Anti-screen capture

o To prevent obvious attack on digital documents



Watermarking

o In theory, can trace stolen content o In practice, of limited value



Metamorphism (or individualization) o For BOBE-resistance

Part 4  Software

842

Security Not Implemented  More

general code obfuscation  Code “fragilization”

o Code that hash checks itself o Tampering should cause code to break

 OS

cannot be trusted

o How to protect against “bad” OS? o Not an easy problem!

Part 4  Software

843

DRM for Streaming Media  Stream

digital content over Internet

o Usually audio or video o Viewed in real time

 Want

to charge money for the content  Can we protect content from capture? o So content can’t be redistributed o We want to make money!

Part 4  Software

844

Attacks on Streaming Media  Spoof

the stream between endpoints  Man in the middle  Replay and/or redistribute data  Capture the plaintext

o This is the threat we are concerned with o Must prevent malicious software from

capturing plaintext stream at client end

Part 4  Software

845

Design Features 

Scrambling algorithms



Negotiation of scrambling algorithm



Decryption at receiver end



De-scrambling in device driver

o Encryption-like algorithms o Many distinct algorithms available o A strong form of metamorphism!

o Server and client must both know the algorithm o To remove the strong encryption

o De-scramble just prior to rendering

Part 4  Software

846

Scrambling Algorithms  Server

has a large set of scrambling algorithms o Suppose N of these numbered 1 thru N

 Each

client has a subset of algorithms

o For example: LIST = {12,45,2,37,23,31}

 The

LIST is stored on client, encrypted with server’s key: E(LIST,Kserver)

Part 4  Software

847

Server-side Scrambling 

On server side

data

scrambled data

encrypted scrambled data

Server must scramble data with an algorithm the client supports  Client must send server list of algorithms it supports  Server must securely communicate algorithm choice to client 

Part 4  Software

848

Select Scrambling Algorithm E(LIST, Kserver)

E(m,K) Alice (client)

scramble (encrypted) data using Alice’s m-th algorithm

Bob (server)

The key K is a session key  The LIST is unreadable by client 

o Reminiscent of Kerberos TGT

Part 4  Software

849

Client-side De-scrambling  On

client side

encrypted scrambled data

scrambled data

data

 Try

to keep plaintext away from potential attacker  “Proprietary” device driver

o Scrambling algorithms “baked in” o Able to de-scramble at last moment

Part 4  Software

850

Why Scrambling? Metamorphism deeply embedded in system  If a scrambling algorithm is known to be broken, server will not choose it  If client has too many broken algorithms, server can force software upgrade  Proprietary algorithm harder for SRE  We cannot trust crypto strength of proprietary algorithms, so we also encrypt 

Part 4  Software

851

Why Metamorphism? The most serious threat is SRE  Attacker does not need to reverse engineer any standard crypto algorithm 

o Attacker only needs to find the key

Reverse engineering a scrambling algorithm may be difficult  This is just security by obscurity  But appears to help with BOBE-resistance 

Part 4  Software

852

DRM for a P2P Application 

Today, much digital content is delivered via peer-to-peer (P2P) networks o P2P networks contain lots of pirated music

Is it possible to get people to pay for digital content on such P2P networks?  How can this possibly work?  A peer offering service (POS) is one idea 

Part 4  Software

853

P2P File Sharing: Query Suppose Alice requests “Hey Jude”  Black arrows: query flooding  Red arrows: positive responses 

Alice

Frank

Carol

Bob

Dean

Marilyn

Pat

Ted



Carol

Pat

Fred

Alice can select from: Carol, Pat

Part 4  Software

854

P2P File Sharing with POS Suppose Alice requests “Hey Jude”  Black arrow: query  Red arrow: positive response 

Bill Ben Joe

Alice

POS

Ted

Carol

Carol

Bob

Dean

Marilyn

Pat

Pat

Fred

Alice selects from: Bill, Ben, Carol, Joe, Pat  Bill, Ben, and Joe have legal content! 

Part 4  Software

855

POS Bill, Ben and Joe must appear normal to Alice  If “victim” (Alice) clicks POS response 

o DRM protected (legal) content downloaded o Then small payment required to play



Alice can choose not to pay

o But then she must download again o Is it worth the hassle to avoid paying small fee? o POS content can also offer extras

Part 4  Software

856

POS Conclusions A very clever idea!  Piggybacking on existing P2P networks  Weak DRM works very well here 

o Pirated content already exists o DRM only needs to be more hassle to break

than the hassle of clicking and waiting



Current state of POS?

o Very little interest from the music industry o Considerable interest from the “adult” industry

Part 4  Software

857

DRM in the Enterprise Why enterpise DRM?  Health Insurance Portability and Accountability Act (HIPAA) 

o Medical records must be protected o Fines of up to $10,000 “per incident”



Sarbanes-Oxley Act (SOA)

o Must preserve documents of interest to SEC



DRM-like protections needed by corporations for regulatory compliance

Part 4  Software

858

What’s Different in Enterprise DRM? Technically, similar to e-commerce  But motivation for DRM is different 

o Regulatory compliance o To satisfy a legal requirement o Not to make money  to avoid losing money!



Human dimension is completely different o Legal threats are far more plausible



Legally, corporation is OK provided an active attack on DRM is required

Part 4  Software

859

Enterprise DRM Moderate DRM security is sufficient  Policy management issues 

o Easy to set policies for groups, roles, etc. o Yet policies must be flexible



Authentication issues

o Must interface with existing system o Must prevent network authentication spoofing

(authenticate the authentication server)



Enterprise DRM is a solvable problem!

Part 4  Software

860

DRM Failures  Many

examples of DRM failures

o One system defeated by a felt-tip pen o One defeated my holding down shift key o Secure Digital Music Initiative (SDMI) completely broken before it was finished o Adobe eBooks o Microsoft MS-DRM (version 2) o Many, many others!

Part 4  Software

861

DRM Conclusions DRM nicely illustrates limitations of doing security in software  Software in a hostile environment is extremely vulnerable to attack  Protection options are very limited  Attacker has enormous advantage  Tamper-resistant hardware and a trusted OS can make a difference 

o We’ll discuss this more later: TCG/NGSCB

Part 4  Software

862

Secure Software Development

Part 4  Software

863

Penetrate and Patch 

Usual approach to software development o Develop product as quickly as possible o Release it without adequate testing o Patch the code as flaws are discovered



In security, this is “penetrate and patch” o A bad approach to software development

o An even worse approach to secure software! Part 4  Software

864

Why Penetrate and Patch? 

First to market advantage o First to market likely to become market leader o Market leader has huge advantage in software o Users find it safer to “follow the leader”

o Boss won’t complain if your system has a flaw,

as long as everybody else has same flaw…

o User can ask more people for support, etc. 

Sometimes called “network economics”

Part 4  Software

865

Why Penetrate and Patch? 

Secure software development is hard o Costly and time consuming development o Costly and time consuming testing o Cheaper to let customers do the work!



No serious economic disincentive o Even if software flaw causes major losses, the

software vendor is not liable

o Is any other product sold this way? o Would it matter if vendors were legally liable? Part 4  Software

866

Penetrate and Patch Fallacy 

Fallacy: If you keep patching software, eventually it will be secure



Why is this a fallacy?



Empirical evidence to the contrary



Patches often add new flaws



Software is a moving target: new versions, features, changing environment, new uses,…

Part 4  Software

867

Open vs Closed Source  Open

source software

o The source code is available to user o For example, Linux  Closed

source

o The source code is not available to user o For example, Windows  What

are the security implications?

Part 4  Software

868

Open Source Security 

Claimed advantages of open source is o More eyeballs: more people looking at the code

should imply fewer flaws

o A variant on Kerchoffs Principle 

Is this valid? o How many “eyeballs” looking for security flaws? o How many “eyeballs” focused on boring parts? o How many “eyeballs” belong to security experts?

o Attackers can also look for flaws! o Evil coder might be able to insert a flaw Part 4  Software

869

Open Source Security 

Open source example: wu-ftp o About 8,000 lines of code

o A security-critical application o Was deployed and widely used o After 10 years, serious security flaws discovered! 



More generally, open source software has done little to reduce security flaws

Why? o Open source follows penetrate and patch model!

Part 4  Software

870

Closed Source Security 

Claimed advantage of closed source o Security flaws not as visible to attacker o This is a form of “security by obscurity”



Is this valid? o Many exploits do not require source code o Possible to analyze closed source code… o …though it is a lot of work! o Is “security by obscurity” real security?

Part 4  Software

871

Open vs Closed Source 

Advocates of open source often cite the Microsoft fallacy which states 1. Microsoft makes bad software 2. Microsoft software is closed source 3. Therefore all closed source software is bad



Why is this a fallacy? o

Not logically correct

o

More relevant is the fact that Microsoft follows the penetrate and patch model

Part 4  Software

872

Open vs Closed Source  No

obvious security advantage to either open or closed source

 More

significant than open vs closed source is software development practices

 Both

open and closed source follow the “penetrate and patch” model

Part 4  Software

873

Open vs Closed Source 

If there is no security difference, why is Microsoft software attacked so often? o Microsoft is a big target! o Attacker wants most “bang for the buck”



Few exploits against Mac OS X

o Not because OS X is inherently more secure o An OS X attack would do less damage o Would bring less “glory” to attacker



Next, we consider the theoretical differences o See this paper

Part 4  Software

874

Security and Testing Can be shown that probability of a security failure after t units of testing is about E = K/t where K is a constant  This approximation holds over large range of t  Then the “mean time between failures” is MTBF = t/K  The good news: security improves with testing  The bad news: security only improves linearly with testing! 

Part 4  Software

875

Security and Testing The “mean time between failures” is approximately MTBF = t/K  To have 1,000,000 hours between security failures, must test 1,000,000 hours!  Suppose open source project has MTBF = t/K  If flaws in closed source are twice as hard to find, do we then have MTBF = 2t/K ? 

o No! Testing not as effective MTBF = 2(t/2)/K = t/K



The same result for open and closed source!

Part 4  Software

876

Security and Testing 

Closed source advocates might argue o Closed source has “open source” alpha testing,

where flaws found at (higher) open source rate

o Followed by closed source beta testing and use,

giving attackers the (lower) closed source rate

o Does this give closed source an advantage? 

Alpha testing is minor part of total testing o Recall, first to market advantage

o Products rushed to market 

Probably no real advantage for closed source

Part 4  Software

877

Security and Testing 

No security difference between open and closed source?



Provided that flaws are found “linearly”



Is this valid? o Empirical results show security improves linearly

with testing

o Conventional wisdom is that this is the case for

large and complex software systems

Part 4  Software

878

Security and Testing  The

fundamental problem

o Good guys must find (almost) all flaws o Bad guy only needs 1 (exploitable) flaw  Software

reliability far more difficult in security than elsewhere

 How

much more difficult?

o See the next slide… Part 4  Software

879

Security Testing: Do the Math 

Recall that MTBF = t/K



Suppose 106 security flaws in some software o Say, Windows XP



Suppose each bug has MTBF of 109 hours



Expect to find 1 bug for every 103 hours testing



Good guys spend 107 hours testing: find 104 bugs o Good guys have found 1% of all the bugs



Trudy spends 103 hours of testing: finds 1 bug



Chance good guys found Trudy’s bug is only 1% !!!

Part 4  Software

880

Software Development 

General software development model o Specify

o Design o Implement o Test o Review o Document

o Manage o Maintain Part 4  Software

881

Secure Software Development 

Goal: move away from “penetrate and patch”



Penetrate and patch will always exist o But if more care taken in development, then

fewer and less severe flaws to patch

 



Secure software development not easy Much more time and effort required thru entire development process Today, little economic incentive for this!

Part 4  Software

882

Secure Software Development  We

briefly discuss the following

o Design o Hazard analysis o Peer review o Testing o Configuration management

o Postmortem for mistakes Part 4  Software

883

Design 

Careful initial design



Try to avoid high-level errors o Such errors may be impossible to correct later o Certainly costly to correct these errors later



Verify assumptions, protocols, etc.



Usually informal approach is used



Formal methods o Possible to rigorously prove design is correct o In practice, only works in simple cases

Part 4  Software

884

Hazard Analysis 

Hazard analysis (or threat modeling) o Develop hazard list o List of what ifs o Schneier’s “attack tree”



Many formal approaches o Hazard and operability studies (HAZOP) o Failure modes and effective analysis (FMEA) o Fault tree analysis (FTA)

Part 4  Software

885

Peer Review 

Three levels of peer review o Review (informal) o Walk-through (semi-formal) o Inspection (formal)



Each level of review is important



Much evidence that peer review is effective



Although programmers might not like it!

Part 4  Software

886

Levels of Testing  Module

testing  test each small section of code

 Component

testing  test combinations of a few modules

 Unit

testing  combine several components for testing

 Integration

testing  put everything together and test

Part 4  Software

887

Types of Testing 



Function testing  verify that system functions as it is supposed to Performance testing  other requirements such as speed, resource use, etc.



Acceptance testing  customer involved



Installation testing  test at install time



Regression testing  test after any change

Part 4  Software

888

Other Testing Issues 

Active fault detection

o Don’t wait for system to fail o Actively try to make it fail  attackers will!



Fault injection

o Insert faults into the process o Even if no obvious way for such a fault to occur



Bug injection o o o o

Insert bugs into code See how many of injected bugs are found Can use this to estimate number of bugs Assumes injected bugs similar to unknown bugs

Part 4  Software

889

Testing Case History In one system with 184,000 lines of code  Flaws found 

o 17.3% inspecting system design o 19.1% inspecting component design o 15.1% code inspection

o 29.4% integration testing o 16.6% system and regression testing 

Conclusion: must do many kinds of testing o Overlapping testing is necessary o Provides a form of “defense in depth”

Part 4  Software

890

Security Testing: The Bottom Line 

Security testing is far more demanding than non-security testing



Non-security testing  does system do what it is supposed to?

Security testing  does system do what it is supposed to and nothing more?  Usually impossible to do exhaustive testing  How much testing is enough? 

Part 4  Software

891

Security Testing: The Bottom Line 

How much testing is enough?



Recall MTBF = t/K



Seems to imply testing is nearly hopeless!



But there is some hope… o If we eliminate an entire class of flaws then

statistical model breaks down

o For example, if a single test (or a few tests)

find all buffer overflows

Part 4  Software

892

Configuration Issues  Types

of changes

o Minor changes  maintain daily functioning o Adaptive changes  modifications

o Perfective changes  improvements o Preventive changes  no loss of performance  Any

change can introduce new flaws!

Part 4  Software

893

Postmortem 

After fixing any security flaw…



Carefully analyze the flaw



To learn from a mistake o Mistake must be analyzed and understood o Must make effort to avoid repeating mistake





In security, always learn more when things go wrong than when they go right

Postmortem may be the most under-used tool in all of security engineering!

Part 4  Software

894

Software Security 

First to market advantage o Also known as “network economics” o Security suffers as a result o Little economic incentive for secure software!



Penetrate and patch o Fix code as security flaws are found o Fix can result in worse problems o Mostly done after code delivered



Proper development can reduce flaws o But costly and time-consuming

Part 4  Software

895

Software and Security 

  



Even with best development practices, security flaws will still exist

Absolute security is (almost) never possible So, it is not surprising that absolute software security is impossible The goal is to minimize and manage risks of software flaws

Do not expect dramatic improvements in consumer software security anytime soon!

Part 4  Software

896

Chapter 13: Operating Systems and Security UNIX is basically a simple operating system, but you have to be a genius to understand the simplicity.  Dennis Ritchie And it is a mark of prudence never to trust wholly in those things which have once deceived us.  Rene Descartes Part 4  Software

897

OS and Security 

OSs are large, complex programs

o Many bugs in any such program o We have seen that bugs can be security threats



Here we are concerned with security provided by OS

o Not concerned with threat of bad OS software

Concerned with OS as security enforcer  In this section we only scratch the surface 

Part 4  Software

898

OS Security Challenges Modern OS is multi-user and multi-tasking  OS must deal with 

o o o o o



Memory I/O devices (disk, printer, etc.) Programs, threads Network issues Data, etc.

OS must protect processes from other processes and users from other users o Whether accidental or malicious

Part 4  Software

899

OS Security Functions 

Memory protection

o Protect memory from users/processes



File protection

o Protect user and system resources



Authentication

o Determines and enforce authentication results



Authorization

o Determine and enforces access control

Part 4  Software

900

Memory Protection 

Fundamental problem

o How to keep users/processes separate?



Separation

Physical separation  separate devices Temporal separation  one at a time Logical separation  sandboxing, etc. Cryptographic separation  make information unintelligible to outsider o Or any combination of the above o o o o

Part 4  Software

901

Memory Protection 

Fence  users cannot cross a specified address o Static fence  fixed size OS o Dynamic fence  fence register

Base/bounds register  lower and upper address limit  Assumes contiguous space 

Part 4  Software

902

Memory Protection 

Tagging  specify protection of each address + Extremely fine-grained protection - High overhead  can be reduced by tagging sections instead of individual addresses - Compatibility



More common is segmentation and/or paging o Protection is not as flexible o But much more efficient

Part 4  Software

903

Segmentation 

Divide memory into logical units, such as o Single procedure o Data in one array, etc.

Can enforce different access restrictions on different segments  Any segment can be placed in any memory location (if location is large enough)  OS keeps track of actual locations 

Part 4  Software

904

Segmentation

memory

program

Part 4  Software

905

Segmentation  OS

can place segments anywhere  OS keeps track of segment locations as  Segments can be moved in memory  Segments can move out of memory  All address references go thru OS

Part 4  Software

906

Segmentation Advantages 

Every address reference can be checked o Possible to achieve complete mediation

Different protection can be applied to different segments  Users can share access to segments  Specific users can be restricted to specific segments 

Part 4  Software

907

Segmentation Disadvantages 

How to reference ?

o OS must know segment size to verify access is

within segment o But some segments can grow during execution (for example, dynamic memory allocation) o OS must keep track of variable segment sizes



Memory fragmentation is also a problem o Compacting memory changes tables

A lot of work for the OS  More complex  more chance for mistakes 

Part 4  Software

908

Paging Like segmentation, but fixed-size segments  Access via  Plusses and minuses 

+ Avoids fragmentation, improved efficiency + OS need not keep track of variable segment sizes - No logical unity to pages - What protection to apply to a given page?

Part 4  Software

909

Paging program Page 0 Page 1 Page 2 Page 3

Page 4

memory Page 1 Page 2 Page 0

Page 4

Page 3 Part 4  Software

910

Other OS Security Functions OS must enforce access control  Authentication 

o Passwords, biometrics o Single sign-on, etc.



Authorization o ACL o Capabilities

These topics discussed previously  OS is an attractive target for attack! 

Part 4  Software

911

Trusted Operating System

Part 4  Software

912

Trusted Operating System 

An OS is trusted if we rely on it for o o o o

Memory protection File protection Authentication Authorization

Every OS does these things  But if a trusted OS fails to provide these, our security fails 

Part 4  Software

913

Trust vs Security Trust implies reliance  Trust is binary  Ideally, only trust secure systems  All trust relationships should be explicit 



Security is a judgment of effectiveness  Judge based on specified policy  Security depends on trust relationships 

Note: Some authors use different terminology! Part 4  Software

914

Trusted Systems Trust implies reliance  A trusted system is relied on for security  An untrusted system is not relied on for security  If all untrusted systems are compromised, your security is unaffected  Ironically, only a trusted system can break your security! 

Part 4  Software

915

Trusted OS  OS

mediates interactions between subjects (users) and objects (resources)  Trusted OS must decide o Which objects to protect and how o Which subjects are allowed to do what

Part 4  Software

916

General Security Principles Least privilege  like “low watermark”  Simplicity  Open design (Kerchoffs Principle)  Complete mediation  White listing (preferable to black listing)  Separation  Ease of use  But commercial OSs emphasize features 

o Results in complexity and poor security

Part 4  Software

917

OS Security 

Any OS must provide some degree of o Authentication o Authorization (users, devices and data) o Memory protection o Sharing o Fairness o Inter-process communication/synchronization o OS protection

Part 4  Software

918

OS Services users

User interface

Synchronization Concurrency Deadlock Communication Audit trail, etc.

Operating system Data, programs, CPU, memory, I/O devices, etc. Part 4  Software

919

Trusted OS 

A trusted OS also provides some or all of o User authentication/authorization o Mandatory access control (MAC) o Discretionary access control (DAC) o Object reuse protection o Complete mediation  access control o Trusted path o Audit/logs

Part 4  Software

920

Trusted OS Services users

User interface

Synchronization Concurrency Deadlock Communication Audit trail, etc.

Authentication Operating system

Part 4  Software

Data, programs, CPU, memory, I/O devices, etc.

921

MAC and DAC 

Mandatory Access Control (MAC) o Access not controlled by owner of object o Example: User does not decide who holds a

TOP SECRET clearance



Discretionary Access Control (DAC) o Owner of object determines access o Example: UNIX/Windows file protection



If DAC and MAC both apply, MAC wins

Part 4  Software

922

Object Reuse Protection  OS

must prevent leaking of info  Example o o o o o

User creates a file Space allocated on disk But same space previously used “Leftover” bits could leak information Magnetic remanence is a related issue

Part 4  Software

923

Trusted Path 

Suppose you type in your password o What happens to the password?

Depends on the software!  How can you be sure software is not evil?  Trusted path problem: 

“I don't know how to to be confident even of a digital signature I make on my own PC, and I've worked in security for over fifteen years. Checking all of the software in the critical path between the display and the signature software is way beyond my patience. ”

 Ross Anderson Part 4  Software

924

Audit System should log security-related events  Necessary for postmortem  What to log? 

o Everything? Who (or what) will look at it? o Don’t want to overwhelm administrator o Needle in haystack problem



Should we log incorrect passwords? o “Almost” passwords in log file?



Logging is not a trivial matter

Part 4  Software

925

Security Kernel Kernel is the lowest-level part of the OS  Kernel is responsible for 

o o o o

Synchronization Inter-process communication Message passing Interrupt handling

The security kernel is the part of the kernel that deals with security  Security kernel contained within the kernel 

Part 4  Software

926

Security Kernel Why have a security kernel?  All accesses go thru kernel 

o Ideal place for access control 

Security-critical functions in one location o Easier to analyze and test o Easier to modify



More difficult for attacker to get in “below” security functions

Part 4  Software

927

Reference Monitor 

The part of the security kernel that deals with access control o Mediates access of subjects to objects o Tamper-resistant o Analyzable (small, simple, etc.)

Objects

Subjects Reference monitor

Part 4  Software

928

Trusted Computing Base TCB  everything in the OS that we rely on to enforce security  If everything outside TCB is subverted, trusted OS would still be trusted  TCB protects users from each other 

o o o o

Context switching between users Shared processes Memory protection for users I/O operations, etc.

Part 4  Software

929

TCB Implementation Security may occur many places within OS  Ideally, design security kernel first, and build the OS around it 

o Reality is usually the other way around 

Example of a trusted OS: SCOMP o Developed by Honeywell o Less than 10,000 LOC in SCOMP security kernel

o Win XP has 40,000,000 lines of code!

Part 4  Software

930

Poor TCB Design Hardware OS kernel Operating system User space

Security critical activities

Problem: No clear security layer Part 4  Software

931

Better TCB Design Hardware Security kernel Operating system User space

Security kernel is the security layer Part 4  Software

932

Trusted OS Summary Trust implies reliance  TCB (trusted computing base) is everything in OS we rely on for security  If everything outside TCB is subverted, we still have trusted system  If TCB subverted, security is broken 

Part 4  Software

OS

OS Kernel

Security Kernel

933

NGSCB

Part 4  Software

934

Next Generation Secure Computing Base NGSCB pronounced “n-scub” (the G is silent)  Was supposed to be part of Vista OS 

o Vista was once known as Longhorn… 

TCG (Trusted Computing Group) o Led by Intel, TCG makes special hardware

NGSCB is the part of Windows that will interface with TCG hardware  TCG/NGSCB formerly TCPA/Palladium 

o Why the name changes? Part 4  Software

935

NGSCB The original motivation for TCPA/Palladium was digital rights management (DRM)  Today, TCG/NGSCB is promoted as general security-enhancing technology 

o DRM just one of many potential applications 

Depending on who you ask, TCG/NGSCB is o Trusted computing o Treacherous computing

Part 4  Software

936

Motivation for TCG/NGSCB 

Closed systems: Game consoles, etc.

o Good at protecting secrets (tamper resistant) o Good at forcing people to pay for software o Limited flexibility



Open systems: PCs

o Incredible flexibility o Poor at protecting secrets o Very poor at defending their own software

TCG: closed system security on open platform  “virtual set-top box inside your PC”  Rivest 

Part 4  Software

937

TCG/NGSCB 

TCG provides tamper-resistant hardware o Secure place to store cryptographic key o Key secure from a user with admin privileges!

TCG hardware is in addition to ordinary hardware, not in place of it  PC has two OSs  regular OS and special trusted OS to deal with TCG hardware  NGSCB is Microsoft’s trusted OS 

Part 4  Software

938

NGSCB Design Goals 

Provide high assurance o High confidence that system behaves correctly o Correct behavior even if system is under attack



Provide authenticated operation o Authenticate “things” (software, devices, etc.)



Protection against hardware tampering is concern of TCG, not NGSCB

Part 4  Software

939

NGSCB Disclaimer Specific details are sketchy  Based on available info, Microsoft may not have resolved all of the details 

o Maybe un-resolvable?

What follows: author’s best guesses  This should all become much clearer in the not-too-distant future 

o At least I thought so a couple of years ago…

Part 4  Software

940

NGSCB Architecture Left-hand side (LHS) Right-hand side (RHS) u n t r u s t e d

 

Application

NCA

NCA Application

User space Kernel

Regular OS Nexus

t r u s t e d

Drivers

Nexus is the Trusted Computing Base in NGSCB The NCA (Nexus Computing Agents) talk to Nexus and LHS

Part 4  Software

941

NGSCB 

NGSCB has 4 “feature groups”

1. Strong process isolation o

Processes do not interfere with each other

o

Data protected (tamper resistant hardware)

o

Data to and from I/O protected

o o

“Things” securely authenticated Allows TCB to be extended via NCAs

2. Sealed storage 3. Secure path 4. Attestation 



All are aimed at malicious code 4. also provides (secure) extensibility

Part 4  Software

942

NGSCB Process Isolation Curtained memory  Process isolation and the OS 

o Protect trusted OS (Nexus) from untrusted OS o Isolate trusted OS from untrusted stuff



Process isolation and NCAs

o NCAs isolated from software they do not trust



Trust determined by users, to an extent… o User can disable a trusted NCA o User cannot enable an untrusted NCA

Part 4  Software

943

NGSCB Sealed Storage 

Sealed storage contains secret data

o If code X wants access to secret, a hash of X

must be verified (integrity check of X) o Implemented via symmetric key cryptography

Confidentiality of secret is protected since only accessed by trusted software  Integrity of secret is assured since it’s in sealed storage 

Part 4  Software

944

NGSCB Secure Path  Secure

path for input

 Secure

path for output

o From keyboard to Nexus o From mouse to Nexus o From any input device to Nexus o From Nexus to the screen

 Uses

crypto (digital signatures)

Part 4  Software

945

NGSCB Attestation (1) 

Secure authentication of things

o Authenticate devices, services, code, etc. o Separate from user authentication



Public key cryptography used

o Certified key pair required o Private key not user-accessible o Sign and send result to remote system



TCB extended via attestation of NCAs o This is a major feature!

Part 4  Software

946

NGSCB Attestation (2) 

Public key used for attestation

o However, public key reveals the user identity o Using public keys, anonymity would be lost



Trusted third party (TTP) can be used o TTP verifies signature o Then TTP vouches for signature o Anonymity preserved (except to TTP)



Support for zero knowledge proofs

o Verify knowledge of a secret without revealing it o Anonymity “preserved unconditionally”

Part 4  Software

947

NGSCB Compelling Apps (1) 

Type your Word document in Windows o I.e., the untrusted LHS

Move document to trusted RHS  Read document carefully  Digitally sign the document  Assured that “what you see is what you sign” 

o Practically impossible to get this on your PC

Part 4  Software

948

NGSCB Compelling Apps (2) Digital Rights Management (DRM)  Many DRM problems solved by NGSCB  Protect secret  sealed storage 

o Impossible without something like NGSCB



Scraping data  secure path

o Cannot prevent without something like NGSCB



Positively ID users

o Higher assurance with NGSCB

Part 4  Software

949

NGSCB According to MS All of Windows works on untrusted LHS  User is in charge of… 

o Which Nexus(es) will run on system o Which NCAs will run on system o Which NCAs allowed to identify system, etc.

No external process enables Nexus or NCA  Nexus can’t block, delete, censor data 

o NCA does, but NCAs authorized by user



Nexus is open source

Part 4  Software

950

NGSCB Critics  Many

critics  we consider two  Ross Anderson

o Perhaps the most influential critic o Also one of the harshest critics

 Clark

Thomborson

o Lesser-known critic o Criticism strikes at heart of NGSCB

Part 4  Software

951

Anderson’s NGSCB Criticism (1) 

Digital object controlled by its creator, not user of machine where it resides: Why? o Creator can specify the NCA o If user does not accept NCA, access is denied o Aside: This is critical for, say, MLS applications



If Microsoft Word encrypts all documents with key only available to Microsoft products o Then difficult to stop using Microsoft products

Part 4  Software

952

Anderson’s NGSCB Criticism (2) Files from a compromised machine could be blacklisted to, e.g., prevent music piracy  Suppose everyone at SJSU uses same pirated copy of Microsoft Word 

o If you stop this copy from working on all NGSCB

machines, SJSU users will not use NGSCB o Instead, make all NGSCB machines refuse to open documents created with this copy of Word… o …so SJSU user can’t share docs with NGSCB user…

Part 4  Software

953

Anderson’s NGSCB Criticism (3)  Going

off the deep end…

o “The Soviet Union tried to register and control all typewriters. NGSCB attempts to register and control all computers.” o “In 2010 President Clinton may have two red buttons on her desk  one that sends missiles to China and another that turns off all of the PCs in China…”

Part 4  Software

954

Thomborson’s NGSCB Criticism  NGSCB

acts like a security guard  By passive observation, NGSCB “security guard” can see sensitive info  Former student worked as security guard at apartment complex o By passive observations…

o …he learned about people who lived there

Part 4  Software

955

Thomborson’s NGSCB Criticism  Can

NGSCB spy on you?  According to Microsoft

o Nexus software is public o NCAs can be debugged (for development) o NGSCB is strictly “opt in”

 Loophole?

o Release version of NCA can’t be debugged

and debug and release versions differ

Part 4  Software

956

NGSCB Bottom Line (1) NGCSB: trusted OS on an open platform  Without something similar, PC may lose out 

o Particularly in entertainment-related areas o Copyright holders will not trust PC o Already lost? (iPod, Kindle, iPad, etc., etc.)

With NGSCB, will users lose some control of their PCs?  But NGSCB users must choose to “opt in” 

o If user does not opt in, what has been lost?

Part 4  Software

957

NGSCB Bottom Line (2) NGSCB is a trusted system  Only trusted system can break security 

o By definition, an untrusted system is not

trusted with security critical tasks o Also by definition, a trusted system is trusted with security critical tasks o If untrusted system is compromised, security is not at risk o If a trusted system is compromised (or simply malfunctions), security is at risk

Part 4  Software

958

Software Summary  Software

flaws

o Buffer overflow o Race conditions o Incomplete mediation

 Malware

o Viruses, worms, etc.

 Other

software-based attacks

Part 4  Software

959

Software Summary  Software

Reverse Engineering (SRE)  Digital Rights Management (DRM)  Secure software development o Penetrate and patch o Open vs closed source o Testing

Part 4  Software

960

Software Summary  Operating

systems and security

o How does OS enforce security?  Trusted

OS design principles  Microsoft’s NGSCB o A trusted OS for DRM

Part 4  Software

961

Course Summary 

Crypto

o Symmetric key, public key, hash functions,

cryptanalysis



Access Control

o Authentication, authorization



Protocols

o Simple auth., SSL, IPSec, Kerberos, GSM



Software

o Flaws, malware, SRE, Software development,

trusted OS

Part 4  Software

962

Conclusion

Conclusion

963

Course Summary 

Crypto o Basics, symmetric key, public key, hash

functions and other topics, cryptanalysis



Access Control o Authentication, authorization, firewalls, IDS



Protocols o Simplified authentication protocols o Real-World protocols



Software o Flaws, malware, SRE, development, trusted OS

Conclusion

964

Crypto Basics  Terminology  Classic

ciphers

o Simple substitution o Double transposition o Codebook o One-time pad  Basic Conclusion

cryptanalysis 965

Symmetric Key 

Stream ciphers o A5/1 o RC4



Block ciphers o DES o AES, TEA, etc. o Modes of operation



Data integrity (MAC)

Conclusion

966

Public Key  Knapsack

(insecure)

 RSA  Diffie-Hellman

 Elliptic

curve crypto (ECC)

 Digital

signatures and non-repudiation

 PKI Conclusion

967

Hashing and Other 

Birthday problem



Tiger Hash



HMAC



Clever uses (online bids, spam reduction, …)



Other topics o Secret sharing

o Random numbers o Information hiding (stego, watermarking) Conclusion

968

Advanced Cryptanalysis  Enigma

 RC4

(as used in WEP)

 Linear

and differential cryptanalysis

 Knapsack  RSA

Conclusion

attack (lattice reduction)

timing attacks

969

Authentication 

Passwords o Verification and storage (salt, etc.) o Cracking (math)



Biometrics o Fingerprint, hand geometry, iris scan, etc. o Error rates



Two-factor, single sign on, Web cookies

Conclusion

970

Authorization  History/system

certification  ACLs and capabilities  Multilevel security (MLS) o BLP, Biba, compartments, covert channel,

inference control

 CAPTCHA

 Firewalls  IDS Conclusion

971

Simple Protocols  Authentication

o Using symmetric key o Using public key o Session key o Perfect forward secrecy (PFS) o Timestamps

 Zero Conclusion

knowledge proof (Fiat-Shamir) 972

Real-World Protocols  SSH  SSL  IPSec

o IKE o ESP/AH, tunnel/transport modes, …  Kerberos  Wireless: Conclusion

WEP & GSM 973

Software Flaws and Malware 

Flaws o Buffer overflow

o Incomplete mediation, race condition, etc. 

Malware o Brain, Morris Worm, Code Red, Slammer o Malware detection o Future of malware, botnets, etc.



Other software-based attacks o Salami, linearization, etc.

Conclusion

974

Insecurity in Software  Software

reverse engineering (SRE)

o Software protection  Digital

rights management (DRM)

 Software

development

o Open vs closed source

o Finding flaws (do the math) Conclusion

975

Operating Systems 

OS security functions o Separation o Memory protection, access control



Trusted OS o MAC, DAC, trusted path, TCB, etc.



NGSCB o Technical issues o Criticisms

Conclusion

976

Crystal Ball  Cryptography

o Well-established field o Don’t expect major changes o But some systems will be broken o ECC is a major “growth” area o Quantum crypto may prove worthwhile…

o …but for now it’s mostly (all?) hype Conclusion

977

Crystal Ball 

Authentication o Passwords will continue to be a problem o Biometrics should become more widely used o Smartcard/tokens will be used more



Authorization o ACLs, etc., well-established areas o CAPTCHA’s interesting new topic o IDS is a very hot topic

Conclusion

978

Crystal Ball 

Protocols are challenging



Difficult to get protocols right



Protocol development often haphazard o “Kerckhoffs’ Principle” for protocols? o Would it help?



Protocols will continue to be a source of subtle problem

Conclusion

979

Crystal Ball 

Software is a huge security problem today o Buffer overflows are on the decline… o …but race condition attacks might increase



Virus writers are getting smarter o Botnets o Polymorphic, metamorphic, sophisticated attacks, … o Future of malware detection?



Malware will continue to be a BIG problem

Conclusion

980

Crystal Ball  Other

software issues

o Reverse engineering will not go away o Secure development will remain hard o Open source is not a panacea  OS

issues

o NGSCB (or similar) might change things… o …but, for better or for worse? Conclusion

981

The Bottom Line 

Security knowledge is needed today…



…and it will be needed in the future



Necessary to understand technical issues o The focus of this class



But technical knowledge is not enough o Human nature, legal issues, business issues, ...

o As with anything, experience is helpful Conclusion

982

A True Story 

The names have been changed…



“Bob” took my information security class



Bob then got an intern position o At a major company that does lots of security



One meeting, an important customer asked o “Why do we need signed certificates?” o “After all, they cost money!”



The silence was deafening

Conclusion

983

A True Story 

Bob’s boss remembered that Bob had taken a security class o So he asked Bob, the lowly intern, to answer o Bob mentioned man-in-the-middle attack on SSL



Customer wanted to hear more o So, Bob explained MiM attack in some detail



The next day, “Bob the lowly intern” became “Bob the fulltime employee”

Conclusion

984

Appendix

Appendix

985

Appendix  Networking

basics

o Protocol stack, layers, etc.



Math basics

o o o o

Modular arithmetic Permutations Probability Linear algebra

Appendix

986

Networking Basics There are three kinds of death in this world. There's heart death, there's brain death, and there's being off the network.  Guy Almes

Appendix

987

Network 

Includes o Computers o Servers o Routers

o Wireless devices o Etc. 

Purpose is to transmit data Appendix

988

Network Edge  

Network edge includes… …Hosts o Computers

o Laptops o Servers o Cell phones o Etc., etc. Appendix

989

Network Core 

Network core consists of o Interconnected

mesh of routers



Purpose is to move data from host to host

Appendix

990

Packet Switched Network 

Telephone network is/was circuit switched o For each call, a dedicated circuit established

o Dedicated bandwidth 

Modern data networks are packet switched o Data is chopped up into discrete packets o Packets are transmitted independently o No dedicated circuit is established

+ More efficient bandwidth usage - But more complex than circuit switched Appendix

991

Network Protocols Study of networking focused on protocols  Networking protocols precisely specify “communication rules”  Details are given in RFCs 

o RFC is essentially an Internet standard

Stateless protocols do not “remember”  Stateful protocols do “remember”  Many security problems related to state 

o E.g., DoS is a problem with stateful protocols Appendix

992

Protocol Stack 

Application layer protocols o HTTP, FTP, SMTP, etc.



Transport layer protocols o TCP, UDP



Network layer protocols o IP, routing protocols



Link layer protocols o Ethernet, PPP



application

user space

transport

OS

network link

NIC card

physical

Physical layer

Appendix

993

Layering in Action data

application

router

transport

transport

host  

data

application

network

network

network

link

link

link

physical

physical

physical

host

At source, data goes “down” the protocol stack Each router processes packet “up” to network layer o That’s where routing info lives

 

Router then passes packet down the protocol stack Destination processes packet up to application layer o That’s where the application data lives Appendix

994

Encapsulation  

X = application data at source As X goes down protocol stack, each layer adds header information: o Application layer: (H, X)

data X application transport network

o Transport layer: (H, (H, X)) o Network layer: (H, (H, (H, X))) o Link layer: (H, (H, (H, (H, X)))) 

Header has info required by layer



Note that app data is on the “inside” Appendix

link physical packet (H,(H,(H,(H,X)))) 995

Application Layer 

Applications o For example, Web browsing, email, P2P, etc. o Applications run on hosts o To hosts, network details should be transparent



Application layer protocols o HTTP, SMTP, IMAP, Gnutella, etc., etc.



Protocol is only one part of an application o For example, HTTP only a part of web browsing

Appendix

996

Client-Server Model 

Client o “speaks first”



Server o responds to client’s request



Hosts are clients or servers



Example: Web browsing o You are the client (request web page) o Web server is the server

Appendix

997

Peer-to-Peer Paradigm  Hosts  For

act as clients and servers

example, when sharing music

o You are client when requesting a file o You are a server when someone downloads a file from you  In

P2P, how does client find server?

o Many different P2P models for this Appendix

998

HTTP Example HTTP request HTTP response



HTTP  HyperText Transfer Protocol



Client (you) requests a web page



Server responds to your request

Appendix

999

initial session

cookie

Web Cookies

cookie

Cookie database

later session 

HTTP is stateless  cookies used to add state



Initially, cookie sent from server to browser



Browser manages cookie, sends it to server



Server uses cookie database to “remember” you

Appendix

1000

Web Cookies  Web

cookies used for…

o Shopping carts, recommendations, etc. o A very (very) weak form of authentication  Privacy

concerns

o Web site can learn a lot about you

o Multiple web sites could learn even more Appendix

1001

SMTP   

SMTP used to deliver email from sender to recipient’s mail server Then POP3, IMAP or HTTP (Web mail) used to get messages from server As with many application protocols, SMTP commands are human readable Recipient

Sender SMTP

Appendix

SMTP

POP3

1002

Spoofed email with SMTP User types the red lines: > telnet eniac.cs.sjsu.edu 25 220 eniac.sjsu.edu HELO ca.gov 250 Hello ca.gov, pleased to meet you MAIL FROM: 250 [email protected]... Sender ok RCPT TO: 250 [email protected] ... Recipient ok DATA 354 Enter mail, end with "." on a line by itself It is my pleasure to inform you that you are terminated . 250 Message accepted for delivery QUIT 221 eniac.sjsu.edu closing connection Appendix

1003

Application Layer 

DNS  Domain Name Service o Convert human-friendly names such as

www.google.com into 32-bit IP address

o A distributed hierarchical database 

Only 13 “root” DNS server clusters o Essentially, a single point of failure for Internet o Attacks on root servers have succeeded… o …but, attacks did not last long enough (yet)

Appendix

1004

Transport Layer   

The network layer offers unreliable, “best effort” delivery of packets Any improved service must be provided by the hosts

Transport layer: 2 protocols of interest o TCP  more service, more overhead o UDP  less service, less overhead



TCP and UDP run on hosts, not routers

Appendix

1005

TCP 

TCP assures that packets… o Arrive at destination o Are processed in order o Are not sent too fast for receiver: flow control



TCP also attempts to provide… o Network-wide congestion control



TCP is connection-oriented o TCP contacts server before sending data o Orderly setup and take down of “connection” o But no true connection, only logical “connection”

Appendix

1006

TCP Header 0

8

bits 16

24

31

Source Port

Offset

Destination Port Sequence Number Acknowledgement Number reserved U A P R S F Window Checksum Urgent Pointer Options Padding Data (variable length)

Source and destination port  Sequence number  Flags (ACK, SYN, RST, etc.)  Header usually 20 bytes (if no options) 

Appendix

1007

TCP Three-Way Handshake SYN request SYN-ACK

ACK (and data)



SYN  synchronization requested



SYN-ACK  acknowledge SYN request



ACK  acknowledge SYN-ACK (send data)



Then TCP “connection” established o Connection terminated by FIN or RST

Appendix

1008

Denial of Service Attack 



The TCP 3-way handshake makes denial of service (DoS) attacks possible Whenever SYN packet is received, server remembers this “half-open” connection o Remembering consumes resources o Too many half-open connections and server’s

resources will be exhausted, and then…

o …server can’t respond to legitimate connections 

This occurs because TCP is stateful

Appendix

1009

UDP 

UDP is minimalist, “no frills” service o No assurance that packets arrive o No assurance packets are in order, etc., etc.



Why does UDP exist? o More efficient (header only 8 bytes) o No flow control to slow down sender o No congestion control to slow down sender



If packets sent too fast, will be dropped o Either at intermediate router or at destination o But in some apps this may be OK (audio/video)

Appendix

1010

Network Layer 

Core of network/Internet o Interconnected mesh of routers



Purpose of network layer o Route packets through this mesh



Network layer protocol of interest is IP o Follows a best effort approach

IP runs in every host and every router  Routers also run routing protocols 

o Used to determine the path to send packets o Routing protocols: RIP, OSPF, BGP, … Appendix

1011

IP Addresses 

IP address is 32 bits



Every host has an IP address



Big problem  Not enough IP addresses! o Lots of tricks used to extend address space



IP addresses given in dotted decimal notation o For example: 195.72.180.27

o Each number is between 0 and 255 

Usually, a host’s IP address can change

Appendix

1012

Socket Each host has a 32 bit IP address  But, many processes can run on one host 

o E.g., you can browse web, send email at same time

How to distinguish processes on a host?  Each process has a 16 bit port number 

o Numbers below 1024 are “well-known” ports

(HTTP is port 80, POP3 is port 110, etc.)

o Port numbers above 1024 are dynamic (as needed) 

IP address + port number = socket o Socket uniquely identifies process, Internet-wide

Appendix

1013

Network Address Translation  Network

Address Translation (NAT)

o Trick to extend IP address space  Use

one IP address (different port numbers) for multiple hosts o “Translates” outside IP address (based on port number) to inside IP address

Appendix

1014

NAT-less Example source 11.0.0.1:1025 destination 12.0.0.1:80

Web server

IP: 12.0.0.1 Port: 80

Appendix

source 12.0.0.1:80 destination 11.0.0.1:1025 Alice IP: 11.0.0.1 Port: 1025

1015

NAT Example src 11.0.0.1:4000 dest 12.0.0.1:80

src 10.0.0.1:1025 dest 12.0.0.1:80

src 12.0.0.1:80 dest 11.0.0.1:4000

src 12.0.0.1:80 dest 10.0.0.1:1025

Web server

IP: 12.0.0.1

Appendix

Firewall IP: 11.0.0.1 NAT Table 4000 10.0.0.1:1025

Alice IP: 10.0.0.1

1016

NAT: The Last Word  Advantage(s)?

o Extends IP address space o One (or a few) IP address(es) can be shared by many users  Disadvantage(s)?

o End-to-end security is more difficult

o Might make IPSec less effective (IPSec discussed in Chapter 10) Appendix

1017

IP Header



IP header has necessary info for routers



Time to live (TTL) limits number of “hops”



Fragmentation information (see next slide)

o E.g., source and destination IP addresses o So packets can’t circulate forever

Appendix

1018

IP Fragmentation fragmented

re-assembled

Each link limits maximum size of packets  If packet is too big, router fragments it  Re-assembly occurs at destination 

Appendix

1019

IP Fragmentation 

One packet becomes multiple packets



Packets reassembled at destination o Prevents multiple fragmentation/reassemble



Fragmentation is a security issue… o Fragments may obscure real purpose of packet o Fragments can overlap when reassembled o Must reassemble packet to fully understand it o Lots of work for firewalls, for example

Appendix

1020

IPv6 

Current version of IP is IPv4



IPv6 is a “new-and-improved” version of IP



IPv6 is “bigger and better” than IPv4 o Bigger addresses: 128 bits

o Better security: IPSec 

How to migrate from IPv4 to IPv6? o Unfortunately, nobody thought about that…



So IPv6 has not really taken hold (yet?)

Appendix

1021

Link Layer 



Link layer sends packet from one node to next Links can be different o Wired o Wireless o Ethernet o Point-to-point… Appendix

1022

Link Layer  On

host, implemented in adapter: Network Interface Card (NIC) o Ethernet card, wireless 802.11 card, etc. o NIC is “semi-autonomous” device

 NIC

is (mostly) out of host’s control

o Implements both link and physical layers

Appendix

1023

Ethernet 

Ethernet is a multiple access protocol



Many hosts access a shared media o On a local area network, or LAN



With multiple access, packets can “collide” o Data is corrupted and packets must be resent



How to efficiently deal with collisions in distributed environment? o Many possibilities, ethernet is most popular



We won’t discuss details here…

Appendix

1024

Link Layer Addressing IP addresses live at network layer  Link layer also needs addresses  Why? 

o MAC address (LAN address, physical address) 

MAC address o 48 bits, globally unique o Used to forward packets over one link



Analogy… o IP address is like your home address o MAC address is like a social security number

Appendix

1025

ARP  



Address Resolution Protocol (ARP)

Used by link layer  given IP address, find corresponding MAC address Each host has ARP table, or ARP cache o Generated automatically o Entries expire after some time (about 20 min)

o ARP used to find ARP table entries

Appendix

1026

ARP 

ARP is stateless



ARP can send request and receive reply



Reply msgs used to fill/update ARP cache IP: 111.111.111.001

IP: 111.111.111.002

LAN MAC: AA-AA-AA-AA-AA-AA

111.111.111.002

BB-BB-BB-BB-BB-BB

Alice’s ARP cache Appendix

MAC: BB-BB-BB-BB-BB-BB

111.111.111.001

AA-AA-AA-AA-AA-AA

Bob’s ARP cache 1027

ARP Cache Poisoning ARP is stateless, so…  Accept “reply”, even if no request sent 

Trudy

111.111.111.003 CC-CC-CC-CC-CC-CC

ARP “reply”

ARP “reply”

111.111.111.001 CC-CC-CC-CC-CC-CC

111.111.111.002 CC-CC-CC-CC-CC-CC

LAN

111.111.111.001 AA-AA-AA-AA-AA-AA

111.111.111.002 BB-BB-BB-BB-BB-BB

111.111.111.002 CC-CC-CC-CC-CC-CC BB-BB-BB-BB-BB-BB

111.111.111.001 AA-AA-AA-AA-AA-AA CC-CC-CC-CC-CC-CC

Alice’s ARP cache

Bob’s ARP cache



Host CC-CC-CC-CC-CC-CC is man-in-the-middle

Appendix

1028

Math Basics 7/5ths of all people don’t understand fractions.  Anonymous

Appendix

1029

Modular Arithmetic

Appendix

1030

Clock Arithmetic 

For integers x and n, “x mod n” is the remainder when we compute x  n o We can also say “x modulo n”



Examples o o o o o

33 mod 6 = 3 33 mod 5 = 3 7 mod 6 = 1 51 mod 17 = 0 17 mod 6 = 5

0 1

5 number “line” mod 6

2

4 3 Appendix

1031

Modular Addition 



Notation and fun facts o o o o

7 mod 6 = 1 7 = 13 = 1 mod 6 ((a mod n) + (b mod n)) mod n = (a + b) mod n ((a mod n)(b mod n)) mod n = ab mod n

o o o o o

3 + 5 = 2 mod 6 2 + 4 = 0 mod 6 3 + 3 = 0 mod 6 (7 + 12) mod 6 = 19 mod 6 = 1 mod 6 (7 + 12) mod 6 = (1 + 0) mod 6 = 1 mod 6

Addition Examples

Appendix

1032

Modular Multiplication  Multiplication

Examples

o 3  4 = 0 mod 6 o 2  4 = 2 mod 6 o 5  5 = 1 mod 6

o (7  4) mod 6 = 28 mod 6 = 4 mod 6 o (7  4) mod 6 = (1  4) mod 6 = 4 mod 6

Appendix

1033

Modular Inverses 

Additive inverse of x mod n, denoted – x mod n, is the number that must be added to x to get 0 mod n o -2 mod 6 = 4, since 2 + 4 = 0 mod 6



Multiplicative inverse of x mod n, denoted x-1 mod n, is the number that must be multiplied by x to get 1 mod n o 3-1 mod 7 = 5, since 3  5 = 1 mod 7

Appendix

1034

Modular Arithmetic Quiz Q: What is -3 mod 6?  A: 3  Q: What is -1 mod 6?  A: 5  Q: What is 5-1 mod 6?  A: 5  Q: What is 2-1 mod 6?  A: No number works!  Multiplicative inverse might not exist 

Appendix

1035

Relative Primality and y are relatively prime if they have no common factor other than 1  x-1 mod y exists only when x and y are relatively prime  If it exists, x-1 mod y is easy to compute using Euclidean Algorithm x

o We won’t do the computation here o But, an efficient algorithm exists Appendix

1036

Totient Function 

(n) is “the number of numbers less than n that are relatively prime to n” o Here, “numbers” are positive integers



Examples o o o o o

Appendix

(4) = 2 since 4 is relatively prime to 3 and 1 (5) = 4 since 5 is relatively prime to 1,2,3,4 (12) = 4 (p) = p-1 if p is prime (pq) = (p-1)(q-1) if p and q prime

1037

Permutations

Appendix

1038

Permutation Definition  Let

S be a set  A permutation of S is an ordered list of the elements of S o Each element of S appears exactly once

 Suppose

S = {0,1,2,…,n-1}

o Then the number of perms is… o n(n-1)(n-2)    (2)(1) = n!

Appendix

1039

Permutation Example  Let

S = {0,1,2,3}  Then there are 24 perms of S  For example, o (3,1,2,0) is a perm of S o (0,2,3,1) is a perm of S, etc.  Perms

Appendix

are important in cryptography

1040

Probability Basics

Appendix

1041

Discrete Probability  We

only require some elementary facts  Suppose that S={0,1,2,…,N1} is the set of all possible outcomes  If each outcome is equally likely, then the probability of event E  S is o P(E) = # elements in E / # elements in S

Appendix

1042

Probability Example  For

example, suppose we flip 2 coins  Then S = {hh,ht,th,tt} o Suppose X = “at least one tail” = {ht,th,tt} o Then P(X) = 3/4  Often,

it’s easier to compute

o P(X) = 1  P(complement of X)

Appendix

1043

Complement  Again,

suppose we flip 2 coins  Let S = {hh,ht,th,tt}

o Suppose X = “at least one tail” = {ht,th,tt} o Complement of X is “no tails” = {hh}

 Then

o P(X) = 1  P(comp. of X) = 1  1/4 = 3/4

 We

Appendix

make use of this trick often!

1044

Linear Algebra Basics

Appendix

1045

Vectors and Dot Product  Let

 be the set of real numbers  Then v  n is a vector of n elements  For example o v = [v1,v2,v3,v4] = [2,1, 3.2, 7]  4

 The

dot product of u,v  n is

o u  v = u1v1 + u2v2 +… + unvn

Appendix

1046

Matrix A

matrix is an n x m array  For example, the matrix A is 2 x 3

 The

element in row i column j is aij  We can multiply a matrix by a number

Appendix

1047

Matrix Addition  We

can add matrices of the same size

 We

can also multiply matrices, but this is not so obvious  We do not simply multiply the elements Appendix

1048

Matrix Multiplication  Suppose

A is m x n and B is s x t  Then C=AB is only defined if n=s, in which case C is m x t  Why?  The element cij is the dot product of row i of A with column j of B

Appendix

1049

Matrix Multiply Example  Suppose

 Then

 And Appendix

AB is undefined 1050

Matrix Multiply Useful Fact Consider AU = B where A is a matrix and U and B are column vectors  Let a1,a2,…,an be columns of A and u1,u2,…,un the elements of U  Then B = u1a1 + u2a2 + … + unan 

Example:

[ 31 45] [ 26 ]

Appendix

=

2[ ] 3 1

+

6

[ ] 4 5

=

[ 30 ] 32 1051

Identity Matrix A

matrix is square if it has an equal number of rows and columns  For square matrices, the identity matrix I is the multiplicative identity o AI = IA = A

 The

Appendix

3 x 3 identity matrix is

1052

Block Matricies Block matrices are matrices of matrices  For example 

We can do arithmetic with block matrices  Block matrix multiplication works if individual matrix dimensions “match” 

Appendix

1053

Block Matrix Mutliplication Block matrices multiplication example  For matrices 



We have



Where X = U+CT and Y = AU+BT

Appendix

1054

Linear Independence  Vectors

u,v  n linearly independent if au + bv = 0 implies a=b=0  For example,

 Are Appendix

linearly independent 1055

Linear Independence  Linear

independence can be extended to more than 2 vectors  If vectors are linearly independent, then none of them can be written as a linear combination of the others o None of the independent vectors is a sum of multiples of the other vectors

Appendix

1056