03 Modification Check Values

Question 1

What are the two main categories of modification check values?

Answer 1

• MDC (Modification Detection Code)
• MAC (Message Authentication Code)

Question 2

What is a Hash function and what are their two main properties?

Answer 2

A hash function is a function “h” with the properties of:

• Compression: h maps an input x of arbitrary finite bit length, to an output h(x) of fixed bit length n.
• Ease of computation: (with h and x it is easy to compute h(x)).

Cryptographic hash functions are used to compute MDC (Modification Detection Codes).

Question 3

What are other (secondary) properties of cryptographic hash functions?

Answer 3

• Pre-image resistance (for all pre-specified outputs y, it is computationally infeasible to find and x that h(x)=y). –> Non-reversible.
• 2nd pre-image resistance (given x it is computationally infeasible to find any second input x’ with x=/=x’ such that h(x)=h(x’) )–> Different results for every hash.
• Collision resistance: it is computationally infeasible to find any pair (x,x’) with x=/= x’ such that h(x)=h(x’) –> Cannot find two different arbitrary inputs that produce the same output/hash.

Question 4

What is a MAC and how it works?

Answer 4

MAC (Message Authentication Code) is a family of functions h_k parameterized by a secret key k with properties:

• Compression: hk maps an input x of arbitrary finite bit-length to an output hk(x) of fixed bit-lenght, called the MAC.
• Ease of computation: given k, x and a known function family hk the value hk(x) is easy to compute.
• Computation-resistance: for every fixed, allowed, but unknown value of k, given zero or more text-MAC pairs (x_i, h_i(x_i)) it is computationally infeasible to compute a text-MAC pair (x, h_k(x)) for any NEW input x=/= x_i.

Question 5

What is computation-resistance on MACs?

Answer 5

Implies a property where k cannot be recovered using pairs (x_i, hk(x_i)).

However, computation-resistance is not deduced solely from key non-recovery as sometimes the key k is not needed to forge new MACs.

Question 6

Message integrity is the principal application which lead the original design of MDC and MAC. Elaborate on each of them:

Answer 6

• MDC (Modification Detection Code) -> represents a digital fingerprint, that can be signed with a private key (RSA, ElGamal…) and two messages cannot have the same fingerprint (non-reusable by attackers).
• MAC (Message Authentication Code) -> over a message m, certifies that a sender of the message possesses the secret key K and the message could not have been modified without that key.

Question 7

What are other (non-original) applications for MDC and MAC that require some caution:

Answer 7

• Confirmation of knowledge
• Key derivation
• Pseudo-random number generation

Question 8

What is the Birthday Phenomenon and how is it related to MDCs?

Answer 8

• Concerns the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday.
  
  • p.50% = 23 people
  • p.99% = 70 people
• If there are n possible different values, the number K of values needed to obtain at least one pair of identical values is of the order: k = 1.18*Sqrt(n)
• This is related to MDCs due to the birthday attack because this one depends on the higher likelihood of collisions (different inputs, same hash output) found between random attack attempts and a fixed degree of permutations.
• Due to this birthday problem, these attacks are much faster than a brute force attack.

Question 9

What are some challenges faced by the Birthday attack?

Answer 9

• At least 1.18*Sqrt(n) variations of each of the two messages must be produced in order to have at least a probability of 0.5
• A memory problem (storing every message tried with their MDCs to find a match)
• m1’ and m2’ should produce MDC1(m1’) = MDC1(m2’)
• Average effort to produce two m1’ and m2’ are of the order n^(MDCs lenght/2)
• Thus a minimum of 160 bitlength of the hash value is recommended as it is considered as infeasible to attack.

Question 10

Explain the Merkle-Dåmgard structure in used by many cryptographic hash functions today:

Answer 10

1. An arbitrary message (y) has its length appended and it is padded/splitted into block sizes b (Creating y₀, y₁,.. y_L-1. L blocks of size b)
2. An IV is assigned to CV₀ (Chaining Value) := IV and then MDC(y) := CV_L
3. f is a compression function wich compresses (n+b) bits to n bits (shifted b comming from the current y) and n comming from the current CV)

Summarized:

CV₀ = IV initial n-bit value

CVi = f (CV_i-1, y_i-1) 1 <= i <= L

H(y) = CV_L

Question 11

Explain the Merkle-Dåmgard structure, a common structure of Cryptographic Hash Functions:

Answer 11

Question 12

Mention some inherent weaknesses of Merkle-Dåmgard constructions:

Answer 12

• If one collision is found, finding more is cheap.
• Multi-collisions can be found with little more work than collisions.
• Second preimage attacks are much more efficient than brute force

Question 13

What are some Cryptographic Hash Functions commonly used for creating MDCs?

Answer 13

• MD5 = Message Digest 5
• SHA1 = Secure Hash Algorithm 1
• SHA2 = Secure Hash Algorithm 2 (SHA-256, SHA-512)
• SHA3 = Secure Hash Algorithm 3

Question 14

Explain and elaborate on MD5:

Answer 14

1. MD5 processes a variable-lenght message into a fixed-length output of 128 bits.
2. A message “y” is padded by a “1” followed by 0-to-511 “0”s bits such that the length of the resulting message is congruent 448 modulo 512 (divisible by 512).
3. Length of the message is up to 64 bits fewer than 512 (=448).
4. The message is divided in blocks of b=512 bits.
5. MD5 operates on a n=128-bit state (chaining value acts as four 32-bit words A,B,C and D).
6. Each block of the message (y_i) is processed with the chaining value CV_i with the function f (internally realized by 4 rounds of 16 steps each = 64 operations in total). This modifies the chain state.
7. The processing of a message block uses a non-linear function F (4 differents), modular addition (with the aid of a table T with 64 constants) and left shift by s-bits.

Question 15

Graphically explain 1 step of MD5:

Answer 15

Question 16

Explain some security concerns about MD5:

Answer 16

• In 1996 an attack that allows a collision (same hash for different inputs) for the function f was published.
• In 2004 the first collision was found.
• Currently a collision can be done with the right hardware within seconds.
• MD5 for collision resistance compliance must be avoided (different files, same MD5, faking signatures such SSL certificates)
• MD5 is still OK against preimage attacks (good for tranmissions checking or data consistency).
• It is recommended to use another higher-output hash function like SHA-256.

Question 17

Explain and elaborate on DES-CBC-MAC:

Answer 17

• DES-CBC-MAC is also called CBC-MAC, uses the Data Encryption Standard in Cipher Block Chaining Mode.
• Constructs a MAC from a block cipher with IV=0
• This chain of blocks ensures that the final encrypted block is changed if any plaintextbits were altered.

Question 18

Explain and elaborate on SHA1:

Answer 18

1. SHA-1 (Secure Hash Algorithm) works on 512-bit blocks and produces a 160-bit hash
2. Inspired by MD4, so, its initialization is basically the same as that one of MD5 (padding data, lenght field added and the message is a multiple of 512 bits)
3. The CV (chaining value) is structured in 5 32-bit registers: A, B, C, D, E (using big-endian format)
4. Each block y_i of the message is processed with CV_i in a module with a compresion function “f” in four rounds of 20 steps each. Each round uses a different function (f1, f2, f3, f4).
5. Each step makes use of a fixed additive constant K_t unchanged per round.
6. A left-bit rotation of n places is carried out.
7. The SHA-1 MDC over a message is the content of the chaining value (CV) after processing the final message block.

Question 19

How does SHA-1 and MD5 compare?

Answer 19

• As SHA-1 design was inspired by MD4, its initialization is basically the same as MD5.
• Speed: SHA-1 is 25% slower than MD5 (CV is about 25% bigger).
• BOTH: simplicity and compactness, both algorithms are simple to describe and implement and do not require large programs or substitution tables.

Question 20

Elaborate on security aspects of SHA-1:

Answer 20

• SHA-1 operates on a length of 160 bits, where MD5 does it on 128 bits. Therefore it is expected that SHA-1 offers better security against brute-force and birthday attacks than MD5.
• In 2005 an attack that allows to find therotical collisions was published and latter improved, however, no practical collisions are publicly known yet.
• Inherent waknesses of Merkle-Dåmgard constructions apply.

Question 21

Graphically explain one step of SHA-1:

Answer 21

Question 22

Elaborate on the security discussion of SHA-2:

Answer 22

• In 2004 a simplified version of the algorithm (with XORs instead of addition and symmetric constants) generated highly correlated output.
• For round-reduced versions (57/80 for SHA-512 and 52/64 for SHA-256) pre-image attack exists that are faster than brute-force but are highly impractical.
• It’s size and complexitly does not allow attacks but the situation is turning uncomfortable -> Led to the need of SHA-3.

Question 23

Explain and elaborate on SHA-2:

Answer 23

• SHA-2 was published in 2001 by the NIST as new variants such as SHA-256 and SHA-512. There are truncated versions like SHA-224 and SHA-384.
• SHA-2 also uses a Merkle-Dåmgard construction with a block size of 512 bits (SHA-256) and 1024 bits (SHA-512).
• The internal state is organized in 8 registers (A, B, C… H) of 32 bits for SHA-256 and 64 bits for SHA-512.
• SHA-256 has 64 rounds and SHA-512 has 80 rounds.
• Design very similar to SHA-1, although the attacks of SHA-1 don’t apply to it.
• Usage of K_t as the fractional part of the cube root of the t^th prime number.
• ROTR and σ functions that XOR different shifts of input values.
• “Ch” and “Maj” as logic combinations of input values.
• 30 to 50% slower than SHA-1 due to size and more complicated round functions (varying in 32 and 64 bit systems).

Question 24

Graphically explain one step of SHA-2:

Answer 24

Question 25

Explain and elaborate on **SHA3**:

Answer 25

* SHA-1 and SHA-2 led to an open competition on 2007 that would have a resulting SHA-3 in 2012. * SHA-3 is very fast (especially in hardware). * Now **based on a "sponge" construction instead of Merkle-Dåmgard constructs.** * Much more versatile than previous hash functions. * Very well documented and analyzable. * Works in **2 phases: "Absorbing" and "Squeezing"** * **Absorbing information of arbitrary length into 1600 bit of internal state**. * Squeezing (outputting) hashed-data of arbitrary length.

Question 26

Describe the function f in SHA-3

Answer 26

* SHA-3 uses 24 rounds of 5 different sub-functions to implement f * Each sub-function ensures certain properties like: * Fast diffusion of changed bits throughtout the state * Long term diffusion * Ensuring that f becomes non-linear * Round-specific substitution

Question 27

Elaborate on Security of SHA-3

Answer 27

* Currently there are no notable weaknesses in SHA-3. * In comparison to SHA-1 and SHA-2, additional security properties are guaranteed as internal state is never made public. It is also not based in the same mechanism as those 2. * Good collision resistance. * No fast way to generate multi-collisions quickly.

Question 28

What are some Cryptographic Hash Functions commonly used for creating MACs?

Answer 28

* MACs (Message Authentication Codes): * DES-**CBC-MAC** * **MACs constructed from MDCs** * AEAD (Authenticated Encryption with Associated Data) * **GCM (Galois-Counter-Mode)** * **Sponge Wrap**

Question 29

How is a CBC-MAC computed? Also elaborate on some characteristics of it.

Answer 29

* A CBC-MAC (Cipher Block Chaining - Message Authentication Code) is computed by encrypting a message in CBC Mode and taking the last ciphertext block or a part of it as the MAC. * It doesn't need to be signed because it was produced using a shared secret K. * BUT it is not possible to know who created the MAC, because everybody who has the secret key K (both sender and receiver) can do so. * Works with any block cipher (DES, IDEA...)

Question 30

Graphically explain how a CBC-MAC is computed:

Answer 30

Question 31

Elaborate on the security of CBC-MAC

Answer 31

* As an attacker doesn't know K, a birthday attack is almost imposible (no hash function). * To attack CBC-MAC requires known pairs (message, MAC). * It can be strengthened by using a second key (K'=/=K) and doing a triple encryption on the last block, doubling the key space with few extra computing effort. * The IV is fixed (usually 0). * UNSECURE when message lenght vary! (last block can be XORed again) to create a valid MAC. * There are some proposals for MDCs from symmetric block ciphers using a fixed (known) key but because of their small block size (64 bits most commonly used), this scheme is not well protected against birthday attacks. Also, symmetric block ciphers require more computing power than hash functions.

Question 32

Explain and elaborate on MACs constructed from MDCs:

Answer 32

* Also called HMAC * Constructing MACs from MDCs Crypto hash functions execute faster than symmetric ciphers * Idea: mix a secret key K with the input to compute an MDC * BUT an attacker needs to know K to produce a valid MAC (this raises some cryptographic concern) * The most used construction is: H(K XOR p₁, H(K XOR p₂, m)) * The key is padded with 0's to fill up the key to one input block of the cryptographic hash function. * Two different constant patterns (p1 and p2 XORed to the padded key) * This scheme seems to be secure

Question 33

Mention some key characteristics of AEAD Modes:

Answer 33

* AEAD = Authenticated Encryption with Associated Data Modes * Data is authenticated AND encrypted (blocks P₀ ... P_n) * Sometimes additional data needs to be authenticated (like packet headers), denoted as A₀...A_m * This led to the development of AEAD modes of operation

Question 34

Mention some AEAD Modes of operation examples (name):

Answer 34

* Galois/Counter Mode (GCM) * Counter with CBC-MAC (CCM) * Offset Codebook Mode (OCM) * SpongeWrap - a method to use Keccak (SHA-3) for AEAD operation

Question 35

Explain and elaborate on AEAD --\> GCM (Galois-Counter-Mode):

Answer 35

* GCM (Galois-Counter-Mode) its a popular AEAD mode * Mainly used in networking applications for its high speed: * Extremely efficient in hardware * Processor support on newer X86 CPUs * Time intensive tasks may be pre-calculated and parallelized * No need for padding * GCM uses a conventional block cipher with 128 bit block size (e.g. AES) * Calculates MAC by multiplications and additions in Galois Field (GF (2¹²⁸) over a irreducible polynomial * Requires only n+1 block ciphers calls per packet (n=lenght of encrypted and authenticated data).

Question 36

Explain the Galois/Counter Mode (GCM) iteration:

Question 37

Elaborate on the Galois/Counter Mode security aspects:

Answer 37

* Fast mode, but needs some care: * Proven to be secure under some preconditions (example: used block cipher is not distinguishable from random numbers). Construction is fragile though: * IVs MUST NOT be reused, otherwise streams can be XORed and the XOR of the streams can be recovered, may lead to instant recovery of secret value "H". * H has a possible weak value of 0¹²⁸, in this case authentication will not work. * If IVs of a lenght =/= 96 bits are used, C₀ will always be the same. * Succesful forgery attempts may leak information about H, thus short MAC lengths MUST be avoided or risk-managed. * The achieved security is only 2^t-k not 2^t (for MAC length t and number of blocks k) as blocks may be modified to make only change parts of the MAC.

Question 38

Explain and elaborate on AEAD --\> Sponge Wrap:

Answer 38

* By using SHA-3 it is also possible an AEAD construct. * Uses a duplex mode for sponge functions, where data-write and read operations are interleaved. * Does not require padding of data to a specific block size. * Cannot be parallelized.

Question 39

Mention some key points about SpongeWrap security:

Answer 39

* Not widely used yet, but several aspects proven to be as secure as SHA-3 in standardized mode. * If the authenticated data A does not contain a unique IV, the same key stream will be generated --\> This allows the recovery of one block of XORed encrypted data!

Question 40

Describe and graphically present the elements of SpongeWrap operation:

Answer 40

* Simplified version, where key and MAC length must be smaller than block-size * Paddings with a single "0" or "1" bit ensure that different data blocks types are well separated.

Question 41

Graphically explain the Sponge Construction in SHA-3:

Answer 41