Entropian ehtyminen ja heikoista avaimista johtuvat virheet

Entropian puutetta esiintyy, kun järjestelmässä ei ole riittävästi ennustamatonta syötettä CSPRNG:n siementämiseen. Näin voi käydä juuri käynnistetyissä sulautetuissa laitteissa, virtualisoiduissa palvelimissa tai järjestelmissä, joissa ei ole käyttäjän syötettä. RNG:n tulosteesta tulee ennustettavaa.

Vuonna 2006 Debian-kehittäjä poisti Valgrindin ilmoittaman rivin: MD_Update(&m, buf, j). Tämä rivi oli entropian lähde. Seurauksena Debianin OpenSSL käytti siemenenä vain PID:tä (enintään 32 768 arvoa). Kaikki vuosina 2006–2008 luodut avaimet kuuluivat 32 768 vaihtoehdon joukkoon.

Debian- ja Ubuntu-järjestelmissä vuosina 2006–2008 luodut RSA-, DSA- ja ECDSA-avaimet, SSH-isäntäavaimet, TLS-varmenteet ja SSL VPN -avaimet vaarantuivat. Vaikutuksen alaisia järjestelmiä olivat Debian Etch, Debian Lenny ja Ubuntu 7.04–8.04. Heikkojen avainten luettelot julkaistiin ja varmenteet mitätöitiin.

Virtuaalikoneita voidaan kloonata identtisen levytilan kanssa. Jos molemmat virtuaalikoneet luovat avaimet samasta CSPRNG-tilasta, ne tuottavat samat avaimet. Hypervisorit syöttävät nykyään entropiaa VirtIO RNG:n tai ACPI-taulukoiden kautta, mutta puutteellisesti määritetyt virtuaalikoneet ovat edelleen alttiita tälle riskille käynnistyksen aikana.

IoT-laitteet (reitittimet, kamerat) luovat usein SSH- ja TLS-avaimet ensimmäisen käynnistyksen yhteydessä, ennen kuin ne ovat keränneet riittävästi entropiaa. Tutkimuksissa havaittiin miljoonia laitteita, jotka jakoivat muutamia tuhansia RSA-avainpareja, koska niiden kaikkien siemenenä oli sama vähän entropiaa sisältävä käynnistystila.

Lenstra ja muut (2012) keräsivät 11,7 miljoonaa TLS-varmennetta ja laskivat niiden parittaiset GCD:t. He löysivät 12 720 RSA-avainta, joilla oli yhteinen alkutekijä — tämä tarkoitti, että molemmat avaimet voitiin tekijöidä kokonaan. 0,2 % kaikista julkisista avaimista oli murrettavissa. Syynä oli riittämätön entropia käynnistyksen aikana.

ECDSA edellyttää joka allekirjoitukselle yksilöllistä satunnaista noncea k. Jos k:ta käytetään uudelleen (tai se on heikko), yksityinen avain voidaan palauttaa välittömästi: d = (s1-s2)^{-1} * (z1-z2) * k / (r1-r2) mod n. Sonyn PS3 käytti arvoa k=constant — kaikki pelit voitiin allekirjoittaa palautetulla avaimella.

Android 4.x:n Java SecureRandom alustettiin tietyissä tilanteissa järjestelmän ajan perusteella. Useat Bitcoin-lompakkosovellukset loivat allekirjoituksia samalla k-noncella, mikä paljasti yksityiset avaimet. Miljoonia dollareita varastettiin. Google korjasi SecureRandom-toteutuksen.

Työkaluja: ssh-vulnkey (tarkistaa Debianin heikkojen avainten luettelon), badkeys (tarkistaa TLS-varmenteista tunnetusti heikot alkuluvut) ja GCD-batch-algoritmi RSA-avainten joukkotarkastukseen. Certificate Transparency -lokit mahdollistavat koko väestön kattavan analyysin.

Käyttäkää getrandom(GRND_RANDOM) -kutsua ensimmäisen avaimen luonnin yhteydessä. Lukekaa /dev/urandom-tiedostosta, kun alkuperäinen siemennys on valmis (tarkistakaa, että /proc/sys/kernel/random/entropy_avail > 128). Käyttäkää laitteiston RNG:tä (RDRAND) täydentävänä entropiana. Älkää koskaan luoko avaimia ensimmäisen käynnistyksen yhteydessä odottamatta.

Säilyttäkää CSPRNG:n tila uudelleenkäynnistysten yli: tallentakaa sammutuksen yhteydessä 32 tavua /dev/urandom-tiedostosta siementiedostoon ja lukekaa ne käynnistyksen yhteydessä takaisin CSPRNG:n syötteeksi. Näin entropian jatkuvuus säilyy kylmien käynnistysten välillä. Linux tekee tämän automaattisesti, mutta sulautetut järjestelmät eivät usein tee sitä.

Entropian puute aiheuttaa ennustettavia avaimia. Todellisia murtoja ovat Debianin OpenSSL (vain PID:hen perustuva siemen), IoT-laitteiden GCD-hyökkäykset, PS3:n ECDSA-noncen uudelleenkäyttö ja Androidin Bitcoin-lompakko. Siementäkää aina käyttöjärjestelmän entropiasta ja tarkastakaa sulautettujen järjestelmien avainten luonti huolellisesti. Seuraavaksi: avainten, noncen ja IV:iden turvallinen luominen.