scrypt

Niet te verwarren met: Script

In de cryptografie is scrypt (dat met een kleine letter wordt geschreven) een algoritmische functie om cryptografische sleutels te genereren uit gebruikerswachtwoorden. Deze scrypt functie is ontwikkeld door Colin Percival, die het aanvankelijk maakte voor Tarsnap, een online back-up service.

Achtergrond

Het algoritme is speciaal ontworpen om grootschalige aanvallen op gegevens met speciale hardware en veel rekenkracht erg kostbaar te maken, doordat er dan zeer veel geheugen nodig is voor zo'n aanval. In 2012 werd het scryptalgoritme gepubliceerd door de IETF als een Internet Draft, en was op weg om een Request for Comments over informatietechnologie te worden. Het wordt gebruikt als een 'proof-of-work'-methode voor mining van Litecoin en Novacoin.

Werking

Een op wachtwoorden gebaseerde KDF (key derivation function) is bewust zo ontworpen dat aanvallen om een cryptografische sleutel uit een wachtwoord af te leiden, een hoge complexiteitsgraad vergen, qua geheugen en/of rekenkracht. Toegestane gebruikers hoeven de functie per bewerking maar een keer te gebruiken (bijvoorbeeld bij authenticatie of inloggen) en dan is deze tijd verwaarloosbaar. Als iemand echter het wachtwoord wil 'raden' met brute force dan moet de bewerking door de functie miljarden keren gebruikt worden, waardoor de aanvalstijd enorm toeneemt. Idealiter wordt voorkomen dat het oorspronkelijke wachtwoord achterhaald wordt.

Voordat scrypt er was waren er al op wachtwoorden gebaseerde KDF's zoals de populaire PBKDF2 van RSA Security), die relatief weinig resources of geheugen verbruiken en goedkoop in hardware te implementeren waren (zoals in een ASIC of zelfs een FPGA). Dit zorgde ervoor dat een aanvaller met voldoende middelen een grootschalige parallelle aanval kon plegen door honderden of duizenden implementaties van het algoritme in hardware te gieten, en elk algoritme te laten zoeken naar een verschillende subset van de sleutelcode. Dit reduceert de tijd die nodig is om een succesvolle brute force aanval te plegen tot een heel aanvaardbare tijdsspanne voor de hacker.

De scryptfunctie is ontworpen om zulke grootschalige aanvallen te verhinderen, door de resourcedruk van het algoritme bewust heel hoog te maken. Het scrypt-algoritme is dus ontworpen om grote hoeveelheden geheugen te moeten gebruiken in vergelijking met andere op wachtwoord gebaseerde KDF's. Dit maakt de grootte en kosten van hardware-implementatie wel duurder en beperkt daardoor de hoeveelheid van mogelijke parallelle aanvallen die een aanvaller kan gebruiken (ook omdat de hardware die een aanvaller moet gebruiken daardoor veel duurder wordt) om toegang te krijgen tot de versleutelde gegevens.

Overzicht

Het grote beroep dat scrypt doet op het geheugen komt voort uit een grote vector van pseudowillekeurige bitstrings die gegenereerd worden als deel van het algoritme. Zodra de vector is gegenereerd worden de elementen daarin in een pseudowillekeurige volgorde benaderd en gecombineerd om de afgeleide sleutel te produceren. Een rechttoe rechtaan implementatie zou steeds de hele vector in het RAM-geheugen moeten houden zodat de data benaderd kunnen worden indien nodig.

Omdat de elementen van de vector door een algoritme worden gegenereerd, zou elk individueel element terstond gegenereerd kunnen worden wanneer het benodigd is, zodat er steeds maar 1 element tegelijk in het geheugen hoeft te zijn, en waardoor het beroep op het geheugen veel kleiner zou zijn. Maar er is bewust voor gekozen om de generatie van zelfs 1 element lastig te maken qua rekenkracht en geheugengebruik, en de losse elementen worden ook nog eens elk vele keren benaderd in het hele proces. Dit vertraagt het proces bewust en aanzienlijk. Er is dus een verband tussen snelheid en geheugengebruik dat benut wordt.

Zo'n verband bestaat vaker in computeralgoritmes: men kan de snelheid verhogen ten koste van meer geheugengebruik, of het geheugengebruik kleiner maken ten koste van andere bewerkingen, waardoor iets langer duurt. Het concept van scrypt maakt bewust elke van deze twee mogelijkheden kostbaar voor een aanvaller, hetzij doordat het veel geheugen kost, hetzij doordat het lang duurt. Zo kan een aanvaller een programma gebruiken dat weinig resources kost, maar dat loopt dan heel langzaam, of de aanvaller kiest dure en snellere hardware, dan vergt het algoritme ineens veel meer geheugen, en wordt parallel aanvallen plotseling veel duurder.

Zie ook

• SHA-familie
• Bitcoin
• Cryptogeld

Externe links

• (en) De scrypt pagina op de Tarsnap website
• (en) Het originele scrypt document
• (en) C# implementatie
• (en) Java implementatie
• (en) PHP implementatie
• (en) Ruby implementatie