Cryptography and
Network
Security
1
11.2
11-3 MESSAGE AUTHENTICATION
A message digest does not authenticate the sender of the
message. To provide message authentication, Alice
needs to provide proof that it is Alice sending the
message and not an impostor. The digest created by a
cryptographic hash function is normally called a
modification detection code (MDC). What we need for
message authentication is a message authentication
code (MAC).
Topics discussed in this section:
11.3.1 Modification Detection Code (MDC)
11.3.2 Message Authentication Code (MAC)
11.3
11.3.1 Modification Detection Code (MDC)
A modification detection code (MDC) is a message digest
that can prove the integrity of the message: that message
has not been changed. If Alice needs to send a message to
Bob and be sure that the message will not change during
transmission, Alice can create a message digest, MDC,
and send both the message and the MDC to Bob. Bob can
create a new MDC from the message and compare the
received MDC and the new MDC. If they are the same,
the message has not been changed.
11.4
11.3.1 Continued
Figure 11.9 Modification detection code (MDC)
11.5
11.3.2 Message Authentication Code (MAC)
Figure 11.10 Message authentication code
11.6
11.3.2 Continued
Note
The security of a MAC depends on the security of
the underlying hash algorithm.
MESSAGE AUTHENTICATION - MDC
• MESSAGE AUTHENTICATION
• Proof of source cannot be
obtained
through Message Digest
• MD helps in knowing the
correctness of the data
not authenticate
• Modification Detection Code
• Message Digest can only detect
modifications in the message
• If both Message and MDC are sent
through the insecure channel, then
Eve can change both and send
7
MESSAGE AUTHENTICATION-MAC
• Message
Authentication Code
(MAC)
• Ensures integrity
and
authentication
both
• Secret key
• Prefix MAC -K|M –
concatenation done
and sent to hash
8
function
MESSAGE AUTHENTICATION
• Security of a MAC
• Suppose Eve has intercepted the message M and the digest h(K|M).
• There are three possible cases for forging:
• 1. If the size of the key allows exhaustive search, Eve may prepend all
possible keys at the beginning of the message and make a digest of the
(K|M) to find the digest
• 2. The size of the key is normally very large in a MAC, but Eve can use
another tool: the preimage attack. She uses the algorithm until she finds X
such that h(X) is equal to the MAC she has intercepted.
• 3. Given some pairs of messages and their MACs, Eve can manipulate them
to comeup with a new message and its MAC
9
MESSAGE AUTHENTICATION
• Nested MAC
MESSAGE
AUTHENTICATION
1
0
MESSAGE AUTHENTICATION
HMAC: Hashed MAC
1. The message is divided into N blocks, each of b bits.
2. The secret key is left-padded with 0’s to create a b-bit key. Note that it
is recommended that the secret key (before padding) be longer than n
bits, where n is the size of the HMAC.
3. The result of step 2 is exclusive-ored with a constant called ipad
(input pad) to create a b-bit block. The value of ipad is the b/8
repetition of the sequence 00110110 (36 in hexadecimal).
4. The resulting block is prepended to the N-block message. The result is N
+ 1 blocks.
5. The result of step 4 is hashed to create an n-bit digest. We call the
digest the intermediate HMAC.
1
1
MESSAGE AUTHENTICATION
6. The intermediate n-bit HMAC is left padded with 0s to make a b-
bit block.
7. Steps 2 and 3 are repeated by a different constant opad (output
pad). The value of opad is the b/8 repetition of the sequence
01011100 (5C in hexadecimal).
8. The result of step 7 is prepended to the block of step 6.
9. The result of step 8 is hashed with the same hashing algorithm
to create the final n-bit HMAC.
1
2
HMAC
NIST has issued a standard (FIPS
198) for a nested MAC that is often
referred to as HMAC
1
3
CMAC
CMAC- Cipher Block Chaining MAC
NIST has also defined a standard (FIPS 113) called Data
Authentication Algorithm, or CMAC, or CBCMAC
CBC – Used for confidentiality every block output
influences CT.
Here they are used only with next block
idea is to create one block of MAC from N blocks
of plaintext using a symmetric-key cipher N times
Procedure followed as shown
If padding is applied to last block, x^2 is used for
multiplication, if there is no padding, x is used.
Multiplication is in GF(2m) with irreducible polynomial of
degree m
9
Cryptographic Hash Functions
• Digital Signature
• Signature is for authenticity- Ex. A signature in a bank cheque
• Electronic signature done by the sender as a proof to the recipient that the document comes from correct
entity (proof of source)
• COMPARISON
• Inclusion
• CS: Cheque and signature are together
• DS: document / message and signature are separate
• Verification Method:
Method of verifying the signature
• CS: once a document is received, signature is verified with the signature in file
• DS: a verification algorithm is used to verify a signature and the signature is not stored anywhere
• Relationship:
• CS: one to many relation -same signatures in many documents
• Digital sign: one to one – each message has a different signature
• Duplicity:
• CS: sign in copy of the signed document and the original may be slightly different
• DS: no change among the two unless a timestamp is used
15
Difference between conventional and digital signature
Cryptographic Hash
Functions
PROCESS
17
Cryptographic Hash Functions
• Need for Keys
• CS is like private key which
is
available only with the
owner of document
• Public key is available in a
file and anyone can use it to
verify
• Asymm key crypto - but
keys
used are completely
diff from regular
procedure
• One single key cannot be
used – ends in forgery
• For every session, a
new pair is required 18
• Summary:
• A digital signature needs a public-key system. The signer signs
with
her private key; the verifier verifies with the signer’s public key.
• A cryptosystem uses the private and public keys of the receiver:
a digital signature uses the private and public keys of the
sender.
19
Cryptographic Hash Functions
• Signing the Digest
• Asymm key cryp
not for long
messages
• In DS sys,
messages
are generally
long
• Soln: sign a digest of
the
message(shorter)
20
Cryptographic Hash Functions
ATTACKS ON DIGITAL SIGNATURE
• Attack Types
• Key-Only Attack
• Eve has access to only public key
• To forge, Eve needs to create Alice’s signature
• Like ciphertext-only attack
• Known-Message Attack
• Eve has access to some M,S Pairs
• With this tries to create a message and tries to sign
• Like known- PT attack
• Chosen-Message Attack
• Eve somehow makes Alice sign one or more messages
• Eve now has a chosen message/ signature pair
• Chosen plaintext attack 21
Cryptographic Hash Functions
• Forgery Types
• Existential Forgery
• Eve may create a valid M,S pair but not the one she can use
• These could be syntactically or semantically unintelligible
• Selective Forgery
• Eve may be able to forge Alice Signature on a message with the content
selectively
chosen by eve
• Probability is very low, but not negligible
22
Cryptographic Hash Functions
• DIGITAL SIGNATURE
SCHEMES
• RSA Digital Signature Scheme
23
Cryptographic Hash Functions
• Key
Generation
24
• Attacks on RSA Signature
• Key-Only Attack
• Has only Alice pub key
• Creates another message- M’== Se mod n
• Not very easy to solve
• Like discrete log attack
• Known-Message Attack
• Eve uses multiplicative property of RSA
• If (M1,S1) and (M2,S2) is intercepted – created using same private
key
• Chosen Message Attack
• Uses Multiplicative property
• If Eve choses two messages and gets it signed from
Alice
• Very serious attack
22
• Multiplicative attack
Cryptographic Hash Functions
26
Cryptographic Hash Functions
• Attacks on RSA Signed Digests
• Key-Only Attack
A)
• Intercepts (S,M)
• Try to find M’ which gives the same hash h(M)=h(M’)
• If hash algo is second preimage resistant, attack is diff
B)
• Finds M and M’ with same signature.
• Makes Alice sign M- has two pairs with same sign
• If hash algo is colli resis then this is difficult
C)
• Random D found which matches with random sign S. Finds Message
D=h(M) 27
Cryptographic Hash Functions
• Known-Message Attack
• Eve has two - (M1,S1) and (M2,S2) – same private key
• Calculates S≡S1 XS2
• IF can find an mess M such that h(M) ≡ h(M1) X h(M2) she had forged a new
message
• Finding M is difficult if HA is preimage resistant
• Chosen Known-Message Attack
• Eve can ask Alice to sign two legitimate mess M1 and M2 for her
• Eve creates a new signature S ≡ S1 X S2
• Calculates h(M) ≡ h(M1)x h(M2)- if a message M can be found given h(M)
the new message is forgery
28
• Diff if HA is preimage resistant
Discrete Logarithm Attacks
Eve can intercept R1 and R2. If she can find x from R1= gx mod p and
y from R2=gy mod p
Then she can easily calculate K = gxy mod p .
To make Diffie-Hellman safe from this type of attack
1. The prime p must be very large ( more than 300 decimal digits)
2. The prime p should be chosen such that p-1 has at-least one large prime factor
3. The generator must be chosen from <Zp*,*>
4. Bob and Alice must destroy x and y after they have calculated the key.
5. The said value of x and y must be used only once
Public Announcement
Trusted
Center