прямое предсказание Linux / dev / urandom - PullRequest
Новая
       13

прямое предсказание Linux / dev / urandom

2 голосов
/ 03 августа 2011

Это вопрос о реализации ядра Linux /dev/urandom.Если пользователь просит прочитать очень большой объем данных (гигабайт) и энтропия не добавляется в пул, если возможно предсказать следующие данные, сгенерированные из urandom, на основе текущих данных?

Обычный случай - это когдаэнтропия часто добавляется в пул, но в моем случае мы можем считать, что никакой дополнительной энтропии не было (например, добавление ее было отключено патчем ядра).Так что в моем случае вопрос касается самого алгоритма urandom.

Источник - /drivers/char/random.c или http://www.google.com/codesearch#KMCRKdMbI4g/drivers/char/random.c&q=urandom%20linux&type=cs&l=116

или http://lxr.linux.no/linux+v3.3.3/drivers/char/random.c

 // data copying loop
    while (nbytes) {
            extract_buf(r, tmp);

            memcpy(buf, tmp, i);
            nbytes -= i;
            buf += i;
            ret += i;
    }

static void extract_buf(struct entropy_store *r, __u8 *out)
{
        int i;
        __u32 hash[5], workspace[SHA_WORKSPACE_WORDS];
        __u8 extract[64];

        /* Generate a hash across the pool, 16 words (512 bits) at a time */
        sha_init(hash);
        for (i = 0; i < r->poolinfo->poolwords; i += 16)
                sha_transform(hash, (__u8 *)(r->pool + i), workspace);

        /*
         * We mix the hash back into the pool to prevent backtracking
         * attacks (where the attacker knows the state of the pool
         * plus the current outputs, and attempts to find previous
         * ouputs), unless the hash function can be inverted. By
         * mixing at least a SHA1 worth of hash data back, we make
         * brute-forcing the feedback as hard as brute-forcing the
         * hash.
         */
        mix_pool_bytes_extract(r, hash, sizeof(hash), extract);

        /*
         * To avoid duplicates, we atomically extract a portion of the
         * pool while mixing, and hash one final time.
         */
        sha_transform(hash, extract, workspace);
        memset(extract, 0, sizeof(extract));
        memset(workspace, 0, sizeof(workspace));

        /*
         * In case the hash function has some recognizable output
         * pattern, we fold it in half. Thus, we always feed back
         * twice as much data as we output.
         */
        hash[0] ^= hash[3];
        hash[1] ^= hash[4];
        hash[2] ^= rol32(hash[2], 16);
        memcpy(out, hash, EXTRACT_SIZE);
        memset(hash, 0, sizeof(hash));
}

Существует механизм предотвращения возврата, но как насчет «прямого следа»?

Например: я выполнил однократный системный вызов чтения для 500 МБ из urandom, и все данные до 200-го МБ были известны, и нетдополнительная энтропия в пуле, могу ли я предсказать, каким будет 201-й мегабайт?

Ответы [ 2 ]

4 голосов
/ 03 августа 2011

Определение «криптографически стойкого генератора псевдослучайных чисел» состоит в том, что в вычислительном отношении невозможно отличить его выходные данные от выходных данных генератора истинных случайных чисел. Если бы вы могли предсказать будущий результат из прошлого, вы могли бы так различать; следовательно, вы не можете сделать это, если алгоритм urandom в Linux не слаб.

Этот код не похож на какой-либо стандартный псевдослучайный генератор для меня - у людей с Linux есть печальная привычка «раскручивать свои собственные» - но, в любом случае, нарушение этого кода может быть опубликованным результатом. Так что, если это можно сломать, я подозреваю, что это нелегко.

Конечно, цель дизайна в том, чтобы "нет" было ответом на ваш вопрос.

[править]

Конечно, в теоретико-информационном смысле ответ - «да», потому что вы не можете получить бесконечную энтропию из конечной энтропии. Но в теоретико-информационном смысле не существует надежного шифра, кроме одноразовой записи. Я предполагаю, что вы спрашиваете о практическом / криптографическом смысле.

[править 2]

Небольшой поиск обнаруживает эту статью , в которой утверждается, что она демонстрирует атаку против "форвардной безопасности" в Linux / dev / urandom. (То есть, учитывая состояние генератора, попытайтесь восстановить более ранние состояния.)

Вот почему программисты не должны никогда пытаться изобрести собственную криптографию. Независимо от того, насколько вы умны, некоторые израильские ученые, которые занимаются этим для жизни, могут заставить вас выглядеть глупо.

Тем не менее, я не вижу никаких атак на выход генератора, о чем вы спрашиваете.

4 голосов
/ 03 августа 2011

В принципе, да, вы можете предсказать. Когда нет доступной энтропии, dev / urandom становится PRNG, и его выход в принципе может быть предсказан, как только известно его внутреннее состояние. На практике это не так просто, потому что внутреннее состояние достаточно велико, а хеш-функция не позволяет нам работать в обратном направлении. Это можно определить методом проб и ошибок, но это может занять много времени.

...