Tilfeldig tallgeneratorangrep - Random number generator attack

Sikkerheten til kryptografiske systemer avhenger av noen hemmelige data som er kjent for autoriserte personer, men ukjente og uforutsigbare for andre. For å oppnå denne uforutsigbarheten brukes vanligvis litt randomisering . Moderne kryptografiske protokoller krever ofte hyppig generering av tilfeldige mengder. Kryptografiske angrep som undergraver eller utnytter svakheter i denne prosessen er kjent som tilfeldige tallgeneratorangrep .

En høy kvalitet tilfeldig tallgenerering (RNG) -prosess er nesten alltid nødvendig for sikkerhet, og mangel på kvalitet gir generelt angrepssårbarhet, og det fører til mangel på sikkerhet, til og med for å fullføre kompromisser, i kryptografiske systemer. RNG -prosessen er spesielt attraktiv for angripere fordi den vanligvis er en enkelt isolert maskinvare- eller programvarekomponent som er lett å finne. Hvis angriperen kan erstatte pseudo-tilfeldige biter generert på en måte de kan forutsi, blir sikkerheten totalt kompromittert, men generelt ikke oppdagbar av noen oppstrøms test av bitene. Videre krever slike angrep bare en enkelt tilgang til systemet som blir kompromittert. Ingen data trenger å sendes tilbake i motsetning til, for eksempel, et datavirus som stjeler nøkler og deretter sender dem en e-post til et eller annet drop point.

Menneskelig generering av tilfeldige mengder

Mennesker gjør det generelt dårlig med å generere tilfeldige mengder. Tryllekunstnere, profesjonelle gamblere og bedragere er avhengige av forutsigbarhet av menneskelig oppførsel. I andre verdenskrig ble tyske kodeksperter instruert om å velge tre bokstaver tilfeldig for å være den første rotorinnstillingen for hver Enigma -maskinmelding . I stedet valgte noen forutsigbare verdier som sine egne eller kjærestens initialer, noe som i stor grad hjalp de allierte med å bryte disse krypteringssystemene. Et annet eksempel er ofte forutsigbare måter datamaskinbrukere velger passord (se passordsprekk ).

Likevel, i det spesifikke tilfellet med å spille blandede strategispill , ble bruk av menneskelig gameplay -entropi for tilfeldighetsgenerering studert av Ran Halprin og Moni Naor .

Angrep

Programvare RNG

Akkurat som med andre komponenter i et kryptosystem, bør en programvare for tilfeldig tallgenerator være designet for å motstå visse angrep. Noen angrep mulig på en RNG inkluderer (fra):

Direkte kryptanalytisk angrep
når en angriper skaffet seg en del av strømmen av tilfeldige biter og kan bruke denne til å skille RNG -utgangen fra en virkelig tilfeldig strøm.
Inputbaserte angrep
endre inngangen til RNG for å angripe den, for eksempel ved å "skylle" eksisterende entropi ut av systemet og sette den i en kjent tilstand.
Statlige kompromissforlengelsesangrep
når den interne hemmelige tilstanden til RNG er kjent på et tidspunkt, kan du bruke denne til å forutsi fremtidig utgang eller for å gjenopprette tidligere utganger. Dette kan skje når en generator starter og har liten eller ingen entropi (spesielt hvis datamaskinen nettopp har blitt startet opp og fulgt en veldig standard operasjonsrekkefølge), så en angriper kan være i stand til å få et innledende gjetning på staten.

RNG -er for maskinvare

En rekke angrep på maskinvare-tilfeldige tallgeneratorer er mulige, inkludert å prøve å fange radiofrekvente utslipp fra datamaskinen (for eksempel å få avbruddstider fra harddisken fra motorstøy), eller prøve å mate kontrollerte signaler til en antatt tilfeldig kilde (f.eks. som å slå av lysene i en lavalampe eller mate et sterkt, kjent signal inn i et lydkort).

RNG -subversjon

Subverted tilfeldige tall kan lages ved hjelp av en kryptografisk sikre pseudo tall generator med et frø verdi kjent for angriperen, men skjult i programvaren. En relativt kort, si 24 til 40 bit, del av frøet kan være virkelig tilfeldig for å forhindre fortellinger om gjentagelser, men ikke lenge nok til å forhindre at angriperen gjenoppretter, for eksempel en "tilfeldig" produsert nøkkel.

Tilfeldige tall går vanligvis gjennom flere lag med maskinvare og programvare før de brukes. Biter kan genereres i en perifer enhet, sendes over en seriell kabel, samles i et operativsystemverktøy og hentes av et systemanrop. De subverterte bitene kan erstattes når som helst i denne prosessen med liten sannsynlighet for deteksjon.

En maskinvarekrets for å produsere undergravede biter kan bygges på en integrert krets på noen få millimeter kvadrat. Den mest sofistikerte maskinvare -tilfeldige tallgeneratoren kan undergraves ved å plassere en slik brikke hvor som helst oppstrøms for hvor tilfeldighetskilden er digitalisert, for eksempel i en utgangsdriverbrikke eller til og med i kabelen som kobler RNG til datamaskinen. Subversjonsbrikken kan inneholde en klokke for å begrense driften til en tid etter at enheten først slås på og kjøres gjennom akseptasjonstester, eller den kan inneholde en radiomottaker for av/på -kontroll. Det kan installeres av produsenten på forespørsel fra deres nasjonale signaler etterretningstjeneste, eller legges til senere av alle med fysisk tilgang. CPU- brikker med innebygde maskinvare for tilfeldige tallgeneratorer kan erstattes av kompatible brikker med en undergravd RNG i chipsenes fastvare.

Forsvar

  • Bland (med for eksempel xor ) maskinvare genererte tilfeldige tall med utgangen på en strømkoder av god kvalitet , så nær brukstedet som mulig. Strømkrypteringsnøkkelen eller frøet bør kunne endres på en måte som kan kontrolleres og hentes fra en pålitelig kilde, f.eks. Terningkast. Den Fortuna slumptallsgeneratoren er et eksempel på en algoritme som bruker denne mekanisme.
  • Generer passord og passord med en ekte tilfeldig kilde. Noen systemer velger tilfeldige passord for brukeren i stedet for å la brukerne foreslå sine egne.
  • Bruk krypteringssystemer som dokumenterer hvordan de genererer tilfeldige tall og gir en metode for å kontrollere generasjonsprosessen.
  • Bygg sikkerhetssystemer med maskinvare på hyllen, helst kjøpt på måter som ikke avslører den tiltenkte bruken, f.eks. Fra gulvet i et stort detaljhandel. Fra dette perspektivet kan lydkort og webkameraer være en bedre kilde til tilfeldighet enn maskinvare laget for dette formålet .
  • Opprettholde fullstendig fysisk kontroll over maskinvaren etter at den er kjøpt.

Å designe en sikker tilfeldig tallgenerator krever minst like høyt omsorgsnivå som å designe andre elementer i et kryptografisk system.

Fremtredende eksempler

Forutsigbart Netscape -frø

Tidlige versjoner av Netscape 's Secure Sockets Layer (SSL) krypteringsprotokoll brukte pseudo-tilfeldige mengder som stammer fra en PRNG som er seedet med tre variable verdier: tid på dagen, prosess-ID og overordnet prosess-ID. Disse mengdene er ofte relativt forutsigbare, og har derfor liten entropi og er mindre enn tilfeldige, og derfor ble den versjonen av SSL funnet å være usikker. Problemet ble rapportert til Netscape i 1994 av Phillip Hallam-Baker , den gang forsker i CERN Web-teamet, men ble ikke løst før utgivelsen. Problemet i å kjøre kode ble oppdaget i 1995 av Ian Goldberg og David Wagner , som måtte reversere den objektkode fordi Netscape nektet å avsløre detaljer om sin tilfeldige tall generasjon ( sikkerhet gjennom uklarhet ). At RNG ble løst i senere utgivelser (versjon 2 og høyere) ved mer robust (dvs. mer tilfeldig og så høyere entropi fra en angriperes perspektiv) såing.

Microsoft Windows 2000/XP tilfeldig tallgenerator

Microsoft bruker en upublisert algoritme for å generere tilfeldige verdier for Windows -operativsystemet . Disse tilfeldige mengdene blir gjort tilgjengelige for brukere via verktøyet CryptGenRandom . I november 2007 fortalte Leo Dorrendorf et al. fra det hebraiske universitetet i Jerusalem og University of Haifa publiserte et papir med tittelen Cryptanalysis of the Random Number Generator of Windows Operating System . Papiret presenterte alvorlige svakheter i Microsofts tilnærming den gangen. Papirets konklusjoner var basert på demontering av koden i Windows 2000, men ifølge Microsoft gjaldt den også for Windows XP. Microsoft har uttalt at problemene som er beskrevet i avisen, er blitt behandlet i påfølgende utgivelser av Windows, som bruker en annen RNG -implementering.

Mulig bakdør i Elliptic Curve DRBG

US National Institute of Standards and Technology har publisert en samling med "deterministiske tilfeldig bitgeneratorer" den anbefaler som NIST Special Publication 800-90. En av generatorene, Dual_EC_DRBG , ble foretrukket av National Security Agency . Dual_EC_DRBG bruker elliptisk kurveteknologi og inkluderer et sett med anbefalte konstanter. I august 2007 viste Dan Shumow og Niels Ferguson fra Microsoft at konstantene kunne konstrueres på en slik måte at de skapte en kleptografisk bakdør i algoritmen. I september 2013 skrev New York Times at "NSA hadde satt inn en bakdør i en 2006 -standard vedtatt av NIST .. kalt Dual EC DRBG -standarden", og avslørte dermed at NSA utførte et angrep mot skadelig programvare mot det amerikanske folket. I desember 2013 rapporterte Reuters at dokumenter utgitt av Edward Snowden indikerte at NSA hadde betalt RSA Security 10 millioner dollar for å gjøre Dual_EC_DRBG til standard i krypteringsprogramvaren, og reiste ytterligere bekymringer for at algoritmen kan inneholde en bakdør for NSA. På grunn av disse bekymringene trakk NIST i 2014 Dual EC DRBG fra utkastet til veiledning om tilfeldige tallgeneratorer, og anbefalte "nåværende brukere av Dual_EC_DRBG overgang til en av de tre gjenværende godkjente algoritmene så raskt som mulig."

MIFARE Crypto-1

Crypto-1 er et kryptosystem utviklet av NXP for bruk på MIFARE- brikker. Systemet er proprietært og opprinnelig har algoritmen ikke blitt publisert. Ved omvendt konstruksjon av brikken fant forskere fra University of Virginia og Chaos Computer Club et angrep på Crypto-1 som utnyttet en dårlig initialisert tilfeldig tallgenerator.

Debian OpenSSL

I mai 2008 avslørte sikkerhetsforsker Luciano Bello sin oppdagelse av at endringer som ble gjort i 2006 i tilfeldighetsgeneratoren i versjonen av OpenSSL- pakken distribuert med Debian Linux og andre Debian-baserte distribusjoner, for eksempel Ubuntu , dramatisk reduserte entropien til genererte verdier og gjorde en rekke sikkerhetsnøkler sårbare for angrep. Sikkerhetssvakheten ble forårsaket av endringer i openssl -koden av en Debian -utvikler som svar på kompilatoradvarsler om tilsynelatende overflødig kode. Dette forårsaket en massiv verdensomspennende regenerering av nøkler, og til tross for all oppmerksomhet problemet fikk, kan det antas at mange av disse gamle nøklene fremdeles er i bruk. Nøkkeltyper som påvirkes inkluderer SSH -nøkler, OpenVPN -nøkler, DNSSEC -nøkler, nøkkelmateriale for bruk i X.509 -sertifikater og sesjonsnøkler som brukes i SSL/TLS -tilkoblinger. Nøkler generert med GnuPG eller GNUTLS påvirkes ikke da disse programmene brukte forskjellige metoder for å generere tilfeldige tall. Nøkler generert av ikke-Debian-baserte Linux-distribusjoner er også upåvirket. Sårbarheten for svak nøklegenerering ble raskt reparert etter at den ble rapportert, men alle tjenester som fortsatt bruker nøkler som ble generert av den gamle koden, er fortsatt sårbare. En rekke programvarepakker inneholder nå kontroller mot en svarteliste med svarteliste for å prøve å forhindre bruk av noen av de gjenværende svake tastene, men forskere fortsetter å finne svake nøkkelimplementeringer.

Playstation 3

I desember 2010 kunngjorde en gruppe som kalte seg fail0verflow gjenoppretting av elliptisk kurve digital signaturalgoritme (ECDSA) privat nøkkel som ble brukt av Sony for å signere programvare for PlayStation 3 spillkonsoll. Angrepet ble gjort mulig fordi Sony ikke klarte å generere et nytt tilfeldig nonce for hver signatur.

RSA offentlig nøkkelfaktorering

En analyse som sammenlignet millioner av RSA offentlige nøkler samlet fra Internett ble kunngjort i 2012 av Lenstra, Hughes, Augier, Bos, Kleinjung og Wachter. De var i stand til å faktorere 0,2% av nøklene ved å bare bruke Euclids algoritme . De utnyttet en svakhet som er unik for kryptosystemer basert på heltallsfaktorisering . Hvis n = pq er en offentlig nøkkel og n ′ = p ′ q ′ er en annen, så hvis tilfeldigvis p = p ′ , så er en enkel beregning av gcd ( n , n ′) = p faktorer både n og n ′, totalt kompromittere begge nøklene. Nadia Heninger , en del av en gruppe som gjorde et lignende eksperiment, sa at de dårlige nøklene forekom nesten helt i innebygde applikasjoner , og forklarer at ett-delt-prim-problemet som ble avdekket av de to gruppene skyldes situasjoner der pseudotilfeldig tallgenerator er dårlig seedet i utgangspunktet og deretter ble sådd igjen mellom generasjonen av første og andre primtal.

Java nonce kollisjon

I august 2013 ble det avslørt at feil i Java -klassen SecureRandom kan generere kollisjoner i k nonce -verdiene som brukes for ECDSA i implementeringer av Bitcoin på Android . Når dette skjedde, kunne den private nøkkelen gjenopprettes, noe som igjen tillot å stjele Bitcoins fra den lommeboken som inneholder .

Se også

Referanser

Videre lesning