Onbreekbaar versleutelingssysteem ontwikkeld?

De Amerikaanse cryptoloog Rabin (die in de cryptografie al bekend was door zijn 'Kwadraatsysteem', een van de weinige cryptosystemen dat wiskundig bewezen veilig is) claimt een onbreekbaar versleutelingssysteem te hebben ontworpen. De zwakte van bestaande systemen is dat er een sleutel gebruikt wordt, zodra deze uitlekt kan een aanvaller alle voorgaande, huidige en toekomstige communicatie ontsleutelen. Er bestaat theoretisch gezien maar één sluitend systeem: de zogenaamde 'One Time Pad'. Hier wordt elke bit van het bericht met een nieuwe 'sleutel-bit' versleuteld. De sleutel is dan even lang als het bericht, dus alle mogelijke sleutels (en berichten) hadden de bron kunnen zijn voor de (afgeluisterde) communicatie.

Het One Time Pad systeem lijkt mooi, in de praktijk is het vrijwel niet te implementeren. De verzendende en ontvangende partij moeten op een of andere manier een 'bitgenerator' hebben, die ze allebei dezelfde random bits geeft. Rabin heeft hier een oplossing voor gevonden:

It works like this. The two conspirators, Alice and Bob, first have to establish a set of secret rules for picking random bits from the data. This is a potential weakness in the scheme-how do they share these rules securely? But it would only involve one meeting, say, rather than the repeated ferrying of one-time pads.

They might share a computer program that taps into the world's data stream, pulling out a certain bit from the Sky TV satellite at 12 noon precisely, a bit from the Microsoft home page half a second later, a bit from the Dow Jones index after that, and so on. The program assembles these bits into a key.

Whenever they want to communicate, Alice just tells Bob over the phone which key-say, the one their program made last Tuesday-she is using to encode the message. The eavesdropper, Eve, is sunk. Without Alice and Bob's program, she doesn't know which bits to look for. So it's a machine for generating an endless one-time pad, with no reliance on couriers.

Al eerder berichtten we over dit systeem, nu blijkt het al in een vergevorderd stadium te zijn. Het idee van Rabin is nu om een gestandaardiseerd systeem te maken dat random bits genereert (een netwerk van 48 satellieten), deze genereren zoveel data (45000 Gigabit per seconde) dat opslag ervan niet mogelijk is. Op deze manier kan de aanvaller niet alle bits opslaan om later rustig te gaan zoeken naar de key, hij zal van te voren moeten weten waar in de bitstream de sleutel verstopt zit.

Dit klinkt natuurlijk geweldig, maar nog steeds is er een impliciete 'key' aanwezig: namelijk de afspraak tussen Alice en Bob. Zodra Eve deze afspraak kan afluisteren (of raden) is het systeem gebroken. De bekende cryptoloog Bruce Schneier heeft in maart 2001 al zijn bedenkingen tegen dit systeem geformuleerd in zijn CryptoGram mailinglist.

Met dank aan Verwijderd voor de tip. Het complete artikel zal 5 januari in het blad 'New Scientist' verschijnen.

Reacties (69)

[Verwijderd]

ONZIN

Alles dat je codeert, moet gedecodeerd kunnen worden en als dat kan is het ook te kraken. Heel simpel. En ja natuurlijk, je kunt het bemoeilijken.
Als het werkelijk zou werken.. dan zou waarschijnlijk amerikaanse overheid er niet blij mee zijn, die zijn zo paranoïa dat alles afluisterbaar moet zijn.

Maar goed wie weet waar het heen gaat.

[Theswitch]

Ok, om jullie even van het idee af te brengen dat "Alles kraakbaar is". Dat is dus niet zo, de one-time pad zoals hier beschreven is *bewezen* onkraakbaar.

Om het in d-net taal te beschrijven:
Je weet bij d-net RC64 wanneer het gekraakt is, omdat je een sleutel hebt die "past". Op die manier weet je dat je het goede bericht hebt.

Bij de one-time-pad , die een keylengte maakt ter lengte van het bericht past *elke* sleutel. Je weet dus niet of je het gekraakt hebt.

Voorbeeld, stel de sleutel is 10101010
Waarbij 1 = neem het ROT13 lettertje
waarbij 0 = neem de gewone letter

Stel je versleuteld "TWEAKERS"
Met versleuteling met bovenstaande key krijg je:
GWRAXEES

Als je dit nu probeert te decoden, weet je niet wanener je het gevonden hebt. Stel je probeert 11110000 als sleutel, dan krijg je:

TJENXEES

Misschien was dat nu juist wel de geheime boodschap, en TWEAKERS helemaal niet.

Ik hoop dat het zo duidelijk is. Je weet dus niet wat de boodschap is, en met een goed algorithme kan je *elke* boodschap genereren met een goed gekozen sleutel.

[Verwijderd]

Als je op deze manier redeneert is ROTxx ook onkraakbaar...

[Theswitch]

Kan je nagaan I've invented the non-hackable ROT13 encoding.

[TheOneLLama]

En wat jij zegt is ONZIN..

Deze meneer heeft een encryptie ontwikkeld die in principe op een heel eenvoudig principe berust: nl. als je een key gebruikt die net zo groot is als het bericht dit niet te kraken is. Als je hier bruteforce cracking op toepast werkt het niet omdat de key zelf als het ware ieder ander bericht kan bevatten.. de 64 bits RC5 key herhaald zich als het ware, omdat deze maar 64 bit is... simpel gezegd: door die herhaling kun je achterhalen wat de key nou eigenlijk is.

Verder zou je de encryptie nog kunnen breken door (op erg wiskundige wijze) naar frequentie te kijken, het bekende verhaal van: in het nederlands komt de e vaker voor dan de andere letters, etc. Dit lossen we op door pure random data te gebruiken, waardoor de frequentie totaal irrelevant wordt tov de gebruikte tekst. Dat dit wat ik hier nu zeg (hoewel sommige dingen een beetje erg wazig zijn geformuleerd en misschien door sommige ook wel als fout zullen worden aangemerkt, de essentie klopt wel redelijk denk ik) allemaal klopt dat is waar deze man zoveel tijd aan besteed heeft: dit wiskundig te bewijzen.. dat was em gelukt en dat stond in die eerdere t.net posting.

Nu is ie dus een systeem aan het bouwen wat er voor zorgt dat als ik iets encrypted naar jouw wil sturen we allebij dezelfde random data gaan gebruiken. Het systeem om aan deze random data te komen zal altijd zwak zijn maar de encryptie methode die hij toepast gaat er van uit dat er 2 bronnen zijn die met die random data.. als de data hier eenmaal mee geencrypt is, is het dus ONMOGELIJK om dit te kraken.
Alleen als je weet welke random data gebruikt is om te encoden en decoden kan dat (dit is dus de key), en die is dus niet te kraken (die moet je gewoon weten). Omdat deze data random is en met onopneembare snelheid voorbij komt is ie dus praktisch vergankelijk.

Een voorbeeld van hoe dit in de praktijk zou gaan..
Er staan ergens 10.000 kamers met het lavarand model (http://www.lavarand.com/) random data te maken (ok extreem voorbeeld ), Ali mailt naar Mohammed met PGP op welk tijdstip, vanuit welke kamer ze random data gaan aftappen, ze gebruiken deze data om met deze vorm van encrypte geheime data over te sturen. Dit doen ze (allemaal leuk) en de volgende week komt de FBI erachter, en na een jaar of 2 kraken ze de PGP key en zien wat de afspraak was.. in de tussentijd is er al zoveel random data geproduceert dat ze dit onmogelijk hebben kunnen opslaan, en er is geen enkele manier om deze random data terug te halen, en ze kunnen niet bruteforcen (ECHT niet, ik hoop dat je het nu snapt, dit is geen onzin.. al heb je een werkende 1024bit quantom computer het zal je niet lukken!), en ook mbv frequentie analyse kunnen ze niks, dus ze zullen er nooit achterkomen!

[Beaves]

Aan de ene kant zijn dit soort ontwikkelingen zeer mooi maar er zitten IMHO te veel nadelen aan een onkraakbare encrypty. Dan heb ik liever een iets minder goede encrypty.

Stel dat dit echt gaat werken, dan gaan alle mensen die echt iets te verbergen hebben (terorristen en andere gekken) dit soort oplossingen gebruiken, dan is het helemaal een raadsel over wat er kan gaan gebeuren. Want je kan ze dan immers helemaal niet meer afluisteren.

Dan heb ik toch liever een iets minder veilige encrypty die met veel moeite en geld gekraakt kan worden. Want niet iedereen heeft geld genoeg om computers te kopen en om mensen in dienst te nemen om een bijna onkraakbare encrypty te kraken. Daardoor blijven je berichten toch redelijk veilig.

[Zarc.oh]

Stel dat dit echt gaat werken, dan gaan alle mensen die echt iets te verbergen hebben (terorristen en andere gekken) dit soort oplossingen gebruiken, dan is het helemaal een raadsel over wat er kan gaan gebeuren. Want je kan ze dan immers helemaal niet meer afluisteren.

Als je dit implementeert en houdt als beheerder van die sateliet bij wie er geregistreerd staat (ALS het per sateliet gaat ), heb je iig een lijst van gebruikers en zou je je de gebruikte codes van verdachte gebruikers kunnen opslaan. Zo kan je toch binnen aanzienlijk tijd een leesbare boodschap te voren schuiven volgens mij. Maar dan moet het systeem ook recursief werken, zodat er verder niemand bij kan.

[JoMr3]

Volgens mij maak je hier een denkfout. De verstuurder en ontvanger spreken namelijk een bepaalde manier van coderen af. Dus bijvoorbeeld: pak het eerste bit op dit tijdstip, het tweede op dat tijdstip, het derde op dat tijdstip, etc. etc. In dit geval kan ook de beheerder van het netwerk niet weten welke codes de gebruikers gebruiken, omdat hij die afspraken niet weet.

Alleen als de beheerder precies kan zien welke bits door wie op welk tijdstip worden gelezen, heeft hij de codes in handen. Bovendien kun je zodanige tijdstippen afspreken, dat het onmogelijk voor een buitenstaander is om het begin van de sleutel te raden. En er wordt ook nog eens afgesproken van welke dag(en) de sleutel wordt gebruikt.

Al met al zijn er dus behoorlijk veel obstakels, die zeer waarschijnlijk onoverbrugbaar zijn.

edit:
Een aantal denkfouten gecorrigeerd

[justice strike]

er zit nog een foutje in dit systeem
het kan met geen mogenlijkheid op het internet gebruikt worden omdat de lag alleen al ervoor zorgt dat de verzender en de verstuurder niet dezelfde bits hebben.. (tijdstip bla etc.. kan dus niet gebruikt worden!!.)

[Xellence]

daar heb je QoS voor (Quality of Service) of IPv6 heeft een soortgelijk systeem ingebouwd. Hiermee kan de data gegarandeerd met de juiste timestamp bezorgd en ontvangen worden.

[Deddiekoel]

Mooi idee. Ik weet alleen nog niet hoe de implementatie ervan zal verlopen. Want zoals gezegd moeten er eerst afspraken komen. Dat dit de zwakte is van het systeem is logisch, maar dat heeft elk systeem. De ontvanger MOET weten wat de verzender met het bericht heeft gedaan.
Maar het voordeel van dit systeem is dat er gebruik gemaakt kan worden subjectieve afspraken, mensen hoeven alleen maar tijdstippen af te spreken etc.

Ik ben erg benieuwd

[TheGhostInc]

Daarnaast begint mijn kabelmodem bij 45000 Gigabit per seconde een bitje te stotteren.

Het is natuurlijk heel leuk als je een of ander bedrijf bent waarbij het uitlekken van 1 boodschap miljoenen kost, maar je kunt natuurlijk ook de sleutel gewoon super bewaren.

* 786562 TheGhostInc

[TheOneLLama]

Een sleutel is te kraken.. zie RC-64
Nu is dat nog heel moeilijk ja, maar denk aan quantom computing enz.. onder het motto je weet maar nooit wat de FBI al in de garage heeft staan Het idee achter deze encryptie is, je gebruikt em, daarna komt iemand erachter dat je dit gedaan hebt en hij heeft de geencrypte data onderschept. Sterker nog even later komt ie erachter, jij hebt het random data blok zo en zoveel gebruikt, startende vanaf 10 uur precies.. (haalt ie uit je logfiles ofzo). Omdat er sinds 10 uur en 11 uur (de tijd dat ie hierachter komt) al zoveel data verstuurt is dat ie er niet meer kan achterhalen wat die random data nou was.

Zelfs als ie realtime meeluisterd met je 14k4 verbinding, dan vraag je die random data toch gewoon op via (bijvoorbeeld) SSH? de enige manier waarop ze het dan kunnen breken is die SSH sessie realtime te ontcijferen (en het exacte punt waarop je je random data binnengaat halen ontcijferen). Zelfs met quantum computing krijgt de FBI dit van z'n leven lang niet voor elkaar
Dit encryptie model heeft echt een goed potentieel!

[Randal Peelen]

Het probleem dat volgens mij ook zou kunnen ontstaan is dat mensen die je aan het "bespioneren" zijn na een tijd doorhebben op welke plekken jij steeds op dezelfde momenten data vandaan plukt. Dit is een vast patroon namelijk en zal dus als degene die jou in de gaten houdt een aanhouder is, een keer op moeten vallen. Je kunt dan wel elke keer dat je data wil gaan vervoeren een andere afspraak maken over waar de key vandaan komt maar dat gaat ook vroeg of laat mis, en kost veel te veel tijd. Het makkelijkst is dus altijd van dezelfde plek je keytje halen, en dat zou een keer op kunnen vallen.

[Verwijderd]

Ik zie een aantal beperkingen. Alice en Bob moeten ook twee precies synchrone klokken hebben; anders nemen ze verschillende bits en kunnen ze elkaars boodschap niet ontcijferen.

Ook moet de bron ook echt digitaal indentiek bij hun aankomen.

Verder moet bij OTP de sleutel echt random zijn. Mocht dat bij hun keuze niet zo zijn dan is hun boodschap te kraken.

[sigma01]

Ik denk dat dit systeem alleen interessant is voor bedrijven die echt dingen geheim moeten houden. Die hebben het geld om atoomklokken e.d. te plaatsen. Dit systeem is ook gevaarlijk omdat er absoluut geen controle meer mogelijk is. Nu is het zo dat de CIA de (meeste) sleutels kan kraken maar met dit systeem moet dat onmogelijk worden.
Een andere zwakheid binnen het systeem is de tijd. Het systeem werkt op zijn vroegst pas over 10 jaar dan is 45000Gbit allang geen probleem meer voor de computers

edit:
Zie post hieronder

[brammus]

Idd, Wat als op dat moment jouw verbinding niet goed werkt, of als de eigenaar van de site waarvan je afspreekt dat je op dat en dat moment die en die bit gebruikt, de site aangepast heeft

Volgens mij is dit onwerkbaar, je bent van veel te veel externe bronnen afhankelijk...
Je kan wel leuk met elkaar afspreken hoe je het aan pakt, maar als internet niet meewerkt, ben je alsnog de lul met je geëncrypte bericht...

Toch

[ta_chi79]

Inderdaad, er zijn tegenwoordig zoveel gegenereerde pagina's (php, asp, java servlets, ...) dat de kans heel groot is dat jouw pagina anders is dan de pagina die op dezelfde tijd wordt gegenereerd.
Denk hier aan een andere reclame banner die wordt meegelinkt, een bezoekers-teller die iedere keer anders is, enzovoorts...
Op deze manier heb je dus nooit de garantie dat 2 personen op exact dezelfde tijd dezelfde pagina te zien krijgen.

[Vaevictis_]

OTP is inderdaad in theorie onkraakbaar.
Met Quantum Computing wordt het wel een stuk interessanter, dan kun je de key normaal laten generen en deze overzenden. Je weet dan in iedergeval of je wordt afgeluisterd. Als de CRC van de key niet correct is. Dan heb je die techniek van Rabin niet meer nodig. Maar dat neemt niet werk dat je wel een betere random key krijgt als je die techniek van Rabin gebruikt.

[RRRobert]

...deze genereren zoveel data (45000 Gigabit per seconde) dat opslag ervan niet mogelijk is

Ooit zei er iemand op deze aarde dat 640Kb ook genoeg was voor iedereen... (no flame intended )

[spaceboy]

Als je toch (dus) moeilijk moet doen om eenmalig die afspraak (tussen Bob en Alice) zo geheim moet doen, zou ik zeggen: doe het dan echt veilig en vertel op die meeting/telefoongesprek de boodschap. Als er ECHT zulke geheime dingen zijn die zo'n encrypte vereisen zijn de kosten voor zo'n meeting (desnoods vliegen beide partijen 8 uur in een prive-jet naar elkaar toe) wel te dragen. Kortom: mijn standpunt is dat dit z'n doel voorbij schiet.

[Kenx]

Alice, Bob en Eve?
Zijn dit standaardnamen bij cryptologie of heeft Rabin ook Computer Networks van Tanenbaum gelezen?

[webster]

Zijn inderdaad standaard voorbeeldnamen.

Als je meer wilt weten over cryptografie en over dit drietal kan ik je absoluut het volgende boek aanraden (leest heel lekker en je hebt geen graad in de wiskunde nodig):

http://www.simonsingh.com/codebook.htm

(ISBN: 9029537434, zie ook bol.com)

[Verwijderd]

Dat zijn inderdaad standaard namen.

PS Studeer jij trouwens aan de UU? Dat boek heb ik vorig jaar namelijk ook door moeten spitten... of is het gewoon een populair boek?

[Kenx]

Ik zit op de TU Delft, erg populair boek blijkbaar.

[justice strike]

de vu, tanenbaum geeft hier les

[Zarc.oh]

Ik ook en zit op de HvA. Moet 'm dit jaar weer voor een deel leren, maar had 'm al verkocht

[Theswitch]

Op de KUN gebruiken ze ook Computer Networks. Maar niet voor Cryptografielessen, maar voor (jawel) computer networks

[Confusion]

Dit heeft een docent ons vorig jaar al op een college quantummechanica vertelt, toen hij de quantum versie van het one-time pad (ononderschepbare data, omdat onderschepping altijd opvalt) uitlegde. Weinig nieuws dus...

[Ruudjah]

Het verschil is dus, dat deze techniek met digitale apparatuur kan worden bewerkstelligd. Het duurt nog wel een aantal decennia voordat er quantumcomputers op de markt worden gebracht.

[Robinski]

Onbrreekbaar was toch onmogenlijk d8 ik

of hebt ik het nu helemaal mis?