Brute kracht

Van Wikipedia

Op Bruteforce staat tekst die in dit artikel ingevoegd zou moeten worden. Daarna kan dát artikel een redirect worden. (Hier melden: Overleg).

Brute kracht, of in het Engels brute force, 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.

[bewerk] Cryptografie

Wanneer je bijvoorbeeld een RSA-sleutel probeert te kraken zou je er gebruik van hebben kunnen maken dat het een product van twee priemgetallen is. Dat is echter niet wat een brute-kracht aanval doet, die doorloopt in principe de hele ruimte aan mogelijke sleutels. Voor slimmere technieken is het van belang dat een sleutel niet te veel interne structuur heeft, maar voor kraken met brute kracht moeten er gewoon 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. Voor de 56 bits van een DES sleutel is dat bijvoorbeeld al praktisch haalbaar, voor een AES sleutel van 128 bits niet. Merk overigens op dat het algoritme er niet toe doet vanwege de aard van brute kracht, behalve dat een algoritme doorgaans grenzen stelt aan het aantal bits dat een sleutel kan bevatten.

Vaak zal een aanval gebruikmaken van een combinatie van slimme trucs die de zoekruimte inperken en een aanval in brute kracht 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, bestand tegen een brute force attack of eender welke 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] Werken met brute kracht

Een handige aanpak voor een kraak met brute kracht is een parallelle machine die de taak verdeelt over zo veel mogelijk afzonderlijk operererende rekencellen. 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.