Hash-rodné číslo

To je asi schvålně, abyste přemýšleli a testovali jen možná rodnå čísla. Mrkněte na wikipedii a přečtěte si o rodných číslech.

Udělej si nějakou představu o tom, co jde upočítat a co už ne. Spočítání hashe bude určitě aspoň 100 instrukcí (sečtení, porovnání, …), spíš víc. V cyklu počítáš 10^9 hashů, tedy potřebuješ vykonat 10^11 instrukcí. Procesor má frekvenci v GHz, tedy miliardy instrukcí za vteřinu. Skript bude tedy trvat aspoň 100 s, web server ho nejspíš zařízne. Dopouštím se spousty zjednodušení, klidně jsem se mohl seknout o řád nebo dva. Závěr je ten, že se to takto nejspíš bude počítat několik minut nebo hodin.

Jiří Ráb:
Cyklus nemůže doběhnout. Hashovací funkce pomocí několika početních operací vytvoří z čísla kód, například 5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9. Výpočet kódu stojí počítač (server) pochopitelně nějaký výkon a hlavně čas. A ty po něm chceš, aby tuhle operaci provedl v cyklu až deset miliarda krát po sobě. Netuším, jak rychle počítač dokáže vypočítat a porovnat jeden hash, ale i kdyby to trvalo jedinou mikrosekundu, na výsledek se zadaným rodným číslem bys čekal přes dvě a půl hodiny. Nemluvě o tom, že existuje malá pravděpodobnost, že stejný hash má i více rozdílných vstupních proměnných, takže na správnost výsledku se nemůžeš 100% spolehnout.

Kajman:
Podle mě jde o názornou ukázku náročnosti prolomení hashe za pomocí brutal force. I s testováním validních rodných čísel se náročnost výpočtu sníží jen o řád až dva, k tomu se připočte ona validace.

Celý výpočet s převedením řetězce rodného čísla do čísla typu integer, tedy bez nul na začátku, je pochybný. Nedokáže rozlišit sedmašedesátiletého muže a dvanáctiletého kluka: 510101/306 vs. 051010/1306 – obě rodná čísla jsou validní a podle udaného výpočtu mají stejný hash.

Kajman, Trejpa:
Citát z českej wikipédie:
„Desetimístná rodná čísla (tzn. RČ od roku 1954) jsou beze zbytku dělitelná jedenácti, aby bylo možno snadno detekovat překlepy či jiné náhodné chyby. Poslední číslice tedy slouží jako kontrolní číslice, jde o zbytek (tzv. modulo) po celočíselném dělení devítimístného čísla jedenácti. Z tohoto pravidla existuje výjimka: pokud je zbytek po dělení devítimístného čísla roven deseti (a neexistuje tedy žádná kontrolní číslice, která by splňovala předchozí podmínku), jako kontrolní číslice se použije nula (a celé rodné číslo pak dělitelné jedenácti není).“

Čiže proces nejde jednoducho zjednodušiť inkrementáciou o 11.

Tomáš123:
Nechápu, co tím chceš říci. Psal snad Kajman nebo já o dělitelnosti nebo inkrementaci čísla jedenáct? Máš snad pocit, že někdo z nás nerozumí formátu českého rodného čísla?

Trejpa:
Skôr taká poznámka. Zaujímalo ma, či existuje aj viac validačných prvkov rodného čísla. A hoci som nenašiel nič konkrétnejšie, zaujala ma citovaná časť.

Tomáš123:
Spočítat zbytek po dělení jedenácti a ověřit, zda to není 0 nebo deset bude řádově rychlejší než spočítání hashe. Proto pokud nejdříve ověříš validitu a pak případně počítáš hash, tak můžeš ušetřit čas. V důsledku jde vždy jen o to, aby to ověření podmínky bylo rychlejší než výpočet funkce samotné.


Co se týče PHP a výpočtů hashů na procesoru, tak od toho se nedají čekat žádné zázraky. Stačí se podívat na dobu běhu obyčejného prázdného cyklu.
Samozřejmě záleží na procesoru a verzi PHP ale při milionu kroků cyklu jsem se dostal na jednotky setin vteřiny. Pro miliardu to je 10 - 30 vteřin. Pro tvých deset miliard to je minuta a půl až pět minut. A to je jenom čas, který zabere režije cyklu.

Nicméně pokud se hashe budou počítat na grafické kartě, tak u sha256 je reálné se dostat do řadu několika Ghash/s takže těch deset miliard kombinací se dá ověřit do deseti sekund.

Trejpa:
„stejný hash má i více rozdílných vstupních proměnných, takže na správnost výsledku se nemůžeš 100% spolehnout“
100% to není nikdy. Ovšem 10 miliard má přibližně 30 bitů informace. sha256 pracuje na prostoru 256 bitů. Takže i když šanci na kolizi nejde nikdy úplně vyloučit, pravděpodobnost takového jevu bude velmi malá.

TomášK:
„Spočítání hashe bude určitě aspoň 100 instrukcí (sečtení, porovnání, …)“
Mimo hlavní téma, ale...

Chceš říci, že spočítat hash znamená vykonat 100 instrukcí (= příkazů?)? To vážně? Neříkám, že ne, ale docela by mě to zajímalo. Dá se o tom někde dočíst více, co všechno se při počítání hashe děje? Děkuji.

Trejpa:
„I s testováním validních rodných čísel se náročnost výpočtu sníží jen o řád až dva, k tomu se připočte ona validace.“
Ono je v praxi pro toto efektivnější rovnou vytvářet validní čísla, protože s těch 10 miliard bude teoreticky validních necelých 107 miliónů rodných čísel a minimálně 1/4 z nich ještě ani nebyla přidělena.

Reálně mi spočítání 107 milionů hashů sha256 na 10 let starém notebooku s CPU @2 GHz v PHP 5.6 trvá asi 4,5 minuty. (Zjednodušený algoritmus pro 12 měsíců po 31 dnech a roky 1900-2053.)

Jiří Ráb:
„nevím proč vždy to skončí s hláškou že byl překročen časový limit“
Většinou je na webovém serveru omezena doba běhu PHP skriptu na 30 vteřin jako ochrana proti zacyklení. Dá se to prodloužit v konfiguraci PHP nastavením max_execution_time nebo funkcí set_time_limit(). Nicméně pro tento případ by asi bylo lepší nainstalovat si PHP na počítač a skripty spouštět pomocí programu php.exe.

Tomášeek:
„Chceš říci, že spočítat hash znamená vykonat 100 instrukcí (= příkazů?)? To vážně? Neříkám, že ne, ale docela by mě to zajímalo.“
To číslo nemusí být daleko od pravdy, Wiki uvádí nějakých 80 cyklů na Skylake procesoru při počítání SHA256 z jednoho bajtového oktetu. Šlo by to pravděpodobně i mnohem rychleji, moderní procesory mají pro výpočty hashů dedikované instrukce, což ale nevím, jestli v implementaci PHP hraje nějakou roli – řekl bych že ne.

Myslím, že logika toho útoku by šla hodně optimalizovat zúžením té testovací množiny, jak už tady padlo. Prvních 6 cifer rodného čísla vyjadřuje den narození, má tedy smysl přeskakovat neexistující měsíce i dny a nepočítat čísla z budoucnosti a minulosti před samotným vznikem rodných čísel. Pro poslední číslici je určitě rychlejší spočítat modulo 11 než zkoušet zbytečně 9 nevalidních pokusů.

M4n:
„nepočítat čísla z budoucnosti a minulosti před samotným vznikem rodných čísel“
Špatná úvaha. Moje babička se narodila před vznikem rodných čísel a přesto rodné číslo má. Stejně tak je nelogické omezovat budoucí čísla.

„má tedy smysl přeskakovat neexistující měsíce i dny“
Ano. Pozice měsíce v RČ má jen 48 kombinací ze sta a dnů 31 kombinací ze sta. Šlo by jít ještě dál a omezit i dny v měsících, které nemají 31 dnů.

Otázkou zůstává, zda se jako vstupní údaj mohlo dostat i nevalidní rodné číslo, a zda je žádoucí najít hash i pro takovou variantu.

Výpočet ověření hashe samozřejmě nemusí začínat od nuly. Pakliže je důvodné očekávat vyšší číslo, je možné cyklus začít provádět dekrementací nebo třeba začít od poloviny rozsahu a druhou polovinu nechat na konec cyklu.

Trejpa:
„Stejně tak je nelogické omezovat budoucí čísla.“
Připadá ti logické počítat hashe lidí, kteří se ještě nenarodili?

Trejpa:
„I s testováním validních rodných čísel se náročnost výpočtu sníží jen o řád až dva, k tomu se připočte ona validace.“

Podle mě ten rozdíl bude větší.
- Výše zmíněná dělitelnost 11 sníží počet platných hodnot zhruba o řád.
- 3.-6. pozice jsou měsíc a den narození, u žen se k první číslici přičte 5; Tedy existuje jen 366 (dní v roce) * 2 (muži/ženy) = 712 platných hodnot z 10 000.
Přitom tady není potřeba validace, dají se rovnou generovat jen platné hodnoty, v extrémním případě šetření výkonem přímo definovat pole platných hodnot.

Čili rozdíl je větší než dva řády.

Jinak ta úplně nejtriviálnější optimalizace by byla místo od 0 začít od "000101000", což je asi nejnižší platné rodné číslo. Ušetří se tím 101 000 cyklů.

Ale na druhé straně upozorním, že je teoreticky potřeba kontrolovat dva formáty rodných čísel: 9-místné a 10-místné (s kontrolní číslicí).
Nejspíš by to šlo řešit dvěma kontrolami v každém cyklu:
1. Sestavit 9-místné RČ a zkontrolovat
2. Dopočítat kontrolní číslici a zkontrolovat 10-místné RČ.


Jiří Ráb:
Ještě jedna věc, která tu zatím nezazněla:
To, že běh trvá dlouho, je sice nepříjemnost, ale není to hlavní problém kódu v [#1].
Ten kód totiž nefunguje správně.
Jednak to, že to kontroluje spoustu neplatných hodnot, vede k nesmyslným výsledkům, např. pro $hash="5FECEB66FFC86F38D952786C6D696C79C2DBC239DD4E91B46729D73A27FB57E9" to najde rodné číslo 0.
Ale 0 přece není rodné číslo.

Dál to vůbec neověří rodná čísla začínající 0. Například výše zmíněné "000101000"; Sice cyklus projde číslem 101 000, jenže hash "101000" se liší od hashe "000101000".

První chyba v návrhu programu je pro rodné číslo použít číselný formát.
Některé hodnoty sice mají v názvu „číslo“, například rodné číslo nebo telefonní číslo, ale z programátorského pohledu to jsou řetězce.

M4n:
„Připadá ti logické počítat hashe lidí, kteří se ještě nenarodili?“
Ano, ale záleží na vstupních podmínkách.

Joker:
„3.-6. pozice jsou měsíc a den narození, u žen se k první číslici přičte 5;“
Špatný předpoklad. U mužů se přičte 0 nebo 2, u žen 5 nebo 7 (wiki).

Trejpa:
Proto jsem psal u standardního rodného čísla.
To dodatečné navýšení 3. číslice o 2 je alternativní rodné číslo pro případ, že se nějaký den vyčerpají standardní rodná čísla.

Tipoval bych, že reálně nikdo alternativní RČ nemá¹, takže se to asi dá zanedbat.

M4n:
„Připadá ti logické počítat hashe lidí, kteří se ještě nenarodili?“

Záleží na formulaci zadání.
Pokud se má ověřovat jen jestli hash odpovídá platnému rodnému číslu, je správně ověřovat i budoucí.
Pokud by se mělo ověřovat jen existující rodné číslo, dokonalá optimalizace by byla to ověřovat podle seznamu reálně přidělených rodných čísel.

¹ Bylo to zavedeno až v roce 2004 pro případ vyčerpání všech standardních rodných čísel. Každý den je k dispozici 2x 999 (pro muže a pro ženy) rodných čísel a dětí se rodí v průměru okolo 300 denně.

Joker:
„Každý den je k dispozici 2x 999 rodných čísel“
Mno, to si nejsem až tak úplně jistý, ale problematiku rodných čísel jsem teď hluboce nestudoval.

Pokud mě paměť neklame, první dvojčíslí (nebo číslice?) za lomítkem určuje porodnici, kde se dítě narodilo. Nebo město/okres/kraj (fakt netuším, musel bych hledat)? Reálně je těch rodných čísel k dispozici méně a k vyčerpání kombinací pro danou lokalitu (porodnici/město/okres/kraj, viz výše) může dojít mnohem snáze.

Joker:
Jedna věc jsou čísla pro právě narozené, další pro cizince s pobytem nebo studiem v ČR, byť dočasným. I tito dostávají rodné číslo. Nenulová šance na současný výskyt takovéto varianty by měla být v programu zahrnuta.

„pro případ, že se nějaký den vyčerpají standardní rodná čísla“
Pokud to nastává nyní zřídka, po roce 2054 může dojít i k vyčerpání zmíněných alternativ, neboť nebude možné opakovaně použít čísla užitá po roce 1954. Pořád bude možno v rodném čísle například navýšit den o padesát nebo začít používat abecední znaky. Pokud však v té době bude české rodné číslo ještě někoho zajímat.

Tomášeek:
Jak jsem psal, nevím, jestli se alternativní rodná čísla reálně přidělují.
Nicméně by záleželo na zadání, jestli kontrolovat i alternativní RČ nebo ne.

Kromě toho některé instituce ve svých databázích cizincům přidělují jakési „pseudo-RČ“, které neodpovídá standardnímu formátu.

Trejpa:
Při rychlosti veřejné správy je možné všechno, ale nepočítá se s tím, že by se ještě v roce 2054 přidělovala současná rodná čísla.