Information Security 2018/19 spring

Avaliku võtme krüptograafia

Ülevaade avaliku võtme krüptograafiast

Avaliku võtme krüptograafias (Public Key Cryptography, PKC) kasutatakse kahte võtit — avalikku ja salajast võtit.

Salajane võti tuleb hoida salajas ja seda kasutatakse dekrüpteerimiseks või signeerimiseks. Avalikku võtit kasutatakse vastavalt krüpteerimiseks ja vastava salajase võtmega antud signatuuride verifitseerimiseks. Kuna pöördoperatsioonide jaoks (allkirjastamine/allkirja kontrollimine, krüpteerimine/dekrüpteerimine) jaoks kasutatakse erinevaid võtmeid, siis sellest tuleneb ka avaliku võtme krüptograafia teine nimi: asümmeetriline krüptograafia.

Avalik ja salajane võti genereeritakse korraga ja nad on omavahel seotud eelnevalt kirjeldatud omaduste abil, kuid avalik võti ei paljasta informatsiooni salajase võtme kohta ning samuti pole võimalik avalikku võtit kurjasti ära kasutada.

Avaliku võtme krüptograafia põhineb sellel, et avalik võti muudetakse avalikuks, et oleks võimalik saata võtmepaari omanikule krüpteeritud infot ning, et oleks võimalik kontrollida kas signatuur on antud vastavat salajast võtit kasutades. Sellest tulenebki nimetus — avaliku võtme krüptograafia.

Praktiliste avaliku võtme krüptosüsteemide turvalisus põhineb mingil arvutuslikult raskel ülesandel. Nii näiteks põhineb RSA krüptosüsteem sellel, et suuri täisarve on raske tegurdada, krüptosüsteemid DSA ja ElGamal põhinevad diskreetse logaritmi arvutamise raskusel jäägiklassiringides. Elliptilistel kõveratel (elliptic curve) põhinevad süsteemid kasutavad ära jagamise probleemi elliptiliste kõverate rühmades.

Ka avaliku võtme krüptosüsteemides kasutatavate võtmete pikkusi väljendadtakse bittides ning võtme pikkus määrab ära kui raske on ründajal krüptosüsteemi aluseks olevat probleemi "lahendada", st krüptosüsteemi murda. Kuna avaliku võtme krüptosüsteemid tuginevad arvutuslikult rasketel ülesannetel, siis on siin kasutatavate võtmete pikkused oluliselt suuremad kui sümmeetrilise krüptograafia puhul.

Tabel. Soovitava turvataseme (st sümmeetrilise krüptograafia ekvivalendi) saavutamiseks vajalik RSA, diskreetse logaritmi probleemil põhineva krüptosüsteemi (DLOG) või elliptilistel kõveratel (EC) põhineva krüptosüsteemi võtme pikkus bittides. Allikas: ECRYPT II Yearly Report on Algorithms and Keysizes, http://www.ecrypt.eu.org/

Tabel. Enim kasutatud RSA ja diskreetse logaritmi probleemil (DLOG) põhineva krüptosüsteemi võtme pikkuste ekvivalent sümmeetrilise krüptograafia puhul. Allikas: ECRYPT II Yearly Report on Algorithms and Keysizes, http://www.ecrypt.eu.org/

Näited avaliku võtme krüptograafia kasutamisest:

• ID-kaardi kasutamine põhineb avaliku võtme krüptograafial
• HTTPS protokolli kasutamine veebis turvaliselt surfamiseks - TLS
• PGP - võimaldab emaile (ja ka faile) signeerida ja krüpteerida
• SSH - võrguprotokoll turvaliseks terminaliühenduseks
• Bitcoin - virtuaalne maksevahend
• DNSSEC - nimelahendusteenuse (DNS) kirjete terviklikkuse tagamiseks

Krüpteerimine

Avaliku võtme krüptograafias kasutatakse andmete krüpteerimiseks avalikku võtit ja lahtikrüpteerimiseks salajast võtit. See tähendab, et üldjuhul on krüpteerimine kellelegi suunatud - krüpteerida saavad kõik (sest avalik võti on teada), aga dekrüpteerida ainult vastava salajase võtme omanik.

Tasub meeles pidada, et avaliku võtme krüptograafias kasutatavad operatsioonid, eriti dekrüpteerimine on arvutuslikult oluliselt kallimad kui sümmeetrilise krüptograafia puhul. Seepärast kasutatakse suuremate andmemahtude krüpteerimisel neid enamasti koos. Andmete krüpteerimiseks genereeritakse kõigepealt juhuslik võti, mida kasutatakse andmete krüpteerimiseks mõne sümmeetrilise krüpteerimise algoritmiga, näiteks AES. Seejärel krüpteeritakse genereeritud võti avaliku võtmega ning saadud krüptogramm pannakse krüpteeritud andmetega kaasa. Andmete lahtikrüpteerimiseks on vaja kõigepealt salajase võtmega lahti krüpteerida sümmeetrilise krüptoalgoritmi võti ning sellega siis omakorda andmed.

Digiallkiri ja räsifunktsioonid

Kui krüpteerimisel ja dekrüpteerimisel avalikku ja salajast võtit vastupidi kasutada, siis nimetatakse seda protsessi digitaalseks allkirjastamiseks.

Nagu mainitud, siis avaliku võtme operatsioonid on aeglased, eriti salajase võtmega teostatavad operatsioonid. Seepärast ei krüpteerita allkirjastamisel tervet dokumenti vaid ainult selle räsi (hash, ka (message) digest).

Krüptograafiline räsifunktsioon

Räsifunktsioon (hash function) on deterministlik algoritm, mis saab sisendiks suvalise hulga andmeid ning mille väljund on alati ühepikkune (teatud arv bitte). Loomulikult tähendab see seda, et ühele räsifunktsiooni väljundile vastab lõpmata palju sisendeid. Oluline on see, et iga muudatus sisendis muudab tervet räsifunktsiooni väljundit.

Allikas: Wikimedia

Krüptograafias kasutatakse räsifunktsioone mitmel pool ning sellistel krüptograafilistel räsifunktsioonidel on nõutud teatavad omadused:

1. Ühesuunalisus (one-wayness): räsifunktsiooni väljundist ei saa tuletada sisendit, st räsifunktsioon ei ole pööratav.
2. Lisaoriginaalikindlus (second pre-image resistance): teades räsifunktsiooni sisendit on raske leida mõni teine sisend, mis annaks samasuguse väljundi.
3. Kollisioonikindlus (collision resistance): on raske leida kahte erinevat sisendit, mis annaks sama väljundi.

Tuntumad räsialgoritmid on MD5, SHA-1, SHA-2 pere (SHA-224, SHA-256, SHA-384, SHA-512), SHA-3 (ehk Keccak). Nii MD5 (2004. a.) kui SHA-1 (2017. a.) funktsioonides on leitud kollisioone ning seetõttu peetakse neid ebaturvalisteks räsifunktsioonideks.

Leiame räsi lausele "krüptograafiline räsifunktsioon on ühesuunaline".

Need omadused võimaldavad dokumendi räsi kasutada signeerimisel, kus seda kasutatakse n-ö viitena originaaldokumendile. Signeerimisel arvutatakse allkirjastatavast dokumendist kõigepealt räsi ning see krüpteeritakse salajase võtmega ning pannakse dokumendiga kaasa. Allkirja verifitseerimiseks krüpteeeritakse signatuur avaliku võtmega lahti ning seejärel arvutatakse originaaldokumendist uuesti räsi ning kontrollitakse neid omavahel.

Kvantarvutid ja avaliku võtme krüptograafia

Kvantarvutid on arvutid, mis suudavad ära kasutada kvantefekte. Seetõttu saavad kvantarvutid lahendada mõningaid keerulisi probeeme, mida tavaarvutid ei suuda tõenäoliselt efektiivselt lahendada. Üheks niisuguseks probleemiks on naturaalarvude tegurdamine. Tavaarvutite jaoks ei leidu efektiivset algoritmi, mis suudaks leida arvule vastavaid algarvulisi tegureid. Vastavad tegurid peavad leiduma, sest kõik ühest suuremad naturaalarvud on üheselt esitletavad kas algarvuna või siis algarvude korrutisena. Selle teoreemi kohta saate lugeda Wikipedia artiklist.

Pilt, mis illustreerib seda kuidas arv 864 saab algarvulisteks teguriteks jagada. Allikas: Wikimedia

Samas leidub kvantarvutite jaoks algoritm, mis suudab efektiivselt arve tegurdada. Selle algoritmi nimi on Shor algoritm ning selle abil oleks võimalik näiteks RSA katki teha. Selleks, et 2048 bitist RSA võtit lahti murda läheks vaja kvantarvutit kus oleks tuhandeid kvantbitte, ilmselt 10000 või rohkem kui arvestada ka veaparanduskoodidele kuluvaid kvantbitte.

Teiseks oluliseks algoritmiks on Groveri algoritm, mis võimaldab kõikide variantide läbiproovimise keerukust vähendada ruutjuure võrra variantide arvust. Seega saaks Groveri algoritmi abil 128 bitise AES võtme lahti murda {$ 2^{64} $} operatsiooniga. Kuna 64 bitine võti oleks liiga nõrk, siis soovitab NSA USA valitsusasutustel kasutada AES koos 256 bitiste võtmetega. Isegi kui kümne aasta pärast suudetakse toota piisavalt võimsad kvantarvuteid, siis nad ei ole suutelised 256 bitiseid võtmeid lahti murdma - Groveri algoritm võimaldaks 256 bitise turvataseme taandada 128 bitiseks turvatasemeks, mis pakub piisavat kaitset.

Oletatakse, et kvantarvutid võivad muutuda reaalseks 10-30 aasta jooksul ning seetõttu on vaja hakata avaliku võtme krüptograafias kasutatavaid algoritme välja vahetama nende vastu, mida ei ole võimalik kvantarvutitega murda. Sellel teemal on arutletud järgmises artiklis: The Tricky Encryption That Could Stump Quantum Computers.

Praegu tehakse suuri investeeringuid kvantarvutite loomiseks. IBM lõi 2017 aasta lõpus 50 kvantbitise kvantarvuti ja Google avalikustas 2018 aasta alguses 72 kvantbitise kvantarvuti. Selleks, et kvantarvuti saaks efektiivselt kvantbitte kasutada tuleb minimaliseerida arvutuse käigus tekkivad vead. Vigadeparandust saab teha veaparanduskoodide abil, aga need omakorda vajavad oma tööks päris palju kvantbitte. Seega on lähemal ajal üheks peamiseks lahendust vajavaks ülesandeks arvutuse käigus tekkivate vigade parandamine. Kui see probleem õnnestub efektiivselt lahendada, siis jõuame lähemale võimsamate kvantarvutite loomisele.

IBM 50 kvantbitine kvantarvuti (vasakul) ja Google 72 kvantbitine kiip paremal, Allikad: IBM kvantarvuti ja Google kiip.

Google hinnang kvantbittide arvu ja efektiivsete veaparanduskoodide suhtele.
Allikas: https://research.googleblog.com

Avaliku võtme infrastruktuur

Avaliku võtme krüptograafiaga võivad kohe tekkida mõned küsimused, näiteks:

1. Kuidas tuvastada internetis, et veebileht on autentne ehk loodud vastava asutuse / isiku poolt?
2. Kuidas kontrollitakse elektrooniliselt, et ID-kaart kuulub vastavale asutusele / isikule?

Tegemist on tavalise võtmevahetuse probleemiga. Avalikud võtmed on vabalt levitatavad, aga kui te tahate kellelegi midagi krüpteerida, siis kuidas te saate kindel olla, et avalik võti, mille te kuskilt leidsite kuulub tõepoolest sellele isikule, kellele te arvate? Kui ründaja on teile oma avaliku võtme sokutanud, siis kõik sellega krüpteeritud andmed saab tema ka avada.

Et siduda võtmepaar konkreetse isikuga (või ettevõttega, veebilehega), liidetakse avaliku võtme juurde isikuandmed ning seda tulemust nimetatakse sertifikaadiks. Nagu avalik võti, on ka seda sisaldav sertifikaat avalik. Privaatne võti on küll sellega kaudselt seotud, aga seda hoitakse salajas.

Aga siis võiks ju ükskõik kes oma avaliku võtme juurde sertifikaadi tekitada ja öelda, et ta on näiteks Toomas-Hendrik Ilves. Tegelikult võibki, aga vaevalt, et keegi seda inimest usub. Et sertifikaat usaldusväärne oleks, peab keegi kolmas tunnustatud osapool seda kinnitama. Antud juhul nimetatakse seda kolmandat osapoolt sertifitseerimiskeskuseks (certification authority ehk CA) ning ta kinnitab sertifikaadi (isikuandmete ja avaliku võtme seose) allkirjastades (ehk signeerides) selle oma privaatse võtmega.

Näide: Facebooki veebisertifikaadi üldandmed:

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            0b:3c:3b:60:1a:18:f5:9e:e2:b6:bb:05:60:5e:f2:c0
    Signature Algorithm: sha256WithRSAEncryption
        Issuer: C=US, O=DigiCert Inc, OU=www.digicert.com, CN=DigiCert SHA2 High Assurance Server CA
        Validity
            Not Before: Dec 15 00:00:00 2017 GMT
            Not After : Mar 22 12:00:00 2019 GMT
        Subject: C=US, ST=California, L=Menlo Park, O=Facebook, Inc., CN=*.facebook.com
        Subject Public Key Info:
            Public Key Algorithm: id-ecPublicKey
                Public-Key: (256 bit)
                pub:
                    04:88:03:ce:c8:8e:aa:8c:e8:90:57:a6:e3:76:d0:
                    15:c2:56:c0:e3:a0:ff:70:9c:5d:ab:49:5e:b4:a8:
                    2d:77:d2:82:d3:ae:07:ce:43:75:24:d5:db:f5:47:
                    a2:c5:0b:1e:20:b3:6a:49:52:ee:a2:0c:a0:52:fd:
                    bf:81:5c:e5:1b
                ASN1 OID: prime256v1
                NIST CURVE: P-256

Seega ka sertifitseerimiskeskustel on privaatne võti ja sertifikaat ja ka see võib olla signeeritud mõne veel prestiižsema sertifitseerimiskeskuse poolt. Nii tekib puukujuline usaldusseoste struktuur, kus juurtipud on laialdaselt usaldatud, st nende sertifikaadid pole kellegi poolt signeeritud (nn self-signed ehk iseenda poolt signeeritud sertifikaadid). See ongi avaliku võtme infrastruktuur (Public Key Infrastructure, PKI).

Ka Eesti ID-kaart (ja mobiil-ID) on üles ehitatud PKI peale. Igal ID-kaardi omanikul on kaks võtmepaari (üks isikutuvastuseks ja teine allkirjastamiseks), mille privaatvõtmed on ID-kaardi kiibi sees. Eestis on tipmiseks sertifiseerimiskeskuseks SK ID Solutions AS (endise nimega AS Sertifitseerimiskeskus), kes on allkirjastanud kõik isikusertifikaadid. Eestis algas sertifitseerimiskeskuse loomine 2000 aastal ja 2001 aastal loodi AS Sertifitseerimiskeskus firmade AS EMT, AS Hansapank, AS Eesti Ühispank ja AS Eesti Telefon koostööna. SK ID Solutions AS pakub sertifitseerimisteenust lisaks ID-kaartidele ka muude riiklikult oluliste PK teenuste jaoks.

Kasulikud lingid

Siin kirjeldatud avaliku võtme krüptograafia edasiarendustest ja spetsialiseerumistest saab hea ülevaate Matthew Green'i blogipostitusest Beyond public key encryption (inglise keeles). Tema postitus räägib nii identiteedi- ja attribuudipõhisest krüpteerimisest (identity and attribute based encryption) kui ka funktsionaalkrüpteerimisest (functional encryption).

• SHA-1 murdmine
  • Announcing the first SHA1 collision
  • SHAttered
• Muud lingid
  • Krüptograafiliste algoritmide elutsükli uuringud
  • Avaliku võtme infrastruktuur (PKI)
  • Võtmepaari genereerimine SSH jaoks (esimesed neli sammu, ülejäänud on Github spetsiifiline)
  • Public Key Cryptography: Diffie-Hellman Key Exchange