Quantum Computing utfordret av sikkerhet, feilretting

Antallet og volumet av advarslene om en verden etter kvantekryptografi (PQC) øker, ettersom regjeringer, banker og andre enheter forbereder seg på et utslett av kompromitterte data og upålitelige digitale signaturer.

Nøyaktig når dette vil bli en reell trussel er fortsatt noe uklart, fordi det avhenger av fremgang i å utvikle robuste qubits. EN rapporterer av McKinsey & Co. anslår at innen 2030 vil rundt 5,000 kvantedatamaskiner være i drift, men maskinvaren og programvaren som trengs for å løse komplekse problemer vil kanskje ikke eksistere før rundt 2035. Andre sier at sammenheng mellom qubits og modulære arkitekturer kan få fart på ting.

I mellomtiden, overfor en truende trussel med en usikker tidsfrist, raser sikkerhetsmiljøet med å bygge opp forsvar. Hvis tidlig kryptografi handlet om symboler og substitusjoner, vil i hvert fall en del av moderne kryptografi handle om å bruke algoritmer for å bekjempe algoritmer.

"Kryptografer og matematikere har snakket om dette siden ca. 2017, som er da de først satte seg ned og sa: 'Dette er ille. Vi må oppdatere disse algoritmene,» bemerket Scott Best, seniordirektør, silisiumsikkerhetsprodukter hos Rambus. "Fantastisk nok, de har gjort store fremskritt."

Kraften til kvanteberegning kommer fra den rike fysikken i kvantedomenet, hvor det er superposisjon, når 0 og 1 er i samme tilstand.

"Tenk på en mynt som snur," sa Mohamed Hassan, leder for kvanteløsninger og planlegging for Nøkkelsikt, som allerede jobber med en kvante EDA-verktøy. "I stedet for å være hale eller hode, spinner den mynten faktisk i begge ender samtidig. Hvis du stopper den og måler den, vil den bli en av de to, og den vil kollapse kvantetilstanden. Samtidig er det kvanteforviklinger, der uansett hvor langt fra hverandre de er, hvis du måler en av dem, kan du gjette tilstanden til den andre.»

RSA, ECC
Når det gjelder de mest brukte krypteringsalgoritmene, er det først og fremst RSA (Rivest–Shamir–Adleman), En asymmetrisk form av kryptografi der en avsender koder en melding med en offentlig nøkkel som kan distribueres bredt, vel vitende om at bare en mottaker med den tilsvarende private nøkkelen kan dekode den. Dette betyr at selv om meldingen er kapret, er den fortsatt trygg mot dekryptering. Dens styrke stammer fra nøkkel lengde, eller antall biter i nøkkelen. Den gjeldende NIST-anbefalte RSA-nøkkellengden er 2,048-biter.

RSA bruker en kompleks formel for å finne sikre nøkler. I hjertet er den villedende enkle prosessen med å multiplisere to primtall, hvis produkt blir grunnlaget for ytterligere forbedringer for å lage nøklene. Det som gjorde RSA tilsynelatende bunnsolid trygt var vanskeligheten med "defaktorisering", dvs. å oppdage hva de opprinnelige hovedfaktorene var. Hvis et produkt er lite nok, kan de fleste defaktorisere det bare ved å kjenne til grunnleggende multiplikasjon, men hvis primtallene som brukes er store nok, kan det ta tusenvis av år å prøve å oppdage de opprinnelige faktorene.

Eller det var det man trodde. I 1994 opprettet MIT-matematiker Peter Shor en algoritme som løste det diskrete loggproblemet, som åpnet veien for å bryte RSA-kryptering. I hovedsak er diskrete logaritmer funksjoner som er det lett å utføre, men vanskelig å reversere, for eksempel defaktorisering. Ved å bruke Shors algoritme på en kvantedatamaskin, kan det å finne RSA-faktorer gå fra å være nesten umulig til bare et spørsmål om beregningstid og kraft.

"Den slags ting som kvantedatamaskiner er gode på er ganske begrenset," sa Michael Osborne, leder for Security Research Group ved IBM Research i Zürich, Sveits. "De er ikke veldig gode på det vi kaller eksakte problemer, fordi de er veldig sannsynlige i hvordan de presterer. Dessverre drar Shors algoritme nytte av kvantehastighet, fordi den i hovedsak passer til en annen måte å se på problemet på."

En annen populær type asymmetrisk kryptering er kryptografi av elliptisk kurve (ECC), som er basert på å manipulere elliptiske kurver. (Initialismen skal ikke forveksles for feilretting av koder, som er en del av informasjonsteorien.) ECC er både raskere og mer komplisert enn RSA, og underbygger blokkjedesikkerhet. Ikke desto mindre kan den beskyttende kompleksiteten til beregningene også oppheves av hastigheten til kvantedatamaskiner, fordi de deler matematiske røtter i Diffie – Hellman nøkkelutveksling.

I tillegg er det symmetrisk kryptering, som oftest brukes til autentisering. Symmetrisk kryptering bruker bare én enkelt nøkkel for både kryptering og dekryptering. Det mest kjente eksemplet er NSA-godkjent AES. Fordi de er basert på hasher, er de mindre sårbare for Shors algoritme, men potensielt sårbare for andre tilnærminger.

"Shors algoritme bryter stort sett alle de offentlige nøkkelkryptosystemene vi bruker i dag, som inkluderer RSA og Diffie-Hellman, og de elliptiske kurveversjonene," sa Dustin Moody, en matematiker og leder av post-kvantekryptografiprosjektet ved NIST. "Med de symmetriske algoritmene som AES, og hash-funksjoner som SHA2 og SHA3, trenger vi ikke å bytte ut algoritmen fordi de ikke er ødelagte. I verste fall bruker vi bare litt lengre nøkkellenker.»

Shors algoritme kan utføres enda raskere på grunn av forskning av Oded Regev, en professor ved Courant Institute of Mathematical Sciences ved New York University, som utvidet Shors arbeid med periodefunn. (En mer teknisk diskusjon kan bli funnet her..)

Høst nå, dekrypter senere
Disse sårbarhetene har ført til at angripere har tatt i bruk det som har blitt kalt en "Harvest Now, Decrypt Later" (HNDL)-strategi, der hackere bryter seg inn, stjeler så mye kryptert data de kan, og venter på at feiltolerante kvantedatamaskiner kommer på nett. slik at de kan samle inn informasjon det er verdt å handle på eller holde for løsepenger.

Til tross for bekymringene stiller Osborne spørsmålstegn ved om vi bør bekymre oss for HNDL-angrep i forkant av andre angrep, basert på den tradisjonelle tilnærmingen til sikkerhet, som er veldig pragmatisk. "Du kommer aldri til å kunne beskytte deg mot alle angrep, så du må prioritere både angriperkapasitet og angrepskostnad for å forstå den relevante risikoen," sa han.

Mens HDNL kan virke som en vag og fjern trussel, er det andre. Ta i betraktning Grovers algoritme, for eksempel, som kan brukes til å finne mønstre i data. Grovers algoritme kan realisere sin fulle kraft med kvanteberegning, og dermed bli et superladet søkeverktøy som kan gi mening med alle de dekrypterte innhøstede dataene. I likhet med Shor har den potensialet til å bryte kryptografiske nøkler.

Kvantefeil kan ta tid for sikkerhetstiltak
I dagens støyende kvante i middels skala epoke, kvantedatamaskiner har langt under antall qubits for å bryte RSAs anbefalte 2,048 nøkler. I 2019 var anslaget 20 millioner fysiske qubits, et tall som ofte utfordres. Sist vinter, kinesiske forskere hevdet å ha faktorisert heltall opp til 48 biter med 10 qubits. Det er imidlertid mange forskere skeptisk av arbeidet. Shor selv twitret, "Det er tilsynelatende mulige problemer med dette papiret."

Likevel tikker klokken. Hvor fort det tikker er ukjent. I likhet med sine klassiske kolleger er kvantedatamaskiner sårbare for både intern og miljøstøy, noe som kan føre til pålitelighetsproblemer. Det er uten tvil verre med kvantedatamaskiner, fordi støy kan føre til at qubits dekoherer (mister superposisjonstilstanden), gjør kvantetilstandene som er nødvendige for å opprettholde beregninger, og dermed ikke bare forringe ytelsen, som kan skje i en klassisk datamaskin, men ødelegger det helt.

Mange diskusjoner om antall qubits som trengs for å bryte kryptering er basert på logiske qubits, et langt mindre antall enn de fysiske qubitene som kreves for å få datamaskinen til å fungere. Alle påstander om antall qubits i en enhet må balanseres mot antall fysiske qubits som kan overleve dekoherens. De nåværende estimat er at 1 logisk qubit vil kreve 1,000 fysiske qubits, en overhead som alvorlig skjærer inn i anslag om når kvantedatamaskiner vil komme helt på nett.

For å presse feltet fremover har IBM, AWS, Google, og flere oppstartsbedrifter, som f.eks QuEra, Bøyningog Kvantinuum, streber etter å oppnå høye koherenstider gjennom forbedringer i feilretting. De fleste av forbedringene er basert på qLDPC-koder (quantum low-density parity check)., som i hovedsak er kvantenivåoppdateringer på klassiske Shannon-paritetssjekker. I forrige måned ledet IBM flokken, med en forsidehistorie Natur som brukte en qLDPC-variant for å redusere feilkorrigeringskostnader med 90 %.

«Artikkelen flytter datoen til venstre fordi det kreves færre logiske qubits for å oppnå det samme angrepet. Dette øker behovet for å gjøre seg klar, sier IBMs Osborne.

Legger enda mer press på sikkerhetsforskere, datoen kan gå enda lenger igjen, på grunn av forskning annonsert denne uken av Quantinuum og Microsoft. Sammen har de demonstrert "de mest pålitelige logiske qubits som er registrert med en feilrate som er 800 ganger bedre enn fysiske qubits," etter å ha kjørt mer enn 14,000 XNUMX qubits uten feil. Prestasjonen bruker ekstraksjon av aktivt syndrom, som gir mulighet for feildiagnose og korrigering uten å ødelegge logiske qubits, og dermed drastisk redusere 1/1000-forholdet. For all spenningen er det verdt å merke seg at papiret deres ikke har blitt fagfellevurdert.

Kvantemenasjeriet
I tillegg til deres eponyme algoritme, skapte Rivest, Shamir og Adleman også kryptografisk kjendisparet, "Alice og Bob," utførelsesformer av "A" og "B" brukt i ligninger. Det er en så insider kryptografi-vits at en fransk kvantestart-up tok det som navn. De Alice og Bob tilnærming reduserer feil ved å lage en mer robust qubit, som de kalte for den mest kjente katten i kvantefysikk. Kombinert med qLDPC feilretting, «katt qubits” er motstandsdyktige mot bit-flipping, og selskapet har vist de kan potensielt redusere antall qubits som trengs for å kjøre Shors algoritme med opptil 200 ganger.

AWS har også tatt i bruk cat qubit-ideen og lagt ut den egen tilnærming. Imidlertid, som alle qubits, er cat-qubits fortsatt sårbare for faseovergangsfeil.

Cat qubits er faktisk en del av et menasjeri av qubit-design. De fem beste, som beskrevet i detalj i en Science review paper, er superledende kretser, hvorav cat qubits er en delmengde. I forskjellige smaker er superledende kretser også foretrukket av Google, IBM og AWS. De neste fire tilnærmingene er kvanteprikker, fargesentre, fangede ioner (brukt av Quantinuum i deres samarbeid med Microsoft), og topologiske qubits, også foretrukket av Microsoft.

"Det er så mange maskinvareteknologier foreslått for å lage en kvantedatamaskin," sa Keysights Hassan. "Alle av dem har en felles funksjon, som er å ha et kvanteobjekt som et kodeelement for å gjøre beregningen - å fungere som qubit. For superledende qubits er det i utgangspunktet et Josephson-kryss. Det som er fascinerende er at superledende qubits under panseret er mikrobølgekretser.»

Variasjonen av qubit-ideer og den skreddersydde karakteren til arbeidet kan også kjøpe tid for sikkerhetsforskere. "Det er mange hull mellom verktøyene," sa Hassan. "Folk bruker punktverktøy og hjemmelagde arbeidsflyter for å fullføre designet, og det fører til lange kostbare utviklingssykluser og ikke-standardiserte ingeniørprosedyrer. Ting må flyttes fra området for forskning og utvikling til produksjon, og det er da EDA-verktøyene er nødvendige for å muliggjøre systematisk utvikling av disse systemene."

Hvis Microsoft, IBM, Alice & Bob eller andre spillere lykkes med feilretting, kan Schrödingers katt springe ut av esken som en tiger som kan rive i stykker asymmetrisk kryptografi. Imidlertid må oppmerksomhet fortsatt rettes mot fremgang i mengden fysiske qubits. I desember i fjor slapp IBM et gjennombrudd 1,000 qubit-brikke, fortsatt langt under de fleste legitime kodebrytende estimater.

mottiltak
Ikke desto mindre er ikke sikkerhetseksperter villige til å risikere at det hele er hype og at alt vil ordne seg. RSA har holdt en konkurranse for å finne de beste forebyggende tiltakene, bare for å oppdage at mange lovende tilnærminger fortsatt er sårbare.

"Det var 69 forslag som startet konkurransen," sa Jayson Bethurem, visepresident for markedsføring og forretningsutvikling hos Flex Logix. "Fem år senere er det fire igjen." De endelige resultatene forventes å bli offentliggjort en gang i sommer. Det er fortsatt noen hasj-baserte algoritmer som går fremover. De som har overlevd lengst er de der de bare fortsetter å øke nøkkellengden. Databanen blir bredere, så det gjør det selvfølgelig vanskeligere, fordi tro mot kraften til databanen tar det bare lengre tid å lage alle disse kombinasjonene."

Tilnærmingene som virker mest robuste mot kjente angrep samtidig som de tilbyr praktisk brukervennlighet er gitterbaserte algoritmer.

"Kvantedatamaskiner er ikke veldig gode på noen black-box-kombinatoriske problemer," sa IBMs Osborne. "Og gitter er et kombinatorisk problem. Alle kan forestille seg et todimensjonalt gitter. Hvis det er et vanlig gitter, og du velger et punkt et sted i ditt todimensjonale gitter, som er nær et av de andre punktene, men ikke på det, er det veldig intuitivt - du kan bare se det i hodet ditt. Men hvis du har et gitter som har hundrevis av dimensjoner, er problemet ekstremt vanskelig, fordi du må prøve ut så mange kombinasjoner for å finne ut hvilke av punktene i dette mangedimensjonale gitteret som er nær punktet ditt. Det er en kombinatorisk eksplosjon av ting du må prøve, som er det som gjør dette effektivt for kryptografi. Du kan prøve en brute force-tilnærming, men det ville ikke engang vært en dråpe i havet av det som kreves.»

De for tiden favoriserte gitterbaserte algoritmene er standardiseringer av eldre teknikker. "Det er en oppdatert nøkkelutvekslingsmekanisme kalt CRYSTALS-Kyber-algoritmen, og en oppdatert digital signaturalgoritme kalt CRYSTALS-Dilithium-algoritmen som nå er standardisert nok til at folk forventer at de kommer til å leve lenge, spesielt Dilithium," ifølge Rambus' Best.

Fig.1: Rambus sin tilnærming til postkvantesikkerhet. Kilde: Rambus

"Allikevel legger vi ikke alle eggene våre i gitterkurven," sa NISTs Moody. "Selv om gitterbasert kryptografi definitivt er den mest lovende, valgte vi fire algoritmer for standardisering. Tre av dem er basert på gitter. Det nest mest lovende området er det som kalles kodebasert kryptografi, som bruker feilkorrigerende koder. Det ligner i intuisjon på gitterbasert kryptografi. Kodene er representert ved hjelp av vektorer. Når du legger til to kodeord, får du et annet kodeord. Noe av det som skjer med feilrettingskoder er at hvis du får en streng med biter, er det en vilkårlig streng. Du ønsker ofte å finne kodeordet som er nærmest, fordi det er rettelsen du vil gjøre. Du antar at noen biter ble forvansket, men det er ment å være dette nærmeste kodeordet. Det er veldig analogt med situasjonen med gitterne. Så en idé for et kryptosystem er at du har en matrise som genererer koden din, du krypterer den for å skjule strukturen du designet den med, og du gjør den til din offentlige nøkkel, som er hva angripere må jobbe med. Mens du designer feilkorrigeringskoden, matrisen for å generere den, med en spesiell struktur som gjør at du kan dekode effektivt. Dette betyr at hvis det er en vilkårlig streng med biter i vektorrommet ditt, kan du dekode og finne det nærmeste kodeordet på en effektiv måte."

For selskaper som leter etter interne tiltak, understreker mange selskaper nødvendigheten av krypto-agility. "Store ASIC-produsenter og nettverksprodusenter, alle begynner å komme rundt til krypto-agility," sa Flex Logixs Bethurem. I fremtiden forventes alle produsenter å ha en kjernekrypteringsmotor som utfører mange av hovedfunksjonene og store behandlingen av disse komplekse algoritmene. "De må sannsynligvis også inkludere en mindre kryptografimotor som er tilpasningsevnen. Hvis du ikke har en form for fleksibilitet, på et tidspunkt, vil antakelsene du gjorde for å beskytte produktet ditt i dag sannsynligvis bli utfordret og brutt i fremtiden."

konklusjonen
Mens alle prøver å opprettholde sin optimisme om å temme PQC, oppfordrer Dana Neustadter, direktør for produktadministrasjon for IP-sikkerhetsløsninger hos Synopsys, designere til å tenke realistisk om hva det kommer til å bety å implementere disse løsningene.

"Risikoen for å introdusere feilaktige implementeringer og løsninger er veldig høy fordi dette er nye algoritmer som i seg selv er på vei," sa Neustadter. "Vi har nettopp sett med NIST at de var i ferd med å velge en gruppe algoritmer som skulle standardiseres, og i siste øyeblikk ble den spesielle algoritmen kompromittert. Hvordan overfører du hele systemet og enhetene til algoritmer som er helt annerledes enn det vi har å gjøre med i dag? Selv om dette er alternative algoritmer, betyr det ikke at de kanskje ikke er ødelagt, fordi de ikke ble studert nok.»

Den andre risikoen, bemerket Neustadter, er at nyhet og ukjenthet alene kan øke sannsynligheten for feilaktige implementeringer. "Hvis du ser tilbake i tid, er situasjonen lik da vi gikk fra symmetriske algoritmer, som DES til AES, bortsett fra at det vil være en annen størrelsesorden mer kompleks og ta år. Vi går over til helt nye typer algoritmer der du håndterer større nøkler, noe som påvirker systemminnets tilgjengelighet. Du må ha smidighet fordi algoritmer endres. Det kommer ikke til å være stabilt over natten. Til slutt kan disse problemene løses i tide, men det er en alvorlig trussel - i hvert fall for en stund."

Andre er enige, og advarer. "Det er vår profesjonelle forpliktelse, kanskje vår patriotiske forpliktelse, å presse innføringen av kvantesikker kryptering," sa Rambus' Best. "Denne teknologien kommer."

Relaterte Stories
Quantum Plus AI utvider trusselen om cyberangrep
Postkvantekryptografi må brukes nå for å hindre hackere i å dekode dagens data når kvantedatamaskiner blir tilgjengelige.

Quantum Computing: Topp 5 spørsmål besvart
Kvantefeildeteksjon, undertrykkelse og korrigeringsstrategier er avgjørende for å realisere feiltolerante kvantedatamaskiner.

Referanser
Pfeiffer, S. Kinesiske forskere: RSA kan brytes. Andre: Ikke få panikk! Hjelp Net Security Åpnet 28. mars 2024, https://www.helpnetsecurity.com/2023/01/25/chinese-researchers-rsa-is-breakable-do-not-panic/

Bravyi, S., Cross, AW, Gambetta, JM et al. Høyterskel og lav overhead feiltolerant kvanteminne. Nature 627, 778–782 (2024). https://doi.org/10.1038/s41586-024-07107-7

Lescanne, R., Villiers, M., Peronnin, T. et al. Eksponentiell undertrykkelse av bit-flips i en qubit kodet i en oscillator. Nat. Fys. 16, 509-513 (2020). https://doi.org/10.1038/s41567-020-0824-x

• SEO-drevet innhold og PR-distribusjon. Bli forsterket i dag.
• PlatoData.Network Vertical Generative Ai. Styrk deg selv. Tilgang her.
• PlatoAiStream. Web3 Intelligence. Kunnskap forsterket. Tilgang her.
• PlatoESG. Karbon, CleanTech, Energi, Miljø, Solenergi, Avfallshåndtering. Tilgang her.
• PlatoHelse. Bioteknologisk og klinisk etterretning. Tilgang her.
• kilde: https://semiengineering.com/quantum-computing-challenged-by-security-error-correction/