Збільшуємо випадковість того, що і так [напевно] [майже] випадково


випадкові числа смачніше, якщо їх трошки поперчити

Будемо поєднувати теорію з практикою — покажемо, що поліпшення ентропії випадкових послідовностей можливе, після чого подивимося вихідні коди, які це роблять.

Дуже хотілося написати про те, що якісна, тобто високоентропійна, генерація випадкових чисел критично важлива при вирішенні величезного числа завдань, але це, напевно, зайве. Сподіваюся, всім це і так прекрасно відомо.

У гонитві за якісними випадковими числами люди винаходять вельми дотепні пристосування. В принципі, досить непогані джерела випадковості вбудовані в API операційних систем, але справа серйозна, і нас завжди трошки гризе черв’ячок сумніву: а чи достатньо хороший той ГВЧ, який я використовую, і не зіпсований він… скажімо так, третіми особами?

Трошки теорії

Для початку покажемо, що при правильному підході якість наявного ГВЧ неможливо погіршити. Найпростіший правильний підхід — це накладення на основну послідовність будь-якого іншого через операцію XOR. Основною послідовністю може бути, наприклад, системний ГВЧ, який ми вже вважаємо непоганим, але деякі сумніви все ж є, і у нас виникло бажання підстрахуватися. Додаткової послідовністю може бути, наприклад, генератор псевдовипадкових чисел, видача якого виглядає непогано, але ми знаємо, що його реальна ентропія досить невисока. Результуючої послідовністю будемо називати результат застосування операції XOR до бітів основної і додаткової послідовностей. Суттєвий нюанс: основна і додаткова послідовності повинні бути незалежними одна від одної. Тобто їх ентропія повинна братися з принципово різних джерел, взаємозалежність яких неможливо обчислити.

Позначимо як x черговий біт основної послідовності, а y — відповідний йому біт додаткової. Біт результуючої послідовності позначимо як r:
r = x⊕y

Перша спроба довести. Спробуємо пройти через інформаційну ентропію x, y і r. Ймовірність нульового x позначимо як px0, а ймовірність нульового y як py0. Інформаційні ентропії x і y вважаємо за формулою Шеннона:

Hx = − (px0 log2px0 + (1−px0) log2(1−px0))
Hy = − (py0 log2py0 + (1−py0) log2(1−py0))

Нуль в результуючій послідовності з’являється тоді, коли на вході два нуля або дві одиниці. Ймовірність нульового r:

pr0 = px0 py0 + (1−px0) (1−py0)
Hr = − (pr0 log2pr0 + (1−pr0) log2(1−pr0))

Для того, щоб довести непогіршення основної послідовності, потрібно довести, що
Hr − Hx ≥ 0 для будь-яких значень px0 і py0. Аналітично це довести у мене не вийшло, але візуалізований розрахунок показує, що приріст ентропії утворює гладку поверхню, яка не збирається йти в мінус:


Наприклад, якщо до перекошеного основним сигналом c px0=0.3 (ентропія 0.881) додаємо сильно перекошений додатковий з py0=0.1, отримуємо результат pr0=0.66 з ентропією 0,925.

Отже, ентропію неможливо зіпсувати, але це поки не точно. Тому потрібна друга спроба. Втім, через ентропію теж можна провести доказ. Схема (всі кроки досить прості, самі можете зробити):

  1. Доводимо, що ентропія має максимум в точці p0=1/2.
  2. Доводимо, що при будь-яких px0 і py0 значення pr0 не може бути далі від 1/2, ніж px0.

Друга спроба довести. Через здатність вгадувати. Припустимо, зловмисник апріорно має деяку інформацію про основну і додаткові послідовності. Володіння інформацією виражається в здатності з деякою ймовірністю заздалегідь вгадувати значення x, y і, як наслідок, r. Ймовірність вгадати x і y позначимо відповідно як gx і gy (від слова guess). Біт результуючої послідовності вгадується або тоді, коли обидва значення вірно вгадані, або тоді, коли обидва невірно, тому ймовірність вгадування виходить така:
gr = gx gy + (1−gx) (1−gy) = 2 gx gy − gx − gy + 1

Читайте також  Нова уразливість Mikrotik? Немає, але варто перевірити свої пристрої

Коли у нас є ідеальний вгадувач, маємо g=1. Якщо нам нічого невідомо, g один… ні, не нулю, а 1/2. Саме така ймовірність вгадування виходить, якщо ми будемо приймати рішення підкиданням монетки. Вельми цікавий випадок, коли g<1/2. З одного боку, такий вгадувач десь всередині себе володіє даними про вгадувану величину, але чогось інвертує свою видачу, і таким чином стає гірше монетки. Запам’ятайте, будь ласка, словосполучення «гірше монетки», воно нам нижче згодиться. З точки зору математичної теорії зв’язку (і, як наслідок, звичної нам кількісної теорії інформації) ця ситуація абсурдна, оскільки це вже буде не теорія інформації, теорія дезінформації, але за життя таке положення справ маємо істотно частіше, ніж того нам хотілося б.

Розглянемо граничні випадки:

  • gx = 1, тобто послідовність x повністю передбачувана:
    gr = gx gy + (1−gx) (1−gy) = 1 gy + (1-1) (1−gy) = gy
    Тобто ймовірність вгадування результату дорівнює ймовірності вгадування додаткової послідовності.
  • gy = 1: Аналогічно попередньому. Ймовірність вгадування результату дорівнює ймовірності вгадування основної послідовності.
  • gx = 1/2, тобто послідовність x повністю непередбачувана:
    gr = 2 gx gy − gx − gy + 1 = 2/2 gy − 1/2 − gy +1 = gy − gy + 1/2 = 1/2
    Тобто додавання будь-якої додаткової послідовності не погіршує повну непередбачуваність основний.
  • gy = 1/2: Аналогічно попередньому. Додавання повністю непередбачуваною додаткової послідовності робить результат повністю непередбачуваним.

Для того, щоб довести, що додавання додаткової послідовності до основної нічим не допоможе зловмиснику, нам потрібно з’ясувати, за яких умов gr може бути більше gx, тобто

2 gx gy − gx − gy + 1 > gx

Переносимо gx з правої частини в ліву, а gy і 1 в праву:

2 gx gy − gx − gx > gy − 1
2 gx gy − 2 gx > gy − 1
Виносимо в лівій частині 2gx за дужки:
2 gx (gy − 1) > gy − 1
Оскільки у нас gy менше одиниці (граничний випадок, коли gy=1, ми вже розглянули), то перетворимо gy−1 у 1−gy, не забувши поміняти «більше» та «менше»:
2 gx (1 − gy) < 1 − gy

Скорочуємо «1−gy» і отримуємо умову, при якому додавання додаткової послідовності поліпшить зловмиснику ситуацію з вгадуванням:

2 gx < 1
gx < 1/2

Тобто gr може бути більше gx тільки тоді, коли вгадування основної послідовності гірше монетки. Тоді, коли наш провісник зайнятий свідомим саботажем.

Кілька додаткових міркувань про ентропію.

  1. Ентропія — на рідкість міфологізоване поняття. Інформаційна — в тому числі. Це дуже заважає. Часто інформаційна ентропія представляється як якась тонка матерія, яка об’єктивно присутня в даних або ні. Насправді інформаційна ентропія — це не те, що присутнє в самому сигналі, а кількісна оцінка апріорної обізнаності одержувача повідомлення щодо самого повідомлення. Тобто це не тільки про сигнал, але і про одержувача. Якщо одержувач заздалегідь про сигнал зовсім нічого не знає, інформаційна ентропія переданої двійкової одиниці строго дорівнює 1 біт незалежно від того, як був отриманий сигнал і що він собою представляє.
  2. У нас є теорема про складання ентропій, згідно з якою сумарна ентропія незалежних джерел дорівнює сумі ентропій цих джерел. Якщо б ми поєднували основну послідовність з додатковою через конкатенацію, ми б зберегли ентропії джерел, але отримали б поганий результат, тому що в нашій задачі потрібно оцінювати не сумарну ентропію, а питому, в перерахунку на окремий біт. Конкатенація джерел дає нам питому ентропію результату, що дорівнює середньому арифметичному ентропій джерел, і ентропійно слабка додаткова послідовність природним чином погіршує результат. Застосування операції XOR призводить до того, що частина ентропії ми втрачаємо, але гарантовано маємо результуючу ентропію не гірше максимальної ентропії доданків.
  3. У криптографів є догма: використання генераторів псевдовипадкових чисел — непрощенна самовпевненість. Тому що у цих генераторів маленька питома ентропія. Але ми тільки що з’ясували, що якщо зробити все правильно, ентропія стає бочкою меду, яку неможливо зіпсувати ніякою кількістю дьогтю.
  4. Якщо у нас є всього 10 байт реальної ентропії, розмазаних по кілобайту даних, з формальної точки зору маємо лише 1% питомої ентропії, що дуже погано. Але якщо ці 10 байт розмазані якісно, і крім брутфорса немає ніякого способу ці 10 байт обчислити, все виглядає не так вже погано. 10 байт — це 280, і якщо наш брутфорс в секунду перебирає трильйон варіантів, нам на те, щоб навчитися вгадувати черговий знак, знадобиться в середньому 19 тисяч років.
Читайте також  SandboxEscaper/PoC-LPE: що всередині?

Як було сказано вище, інформаційна ентропія — величина відносна. Там, де для одного суб’єкта питома ентропія дорівнює 1, для іншого вона цілком може бути 0. Притому той, у кого 1, може не мати ніякої можливості дізнатися про справжній стан справ. Системний ГВЧ видає потік, невідмітний для нас по-справжньому випадково, але на те, що він дійсно випадковий для всіх, ми можемо тільки сподіватися. І вірити. Якщо параноя підказує, що якість основного ГВЧ може раптом виявитися незадовільною, є сенс підстрахуватися за допомогою додаткового.

Реалізація підсумкового ГВЧ на Пітоні

 

from random import Random, SystemRandom
from import random BPF as _BPF, RECIP_BPF as _RECIP_BPF
from functools import reduce as _reduce
from operator import xor as _xor

class CompoundRandom(SystemRandom):
 def __new__(cls, *sources):
 """Positional arguments must be descendants of Random"""
 if not all(isinstance(src, Random) for src sources in):
 raise TypeError("all the sources must be descendants of Random")
 return super().__new__(cls)

 def __init__(self, *sources):
 """Positional arguments must be descendants of Random"""
 self.sources = sources
super().__init__()

 def getrandbits(self, k):
 """getrandbits(k) -> x. Generates an int with k random bits."""
 ######## Насправді все це заради ось цієї рядки:
 return _reduce(_xor, (src.getrandbits(k) for src in self.sources), 0)

 def random(self):
 """Get the next random number in the range [0.0, 1.0)."""
 ######## Не зрозуміло, чому в SystemRandom так не зроблено. Ну гаразд...
 return self.getrandbits(_BPF) * _RECIP_BPF

Приклад використання:

>>> import random_xe # <<< Так воно називається
>>> from random import Random, SystemRandom
>>> # Створюємо об'єкт:
>>> myrandom1 = random_xe.CompoundRandom(SystemRandom(), Random())
>>> # Використовуємо як звичайний Random:
>>> myrandom1.random()
0.4092251189581082
>>> myrandom1.randint(100, 200)
186
>>> myrandom1.гаус(20, 10)
19.106991205743107

В якості основного потоку взято  той, який вважається правильним SystemRandom, а в якості додаткового – стандартний ДПРЧ Random. Сенсу в цьому, звичайно, не дуже багато. Стандартний ДПРЧ – точно не та добавка, заради якої все це варто було затівати. Можна замість цього скласти між собою два системних ГВЧ:

>>> myrandom2 = random_xe.CompoundRandom(SystemRandom(), SystemRandom())

Сенсу, правда в цьому ще менше (хоча саме такий прийом чомусь рекомендує Брюс Шнайер в «Прикладної криптографії»), тому що наведені вище викладки справедливі тільки для незалежних джерел. Якщо системний ГВЧ скомпрометований, результат також вийде скомпрометованим. В принципі, політ фантазії у справі пошуку джерела додаткової ентропії нічим не обмежений (в нашому світі безлад зустрічається набагато частіше, ніж порядок), але в якості простого рішення запропоную ДПРЧ HashRandom, також реалізований в бібліотеці «random_xe».

Читайте також  Бізнес просить право на персональні дані користувачів

ДПРЧ на основі потокового циклічного хешування

В найпростішому випадку можна взяти деяку відносно невелику кількість початкових даних (наприклад, попросити користувача побарабанить по клавіатурі), обчислити їх хеш, а потім циклічно доливати хеш на вхід алгоритму хешування і брати наступні хеши. Схематично це можна зобразити так:

Криптостійкість цього процесу грунтується на двох припущеннях:

  1. Завдання відновлення вихідних даних за значенням хеш нестерпно складне.
  2. За значенням хеш неможливо відновити внутрішній стан хеширующого алгоритму.

Порадившись з внутрішнім параноїком, визнав друге припущення зайвим, і тому в чистовій реалізації ДПРЧ схема трошки ускладнена:

Тепер якщо зловмисникові вдалося отримати значення Хеш 1r», він не зможе обчислити наступні за ним значення Хеш 2r», так як у нього немає значення Хеш 2h», яке він не зможе дізнатися, не визначивши функцію хешування «проти шерсті». Таким чином, криптостійкість цієї схеми відповідає криптостійкості застосовуваного хешуючого алгоритму.

Приклад використання:

>>> # Створюємо об'єкт, проинициализировав HashRandom найкращим у світі паролем '123':
>>> myrandom3 = random_xe.CompoundRandom(SystemRandom(), random_xe.HashRandom('123'))
>>> # Використовуємо як звичайний Random:
>>> myrandom3.random()
0.8257149881148604

За замовчуванням використовується алгоритм SHA-256. Якщо хочеться чогось іншого, можна конструктор другим параметром передати бажаний тип алгоритму хешування. Для прикладу зробимо складовою ГВЧ, підсумовуючий в купу наступне:

1. Системний ГВЧ (це святе).
2. Користувальницький введення, оброблюваний алгоритмом SHA3-512.
3. Час, витрачений на цей enter, оброблюваний SHA-256.

>>> from getpass import getpass
>>> import from time perf_counter
>>> from hashlib import sha3_512
# Оформимо у вигляді функції:
>>> def super_myrandom():
 t_start = perf_counter()
 return random_xe.CompoundRandom(SystemRandom(),
random_xe.HashRandom(
 getpass('Побарабаньте по клавіатурі:'), sha3_512),
 random_xe.HashRandom(perf_counter() - t_start))
>>> myrandom4 = super_myrandom()
Побарабаньте по клавіатурі:
>>> myrandom4.random()
0.35381173716740766

Висновки:

  1. Якщо ми не впевнені в своєму генераторі випадкових чисел, ми можемо легко і приголомшливо дешево вирішити цю проблему.
  2. Вирішуючи цю проблему, зробити гірше ми не зможемо. Тільки краще. І це математично доведено.
  3. Потрібно не забути постаратися зробити так, щоб використані джерела ентропії були незалежними.

 

Степан Лютий

Обожнюю технології в сучасному світі. Хоча частенько і замислююся над тим, як далеко вони нас заведуть. Не те, щоб я прям і знаюся на ядрах, пікселях, коллайдерах і інших парсеках. Просто приходжу в захват від того, що може в творчому пориві вигадати людський розум.

You may also like...

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *