Notatnik techniczny

MD5 implementacja w C++

Poniżej umieszczam moją implementację algorytmu MD5 w c++.

Kod powstał na potrzeby pewnego konkursu CTF, gdzie musiałem napisać lekko zmodyfikowaną wersję algorytmu MD5. Po usunięciu zmian wymaganych przez zadanie pozostał poniższy kod.

Uwagi odnośnie do kodu

Zwracam uwagę, że w kodzie nie ma ani jednego MACRO. Dzięki constexpr obecnym w nowszych wydaniach c++ możemy uzyskać identyczną szybkość jak dzięki użyciu MACRO, bez potrzeby korzystania z tak mało wygodnych i eleganckich rozwiązań jak pre-procesor.

Kod

#pragma once
#include <cstdint>
 
class md5_computer {
private:
    void process_block ( ) noexcept;
    struct {
        uint32_t state[4];
        uint8_t buffer[64];
    } ctx;
 
public:
    const uint8_t* hash_it(const char* data, uint32_t len ) noexcept;
};
#include "md5_computer.h"
#include "md5_functions.h"
 
#include <cstring>
 
const uint8_t* md5_computer::hash_it( const char* data, uint32_t len ) noexcept
{
    constexpr uint32_t INIT_STATE[] = {0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476};
    memcpy( ctx.state, INIT_STATE, sizeof(ctx.state) );
 
    uint64_t bit_count = len << 3;
    int i = 0;
    while( len >= 64 ){
        memcpy( &ctx.buffer[0], data + 64 * i, 64 );
        process_block( );
        len -= 64;
        i++;
    }
 
    memcpy( &ctx.buffer[0], data + 64 * i, len );
 
    ctx.buffer[len] = 0x80;
    if( len >= 56 ) {
        memset(&ctx.buffer[len+1], 0x0, 63 - len);
        process_block( );
        memset(ctx.buffer, 0x0 , 56 );
    }
    else {
        memset(&ctx.buffer[len+1], 0x0, 55 - len);
    }
 
    memcpy(&ctx.buffer[56], &bit_count, sizeof(bit_count));
    process_block( );
    return (const uint8_t*)&ctx.state;
}

Funkcja md5_computer::process_block( )

void md5_computer::process_block( ) noexcept
{
    uint32_t T[4];
    memcpy(T, ctx.state, 16);
    const uint32_t* x = ( const uint32_t* )ctx.buffer;
 
    constexpr static uint32_t S1[] = { 7 , 12 , 17, 22 };
    FF (T[0], T[1], T[2], T[3], x[ 0], S1[0], 0xd76aa478);
    FF (T[3], T[0], T[1], T[2], x[ 1], S1[1], 0xe8c7b756);
    FF (T[2], T[3], T[0], T[1], x[ 2], S1[2], 0x242070db);
    FF (T[1], T[2], T[3], T[0], x[ 3], S1[3], 0xc1bdceee);
    FF (T[0], T[1], T[2], T[3], x[ 4], S1[0], 0xf57c0faf);
    FF (T[3], T[0], T[1], T[2], x[ 5], S1[1], 0x4787c62a);
    FF (T[2], T[3], T[0], T[1], x[ 6], S1[2], 0xa8304613);
    FF (T[1], T[2], T[3], T[0], x[ 7], S1[3], 0xfd469501);
    FF (T[0], T[1], T[2], T[3], x[ 8], S1[0], 0x698098d8);
    FF (T[3], T[0], T[1], T[2], x[ 9], S1[1], 0x8b44f7af);
    FF (T[2], T[3], T[0], T[1], x[10], S1[2], 0xffff5bb1);
    FF (T[1], T[2], T[3], T[0], x[11], S1[3], 0x895cd7be);
    FF (T[0], T[1], T[2], T[3], x[12], S1[0], 0x6b901122);
    FF (T[3], T[0], T[1], T[2], x[13], S1[1], 0xfd987193);
    FF (T[2], T[3], T[0], T[1], x[14], S1[2], 0xa679438e);
    FF (T[1], T[2], T[3], T[0], x[15], S1[3], 0x49b40821);
 
    constexpr static uint32_t S2[] = { 5 , 9 , 14, 20 };
    GG (T[0], T[1], T[2], T[3], x[ 1], S2[0], 0xf61e2562);
    GG (T[3], T[0], T[1], T[2], x[ 6], S2[1], 0xc040b340);
    GG (T[2], T[3], T[0], T[1], x[11], S2[2], 0x265e5a51);
    GG (T[1], T[2], T[3], T[0], x[ 0], S2[3], 0xe9b6c7aa);
    GG (T[0], T[1], T[2], T[3], x[ 5], S2[0], 0xd62f105d);
    GG (T[3], T[0], T[1], T[2], x[10], S2[1],  0x2441453);
    GG (T[2], T[3], T[0], T[1], x[15], S2[2], 0xd8a1e681);
    GG (T[1], T[2], T[3], T[0], x[ 4], S2[3], 0xe7d3fbc8);
    GG (T[0], T[1], T[2], T[3], x[ 9], S2[0], 0x21e1cde6);
    GG (T[3], T[0], T[1], T[2], x[14], S2[1], 0xc33707d6);
    GG (T[2], T[3], T[0], T[1], x[ 3], S2[2], 0xf4d50d87);
    GG (T[1], T[2], T[3], T[0], x[ 8], S2[3], 0x455a14ed);
    GG (T[0], T[1], T[2], T[3], x[13], S2[0], 0xa9e3e905);
    GG (T[3], T[0], T[1], T[2], x[ 2], S2[1], 0xfcefa3f8);
    GG (T[2], T[3], T[0], T[1], x[ 7], S2[2], 0x676f02d9);
    GG (T[1], T[2], T[3], T[0], x[12], S2[3], 0x8d2a4c8a);
 
    constexpr static uint32_t S3[] = { 4 , 11 , 16, 23 };
    HH (T[0], T[1], T[2], T[3], x[ 5], S3[0], 0xfffa3942);
    HH (T[3], T[0], T[1], T[2], x[ 8], S3[1], 0x8771f681);
    HH (T[2], T[3], T[0], T[1], x[11], S3[2], 0x6d9d6122);
    HH (T[1], T[2], T[3], T[0], x[14], S3[3], 0xfde5380c);
    HH (T[0], T[1], T[2], T[3], x[ 1], S3[0], 0xa4beea44);
    HH (T[3], T[0], T[1], T[2], x[ 4], S3[1], 0x4bdecfa9);
    HH (T[2], T[3], T[0], T[1], x[ 7], S3[2], 0xf6bb4b60);
    HH (T[1], T[2], T[3], T[0], x[10], S3[3], 0xbebfbc70);
    HH (T[0], T[1], T[2], T[3], x[13], S3[0], 0x289b7ec6);
    HH (T[3], T[0], T[1], T[2], x[ 0], S3[1], 0xeaa127fa);
    HH (T[2], T[3], T[0], T[1], x[ 3], S3[2], 0xd4ef3085);
    HH (T[1], T[2], T[3], T[0], x[ 6], S3[3],  0x4881d05);
    HH (T[0], T[1], T[2], T[3], x[ 9], S3[0], 0xd9d4d039);
    HH (T[3], T[0], T[1], T[2], x[12], S3[1], 0xe6db99e5);
    HH (T[2], T[3], T[0], T[1], x[15], S3[2], 0x1fa27cf8);
    HH (T[1], T[2], T[3], T[0], x[ 2], S3[3], 0xc4ac5665);
 
    constexpr static uint32_t S4[] = { 6 , 10 , 15, 21 };
    II (T[0], T[1], T[2], T[3], x[ 0], S4[0], 0xf4292244);
    II (T[3], T[0], T[1], T[2], x[ 7], S4[1], 0x432aff97);
    II (T[2], T[3], T[0], T[1], x[14], S4[2], 0xab9423a7);
    II (T[1], T[2], T[3], T[0], x[ 5], S4[3], 0xfc93a039);
    II (T[0], T[1], T[2], T[3], x[12], S4[0], 0x655b59c3);
    II (T[3], T[0], T[1], T[2], x[ 3], S4[1], 0x8f0ccc92);
    II (T[2], T[3], T[0], T[1], x[10], S4[2], 0xffeff47d);
    II (T[1], T[2], T[3], T[0], x[ 1], S4[3], 0x85845dd1);
    II (T[0], T[1], T[2], T[3], x[ 8], S4[0], 0x6fa87e4f);
    II (T[3], T[0], T[1], T[2], x[15], S4[1], 0xfe2ce6e0);
    II (T[2], T[3], T[0], T[1], x[ 6], S4[2], 0xa3014314);
    II (T[1], T[2], T[3], T[0], x[13], S4[3], 0x4e0811a1);
    II (T[0], T[1], T[2], T[3], x[ 4], S4[0], 0xf7537e82);
    II (T[3], T[0], T[1], T[2], x[11], S4[1], 0xbd3af235);
    II (T[2], T[3], T[0], T[1], x[ 2], S4[2], 0x2ad7d2bb);
    II (T[1], T[2], T[3], T[0], x[ 9], S4[3], 0xeb86d391);
 
    for( int i=0; i < 4; ++i )
        ctx.state[i] += T[i];
}

Funkcje składowe algorytmu MD5

#pragma once
 
template<typename T>
static inline constexpr T ROTATE_LEFT( const T x, const uint32_t n ) noexcept {
    return (x << n) | (x >> (32-n));
}
 
//=================================================s
 
template<typename T>
static inline constexpr T F( const T x, const T y, const T z ) noexcept {
    return (x & y) | (~x & z);
}
 
template<typename T>
inline constexpr void FF( T& a, const T b, const T c, const T d, const T x, const uint32_t s, const uint32_t ac ) noexcept {
    a += F(b, c, d) + x + ac;
    a = ROTATE_LEFT (a, s) + b;
}
 
//=================================================
 
template<typename T>
static inline constexpr T G( const T x, const T y, const T z ) noexcept {
    return (x & z) | (y & ~z);
}
 
template<typename T>
inline constexpr void GG( T& a, const T b, const T c, const T d, const T x, const uint32_t s, const uint32_t ac ) noexcept {
    a += G (b, c, d) + x + ac;
    a = ROTATE_LEFT (a, s) + b;
}
 
//=================================================
 
template<typename T>
static inline constexpr T H( const T x, const T y, const T z ) noexcept {
    return x ^ y ^ z;
}
 
template<typename T>
inline constexpr void HH( T& a, const T b, const T c, const T d, const T x, const uint32_t s, const uint32_t ac ) noexcept {
    a += H(b, c, d) + x + ac;
    a = ROTATE_LEFT(a, s) + b;
}
 
//=================================================
 
template<typename T>
static constexpr T I( const T x, const T y, const T z ) noexcept {
    return y ^ (x | ~z);
}
 
template<typename T>
inline constexpr void II( T& a, const T b, const T c, const T d, const T x, const uint32_t s, const uint32_t ac ) noexcept {
    a += I (b, c, d) + x + ac;
    a = ROTATE_LEFT (a, s) + b;
}

Ten kod był pisany w konkretnym celu i zawiera pewne ograniczenie. Aby policzyć hash, musimy wczytać do bufora cały blok danych do hashowania, nie ma możliwości podzielenia tego bloku na kawałki.

Odnośniki