Nieuwe methode van ontbinden bedreigt encryptie?

Op Slashdot viel te lezen dat een wiskundige met de naam Daniel Bernstein een methode heeft gevonden om zeer grote getallen zeer veel sneller te factoriseren dan tot nu toe mogelijk was. Deze wiskundige beweert - door in plaats van één computer met zeer veel geheugen, veel computers met een beetje geheugen te gebruiken - niet linear, maar exponentieel sneller de factoren van een groot getal te kunnen berekenen, terwijl de kosten voor de benodigde hardware niet toenemen.

Met deze techniek zouden getallen met een factor drie groter dan nu het geval is gefactoriseerd kunnen worden. Als dit waar is zouden RSA sleutels van 2048 bits - op dit moment vrijwel onbreekbaar geacht - gefactoriseerd kunnen worden. Een markant detail is dat er veel geruchten de ronde gaan dat de NSA al jaren van deze methode op de hoogte was. Overigens wordt de veiligheid van symetrische sleutel cryptografie (DES, AES) niet door deze ontdekking aangetast:

"Now that this technique is known it explains how the spooks may be able to break crypto everyone else believed was "unbreakable" if they had previously made this discovery. Remember what happened with DES. The NSA said "make these changes. We can't tell you why." IBM made the changes. 20 years later, when differential cryptography was "discovered", it turned out those changes made it more resistant to differential cryptography..."

Verwijderd gooide dit nieuws in de nieuwssubmit. Bedankt

Reacties (43)

Roland684 4 maart 2002 02:11

Het werkt natuurlijk 2 kanten op, als een bericht al sneller gedecodeerd kan worden (eerst zien, dan geloven, die gast kan nog doodgaan en zijn methode mee het graf in nemen

) dan kan een bericht ook sneller ge-encodeerd worden, en dus kunnen we (veel) grotere keys gaan gebruiken.

Verwijderd @Roland684 • 4 maart 2002 07:58

Dat is niet altijd zo; sommige algoritmen laten zich net zo snel encoderen als decoderen, sommige doen er langer over om te encoderen dan te decoderen (anders is een DivX-filmpje kijken lang niet zo leuk meer

)

joker1977 @Roland684 • 4 maart 2002 08:06

Lijkt me nauwelijks van toepassing. Het maken van zo'n sleutel ging sowieso al vele vele malen sneller dan het factoriseren. Het maken van zo'n sleutel is een recht-toe-recht-aan-proces, terwijl het kraakproces nog steeds vrijwel een brute-force methode is.

Maar we kunnen eenvoudig grotere sleutels gebruiken, klopt. We moeten alleen 'onze' inschatting van 'hoe groot moet een vrijwel onkraakbare sleutel zijn' aanpassen.

max3D 3 maart 2002 22:12

Met recht opzienbarend nieuws! Als het waar is zou het koetjes project (RC-5) dat nog steeds graast naar een sleuteltje van 64 bits geheel achterhaald zijn.
Gek genoeg lijkt de methode van Bernstein zich overigens juist perfect te lenen voor een gedistribueerde aanpak. Een programma dat niet één super pc vereist, maar vele zwakkere met een relatief kleine memory footprint is ideaal voor voor een geheel vernieuwd koetjes project.

musiman

@max3D • 4 maart 2002 10:09

Het RC5-64 project is de meest primitieve manier van het sleutel kraken (ik doe hier overigens vrolijk aan mee:-) aangezien gewoon domweg alle sleutels geprobeerd worden (=brute force methode).
Wat al langer toegepast wordt is het op wiskundige wijze kraken van een code. Het voorbeeld van dit artkel is er hier weer 1 van.

Confusion 3 maart 2002 22:32

Als je goed doorleest, merk je dat dit resultaat slechts voor de limiet van zeer grote sleutels geldt. Het is heel goed mogelijk (merkt Bernstein zelf ergens op) dat het voor de huidige 1024/2048 bit sleutels geen enkel verschil maakt (of zelfs nadelig is).

Verwijderd @Confusion • 3 maart 2002 23:15

+3 (Interessant)

Of gewoon een betere c.q aandachtigere lezer dan de rest.

Rembert 4 maart 2002 17:10

Hmmm... het kan ook een totaal ander verhaal zijn. Voer voor de paranoiden onder ons:

Stel NSA en die Daniel Bernstein kunnen al jarenlang met deze techniek berichten decoderen maar dat mensen als Phil Zimmerman hier niet van op de hoogte zijn.

Resultaat: PGP en aanverwante proggies worden als veilig gewaand en veel gebruikt, kijk naar Al Qaeda - die schijnt het ook intensief gebruikt te hebben. Ondertussen kijken de NSA lekker mee met die informatie.

Ze kunnen niet met de gevonden informatie naar buiten treden. Immers, daarmee geven ze direkt toe dat ze de encryptie hebben doorbroken. Is niet tactisch, je kunt beter de vijand in de waan laten dat ze een perfecte encryptie gebruiken en ondertussen lekker meelezen.

Wat hebben ze dan aan die informatie? Eenvoudig, het zet de NSA op een spoor - vergelijk het met de anonieme tipgever. Via dat spoor komen ze 'toevallig' ook andere onderwerpen tegen en bouwen dan op een zodanige wijze hun bewijsvoering op dat de hele decoderings-geschiedenis kan worden vergeten.

Dat lijkt me helemaal geen ondenkbare situatie. Maar waarom dan ineens deze wijziging? Mogelijk is die Daniel Bernstein gewoon geniaal en heeft een nieuwe methode gevonde en deze meteen aan de grote klok gehangen. Kan.

Mogelijk dat de NSA via hun decryptie methodiek informatie heeft ontdekt waarbij ze op geen enkele manier kunnen verdoezelen dat ze onkraakbaar geachte data hebben gedecodeerd. Het is natuurlijk niet tactisch voor de NSA om zelf te vertellen dat ze dergelijk goed gecrypte code kunnen decoderen want daarmee zouden ze de vijand meteen ongelovelijk op scherp zetten. Dus dan maar een geniaal wiskundige inzettend die zich hier wel voor wil lenen.

Resultaat is dat de publicatie een feit wordt. Enige tijd later zal de NSA komen met informatie waar ze al enige tijd mee in hun maag zitten.

Ondertussen gaan terroristen en anderen die gecrypte communicatie hebben gevoerd, zich afvragen of NSA alle gecrypte documenten hebben onderschept en nu gaan decoderen. Vast wel...

Welkom in de Brave New World.

Verwijderd 3 maart 2002 22:16

Euh.. cpu kracht is toch belangrijker dan een hoeveelheid geheugen? Meer pc's is uiteindelijk meer cpu kracht. Of snap ik het nou niet?

Skinkie @Verwijderd • 3 maart 2002 22:25

misschien werkt het op basis van uitsplitsen van processen. Jouw proc kan nog steeds maar 1 proces doen.... welliswaar heel snel als je heel veel rekenkracht hebt. Maar als je een heleboel computers iets heel makkelijks laat doen, door die truck van hem dus... zou dat misschien het collosale verschil kunnen zijn.

Professor_Botje @Skinkie • 3 maart 2002 23:14

Dus als je nu DUAL CPU draaid heb je eigenlijk het zelfde...

als je dan de "echte" IBM servers ziet

512x P3 550Mhz XEON CPU's hebt met 2mb L2 cash en 64Gb ram denk ik dat als je 512
losse P3 550 Xeons met 2Mb pakt toch echt slomer is dan de eerste config...

Simpel anders moet je ook 512x Win2k Advanced server Bv. draaien...

512x!!! anders maar 1keer en je hebt 512 instrukties die hij kan bewerken tegelijkertijd...

goalgetter @Professor_Botje • 4 maart 2002 02:42

Ik denk dat je je daarin nog wel enorm kan vergissen.

Bij systemen met een dergelijk groot aantal processoren komen ook hele andere factoren om de hoek kijken waar je bij simpele dual/quad processor systemen geen problemen mee hebt. Om maar een voorbeeldje te noemen, alle cpu's van data voorzien, de verdeling van geheugen over de cpu's. De overhead zou op een bepaald moment een dusdanig grote component van de processorkracht kunnen gaan vormen dat het toevoegen van processoren het geheel alleen maar trager maakt.
Ik zeg niet dat dit per definitie zo is voor het genoemde voorbeeld, maar ik wil je er wel even op wijzen dat brute specs niet alles zeggend zijn.

Verwijderd @Professor_Botje • 4 maart 2002 15:29

Dus als je nu DUAL CPU draaid heb je eigenlijk het zelfde...

als je dan de "echte" IBM servers ziet

512x P3 550Mhz XEON CPU's hebt met 2mb L2 cash en 64Gb ram denk ik dat als je 512
losse P3 550 Xeons met 2Mb pakt toch echt slomer is dan de eerste config...

Simpel anders moet je ook 512x Win2k Advanced server Bv. draaien...

512x!!! anders maar 1keer en je hebt 512 instrukties die hij kan bewerken tegelijkertijd...

Zal niet lukken met w2k advanced server, daar kan je er maar 16 (of 32) mee aansturen.

Met datacenter kom je er wel, 512 cpu's.

.oisyn Moderator Devschuur® @Verwijderd • 4 maart 2002 01:45

De huidige methode heeft een gigantische hoeveelheid geheugen nodig om grote getallen te factorizeren. In de Factoring Challenge FAQ van RSA Laboratories staat een klein tabelletje met hoeveel machines (vergelijkbaar met een pentium 500) en geheugen er nodig zijn voor het factorizeren van sleutels met verschillende lengtes in 1 jaar als je de huidige methode gebruikt:

Bits in de sleutel______# machines______geheugen
___430______________________1_________weinig
___760_________________215000_________4GB
__1020______________342000000_______170GB
__1620______________1.6 * 10^15_______120TB

het geheugenaantal is dus per machine, en niet totaal

Verwijderd @Verwijderd • 3 maart 2002 22:32

Ja idd, enkel moet je als je aan het 'rekenen' bent ook dingen in je geheugen opslaan en daarvoor is veel geheugen nodig vooral bij het trachten te kraken van code moet je heel veel onthouden.
Dus je moet genoeg geheugen hebben om alle 'tussen' berekeningen te onthouden en CPU power is nog even belangerijk voor het snel uitvoeren van het kraken enkel zonder genoeg geheugen dus veel geheugen kun je alles niet opslaan dus gebruik je niet alle power!

SH007 3 maart 2002 22:03

het zou niet best zijn als dit zou werken, dan moeten er nieuwe enctypie methoden bedacht worden.

Verwijderd @SH007 • 3 maart 2002 22:25

Nee hoor, alleen langere codeersleutels.

Verwijderd @SH007 • 4 maart 2002 12:27

Als er bedrijven zijn die hier allang van op de hoogte waren, dan zijn vast ook wel technieken om het betere te encrypten

Dj Neo Ziggy 3 maart 2002 23:57

Is dit niet wat wij nu ook al doen! met je

.oisyn Moderator Devschuur® @Dj Neo Ziggy • 4 maart 2002 01:55

nee

De RC5-64 contest van distributed.net heeft niets met het factorizeren van sleutels te maken. Bovendien is de methode van distributed.net brute force, dwz dat ze simpelweg alle mogelijkheden proberen tot de goeie is gevonden

En het factorizeren van sleutels is ook wel brute force te doen, maar dat kost echt veel teveel tijd (denk aan iets dat velen malen langer duurt dan de leeftijd van het universum

)

bille @Dj Neo Ziggy • 4 maart 2002 00:16

hm jah lijkt er wel op..eigelijk wel een beetje weird dat dit nu wordt gezegd want et was toch al wel eerder duidelijk dat als je 100.000 computers gebruik dat altijd sneller is dan één supercomputer... wat dat betreft is er geen zupah bakkie die tegen alle

van NL kan.. alleen zoals je in de progressbar kan zien op distributed gaat et niet echt snel ofzo.. uiteindelijk wordt de key wel gekraakt.. maar of je dat écht gekraakt kan noemen..tis eigelijk net zoiets als een titanuimslot met een nagelvijl doorvijlen

-=marauder=- @bille • 4 maart 2002 01:15

titanium is helemaal niet zo hard hoor dus als je een beetje een goeie nagelvijl hebt kom je wel een heel end gok ik.

Verwijderd 3 maart 2002 22:15

hmm, hier wil ik wel meer over horen, lijkt me sterk dat ze daar niet eerder aan zouden gedacht hebben.

T.T. @Verwijderd • 3 maart 2002 22:22

gewoon zijn paper lezen, is best te doen. Ik zit nu op pagina 5

Skinkie @T.T. • 3 maart 2002 22:25

Is dat te openen met Ghostviewer? Of waaranders mee?

Ashe @Skinkie • 4 maart 2002 02:26

Jep, gezien het een PostScript file is kan je het openen met Ghostview.

Voor hen die het nog niet kennen of hebben, je kan het downloaden op http://www.cs.wisc.edu/~ghost/

Skinkie 3 maart 2002 22:13

De 3-8-6 en de 4-8-6 kommen weer helemaal terug

dalijk wil iedereen mijn 486 afpakken...

Ik bescherm je liefie

jij mag lekker blijven serveren voor Stefan

Nee alles goed en aardig, wiskunde blijft oplosbaar en als je de regels goed gebruikt kan iets wat heel moeilijk lijkt, door een algoritme makkelijk oplosbaar zijn.

Met koude kernfusie, zie fok! wordt de wereld in 1 dag toch een stuk beter. Opeens gaat iedereen meehelpen aan nuttige dingen vaccins ontwikkelen voor ziekten bevoorbeeld, want als die RC• binnen een aantal dagen gekraakt is, dan is lang en breed bewezen dat het te kraken is.

T.T. @Skinkie • 3 maart 2002 22:28

Dat van die koude kernfusie moet ik nog zien, er zijn al genoeg wetenschappers geweest die hetzelfde beweerden en het fout hadden.

wiskunde blijft oplosbaar

Je kunt met wiskunde ook bewijzen dat sommige dingen onoplosbaar zijn! Ik weet niet precies wat je probeert te zeggen, maar ik denk dat je het iets te simplistisch probeert voor te stellen