Cryptographic Data Integrity Algorithms: Hash Functions - Simple hash functions, Secure Hash Algorithm SHA-512;
Message Authentication Codes – Requirements, Functions, Security of MACs, HMAC; Digital signatures - Schnorr
Digital signature scheme
Message Authentication SERVICEs:
Protecting the integrity.
validating identity of the originator.
Non-repudiation (denying that I am not done)of origin.
Message Authentication REQUIREMENTs:
1. Disclosure: Release of message contents to any person or process.
2. Traffic analysis: Discovery of the pattern of traffic between parties. In a connection-oriented application, the
frequency and duration of connections could be determined.
3. Masquerade: Insertion of messages into the network from a fraudulent source. This includes the creation of
messages by an opponent that are purported to come from an authorized entity.
4. Content modification: Changes to the contents of a message, including insertion, deletion, transposition,
and modification.
5. Sequence modification: Any modification to a sequence of messages between parties, including insertion,
deletion, and reordering.
6. Timing modification: Delay or replay of messages. In a connection-oriented application, an entire session or
sequence of messages could be a replay of some previous valid session, or individual messages in the
sequence could be delayed or replayed.
7. Source repudiation: Denial of transmission of message by source.
8. Destination repudiation: Denial of receipt of message by destination.
Message Authentication Functionality’s:
Message encryption: The ciphertext of the entire message serves as its authenticator
Hash function: A function that maps a message of any length into a fixed-length hash value(hash code),
which serves as the authenticator
Message authentication code (MAC): A function of the message and a secret key that produces a fixed-
length value(Mac code) that serves as the authenticator .
Basic Uses of Message Encryption
The straightforward use of public-key encryption (Figure b) provides confidentiality but not
authentication. The source (A) uses the public key PUb of the destination (B) to encrypt M.
Because only B has the corresponding private key PRb, only B can decrypt the message. This
scheme provides no authentication, because any opponent could also use B’s public key to
encrypt a message and claim to be A.
To provide authentication, A uses its private key to encrypt the message, and B uses A’s public
key to decrypt (Figure:c). This provides authentication using the same type of reasoning as in the
symmetric encryption case: The message must have come from A because A is the only party
that possesses PRa and therefore the only party with the information necessary to construct
ciphertext that can be decrypted with PUa. Again, the same reasoning as before applies: There
must be some internal structure to the plaintext so that the receiver can distinguish between
well-formed plaintext and random bits.
1. In effect, A has “signed” the message by using its private key to encrypt. Note that this
scheme does not provide confidentiality.
To provide both confidentiality and authentication, A can encrypt M first using its private key, which
provides the digital signature, and then using B’s public key, which provides confidentiality (Figure :d). The
disadvantage of this approach is that the public-key algorithm, which is complex, must be exercised four
times rather than two in each communication.
Error detection code:
append an error-detecting code, also known as a frame check sequence (FCS) or checksum, to each
message.
Message Authentication code:
An alternative authentication technique involves the use of a secret key to generate a small fixed-size
block of data, known as a cryptographic checksum or MAC, that is appended to the message. This
technique assumes that two communicating parties, say A and B, share a common secret key K. When A
has a message to send to B, it calculates the MAC as a function of the message and the key:
MAC = C(K, M)
where M = input message ,C = MAC function, K = shared secret key, MAC = message authentication code
The message plus MAC are transmitted to the intended recipient. The recipient performs the same
calculation on the received message, using the same secret key, to generate a new MAC. The received
MAC is compared to the calculated MAC (Figure 12.4a). If we assume that only the receiver and the
sender know the identity of the secret key, and if the received MAC matches the calculated MAC,
then
1. The receiver is assured that the message has not been altered. If an attacker alters the message but
does not alter the MAC, then the receiver’s calculation of the MAC will differ from the received MAC.
Because the attacker is assumed not to know the secret key, the attacker cannot alter the MAC to
correspond to the alterations in the message.
2. The receiver is assured that the message is from the alleged sender. Because no one else knows the
secret key, no one else could prepare a message with a proper MAC.
MAC algorithm is an irreversible algorithm.
For example, suppose that we are using 100-bit messages and a 10-bit MAC. Then, there are a total of 2
power(100) different messages but only 2 power(10) different MACs. So, on average, each MAC value is
generated by a total of 2 power(100)/2power(10) = 2power(90) different messages. If a 5-bit key is used,
then there are 2power(5) = 32 different mappings from the set of messages to the set of MAC values.
In the first case, the MAC is calculated with the message as input and is then concatenated to the message.
The entire block is then encrypted.
In the second case, the message is encrypted first. Then the MAC is calculated using the resulting ciphertext
and is concatenated to the ciphertext to form the transmitted block.
Note:
1. It takes variable length of input and provides fixed length of output.
2. The main difference between the mac algorithm and hash function in mac along with the input we also
provide the key as input.
Hash Function:
A hash function H accepts a variable-length block of data M as input and produces a fixed-size hash
value
h = H(M).
In general terms, the principal object of a hash function is data integrity.
A change to any bit or bits in M results, with high probability, in a change to the hash value.
The kind of hash function needed for security applications is referred to as a cryptographic hash
function.
The input is padded out to an integer multiple of some fixed length (e.g., 1024 bits), and the padding
includes the value of the length of the original message in bits
a variety of ways in which a hash code can be used to provide message authentication
a) The message plus concatenated hash code is encrypted using symmetric encryption. Because only A and B
share the secret key, the message must have come from A and has not been altered. The hash code provides
the structure or redundancy required to achieve authentication. Because encryption is applied to the entire
message plus hash code, confidentiality is also provided
b) Only the hash code is encrypted, using symmetric encryption. This reduces the processing burden for those
applications that do not require confidentiality.
c) It is possible to use a hash function but no encryption for message authentication. The technique assumes
that the two communicating parties share a common secret value S. A computes the hash value over the
concatenation of M and S and appends the resulting hash value to M. Because B possesses S, it can
recompute the hash value to verify. Because the secret value itself is not sent, an opponent cannot modify
an intercepted message and cannot generate a false message.
d) Confidentiality can be added to the approach of method (c) by encrypting the entire message plus the hash
code.
e) Applications:
one-way password file.(store hash of passwords not an actual password)
for intrusion detection and virus detection (keep & check hash of files on system)
pseudorandom function (PRF) or pseudorandom number generator (PRNG)
Simple hash functions:
consider two simple insecure hash functions
1. bit-by-bit exclusive-OR (XOR) of every block
Ci = bi1 xor bi2 xor . . . xor bim
a longitudinal redundancy check
reasonably effective as data integrity check
2. one-bit circular shift on hash value
for each successive n-bit block.
rotate current hash value to left by 1bit and XOR block
good for data integrity but useless for security
secure hash functions (SHA):
SHA was developed by the National Institute of Standards and Technology (NIST) and published as a federal
information processing standard (FIPS 180) in 1993.
SHA-1 SHA-256 SHA-384 SHA-512
Message digest 160 256 384 512
Message size <2power(64) <2power(64) <2power(128) <2power(128)
Block size 512 512 1024 1024
round 80 64 80 80
Word size 32 32 64 64
SHA-512:
The algorithm takes as input a message with a maximum length of less than 2power(128) bits and produces
as output a 512-bit message digest.
The input is processed in 1024-bit blocks.
Steps:
Step1: Append padding bits: Padding is always added, even if the message is already of the desired length.
Thus, the number of padding bits is in the range of 1 to 1024. The padding consists of a single 1 bit followed
by the necessary number of 0 bits
Step2: Append length. A block of 128 bits is appended to the message. This block is treated as an unsigned
128-bit integer (most significant byte first) and contains the length of the original message in bits (before the
padding). The outcome of the first two steps yields a message that is an integer multiple of 1024 bits in
length the expanded message is represented as the sequence of 1024-bit blocks M1, M2, c , MN, so that the
total length of the expanded message is N * 1024 bits.
Step3: Initialize hash buffer: A 512-bit buffer is used to hold intermediate and final results of the hash
function. The buffer can be represented as eight 64-bit registers (a, b, c, d, e, f, g, h). These values are stored
in big-endian format.
Step4: process message: The heart of the algorithm is a module that consists of 80 rounds; this module is
labeled F in above figure.
Each round takes as input the 512-bit buffer value, abcdefgh, and updates the contents of the buffer.
At input to the first round, the buffer has the value of the intermediate hash value, Hi-1.
Each round t makes use of a 64-bit value Wt (word), derived from the current 1024-bit block being
processed (Mi ).
These values are derived using a message schedule described subsequently. Each round also makes
use of an additive constant Kt , where 0 … to… 79 indicates one of the 80 rounds.
These words represent the first 64 bits of the fractional parts of the cube roots of the first 80 prime
numbers
The output of the eightieth round is added to the input to the first round (Hi-1) to produce Hi . The addition is done
independently for each of the eight words in the buffer with each of the corresponding words in Hi-1, using addition
modulo 264
Step 5 Output: After all N 1024-bit blocks have been processed, the output from the Nth stage is the 512-bit
message digest.
SHA-512 Round function:
Six of the eight words of the output of the round function involve simply permutation (b, c, d, f, g, h) by
means of rotation.
Only two of the output words (a, e) are generated by substitution.
Word e is a function of input variables (d, e, f, g, h), as well as the round word Wt and the constant Kt .
Word a is a function of all of the input variables except d, as well as the round word Wt and the constant Kt
SHA-512 word(64 bits):
It remains to indicate how the 64-bit word values Wt are derived from the 1024-bit message.
The first 16 values of Wt are taken directly from the 16 words of the current block.
The remaining values are defined as
HMAC-MAC based on hash functions:
Objectives:
To allow for easy replaceability of the embedded hash function in case faster or more secure hash functions
are found or required.
To preserve the original performance of the hash function without incurring a significant degradation.
To use and handle keys in a simple way
To have a well-understood cryptographic analysis of the strength of the authentication mechanism based on
reasonable assumptions on the embedded hash function
