Уроки утечки LinkedIn

[waqur]

Poul-Henning Kamp делает выводы из утечки базы данных хэшей к паролям пользователей социальной сети LinkedIn:
http://queue.acm.org/detail.cfm?id=2254400

Статья в целом хорошая и годная, но совет зациклить хэш-функцию на тысячу итераций (равно как и использовать эквивалентные bcrypt/PBKDF2) не очень хорош, с точки зрения устойчивости к аппаратному криптоанализу на FPGA, и с точки зрения потери энтропии. Чтобы сделать жизнь аппаратных ребят веселее и увлекательнее, лучше сделать алгоритм, которому нужно много памяти. Например:

std::vector< unsigned char >  OneWayTransform(
    const std::string&  password
)
{
    // 1. Распределить память
    std::vector< unsigned char >  blob_storage( 16*1024*1024, 0 );
    unsigned char*  blob = &(blob_storage.at(0));

    // 2. Залить память выводом линейного ГПСЧ
    std::vector< unsigned char >  noise = SHA2(
        password.begin(), password.end()
    );
    unsigned int  t = (
        ((unsigned int)( noise.at(0) ) << 24) |
        ((unsigned int)( noise.at(1) ) << 16) |
        ((unsigned int)( noise.at(2) ) << 8 ) |
         (unsigned int)( noise.at(3) )
    );
    unsigned char*  p = blob;
    unsigned char*  p_limit = p + blob_storage.size();
    while( p != p_limit )
    {
        // константы из MSVC libc rand()
        t = 214013U*t + 2531011U;
        *p++ = (unsigned char)( (t >> 16) & 0xFF );
    }

    // 3. Применить HMAC к памяти точечно, в случайных местах
    for( int  i = 0; i < OWT_ITERATION_COUNT; ++i )
    {
        t = 214013U*t + 2531011U;
        unsigned int  index = (t & 0x7FFFF000) >> 12;
        assert( (index + 1) * 32 <= blob_storage.size() );

        noise = HMAC_SHA2(
            password.begin(), password.end(), 
            blob + (index * 32)
        );
        memcpy( blob + (index * 32), &(noise.at(0)), 32 );
    }

    // 4. Свернуть всё вместе
    //    (Последовательность, сгенерированная преобразованием t <- (214013*t + 2531011) mod 2^32,
    //     имеет длину цикла 2^32. Таким образом, это преобразование не теряет энтропии.)
    unsigned int  results[8] = { 0, };
    for( int  i = 0, i_limit = blob_storage.size() / 32; i < i_limit; ++i )
        for( int  j = 0; j < 8; ++j )
        {
            t = results[j];
            t ^= ((unsigned int)( blob[i*32 + j*4] )     << 24) |
                 ((unsigned int)( blob[i*32 + j*4 + 1] ) << 16) |
                 ((unsigned int)( blob[i*32 + j*4 + 2] ) << 8 ) |
                  (unsigned int)( blob[i*32 + j*4 + 3] );
            t = 214013U*t + 2531011U;
            results[j] = t;
        }

    std::vector< unsigned char >  ret_value( 32, 0 );
    for( int  j = 0; j < 8; ++j )
    {
        ret_value.at(4*j)   = (unsigned char)( (results[j] >> 24) & 0xFF );
        ret_value.at(4*j+1) = (unsigned char)( (results[j] >> 16) & 0xFF );
        ret_value.at(4*j+2) = (unsigned char)( (results[j] >> 8 ) & 0xFF );
        ret_value.at(4*j+3) = (unsigned char)(  results[j]        & 0xFF );
    }
    return  ret_value;
}

Первоначальная заливка и свёртка итогов заняли некоторое время, но его можно выиграть уменьшением количества итераций дорогого в вычислении HMAC (OWT_ITERATION_COUNT), зато количество задействованных в вычислениях транзисторов сразу увеличилось на 3-4 порядка, как и рассеиваемое системой криптоанализа тепло, как и счета криптоаналитика за электричество. В видеокартах объём памяти для кода, кэши и пропускная способность шины данных тоже не резиновые.