Minimipituus turvallisena pidettävälle salausavaimelle

1.11.1999

Kari Tuomainen
Tietotekniikka
Teknillinen korkeakoulu
Kari.Tuomainen@hut.fi

Tiivistelmä

Useimmissa kryptograafisissa menetelmissä avaimen pituus määrää pitkälti sen, kuinka hyvin sillä salattu tai suojattu tieto pysyy suojassa. Tässä esseessä tarkastellaan nimenomaan tällaisten salausmenetelmien turvallisuuden riippumista käytetyn avaimen pituudesta, tarkastellaan nykyisin käytössä olevien salausjärjestelmien avaimenpituuksia ja annetaan suosituksia vähimmäispituuksista. Lisäksi tarkastellaan minkä syiden takia nykyään ei riittävä avaimenpituus ole mikään itsestäänselvyys.

1 Johdanto

2 Erilaisia salausmenetelmäluokkia

2.1 Symmetriset salausmenetelmät

2.2 Epäsymmetriset salausmenetelmät

2.3 Poikkeuksia

3 Tyypillisen käyttäjän käyttämiä salausohjelmia

3.1 Netscape

3.2 PGP

4 Millaisia avaimia nykypäivänä pystyään murtamaan

4.1 Symmetristen avainten murtokilpailut

4.2 Epäsymmetristen avainten murtokilpailut

5 Poliittiset tekijät

6 Johtopäätökset

Lähdeluettelo

Lisätietoja

1 Johdanto

Useissa kryptograafisissa menetelmissä voidaan salattu viesti saada käytännössä selville ns. brute force -menetelmällä, eli kokeilemalla kaikki mahdolliset avaimet läpi. Jos salausavain ajatellaan biteistä koostuvana jonona, jonka pituus on n bittiä, niin avainavaruuden koko on 2n. Brute force -hyökkäyksessä tarvitaan keskimäärin 2n/2 = 2n-1 yritystä, ennen kuin oikea avain löytyy - ts. keskimäärin joudutaan kokeilemaan puolet avaimista, ennen kuin oikea avain löytyy. Koska tarvittava työmäärä kasvaa eksponentiaalisesti, kasvaa murtamisen vaikeus merkittävästi jo verraten pienestä avaimen pituuden lisäyksestä.

Toisaalta, joidenkin tahojen intressien mukaista on ollut rajoittaa riittävän pitkien avainten käyttöä, vaikka niiden toteuttaminen ei ohjelmallisesti olisi juuri sen vaikeampaa kuin lyhyempienkään. Käytännössä tällaisia tahoja on mm. eräiden suurten valtioiden tiedustelupalvelut, joille kunnollisten salaustuotteiden yleistyminen aiheuttaisi ongelmia. Usein nämä tahot ovat perustelleet rajoituksia mm. terrorismin tai järjestäytyneen rikollisuuden vastaisella taistelulla, mutta lienee luultavaa, että suurimmat rikollisorganisaatiot ovat jo pitkään käyttäneet riittävän pitkiä salausavaimia; salausmenetelmäthän on varsin hyvin tunnettuja. Käytännössä salausrajoitukset tarjoavat enemmän mahdollisuuksia mm. teollisuusvakoiluun ja pienempien pelureiden tarkkailuun.

2 Erilaisia salausmenetelmäluokkia

2.1 Symmetriset salausmenetelmät

Parhaiten brute force -hyökkäykset kuvaavat sitä, millaista on pahimmillaan ns. symmetrisia salausmenetelmiä kohtaan hyökkääminen. Näissä menetelmissä viesti salataan ja puretaan samalla avaimella, joka on yleensä merkittävästi salattavaa viestiä lyhyempi. Eräs nykymittapuun mukaan liian lyhyisiin avainpituuksiin kykenevä, mutta kuuluisa symmetrinen salausmenetelmä on DES. Sen sijaan modernimpia ja pidempiin symmetrisiin avaimiin soveltuvia salausmenetelmiä ovat mm. 3-DES, IDEA ja Blowfish. Tällä hetkellä avaimen vähimmäispituudeksi tyypillisessä symmetrisessä salausmenetelmässä suositellaan 128 bittiä2.

2.2 Epäsymmetriset salausmenetelmät

Eräs toinen tärkeä luokka kryptograafisia menetelmiä on ns. epäsymmetriset salausmenetelmät, joita usein kutsutaan myös julkisen avaimen menetelmiksi. Niissä salaus- ja purkuavain eivät ole samoja. Näissä usein salausavain on ns. julkinen avain, jota voidaan jakaa kaikille halukkaille tahoille ilman rajoituksia. Tällä avaimella salatut viestit purkava avain on taas salainen avain. Useimmiten epäsymmetrisiä menetelmiä käytetään symmetristen salausmenetelmien kanssa siten, että ensiksi arvotaan satunnainen symmetrisen menetelmän avain, jolla salataan varsinainen viesti. Sitten tämä avain salataan julkisella avaimella ja välitetään viestin kanssa toiselle osapuolelle. Lisäksi julkisen avaimen menetelmiä käytetään viestien yms digitaaliseen allekirjoitukseen. Epäsymmetrisillä salausmenetelmillä usein hyökkäykset ovat brute force -menetelmää hienostuneempia ja näistä syistä tarvittavat avaimenpituudet ovat merkittävästi pidempiä kuin symmetrisissä menetelmissä. Eräitä kuuluisimmista epäsymmetrisiä menetelmistä ovat RSA, Diffie-Hellman sekä elliptisiin käyriin perustuvat menetelmät. Vähimmäissuosituksena RSA:lle ja Diffie-Hellmanille voidaan nykyään pitää noin 1000 bittiä. Sen sijaan elliptisten käyrien kohdalla ei nykytietämyksen mukaan tarvitse käyttää aivan yhtä pitkiä avaimia.

2.3 Poikkeuksia

Eräs symmetrisiin salausalgoritmeihin kuuluva salausmenetelmä on mielenkiintoinen poikkeus. Tässä ns. one time pad -menetelmässä käytetään kertakäyttöistä avainta, joka on yhtä pitkä kuin salattava eksti. Salaus toimii siten, että salattava teksti XORrataan salausavaimen kanssa ja saatu luku on kyseinen viesti salattuna. Tässä menetelmässä hyökkääjän ongelmana on se, että koko avainavaruuden läpikäyminen tuottaa oikean selväkielisen sanoman lisäksi kaikki muutkin yhtä pitkät merkkijonot. Käytännössä one time padin käyttäminen on kuitenkin usein liian vaikeaa, koska se vaatii suuren määrän salaisen ja satunnaisen datan toimittamista etukäteen osapuolelle, jonka kanssa halutaan kommunikoida. Lisäksi varastoitaessa tietoa ei ole kovin järkevää käyttää one time padia, sillä jos tieto halutaan joskus vielä purkaakin, tulee itse avainkin vielä tallentaa turvallisesti - ja tällöinhän voisi aivan yhtä hyvin tallentaa itse salattavan datan sinne, minne aikoisi avaimen tallettaa - nehän ovat yhtä pitkiä.

3 Tyypillisen käyttäjän käyttämiä salausohjelmia

3.1 Netscape

Yhdysvaltojen ja Kanadan sisällä levitettävässä Netscape-versiossa on käytössä 128-bittinen avain symmetrisessä salausmenetelmässä. Sen sijaan kansainvälisesti levitettävässä versiossa avaimenpituus on vain 40 bittiä, jota pidetään riittämättömänä turvalliselle liikenteelle. Pienenä poikkeuksena tälle on pankkilaitokset, joille myönnetyillä sertifikaateilla myös kansainväliset versiot Netscapesta suostuvat käyttämään pidempiä avaimia.

3.2 PGP

PGP käyttää IDEA-salauksessa turvallisena pidettyä 128 bitin avainpituutta ja RSA:ssa se tukee avaimenpituuksia 2048 bittiin asti. Lisäksi uudemmat versiot tukevat pidempiä RSA-avaimia ja niissä on tukea myös muille epäsymetrisille salausmenetelmille kuin vain RSA:lle.

Millaisia avaimia nykypäivänä pystytään murtamaan

4.1 Symmetristen avainten murtokilpailut

RSA Security -yhtiö on jo useamman vuoden ajan järjestänyt murtokilpailuja, joissa on rahapalkintoja, jotta ihmisillä olisi enemmän intoa etsiä ja osoittaa heikkojen salaustapojen heikkous. Eräs tällainen kilpailu oli 56-bittistä avainta käyttävällä DES-algoritmilla salatun tiedon murtaminen.

Electronic Frontier Foundationin suorittama murtoprojekti onnistui murtamaan kyseisen salauksen alle 3 päivässä, vaikka aiempi julkinen ennätys oli vaatinut 39 päivää tuhansilta tietokoneilta1. EFF:n salaisuutena oli tehtävää varten nimenomaisesti suunnitellut mikropiirit. Luultavasti vähintään yhtä tehokkaita tällaisia piirejä on myös esimerkiski Yhdysvaltain vakoilu- ja tiedusteluorganisaatioiden käytössä.

4.2 Epäsymmetristen avainten murtokilpailut

RSA Security -yhtiön on järjestää myös epäsymmetristen menetelmien murtokilpailuja RSA-avaimilla, joskaan palkinnot eivät ole yhtä suuria kuin eräillä toisilla julkisen avaimen menetelmien murtokilpailuja järjestävillä tahoilla. Tällä hetkellä tiettävästi suurin kilpailuissa murrettu avain on ollut 512-bittinen3.

Lisäksi Adi Shamirin, erään RSA-algoritmin alkuperäisistä keksijöistä, äskettäin keksimä TWINKLE-niminen laite tekee suunnilleen tätä kokoluokkaa olevan RSA-avainten murtamisesta helpompaa kuin ennen. Laite ei kuitenkaan ole mikään suuremmat RSA-avaimet romuttava keksintö, sillä laite ratkaisee vain erään osaongelman4. Sen sijaan isohkon kvanttitietokoneen rakentaminen merktsisi käytännössä RSA-menetelmän romahtamista, sillä tunnetaan tehokas menetelmä murtaa kvanttitietokoneella suuria alkulukuja tekijöihinsä.

Poliittiset tekijät

Eräät suuret valtiot ovat vastustaneet vahvan salauksen käyttöönottoa. Näistä merkittävin on Yhdysvallat - ennen kaikkea sen vuoksi, että hyvin suuri osa ohjelmistoista siellä. Ja salaustuotteiden vientikiellot ovat saaneet aikaan sen, että suosituista ohjelmista usein on muissa maissa saatavissa vain heikkoon salaukseen kykenevät versiot. Vaikka itse salausmenetelmät olisikin helppo toteuttaa kussakin maassa erikeen, niin yhdysvaltain vientisäädökset kieltävät myös sellaisten ohjelmien viemiset, joissa ei olisi vahvaa salausta, mutta joihin olisi helppo lisätä tällainen salaus kussakin maassa. Ainakin tällä hetkellä kuitenkin vahva salaus on sallittua Yhdysvaltojen sisällä, vaikka viranomaiset ovat pyrkineet luomaan järjestelmää, jossa viranomaisilla olisi salatun tiedon avaava toinen avain. Aivan äskettäin Yhdysvallat oli pyörtävinään aiemmin käytännössä ehdottomat vahvan salauksen vientikieltonsa eräänlaisella tarkastusmenettelyllä, mutta varsin yleisesti arvellaan tämän käytännössä vain merkitsevän sitä, että salassa vaaditaan yhdysvaltalaisille viranomaisille avointa takaovea näihin ohjelmiin tai laitteisiin, ennen myönnetään vientilupaa.

Lisäksi suuri määrä länsimaita, Suomi mukaanluettuna, kirjoitti vajaa vuosi sitten ns. Wassenaarin sopimuksen, joka tullee rajoittamaan ainakin jossain määrin vahvojen salaustuotteiden vientiä - ainakin siten, että niitä ei saa viedä ilman erityistä lupaa. Eri asia on sitten myönnetäänkö lupa melkein poikkeuksetta vai onko sellaisen saaminen kovin rajoitettua. Aiemminhan Suomi on ollut varsin salliva salaustuotteiden suhteen, etenkin kun SSH-salausohjelmistosta on ollut muodostumassa tärkeä vientituote.

Johtopäätökset

Vaikka nykyään salaukseen ja muuhun kryptografiaan tarvittavat algoritmit tunnetaankin melko hyvin maailmanlaajuisesti, niin suuressa osassa ohjelmia ei kuitenkaan ole tietoturvaa takaavaa salausta. Tämä koskee erityisesti Yhdysvalloista tuotuja ohjelmistoja. Lisäksi ei tulisi luottaa tuotteeseen, ellei se käytä julkisesti tunnettua protokollaa ja lisäksi tulisi vahvasti harkita käyttääkö sellaista salaustuotetta, josta ei ole lähdekielistä versiota saatavilla, sillä lähdekielisestä versiosta takaporttien pitäisi olla löydettävissä helpommin.

Käytettävistä salausmenetelmistä tulisi varmistaa, että niissä todella käytetään kyseiselle menetelmälle riittävän pitkää avainta. Lisäksi tulisi pitää mielessä, että mitä pidempään salatun tiedon pitäisi pysyä salassa, sitä pidempiä avaimia ja parempia salausmenetelmiä tulisi käyttää. Näissä laskemissa on syytä käyttää tarpeeksi suuria marginaaleja, sillä muutamassa vuosikymmenessä tietokoneteho suhteessa hintaan jatkanee kasvuaan Mooren lain mukaan. Lisäksi brute force -keinot ovat yleensä äärimmäisen hyvin rinnakkaistuvia. Eikä ole syytä unohtaa, että isoimmilla tiedusteluorganisaatioilla saattaa olla tiedossa joitain sellaisia lukuteoreettisia läpimurtoja, joita ei vielä julkisesti tiedetä, mutta jotka saattavat merkittävästi helpottaa joidenkin salausmenetelmien murtamista.

Lähdeluettelo

[1]Anon, EFF DES Cracker Project, 10.9.1999 [viitattu 20.9.1999]
<http://www.eff.org/descracker/>
[2]Blaze, M., Diffie, W., Rivest, R., Schneier, B., Shimomura, T., Thompson, E., Weiner, M., Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security, tammikuu 1996 [viitattu 20.9.1999]
<http://www.counterpane.com/keylength.html>
[3]RSA Security Inc., Factorization of RSA-155, [viitattu 20.9.1999]
<http://www.rsasecurity.com/rsalabs/factoring/rsa155.html>
[4]RSA Security Inc., Questions and Answers: Shamir's Factoring Device and RSA, [viitattu 20.9.1999]
<http://www.rsasecurity.com/rsalabs/bulletins/twinkle_qa.html>

Lisätietoja

Anon, PGP ATTACKS, 10.11.1997 [viitattu 20.9.1999]
<http://axion.physics.ubc.ca/pgp-attack.html>
Anon, Cryptographic Algorithms, [viitattu 20.9.1999]
<http://www.ssh.fi/tech/crypto/algorithms.html>
Anon, Cryptography FAQ, 29.8.1999 [viitattu 20.9.1999]
<http://www.faqs.org/faqs/cryptography-faq/>
Anon, Project RC5, 15.7.1999 [viitattu 20.9.1999]
<http://www.distributed.net/rc5/>
Blaze, M., & Diffie, W., Memo from NSA regarding key length report, with comments from M. Blaze and W. Diffie, [viitattu 20.9.1999]
<ftp://ftp.research.att.com/dist/mab/keylength.nsa>
Curtin, M., Snake Oil Warning Signs: Encryption Software to Avoid, 9.12.1999 [viitattu 20.9.1999]
<http://axion.physics.ubc.ca/snake-oil-faq.html>
Licquia, J., PGP Frequently Asked Questions with Answers, 23.6.1999 [viitattu 20.9.1999]
<http://www.faqs.org/faqs/pgp-faq/>
Lynn, E.D., Amendments to the International Traffic in Arms Regulations, 22.7.1997 [viitattu 20.7.1999]
<http://axion.physics.ubc.ca/ITAR.html>
RSA Security Inc., DES Challenge III Questions and Answers, [viitattu 20.9.1999]
<http://www.rsasecurity.com/rsalabs/des3/des3_qa.html>
RSA Security Inc., RSA Laboratories' Bulletins, [viitattu 20.9.1999]
http://www.rsasecurity.com/rsalabs/bulletins/
Silverman, R.D., An Analysis of Shamir's Factoring Device, 3.5.1999 [viitattu 20.9.1999]
<http://www.rsasecurity.com/rsalabs/bulletins/twinkle.html>