bloghoved ole tange

Kryptering og kvantecomputere

Kvantecomputere er en fantastisk teknologi, som er under udvikling i disse år. Kvantecomputeren er en specialiseret computer, som kan løse visse problemer uhyggeligt hurtigt, men som er ubrugelig som en almindelig computer.

Strøm til køling

Vi kommer næppe til at se kvantecomputere lige så udbredte som PC'er. Kvantecomputere kræver køling ned til under -273 C (nemlig nogle få millikelvin). Derfor kommer vi nærmere til at se dem i de samme miljøer, som benytter supercomputere i dag. En kvantecomputere fylder i dag svarende til 3-4 rackskabe og bruger 25 kW strøm (hvilket er i samme størrelsesorden som 3-4 rackskabe fulde af servere). Strømmen bruges i stort omfang til at køle med, og med mindre der kommer et gennembrud inden for køling, så kommer det næppe til at ændre sig væsentligt – heller ikke selvom regnekapaciteten øges kraftigt.

Symmetrisk og asymmetrisk kryptering

De fleste interessante problemer, som kvantecomputeren i teorien kan løse, er ikke direkte relevante for almindelige borgere, men kun interessante i forskningsmiljøer.

Et af de få problemer, som kvantecomputere kan løse og som har relevans for mange borgere, er at bryde kryptering.

Når du tilgår en krypteret webside, så benytter du to former for kryptering: asymmetrisk kryptering og symmetrisk kryptering. De hænger lidt sammen som en to-trinsraket: Du kan ikke nøjes med den ene, men skal bruge begge former.

Der findes forskellige algoritmer for asymmetrisk kryptering. Måske har du hørt om: RSA, elliptiske kurver eller Diffie-Hellman. Det samme gælder for symmetrisk kryptering. Her hedder algoritmerne bl.a. AES, Triple-DES og Blowfish.

Kvantecomputere kan gøre det en smule hurtigere at bryde symmetrisk kryptering, men det er nemt at sikre sig imod ved blot at lade krypteringsnøglen være længere. De bedste angreb på symmetrisk kryptering med en klassisk computer er i størrelsesorden O(2^n), hvor n er antal bits i nøglen; med kvantecomputeren er det bedste angreb i størrelsesorden O(sqrt(2^n)), så hvis man fordobler nøglelængden til 2n, så vil det bedste angreb være på O(sqrt(2^(2*n))) = O(sqrt(2^n * 2^n)) = O(2^n) - altså svarende til et angreb for en klassisk computer på en nøgle med n bits.

Værre er det med de mest udbredte asymmetriske krypteringsalgoritmer: De kan brydes helt, for her er det bedste angreb i størrelsesorden O(n^3) for en nøgle med n bits. Og hvis blot den ene del af to-trinsraketten er brugt, så kan hele beskeden dekrypteres og læses.

Af den grund forsker man i at udvikle asymmetriske algoritmer, der ikke kan brydes af kvantecomputere. I tekniske fora kaldes dette for post-quantum-cryptography eller PQCrypto. I dag er udviklingen så langt, at man har udviklet algoritmer, som ser ud til at kunne modstå kvantecomputere. Desværre er koster de mange computerressourcer at bruge: Nøglerne fylder 1000 gange mere eller hastigheden er 100 gange langsommere. Derfor forskes der i, hvordan man kan lave sikre algoritmer, der kræver færre computerressourcer.

Allerede i dag er PQCrypto-folket kommet med anbefalinger, som de betragter som konservative. De kan sagtens køre på laptops i dag, men er ikke klar til smartcards med 8-bit processorer – dertil kræver de simpelthen for meget beregningskraft og lagerplads.

Illustration: https://hyperelliptic.org/tanja/vortraege/tpm-ws.pdf

Tidshorisont: mindst 10 år

Kvantecomputere kan groft grupperes i to grupper: Quantum Annealing computers og Universal Quantum computers. Det er kun Universal Quantum computers, der kan knække kryptering, også selvom Quantum Annealing computers kan have langt større beregningskraft.

Kvantecomputere har i disse år nået Quantum Supremacy. Det betyder helt simpelt, at der findes mindst een opgave, som en kvantecomputer kan udregne hurtigere end en klassisk computer. Det betyder med andre ord ikke, at alle opgaver, som en klassisk computer kan udregne, kan udregnes hurtigere på en kvantecomputer. At Quantum Supremacy er nået er et interessant og væsentligt skridt - men primært af akademisk interesse.

Beregningskraften af en kvantecomputer måles i qubits. De største Universal Quantum computers er vokset fra 9 qubit i 2016, over 17 qubit i 2017 til 72 qubits i 2018, mens Quantum Annealing computers findes op til 2000 qubits. De ser ud til at vokse eksponentielt, så forvent at de er dobbelt så store om 1-2 år.

For at kunne løse reelle problemer af forskningsmæssig værdi skal computeren have 50-100 qubits, og hvis computeren skal kunne bryde moderne kryptering, skal den både være en Universal Quantum computer og have over 1000 qubits. For at knække 4000 bit RSA skal maskinen have 5*4000 qubits, og hvis de 72 qubit fordobles hvert år, så taler vi om tidligst 2028, før det bliver et problem for 4000 bit nøgler, og tidligst 2029 før 8000 bit nøgler er i fare. Med til historien hører også, at qubitsene skal være uden støj, og det er ikke uproblematisk at holde dem støjfri - så det kan give os endnu længere tid, før problemet indtræder.

Så en kodebrydende kvantecomputer er nærmer sig, og derfor er det godt vi allerede i dag har algoritmer, der kan beskytte os mod dekryptering af kvantecomputere – det koster blot nogle flere computerressourcer.

Quantum cryptography

Kvantemekanik kan også bruges til kryptering, men det er i praksis langt mindre brugbart: Du skal kunne sende uforstyrrede fotoner direkte til modtager - altså ikke noget med routere og repeatere undervejs. Det betyder, at du enten skal have line-of-sight eller et fiberkabel til hver modtager eller en satellit til at lave quantum key distribution.

Det er teoretisk interessant, men bliver næppe praktisk brugbart som vores primære form for kryptering.

Fremtidig dekryptering

NSA har siden 2. verdenskrig opsamlet krypteret materiale. I de seneste år er computere blevet så kraftige og dekrypteringsalgoritmerne så gode, at man kan dekryptere de 50-60 år gamle beskeder. Det er rimeligt at forvente, at hverken NSA eller andre spionorganisationer er stoppet med at indsamle krypteret materiale, som de ikke kan dekryptere i dag. Har du materiale, som skal være hemmeligholdt i 50 år fremover, så vil det nok være en god ide allerede i dag at overveje, om en kodebrydende kvantecomputer vil være en realitet om 10 år, og i så fald benytte algoritmer, der kan modstå en kvantecomputeren.

Forbered dig allerede nu

Hvis du i dag udvikler ny kode, der afhænger af kryptering, så sørg lige for at bruge et library, der har support for PQCrypto, så det bliver nemt at opgradere senere.

Kommentarer (6)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Peder Simonsen

Rigtig fin artikel, god og informativ der er uden tvivl nogle udfordringer i fremtiden som gør nutidens kodning "svagere".
Men sådan har det jo hele tiden været igennem tiden, derved ment at computernes formåen og hastighed stiger år for år.
Nu har man så fundet på noget nyt, kvante computere.

Fint man i artiklen skriver at en løsning kan være at "forlænge" vores nuværende nøgler men det også kræver mere regnekraft at bryge en sådan beskyttelse, og det er jo et lille dilemma. Sikkerhed vs hastighed.
Men mon ikke at vi over de næste 10 år stadig vil få hurtigere computere med flere kerner og at krypteringen måske til den tid kan håndteres bedre ;-)

Men usanset hvad... så skal folk være klar over en meget vigtig ting når det kommer til kryptering/koder...:
1). For det første skal man være være af meget særlig interesse for at nogen stat/banditter lige frem vil påbegynde at bryde dine krypterede data hvilket selv idag kræver enorme resource og supercomputere.
Så man dekryptere ikke lige flere millioner menneskers dit og dat hvis ikke man har en årsag... ELLER at f.eks. NSA har en hemmelig måde at bryde f.eks. AES256 på.. Jeg kan dog ikke forestille mig de har en sådan metode for hvis en sådan fandtes så ville man jo nok ikke selv bruge den type kryptering. Det er nok mere sandsynligt med software/hardware bagdøre som kan bruges eller indsamling af koder.

2). huske på at det er MEGET nemmere at STJÆLE din kode, end det er at bryde den.
Jeg siger bare det globale overvågnings system, app's, software osv. hardware, bugs / software sikkerheds problemer som gør en angriber i stand til at indsamler kodeord for at bruge dem senere hen.
- Da jeg var soldat fandt man i en af Natos HQ kontor spion udstyr i form af usb kabler som kunne sende "wifi" signaler ud af huset til spioner som kunne læse med. OG printere hos div. militære enheder havde USB porte hvor man sågar via menuen bede printer om at lave backups og putte det på en usb nøgle.. hmmmm
Tænk engang, hvornår har en hvilket sm helst virksomhed reelt set giddet at undersøge det usb keyboard som du bruger, eller mange andre ting og sager... Og hvem har giddet at holde lidt øje med rengørings personalet som kommer og kan "afhente" data ved at udskifte en lille dims i usb stikket.
Er i sikre på jeres IT udstyr ikke er manipuleret/udskiftet ?
( f.eks "nye"usb kabler som kan sende data ud af huset )

Jeg siger bare, det er meget nemmere at stjæle koden end at hacke sig ind.. ( eller lave mand in the middle angreb f.eks. på et hotel hvor mange forretnings rejsende kommer til når de vælger at koble på det forkerte netværk og ikke bruger en krypteret VPN forbindelse. ).
Man kan gøre dette reelt set over alt.

I 80-90erne brugte man iøvrigt metoder så som at rode i affald fra private/virksomheder, eller kom til at tabe en diskette/usb pen i håbet om nogen ville samle den op og sætte den i deres computer.... = adgang.

  • 3
  • 0
Ole Tange Blogger

Fint man i artiklen skriver at en løsning kan være at "forlænge" vores nuværende nøgler men det også kræver mere regnekraft at bruge en sådan beskyttelse, og det er jo et lille dilemma. Sikkerhed vs hastighed.

For AES er performance ikke en reel flaskehals: Moderne CPUer kan kryptere flere GB/s, og mange har idag en hardware kryptochip, så performance-forskellen mellem AES128 og AES256 er 10-20%: https://github.com/mdaxini/howto-openssl/wiki/OpenSSL-Cipher-Speed

Så med mindre man har en virkelig god grund, så ville jeg opgradere AES128 til AES256 allerede ved næste softwareopdatering.

Men mon ikke at vi over de næste 10 år stadig vil få hurtigere computere med flere kerner og at krypteringen måske til den tid kan håndteres bedre ;-)

Dette vil dog ikke hjælpe, hvis vi ikke skifter de asymmetriske algoritmer. Hvis vi for antager, at kvantecomputere får dobbelt så mange qubits hvert år; så skal vi fordoble nøglelængden på vores asymmetriske nøgler hvert år.

Hvis du har prøvet at generere en 16000-bit RSA-nøgle (det har jeg), så ved du, at det tager langt mere end 16 gange så lang tid som at lave en 1000-bit RSA-nøgle. Hvis jeg husker ret, så tog 1000-bit i størrelsesorden 0.1 sek, mens 16000-bit tog 1000 sek.

  • 2
  • 0
Torben Mogensen Blogger

Jeg er lidt skeptisk overfor universelle kvantecomputere, der kan bryde praktiske koder. Ikke alene skal der som artiklen siger bruges mange qubits uden støj, men de skal også kunne holde til et stort antal operationer, før kvantetilstanden kollaper til en klassisk tilstand.

Man har i dag under 100 qubits, de er ikke støjkorrigerende, og de kan kun tåle til få hundrede operationer, før kvantetilstanden kollapser. Dette er meget simple operationer: Operationer på et qubit eller en negation af et qubit kontrolleret af et naboqubit, og den sidstnævnte giver større risiko for kollaps, og større risiko for forkerte resultater (støj) så dem kan du kun lave få dusin af.

For at lave støjkorrektion repræsenterer man et "virtuelt" qubit med flere tusinde fysiske qubits, der populært sagt holder hinanden i skak. Det betyder, at de nuværende kvantecomputere ikke engang har nok qubits til et enklet støjkorrigerende qubit.

Så jeg tror, at der går langt mere end ti år, før kvantecomputere kan knække dagens koder. Og måske sker det aldrig -- det er absolut tænkeligt, at det ganske enkelt er umuligt at holde koherens mellem et stort antal entangled qubits over et større antal operationer.

  • 2
  • 0
Peter Valdemar Mørch

Så vidt jeg husker gør man så ikke typisk det at man vælger en tilfældig nøgle som man så krypterer asymmetrisk og sender og derefter sender man resten af beskeden krypteret symmetrisk med denne nøgle?

Så betyder det vel næsten intet at den asymmetriske del performer dårligere / bruger flere computerressourcer da den kun skal bruges til at kryptere nogle få kb uanset beskedens længde.

  • 0
  • 0
Ole Tange Blogger

Så vidt jeg husker gør man så ikke typisk det at man vælger en tilfældig nøgle som man så krypterer asymmetrisk og sender og derefter sender man resten af beskeden krypteret symmetrisk med denne nøgle?

Præcis - det er to-trins raketten.

Så betyder det vel næsten intet at den asymmetriske del performer dårligere / bruger flere computerressourcer da den kun skal bruges til at kryptere nogle få kb uanset beskedens længde.

Performance består af to dele: Initialisering (som er fast - uanset længde af data) og dekryptering af bytestrømmen (som kan variere).

Din betragting er korrekt for dekryptering af bytestrømmen.

Men uanset hvor lille bytestrømmen er, så er der også initialiseringen. Og den kan godt være ret ressourcekrævende.

  • 3
  • 0
Michael Cederberg

1). For det første skal man være være af meget særlig interesse for at nogen stat/banditter lige frem vil påbegynde at bryde dine krypterede data hvilket selv idag kræver enorme resource og supercomputere.

Husk på at du bare skal bryde nøglen en gang - så kan man bryde alt din kommunikation. Ideen med public-key kryptering er netop at man en gang for alle udveksler nøgler og så bruger dem til assymetrisk kryptering derefter. Set i lyset af hvor mange penge NSA investerer i aflytning, så synes det åbenlyst at de har en interesse i af udbrede denne teknologi. Stykprisen for q-computere bliver sikkert lavere når man køber 1000.

Vigtigere er det at public-key cryptografi også bruges til digital signatur. Hvis jeg bryder din signatur, så kan jeg forfalske et dokument der siger at vi indgik en aftale i 2005 om at jeg i dag kan købe dit hus for kr. 1.00.

2). huske på at det er MEGET nemmere at STJÆLE din kode, end det er at bryde den.

Ja men det er kun fordi koderne er så gode. Under første og anden krig brød man koder fordi det var det nemmeste. Man skal således sikre at kryptering ikke bliver det svageste led i kæden. Men i øvrigt er jeg enig i at den slags sikkerhed er undervurderet og at det i store netværk i praksis er umuligt at undgå den slags angreb du beskriver.

Så jeg tror, at der går langt mere end ti år, før kvantecomputere kan knække dagens koder

Jeg har ingen insight, men jeg har svært ved at forstå hvorfor flere store amerikanske virksomheder investerer massivt i dette område hvis horizonten er så lang. Jeg medgiver at specielt IBM traditionelt har beskæftiget sig med grundforskning men initiativerne synes at gå langt videre end grundforskning.

Så betyder det vel næsten intet at den asymmetriske del performer dårligere / bruger flere computerressourcer da den kun skal bruges til at kryptere nogle få kb uanset beskedens længde.

For RSA har man traditionelt valgt det offentlige primtal til at være lille for at reducere den ene del af opgaven. Store nøglelængder stiller krav til hardwaren som den ikke altid kan håndtere.

Hvis du fx. beder din home-router om at køre openvpn med en 8192 bit nøgle, så vil du opdage at sessions tager lang til at sætte op.

  • 0
  • 0
Log ind eller Opret konto for at kommentere
IT Company Rank
maximize minimize