Comments 7
Всё бы хорошо, если бы не было так плохо. Пробовали ли вы считать энтропию от обычного ГПСЧ, который уже встроен в любые стандартные библиотеки любого языка программирования, включая 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))
}
Благодарю за уточнение. Да, вы правы в данном случае энтропия Шеннона будет иллюзией, а реальная энтропия от джиттера не будет превышать 1-2 бита. Но разве реальная случайность не зависит от наблюдателя? Для взломщика это скорее всего будут те самые 6-7 бит, ибо он не может восстановить внутреннее состояние таймеров. Даже если он знает алгоритм и начальный seed, он не знает, в какой момент времени были сделаны замеры (T1, T2), а джиттер вносит непредсказуемость. Это не классический PRNG с фиксированным состоянием, а гибрид, где время выступает источником скрытой энтропии. Поэтому для внешнего наблюдателя эффективная энтропия на байт действительно близка к 8, хотя для создателя, знающего состояние, она равна энтропии джиттера. Минус такого подхода - синхронизация почти невозможна, потому что запустить два компьютера и получить один и тот же результат не получится, выход всегда разный. И да, а вы не задумывались, что было бы если бы такой генератор построить на сверхточных часах? :)
Но разве реальная случайность не зависит от наблюдателя?
Если не углубляться в философию наблюдателя и говорить именно что про +- реальную случайность, то в контексте криптографии - не зависит. Если случайность реальна, то и взломать или найти закономерности в ней будет теоретически невозможно / неосуществимо.
Для взломщика это скорее всего будут те самые 6-7 бит, ибо он не может восстановить внутреннее состояние таймеров. Даже если он знает алгоритм и начальный seed, он не знает, в какой момент времени были сделаны замеры (T1, T2)
Предположим, что это вообще единственная модель угроз, доступная криптоаналитику. Даже в этом случае, T1,T2 - это 64-битные числа и для правильного их нахождения потребуется потратить приблизительно 2^65 операций. Теперь примем во внимание, что сам timestamp - это не случайное число, мы чётко знаем его поведение - оно увеличивается, а некоторая его часть остаётся в основном неизменной (по типу префикса 17755... для текущего времени). Это говорит о том, что область вычислений на самом деле куда ниже 2^64. Итого, мы получаем, что даже если бы генератор был +- безопасным, он является небезопасным по выбранным параметрам - буквально уязвим к перебору при достаточных средствах злоумышленника.
Поэтому для внешнего наблюдателя эффективная энтропия на байт действительно близка к 8, хотя для создателя, знающего состояние, она равна энтропии джиттера.
Энтропия - это абсолютная величина, вы говорите про вычислительную сложность. Из более-менее близкого примера - это пароль и пароль проброшенный через KDF (с конфигурацией, например +2^20 вычислений). Если энтропия пароля 40-бит, то даже когда он будет проброшен через KDF, энтропия результата также будет 40-бит, но вычислительная сложность станет уже 60-бит. Энтропия - это фактически начальные условия в отрыве от какого-либо алгоритма. В вашем случае энтропией выступает timestamp, но вы решаете вычислять энтропию от результата алгоритма (который был произведён от метки времени). В этом и суть, что предоставленная вами энтропия - она ложная при любом сценарии, будь то практическом или теоретическом.
Минус такого подхода - синхронизация почти невозможна, потому что запустить два компьютера и получить один и тот же результат не получится, выход всегда разный.
Точно также, как если бы мы просто запустили rand(time.Now().UnixNano()) на двух машинах - т.к., мы физическим не сможем запустить их синхронно, даже если будем использовать для этого какие-нибудь автоматизированные скрипты или программы.
И да, а вы не задумывались, что было бы если бы такой генератор построить на сверхточных часах?
Мы бы потратили много денег на аренду сверхточных часов только для того, чтобы протестировать небезопасный ГПСЧ. К тому же, если мы говорим про ГСЧ построенные на хаосе, то скорее всего результат был бы вообще противоположным - тобишь генератор стал бы ещё хуже рандомить числа.
Да, вы правы. Но посмотрите внимательнее, как работает механизм.
Т5/Т6 - срезы от 1000 до 10000 и выбор конкретного среза зависит от стейт, но момент времени - нет
Т11/т12 - случайные вставки нулевого байта и паузы ( с разбросом 1-100 ) тактов не хранятся в state и не могут быть восстановлены.
Т8/т9 - нелинейная зависимость, которая зависит от последнего байта строки - тоже не может быть восстановлена. В худшем случае, где нападающий знает все о времени и state, он не знает были ли паузы ( и сколько они длились ) и нулевые байты.
Состояние для паузы ( извините, тут воспользовался подсказкой ) - 100^(n-1), где n = 32 (32 байта ключа), то есть 100^31 ≈ 10^62 ≈ 2^206 — это для пауз между 32 байтами (31 промежуток).
Таким образом state это только первый шаг. Без асинхронных слоев он не дает взлома.
Я пересчитал через Qwen, теоретическая стойкость, как я указал выше, но практическая 2^80 - 2 ^100. Не могу проверить эти результаты, у меня изначально другие были, но имеет место быть. Если интересно, то могу скинуть, как это рассчитывалось, спасибо за критику
Если у него энтропия 7.1 бит на байт, то статистические тесты он провалит. Для повышения качества можно накопить избыток бит и пропустить через какую-то криптографическую хеш-функцию. Ещё есть риск того, что под разными операционными системами все эти таймеры могут работать с разной точностью.
Спасибо за комментарий. Идея была в том, чтобы использовать время, как источник энтропии, поэтому сам факт того, что мы можем достичь 7.1 бита на байт уже неплохо, с учетом того, что никаких дополнительных библиотек не используется. Никто не запрещает добавить еще таймеров поверх и добиваться полноценных 8 бит.
Касательно разных ОС - я не тестировал, но да, вероятно будет работать по-разному, но качество "шума" должно больше зависеть от железа, чем от ОС.
Эксперимент: ГПСЧ на таймерах с помощью PHP