Šifrovací knihovna s obtížným dešifrováním

[Ondřej Novák]

Zdar

Potřebuju poradit, ukázat kde hledat následující (bohužel nevím, jak se zeptat googla)

Knihovnu (nějaký libXXX-dev, ještě lépe se zdrojáky) která by realizovala šifrování a dešifrování s tím, že při zadání správného hesla by dešifrování trvalo nějakou významnou dobu, třeba stovky milisekund až sekundy. Ideálně, kdyby se obtížnost zašifrování dalo nastavit při šifrování.

Cílem je významně ztížit offline louskání hesla brutal force. Je mi jasné, že když útočník použije nějaký distribuovaný systém louskání, tak že stejně nemám moc šancí, ale to bych řešil tím, že bych obtížnost nastavoval podle toho, jakou data mají hodnotu. (příklad... zašifrování privátního klíče bitcoinové adresy)

Nějaký nápad?

[Reklama]

[Emanuel Komínek]

Obecně se to řeší tak, že zprávu zašifrujete mnohokrát dokola (desítky i stovky tisíc průchodů).

[sycheable]

Tahle predstava mi prijde trochu blazniva. Knihovna implementuje ruzne zname algoritmy. Nehledas tedy knihovnu, ale algoritmus. Jak dlouho bude trvat utok hrubou silou zalezi predevsim na delce klice a pouzitem algoritmu. Dnes je pro symetrickou kryptografie pouzivany Advanced Encryption Standard. Podporuje delky klicu 128, 192  a 256 bitu. Schvalne zkus pohledat, jak by takovy brutte force utok trval (Pokud neznas backdoor - to by te ale IMHO tezko zajimala data pana Novaka)

Samozrejme, daji se delat ruzne veci - napr. sifrovat postupne vice algoritmy, ale hlavni problem je spise sprava klicu nez resit (vicemene nerealny) brutte force utok.

[Santa]

Chceš použít nějakou key derivation function, třeba PBKDF2 nebo scrypt. Tyhlety funkce mají jako jeden z parametrů počet iterací. Ten nastavíš tak vysoko, aby operace trvaly (pro tebe) přijatelně dlouho.

[Filip Jirsák]

Nejprve byste měl hledat algoritmus, teprve pak jeho implementaci. Abyste nenašel knihovnu, která implementuje nějaký autorem knihovny vynalezený algoritmus, při zadání správného hesla a použití dané knihovny trvá dešifrování dlouho, ale algoritmus je velmi slabý a snadno rozlousknutelný.

Váš problém se spíš řeší tak, aby útoční po pokusu o rozšifrování nemohl rychle poznat, zda byl úspěšný. Jak ty privátní klíče vypadají? Opravdu jde ode sebe rychle rozeznat, co je privátní klíč a co náhodné číslo?

Jinak pozor na opakované šifrování, je potřeba prověřit, zda se opakovaným šifrováním neoslabuje bezpečnost. Triviální příklad -- XOR s klíčem stejné délky, jako je zpráva, je velice dobrá šifra. Ale pokud jej budete aplikovat opakovaně, budete při lichém počtu opakování dostávat stále stejný výstup, při sudém počtu opakování dokonce původní nešifrovaný vstup.

[Reklama]

[Ondřej Novák]

Chceš použít nějakou key derivation function, třeba PBKDF2 nebo scrypt. Tyhlety funkce mají jako jeden z parametrů počet iterací. Ten nastavíš tak vysoko, aby operace trvaly (pro tebe) přijatelně dlouho.

Díky, našel jsem i nějaké zdrojáky, které PBKDF2 počítají, tak si to s tím zkusím.

[Jenda]

Chceš použít nějakou key derivation function, třeba PBKDF2 nebo scrypt. Tyhlety funkce mají jako jeden z parametrů počet iterací. Ten nastavíš tak vysoko, aby operace trvaly (pro tebe) přijatelně dlouho.

Díky, našel jsem i nějaké zdrojáky, které PBKDF2 počítají, tak si to s tím zkusím.

Ano, to bude nejbezpečnější, kopírovat nějaké zdrojáky z netu…

Když máš špatné heslo, KDF ti moc nepomůže (protože složitost útoku roste s délkou hesla exponenciálně, ale s délkou KDF jen lineárně). Mnohem lepší je heslo prostě prodloužit. Příklad: pokud prodloužíš heslo o pouhé dva znaky, ztížíš útok 4000x. Tedy podobně, jako kdybys aplikoval KDF (předpokládám zpomalení z 1 ms na 4 s).

[Bla]

Prakticky každá vlastní knihovna je "nenapadnutelná".

A dokonce i heslo dlouhé na 4 písmekna je NEZLOMITELNÉ!
(To vysvětlím dále.)

Co to znamená?
To znamená, že se nikdo nebude chtít drbat ani s jednoduše XORovaným textem, pokud to nebude dostatečně významné.

Příklad jednoduchého šifrování:
Komprese
Substituuješ písmenka za čísla, tj. nahradíš písmenka pozicí, víš že písmeno A je na pozici 1,20,40,80.
Substituuješ písmenka pomocí vložené tabulky klíčů
Substituuješ v hesle část řetězce
Provedeš XOR o daný počet bitů

Uživatel použil heslo: IVAN
Třeba podle třetího písmenka se rozhodneš že kroky provedeš v tomto pořadí:
Doplnění textu o náhodně vygenerované řetězce, tj. mezi písmena dáváš jiné znaky Ahoj -> Axhioaj 
Substituce z tabulky klíčů a to včetně znaků hesla
Substituce písmenek za čísla
XOR
Doplnění hesla o slovo a číslo: Tedy z IVAN uděláš I2007VANTYDLYDUMVYMRDAMTIzadek
Vtip je v tom, abys z primitivního hesla pomocí šifrovací tabulky vždy dokázal udělat to stejné heslo.
Tím výsledným heslem: I2007VANTYDLYDUMVYMRDAMTIzadek tebou zamotaný text zašifruješ.

Při rozšifrování postupuješ stejně.
Uživatel zadá heslo IVAN, z toho ty vygeneruješ doplněk hesla, tedy celý ten hrozně dlouhý klíč, kterým to je zašifrované: I2007VANTYDLYDUMVYMRDAMTIzadek

Tím to rozšifruješ a provedeš inverzi tvých primitivních metod.

Výhoda?
TVŮJ SOFTWARE NIKOHO NEZAJÍMÁ!
Aby to někdo dokázal rozlousknout, tak mu žádný slovník nepomůže, musí přijít na to, jak generuješ doplněk toho hesla a i kdyby se mu nakrásně povedlo to nějak rozšifrovat (třeba závadou v knihovně), substituce dohromady s XORem jsou pro běžné ignoranty dostatečně bezpečná metoda, aby se na to vykašlali.
Navíc ty provádíš substituci podle nějakého náhodného klíče a XORuješ to podle náhodného klíče.
Velmi pochybuji o tom, že budeš mít data natolik zajímavá, aby na to nasadili vlastní tým analytiků CIA.

[pepak]

Když máš špatné heslo, KDF ti moc nepomůže (protože složitost útoku roste s délkou hesla exponenciálně, ale s délkou KDF jen lineárně). Mnohem lepší je heslo prostě prodloužit. Příklad: pokud prodloužíš heslo o pouhé dva znaky, ztížíš útok 4000x. Tedy podobně, jako kdybys aplikoval KDF (předpokládám zpomalení z 1 ms na 4 s).

To je sice obecně pravda, prakticky ale je velký problém přimět uživatele, aby to heslo smysluplně prodloužil (tzn. jinak, než že za svoje normální krátké heslo dopíše 12345..., aby dostal potřebnou délku). KDF s mnoha smyčkami zabere i v tomto případě.

[pepak]

Prakticky každá vlastní knihovna je "nenapadnutelná".

Naopak.

To znamená, že se nikdo nebude chtít drbat ani s jednoduše XORovaným textem, pokud to nebude dostatečně významné.

A to máte podloženo čím? Naopak, spousta útočníků to zkusí prostě proto, že můžou. Jasně že by bylo lepší prolomit Gmail než stránku s návštěvností 3 UIP denně, ale pokud mám téměř jistotu, že u toho Gmailu neuspěju, je lepší mít úspěch aspoň na té pidistránce.

Substituuješ písmenka za čísla, tj. nahradíš písmenka pozicí, víš že písmeno A je na pozici 1,20,40,80.
Substituuješ písmenka pomocí vložené tabulky klíčů
Substituuješ v hesle část řetězce
Provedeš XOR o daný počet bitů

Toto schéma se používalo už od 16. století, prolomené bylo nejpozději ve století 18.

Doplnění textu o náhodně vygenerované řetězce, tj. mezi písmena dáváš jiné znaky Ahoj -> Axhioaj

To je plně závislé na security by obscurity, tedy na tom, že útočník neví, podle jakého systému se ty jiné znaky doplňují. To nejde dlouhodobě zaručit. Navíc to má i praktické nevýhody, např. příliš velkou redundanci, která nic nepřináší.

[Ondra Satai Nekola]

@Bla - nic tak hloupeho uz jsem dlouho necetl.

Jak uz psali predrecnici. Vzit scrypt, heslo poradne osolit. A uzivatele nutit pouzit netrivialni hesla.

[Filip Jirsák]

Vycházíte z předpokladu, že útočník nemá k dispozici ten šifrovací a dešifrovací kód - tedy že jde o uzavřenou aplikaci, která běží někde na serveru, který je dostatečně zabezpečený. Pak je ale zbytečné dělat ty vaše opičárny, stačí uživatelovo heslo spojit s třeba 40 znakovým heslem "ukrytým" ve zdrojáku a to celé použít jako vstup třeba pro AES. Na rozdíl od vašeho postupu to bude i bezpečné. Váš postup je totiž možné rozlousknout se znalostí několika dvojic vstupní text - šifrovaný text. Stačí tedy, aby se útočník stal uživatelem toho programu a pár svých klíčů tím zašifroval. Analytická práce člověka na tom není potřeba žádná, rozlousknutí substituční šifry zvládne automat.

Pokud útočník ten kód má k dispozici, třeba protože je to program, který běží u uživatele, může mu jednoduše předhazovat jedno heslo za druhým. Protože jste použil čtyřznakové heslo ze slovníku, bude ho mít hrubou silou prolomené za chvilinku. To vaše prokládání hesla jiným známým heslem nemá na výsledek žádný vliv. Heslo nejde automatizovaně prodloužit, pro sílu hesla je podstatné jenom to, kolik bitů neznámého vstupu tam je.

Jediné, co se z vašeho příspěvku dá použít, je to, že ten software může být nezajímavý. Což už si myslelo několik bitcoinových institucí a někdo si na tom pěkně přivydělal. Pak ale stačí ten klíč ukládat třeba pozpátku, aby to nebylo nápadné na první pohled, bude to nesrovnatelně jednodušší, než váš postup, a bezpečnost bude stejná.

[Stalin]

Vyprdni sa na to, snad si nechces nechat radit od ludi, ktori mali nahodou minuly semester zapisanu kryptografiu.

[DgBd]

Vyprdni sa na to, snad si nechces nechat radit od ludi, ktori mali nahodou minuly semester zapisanu kryptografiu.

Tak pořád lepší než si nechat radit od někoho, kdo žádnou přednášku nikdy neměl. Ale i to je patrně lepší než si nechat radit od expertů z RSA.

[Tonda]

Mě tyhlety KDF přijdou jako poměrně zoufalý pokus jak to zaflikovat a ztížit útok, pokud musím vystačit se slabým či krátkým heslem, tj. např. tam kde si hesla volí uživatelé služby, viz nedávný incident u Adobe. Pokud si volím heslo sám, standardní čistý postup je nikoliv nějakými nesmysly uměle zvyšovat výpočetní složitost jednoho pokusu ale zvyšovat počet nutných pokusů, tj. navýšit délku hesla.

Bohužel dotaz je zadán bez zásadních informací o aplikaci toho šifrování, takže těžko radit.