Эксперимент: ГПСЧ на таймерах с помощью PHP

[Number571]

Всё бы хорошо, если бы не было так плохо. Пробовали ли вы считать энтропию от обычного ГПСЧ, который уже встроен в любые стандартные библиотеки любого языка программирования, включая PHP? Вы бы обнаружили, что при вычислении энтропии почти любая встроенная функция рандома будет всегда стремиться к 8 битам вне зависимости от криптостойкости генератора - даже обычный линейный конгруэнтный генератор по вашей функции будет стремиться к максимальному значению. А всё по тому, что некорректно проводить тестирование качества генератора по формуле вычисления энтропии. При вычислении энтропии мы должны брать во внимание не только те байты, которые уже имеются на руках, но также и априорные вероятности того, как и за счёт чего эти байты были получены. Из-за этого реальная энтропия вычисления будет куда ниже вычисляемой по сырым байтам.

Вот как пример кода на языке Go, где я использую стандартный математический (не криптографический) ГПСЧ и получаю "энтропию" в 7.997064, хотя фактическая энтропия сводится только лишь к использованию time.Now().UnixNano() - и это вряд-ли достигнет даже пары бит.

package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

func entropy(b []byte) float64 {
	freq := make(map[byte]uint, 256)
	for _, v := range b {
		freq[v]++
	}
	e := .0
	total := uint(len(b))
	for _, v := range freq {
		if v > 0 {
			p := float64(v) / float64(total)
			e -= p * math.Log2(p)
		}
	}
	return e
}

func main() {
	r := rand.New(rand.NewSource(time.Now().UnixNano()))

	buf := make([]byte, 65536)
	if _, err := r.Read(buf); err != nil {
		panic(err)
	}

	fmt.Printf("Entropy: %f\n", entropy(buf))
}

[3ball]

Благодарю за уточнение. Да, вы правы в данном случае энтропия Шеннона будет иллюзией, а реальная энтропия от джиттера не будет превышать 1-2 бита. Но разве реальная случайность не зависит от наблюдателя? Для взломщика это скорее всего будут те самые 6-7 бит, ибо он не может восстановить внутреннее состояние таймеров. Даже если он знает алгоритм и начальный seed, он не знает, в какой момент времени были сделаны замеры (T1, T2), а джиттер вносит непредсказуемость. Это не классический PRNG с фиксированным состоянием, а гибрид, где время выступает источником скрытой энтропии. Поэтому для внешнего наблюдателя эффективная энтропия на байт действительно близка к 8, хотя для создателя, знающего состояние, она равна энтропии джиттера. Минус такого подхода - синхронизация почти невозможна, потому что запустить два компьютера и получить один и тот же результат не получится, выход всегда разный. И да, а вы не задумывались, что было бы если бы такой генератор построить на сверхточных часах? :)