Brute force
Uit Wikipedia, de vrije encyclopedie
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 die sneller of efficiënter tot een oplossing leidt. De methode bestaat uit het botweg uitproberen van alle mogelijke opties, net zolang tot diegene gevonden is die overeenkomt met de gewenste invoer.
[bewerk] Kraken van wachtwoorden met brute force
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 wordt mogelijke combinaties van beschikbare tekens geprobeerd, 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 seconden) 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 is 36 verschillende karakters) en het wachtwoord is maximaal 6 posities lang. Dan duurt het circa 36^6/3000000=725.5 seconden voordat dit wachtwoord is geraden. Indien men uitgaat van de 95 (alle karakters op het toetsenbord) dan duurt het reeds 95^6/3000000=245030 seconden, wat overeenkomt met 68 uur. Indien men het wachtwoord 7 karakters lang maakt i.p.v. 6 karakters, duurt het inmiddels 17 jaar. Om deze reden is het raadzaam om wachtwoorden langer dan 6 karakters te gebruiken.
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/of -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 bijvoorbeeld al 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 dus een veel kleinere zoekruimte aanpakken met brute kracht, en daarmee redelijke kans op succes hebben.
De enige bestaande perfect veilige vercijfering die bestand is tegen een brute force-aanval of een andere cryptoanalytische aanval is Vernam's one-time-pad. Dit werd bewezen in Claude Shannon's verhandeling 'Communication theory of secrecy systems'. De correcte toepassing hiervan stelt de gebruiker echter voor enorme problemen op het gebied van sleutelbeheer.
[bewerk] Parallellisatie
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 één voor één 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 verdeelt 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.
