Topic 5-Crytographic Checksum PDF

Preview

Summary

Lecuture notes topic 5 of Cryptography and network security...

Description

Topic 5: Cryptographic Checksums Understand the need for cryptographic checksums, how to construct them, and their applications

Source: Stallings book: chapters 11 and 12

COMP38411 (Topic 5)

1

Overview q Part

1 Ø Motivation and Definitions q Part 2 Ø Cryptographic Hash Functions q Part 3 Ø Block Cipher based MAC (Message Authentication Code) Ø HMAC (hash function based MAC) q Part 4 Ø Authenticated Encryption Ø Conclusion

COMP38411 (Topic 5)

2

Threats to Message Security q Content

disclosure (confidentiality) q Traffic flow analysis (traffic flow confidentiality) q Sender masquerading/impersonation (entity authentication) q Content modification (message authentication) q Sequence modification (message authentication) q Timing modification (message authentication) q Repudiation of transmission/origin (message authentication + …) q Repudiation of receipt These terms are used interchangeably: Checksum=digest=fingerprint=compressed value=hash value MAC (Message Authentication Code) = cryptographic checksum COMP38411 (Topic 5)

3

Need for a Cryptographic Checksum

Why do I emphasise  a certain degree here?

q Conventional

(symmetric) encryption, A --> B: EK[M] Ø Provides confidentiality, as ONLY A and B share K. Ø Provides a certain degree of origin authentication, as it could only come from A or B. Ø Does not provide non-repudiation, as o A could deny sending the message – repudiation of origin. o B could also generate the encryption.

q Another

variant, A --> B: EK[M||h(M)] Ø Assuming that h is a compression function. Ø What is the difference between this protocol and the one above? Ø What benefit does this protocol provide vs the one above?

COMP38411 (Topic 5)

4

Need for a Cryptographic Checksum q Public-key

encryption, A --> B: EKUb [M] (using Bs public key) Ø Provide confidentiality as only B has the decryption key. Ø Provides no origin authentication, as anybody could get hold of Bs public key.

q Digital signing, A --> B: M||EKRa [h(M)] (using As private Ø Provides origin authentication and non-repudiation, as

key)

o Only A has KRa, so signed item (called checksum) must have come from A. o Any party can use KUa to verify the signed item. o Provided KUa is trust-worthy, and the signature is dated. Ø Provide no confidentiality. COMP38411 (Topic 5)

5

Need for a Cryptographic Checksum q Cryptographic

checksum can be used to achieve Ø Content authentication (= origin + integrity) for any kind of messages including unstructured. Ø Non-repudiation of origin provided Øthe communication parties trust each other, or Øthe checksum is uniquely associated to the message originator, if the parties do not trust each other Ø Anti-replay (i.e. achieve freshness) q It is attractive to applications that only require authentication Ø secure broadcast; Ø source code distribution. q A cryptographic checksum should be Ø hard to forge and tamper-proof COMP38411 (Topic 5)

6

Part 2 Overview q

Cryptographic Hash Functions

COMP38411 (Topic 5)

7

Hash Functions – Compression Property q Given

a message M of arbitrary length, a hash function, H, produces a fixed-sized output, h (called a message digest, checksum, hash value, or fingerprint, of M), i.e. h=H(M). q H should be a function of all the bits of M. This is a message of any length …….. H(x)

Fixed length value

01100100…1

This is a many-to-one mapping, so collisions are unavoidable, but we should make finding collisions as difficult as possible. COMP38411 (Topic 5)

8

Hash Functions – Compression Property q Each

hash function execution processes a block of M; the output is the input for the next iteration; the output of the last block is the digest for M. L × block size Message + padding bits + message-length bits; L blocks: M1 , M2 , … ML h0

M1

M2 …

Hash function

Hash function

hL-1

ML

Hash function Digest

h1

h2

hL

h0 is a constant initial value, and the output of the last block is the digest of the entire message. COMP38411 (Topic 5)

9

Hash Functions - Security Requirements/Properties Cryptographic hash functions are hash functions with additional security requirements/properties: qPreimage resistant (one-way): Given y ÎY, it is computationally infeasible to find a value x ÎX s.t. H(x) = y. q2-nd preimage resistant (weak collision-resistant): Given x Î X, it is computationally infeasible to find another value x’ Î X, s.t. x’¹x and H(x’) = H(x). qCollision resistant (strong collision-resistant): It is computationally infeasible to find two distinct values, x’ and x Î X, s.t. H(x’) = H(x). PS: If H is strong collision-resistant, then it is also weak collision-resistant. COMP38411 (Topic 5)

10

Hash Functions – Importance of the Security Properties q Signature

forgery if weak collision resistance property is not

met. Ø Assuming that A has sent a signed message M to B, i.e. M||s where s=EKRa[H(M)] and KRa is As private key; o An attacker intercepts A s signature and message; o The attacker finds another message M with H(M)=H(M ); o The attacker now has your signature s on the message M . Ø Think

about the implication of this attack in real-life!

COMP38411 (Topic 5)

11

Hash Functions – Importance of the Security Properties q Repudiation

if strong collision resistance property is not met. Ø Assuming that A is to send a signed message M to B o A chooses two messages M and M with H(M)=H(M); o A signs M by generating signature s=EKRa[H(M)]; o A sends B M||s; o Later A repudiates this signature, saying it was really a signature on the message M . Ø Think about the implication of this attack, if o The communication is for A to make an e-payment; and o M is an electronic cheque for £10. o M is an electronic cheque for £1000.

COMP38411 (Topic 5)

12

Hash Functions – Commonly used Hash Functions SHA-1

SHA-256

SHA-384

SHA-512

Hash value size

160

256

384

512

Block size

512

512

1024

1024

Word size

32

32

64

64

Security

80

128

192

256

* All sizes are measured in bits;

*SHA = Secure Hash Algorithm

* Security refers to the fact that a birthday attack on a message digest of size n produces a collision with a work-factor of approx 2n/2. COMP38411 (Topic 5)

13

Hash Function Applications q Secure

storage of passwords q Digital signatures q Pseudo-random number generations q Bit commitment (or coin flipping) problem q Bit coins q Blockchains q Digital payment systems q Digital right management systems q…

COMP38411 (Topic 5)

14

Part 3 Overview q Block

Cipher based MAC (Message Authentication Code) q HMAC (hash function based MAC)

COMP38411 (Topic 5)

15

Message Authentication Code (MAC) using Block Ciphers q A cryptographic

checksum can also be generated using a symmetric block cipher, i.e. MAC=fK(M), where fK is a block cipher based digest function. q An example is CBC-MAC: Ø Can be any symmetric block cipher Ø the output of the last block is MAC q The block cipher based digest function has an embedded key. Plain

Text

Message

Input

Block Cipher

Block Cipher

Block Cipher

Block Cipher

IV K

COMP38411 (Topic 5)

16

MAC in Operation q Sender Ø uses

K and a MACing function, f, to generate a checksum, MAC=fK(M). Ø then sends M||MAC, where || is concatenation of data items. q Receiver Ø computes MAC= fK(M), where M  is the message received, and K  is receivers copy of the key. Ø If MAC=MAC, then the message has not been tampered with.

COMP38411 (Topic 5)

17

MAC in Operation K Message M

Sender A

Message M MAC algorithm Transmit MAC’

MAC MAC algorithm

MAC

Compare

MAC Cryptographic Checksum

Receiver B

K

COMP38411 (Topic 5)

18

MAC in Operation q If

only A and B know the secret key K, and if MAC=MAC’, then the receiver can be assured Ø the message has not been altered - integrity protection; Ø the message is from the alleged sender - origin authentication; Ø the message is of the proper sequence if the message includes a sequence number; Ø the message is fresh - i.e, not a replay o if the message includes a timestamp; or o a random number contributed (fully or partially) by B (the recipient). q The MAC operation described above is also applicable to MACs generated with another method, e.g. a hash function. COMP38411 (Topic 5)

19

HMAC q KeyedHash

= Hash(K||Message) q HMAC is a keyed hash function, specified as Internet standard H(K2||H(K1||M))

HMAC(K, M)= H[ K+ XOR opad) || H[ K+ XOR ipad) || M)]];

where H = any hash function such as SHA-256; K+ is the key padded out to block size; ipad = a string by repeating the byte 0x36 (00110110) as often as necessary; opad = a string by repeating the byte 0x5c (01011100) as often as necessary. COMP38411 (Topic 5)

20

HMAC Secret key padded to block size

Block size of hash function, H.

Strength of HMAC relies on strength of this hash function, H.

HMAC can be constructed with any hash function.

hash(key2, hash(key1, message)) “Amplify” key material: get two keys out of one.

21

Security of MACs q Brute

force attacks Ø Finding collisions cost 2n/2, where n is the bit-length of MAC value. The larger the n value, the more secure it is. Ø Attack key space or MAC by exploiting MACs with known message-MAC pairs.

q Worth

mentioning: a MAC is not a digital signature; it does not provide non-repudiation.

COMP38411 (Topic 5)

22

Part 4 Overview q Authenticated

Encryption Ø Part 4.1 – Overview Ø Part 4.2 - CCM: Counter Mode with CBC Ø Part 4.3- GCM: Galois/Counter Mode q Conclusion

COMP38411 (Topic 5)

23

Authenticated Encryption q This

is for achieving both message authentication and confidentiality. q Possible approaches: Ø Hash-then-encrypt: E(K, (M||H(M)) Ø MAC-then-encrypt

(used in SSL): E(K2, (M||MAC(K1, M)); or Tag= MAC(K1, M), E(K2, (M||Tag)); Tag is for authentication Ø Encrypt-then-MAC

(used in IPSec): C=E(K2, M), Tag=MAC(K1, C) Ø Encrypt-and-MAC

(used in SSH): C=E(K2, M), Tag=MAC(K1, M) COMP38411 (Topic 5)

24

Authenticated Encryption with Associated Data (AEAD) q In

some contexts, such as networks, a message (packet) consists of two parts, a header field and a payload, and the two parts often have different security requirements. q In addition, the protections should be provided efficiently (with as less overhead as possible). Needs Authentication Header

Payload Needs Confidentiality

COMP38411 (Topic 5)

25

Authenticated Encryption with Associated Data q Plaintext (Payload) should be encrypted AND authenticated. q Associated Data (Header) should be authenticated (without encryption). q Nonce should be distinct for each AEAD operation. Header Associated Data

Payload Plaintext

Key Authenticated Encryption Nonce COMP38411 (Topic 5)

26

Authenticated Encryption with Associated Data q Tag

also goes through the encryption operation. Header Associated Data

Payload Plaintext

Key Authenticated Encryption Nonce Ciphertext||Tag Header COMP38411 (Topic 5)

Nonce

Protected (Payload + Tag) 27

Authenticated Encryption with Associated Data q Two

notable schemes: CCM and GCM Ø CCM: Counter Mode with CBC-MAC (NIST SP 800-38C for WiFi) Ø GCM: Galois/Counter Mode (NIST standard SP 800-38D)

COMP38411 (Topic 5)

28

CCM: Counter Mode with CBC-MAC q CTR

encryption example: assuming two plaintext blocks, counter value is initialised to 5, AES is chosen as the block cipher. Ø Counter value increment for each subsequent plaintext block. Ø Parallel/pipelined computation/processing/operation. Ø Encryption/decryption are done using XOR – very fast. counter = 5

Counter=6

(n) K

(n) K

AES

AES

(n) M1

(n)

COMP38411 (Topic 5)

(n) (n)

+

C1

M2

(n)

(n) +

C2 29

CCM: Parallel/pipelined computation q Computation

M1 arrival time

time: pipelined vs non-pipelined operations

1st XOR

1st XOR 1st block AES 2nd block AES

1st block AES

2nd XOR

2nd block AES

2nd XOR

M2 arrival time

Using CTR Mode: Total time taken to encrypt the two blocks

COMP38411 (Topic 5)

Using CBC Mode: Total time taken to encrypt the two blocks

30

CCM Authentication Tag is generated using CBC-MAC (also referred to as CMAC): Tag=CMAC(K, M) where Plaintext=Payload; M=Nonce||Plaintext||Ass.Data; Ass.Data=Associated Data (e.g. packet headers) Encryption is by AES CTR mode: E(K, Payload||Tag) Nonce (random number) to ensure Tag is fresh. COMP38411 (Topic 5)

E(K, (M||MAC(K, M))

CCM: Counter Mode with CBC-MAC q Tlen

(Tag Length) most significant bits of the output are XORed with the tag to produce an encrypted tag. IV q Same key (can be different) for K MACing and encryption. q Plaintext passes 2 block cipher operations (MAC and encryption). q CBC-MAC is not pipelinable/parallelizable.

M=Nonce||Plaintext||Ass.Data

AES

AES

AES

AES

Tag

q To

speed up the performance further, we have GCM. COMP38411 (Topic 5)

32

GCM q Galois/Counter

Mode (GCM) q GCM is designed to provide authenticated encryption for high speed applications (can do authenticated encryption at > 10 gigabits per second) q Combines counter mode with Galois mode q Counter mode can be pipelined and parallelized in hardware implementations q Rather than using block chaining to generate tags (MACs), GCM uses a Galois field multiplication that is less computationally intensive than CBC-MAC q Cost half of the number of AES operations used in CCM q NIST standard SP 800-38D COMP38411 (Topic 5)

33

GCM q GCM

has two functions, authenticated encryption and authenticated decryption. q Authenticated encryption: Given a selected block cipher & K, authenticated encryption function has 3 inputs: o Plaintext, denoted P. o Additional authenticated data (AAD), denoted A. o An initialization vector, denoted IV (Nonce to ensure freshness). q It generates two outputs: o A ciphertext, denoted C, which has the same length as P. o An authentication tag, denoted as T, used to protect authenticity of P, A and IV.

COMP38411 (Topic 5)

34

GCM decryption: Given a selected block cipher & K, this function has 4 inputs: IV, A, C, and T. q The output is one of the following: o plaintext P that corresponds to the ciphertext C, or o a special error code, denoted FAIL. q The output P indicates that T is the correct authentication tag for IV, A, and C; otherwise, the output is FAIL. q Authenticated

COMP38411 (Topic 5)

35

GCM q Uses

two functions: o GHASH - a keyed hash function over a binary Galois field. o GCTR - a variation of CTR mode (with a particular incrementing function, denoted inc). q GHASH: plaintext xor’ed with feedback and multiplied with H (a hash subkey) in GF 2128). Y0 is a 128-bit length “zero block” 0128. For i=1 ,…, m, Yi=(Yi-1⊕Xi)·H, where block H is the hash subkey, generated by applying the block cipher to the “zero” block. Ym is the output.

GHASH q GHASH

function can be expressed as:

Ym=(X1 • Hm ) XOR (X2 • Hm–1 ) XOR ... XOR (Xm–1 • H2 ) XOR (Xm • H)

where • designates multiplication in GF(2128 )

COMP38411 (Topic 5)

37

GCM in the two figures, (a) and (b), are not related. q ICB=Initial Counter Block. q MSBsX: bit string consisting of s left-most bits of the bit string X. q Yi

E=CIPH; a block cipher with a 128-bits block size COMP38411 (Topic 5)

= Y1||Y2 ||...||Yn-1|| Yn* 38

GCM q J0=ICB

(Initial Counter Block)

GCM compresses an encoding of AAD (A) and the ciphertext (C) into a single block, which is then encrypted to produce the authentication tag, T=Tag. q C can be null, resulting a variant of GCM, called GMAC, generating and verifying tag on non-confidential data. q J0 (ICB=Initial Counter Block) is generated from IV. q Inc32: an increment function; it increments the right-most 32 bits of the string with the remaining bits unchanged. q CIPH: a block cipher with a 128-bits block size, and the key size should be at least 128 bits. q GHASH

COMP38411 (Topic 5)

40

Exercise Question – E5.1 For a hash value to be used as a cryptographic checksum, it must be protected with a secret, as it is clear, from the above, that a hash function does not have an embedded key. Assuming that a sender, s, is to send a message, M, to a receiver, r. Propose as many different methods as you can to protect the hash value of M to assure the authenticity of M. Comment on the suitability/applicability of each of the methods you propose.

COMP38411 (Topic 5)

41

Exercise Question – E5.2 For each of the following applications, please identify what property(ies) the hash function needs to have to ensure the security of the application. (i) Secure storage of passwords Password file: User_A *** Psword = myDoB User_B *** What should we put in there? What if backup tape is stolen? What property do we need?

(ii) Protection against viruses mA software manufacturer wants to ensure that the executable files are received by users without modification. mThey send out each file to users and publish its hash value on an authentic website.

Exercise Question – E5.2 (continue) (iii) Digital signatures One party can sign a message, M, and many parties can verify. Such applications include contract signing, code signing, etc. A raw signature scheme only signs a few hundred (e.g. 160) bits. What properties do we need? Integrity, authentication, and non-repudiation are provided. *This is the essence of the digital signature technique. || M

H M Compare

H

E

D KRa

COMP38411 (Topic 5)

EKRa[H(M)]

KUa

43

Exercise Question – E5.3 q This

is a Coin Flipping Over the Telephone problem...