Howdy,

Did some reading yesterday on MACs and want to summarize that information:

MACs are Message Authentication Codes. They take a message m and a key k then produce a MAC(m, k). If you have the key and receive message m with MAC(m, k), you can validate that m wasn’t messed with.

This is helpful in symmetric key messaging. For example., say Alice and Bob are messaging with shared key k. If they send messages without a MAC, a malicious middleman or a random error could scramble up the message and the receiver wouldn’t know the scrambled message was modified. This works even with encryption. If a MAC was also sent, the receiver would know the message was modified in transit.

Of course, MACs don’t solve everything by themselves. Naively, they are fooled by replay attacks. An attack will save a message + MAC pair and resend them later (e.g., resend a message telling a broker to sell shares a stock). This can be solved by adding a count to messages.

Another attack involves forging a MAC. MACs should theoretically prevent this; however, crafty individuals can find bugs with implementation or math.

Given a message, MACs can’t be guessed/forged wtihout the key. There are quite a few different ways we have to create this type of function.

PRFs are functions that take a secret key and message and return an output that looks random. They should be indistinguishable from random functions.

From the definition it’s easy to see why a PRF can be used as a MAC. MAC(k, m) is a number that can only be created if you have the key. PRF(k, m) is a random number that can only be created if you have the key. In fact, you can see that PRFs are stronger than MACs because of the additional requirement of randomness.

So if you create a PRF, you have create a MAC.

One way to make MACs and PRFs is by using hash functions. Specifically, a keyed hash that hashes a message and a key to create a random number.

There are some naive ways of making this work:

H(k, m) = H( k || m ): Secret-Prefix construction aka appending the key before the message. This is weak to hash functions that allow Length-Extension attacks (e.g., SHA2). This attack allows an attacker to turn H(m) and message n into H(m+n) by using H(m) as the initial state for hashing message n. Another attack is that you need to include the key length when you hash. H( 123 || 456) = H(12 || 3456) making the same MAC work for multiple key message pairs. You can fix this with H( length of key || key || message) but this is annoying.

H(k, m) = H( m || k): Secret-Suffix construction aka putting the key after the message. The problem with this is that it’s easy to find colliding MACs. If H(m) = H(n) then H(m || k( = H(n || k).

The main way that people creates makes is through HMAC. Follow the formula using any hash function that is collision resistant or if the hash’s compression function is a PRF.

There is a generic attack that works against all hash based MACs. At some point, you’ll be hashing 2 numbers H(a, b). You can find another hash with the same value H(a, c). You then figure out H(a, c + d) = H(a, b + d), where + is some combination operation that I’m not sure of, so you’ve broken the hash. It takes ~ 2^(n/2) guesses, so it becomes infeasible as you increase the number of bits of the hash.

https://en.wikipedia.org/wiki/HMAC

We can make PRFs from compression algorithms like hashes, so we can make them out of block ciphers as well (in fact, SHA is a hash function who’s compression algorithm is a block cipher). This a CMAC.

You can also build MACs the are specially built from weaker hashes or block ciphers. You don’t need to use the strongest hashes/ciphers or go through the fully process if you do it just right.

It’s worth pointing out that side channels can cause problems (I mean where can’t they cause problems). Other bits of information can leak info about your secrets. For example, MACs not based on compression functions (e.g., SHA3 and SipHash) can be broken if RAM/registers/system state is leaked (SHA2 and BLAKE2 are examples of compression algorithms).

From my understanding, quantum computers have the same kind of power over MACs as they do over single key encryption. Namely, Grover’s algorithm giving a root(n) speed up. This is because MACs and symmetric encryption are built using the same primitives, e.g., hash functions and ciphers. Right now, the only known speed ups from quantum computers come from Grover’s algorithm allowing quantum computers to solve the problem with half the number of bits. There’s no factoring of prime numbers. just good old fashion XOR and AES (aka flipping, shifting, and scrambling bits).

Got a bit about MACs done. Nice!

There might be a follow up looking into some other questions.

Night,

Lucas

Howdy,

Did some reading yesterday on MACs and want to summarize that information:

MACs are Message Authentication Codes. They take a message m and a key k then produce a MAC(m, k). If you have the key and receive message m with MAC(m, k), you can validate that m wasn’t messed with.

This is helpful in symmetric key messaging. For example., say Alice and Bob are messaging with shared key k. If they send messages without a MAC, a malicious middleman or a random error could scramble up the message and the receiver wouldn’t know the scrambled message was modified. This works even with encryption. If a MAC was also sent, the receiver would know the message was modified in transit.

Of course, MACs don’t solve everything by themselves. Naively, they are fooled by replay attacks. An attack will save a message + MAC pair and resend them later (e.g., resend a message telling a broker to sell shares a stock). This can be solved by adding a count to messages.

Another attack involves forging a MAC. MACs should theoretically prevent this; however, crafty individuals can find bugs with implementation or math.

Given a message, MACs can’t be guessed/forged wtihout the key. There are quite a few different ways we have to create this type of function.

PRFs are functions that take a secret key and message and return an output that looks random. They should be indistinguishable from random functions.

From the definition it’s easy to see why a PRF can be used as a MAC. MAC(k, m) is a number that can only be created if you have the key. PRF(k, m) is a random number that can only be created if you have the key. In fact, you can see that PRFs are stronger than MACs because of the additional requirement of randomness.

So if you create a PRF, you have create a MAC.

One way to make MACs and PRFs is by using hash functions. Specifically, a keyed hash that hashes a message and a key to create a random number.

There are some naive ways of making this work:

H(k, m) = H( k || m ): Secret-Prefix construction aka appending the key before the message. This is weak to hash functions that allow Length-Extension attacks (e.g., SHA2). This attack allows an attacker to turn H(m) and message n into H(m+n) by using H(m) as the initial state for hashing message n. Another attack is that you need to include the key length when you hash. H( 123 || 456) = H(12 || 3456) making the same MAC work for multiple key message pairs. You can fix this with H( length of key || key || message) but this is annoying.

H(k, m) = H( m || k): Secret-Suffix construction aka putting the key after the message. The problem with this is that it’s easy to find colliding MACs. If H(m) = H(n) then H(m || k( = H(n || k).

The main way that people creates makes is through HMAC. Follow the formula using any hash function that is collision resistant or if the hash’s compression function is a PRF.

There is a generic attack that works against all hash based MACs. At some point, you’ll be hashing 2 numbers H(a, b). You can find another hash with the same value H(a, c). You then figure out H(a, c + d) = H(a, b + d), where + is some combination operation that I’m not sure of, so you’ve broken the hash. It takes ~ 2^(n/2) guesses, so it becomes infeasible as you increase the number of bits of the hash.

https://en.wikipedia.org/wiki/HMAC

We can make PRFs from compression algorithms like hashes, so we can make them out of block ciphers as well (in fact, SHA is a hash function who’s compression algorithm is a block cipher). This a CMAC.

You can also build MACs the are specially built from weaker hashes or block ciphers. You don’t need to use the strongest hashes/ciphers or go through the fully process if you do it just right.

It’s worth pointing out that side channels can cause problems (I mean where can’t they cause problems). Other bits of information can leak info about your secrets. For example, MACs not based on compression functions (e.g., SHA3 and SipHash) can be broken if RAM/registers/system state is leaked (SHA2 and BLAKE2 are examples of compression algorithms).

From my understanding, quantum computers have the same kind of power over MACs as they do over single key encryption. Namely, Grover’s algorithm giving a root(n) speed up. This is because MACs and symmetric encryption are built using the same primitives, e.g., hash functions and ciphers. Right now, the only known speed ups from quantum computers come from Grover’s algorithm allowing quantum computers to solve the problem with half the number of bits. There’s no factoring of prime numbers. just good old fashion XOR and AES (aka flipping, shifting, and scrambling bits).

Got a bit about MACs done. Nice!

There might be a follow up looking into some other questions.

Night,

Lucas