1
Q
What are the two main categories of modification check values?
A
- MDC (Modification Detection Code)
- MAC (Message Authentication Code)
2
Q
What is a Hash function and what are their two main properties?
A
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).
3
Q
What are other (secondary) properties of cryptographic hash functions?
A
- 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.
4
Q
What is a MAC and how it works?
A
MAC (Message Authentication Code) is a family of functions hk 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 (xi, hi(xi)) it is computationally infeasible to compute a text-MAC pair (x, hk(x)) for any NEW input x=/= xi.
5
Q
What is computation-resistance on MACs?
A
Implies a property where k cannot be recovered using pairs (xi, hk(xi)).
However, computation-resistance is not deduced solely from key non-recovery as sometimes the key k is not needed to forge new MACs.
6
Q
Message integrity is the principal application which lead the original design of MDC and MAC. Elaborate on each of them:
A
- 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.
7
Q
What are other (non-original) applications for MDC and MAC that require some caution:
A
- Confirmation of knowledge
- Key derivation
- Pseudo-random number generation
8
Q
What is the Birthday Phenomenon and how is it related to MDCs?
A
- 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.
9
Q
What are some challenges faced by the Birthday attack?
A
- 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.
10
Q
Explain the Merkle-Dåmgard structure in used by many cryptographic hash functions today:
A
- An arbitrary message (y) has its length appended and it is padded/splitted into block sizes b (Creating y0, y1,.. yL-1. L blocks of size b)
- An IV is assigned to CV0 (Chaining Value) := IV and then MDC(y) := CVL
- 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:
CV0 = IV initial n-bit value
CVi = f (CVi-1, yi-1) 1 <= i <= L
H(y) = CVL
11
Q
Explain the Merkle-Dåmgard structure, a common structure of Cryptographic Hash Functions:
A
12
Q
Mention some inherent weaknesses of Merkle-Dåmgard constructions:
A
- 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
13
Q
What are some Cryptographic Hash Functions commonly used for creating MDCs?
A
- MD5 = Message Digest 5
- SHA1 = Secure Hash Algorithm 1
- SHA2 = Secure Hash Algorithm 2 (SHA-256, SHA-512)
- SHA3 = Secure Hash Algorithm 3
14
Q
Explain and elaborate on MD5:
A
- MD5 processes a variable-lenght message into a fixed-length output of 128 bits.
- 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).
- Length of the message is up to 64 bits fewer than 512 (=448).
- The message is divided in blocks of b=512 bits.
- MD5 operates on a n=128-bit state (chaining value acts as four 32-bit words A,B,C and D).
- Each block of the message (yi) is processed with the chaining value CVi with the function f (internally realized by 4 rounds of 16 steps each = 64 operations in total). This modifies the chain state.
- 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.
15
Q
Graphically explain 1 step of MD5:
A
16
Q
Explain some security concerns about MD5:
A
- 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.
17
Q
Explain and elaborate on DES-CBC-MAC:
A
- 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.
18
Q
Explain and elaborate on SHA1:
A
- SHA-1 (Secure Hash Algorithm) works on 512-bit blocks and produces a 160-bit hash
- 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)
- The CV (chaining value) is structured in 5 32-bit registers: A, B, C, D, E (using big-endian format)
- Each block yi of the message is processed with CVi 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).
- Each step makes use of a fixed additive constant Kt unchanged per round.
- A left-bit rotation of n places is carried out.
- The SHA-1 MDC over a message is the content of the chaining value (CV) after processing the final message block.
19
Q
How does SHA-1 and MD5 compare?
A
- 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.
20
Q
Elaborate on security aspects of SHA-1:
A
- 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.
21
Q
Graphically explain one step of SHA-1:
A
22
Q
Elaborate on the security discussion of SHA-2:
A
- 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.
23
Q
Explain and elaborate on SHA-2:
A
- 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 Kt as the fractional part of the cube root of the tth 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).
24
Q
Graphically explain one step of SHA-2:
A
25
Explain and elaborate on **SHA3**:
* 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.
26
Describe the function f in SHA-3
* 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
27
Elaborate on Security of SHA-3
* 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.
28
What are some Cryptographic Hash Functions commonly used for creating MACs?
* MACs (Message Authentication Codes):
* DES-**CBC-MAC**
* **MACs constructed from MDCs**
* AEAD (Authenticated Encryption with Associated Data)
* **GCM (Galois-Counter-Mode)**
* **Sponge Wrap**
29
How is a CBC-MAC computed? Also elaborate on some characteristics of it.
* 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...)
30
Graphically explain how a CBC-MAC is computed:
31
Elaborate on the security of CBC-MAC
* 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.
32
Explain and elaborate on MACs constructed from MDCs:
* 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 p1, H(K XOR p2, 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
33
Mention some key characteristics of AEAD Modes:
* AEAD = Authenticated Encryption with Associated Data Modes
* Data is authenticated AND encrypted (blocks P0 ... Pn)
* Sometimes additional data needs to be authenticated (like packet headers), denoted as A0...Am
* This led to the development of AEAD modes of operation
34
Mention some AEAD Modes of operation examples (name):
* Galois/Counter Mode (GCM)
* Counter with CBC-MAC (CCM)
* Offset Codebook Mode (OCM)
* SpongeWrap - a method to use Keccak (SHA-3) for AEAD operation
35
Explain and elaborate on AEAD --\> GCM (Galois-Counter-Mode):
* 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 (2128) over a irreducible polynomial
* Requires only n+1 block ciphers calls per packet (n=lenght of encrypted and authenticated data).
36
Explain the Galois/Counter Mode (GCM) iteration:
37
Elaborate on the Galois/Counter Mode security aspects:
* 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 0128, in this case authentication will not work.
* If IVs of a lenght =/= 96 bits are used, C0 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 2t-k not 2t (for MAC length t and number of blocks k) as blocks may be modified to make only change parts of the MAC.
38
Explain and elaborate on AEAD --\> Sponge Wrap:
* 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.
39
Mention some key points about SpongeWrap security:
* 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!
40
Describe and graphically present the elements of SpongeWrap operation:
* 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.
41
Graphically explain the Sponge Construction in SHA-3:
Information Security
flashcards
Decks in class (5)
# Cards
