hoe rekent de koe? (ik kan het vast slimmer)

[irrelevant]

Uit het DPC stukje op t.net:<BLOCKQUOTE><font size=1 face=Verdana, Arial, Helvetica>quote:</font><HR>Dat gebeurt middels de brute-force methode waarbij bruutweg alle 2^64 sleutels worden uitgeprobeerd[/quote]Beetje onduidelijk. Van wat ik weet van cryptografie (heb zelf een 512-bits versleutelaar ontworpen) probeer je meestal een sleutel te ontbinden in factoren. Is dit ook wat DPC probeert te doen of zit ik er nu helemaal naast?

Bij het ontbinden van een 64-bits getal in factoren weet je dat de kleinste factor ten hoogste wortel(x) is, met x de 64-bits sleutel. Immers, als x=y*z en y*z zijn beide groter dan wortel(x), dan is y*z>x. Je zoekt dus de kleinste factor vanaf wortel(x) omlaag.
Maar dat moet je natuurlijk niet gaan doen door elk getal kleiner dan wortel(x) te gaan delen op x en kijken of de rest 0 is. Dat kost enorm veel rekenkracht. Is dit wat DPC doet want dan kan ik het op de volgende manier veel sneller:

Voorbeeld:
1.000.000 = 1000*1000 ( 1000 = wortel(1.000.000)
1.000.000 = 999*1000+1000 = 999*1000+999+1 = 999*1001+1. Rest 1 dus 999 geen deler van 1.000.000
1.000.000 = 998*1001+1+1001 = 998*1001+998+4 = 998*1002+4. Rest 4 dus 998 geen deler van 1.000.000
1.000.000 = 997*1002+4+1002 = 997*1002+997+9 = 997*1003+9. Rest 9 dus 997 geen deler van 1.000.000
Enz...

Mijn punt is dat je kunt volstaan met hele simpele en snelle operaties ipv een hele deling uit te voeren.
(Het voorbeeld was kunstmatig omdat ik begon bij twee factoren die ik al wist, 1000*1000, maar het uitrekenen van een echte quotient en rest van floor(wortel(x)) hoeft maar eenmalig dus is niet erg als het een paar seconde kost)
Verder heb ik uit mijn werk aan cryptografie geleerd dat er vast nog veel slimmere rekenmethodes zijn als je wat literatuuronderzoek doet, want deze heb ik zelf maar uit mijn duim gezogen. Het kan dus nog veel sneller.
En dat is ook logisch want ze zijn er al in geslaagd een 512 bits sleutel te kraken. Ga even na dat een sleutel van 2 extra bits 2 keer zo lang kost om te factoriseren en je kunt wel nagaan dat daarvoor veel slimmere methoden dan brute force alles proberen te delen gebruikt is.

[Verwijderd]

Daarom duurt deze contest zo lang : Er wordt NIET slim gerekend, sleutel voor sleutel wordt gewoon gekeken of het de goede is. Dus idd zal jij het slimmer kunnen. Misschien zelfs ik wel

[Verwijderd]

Dan ga je toch als concurrent van distributed.net ook mee doen aan de wedstrijd van RSA [of zoiets] dan kan je zelf al die knaken binnen slepen.

Check:
www.rsasecurity.com/rsalabs/challenges/

Hier kan je zeer waarschijnlijk ook de precieze opgave vinden en kijken of jou methode werkt.

edit:
ff Regels van de challenge toevoegen:
www.rsasecurity.com/rsalabs/challenges/secretkey/rules.html

[irrelevant]

Er zijn allerlei verschillende opgaven. Wat is nu precies wat de opgave die DPC probeert op te lossen?

[Verwijderd]

Eenvoudig de passende sleutel vinden

Wat wij hier doen heet "Brute Kracht Kraken",

er zijn heel veel sleuteltjes en slechts een past er, degene die die sleutel heeft/krijgt wint.

[irrelevant]

Ja, maar hoe doe je dat? Is het idd een factoriseerkwestie? Of is het iets van de vorm x^y mod z voor hele grote x,y en z. Dat is nl. ook iets wat veel voorkomt bij cryptografie. Of iets heel anders?
----------
Oftewel: welk probleem proberen jullie nu precies op te lossen?

[IceStorm]

Het gaat toch gewoon op de voglende manier:
-Neem een sleutelbos met 2^64 sleutels.
-Pak sleutel 1, stop die in het slot, draai hem om.
-Hoor je klik dan heb je de goede sleutel, zoniet op naar de volgende

Toch?

[redwing]

Inderdaad is het gewoon een kwestie van alle sleutels uitproberen totdat je de goede tegenkomt.

[irrelevant]

Maar dat zou juist veel sneller moeten kunnen als je het slim aanpakt i.h.a. Of is dit echt een waterdicht systeem wat niet sneller te doen is?
Zal er flink wat dieper in moeten duiken zie ik wel. Ik heb inmiddels wel de exacte opgave gevonden, alleen weet ik dus nog niet wat het precies inhoudt.

http://www.rsasecurity.com/rsalabs/challenges/secretkey/secret-key.html<BLOCKQUOTE><font size=1 face=Verdana, Arial, Helvetica>quote:</font><HR>Contest identifier: RC5-32/12/8
Cipher: RC5-32/12/8 (RC5 with 32-bit wordsize, 12 rounds, and 8*8=64-bit key)
Start of contest: 28 January 1997, 9 am PST
State of contest: ongoing
IV: 79 ce d5 d5 50 75 ea fc
Hexadecimal ciphertext:

bf 55 01 55 dc 26 f2 4b 26 e4 85 4d f9 0a d6 79
66 93 ab 92 3c 72 f1 37 c8 b7 0d 1f 60 11 0c 92
ae 2e cd fd 70 d3 fd 17 df b0 42 12 b9 7d cf 22
18 6b a7 15 ce 2c 84 bf ce 0d d0 4d 00 6b e1 46[/quote]Moet dus eerst weten wat dit precies voorstelt. Hoe Distributed.net het aanpakt en of dat dom is of dat het slimmer kan.

[Verwijderd]

ik denk dat je hier wel wat aan hebt.

http://citeseer.nj.nec.com/rivest95rc.html

--Ray

[daaan]

deze methode werkt toch sowieso niet, want je hebt de waarde van de goede sleutel niet om mee te vergelijken, of heb ik het nu fout gebegrijpt

[redwing]

Volgens mij waren de eerste karakters van de encrypted zin wel bekend. Je kunt dus de key proberen, en dan kijken of je deze karakters tegenkomt, zo ja => goed key anders de volgende proberen.

[Onno]

<BLOCKQUOTE><font size=1 face=Verdana, Arial, Helvetica>quote:</font><HR>Maar dat zou juist veel sneller moeten kunnen als je het slim aanpakt i.h.a. Of is dit echt een waterdicht systeem wat niet sneller te doen is?[/quote]Nou, leef je uit. Als je een manier vindt om RC5 eenvoudiger te kraken ben je de eerste die dat gelukt is.

ftp://ftp.rsasecurity.com/pub/rsalabs/rc5/

[Verwijderd]

Ik leg er hoogstpersoonlijk 1000 piek bij als het iemand lukt om de juiste key "handmatig" te vinden voor 31/12/00.

[Tourniquet]

<BLOCKQUOTE><font size=1 face=Verdana, Arial, Helvetica>quote:</font><HR>Op 09 november 2000 12:28 schreef redwing het volgende:
Volgens mij waren de eerste karakters van de encrypted zin wel bekend. Je kunt dus de key proberen, en dan kijken of je deze karakters tegenkomt, zo ja => goed key anders de volgende proberen.[/quote]Idd, de gecodeerde boodschap is een zin die begint met "The secret message is:" of zoiets. Pas wanneer een koe dit begin van een zin vindt, wordt de hele zin gedecodeerd en wordt het resultaat voorgelegd aan RSA om te kijken of dit idd de goede zin is (in theorie is het natuurlijk mogelijk dat er per ongeluk een heel andere zin wordt gevonden!)

[irrelevant]

Onno: soms weet je bijvoorbeeld dat de key een product van twee priemgetallen is oid. Dan is het nog steeds een hoop werk om hem te vinden maar kun je toch al heel veel getallen buiten beschouwing laten.
Zijn hier ook niet wat zwakheden die uit te buiten zijn om de zoekruimte te verkleinen?

Ik heb inmiddels wat gelezen over hoe het werkt (bedankt voor de links!) maar nog niets over hoe het kraken aangepakt wordt. Zou er echt uit elke moglijke sleutel een tabel gegenereerd worden en dan gedecodeerd? Is het probleem toch niet te vertalen naar een factoriseringprobleem oid? Wat is de kern?
Naar zulke dingen ben ik dus op zoek.
En sowieso blijft het de vraag hoe de huidige implementatie is. Voor allerlei basisoperaties zoals het vermenigvuldigen van 2 getallen zijn allerlei ingenieuze algoritmes die veel sneller zijn dan standaardmethodes.

[Verwijderd]

<BLOCKQUOTE><font size=1 face=Verdana, Arial, Helvetica>quote:</font><HR>Op 09 november 2000 13:34 schreef irrelevant het volgende:
Onno: soms weet je bijvoorbeeld dat de key een product van twee priemgetallen is oid. Dan is het nog steeds een hoop werk om hem te vinden maar kun je toch al heel veel getallen buiten beschouwing laten.
Zijn hier ook niet wat zwakheden die uit te buiten zijn om de zoekruimte te verkleinen?[/quote]Nee er zijn geen priemgetallen of zo die ze gebruiken. het is gewoon een waarde tussen 1 en heel veel. volgens mij worden er een aantal xor's en adds gedaan in het systeem. kijk op de RSA page. Het patend is net vrijgegeven voor publiek. (daarvoor was het ook al open. wat juist de kracht was van het systeem. alle grote goden op de planeet hebben het al via een analitische methode geprobeerd.)<BLOCKQUOTE><font size=1 face=Verdana, Arial, Helvetica>quote:</font><HR>Ik heb inmiddels wat gelezen over hoe het werkt (bedankt voor de links!) maar nog niets over hoe het kraken aangepakt wordt. Zou er echt uit elke moglijke sleutel een tabel gegenereerd worden en dan gedecodeerd? [/quote]ja er zijn verschillende keyspaces gemaakt (64 stuks) met daarin alle mogelijke keys. gewoon 1 to heelveel. deze worden allemaal aan de clients uitgedeeld en geprobeerd. alles wat niet goed is wordt uit de lijst weggestreept.<BLOCKQUOTE><font size=1 face=Verdana, Arial, Helvetica>quote:</font><HR>En sowieso blijft het de vraag hoe de huidige implementatie is. Voor allerlei basisoperaties zoals het vermenigvuldigen van 2 getallen zijn allerlei ingenieuze algoritmes die veel sneller zijn dan standaardmethodes.[/quote]wat dacht je dat dit de eerste versie van de client was en dat we stom zijn. de client is hoog geoptimaliseerd. bijvoorbeeld alle adds zijn shifts. etc. de grote mensen der aarde van de assembly zijn voor een aantal cpu's aan de gang. zo is er een MMX versie, een Athlon versie (gemaakt door iemand die ook de compaq compiler voor de alpha gemaakt heeft), etc. nee jongen je kan hier nog weinig meer uit halen. en als je het toch kan, dan trek ik alles terug en zal je schoenen komen poetsen. maar wel meteen naar d.net mailen zodat ze een nieuwe client kunnen maken zodat het snel over is. snel snel snel snel

[raptorix]

<BLOCKQUOTE><font size=1 face=Verdana, Arial, Helvetica>quote:</font><HR>Op 09 november 2000 09:50 schreef IceStorm het volgende:
Het gaat toch gewoon op de voglende manier:
-Neem een sleutelbos met 2^64 sleutels.
-Pak sleutel 1, stop die in het slot, draai hem om.
-Hoor je klik dan heb je de goede sleutel, zoniet op naar de volgende

Toch?[/quote]Nee hoor 1 minder als je alles getest hebt en je hebt er nog 1 over ga je natuurlijk niet moeilijk doen en die laatste testen

[Verwijderd]

Ik wil niet lullig doen of zo maaruh:

NIEMAND REKENT BETER/SLIMMER DAN MIJN KOE!

<------------------------------

[Onno]

<BLOCKQUOTE><font size=1 face=Verdana, Arial, Helvetica>quote:</font><HR>En sowieso blijft het de vraag hoe de huidige implementatie is.[/quote]De source is gewoon vrij beschikbaar: http://www.distributed.net/source/<BLOCKQUOTE><font size=1 face=Verdana, Arial, Helvetica>quote:</font><HR>Onno: soms weet je bijvoorbeeld dat de key een product van twee priemgetallen is oid.
Dan is het nog steeds een hoop werk om hem te vinden maar kun je toch al heel veel getallen buiten beschouwing laten.[/quote]Zoals ik al zei: als het je lukt zul je de eerste zijn. En daarom denk ik eerlijk gezegd ook niet dat je iets vindt.

[irrelevant]

Ik heb het al opgegeven inmiddels.

Gewoon doordat er stond "brute-force alle mogelijkheden testen" dacht ik: dat moet sneller kunnen (slechter kan immers niet ).
Maar als dit inderdaad openbaar is en niemand erin is geslaagd het te verbeteren zal het wel zinloos zijn.
Door dat "brute-force" ging ik ervan uit dat een klein clubje gewoon hun eigen code in elkaar gezet had zonder verder goed onderzoek te doen.

[dyna18]

Voor een begrijpelijke uitleg over de RC5 encryptie algoritme moet je hier ff kijken: "The RC5 Encryption Algorithm"

[weird0]

ik vind helemaal niet dat we sneller moeten
je moet het zien als F1 racing...

een F1 car mag ook niet zomaar extra vleugeltjes hebben om em sneller te laten grazen ehhh rijden...

ik vind dus dat we nie zomaar een "nieuwe koe" mogen ontwerpen om sneller te grazen...

das niet eerlijk voor TA weetje want dan verliezen ze te snel en dan moet ik ook nog eens een andere hobby gaan zoeken dan stats kijken

[Verwijderd]

<BLOCKQUOTE><font size=1 face=Verdana, Arial, Helvetica>quote:</font><HR>Op 09 november 2000 15:40 schreef irrelevant het volgende:
Ik heb het al opgegeven inmiddels.[/quote]das nou jammer. en je hebt niet eens een poging gewaagd. Heb je wel de source de download? je geeft wel snel op. kijk ik kan tenminsten nog zeggen dat ik de source aan de praat gekregen heb en een aantal bugs voor de AIX client eruit gehaald heb. mijn naam staat zelfs in de about van de logvis. kom op probeer eens iets.