Salasanojen kestävyys

22.10.2021

Salasanojen kestävyys

TL;DR tietokoneiden laskentakyky kasvaa eksponentiaalisesti ja sillä on valtava vaikutus salasanojen kestävyyteen. Toisaalta salasanoja joiden entropia on 192 bittiä on mahdotonta murtaa. Esimerkkejä tämän kaltaisista salasanoista voisi olla 28b3043325104886db6e3c9f7c75f8b1712c1e422314225e (hexadecimal, 48 merkkiä) ja UAEOWtKlFdpMw5QzVBj5wrSEkh/BFueu (base64, 32 merkkiä).

Pidin taannoin meidän perjantai pöhinöissä lyhyen esityksen salasanojen vahvuudesta.

Mikä on riittävän hyvä salasana? Entä onko sama salasana turvallinen enää kymmenen tai kahdenkymmenen vuoden kuluttua?

Suositeltu salasanan pituus on kasvanut vuosien saatossa: vähintään kuusi merkkiä, sitten kahdeksan, kymmenen, kolmetoista… Jatkuuko tämä ikuisesti? Mikä logiikka tässä on taustalla?

Entä jos salasanan pitäisi kestää ikuisesti? Tähän kysymykseen on melko helppo löytää vastaus. Mutta ensin on hyvä selvittää miten salasanan vahvuutta voi mitata.

Salasanan vahvuuden mittari on sen entropia. Hiukan yksinkertaistettuna se kertoo kuinka monta murtoyritystä vaaditaan jotta salasana on varmasti murrettu. Esim. salasana jonka entropia on 42 bittiä vaatii 2^42 murtoyritystä kaikkien kombinaatioiden läpikäymiseksi. Pelkästään numeroista koostuva salasana sisältää 3.322 bittiä entropiaa per numero. Tavuista koostuva salasana sisältää 8 bittiä entropiaa per tavu. Oletus on että salasana on satunnaisgeneroitu. Itse keksittyjen salasanojen entropia on huomattavasti pienempi.

Bruce Schneier on kirjassaan Applied Cryptography selvittänyt kuinka paljon salasanalla tulisi olla entropiaa jotta sitä olisi teoriassa mahdotonta murtaa. Hän siteeraa kirjaansa blogissaan:

If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2^192.

Brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

Salasanat joiden entropia on 192 bittiä ovat hiukan epäkäytännöllisiä pituutensa johdosta jos niitä joutuisi muistamaan tai ylipäätään kirjoittamaan.

Mikä olisi sopivan turvallinen määrä entropiaa salasanalle? Suurimmalle osalle meistä riittää salasanat jotka kestävät vähemmän kuin 100 vuotta jonkun itsepintaisen suurvallan jatkuvaa täyden tehon hyökkäystä.

Edward Snowed on 2013 todennut että NSA:lla on kyvykkyys tehdä triljoona (10^12) murtoyritystä sekunnissa.

Voimme verrata tätä supertietokoneiden kehitysvauhtiin ja tehdä tämän perusteella algoritmin joka laskee tarvittavan määrän entropiaa.

Tietokoneiden kehitys on melko huimaa. Vertailun vuoksi: syyskuussa 2020 julkaistun GeForce RTX 3090 grafiikkakortin suorituskyky oli 29.3 TFlop/s. Maailman nopeimmassa supertietokoneessa oli karkeasti saman verran laskentatehoa (35.9 TFlop/s) 2002. Eli se mikä on tänään maailman nopein tietokone on todennäköisesti 20 vuoden kuluttua kuluttajien ulottuvilla parilla tuhannella eurolla.

Vuonna 2013 maailman nopein supertietokone kykeni laskemaan 33.9 PFlop/s (33.9*10^15 flop/s). Jos tätä vertaa Snowdenin ilmoittamaan triljoonaan murtoyritykseen sekunnissa niin tästä voisi tehdä nopean johtopäätöksen että yksi murtoyritys vaatisi n. 33900 flopsia. Mutta koska emme voi olla täysin varmoja niin päädyin ehkä liiankin konservatiiviseen arvioon käyttää mittana maailman nopeimman supertietokoneiden flop/s kehitystä.

Laskenta

Nyt sukelletaan! Jos matematiikka ja teoria ei kutkuttele niin hyppää rohkeasti suoraan alemmas yhteenvetoon.

Selvitetään flop/s halutulle ajanjaksolle.

  • Poimitaan sivun https://www.top500.org/statistics/perfdevel/ lähdekoodista nopeimman supertietokoneen statistiikka.
  • Muunnetaan data csv muotoon (gflops.csv) siten että ensimmäinen sarake on unix epoc sekunteja ja toinen GFlop/s
  • Tehdään regressioanalyysi jotta voimme laskea miten flop/s tulee kehittymään.
  • Yhtälö on muotoa y = a * b^x jossa x on aika unix epoc sekunneissa ja y on GFlop/s
  • Kun yhtälö integroidaan integrate a*b^x dx from x=i to j saadaan (a * (-b^i + b^j)) / log(b)
  • Nyt voimme laskea kunka monta gigaflopsia kumuloituu ajanjaksolle

Regressioanalyysi hoituu esim. käyttämällä R:ää

data <- read.csv("gflops.csv", header=FALSE)
x <- data[,1]
y <- data[,2]
model <- lm(log(y) ~ x)
a <- exp(unname(model$coefficients[1]))
b <- exp(unname(model$coefficients[2]))
sprintf("a = %s", a)
sprintf("b = %s", b)

regressiokertoimet:

a = 6.80261320890583e-05
b = 1.00000001886219

Esimerkiksi 50 vuodessa kertyy gigaflopseja seuraavasti vuodesta 1994 sekä 2020

i = 757382400 # 1994-01-01T00:00:00Z
j = 2335219200 # 2044-01-01T00:00:00Z
gflops = (a * (-b^i + b^j)) / log(b) = 4.859636690149365E22
i = 1577836800 # 2020-01-01T00:00:00Z
j = 3155760000 # 2070-01-01T00:00:00Z
gflops = (a * (-b^i + b^j)) / log(b) = 2.5601462397922633E29

Jos oletamme että yksi flops vastaa yhtä murtoyritystä niin tarvittava entropian määrä jotta salasanalla olisi 50% todennäköisyys tulla murretuksi:

  • muunnetaan gigaflops => flops
  • otetaan luvusta log2 jolloin saadaan tarvittava bittien määrä kaikkien kombinaatioiden läpikäymiseksi
  • lisätään 1 jotta päästään 50% todennäköisyyteen

Esimerkiksi

log2(2.5601462397922633E29 * 1000000000) + 1 = 128.589493827428332
# tai jos oletetaan että yksi murtoyritys vaatii 33900 flops:
log2(2.5601462397922633E29 * 1000000000 / 33900) + 1 = 112.540496174517264

Lopuksi laskemme tarvittavan salasanan pituuden

L = ceil(H/(log2(N)))

Jossa L on salasanan pituus, H on entropian määrä, N on symbolien määrä ja ceil pyöristää ylöspäin.

Joitain esimerkkejä

ceil(128.59/(log2(10))) = 39 # digits
ceil(128.59/(log2(16))) = 33 # hex
ceil(128.59/(log2(62))) = 22 # alphanumeric
ceil(128.59/(log2(64))) = 22 # base64
ceil(128.59/(log2(95))) = 20 # printable ascii
ceil(128.59/(log2(256))) = 17 # bytes
ceil(128.59/(log2(7776))) = 10 # diceware

Yhteenveto

Kävimme läpi miten salasanan vahvuus määritetään entropian avulla, mikä on suurin tarvittava entropian määrä ja miten tietokoneiden kehitys tulee vaikuttamaan salasanojen kestävyyteen. Seuraavaksi kävimme läpi miten salasanan entropia laskentaan halutulle ajanjaksolle sekä miten salasanan pituus lasketaan entropiasta.

Mitä tästä kaikesta pitäisi jäädä käteen? Tietokoneiden laskentateho kehittyy exponentiaalisesti ja sillä on valtava vaikutus salasanojen kestävyyteen. Salasana joka voi olla nyky suosituksilla turvallinen voi olla melko turvaton 20 vuoden kuluttua.

Mutta onko hyvällä salasanalla lopulta suuri merkitys?

Algoritmit saattavat murtua ajan saatossa, ihmiset saattavat murtua tai tulla huijatuksi ja tapoja saada salasana on monia. Pointti näissä on että salasanat jotka ovat laskennallisesti murtamattomissa voivat silti murtua inhimillisen erheen seurauksena.

Näistä huolimatta aina kannattaa valita salasana joka on kuhunkin käyttötarkoitukseen tarpeeksi vahva.

Mutta ennen kuin ryntää vaihtamaan kaikkia salasanoja on parempi miettiä ovatko muut käytännöt kunnossa, kuten salasanojen hallinta.