Po drátě 4: Řešení úlohy č. 14
Poslední letošní úloha byla uvedena samomluvou našeho mailového robůtka, který si stěžoval na celý svět a zejména na ty zatracené orgy, kteří ho nutí šifrovat jim maily, a ještě k tomu slabými šiframi. A aby svým slovům dodal váhy, rovnou jeden takový mail poslal jako přílohu.Byl to mail jednoho z orgů Nielovi Ambrožovi a byl zašifrován pomocí PGP. To že má být slabá šifra? Vidíte, a byla. Na key serverech byl snadno k nalezení Nielův veřejný klíč. Kdo si ho pořádně prohlédl, nenašel nic zvláštního. Co dál? Prostě cracknout RSA. Cože? Ale ano, i nápověda nás v tom utvrzuje. A jak se RSA crackuje? Nejlépe faktorizací. To je samozřejmě poněkud šílený podnik, 1024-bitové klíče dneska nikdo faktorizovat neumí, jenže jak textík od robůtka, tak falešná manuálová stránka od GPG v nápovědě zmiňovaly, že by to měla být slabá šifra. Kdo vytrval a opravdu faktorizaci zkusil, nejspíš rychle zjistil, že náš 1024-bitový klíč je součinem 30-bitového a 994-bitového prvočísla.
Se znalostí faktorizace už stačilo vyrobit si z veřejného klíče soukromý (třeba oeditováním generátorů klíčů v gpg).
Mimo louskání PGP jsme zaznamenali několik nádherných pokusů o sociální inženýrství :)
Komentář
Tato úloha prošla dlouhatánskou evolucí. Na počátku byl Aniččin nápad vyrobit úlohu s crackováním SSH spojení zabezpečeného krátkým klíčem. Ukázalo se ale, že openssh si s takovými klíči vůbec nedokáže poradit, tak jsme začali hledat jinde. Volba padla na gpg. Krátké klíče opět nefungují (klíč musí mít aspoň 512 bitů, aby se jím dal zašifrovat session key), ale napadl nás jiný ďábelský trik: Vyrobíme RSA klíč, který nebude součinem dvou prvočísel, nýbrž druhou mocninou jednoho prvočísla. RSA s takovými klíči skoro funguje (nedají se dešifrovat pouze zprávy, které jsou dělitelné daným prvočíslem, ale jelikož session key je náhodný, nastane to se zanedbatelnou pravděpodobností) a navíc se takové klíče dají snadno prolomit faktorizací (respektive výpočtem odmocniny :)).
Jenže i zde jsme narazili: upravili jsme si sice gpg tak, aby takové klíče generovalo, ale pak s nimi neumělo pracovat, protože RSA nepočítá přesně podle definice, nýbrž rychlejším algoritmem, ktery je založený na znalosti multiplikativní inverze menšího z prvočísel modulo větší z nich. Ta samozřejmě pro dvě stejná prvočísla neexistuje.
Nakonec jsme tedy zvolili klíč složený ze dvou různých, nicméně velmi různě velkých prvočísel, který se také dá snadno faktorizovat. Tím jsme také úlohu značně zjednodušili, protože stačilo upravit generátor klíčů v gpg, zatímco v případě druhé mocniny prvočísla by se ještě musel předělat, aby správně spočítal Eulerovu funkci.
Úlohu vyrobil Martin Mareš, aniž se nechal zviklat přesvědčením části ostatních organizátorů o tom, že něco takového nám nikdo nevyřeší.
1. Podle OpenPGP RFCcka jsem vytahl z klice $n$ a $e$ (o nedokumentovanem switchiku gpg jsem nevedel a tehdy jsem jeste z mne samemu nepochopitelnych duvodu nechtel sahat primo do gpg).
2. $n$ a $e$ jsem si prevedl do desitkove soustavy, nasazel do Mathematicy a nechal zfaktorizovat. Behem toho jsem si jeste Mathematicou nechal spocitat par dalsich veci, ktere jsem nakonec zahodil.
3. Vyslo mi $d$, to jsem si prevedl zpatky do hexu a chtel si rucne vyrobit novy klic, nez jsem si to nastesti konecne rozmyslel.
4. Stahl jsem GPG a v crypts/rsa.c jsem na mista, kde se generuje prvociselny par, nahardcodoval $d$ a $e$. ./configure && make.
5. Vygeneroval jsem si RSA klic se spravnou velikosti.
6. cat mail | gpg --try-all-secrets
Behem celeho procesu jsem strasne nadaval (zvlaste protoze kdyz jsem testoval, verejny klic jeste nebyl ani na pgp.mit.edu, jen na nejakych mirrorech pgp.net, ktere byly z CESNETu nedostupne; a pak mne Anicka s Martinem presvedcovali, jak je to jednoduche, takze jsem metodu crackovani uplne zavrhl ;), nakonec jsem ale celkem rad, ze jsem si behem lusteni zase zopaknul RSA (uz si to skoro i pamatuju), naucil se dve knihovny pro praci s velkymi cisly, zaklady Mathematicy a zhruba format OpenPGP. :)
2. Nastudování RFC 4880, vytažení hodnot n, e
3. nalezení rozkladu n = p * q, dopočítání f = (p-1)(q-1), určení e tak,
aby de % f = 1 (rozšířený Eukleidův algoritmus), podobně u tak, aby
pu % q = 1.
4. Sestavení minimalistické verze souboru s tajným klíčem podle RFC
4880, pokus o import do GPG. Neúspěšný...
5. Návrat k RFC 4880, vytažení zašifrovaného session key (z = m^e % n),
dešifrování (m = z^d % n) a dekódování session key podle RFC 3447.
6. gpg --decrypt --override-session-key ... mail
Protože už jsem neřešil čas, při počítání (body 3 a 5) jsem si napsal
vlastní "dlouhou aritmetiku". Teprve po vyřešení mi došlo, že jsem to
celé mohl spočítat v bc, který jsem používal jen pro kontrolu při
ladění. Proti Mathematice má navíc výhodu, že není potřeba nic převádět,
když se nastaví ibase a obase na 16.