«

»

Led 11

„Je libo náhodička?“

Štruktúra súborového systému v Linuxe obsahuje niekoľko adresárov. A jeden z nich je aj /dev, ktorý obsahuje súbory zariadení ako je napríklad USB či DVD mechanika. Pomocou príkazu ls -l /dev si môžete pozrieť výpis všetkých zariadení… blokových (s označením b) a znakových (s označením c). V tomto prípade nás budú zaujímať dve pseudozariadenia generujúce náhodné dáta (obe sú znakové):

  • /dev/random
  • /dev/urandom

 

/dev/random

V unixových systémoch ide o špeciálne súborové zariadenie implementované priamo do jadra. V podstate je rozhraním API pre výstup generátoru pseudonáhodných čísel. Umožňuje prístup ku nahromadenej entropii. V prípade, že jej je nedostatok, zariadenie šifrovanie zablokuje a čaká, pokiaľ sa opäť nazhromaždí a volajúci program dovtedy nepokračuje. Generátor sa pokúša udržať odhad entropie. A z tejto zásoby sú vytvárané náhodné čísla. Pri čítaní vracia iba náhodné bajty.

Blokovanie, na jednej strane vytvára veľmi kvalitný mechanizmus pre tvorbu kryptografických kľúčov. No na druhej strane spôsobuje jeho nesmiernu pomalosť.

Nevýhodou tohto zariadenia je fakt, že po vyprázdnení a postupnom zapĺňaní môžeme sledovať jeho postup. Čiže sa dá presne zistiť v akých intervaloch boli udalosti zapísané. Síce sa nedá presne určiť o aké konkrétne informácie ide, ale dajú sa rozlíšiť situácie ako je stisk klávesy, a to vďaka špecifickému vzorcu:

stisk klávesy (jeden až dva bajty)

trvanie stisku klávesy 50 až 150 ms

uvoľnenie klávesy (jeden až dva bajty)

oneskorenie 50 ms a viac

aktivita diskových zariadení sa prejavuje ako zhluky udalostí s oneskorením 1ms

Keďže aktivita spojená s diskovými zariadeniami je pomerne zriedkavá, pri odhade sa stačí sústrediť iba na klávesy. Na ich meranie netreba žiadne privilégiá.

 

slovo „evil“ („v“ stisknutá ľavou rukou je uvoľnená až po stlačení „i“ pravou rukou)

klávesa: akcia: oneskorenie:

e stisk |

e uvoľnenie | =========

v stisk | ===============

i stisk | ====

v uvoľnenie | ==

i uvoľnenie | ====

l stisk | =======

l uvoľnenie | ============

 

slovo „good“ (podobná situácia pri písaní druhého „o“)

klávesa: akcia: oneskorenie:

g stisk |

g uvoľnenie | ========

o stisk | ====

o uvoľnenie | =====

o stisk | =======

d stisk | =========

o uvoľnenie | =======

d uvoľnenie | ==============

Jednoduchým riešením tohto problému by bolo pridanie nadbytočných oneskorení, než zariadenie /dev/random poskytne ďalšie dáta pre čítanie po tom, čo algoritmus na vstup obdrží ďalšie vstupné dáta. Keďže pri čítaní z /dev/random dochádza ku prirodzeným oneskoreniam, tak by to nevadilo.

Čo sa týka zápisu, je možný, ale nezvykne sa používať. Nakombinovať náhodné dáta je umožnené akémukoľvek používateľovi. Nenáhodné čísla sú v podstate neškodné, pretože len root môže vydať ioctl potrebný pre zvýšenie odhadu entropie. Aktuálna veľkosť entropie a veľkosť zásoby entropie linuxového jadra sú k dispozícii v /proc/sys/kernel/random/.

 

Vypísanie množstva dostupnej entropie v bitoch:

cat /proc/sys/kernel/random/entropy_avail

Vypísanie náhodných znakov, pokiaľ nedôjde entropia:

xxd /dev/random

Linuxové jadro podporuje niekoľko hardwarových generátorov náhodných čísel. Neupravený výkon z takéhoto zariadenia môže byť získaný z /dev/hwrng.
Napríklad u FreeBSD, narozdiel od Linuxu, zariadenie /dev/random neblokuje. A s /dev/urandom sú zlúčené. Na šifrovanie používa 256 bitovú variantu Yarrowho algoritmu.

 

/dev/urandom

Je protipól pre /dev/random. Líši sa tým, že pseudonáhodné dáta produkuje aj napriek nedostatku entropie. Preto je rýchlejší, no miestami menej bezpečný. Teoreticky je možné, že pri minimálnej entropii, sa dá šifrovanie ľahko prelomiť.

 

Článok, ktorý rozoberá mýty o /dev/urandom.

Reakcia na predchádzajúci článok.

 

entropia

Je jedným zo základných fyzikálnych pojmov, pojmov v pravdepodobnosti, informatike, matematike a v iných teoretických či aplikovaných vedách. Často sa definuje ako veličina udávajúca mieru neurčitosti systému. Môžte si to predstaviť ako informácie. Čím viac informácii, tým nižšia entropia. No informáciu treba chápať nielen ako obyčajnú správu, ktorú si predávame, lež ako správu s obsahom. Pretože ten obsah je dôležitý.

Informačná entropia veľmi úzko súvisí s termodynamickou entropiou. Tiež sa nazýva aj Shannonova entropia. Je definovaná ako stredná hodnota jedného kódového znaku. Miera entropie súvisí s problematikou generovania náhodných respektíve pseudonáhodných čísel, pretože sekvencia úplne náhodných čísel by mala mať maximálnu mieru entropie. Taktiež tvorí limit pri bezstratovej kompresii dát. Čo znamená, že komprimované dáta sa nedajú zhustiť viac ako dovoľuje ich entropia.

Unixové systémy poskytujú bezpečný zdroj entropie, ktorý je udržiavaný samotnou aktivitou na PC (stisky kláves, začiatok a ukončenie procesov, pohyby myšou, kliky myšou, spúšťanie a zatváranie programov… a mnoho ďalších). Tie informácie sú následne prehnané hašovacou funkciou, ktorou sú algoritmy MD5 alebo SHA1. Výsledok sa použije na generovanie náhodných dát potrebných na vytvorenie šifrovacích kľúčov.

 

pseudonáhodné čísla

Sú čísla vygenerované generátorom náhodných čísel. Keďže nejde o skutočné náhodné čísla, ale len čísla generované deterministickým algoritmom, preto je dôležitý použitý algoritmus.

 

deterministický algoritmus

Je algoritmus, ktorý za rovnakých vstupných podmienok vytvára rovnaké výstupné dáta. Čiže za „vhodných“ okolností je predvídateľný. Všetky kroky sú presne definované. Oficiálne sa definuje ako algoritmus slúžiaci na výpočet matematických funkcií s presne stanovenými hodnotami výstupu pre jednotlivé vstupy. Príkladom deterministického stroja je Turingov stroj.

Za určitých okolností sa môže deterministický algoritmus chovať nedeterministicky. Napríklad v prípade, že sa viac procesov zapisuje do jednej premennej (dôležité je poradie v akom sa procesy zapíšu) alebo pri zacyklení algoritmu.

Opakom je nedeterministický algoritmus.

 

generátor pseudonáhodných čísel (PRNG)

Je fiktívny deterministický program, ktorý generuje pseudonáhodné dáta. V najlepšom prípade nerozlíšiteľných od tých náhodných. Vstupné dáta za určitých okolností môžu byť náhodné. No vďaka postupnosti zvanej random seed, ktorá určuje ďalší priebeh generátoru a vďaka ktorému je možné rozpoznanie použitého algoritmu. Preto sú postupnosti v podstate periodické. Ale tá periodicita môže byť veľmi dlhá a prakticky nedekovateľná. Štandardizované generátory obsahujú tzv. zadné vrátka v podobe univerzálneho kľúča.

Napríklad šum vytváraný hardvérom produkuje skutočne náhodné dáta.

V súčasnej dobe sa začína experimentálne používať aj CPRNG (crypto pseudo-random-number-generator). Na šifrovanie používa jednotku o veľkosti 1MB vykazujúcu entropiu 7.999837 bitov na 1 bajt. Pre porovnanie, urandom pre jednotku rovnakej veľkosti vykáže entropiu o veľkosti 7.999831 bitov na 1 bajt.

 

hardwarový generátor pseudonáhodných čísel (TRNG)

Je zariadenie pripojené k počítaču, ktoré je schopné generovať náhodné čísla z fyzikálnych javov. Tieto zariadenia sú založené na zaznamenávaní mikroskopických javov v podobe akéhosi šumu (teplo, fotoelektrické javy, šum vytváraný v elektronických obvodoch). Teoreticky sú úplne nepredvídateľné.

 

ioctl (input/output control)

Systémové volanie pre vstupné/výstupné operácie pre zariadenia či ďalšie operácie. Dá sa ním predať ľubovoľný príkaz s akýmkoľvek parametrom.
API (Application Programming Interface)

Je rozhranie pre programovanie aplikácií. Ide o zbierku tried, procedúr, protokolov a funkcií knižnice, jadra OS či iného programu. Definuje rozhranie medzi zdrojovým kódom a knižnicami. Určuje, akým spôsobom sú knižnice zo zdrojového kódu vyvolávané.

Poznáme napríklad grafické API (DirectX, OpenGL), API OS (POSIX pre unix a Win32) a webové API (http).

Poznáme aj ABI (Application Binary Interface). To je nízkoúrovňové rozhranie, ktoré je používané na úrovni zdrojového kódu. Patrí sem napríklad prekladač GCC (GNU Compiler Collection).

O autorovi

lombardo1981

Ja som proste ja. Baba zamilovaná do Archu, kyberpunku, metalu, spevu a Slovenských čuvačov.

1 ping

  1. Pozor! Čierna diera! »
    WordPress 4.7

    […] « „Je libo náhodička?“ […]

Napsat komentář

%d blogerům se to líbí: