Willekeurige nummergenerator aanval - Random number generator attack

De veiligheid van cryptografische systemen hangt af van enkele geheime gegevens die bekend zijn bij bevoegde personen, maar onbekend en onvoorspelbaar voor anderen. Om deze onvoorspelbaarheid te bereiken, wordt typisch enige randomisatie toegepast. Moderne cryptografische protocollen vereisen vaak het frequent genereren van willekeurige hoeveelheden. Cryptografische aanvallen die zwakke punten in dit proces ondermijnen of uitbuiten, staan ​​bekend als random number generator-aanvallen .

Een hoogwaardig RNG-proces ( random number generation ) is bijna altijd vereist voor beveiliging, en een gebrek aan kwaliteit zorgt over het algemeen voor kwetsbaarheden voor aanvallen en leidt dus tot een gebrek aan beveiliging, zelfs tot volledige compromissen, in cryptografische systemen. Het RNG-proces is bijzonder aantrekkelijk voor aanvallers omdat het doorgaans een enkele geïsoleerde hardware- of softwarecomponent is die gemakkelijk te vinden is. Als de aanvaller pseudo-willekeurige bits kan vervangen die zijn gegenereerd op een manier die ze kunnen voorspellen, is de beveiliging volledig in gevaar, maar over het algemeen niet detecteerbaar door een stroomopwaartse test van de bits. Bovendien vereisen dergelijke aanvallen slechts één enkele toegang tot het gecompromitteerde systeem. Er hoeven geen gegevens teruggestuurd te worden, in tegenstelling tot bijvoorbeeld een computervirus dat sleutels steelt en deze vervolgens naar een afgiftepunt e-mailt.

Menselijke generatie van willekeurige hoeveelheden

Mensen doen het over het algemeen slecht in het genereren van willekeurige hoeveelheden. Goochelaars, professionele gokkers en oplichters zijn afhankelijk van de voorspelbaarheid van menselijk gedrag. In de Tweede Wereldoorlog kregen Duitse codebedienden de opdracht om willekeurig drie letters te selecteren als initiële rotorinstelling voor elk Enigma-machinebericht . In plaats daarvan kozen sommigen voor voorspelbare waarden zoals hun eigen initialen of die van een vriendin, wat de geallieerden enorm hielp bij het breken van deze versleutelingssystemen. Een ander voorbeeld is de vaak voorspelbare manier waarop computergebruikers wachtwoorden kiezen (zie wachtwoord kraken ).

Niettemin, in het specifieke geval van het spelen van gemengde strategiespellen , werd het gebruik van menselijke gameplay- entropie voor het genereren van willekeur bestudeerd door Ran Halprin en Moni Naor .

Aanvallen

Software RNG's

Net als bij andere componenten van een cryptosysteem, moet een softwarematige generator voor willekeurige getallen ontworpen zijn om bepaalde aanvallen te weerstaan. Enkele mogelijke aanvallen op een RNG zijn (van):

Directe cryptanalytische aanval
wanneer een aanvaller een deel van de stroom van willekeurige bits heeft verkregen en dit kan gebruiken om de RNG-uitvoer te onderscheiden van een echt willekeurige stroom.
Op invoer gebaseerde aanvallen
wijzig de invoer naar de RNG om deze aan te vallen, bijvoorbeeld door bestaande entropie uit het systeem te "spoelen" en in een bekende staat te brengen.
Staat compromis extensie aanvallen
wanneer de interne geheime status van de RNG op een bepaald moment bekend is, gebruik dit dan om toekomstige output te voorspellen of om eerdere outputs te herstellen. Dit kan gebeuren wanneer een generator opstart en weinig of geen entropie heeft (vooral als de computer net is opgestart en een zeer standaard reeks bewerkingen heeft gevolgd), dus een aanvaller kan mogelijk een eerste schatting van de status krijgen.

Hardware-RNG's

Er zijn een aantal aanvallen op hardwarematige generatoren van willekeurige getallen mogelijk, waaronder het proberen radiofrequentie-emissies van de computer vast te leggen (bijvoorbeeld het verkrijgen van onderbrekingstijden van de harde schijf door motorruis), of het proberen om gecontroleerde signalen naar een zogenaamd willekeurige bron te sturen (zoals zoals het uitschakelen van de lichten in een lavalamp of het invoeren van een sterk, bekend signaal in een geluidskaart).

RNG-ondermijning

Ondermijnde willekeurige getallen kunnen worden gemaakt met behulp van een cryptografisch veilige pseudowillekeurige nummergenerator met een seed-waarde die bekend is bij de aanvaller maar verborgen is in de software. Een relatief kort, zeg 24 tot 40 bit, deel van het zaad kan echt willekeurig zijn om herhalingen van verklikkers te voorkomen, maar niet lang genoeg om te voorkomen dat de aanvaller bijvoorbeeld een "willekeurig" geproduceerde sleutel terugkrijgt.

Willekeurige getallen doorlopen meestal verschillende hardware- en softwarelagen voordat ze worden gebruikt. Bits kunnen worden gegenereerd in een randapparaat, via een seriële kabel worden verzonden, worden verzameld in een hulpprogramma van het besturingssysteem en worden opgehaald door een systeemaanroep. De ondermijnde bits kunnen op elk punt in dit proces worden vervangen met weinig kans op detectie.

Een hardwarecircuit om ondermijnde bits te produceren, kan worden gebouwd op een geïntegreerd circuit van enkele millimeters in het vierkant. De meest geavanceerde hardware-generator voor willekeurige getallen kan worden ondermijnd door zo'n chip ergens stroomopwaarts te plaatsen van waar de bron van willekeur is gedigitaliseerd, bijvoorbeeld in een uitvoerstuurprogramma-chip of zelfs in de kabel die de RNG met de computer verbindt. De subversion-chip kan een klok bevatten om de start van de operatie te beperken tot enige tijd nadat het apparaat voor het eerst is ingeschakeld en acceptatietests heeft doorlopen, of het kan een radio-ontvanger bevatten voor aan / uit-bediening. Het kan door de fabrikant worden geïnstalleerd in opdracht van hun nationale inlichtingendienst voor signalen, of later worden toegevoegd door iedereen met fysieke toegang. CPU- chips met ingebouwde hardware-generators voor willekeurige getallen kunnen worden vervangen door compatibele chips met een ondermijnde RNG in de firmware van de chips.

verdedigingen

  • Mix (met bijvoorbeeld xor ) hardware gegenereerde willekeurige getallen met de output van een goede kwaliteit stream cipher , zo dicht mogelijk bij het punt van gebruik. De stroomcoderingssleutel of -zaad moet op een manier kunnen worden gewijzigd die kan worden gecontroleerd en afgeleid van een betrouwbare bron, bijvoorbeeld dobbelstenen. De Fortuna random number generator is een voorbeeld van een algoritme dat gebruik maakt van dit mechanisme.
  • Genereer wachtwoorden en wachtwoordzinnen met behulp van een echte willekeurige bron. Sommige systemen selecteren willekeurige wachtwoorden voor de gebruiker in plaats van gebruikers hun eigen wachtwoorden te laten voorstellen.
  • Gebruik coderingssystemen die documenteren hoe ze willekeurige getallen genereren en een methode bieden om het generatieproces te controleren.
  • Bouw beveiligingssystemen met kant-en-klare hardware, bij voorkeur gekocht op een manier die het beoogde gebruik niet onthult, bijvoorbeeld van de vloer in een grote winkel. Vanuit dit perspectief kunnen geluidskaarten en webcams een betere bron van willekeur zijn dan hardware die voor dat doel is gemaakt .
  • Behoud volledige fysieke controle over de hardware nadat deze is aangeschaft.

Het ontwerpen van een veilige generator voor willekeurige getallen vereist minstens even grote zorgvuldigheid als het ontwerpen van andere elementen van een cryptografisch systeem.

Prominente voorbeelden

Voorspelbare Netscape seed

Vroege versies van Netscape 's Secure Sockets Layer (SSL)-coderingsprotocol gebruikten pseudo-willekeurige hoeveelheden die waren afgeleid van een PRNG met drie variabele waarden: de tijd van de dag, de proces-ID en de bovenliggende proces-ID. Deze hoeveelheden zijn vaak relatief voorspelbaar, hebben dus weinig entropie en zijn minder dan willekeurig, waardoor de versie van SSL onveilig bleek te zijn. Het probleem werd in 1994 aan Netscape gemeld door Phillip Hallam-Baker , toen een onderzoeker in het CERN-webteam, maar was niet verholpen voordat het werd uitgebracht. Het probleem in de actieve code werd in 1995 ontdekt door Ian Goldberg en David Wagner , die de objectcode moesten reverse-engineeren omdat Netscape weigerde de details te onthullen van het genereren van willekeurige getallen ( security through obscurity ). Die RNG werd in latere releases (versie 2 en hoger) opgelost door meer robuuste (dwz meer willekeurige en dus hogere entropie vanuit het perspectief van een aanvaller) seeding.

Willekeurige nummergenerator van Microsoft Windows 2000/XP

Microsoft gebruikt een niet-gepubliceerd algoritme om willekeurige waarden voor zijn Windows-besturingssysteem te genereren . Deze willekeurige hoeveelheden worden beschikbaar gesteld aan gebruikers via het hulpprogramma CryptGenRandom . In november 2007 hebben Leo Dorrendorf et al. van de Hebreeuwse Universiteit van Jeruzalem en de Universiteit van Haifa publiceerden een paper met de titel Cryptanalysis of the Random Number Generator of the Windows Operating System . De paper presenteerde ernstige tekortkomingen in de toenmalige aanpak van Microsoft. De conclusies van de paper waren gebaseerd op demontage van de code in Windows 2000, maar waren volgens Microsoft ook van toepassing op Windows XP. Microsoft heeft verklaard dat de problemen die in het document worden beschreven, zijn verholpen in volgende versies van Windows, die een andere RNG-implementatie gebruiken.

Mogelijke achterdeur in Elliptic Curve DRBG

Het Amerikaanse National Institute of Standards and Technology heeft een verzameling "deterministische willekeurige bitgeneratoren" gepubliceerd die het aanbeveelt als NIST Special Publication 800-90. Een van de generatoren, Dual_EC_DRBG , kreeg de voorkeur van de National Security Agency . Dual_EC_DRBG maakt gebruik van elliptische curve-technologie en bevat een reeks aanbevolen constanten. In augustus 2007 toonden Dan Shumow en Niels Ferguson van Microsoft aan dat de constanten zo konden worden geconstrueerd dat er een kleptografische achterdeur in het algoritme werd gecreëerd . In september 2013 schreef The New York Times dat "de NSA een achterdeur had geplaatst in een door NIST aangenomen norm uit 2006, de Dual EC DRBG-norm genaamd", waarmee werd onthuld dat de NSA een malware-aanval uitvoerde op het Amerikaanse volk. In december 2013 meldde Reuters dat documenten die door Edward Snowden waren vrijgegeven, aangaven dat de NSA RSA Security $ 10 miljoen had betaald om Dual_EC_DRBG de standaard in hun coderingssoftware te maken, en verdere bezorgdheid geuit dat het algoritme een achterdeur voor de NSA zou kunnen bevatten. Vanwege deze zorgen heeft NIST in 2014 Dual EC DRBG ingetrokken uit zijn ontwerprichtlijnen voor generatoren van willekeurige getallen, en beval het "huidige gebruikers van Dual_EC_DRBG zo snel mogelijk over naar een van de drie resterende goedgekeurde algoritmen."

MIFARE Crypto-1

Crypto-1 is een cryptosysteem ontwikkeld door NXP voor gebruik op MIFARE- chips. Het systeem is eigendom en oorspronkelijk is het algoritme niet gepubliceerd. Na reverse-engineering van de chip, ontdekten onderzoekers van de Universiteit van Virginia en de Chaos Computer Club een aanval op Crypto-1 waarbij gebruik werd gemaakt van een slecht geïnitialiseerde generator voor willekeurige getallen.

Debian OpenSSL

In mei 2008 onthulde beveiligingsonderzoeker Luciano Bello zijn ontdekking dat wijzigingen die in 2006 zijn aangebracht aan de generator voor willekeurige getallen in de versie van het OpenSSL- pakket die wordt gedistribueerd met Debian Linux en andere op Debian gebaseerde distributies, zoals Ubuntu , de entropie van gegenereerde waarden drastisch hebben verminderd en maakte een verscheidenheid aan beveiligingssleutels kwetsbaar voor aanvallen. De zwakke plek in de beveiliging werd veroorzaakt door wijzigingen die door een Debian-ontwikkelaar in de openssl-code werden aangebracht als reactie op compilerwaarschuwingen van schijnbaar overbodige code. Dit veroorzaakte een massale wereldwijde regeneratie van sleutels, en ondanks alle aandacht die het probleem kreeg, kon worden aangenomen dat veel van deze oude sleutels nog steeds in gebruik zijn. Betrokken sleuteltypen zijn onder meer SSH- sleutels, OpenVPN- sleutels, DNSSEC- sleutels, sleutelmateriaal voor gebruik in X.509-certificaten en sessiesleutels die worden gebruikt in SSL/TLS- verbindingen. Sleutels die zijn gegenereerd met GnuPG of GNUTLS worden niet beïnvloed omdat deze programma's verschillende methoden gebruikten om willekeurige getallen te genereren. Sleutels die worden gegenereerd door niet-Debian-gebaseerde Linux-distributies worden ook niet beïnvloed. De kwetsbaarheid voor het genereren van zwakke sleutels werd onmiddellijk gepatcht nadat het was gemeld, maar alle services die nog steeds sleutels gebruiken die door de oude code zijn gegenereerd, blijven kwetsbaar. Een aantal softwarepakketten bevat nu controles op een zwarte lijst met zwakke sleutels om te proberen het gebruik van deze resterende zwakke sleutels te voorkomen, maar onderzoekers blijven zwakke sleutelimplementaties vinden.

PlayStation 3

In december 2010 kondigde een groep die zichzelf fail0verflow noemde het herstel aan van de privésleutel van het elliptic curve digital signature algorithm (ECDSA) die door Sony werd gebruikt om software voor de PlayStation 3 gameconsole te ondertekenen . De aanval werd mogelijk gemaakt omdat Sony er niet in slaagde voor elke handtekening een nieuwe willekeurige nonce te genereren .

RSA-factoring van openbare sleutels

Lenstra, Hughes, Augier, Bos, Kleinjung en Wachter hebben in 2012 een analyse aangekondigd waarin miljoenen openbare RSA- sleutels worden vergeleken die via internet zijn verzameld. Ze waren in staat om 0,2% van de sleutels te factoriseren met alleen het algoritme van Euclid . Ze maakten gebruik van een zwakte die uniek is voor cryptosystemen op basis van factorisatie van gehele getallen . Als n = pq één openbare sleutel is en n ′ = p ′ q ′ een andere is, dan is als toeval p = p ′ , een eenvoudige berekening van ggd( n , n ′) = p factoren zowel n als n ′, totaal beide sleutels in gevaar brengen. Nadia Heninger , onderdeel van een groep die een soortgelijk experiment deed, zei dat de slechte sleutels bijna volledig voorkwamen in embedded applicaties , en legt uit dat het one-shared-prime-probleem dat door de twee groepen werd ontdekt, het gevolg is van situaties waarin de pseudo-willekeurige nummergenerator slecht is. aanvankelijk gezaaid en vervolgens opnieuw ingezaaid tussen de generatie van de eerste en tweede priemgetallen.

Java nonce botsing

In augustus 2013 werd onthuld dat bugs in de Java- klasse SecureRandom botsingen kunnen veroorzaken in de k nonce-waarden die worden gebruikt voor ECDSA in implementaties van Bitcoin op Android . Toen dit gebeurde, kon de privésleutel worden teruggevonden, waardoor Bitcoins uit de portefeuille konden worden gestolen .

Zie ook

Referenties

Verder lezen