Brute force (methode)

Brute force (Engels voor "brute kracht") is het gebruik van rekenkracht om een probleem op te lossen met een computer zonder gebruik te maken van algoritmen of heuristieken om de berekening te versnellen. Brute force wordt gebruikt als er geen algoritme bekend is dat sneller of efficiënter tot een oplossing leidt. De methode bestaat uit het botweg uitproberen van alle mogelijke opties, net zo lang tot er een gevonden is die overeenkomt met de gewenste invoer.

Brute force wordt vaak gebruikt voor het kraken van wachtwoorden of achterhalen van verloren gegane of vergeten wachtwoorden die versleuteld zijn met sterke encryptie. Hierbij worden alle mogelijke combinaties van beschikbare tekens geprobeerd. Dit is een zeer inefficiënte methode door de zeer lange duur, maar 100% trefzeker.

De formule voor de schatting van de maximumtijd om een wachtwoord te vinden (gebaseerd op drie miljoen wachtwoorden per seconde) is:

seconden = karakters^posities/3000000

Voorbeeld: We hebben de mogelijkheid om in een wachtwoord alleen cijfers en alle kleine letters van het alfabet te gebruiken (dus 26 + 10 = 36 verschillende karakters) en het wachtwoord is maximaal 6 posities lang. Dan duurt het circa 36⁶/3000000 = 725,6 seconden voordat dit wachtwoord is geraden. Indien men uitgaat van de 95 (alle karakters op het toetsenbord) dan duurt het reeds 95⁶/3000000 = 245031 seconden, wat overeenkomt met 68 uur. Indien men het wachtwoord 7 karakters lang maakt in plaats van 6, duurt het inmiddels 95⁷/3000000 = 23277910 seconden, wat overeenkomt met 269 dagen. Om deze reden is het raadzaam om lange wachtwoorden te gebruiken. In de praktijk is de gemiddelde zoektijd naar een juist wachtwoord meestal binnen de helft van een doorlopen zoekruimte: de bovenstaande formule kan men het aantal karakters^posities delen door 2 voor een benadering van de gemiddelde zoektijd.

Voor het kraken met brute force moeten er niet te veel mogelijke sleutels zijn. Wanneer het aantal mogelijke cryptografische sleutels extreem hoog is, moet ook extreem veel worden geïnvesteerd in rekenkracht en -tijd om een sleutel te kraken. Een RSA-sleutel bestaat uit het product van twee priemgetallen en is daarom zeer moeilijk te kraken met gebruik van brute force. Voor de 56 bits van een DES sleutel is dat praktisch haalbaar, voor een AES sleutel van 128 bits niet.

Vaak zal een aanval gebruikmaken van een combinatie van slimme trucs die de zoekruimte inperken en een aanval in brute force op datgene wat overblijft. Daarom moeten sleutels voor asymmetrische encryptie ook langer zijn dan die voor symmetrische encryptie om een vergelijkbaar veiligheidsniveau te bereiken – er is meer informatie aanwezig die structuur kan helpen achterhalen. Het is ook om deze reden, dat het aanmaken van sleutels met grote zorgvuldigheid dient te gebeuren, ofwel dat de entropie van sleutelmateriaal zo hoog mogelijk moet zijn. Als een symmetrische sleutel 112 bits inneemt, maar door interne structuur slechts voor 40 bits aan verrassing bevat, dan kan een kraker die daar weet van heeft, een veel kleinere zoekruimte aanpakken met brute kracht en daarmee de slaagkans verhogen.

De enige bestaande perfect veilige vercijfering die bestand is tegen een bruteforce-aanval of een andere cryptoanalytische aanval is Vernams one-time-pad. Dit werd bewezen in Claude Shannons verhandeling 'Communication theory of secrecy systems'. De correcte toepassing hiervan stelt de gebruiker echter voor enorme problemen op het gebied van sleutelbeheer.

Een voorbeeld waarbij dit gebruikt wordt is om MD5-hashes te achterhalen. Stel we hebben een wachtwoord als md5-hash opgeslagen: 900150983cd24fb0d6963f7d28e17f72
Dan zal bij een bruteforce attack het kraakprogramma alle mogelijkheden afgaan:
a = 0cc175b9c0f1b6a831c399e269772661
b = 92eb5ffee6ae2fec3ad71c777531578f
...
aa = 4124bc0a9335c27f086f24ba207a4912
ab = 187ef4436122d1cc2f40dc2b92f0eba0
..
En uiteindelijk zal het bij de goede komen:
abc = 900150983cd24fb0d6963f7d28e17f72

Merk op dat Abc een andere uitkomst geeft dan abc, en dat dit dus alweer tientallen extra pogingen vereist.
Wachtwoorden zouden als het goed is altijd opgeslagen moeten staan als hash. Dit is in Windows zo, en bij de meeste webdiensten. Hierdoor is het wachtwoord nooit meer zomaar terug te halen, maar wel te resetten (de opgeslagen hash overschrijven). Dit voorkomt dat als de database ooit gehackt zou worden, alle wachtwoorden meteen te zien en te gebruiken zijn.

Bruteforce-aanvallen zijn niet alleen van toepassing op MD5-hashes. Ook NTLM-hashes (gebruikt om een Windows-wachtwoord op te slaan) kunnen via deze methode gedecodeerd worden. Deze techniek heet ook wel 'reverse engineering'.

Als de aanvaller de hash niet bezit kan deze ook gewoon een script schrijven dat in een loginscherm alle mogelijkheden uitprobeert. Een hash zal normaal de voorkeur hebben aangezien die het programma niet nodig heeft, het programma zou namelijk restricties aan het aantal loginpogingen per minuut of per uur kunnen opleggen. Ook zal het programma iedere poging het scherm minimaal een keer verversen, wat ook weer tijd kost. Dit lijkt nihil, maar zelfs 3 milliseconden maken een gigantisch verschil als er bijvoorbeeld 3 miljoen pogingen vereist zijn om het wachtwoord te raden.

Via internet is nog langzamer, zeer vaak zijn er een bepaald aantal loginpogingen mogelijk voor een captcha ingevuld moet worden of men moet een aantal seconden wachten tussen de pogingen. Zelfs als deze restricties niet aanwezig zijn, duurt het vaak nog 20-200 milliseconden voor een enkele poging.

Stel we hebben een wachtwoord Za113, en we weten dat er alleen alfanumerieke karakters in het wachtwoord voorkomen, dan zal het iets minder dan 916000000 pogingen vereisen het wachtwoord te kraken. Ditmaal, in het allerbeste geval, 15 milliseconden is al een behoorlijke tijd.

MD5-hashes kunnen met de juiste software en een goede computer met een snelheid van 500 miljoen pogingen per seconde geprobeerd worden. Als deze als MD5 opgeslagen zou staan in een database, en deze database zou gehackt worden, zou het wachtwoord dus slechts 2 seconden nodig hebben om te kraken.

Om brute force-methodes te doen versnellen gebruiken programmeurs een techniek genaamd parallellisatie. Een parallelle machine verdeelt de taak over zo veel mogelijk afzonderlijk operererende rekencellen. In plaats van een voor een de mogelijkheden te proberen, kunnen meerdere processoren dan wel systemen meerdere mogelijkheden tegelijkertijd uitproberen. Dit kan relatief eenvoudig gedaan worden door het probleem in stukken op te splitsen en aan verschillende systemen/processoren toe te wijzen. Zo kan men theoretisch bij het kraken van een wachtwoord van bijvoorbeeld 7 posities met een systeem met 4 processoren (SMP-systeem) de tijd van 17 jaar terugbrengen naar iets meer dan 17/4=4,25 jaar.

De methoden daarbij kunnen verschillen — het is mogelijk het werk tussen de cellen te coördineren om dubbelwerk te voorkomen (vergelijkbaar met de aanpak van het SETI-project) of het is mogelijk om elke cel willekeurige pogingen te laten wagen (zoals in een Chinese Loterij). In het laatste geval valt de te verwachten rekenklus tweemaal zo hoog uit, maar wel zonder enige vorm van overhead in het aansturen van de rekencellen.

Door het gebruik van parallellisatie komt extra rekenkracht om de hoek kijken doordat gegevens moeten worden opgesplitst en verdeeld en er onderlinge communicatie tussen de verschillende processen (programma's dan wel threads) plaats moet vinden. De rekenkracht moet dus opwegen tegen de complexiteit dan wel duur van het te behalen resultaat.

Zorg altijd dat er restricties gesteld worden aan het aantal loginpogingen per uur en per minuut. Bijvoorbeeld hooguit 45 per minuut, met een maximum van 150 per uur.

Bij hashes (MD5, SHA1, NTLM, enzovoorts), gebruik altijd een salt. Een salt, of zout in het Nederlands, vertroebelt de hash.

Als crackers of hackers de hash kennen van een aantal veelgebruikte wachtwoorden, en ze krijgen toegang tot een lijst met hashes, dan kunnen ze heel gemakkelijk de gebruikers met die veelgebruikte wachtwoorden er uit halen. Met een salt zal men voor elke gebruiker een willekeurige salt bijhouden, en deze samenvoegen met zijn of haar wachtwoord om de hash te berekenen. Hierdoor krijgen gebruikers met eenzelfde wachtwoord toch een andere hash.

Het werkt zo:
Even ervan uitgaand dat functies zo werken: uitkomst = functie ( variabele ), zou een md5-functie er zo uit kunnen zien:
hash = md5 ( "abc" )
De uitkomst van md5("abc") is dan dus 900150983cd24fb0d6963f7d28e17f72. We zouden de salt op deze manier toe kunnen passen:
variable salt = "am1MAi1mDA*1msA__"
hash = md5 ( salt + "abc" )
Dit zal de complexiteitsfactor van O(26³) verhogen naar de complexiteitsfactor O(95²⁰). Ofwel, het verschil tussen 17576 pogingen en ~3584859200000000000000000000000000000000 pogingen.
Waarom het grondgetal van 26 naar 95, en de macht van 3 naar 20?
Het grondgetal stelde de 26 letters van het alfabet voor. Er komen in het wachtwoord abc geen hoofdletters, cijfers of tekens voor, dus zijn er maar 26 mogelijkheden. Maar als er ook tekens in zitten wordt het opeens 95 karakters: 26 (kleine letters) + 26 (hoofdletters) + 10 (cijfers) + ~!@#$%^&*()_+-=[]\|}{;:<>?,./"'` (inclusief de laatste spatie) = 95.
Dan de macht van 3 naar 20, dit is de lengte van de gehashte tekenreeks. Eerst berekenden we de hash van abc (3 tekens), en met de salt berekenden we de hash van am1MAi1mDA*1msA__abc (20 tekens).

Een nog sterkere hash kan bereikt worden door de hash-functie meerdere malen uit te voeren op dezelfde tekenreeks. We gaan weer uit van dezelfde functiestructuur:
variabele salt = "am1MAi1mDA*1msA__"
hash = md5 ( salt + "abc" ) - in de variabele hash staat nu "d39faeb254034fdf0503bd33c6f509d9" - hash = md5 ( hash ) - in de variabele hash staat nu "1ee5ce0c0ee2c7efe89af6f96c1f15df", ofwel md5( "d39faeb254034fdf0503bd33c6f509d9" ) -
Hierdoor zal een kraker dus eerst de tekst achter 1ee5ce0c0ee2c7efe89af6f96c1f15df moeten achterhalen, en vervolgens de tekst achter d39faeb254034fdf0503bd33c6f509d9 om bij het originele wachtwoord te komen.

Opmerking: niet alle hash-functies zijn veilig. Soms kunnen er collisions voorkomen, dit is als twee tekenreeksen dezelfde hash-uitkomst geven. Bijvoorbeeld (fictief voorbeeld) zou het kunnen zijn dat "nads91" dezelfde md5-uitkomst geeft als "m19d00amms". Verouderde NTLM-hashes hebben ook een zwakte met lengte, maar dit is in nieuwere versies van Windows opgelost door een dubbele hash toe te passen. De kwetsbaarheid van korte hashes is zeer verminderde maten aanwezig met SHA1, maar deze techniek is langzamer, heeft een grotere uitkomst (24bits extra) en wordt minder ondersteund door verschillende software. Echter, zowel MD5 als SHA1 zijn tegenwoordig simpelweg te onveilig, en zijn zelfs met een salt zeer gemakkelijk te brute forcen^[1].
Daarnaast, als er te veel bewerkingen worden uitgevoerd met een tekenreeks is het mogelijk dat een andere tekenreeks dus eenzelfde uitkomst geeft (ofwel een collision veroorzaakt). Weer een fictief voorbeeld: abc zou dezelfde uitkomst kunnen genereren als salt+"abc"+salt. De kans is ontzettend klein, maar wel aanwezig.

Een andere methodiek die ter bemoeilijking van brute force-aanvallen kan worden ingezet, is het oprekken van een wachtwoord. Het oprekken van wachtwoorden werkt door versleuteling van wachtwoorden met een sterker salt-algoritme. Deze techniek noemen we key stretching. Voor het controleren van juistheid van een opgerekt wachtwoord moeten, afhankelijk van de gebruikte salt, minimaal een paar duizend rekenkundige operaties worden uitgevoerd. Deze ingebrachte complexiteit voor het controleren van een opgerekt wachtwoord werkt als een vertragende factor tijdens een brute force-aanval.

Key stretching kan ook enige bescherming bieden tegen het gebruik van brute force tegen aanvankelijk zwak gekozen wachtwoorden, omdat het vooraf laten berekenen en vastleggen van alle mogelijke hashes van wachtwoorden in sommige gevallen haast een onmogelijke taak is (zoals het samenstellen van rainbow tables). Bij gebruik van een 512-bits-salt zijn er bijvoorbeeld 2⁵¹² mogelijkheden voor ieder wachtwoord.

• British Museum-algoritme
• Rainbow table