De IV in het RC5 algoritme

[wacco]

Eej koetjes,

Ik zit met m'n opleiding electronica de laatste tijd wat te spelen met VHDL (hardware beschrijvings taaltje) en vond het wel een strak plan om een RC5 brute force pipe uit te werken. Naja, dat bleek iets lastiger dan het op het eerste puntje leek aangezien je bijvoorbeeld zit met een S[26] die gevuld wordt van rechts naar links met de secret key over een semirandom patroon (Q en P op een maniertje, maar is verder passief), en dat drie keer. Daarna wordt ie gebruikt van links naar rechts. Ouch, dat zou dus één: een hele lange pipe worden, en twee: 26x4x8bits aan alleen al je hash table in de pipe. Maar goed, daar heb ik wel wat dingetjes voor bedacht, of het haalbaar is is een tweede.
Voor zover de inleiding, waar ik nu mee in m'n maag gesplitst zit is het volgende; waarvoor dient de hele IV nou eigenlijk?

code:

   printf("bigplain: "); printword(bigplain[0]); 
   printf(" "); printword(bigplain[1]); printf("\n");
   
   bigplain[1] ^= iv[1]; bigplain[0] ^= iv[0];
   
   printf("after iv: "); printword(bigplain[0]); printf(" "); 
   printword(bigplain[1]); printf("\n");

Moet je nu op "The unkn" checken, of kan je gewoon de hele xor weglaten en op de stap ervoor checken? Volgens mij kan dit, immers, het is maar een xor, alleen zie ik het nut er dan niet van in dat deze er zowiezo in zit. Kan iemand mij dit uitleggen?

Daarnaast zou ik wel eens willen horen of mensen dit een strak plan zouden vinden, een rc5 pipe op de pci poort oid (als ik pci werkend kan krijgen natuurlijk)

[0rbit]

En hoe wou je de chip gaan maken? Programmeerbaar chippie?

[SWfreak]

Het is een beetje moeilijk om uit de code die je gepost hebt te achterhalen waar dit stukje code nu precies zit. Bij RC4 weet ik hoe de IV in elkaar zit en bij RC5 lijkt ie een vergelijkbare rol te vervullen. Die iv (initialisatie vector) moet je je ongeveer zo voorstellen. Stel we hebben tekst1 en tekst2, beide ge-encrypt met RC4 met dezelfde sleutel. De ge-encrypte tekst noemen we cypher1 en cypher2. Dus

code:

cypher1 = pseudo-data-van-sleutel xor tekst1
cypher2 = pseudo-data-van-sleutel xor tekst2

Als een aanvaller nu (een deel van) tekst1 te weten komt, dan kan hij zonder problemen pseudo-data-van-sleutel uitrekenen en dan tekst2 uitrekenen. Ofwel, een RC4 sleutel is maar eenmalig te gebruiken! Om dit te voorkomen wordt de IV aan de sleutel toegevoegd. De IV is gewoon een aantal bits (bijvoorbeeld het nummer van een bericht) om de gebruikte sleutel uniek te maken. Hierdoor is de sleutel voor ieder bericht verschillend en heb je het eenmalig gebruik probleem niet. (Dan is de boel overigens als nog wel te kraken, zie bijvoorbeeld hier).
Zo werkt het iig bij RC4 (als ik me alles goed herinner). Bij RC5 is het voor zover ik ff heb kunnen nagaan ongeveer hetzelfde. Volgens een post op distributed.net is de IV gexored met de eerste zoveel bits van de plaintext. Weer xoren zou dus de originele plaintext moeten opleveren. Ik zou die xor er dan ook vooral inlaten, anders zit je zo te zien rare dingen te checken...
Overigens is dit volgens mij heel google-baar

[wacco]

Mr_Atheist: FPGA

Verder doe je bij rc5 setup (met key), decrypt, en dan xor. Heb je je plaintext ( "The unkn" ) ge-xor-ed en check je daar op, dan zou het ten alle tijden moeten werken. Lijkt me. Ik heb de source van d.net flink lopen strippen, en die 'werkt' nu zonder xor.
* wacco bekijkt link... Die post die je vond zegt idd hetzelfde. Moet toch nog maar eens m'n google kunsten aanscherpen.

Ik heb iig de pipe een soort van uitgewerkt naar aanleiding van de code. 1) Deze pipe wordt gigantisch lang, en 2) Als tussen elke stage alles nog eens in flipflops geplaatst moet worden ook nog eens gigantisch groot. Aangezien S[26] maar eens in de 26*7 stages wordt aangesproken valt hier wel wat te knutselen, maar dit staat er nog niet in (net zoals L[3] en wat globalere variabelen). De logica rechtsonder is voor een wat overzichtelijkere interface met het externe-who-knows-what. Nou ja, plaatjes spreken boekdelen, so here goes nothing:

Sorry dat hij wat groot is, maar hopelijk wel duidelijk. Zoals je ziet doe ik hier nog 2*32 bits in initialisatie en in decrypten. Aangezien het een FPGA is ben ik hier niet toe gelimiteerd, dus ik wil hier nog 64 (danwel 128) van maken, maar moet daarvoor even de rfc induiken (en m'n gezonde verstand gebruiken ) dus dat komt nog. Ik wordt btw wel gelimiteerd door de kloksnelheid die ik wil halen, want hoe breder, hoe trager (bij + bijvoorbeeld). edit: competitie is 32/12/9 dus dit gaat helemaal niet op
Tips, hints, hulp, etc, allen welkom

Nog even een minor update: loop twee (i 12..0) hoeft maar 11 keer, kleine typo (i 12..1) en multiple pipes (dus meerdere keys / clk) is niet beschikbaar op deze manier, daarvoor moet een stukje key-regel logica komen (indien van toepassing dus).
En stage buzy en key++ moeten omgedraaid worden (en key++ moet eigenlijk my_key = key; key++ zijn)

[ Voor 19% gewijzigd door wacco op 26-01-2004 02:19 ]

[Verwijderd]

Het idee voor een hardware oplossing voor RC5 (die ook nog eens door de client ondersteunt wordt) is al vaker bij distributed.net voorbij gekomen.

Ik zal eens informeren of er daar nog info van beschikbaar is.

[0rbit]

Is zo'n FPGA op relatief hoge klokfrequenties niet net zo duur als een normale CPU? Een moederbordje en wat geheugen zijn de kosten niet. Zeker voor een project als RC5 is 128 MB SDRAM meer dan zat. Kortom; Is het geheel wel nuttig?

[Mobster]

Nuttig? Misschien niet.
Leuk om uit te zoeken en te ontwerpen? Zekers

[[eNeRGy]]

Mr_Atheist snapt er weer niets van

[wacco]

Een FPGA kost niet zo veel eigenlijk, het probleem alleen is dat ik een gigantische pipe heb uitgetekend gisteren. Een stapje of 650. Als je voor elke stage alle waarden, dus een hash table van 26*32 bits, en een L van 3*32 (alleen over de eerste 550 or so, dat dan weer wel) moet kopieren elke stap, ben je een flipflop of 60K kwijt. En dat betekend dat je een grote FPGA nodig hebt, wat de prijs wel omhoog jaagt. Een manier om dit weer naar beneden te krijgen is het aantal stages naar beneden werken, wat heel goed mogelijk is. Alleen zorgen grotere stages ervoor dat de kloksnelheid weer instort.

Een beetje wikken en wegen dus, waar als belangrijkste argument wel telt dat het nog altijd 'for fun' is, en we dus niet extreem veel blingbling erin kunnen (en gaan) pompen. Dat wordt dus inleveren op de snelheid. En of het geheel nuttig is, stel; als een RC5 pipeline een key per clockcycle kan checken, en deze past in een FPGA van 50 euro, en deze FPGA draait op een 50Mhz, hoe blij ben jij dan dat dat aan je seriele poort hangt? You do the math... _{50mkey/sec dus} Anyhoe deze waarden zijn maar een wilde gok, ze kunnen veel hoger uitvallen (ook de kosten )

Dan over 'of het al eens gedaan is', ik ben de pipermail hardware lists ingedoken, en maart '98 kwam idd de discussie omhoog die hier nu ook dreigt te ontstaan. Eigenlijk niet zo'n mooi begin van een projectje, aangezien ik eerst eens wil zien of het wel te implementeren is at all. Iig; in april '98 heeft iemand daadwerkelijk iets geproduceerd in verilog wat met een 'sneller algoritme' werkt. Al las ik dat z'n pipe dus niet key/clk deed. Ik ga dat even bekijken, misschien dat ik er gebruik van kan maken.
En verder ga ik nog ff verder spitten in de mailinglist, misschien dat er nog meer bruikbaars in staat.

Wacco out - will keep you updated. Misschien dat we dit topic moeten omdopen naar '[RC5] hardware brute force pipeline' oid.

-edit-
Er zijn ook bakken vol FPGA's met vanallesennogwat onboard, en dus ook mem. Nu weet ik niet exact hoe hier gebruik van te maken, en of het snel genoeg is (!) maar als dat zo is dan kan zo'n 650-stage pipe natuurlijk wel Maar daar moet ik eerst nog eens stevig over gaan lezen

[ Voor 9% gewijzigd door wacco op 26-01-2004 23:38 ]

[0rbit]

Nee hoor, ik vind het echt interessant Ik heb zelf ervaring met VHDL. Ik kan me alleen niet voorstellen dat zoiets kan opwegen tegen een zware CPU met een stukje uitontwikkelde software.

In ieder geval succes; Ik volg je werkzaamheden met grote interesse en als je ongeveer een megakey per euro doet dan heb ik wel interesse in een USB-exemplaar

[ Voor 4% gewijzigd door 0rbit op 27-01-2004 00:16 ]

[[eNeRGy]]

Het ligt eraan, kijk maar naar de verschillen van de P4, P3, XP en G4, daar maakt het aantal hardware vector rotators (ofzoiets) (repectievelijk: 0, 1, 2 en 4) heel erg uit.

Ik heb verder geen ervaring met alles wat hier in het topic langskomt (ik snap de helft ongeveer ) maar het lijkt me als je de hardware inricht op RC5 je nog veel verder zal komen dan zo'n "zware CPU met een stukje uitontwikkelde software".

[ Voor 7% gewijzigd door [eNeRGy] op 27-01-2004 00:29 ]

[0rbit]

[eNeRGy] schreef op 27 januari 2004 @ 00:29:
Het ligt eraan, kijk maar naar de verschillen van de P4, P3, XP en G4, daar maakt het aantal hardware vector rotators (ofzoiets) (repectievelijk: 0, 1, 2 en 4) heel erg uit.

Ik heb verder geen ervaring met alles wat hier in het topic langskomt (ik snap de helft ongeveer ) maar het lijkt me als je de hardware inricht op RC5 je nog veel verder zal komen dan zo'n "zware CPU met een stukje uitontwikkelde software".

Misschien is dat wel zo; Leuk dat meneer wacco dat eens grondig voor ons gaat uitzoeken

Je hebt met RC5 natuurlijk een groot voordeel; Je kunt de keys onafhankelijk van elkaar testen. Je zou dus inderdaad de zaak in 64-voud naast elkaar kunnen uitvoeren (tot je chip vol is) en dan kan het bij lage kloksnelheid zeker hout snijden. Het probleem is dat de kloksnelheden van zo'n programmeerbare chip niet erg hard oplopen en met name de prijzen dan redelijk snel toenemen

Er is altijd een optimum te vinden

[wacco]

Het is niet zo zeer naast elkaar, maar meer achter elkaar door z'n strot rammen om het maar subtiel te zeggen Das het hele idee van een pipeline; als een key door een stap heen is, kan een volgende key bewerkt worden door deze stap. En als zo'n stap heel kort is dan kan de kloksnelheid omhoog. Je krijgt dan bijvoorbeeld een pipeline die extreem lang is (hier 650 stappen, een P4 heeft er 28 bijvoorbeeld) en daar zit een nadeel aan als je met code werkt die bijvoorbeeld naar een andere locatie springt. Maar dat doen we hier niet, dus daar hebben we geen last van