V dôležitých krypto algoritmoch môžu byť zadné vrátka v samotných číslach, ukázali experti

Značky: kryptografiabezpečnosť

DSL.sk, 12.10.2016

Vo viacerých dôležitých dnes masovo používaných kryptografických algoritmoch sa môžu potenciálne nachádzať zadné vrátka umožňujúce osobám, ktoré ich tam prípadne dostali, tieto algoritmy prekonať.

Ukázal to tím expertov na kryptografiu z Pensylvánskej univerzity, Univerziy v Lorraine a francúzskych inštitútov INRIA a CNRS.

Parametre diskrétneho logaritmu

Dôležité kryptografické asymetrické algoritmy používané dnes na šifrovanie alebo podpisovanie sú založené na efektívnej neriešiteľnosti základných matematických problémov pri veľkých číslach, napríklad rozloženia čísla na súčin prvočísel alebo nájdenia tzv. diskrétneho logaritmu.

Kým u niektorých z týchto algoritmov, napríklad RSA, nemá samotný algoritmus žiadne číselné parametre a všetky používané čísla sú už individuálnymi kľúčami, pri algoritmoch postavených na diskrétnom logaritme, napríklad Diffie-Hellman a DSA, môžu byť súčasťou implementácie alebo dokonca štandardu aj konkrétne parametre v podobe okrem iného dlhého prvočísla p.

Modulo týmto prvočíslom sa realizujú príslušné celočíselné výpočty, nie je tajné a rovnaké prvočíslo môže byť používané množstvom inštalácií. Dôvodom pre používanie rovnakého čísla a negenerovanie iných hodnôt na každom zariadení je okrem iného skutočnosť, že na p a ďalšie parametre sú kladené ďalšie nároky pre zabezpečenie dostatočnej bezpečnosti a čísla je potrebné komplikovanejšie preveriť.

Lámanie diskrétneho logaritmu

Najefektívnejším verejne známym algoritmom na vyriešenie problému diskrétneho logaritmu a tým aj prelomenie kryptografických algoritmov na ňom postavených je algoritmus Number Field Sieve, NFS, vo verzii pre diskrétny logaritmus. Teoreticky je ho už v súčasnosti podľa vedcov možné použiť na prelomenie problému diskrétneho logaritmu s ľubovoľným 1024-bitovým prvočíslom, ale s nákladmi v rádoch stoviek miliónov dolárov na špecializovaný hardvér.

Už dávnejšie je známe, že NFS je výrazne efektívnejší pri prvočíslach špecifického tvaru. Doteraz sa podľa vedcov ale predpokladalo, že takéto prvočísla je možné ľahko identifikovať a pokusy prepašovať ich do implementácií a štandardov tak nemajú šancu uspieť.

Experti teraz dokázali vygenerovať 1024-bitové prvočíslo pre algoritmy založené na diskrétnom logaritme, ktoré má špeciálny tvar a zlomiť ho je možné pomocou NFS minimálne 10-tisíc krát ľahšie ako ľubovoľné rovnako dlhé prvočíslo. Expertom sa to konkrétne podarilo za dva mesiace výpočtov na menej ako tritisíc počítačových jadrách, následne boli schopní konkrétny logaritmus vypočítať a teda prelomiť napríklad konkrétnu komunikáciu za 80 minút s využitím cca päťsto jadier.

Hlavne ale podľa ich tvrdení u nimi vygenerovaného prvočísla nie je možné detekovať, že je špeciálneho tvaru umožňujúceho efektívne zlomenie pomocou NFS.

Možné zadné vrátka

Tým experti demonštrovali, že takejto špecifickej pripravenej povahy by mohli byť aj prvočíslá používané v dnes masovo rozšírených implementáciách a štandardoch DSA a Diffie-Hellman.

V súčasnosti sú známe riešenia, ako tomu zabrániť, preukázaním spôsobu generovania prvočísiel zvolených do štandardov a implementácií.

Otázka takýchto zadných vrátok vyvstala podľa vedcov už pred desaťročiami. Keďže problém sa nezdal byť vážny, u dnes používaných 1024-bitových prvočísel pre algoritmy založené na diskrétnom logaritme sa takéto dôkazy nevyžadovali a podľa expertov ich napríklad ani prvočísla definované ako vhodné v štandardoch IETF nemajú. Potenciálne tak môže ísť o prvočísla vytvorené takým spôsobom, že ich tvorcovia vedia a už dlhšiu dobu vedeli efektívne riešiť problém diskrétneho logaritmu s danými prvočíslami.

Experti v tejto súvislosti poukazujú na informácie vynesené Edwardom Snowdenom, podľa ktorých sa NSA snažila ovplyvniť kryptografické štandardy a špecifikácie za účelom dokázať ich prekonať. V tomto kontexte sa doteraz za takýto štandard považoval len príliš nepresadený algoritmus pre generovanie pseudonáhodných čísiel Dual_EC_DRBG, do ktorého sa zadné vrátka podarilo NSA dostať podľa novín The New York Times a ktorý bol ako štandard organizáciou NIST v 2014 stiahnutý.

Ochrana

Hoci používanie Diffie-Hellman a DSA s 1024 bitmi nie je už niekoľko rokov odporúčané, v praxi sa ešte bežne s takýmito parametrami tieto algoritmy využívajú.

Rovnaký principiálny problém sa týka aj dlhších prvočísiel, napríklad u 2048-bitových aj špeciálneho tvaru by algoritmus NFS ale nebol zatiaľ praktický. Odporúčaným riešením je tak prejsť minimálne na 2048 bitov.

Zároveň je odporúčané používať len prvočísla, u ktorých bude príslušným postupom preukázané ako boli vytvorené a teda že nie sú špeciálneho tvaru umožňujúceho jednoduchšie zlomenie algoritmov postavených na diskrétnom logaritme.




Najnovšie články:



Diskusia:

Re: \\\\\\\\\\\\\\\\\\ Od: Makovník | Pridané: 12.10.2016 16:31 Nerozumiem ani prd, ale autorovi článku dávam veľké plus, pretože tomu zjavne rozumie. Odpovedať Známka: 8.6 Hodnotiť:

Re: \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ Od: rolh | Pridané: 12.10.2016 17:38 Kto tomu nerozumnie, mal by vratit maturitu z matematiky, problemy diskretneho logaritmu u nas ucia uz na strednych skolach Odpovedať Známka: -8.2 Hodnotiť:

Ghfugfutfutvjhvjhv Od: zxcvbn | Pridané: 12.10.2016 19:00 Mas na mysli tie skoly z ktory vyliezaju individua neschopne pouzivat zlomky alebo trojclenku? Odpovedať Známka: 9.1 Hodnotiť:

hruza Od: mr.Proper | Pridané: 12.10.2016 21:18 Neurazaj ! Ano ? Vlastnim malu IT firmu a bez kalkulacky mam problem scitat dvojciferne cisla. Odpovedať Známka: 5.7 Hodnotiť:

Re: \"vylomitkovany riadok\" Od: Fako | Pridané: 12.10.2016 21:20 Precitaj si svoj prispevok po sebe znovu, aby si si uvedomil, ako si sa zhovadil... :-) Odpovedať Známka: 5.0 Hodnotiť:

Re: \\\\\\\\\\\\\\\\\\\\\\\\\\\\ Od: Dedo. | Pridané: 12.10.2016 22:11 Strednych? Si srandu robis? Diskretne logaritmy mna ucili v druhej triede nasej ludovej skoly v casoch ked sme este kazde rano chodili 38 kilometrov peso do skoly a po vyucovani 38 kilometrov domov ovce dojit, lebo autobusy neboli! A to bolo este poriadne vzdelanie, nie ako teraz vy mladi iba kalkulacky picoviny. A ked som cosi nevedeu spravne diskretne zlogaritmovat, tak ma este doma stary otec, nech mu je zem lahka, trstenicou vylatal. Ach ty stredna skola... Na strednu skolu ja ked som isou v padesiatom tretom, to sme vtedy prijimacky robili z kvantovej fyziky a specialnej teorie relativity, to nie ako vy mladi, co este len pride cas ked bude vam treba logritmuvat s posuvnym pravitkom a nebudes vediet. Odpovedať Známka: 9.1 Hodnotiť:

Re: \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ Od: sensei-san | Pridané: 12.10.2016 23:13 > sme este kazde rano chodili 38 kilometrov peso do skoly Tipujem, že to bolo v snehu. A hore kopcom. Oboma smermi. Odpovedať Známka: 9.5 Hodnotiť:

základné vzdelanie Od: syntaxterrorA | Pridané: 13.10.2016 7:59 Kto vie, či v zime ovce doja, hneď vie, kto pravdu píše i kto sa zaň iba vydáva. Odpovedať Známka: 3.3 Hodnotiť:

kluce Od: efg323 | Pridané: 12.10.2016 18:44 nechapem jedno - cicmeme sa tu stale s 1024 bitovymi klucmi a nadavame ze sa to tak ci onak da prelomit, a postupne, mozno, rokmi sa precicmeme k 2048 bitovym klucom, zas budeme nadavat ze sa to da prelomit a tak donekonecna - preco preboha rovno nezacneme pouzivat nejake 32768 bitove alebo 65536 bitove kluce, a bol by pokoj na niekolko rokov. Pride mi to ako keby niekto potreboval neustale nieco riesit, nejako sa zviditelnovat, a za to pochopitelne neustale brat peniaze - a pritom riesenie problemu je trivialne - radovo zvacsit velkost kluca a je vystarane na par rokov dopredu. Odpovedať Známka: 6.2 Hodnotiť:

zamky Od: syntaxterrorA | Pridané: 12.10.2016 19:16 Presne tak. Eventuálne by síce namiesto obligátneho navrhovania generickej exponenciálizácie na prelomenie algoritmu potrebného výkonu bolo možné použitie kryptografickými expertami neočakávaného čísla, napríklad -1, ale svet by bol ochudobnený o množstvo odborných postupov optimalizácií efektívnej riešiteľnosti základných matematických problémov. Odpovedať Známka: -2.9 Hodnotiť:

Re: kluce Od: knjiCdo | Pridané: 12.10.2016 20:23 Väčšie kľúče sa generujú dlhšie. už 2048 biť kľúč môže trvať niekoľko sekúnd, v závislosti od stroja. A samozrejme zaberajú viac miesta. Myslím, že kľúče, ktoré používame sa zväčšujú zároveň z výpočtovým výkonom aký máme. Odpovedať Známka: 8.7 Hodnotiť:

Re: kluce Od: :Pjetro de | Pridané: 12.10.2016 20:25 1A) To je sice na jednej strane pravda, na druhej strane si uvedom, ze 2048-bitove cislo je asi 10^300(1 a 300 nul)-nasobne vacsie ako 1024-bitove. Aj keby specialny tvar cisla zarucil, ze 98% hodnoty zvyseneho exponentu ide do stratenej prdele, stale ostava 300*0,02 = 6 raov a teda 10^6 = milion-nasobne vacsia narocnost. Je to menej ako 10^300, ale aj tych 10^6 je dost. Hlavne ked specialny tvar 1024-bit trva 2 mesiace, tak specialny tvar 2048-bit bude trvat 2 miliony mesiacov. Ta super ne? A co ked specialny tvar cisla zarucil ze pojde iba 95% hodnoty zvyseneho exponentu ide do stratenej prdele? potom to neni milion-nasobok, ale biliarda-nasobok a teda specialny tvar 2048-bit bude trvat 2 biliardy mesiacov. Odpovedať Známka: 10.0 Hodnotiť:

Re: kluce Od: :Pjetro de | Pridané: 12.10.2016 20:25 1B) 65536-bitove prvocisla sa hladaju asi trocha tazsie ako napr. 4096-bitove. 2) Nikto nikde este len neprechadza, neni problem mat soft ktory podporuje 4096- alebo 8192-bitovu verziu klucov pri vytvarani certifikatov a SHA512 hesku. To ze je niekde certifikat s 1024 bit a SHA1 (nedajboze MD5) je problem inde. 3) Slabina sa ukaze az s pravymi kvantovymi pocitacmi, kde budu aj 1048576-bitove kluce na uplne hovno. Odpovedať Známka: 10.0 Hodnotiť:

Re: kluce Od: Reg.: x x l l | Pridané: 13.10.2016 1:40 1B) ak si to myslel v zmysle generovania prvocisel, tak to nie je uplne pravda. Vygenerovat velke prvocislo je paradoxne ovela jednoduchsie, ako skutocne dokazat, ze ide o prvocislo. Ale ano, neches cakat desiatky sekund, kym sa ti nadviaze TLS session :D 3) Kvoli kvantovym pocitacom sa uz dnes pripravuju "post quantum" algoritmy, ktore budu odolne voci utokom kvantovymi pocitacmi. Je to vsetko v ranych stadiach, ale az ta doba nastane, tak tu urcite bude vhode riesenie :) Napr. Google pridal relativne nedavno "New hope" algoritmus do experimentalych verzii Chrome. Odpovedať Hodnotiť:

Re: kluce Od: chrome | Pridané: 13.10.2016 5:51 "the empire strikes back" - alebo nechaju ten google algoritmus trojpismenkove agentury na pokoji? Odpovedať Hodnotiť:

Re: kluce Od reg.: Pjetro de | Pridané: 13.10.2016 8:01 Pokial sa nemylim oni sa vlastne negeneruju prvocisla, ale pseudo-prvocisla. Preto to ide tak "rychlo". T.j. existuje neslusne mala (ale zato nenulova) pravdopobonost, ze to neni prvocislo. Napr. sanca 1 : 10^50 ze to 1024-bitove (cca 300-ciferne) cislo neni prvocislo. S tym sa da uspokojit. Nikto len tak na beziacom pase negeneruje 8192-bitove prvocisla ako ze naozaj preukazane, ze su prvocisla. Zvlast ked nie su nejakeho specialneho tvaru a na absolutne overenie prvociselnoti nemozno pouzit kvantum efektivnejsich algoritmov. Odpovedať Hodnotiť:

Re: kluce Od: zxcvbn | Pridané: 12.10.2016 20:47 Pretoze napr. aby tvoj mobil nadviazal HTTPS spojenie s eshopom pomocou 32768b kluca, tak to je jednoduchsie rovno ist nakupovat do kamenneho obchodu. Odpovedať Známka: 8.8 Hodnotiť:

Re: kluce Od reg.: nemam a nebudem mat | Pridané: 12.10.2016 21:44 ak by v nom bolo vobec miesto na ulozenie takeho kluca :D Odpovedať Známka: -6.0 Hodnotiť:

Re: kluce Od: zxcvbn | Pridané: 13.10.2016 10:44 32kB? Bitch please. Odpovedať Známka: 10.0 Hodnotiť:

Re: kluce Od reg.: RB_    | Pridané: 15.10.2016 21:21 dal by som ti plus keby si za otaznikom vynechal to trapne meme z roku 2012 Odpovedať Hodnotiť:

Re: kluce Od: Dddddddd | Pridané: 12.10.2016 20:50 DHE s 2048 je v podstate vacsi vykonovy problem pre samotny server ako pre utocnika. :-( Odpovedať Známka: 7.1 Hodnotiť:

Re: kluce Od: syntaxterrorA | Pridané: 12.10.2016 21:10 Presne tak. Na pripojenie logaritmického pravítka, uchyteného napríklad cez Merkur a ovládaného Rasberry PI treba minimálne RS-232 a to je v datacentrách a najmä virtuálnych serveroch komplikované nielen bezpečnostnými predpismi. Odpovedať Známka: 1.5 Hodnotiť:

Re: kluce Od: Fako | Pridané: 12.10.2016 21:25 To je taka pichovina, ze som ti musel dat plusko! :-) Odpovedať Známka: 5.7 Hodnotiť:

Re: kluce Od: |\|\|\| | Pridané: 13.10.2016 9:24 https://youtu.be/MEyIppEOQTw Odpovedať Známka: 10.0 Hodnotiť:

Re: kluce Od: Reg.: x x l l | Pridané: 13.10.2016 1:21 Vies preco sa nepouzivaju? Lebo tomu nerozumies. Tak preto :) Odpovedať Známka: 10.0 Hodnotiť:

to nie je nic nove Od reg.: Lars Schotte | Pridané: 13.10.2016 22:04 vseobecne ked sa pozerame na historiu, co sme zazili poslednych 20 rokov, tak je to furt nejake zvaecsovanie alebo predlzovanie dlzok klucov. nedavno este md5 bol povazovany za bezpecny, teraz uz nie je povazovany za bezpecny ani sha-1 a s kryptografiou to je to iste, ako si mysleli, ze DES je super, potom presli na 3DES a nakonec to aj tak dumpli cele pre AES a aj u tych AES boli prelomene tie nizke verzie. To, ze teraz niekdo pride s tym, ze v DH algoritme pre asymetricke kryptovanie sa tiez nasli chyby, resp ze sa predlzuje s 1k na 4k alebo podobne, to tiez neni nic nove. Tiez boli casy ked sa pouzivali 768bitove kluce pre asymetricku kryptografiu, kym boli prelomene. Takisto je uz kopec seliakych blacklistov, ako napr v OpenSSH, kere cisla su odmietane. To tiez neni nic nove. Vseobecne je kryptografia len jedna cast bezpecnosti. Odpovedať Hodnotiť:

to nie je nic nove part2 Od reg.: Lars Schotte | Pridané: 13.10.2016 22:04 Ak mas nejaku linku, napr SSH a spoliehas sa na to, ze saq to je kryptovane, tak si blazon. Lebo ak sa v SSH najde chyba, tak de je bezpecnost? Preto je dobre mat okrem toho seckeho aj bezpecnost fyzicku, limitovanie pristupu k svetlokablom a podobne. Odpovedať Hodnotiť:

Re: to nie je nic nove part2 Od: Tokiki | Pridané: 15.10.2016 0:23 Mudry si jak radio. Odpovedať Hodnotiť:

Pridať komentár