Department of Computer Science - Wake Forest University

Cryptography, Authentication, and Integrity CSC 348·648

WAKE FOREST U N I V E R S I T Y

Department of Computer Science

Fall 2014

Authentication • We have discussed encryption to protect against passive attacks – Providing confidentiality by encrypting messages

• Can also provide authentication and integrity using encryption – Verify the sender and the message

– Want to answer: Is this who I think it is? (authentication) and Have the contents of the message been changed? (integrity)

E. W. Fulp

CSC 348·648

Fall 2014

1

Shared Secret Key Authentication • Assume Alice and Bob share a secret key kAB

– To establish the key they could use the telephone, etc...

• The protocol will use a challenge-response technique

Alice

2 3

RB

KAB (RB) 4

5

A

Bob

1

RA

KAB (RA)

– Alice first sends identity (A) to Bob – Bob responds with a challenge, a RN (rB ) in plantext – Alice returns the RN encrypted using kAB (the response)

E. W. Fulp

CSC 348·648

Fall 2014

2

Fall 2014

3

– At this point Bob knows it’s Alice, but Alice knows nothing What is one possible attack by Trudy? – Alice selects a RN (rA ) and sends it to Bob – Bob returns rA encrypted using kAB (his response) – They can select a new key and establish a separate session • The previous can be condensed to the following steps

2

A, RA

RB, KAB (RA)

3

Bob

Alice

1

KAB (RB)

Is the challenge-response protocol immune from attack?

E. W. Fulp

CSC 348·648

Trudy’s Revenge, Part 2 • Under certain circumstances, Trudy can apply a reflection attack – Assume Bob allows multiple simultaneous sessions

• Steps of the attack are 1

First session

3 4

A, RT

RB, KAB (RT) A, RB

Bob

Trudy

2

Second session

RB2, KAB (RB) 5

KAB (RB)

First session

– Trudy claims she is Alice and sends Bob A, rT – Bob responds with his own challenge rB – Trudy is stuck, she does not know kAB for a response

E. W. Fulp

CSC 348·648

Fall 2014

4

– Trudy opens a second session, supplying rB as her challenge – Bob replies with the kAB encrypted rB – Trudy now has the response for the first session... • The moral of the story is designing a proper authentication protocol ain’t easy • 3 general rules

1. Have initiator prove identity before responder Was this the case in the first method?

2. Have initiator and responder use different keys for proof 3. Have initiator and responder draw challenges from different sets What? Man-in-the-middle versus reflection, do both attack the same thing (privacy, integrity, or availability)?

E. W. Fulp

CSC 348·648

Fall 2014

5

Key Distribution Center • Establishing a secret key with a stranger almost worked – However, such solutions typically do not scale – To talk to n people, you need n keys • An alternative is a trusted Key Distribution Center (KDC) – Controls authentication and session key management

A, KA (B, KS)

2

Bob

Alice

1

KDC

• A simple example, again assume Alice wants to talk to Bob KB (A, KS)

– Alice selects a session key kS and tells the KDC she wishes to talk to Bob E. W. Fulp

CSC 348·648

Fall 2014

6

– Alice encrypts the session key using another key (kA ) only she the KBC knows – KBC decrypts the message and sends Bob the session key encrypting it with another key (kB ) only the KBC and Bob knows Has authentication occurred? • Achtung! Symmetric key solutions rely on session keys (kAB )

– Key is only for a session between the two parties (Alice and Bob) – If Alice wanted to contact Bob, KDC does not give Alice kB (the secret key established between Bob and the KDC) and/or Bob kA Why? Won’t knowing kA and/or kB provide authentication?

E. W. Fulp

CSC 348·648

Fall 2014

7

Trudy’s Revenge, Part 3 • Unfortunately, the simple KDC system has a serious flaw

– Assume Bob is Alice’s banker, and Alice owes Trudy money – Alice establishes a secret key with Bob, then sends Bob an encrypted request for a money transfer to Trudy – Trudy copies the second message from the KDC system (ekB (A, ks )) and the money request message that follows

– Trudy then replays the two messages to Bob over and over, ... • This is a replay attack

– One solution is to include a timestamp (freshness);however, this requires clock synchronization – Another solution is a nonce, a unique one-time message number, so users would need to remember (and not reuse) nonce values... perhaps there is a simpler approach [insert laugh track here]

E. W. Fulp

CSC 348·648

Fall 2014

8

Needham-Schroeder Authentication • A multiway challenge response protocol

– A KDC-based systems that includes nonces

• Authentication steps are as follows RA, A, B

KA (RA, B, KS, KB(A, KS)) 3

Bob

Alice

2

KDC

1

KB(A, KS), KS (RA2) 4

KS (RA2 –1), RB 5

KS (RB –1)

1. Alice tells the KDC she wants to talk to Bob, message include a large random number (rA ) as a nonce 2. KDC sends Alice message with rA , a session key (ks ), and ticket – The ticket is kB (A, ks ) (encrypted with Bob’s key) E. W. Fulp

CSC 348·648

Fall 2014

9

1

KDC

RA, A, B

3

Bob

KA (RA, B, KS, KB(A, KS))

Alice

2

KB(A, KS), KS (RA2) 4

KS (RA2 –1), RB 5

KS (RB –1)

3. Alice sends the ticket and a new random number rA2 encrypted with ks to Bob 4. Bob responds with rA2 − 1 and rB encrypted with session key Why not return rA2 ?

5. Alice knows this is Bob, she returns rB − 1

6. Bob knows this is Alice

• Actually, this protocol is still susceptible...

– Variations are used in commercial products

E. W. Fulp

CSC 348·648

Fall 2014

10

Kerberos • Kerberos is a Needham-Schoerder variant

– Designed by MIT to allow workstations to access resources – Named after multi-headed guard dog in Greek Mythology

• Involves two additional types of servers

– Authentication Server (AS) - verifies user during login

1

KB (A, KAB ), KAB (t) 6 KAB (t +1)

Get a ticket

Bob

Alice

KTGS (A, KS), B, KS (t) KS (B, KAB), KB (A, KAB ) 5

E. W. Fulp

Login

KA (KS, KTGS (A, KS)) 3

4

A

TGS

2

AS

– Ticket-Granting Server (TGS) - issues proof of identity tickets

Do the work

CSC 348·648

Fall 2014

11

Login


4



Get a ticket

Bob

Alice

A

TGS

2

AS

1

Do the work

• Assume Alice is at a workstation and wants to contact Bob

1. Alice types in her login ID, which sends her name to the AS 2. The AS responds with a session key and ticket (kT GS (A, kS )), encrypted using Alice’s secret key – The workstation asks for Alice’s password to generate kA – Using kA the session key (kS ) and TGS ticket obtained

3. Alice wants to contact Bob, sends TGS a request for a ticket with Bob – Message includes kT GS (A, ks ) (proves Alice’s ID), Bob’s ID, and ks (t) (timestamp) CSC 348·648

1

12

Login



Get a ticket

Bob

Alice

Fall 2014


4

A

TGS

2

AS

E. W. Fulp

Do the work

4. TGS responds with session key kAB – One is encrypted with kS , the other with kB Why encrypt the same thing twice? 5. Alice encrypted session key (kAB ) to Bob – kAB encrypted with Bob’s key (kB only shared between TGS and Bob) – Message includes a timestamp • If Alice wants to contact someone else, she now starts with the TGS since there is no need to authenticate again (unless she logs out) E. W. Fulp

CSC 348·648

Fall 2014

13

Authentication Using Public-Key • Mutual authentication can be achieved using public-key

– Assume Alice and Bob already know each other’s public key – This is a non-trival assumption

– They want to establish a session, then use secrete key (which is typically much faster than public key) • Establishing a secret key would have the following steps

– Alice encrypts her identity and RN (rA ) using Bob’s public key 2

EB (A, RA)

EA (RA, RB, KS) 3

Bob

Alice

1

KS (RB)

– Bob decrypts and replies with rA , rB , and ks encrypted with Alice’s public key E. W. Fulp

CSC 348·648

Fall 2014

14

Fall 2014

15

– Alice decrypts and verifies that rA is correct What can Trudy do? • The only true weakness of this approach is the public key – How are public keys distributed in a safe fashion?

– This is one area of research, Public Key Infrastructure (PKI)

E. W. Fulp

CSC 348·648

Authenticity • Authenticity of many legal documents is determined by a signature – Notary public is used and photocopies do not count

– For computer documents an alternative solution is needed • Need a system where one party can send a signed message to another in such a way that – Receiver can verify the claimed identity of sender – Sender cannot repudiate the contents of the message – Receiver cannot have created the message • This requirements are provided using digital signatures

– Integrity - indicate whether a message has been altered – Authentication - indicate the person who signed

E. W. Fulp

CSC 348·648

Fall 2014

16

Fall 2014

17

Private Key Authentication • It is possible to use secret key encryption for authentication – The key is known only to authorized people (not trival)

– Only authorized people can encrypt and decrypt What about replay attack? How do you prevent? Can either party refute a message?

E. W. Fulp

CSC 348·648

Public-Key Signatures • Assume the public-key algorithm has the property

– d(e(p)) = p as well as e(d(p)) = p (RSA has this property )

• If the above condition is true

– Alice can sign and send the message eB (dA (p)), where Alice uses her private decryption key dA and Bob’s public key eB – Bob receives the message and transforms using his private key, yielding dA (p), he then decrypts this using eA Transmission line

Alice's computer

P

Bob's public key, EB

Alice's private key, DA

DA(P)

Bob's computer

Alice's public key, EA

Bob's private key, DB

EB (DA(P))

P

DA(P)

E. W. Fulp

CSC 348·648

Fall 2014

18

Fall 2014

19

• What happens if Alice denies sending p to Bob? – Bob produces p and dA (p) in court

– Judge can verify the message was encrypted by dA by applying eA to it What is Alice’s final plea in court to get out of this? • In principle, any public-key algorithm can be used for signatures – The de facto standard is RSA

– In 1991 the NIST proposed using a variant of El Gamma for their Digital Signature Standard

E. W. Fulp

CSC 348·648

Message Digests • A complaint of signature methods is they couple disjoint functions – Authentication and secrecy

– Often authentication is needed, but not secrecy – Encryption is often slow • An alternative is the one-way hash

– Takes an arbitrarily long p and generates fixed size message – No key is needed So where does the complexity lie? – There is no decryption (hence the one-way name) Without decryption how do you verify?

E. W. Fulp

CSC 348·648

Fall 2014

20

Fall 2014

21

• Four objectives of one-way hash

1. Given p, easy to compute md(p) 2. Given md(p), effectively impossible to find p

3. Small change in p causes many bits to change in md(p) 4. No two reasonable messages have same message digest • Using a message digest with public key encryption – Alice would send [p, dA (md(p))]

P, DA (MD (P))

Bob

Alice

– Bob would compute md(p) and compare with received digest

Does MD provide integrity and/or authenticity?

E. W. Fulp

CSC 348·648

Simple Hash Function • All hash functions have a similar format

– Input is seen as a series of n bit blocks – Input is processed one block at a time iteratively – Result is an n bit hash value

• Longitudinal redundancy check is one example – Bit-by-bit exclusive OR of every block

ci = bi,1 ⊕ bi,2 ⊕ ... ⊕ bi,m Where ci is the ith bit of the hash code, m is the number of n bit blocks in the input, and bi,j is the ith bit of the j th block

E. W. Fulp

CSC 348·648

bit 1

bit 2

...

bit n

block 1

b1,1

b2,1

...

bn,1

block 2

b1,2 . . .

b2,2 . . .

... . . .

bn,2 . . .

block m

b1,m

b2,m

...

bn,m

hash

c1

c2

...

cn

Fall 2014

22

Fall 2014

23

How many bits can change and still have a valid hash? More suitable for error detection in transmission, why? • Not a good one-way-hash

– Single input bit change should change multiple hash bits

E. W. Fulp

CSC 348·648

MDn • There are a variety of message digest algorithms called MDn – Where n represents different methods, currently MD5

• MDn methods tend to have more in common with DES than RSA – Do not have a formal mathematical basis

– Rely on complexity of the algorithm for strength – Every output bit is affected by every input bit • The basic operation (MD4, MD5, and SHA)

– Operates on 512 bits at a time (pad if necessary) – Digest calculation begins with initial constant – Value is combined with first 512 bits to produce a new value – Computation repeats until the final value created

E. W. Fulp

CSC 348·648

Initial "digest" (constant)

Fall 2014

24

Message (padded) 512 bits 512 bits

...

512 bits

Transform

...

Transform

Transform

Message digest

• Main ingredient of MD5 is the transform

– Inputs are the current 128 bit digest and 512 bits from message

– Operates on 32 bit words so the current digest is (d0 , d1 , d2 , d3 ) – The current message block is (m0 , ..., m15 )

E. W. Fulp

CSC 348·648

Fall 2014

25

• Basic transform (compression module) can be divided into 4 passes – The first pass consists of 16 steps

d0 = (d0 + f (d1 , d2 , d3 ) + m0 + t1 ) ← 7

d3 = (d3 + f (d0 , d1 , d2 ) + m1 + t2 ) ← 12

d2 = (d3 + f (d3 , d0 , d1 ) + m2 + t3 ) ← 17

d1 = (d1 + f (d2 , d3 , d0 ) + m3 + t4 ) ← 22 d0 = (d0 + f (d1 , d2 , d3 ) + m4 + t5 ) ← 7

d1 = (d3 + f (d0 , d1 , d2 ) + m5 + t6 ) ← 12 .. . where f (·) is a set of bitwise operations and ti is a constant – Remaining passes have a similar form

E. W. Fulp

CSC 348·648

Fall 2014

26

SHA-1 and SHA-2 • Secure Hash Algorithm-n (SHA-n) was originally designed by the CIA – Processes 512 bit blocks and produces 160 bit output Start of message

512-Bit block

32-Bit word

M0

H0

W0

M1

H1

W1

M2

H2

W2

Padding Mn-1

H3 H4

padded message

output

W79 word array

• Starts with padding the message by adding a 1 bit to the end and as many 0 bits as necessary (make multiple lengths of 512) • The original length of the message is ORed into the lower 64 bits • During computations SHA-1 maintains 5 32-bit variables, H0 − H4 E. W. Fulp

CSC 348·648

Fall 2014

27

• Each block M0 through Mn−1 is processed

– For the block, the 16 words are copied in to W – The remaining 64 words in W are Wi = S 1 (Wi−3 ⊕ Wi−8 ⊕ Wi−14 ⊕ Wi−16 ),

16 ≤ i ≤ 79

where S i is a left circular shift – Five local variables are created and initialized with H0 through H4 , processed (several XORs), then added back to H0 through H4 – Process repeats for the next block, keeping the current H0 − H4 • Once all blocks processed, the H0 − H4 is the hash • Newer versions (SHA-2) can provide 224, 256, 384, and 512 bits So why would I want longer message digests?

E. W. Fulp

CSC 348·648

Fall 2014

28

Happy Birthday “How many students do you need in a class before the probability of having two students with the same birthday exceeds 50%?” • Assume 23 students in the class are arranged in a line – The first person has 22 chances to find a match

– If no match, then the second person has 21 chances to match, ... – Therefore there are 22 + 21 + 20 + . . . + 1 = 253 pairs, the general equation is n(n−1) pairs 2 – Each pair has 1/365 chance of matching, therefore there is a greater than 50% chance when you have 23 students • General equation is p ≈ 1 − e

E. W. Fulp

−n2 2d

CSC 348·648

Fall 2014

29

Shared Birthdays

Probability of match

1 Any match Specific match

0.8 0.6 0.4 0.2 0 0

100

200

300

Number of people

• Note, we are finding any two students that match, which is not the same as finding a match for a certain birthday (and less likely)

E. W. Fulp

CSC 348·648

Fall 2014

30

Birthday Attack

n messages

k digests

• Consider a mapping between inputs to outputs (as done with a hash) – Assume n inputs (people, messages, etc...) and k outputs input pairs (birthdays, digests, etc...), therefore n(n−1) 2 n(n−1) 2

> k then there’s a good chance of a match √ – Rearranging, if n > k then a match is likely

– If

E. W. Fulp

CSC 348·648

Fall 2014

31

• Now consider a message digest √ – Only need create k messages to find a matching pair (kinda) – If the digest is m bits, there are k = 2m possible digests √ m – Only generate 2m = 2 2 messages to have great than 50% chance What assumptions are we making regarding the digest algorithm? Is this analysis best case or worst case? • Every message digest algorithm is susceptible to this attack, the best prevention is to increase the number of digest bits...

E. W. Fulp

CSC 348·648

Fall 2014

32

Hash Security Summary Below are publicly known attacks against popular hash methods. Rows in red are demonstrated attacks, while yellow rows are theoretical breaks. • Collision attack (find two arbitrary inputs that will produce the same hash value)

E. W. Fulp

Hash

Security Claim

Best Attack

Attack Date

Notes

MD5

264

218 time

3/25/2013

This attack takes seconds on a regular PC.

SHA-1

280

261 time

8/17/2005

Feasible given large amounts of computation power.

SHA256

2128

24 of 64 rounds (228.5 )

11/25/2008

SHA512

2256

24 of 80 rounds (232.5 )

11/25/2008

MD2

264

263.3 time, 252 memory

2009

Slightly less computationally expensive than a birthday attack, but for practical purposes, memory requirements make it more expensive.

MD4

264

3 operations

3/22/2007

Finding collisions almost as fast as verifying them.

CSC 348·648

Fall 2014

33

• Chosen prefix collision attack (attacker can choose two arbitrarily different documents, and then append different calculated values that result in the whole documents having an equal hash value) Hash

Security Claim

Best Attack

Attack Date

Notes

MD5

264

239 time

6/16/2005

This attack takes hours on a regular PC.

SHA-1

280

263 time

8/22/2006

Extends Wang’s SHA-1 collision attack to partially chosen prefix collisions.

SHA256

2128

SHA512

2256

E. W. Fulp

CSC 348·648

Fall 2014

Algorithm

Output size (bits)

Internal state size

Block size

Length size

Word size

Rounds

Collision

Second preimage

GOST

256

256

256

256

32

256

Yes (2105 )

Yes (2192 )

Yes (2192 )

HAVAL

256/224/192/160/128

256

1,024

64

32

160/128/96

Yes

No

No

MD2

128

384

128

-

32

864

Yes (263.3 )

No

Yes (273 )

MD4

128

128

512

64

32

48

Yes (3)

Yes (264 )

Yes (278.4 )

MD5

128

128

512

64

32

64

Yes (220.96 )

No

Yes (2123.4 )

Yes

No

No

With flaws (2352 or 2704 )

No

No

PANAMA

256

8,736

256

RadioGat´ un

Up to 608/1,216

58 words

3 words

32 -

164

-

18

34

Preimage

RIPEMD

128

128

512

64

32

48

Yes (2 )

No

No

RIPEMD-128/256

128/256

128/256

512

64

32

64

No

No

No

RIPEMD-160

160

160

512

64

32

80

Yes (251 :48)

No

No

RIPEMD-320

320

320

512

64

32

80

No

No

No

SHA-0

160

160

512

64

32

80

Yes (233.6 )

No

No

SHA-1

160

160

512

64

32

80

Yes (251 )

No

No

SHA-256/224

256/224

256

512

64

32

64

Yes (228.5 :24)

No

Yes (2248.4 :42)

SHA-512/384

512/384

512

1,024

128

64

80

Yes (232.5 :24)

No

Yes (2494.6 :42)

SHA-3

224/256/384/512

1600

?

?

64

24

No

No

No

Tiger(2)-192/160/128

192/160/128

192

512

64

64

24

Yes (262 :19)

No

Yes (2184.3 )

WHIRLPOOL

512

512

512

256

8

10

Yes (2120 :4.5)

No

No

preimage attack, it is computationally infeasible to find any input which hashes to that output second-preimage attack, it is computationally infeasible to find any second input which has the same output as any specified input

E. W. Fulp

CSC 348·648

Fall 2014

35

The Unix Encrypted Password System • When you type in a password, Unix needs a way to verify – However, Unix never stores plaintext passwords

– Instead, Unix stores the encrypted values in /etc/passwd • Unix uses a secret key algorithm to compute a hash of a password – Unix never has to reverse the hash (encrypted password)

– When you type in a password, it is hashed and compared • Unix uses an algorithm (originally DES-like) for encrypting

– Add salt to password then hash and store in /etc/passwd (actually stored in /etc/shadow)

E. W. Fulp

CSC 348·648

Fall 2014

36

Encrypted Password • Encrypted password has three parts $id$salt$encryptedPassword • The $id field identifies the encryption method ID

Encryption Method

1

MD5

2a

Blowfish (not part of glib, but some Unix distro’s include)

5

SHA-256 (since glib 2.7)

6

SHA-512 (since glib 2.7, typically used)

• The $salt field help prevent precomputed hash attacks

– Random value added to the password before it is encrypted – Salt is stored in plaintext So how does this improve security?

E. W. Fulp

CSC 348·648

Fall 2014

37

• The last field $encryptedPassword is the encrypted password • Consider the $encryptedPassword entry for root again $1$CQoPk7Zh$370xDLmeGD9m4aF/ciIlC. – The encryption is MD5 – The salt is CQoPk7Zh – The encrypted password is 370xDLmeGD9m4aF/ciIlC.

E. W. Fulp

CSC 348·648

Fall 2014

38