Information Security 2023/24 spring

Avaliku võtme krüptograafia

Erinevalt sümmeetrilisest krüpteerimisest kasutatakse avaliku võtme krüptograafias (Public Key Cryptography, PKC) kahte võtit — avalikku ja salajast võtit. Mõnikord nimetatakse salajast võtit ka privaatvõtmeks, ilmselt kuna inglise keeles on selles kontekstis kasutusel termin private key (ning avaliku võtme vasteks on public key).

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 (selleks, et matemaatilisest poolest aru saada on vaja õppida ülikoolis algebrat). Elliptkõveratel (elliptic curve) põhinevad süsteemid kasutavad ära jagamise probleemi elliptkõverate rühmades. 2019. aastal tegurdati 795 bitine arv ja 2020. aasta alguses tegurdati 829 bitine arv (uudislugu), aga nendest suuremaid arve pole siiani suudetud tegurdada (vähemalt pole selle kohta avalikku infot).

Ka avaliku võtme krüptosüsteemides kasutatavate võtmete pikkusi väljendatakse 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 elliptkõ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 tervikluse 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.

Need omadused võimaldavad dokumendi räsi kasutada digiallkirjastamisel ehk 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.

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. Kollisiooni leidmine tähendab seda, et on leitud kaks suvalist sisendväärtust (nt. dokumenti), mis annavad täpselt sama räsi. Seetõttu annaks kollisioonide leidmine võimaluse teatud tüüpi pettuste korraldamiseks. Näiteks saaks krüptograafiliselt nõrka räsifunktsiooni kasutava signeerimisalgoritmi korral leida kaks sama räsiga dokumenti ning seejärel meelitada allkiri välja ühele neist dokumentidest. Kuna mõlemal dokumendil on sama räsi, siis saaks digiallkirja konteineris asendada ühe faili teisega. Praktikas loomulikult niisugused ründed võimalikud ei ole, kuna digiallkirjastmiseks kasutatakse krüptograafiliselt tugevaid räsifunktsioone. Isegi kui selgub, et kasutatava räsifunktsiooni kollisioonikindluse omadust saab murda, siis see ei tähenda see automaatselt, et digiallkirju saaks võltsida. Näiteks SHA-1 korral ennustati ette, et kollisiooni leidmine peaks olema võimalik ning seetõttu vahetati see aegsasti üle kogu maailma turvalisema SHA-2 vastu.

Samuti ei tähenda kollisioonide leidmine, et lisaoriginaalikindlus oleks murtud, kuna see on tugevam turvaomadus. Näiteks pole ei MD5 ega SHA-1 jaoks leitud rünnet lisaoriginaalikindluse vastu. Seega kui on olemas mingi konkreetse dokumendi räsi, siis pole praeguste teadmiste põhjal võimalik leida räsifunktsioonile teist sisendit (nt. teist dokumenti), mis annaks tulemuseks täpselt sama räsi. See on oluline digiallkirjastamise juures, sest see kaitseb minevikus allkirjastatud dokumente (st. mingit konkreetset dokumenti ehk räsifunktsiooni sisendit). Mõelge, et mis probleemid tekiksid digiallkirjastatud dokumendiga kui digiallkirjastamiseks kasutatud räsifunktsioonis leitaks rünne lisaoriginaalikindluse vastu. Samas kui on juba leitud rünne räsifunktsiooni kollisioonikindluse vastu, siis tasub olla ettevaatlik, sest pole teada kunas võidakse leida ka rünne lisaoriginaalkindluse vastu. Seetõttu on mõistlik vanad SHA-1 abil allkirjastatud failid üle allkirjastada nii, et kasutusel oleks turvaline räsifunktsioon (nt. SHA-256).

Näide räsifunktsiooni kasutamisest: leitud on räsi lausele "krüptograafiline räsifunktsioon on ühesuunaline".

Kvantarvutid ja avaliku võtme krüptograafia

Kvantarvutid on arvutid, mis suudavad ära kasutada kvantefekte. Seetõttu saavad kvantarvutid lahendada mõningaid keerulisi probleeme, 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 kuni ruutjuure võrra variantide arvust. Seega saaks ideaalsetes tingimustes Groveri algoritmi abil 128 bitise AES võtme lahti murda {$ 2^{64} $} operatsiooniga (praktikas ei pruugi Groveri algoritmi kasutamine nii lihtne olla). 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. 2019. aastal esitles IBM 53 kvantbitist kvantarvutit ning 2020. aasta septembris kuulutati välja plaan luua aastaks 2023. 1000 kvantbitine arvuti. 2022. aasta novembris teatas IBM 433 kvantbitise protsessori loomisest. Ühtlasi tutvustas IBM kvantarvutite arendamise edasisi plaane, mida nad on iga aasta uuendanud. 2023. aastal tuli IBM välja 1121 kvantbitise protsessoriga, koodnimega Condor.

2023. aastal uuendas IBM kvantarvutite arendamise edasisi plaane, nüüd kirjeldatakse plaane kuni 2033. aastani. Allikad: IBM kvantarvuti arendamise teekaart, foto.

Siiski pole siiani suudetud ehitada kvantarvuteid mida saaks kasutada praktiliste ülesannete lahendamiseks. Selleks, et kvantarvuti saaks efektiivselt kvantbitte kasutada ei piisa ainult kvantbittide arvu suurendamisest, kuna lisaks tuleb minimaliseerida ka 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 ja praktilist kasutust omavate 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: Nüüdseks juba aegunud Facebooki veebisertifikaadilt on näha, et selle allkirjastamiseks kasutati räsialgoritmi SHA256 ning avaliku võtme krüptosüsteemina oli kasutusel RSA.

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 sertifitseerimiskeskuseks 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 (2017)
  • SHAttered
  • Why it’s harder to forge a SHA-1 certificate than it is to find a SHA-1 collision
• Muud lingid
  • Krüptograafiliste algoritmide elutsükli uuringud
  • Krüptoalgoritmid ning nende tugi teekides ja infosüsteemides (2023)
  • Public Key Cryptography: Diffie-Hellman Key Exchange
  • Ten Risks of PKI: What You’re not Being Told about Public Key Infrastructure (2000)
  • Attack against DigiNotar (2011)
  • A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography (2013)
  • NIST to Standardize Encryption Algorithms That Can Resist Attack by Quantum Computers (2023)