A Novel Memory-Efficient MitM Attack on Ascon-Hash

In de digitale wereld rust beveiliging vaak op een delicaat evenwicht tussen kracht en efficiëntie. Voor de miljarden kleine, batterijgestuurde apparaten die de Internet of Things vormen — sensoren in fabrieken, slimme meters en medische monitoren — is rekenkracht schaars, en geheugen zelfs nog schaarser. Deze apparaten hebben cryptografische hulpmiddelen nodig die robuust genoeg zijn om gegevens veilig te houden, maar licht genoeg om te draaien zonder een batterij leeg te trekken of een piepkleine chip te vullen. Ascon is een toonaangevende oplossing voor deze uitdaging, een familie van encryptie- en hashingmethoden die specifiek zijn ontworpen voor deze hulpbron-beperkte omgevingen. Om ervoor te zorgen dat Ascon veilig blijft, testen onderzoekers het constant tegen geavanceerde aanvallen, waarbij ze proberen de kortste weg te vinden om de code te breken. Een van de krachtigste instrumenten in dit arsenaal is de "meet-in-the-middle"-aanval, een strategie waarbij een aanvaller achteruit werkt vanaf het eindresultaat en vooruit vanaf het startpunt, in de hoop in het midden een match te vinden. Deze strategie vereiste echter traditioneel een enorme hoeveelheid geheugen om de miljoenen tussenstappen op te slaan, een vereiste die de aanval vaak onpraktisch maakte voor de zeer specifieke apparaten die Ascon juist moet beschermen.

Een team van onderzoekers heeft nu een nieuwe manier ontwikkeld om deze aanval uit te voeren die de benodigde hoeveelheid geheugen drastisch vermindert, waardoor de test veel realistischer wordt voor lichte systemen. In een studie gericht op de Ascon-Hash functie, toonden de auteurs aan dat ze de aanval op een gereduceerde versie van het systeem konden uitvoeren met aanzienlijk minder opslagruimte dan voorheen mogelijk werd geacht, zonder de snelheid van de berekening op te offeren. Door het probleem te behandelen als een complexe puzzel van logische beperkingen, vonden ze een manier om overtollige gegevens te filteren voordat ze überhaupt opgeslagen hoefden te worden. Hun werk laat zien dat voor een drie-ronde versie van de hash, de benodigde hoeveelheid geheugen kan worden verminderd van een complexiteit van 2^24 naar 2^14. Voor een vier-ronde versie is de reductie zelfs nog dramatischer, waarbij de vereiste daalt van een complexiteit van 2^34 naar 2^12. Deze prestatie verlaagt niet alleen de kosten van de aanval; het geeft een scherper, nauwkeuriger beeld van hoe veilig Ascon werkelijk is wanneer het wordt geconfronteerd met een tegenstander met beperkte middelen.

De onderzoekers begonnen door te erkennen dat eerdere pogingen om Ascon te breken met geautomatiseerde zoektools tegen een muur van geheugengebruik aanliepen. Hoewel computers sneller waren geworden in het vinden van het juiste pad door de encryptie, vereiste het proces nog steeds dat de aanvaller een enorme bibliotheek van tussenresultaten in het geheugen hield, vergelijkbaar met het proberen op te lossen van een doolhof door elke enkele draai die je neemt op een apart stuk papier op te schrijven. Als het doolhof groot genoeg is, ben je aan papier verloren voordat je de uitgang vindt. Het team realiseerde zich dat de sleutel tot het oplossen hiervan niet alleen het sneller vinden van het pad was, maar slimmer zijn over wat ze opschreven. Ze gebruikten een methode genaamd satisfiability solving, wat in essentie een manier is om een computer te vragen om een set condities te vinden die een complexe logische stelling waar maakt. Dit stelde hen in staat om de specifieke punten in het encryptieproces in kaart te brengen waar de voorwaartse en achterwaartse berekeningen potentieel konden samenkomen.

Zoduiten ze deze potentiële ontmoetingspunten in kaart hadden gebracht, pasten de onderzoekers een reeks algebraïsche filters toe om de gegevens op te schonen. Ze merkten op dat veel van de beperkingen die de encryptie beheersen, konden worden gescheiden in eenvoudige, lineaire relaties en complexere, niet-lineaire relaties. De lineaire delen waren rechttoe rechtaan; ze konden worden vereenvoudigd met standaard wiskundige technieken om overbodige informatie te verwijderen, waardoor de lijst met mogelijkheden die de computer moest bijhouden effectief werd verkleind. De niet-lineaire delen waren lastiger, maar het team ontwikkelde een methode om ze in een driehoekige vorm te herschikken, waardoor ze bepaalde variabelen konden oplossen op basis van andere variabelen. Dit proces elimineerde de noodzaak om die specifieke variabelen expliciet te berekenen en op te slaan, wat de geheugenvoetafdruk verder verkleinde.

De meest significante innovatie kwam in de manier waarop ze de resterende complexe beperkingen afhandelden die niet gemakkelijk vereenvoudigd konden worden. In plaats van elke mogelijke uitkomst op te slaan, gebruikten de onderzoekers deze resterende beperkingen om een "residuele index" te creëren, een soort digitale tag of label. Terwijl ze de lijst met potentiële voorwaartse paden genereerden, voegden ze aan elk pad een tag toe op basis van hun specifieke eigenschappen. Cruciaal was hun besef dat het achterwaartse pad alleen kon matchen met een voorwaarts pad als hun tags compatibel waren. Dit betekende dat de computer niet elk mogelijk voorwaarts pad in het geheugen hoefde te houden; het hoefde alleen de paden te bewaren die een tag droegen die het achterwaartse pad mogelijk kon bereiken. In de specifieke configuraties die zij testten, was deze filtering zo effectief dat het de gehele lijst van noodzakelijke voorwaartse paden reduceerde tot een enkele, minuscule bak met gegevens.

De resultaten van deze nieuwe aanpak waren opmerkelijk. Wanneer toegepast op een drie-ronde versie van Ascon-Hash, behield de methode dezelfde snelheid als eerdere aanvallen, maar verminderde het de geheugenvereiste van een complexiteit van 2^24 naar 2^14. Voor de vier-ronde versie was de reductie nog diepgaander, waarbij de geheugenbehoefte van een complexiteit van 2^34 naar 2^12 daalde vergeleken met de vorige beste methode. De onderzoekers verifieerden dat deze agressieve filtering niet per ongeluk geldige oplossingen weggooide; ze controleerden of de resterende gegevens nog steeds aan de oorspronkelijke regels van het encryptiesysteem voldeden. De studie bevestigt dat het, door de structuur van de encryptie zorgvuldig te analyseren en deze logische filters toe te passen, mogelijk is om diepe beveiligingstests uit te voeren met een fractie van de middelen die voorheen nodig werden geacht. Dit werk suggereert dat de beveiligingsmarge van Ascon in hulpbron-beperkte omgevingen met grotere precisie wordt geëvalueerd, wat ervoor zorgt dat de cryptografische standaarden die onze verbonden wereld beschermen, zo robuust zijn als ze lijken.