28-and-29

Challenge 28: Implement a SHA-1 keyed MAC

Find a SHA-1 implementation in the language you code in.

Don't cheat. It won't work. Do not use the SHA-1 implementation your language already provides (for instance, don't use the "Digest" library in Ruby, or call OpenSSL; in Ruby, you'd want a pure-Ruby SHA-1).

Write a function to authenticate a message under a secret key by using a secret-prefix MAC, which is simply:

SHA1(key || message)

Verify that you cannot tamper with the message without breaking the MAC you've produced, and that you can't produce a new MAC without knowing the secret key.

In [1]:
from libmatasano import html_test, bxor

Two important remarks:

  • We know SHA-1 has security issues since 2004 (see Bruce Schneier's blog post). At the time they were only theoretical issues, meaning that they didn't give a way to actually break it, but we were pretty sure it would get broken soon. This is what motivated the switch to SHA-2. Nowadays SHA-1 is completely broken (see Leurent and Peyrin 2020)
  • The attack in the next challenge does not use the fact that SHA-1 is broken. It uses a specific property of SHA-1 due to the way it is built (“Merkle–Damgård Construction”). The same attack would work even with SHA-2 because SHA-2 has that same property.

    Said differently: the attack in the next challenge is not due to a problem in SHA-1 (even if SHA-1 is broken as hell) but to a problem in the (bad) MAC algorithm we build on top of SHA-1.

Implementing SHA-1 in Python

The instructions do not explicitely ask us to implement SHA-1 ourselves, but this is a nice opportunity to dip your toes in the waters of hash functions implementation.

For the specifications you can use RFC 3174 or NIST FIPS 180-4.

For some test data with intermediate values (useful for debugging your implementation) see this page:

https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values

In [2]:
from libmatasano import split_bytes_in_blocks

def sha1(msg):
    # following RFC 3174
    # https://tools.ietf.org/html/rfc3174

    # we are prioritizing readability and similarity with the specs
    # over optimization

    # we are always in big-endian form in SHA1
    # (Section 2.c: "The least significant four bits of the integer are
    # represented by the right-most hex digit of the word representation")

    # to use as a bit mask for reduction modulo 2^32
    MAX_WORD = 0xFFFFFFFF

    # Section 3: Operations on Words

    def S(X, n):
        'circular left shift (a.k.a "rotate left")'
        # don't forget reduction modulo 2^32 !
        # it is not explicitely written in the formula in the RFC
        # (it is in the prose below it though)
        return ((X << n) | (X >> (32-n))) & MAX_WORD

    # Section 4: Padding

    # we are limiting ourselves to messages being byte strings
    # even though specification mentions bit strings of any length
    assert isinstance(msg, bytes)

    # message length in bits
    msg_length = len(msg)*8

    # we must append a "1" bit.
    # since we are always working with bytes
    # the appended bit will always be at the beginning of the next byte

    # computing the number of "zeroes" to append
    # we need msg_length + 1 + m + 64 = 0 mod 512
    # thus m = -(msg_length + 1 + 64) mod 512
    m = -(msg_length + 1 + 64) % 512

    # m+1 will always be a multiple of 8 in our case
    padded_msg = (msg
                  + bytes([0b10000000])
                  + b'\x00'*(m//8)
                  + msg_length.to_bytes(8, byteorder='big')
                 )

    words = [int.from_bytes(w, byteorder='big')
             for w in split_bytes_in_blocks(padded_msg, 4)]

    # "The padded message will contain 16 * n words"
    n = len(words)/16
    assert n.is_integer()
    n = int(n)

    # "The padded message is regarded as a sequence of n blocks M(1), M(2), …"
    M = split_bytes_in_blocks(words, 16)

    # Section 5: Functions and Constants Used

    def f(t, B, C, D):
        if 0 <= t <= 19:
            return (B & C) | ((~B) & D)
        elif 20 <= t <= 39 or 60 <= t <= 79:
            return B ^ C ^ D
        elif 40 <= t <= 59:
            return (B & C) | (B & D) | (C & D)
        else:
            raise Exception('t must be between 0 and 79 inclusive')

    # this could be optimized, for instance with an array
    # but this way is closer to how it is described in the specs
    def K(t):
        if 0 <= t <= 19:
            return 0x5A827999
        elif 20 <= t <= 39:
            return 0x6ED9EBA1
        elif 40 <= t <= 59:
            return 0x8F1BBCDC
        elif 60 <= t <= 79:
            return 0xCA62C1D6
        else:
            raise Exception('t must be between 0 and 79 inclusive')

    # Section 6: Computing the Message Digest
    # Using "method 1" (Section 6.1)

    H0 = 0x67452301
    H1 = 0xEFCDAB89
    H2 = 0x98BADCFE
    H3 = 0x10325476
    H4 = 0xC3D2E1F0

    for i in range(len(M)):
        W = M[i]
        assert len(W) == 16
        
        for t in range(16, 80):
            W.append( S(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16],
                        n=1) )

        A, B, C, D, E = H0, H1, H2, H3, H4

        for t in range(80):
            TEMP = (S(A, 5) + f(t, B, C, D) + E + W[t] + K(t)) & MAX_WORD

            E = D; D = C; C = S(B, 30); B = A; A = TEMP

        H0 = (H0 + A) & MAX_WORD
        H1 = (H1 + B) & MAX_WORD
        H2 = (H2 + C) & MAX_WORD
        H3 = (H3 + D) & MAX_WORD
        H4 = (H4 + E) & MAX_WORD

    result = b''.join(H.to_bytes(4, byteorder='big') for H in [H0, H1, H2, H3, H4])

    return result
In [3]:
# testing with the sha1 from hashlib
import hashlib
import os
from random import randint

for _ in range(5):
    size = randint(3,256)
    msg = os.urandom(size)
    assert sha1(msg) == hashlib.sha1(msg).digest()
    
html_test(True)
OK

Implementing the MAC

By far the simplest part.

“MAC” is for “Message Authentication Code”, it's the equivalent of signatures for symmetric cryptography (signatures are part of asymmetric cryptography).

In [4]:
def secret_prefix_sha1_mac(msg, key):
    return sha1(key + msg)
In [5]:
key = os.urandom(16)
msg = b'must not be altered'
In [6]:
secret_prefix_sha1_mac(msg, key)
Out[6]:
b'<\xf3\x90\x10\xfa\xda\xc3A\x17\x10e\x12[\xedHv\xe5\xfcp\x90'
In [7]:
secret_prefix_sha1_mac(bxor(msg, b'modification'), key)
Out[7]:
b'}]\xbbB\xd0\xfe\xe7\xd5{\xb7\x15\xb7\x10RvB\xc8\xc5\x06u'
In [8]:
secret_prefix_sha1_mac(msg + b'adding some bytes...', key)
Out[8]:
b'j_I\x83\xc0\x86\xa4\x86\xe1T\x1b5F\xf2\x15\xfb\xa1\xd5-\xd2'

There isn't really a way to "verify" that we cannot break a MAC. Here we just observed that if you modify the message the output is modified as well. The property a MAC function should satisfy is that someone who doesn't know the key must not be able to create a value Y such that max(modified_message, key) == Y. Said differently a person knowing the key and receiving a pair (message, tag) can make sure that the tag was computed by someone who knows the key as well for this exact message.

Challenge 29: Break a SHA-1 keyed MAC using length extension

Secret-prefix SHA-1 MACs are trivially breakable.

The attack on secret-prefix SHA1 relies on the fact that you can take the ouput of SHA-1 and use it as a new starting point for SHA-1, thus taking an arbitrary SHA-1 hash and "feeding it more data".

Since the key precedes the data in secret-prefix, any additional data you feed the SHA-1 hash in this fashion will appear to have been hashed with the secret key.

To carry out the attack, you'll need to account for the fact that SHA-1 is "padded" with the bit-length of the message; your forged message will need to include that padding. We call this "glue padding". The final message you actually forge will be:

SHA1(key || original-message || glue-padding || new-message)

(where the final padding on the whole constructed message is implied)

Note that to generate the glue padding, you'll need to know the original bit length of the message; the message itself is known to the attacker, but the secret key isn't, so you'll need to guess at it.

This sounds more complicated than it is in practice.

To implement the attack, first write the function that computes the MD padding of an arbitrary message and verify that you're generating the same padding that your SHA-1 implementation is using. This should take you 5-10 minutes.

Now, take the SHA-1 secret-prefix MAC of the message you want to forge --- this is just a SHA-1 hash --- and break it into 32 bit SHA-1 registers (SHA-1 calls them "a", "b", "c", &c).

Modify your SHA-1 implementation so that callers can pass in new values for "a", "b", "c" &c (they normally start at magic numbers). With the registers "fixated", hash the additional data you want to forge.

Using this attack, generate a secret-prefix MAC under a secret key (choose a random word from /usr/share/dict/words or something) of the string:

"comment1=cooking%20MCs;userdata=foo;comment2=%20like%20a%20pound%20of%20bacon"

Forge a variant of this message that ends with ";admin=true".

This is a very useful attack: For instance: Thai Duong and Juliano Rizzo, who got to this attack before we did, used it to break the Flickr API.

In [9]:
original_msg = (b"comment1=cooking%20MCs;userdata=foo;"
                b"comment2=%20like%20a%20pound%20of%20bacon")
key = os.urandom(16)

mac = sha1(key + original_msg)

We have the MAC of original_msg, that is the SHA1 hash of key + original_msg. What we want to have is a valid MAC for a string containing new_text, without having the knowledge of key.

Here is how we are going to do it: the SHA1 function works by keeping a "state" that is "updated" for each block of 512 bits from the data that must be hashed. When SHA-1 hashes the concatenation X || Y of two strings X and Y, during the processing of the blocks of X the state goes through the same values as if we were hashing just X.

The idea of the length-extension attack is then the following: using the hash we have of some unknown string X, we can copy the state the SHA-1 function was in when it returned this hash. Then we can use our "cloned" SHA-1 to hash some more bytes Y. We get the hash of X || Y even without knowing X.

How hard is it to "clone the state"? Not hard at all: in SHA-1 the hash that is returned is the concatenation of registers H0, H1, H2, H3, H4, which are... the state registers themselves. I don't know why the instructions mention the A, B, C, … registers.

In [10]:
H0, H1, H2, H3, H4 = [int.from_bytes(x, byteorder='big')
                      for x in split_bytes_in_blocks(mac, blocksize=4)]

H0, H1, H2, H3, H4
Out[10]:
(3723479287, 289492558, 2524822031, 820116683, 484465219)

Good ! Cloning should be as simple as initializing a new SHA-1 but setting the H0, H1, H2, H3, H4 values to the values we just recovered instead of the fixed values given in the specification.

But there is still something we did not take into account: padding.

First, we must alter the way our "cloned SHA-1 function" does padding: we want a padding corresponding to the entire forged message, not just the extra bytes we are feeding the cloned SHA-1 with.

Second problem with padding: The state we just cloned does not correspond to just key + original_msg but to this plus the padding that was added by SHA-1. This is our X: key + original_msg + glue_padding

We need to know the value of this "glue padding" because we will have to integrate it in our forged message.

Finding the padding value is very simple ... when you know the length of the input you are padding. We know the length of the original message; but are we supposed to know the lenght of the secret key? From the instructions, it seems that we don't:

Note that to generate the glue padding, you'll need to know the original bit length of the message; the message itself is known to the attacker, but the secret key isn't, so you'll need to guess at it.

This seems a bit weird; In many cases even if the attacker does not know the value of the key, he should be able to know its length, for keysizes are rarely random and are often set by a strict standard.

Suppose we don't know the key size, what can we do ? We could just try to guess (which is what the instructions seem to indicate) and have several candidate message-MAC pairs, one for each keysize candidate. You can just submit all of them to the victim and hope that doing so is not flagged as "suspicious behavior". Actually even if the victim server is using behavioral detection, this behavior is not that likely to trigger a warning because we don't have that many candidates to try out: we are trying different key sizes not key values

New functions and MAC forgery

We are going to need sha1 padding as a separate function, and with a parameter to modify its behaviour:

In [11]:
def sha1_padding(msg, forced_msg_byte_length=None):

    # we are limiting ourselves to messages being byte strings
    # even though specification mentions bit strings of any length
    assert isinstance(msg, bytes)

    # message length in bits
    if forced_msg_byte_length == None:
        msg_length = len(msg)*8
    else:
        msg_length = forced_msg_byte_length*8

    # we must append a "1" bit.
    # since we are always working with bytes
    # the appended bit will always be at the beginning of the next byte

    # computing the number of "zeroes" to append
    # we need msg_length + 1 + m + 64 = 0 mod 512
    # thus m = -(msg_length + 1 + 64) mod 512
    m = -(msg_length + 1 + 64) % 512

    # m+1 will always be a multiple of 8 in our case
    padded_msg = (msg
                  + bytes([0b10000000])
                  + b'\x00'*(m//8)
                  + msg_length.to_bytes(8, byteorder='big')
                 )

    return padded_msg

And here is our new SHA-1 function with optional parameters to allow cloning:

In [12]:
def sha1(msg, state=None, message_added_length=None):
    # following RFC 3174
    # https://tools.ietf.org/html/rfc3174

    # we are prioritizing readability and similarity with the specs
    # over optimization

    # we are always in big-endian form in SHA1
    # (Section 2.c: "The least significant four bits of the integer are
    # represented by the right-most hex digit of the word representation")

    # to use as a bit mask for reduction modulo 2^32
    MAX_WORD = 0xFFFFFFFF

    # Section 3: Operations on Words

    def S(X, n):
        'circular left shift (a.k.a "rotate left")'
        # don't forget reduction modulo 2^32 !
        # it is not explicitely written in the formula in the RFC
        # (it is in the prose below it though)
        return ((X << n) | (X >> (32-n))) & MAX_WORD

    # Section 4: Padding
    
    if message_added_length == None:
        padded_msg = sha1_padding(msg)
    else:
        forced_msg_byte_length = len(msg) + message_added_length
        padded_msg = sha1_padding(msg, forced_msg_byte_length)

    words = [int.from_bytes(w, byteorder='big')
             for w in split_bytes_in_blocks(padded_msg, 4)]

    # "The padded message will contain 16 * n words"
    n = len(words)/16
    assert n.is_integer()
    n = int(n)

    # "The padded message is regarded as a sequence of n blocks M(1), M(2), …"
    M = split_bytes_in_blocks(words, 16)

    # Section 5: Functions and Constants Used

    def f(t, B, C, D):
        if 0 <= t <= 19:
            return (B & C) | ((~B) & D)
        elif 20 <= t <= 39 or 60 <= t <= 79:
            return B ^ C ^ D
        elif 40 <= t <= 59:
            return (B & C) | (B & D) | (C & D)
        else:
            raise Exception('t must be between 0 and 79 inclusive')

    # this could be optimized, for instance with an array
    # but this way is closer to how it is described in the specs
    def K(t):
        if 0 <= t <= 19:
            return 0x5A827999
        elif 20 <= t <= 39:
            return 0x6ED9EBA1
        elif 40 <= t <= 59:
            return 0x8F1BBCDC
        elif 60 <= t <= 79:
            return 0xCA62C1D6
        else:
            raise Exception('t must be between 0 and 79 inclusive')

    # Section 6: Computing the Message Digest
    # Using "method 1" (Section 6.1)

    if state == None:
        H0 = 0x67452301
        H1 = 0xEFCDAB89
        H2 = 0x98BADCFE
        H3 = 0x10325476
        H4 = 0xC3D2E1F0
    else:
        # SHA-1 state cloning
        assert isinstance(state, tuple)
        assert len(state) == 5
        assert all(isinstance(x, int) for x in state)

        H0, H1, H2, H3, H4 = state

    for i in range(len(M)):
        W = M[i]
        assert len(W) == 16
        
        for t in range(16, 80):
            W.append( S(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16],
                        n=1) )

        A, B, C, D, E = H0, H1, H2, H3, H4

        for t in range(80):
            TEMP = (S(A, 5) + f(t, B, C, D) + E + W[t] + K(t)) & MAX_WORD

            E = D; D = C; C = S(B, 30); B = A; A = TEMP

        H0 = (H0 + A) & MAX_WORD
        H1 = (H1 + B) & MAX_WORD
        H2 = (H2 + C) & MAX_WORD
        H3 = (H3 + D) & MAX_WORD
        H4 = (H4 + E) & MAX_WORD

    result = b''.join(H.to_bytes(4, byteorder='big') for H in [H0, H1, H2, H3, H4])

    return result

Okay, now we're ready

In [13]:
# say that's our "guess"
keysize = 16

# to get the glue padding
# we will compute a padding of a random key of the proper size
# and the original message,
# and we only keep the added bytes
glue_padding = sha1_padding(os.urandom(keysize) + original_msg)[keysize + len(original_msg):]

message_added_length = keysize + len(original_msg) + len(glue_padding)
extra_text = b';admin=true'
forged_mac = sha1(extra_text, (H0, H1, H2, H3, H4), message_added_length)

forged_msg = original_msg + glue_padding + extra_text

html_test(sha1(key + forged_msg) == forged_mac)
OK