"Már ma is törhető az RSA titkosítás?"

HUP
A 24 kínai kutató által tavaly karácsonykor megjelentetett publikáció alapvető állítása, hogy sikerült találniuk olyan algoritmust, amely lehetővé teszi a 2048 bites RSA kulcsok törését még a ma elérhető, relatíve kis teljesítményű kvantumszámítógépek számára is. Abban nincs igazán újdonság, hogy a kvantumszámítógépek úgy általában kockázatot jelentenek az olyan, a biztonságos internetes kommunikációt szavatoló, kriptográfiai eljárások megbízhatóságára nézvést, mint az RSA nyílt kulcsú titkosító, vagy a Diffie-Hellman kulcscsere algoritmus. Ezen eljárások ugyanis olyan matematikai problémán alapulnak, melyek a hagyományos számítógépekkel a gyakorlatban megoldhatatlanok, viszont kellően nagy kapacitású kvantumszámítógépek esetén akár néhány óra alatt is megoldhatóak. A kellően nagy ez esetben 20 millió kvantumbit, a kvantumszámítógépek esetén a bit megfelelője. Ezzel a 20 milliós értékkel csupán annyi a probléma, hogy az IBM tavaly novemberben bejelentett – egyszersmind a legnagyobb ma ismert – kvantumszámítógépe ebből a 20 millió kvantumbitből mindösszesen 433-at képes felmutatni. Nem túlzás tehát azt állítani, hogy a kínai kutatók egy Grand Canyon méretű szakadék áthidalására tettek kísérletet. De sikerült?

A teljes cikk itt olvasható.

( laysoft v | 2023. 01. 16., h – 13:26 )

Szerkesztve: 2023. 01. 16., h – 14:28

Hiszem, ha látom. Valami ilyesmire gondolok mint bizonyíték, amit ki tudok próbálni.

A tudomány és a hit vitája akkor eldőlt, amikor villámhárítót szereltek a templomokra.

( laysoft v | 2023. 01. 16., h – 13:44 )

Elolvastam a hwsw cikkét is. "sikerült egy 48 bites (15 számjegy) számot faktorizálniuk"

Anno, mikor egy Amiga-s CD író szoftver RSA alapú védelmét törtem meg, online faktorizálóval sikerült megtalálnom a két prímet:

https://www.dcode.fr/prime-factors-decomposition

Íme egy egy példa, két prím szorzata, 41 digit:

69952303111011470828287386386995615578841

Kb. fél másodperc alatt köpi a két 22 digites prímet:

256257538298748946109

272976567149646185549

Össze lehet szorozni, kiadja az eredményt. Szóval a 15 digites szám faktorizálása elég karcsú...

A tudomány és a hit vitája akkor eldőlt, amikor villámhárítót szereltek a templomokra.

Ok, vigyük tovább!

Az "Elolvastam a hwsw cikkét is." mondatomban az "is" szóval csak azt szerettem volna kifejezni, hogy EZEN KÍVÜL elolvastam a HWSW CIKKÉT IS, nem azt hogy egy másik cikket IS.

(hwsw) cikkét is

helyett

(hwsw cikkét) is.

Vagyis nem állt szándékomban lecikkezni egy hírt. Aminek persze nem Te vagy a szerzője, hanem a hup... :)

A tudomány és a hit vitája akkor eldőlt, amikor villámhárítót szereltek a templomokra.

( rpsoft v | 2023. 01. 16., h – 15:51 )

Elég nagy felhajtás és vita van körülötte. Ha jól értem, az vele a gond, hogy arról nem szol a cikk, hogy milyen gyorsan megy a dolog, így a jelentősége inkább elméleti. Megmutatja, hogy lehet erre a feladatra hibrid klasszikus-kvantum-algoritmust írni, kevés bites kvantumszámítógépre, de az egyelőre meg nem világos (ill. mások szerint nem igaz), hogy ez gyorsabb, mint teljesen klasszikus algoritmussal megoldani a feladatot.

Nekem az a fura, hogy QAOA-t hasznal, mert az egy kozelito algo. Ugy remlik, nem garantalt, hogy megtalalja a minimumot, csak nagyon jo kozelitest ad ra. Ok is irjak a cikk vegen, hogy mintavetelezni kell a QAOA utan, "de az nagy valseggel a minimalizao allapot". Ami lehet igaz 10 qbitnel, de 100nal is? 

( dotnetlinux | 2023. 01. 16., h – 16:29 )

Bankban dologozom, teszteljük a 4096os RSA-t új projektekhez, biztos ami biztos. Azt tudjuk hogy az ECC-ket is törik-e vagy csak sima RSA-t?

Szerintem olyan cégeknek, intézményeknek, ahol az adatok titkossága tényleg fontos, elengedhetetlen lenne már egy quantum-crypto szakértő véleményének a kikérése. Lehet (sőt, nagyon valószínű), hogy most még nem törnek semmit. A közeljövőben viszont már itt lesz a NISQ (noisy intermediate-scale quantum) computer (nagyságrendileg ezer qubit, egyelőre hibajavítás nülkül), és lesznek dolgok, amit meg lehet csinálni rajtuk hibrid klasszikus-kvantum eljárásokkal. A kicsit távolabbi jövőben pedig könnyen lehet, hogy lesznek tényleg nagy kvantumszámítógépek.

Biztos van nagyon sok titkosított adat, ami most fontos, de tökmindegy, hogy ki olvassa majd el tizenöt év múlva (pl. az addigra lejáró jelszavak), de van olyan is, ami akkor is titkos kell maradjon (személyes adatok, pénzügyi, orvosi). Azokat pedig el lehet most rakni, és majd akkor elolvasni. Lehet majd koppanni, mint amikor a VENONA projektben az amerikaiak és az angolok a negyvenes évek végén-ötvenes évek elején megfejtették a szovjet követség 30-as években lehallgatott táviratait, aztán egyszer csak letartóztatták a Rosenberg-házaspárt, Klaus Fuchs-ot, etc.

Tevalyi poszt: https://marcofranssen.nl/upgrade-your-ssh-security

"Ed25519 | It’s the most recommended public-key algorithm available today! It has a 256-bit length and gives equal if not better protections as a 4096-bit RSA key. |"

En spec 4096bites rsa kulcsot hasznalok, es egyelore nem parazok, hogy kinyitjak.

"Nem akkor van baj amikor nincs baj, hanem amikor van!"
Népi bölcsesség

Azt, hogy ha fontos nekem a titkosítás, akkor utána kell néznem, hogy mik azok az algoritmusok, amik megbízhatók. Ha az is fontos, hogy amit titkosítok, az 10-15-20 év múlva is titkos legyen, akkor már most olyan algoritmust kell használnom, amit kvantumszámítógéppel sem lehet olyan könnyen megfejteni. Ez valószínűleg nem az RSA.

Figyelni kell nem csak a kvantumszámításra, hanem a kvantumkommunikációra is. Az előbb fog működni, mint a kvantumszámítógép (igazából az már most is működik, csak még nem lett belőle üzleti termék), és megoldás lehet ezekre a problémákra.

Ha az is fontos, hogy amit titkosítok, az 10-15-20 év múlva is titkos legyen,

Ez mindig is csak egy vágy volt, de ezt soha nem lehet garantálni.

 

Mi van ha holnap megtalálják/publikálják a jelenleg használt, és "mindenki" által atombiztosnak vélt algoritmus/implementáció hibáját? azonnali bukó.

A titkosítás - önmagában - rövidtávú stratégia. pont.

 

szerintem.

zrubi.hu

Jah, idezet innen: "A vegtelen ciklus is vegeter egyszer, csak kelloen eros hardver kell hozza!"

Ezen alapon bele se kezdj!.. Azer' megneznem, amikor a te sajat kulcsodat kvantumszamitogeppel fogjak torogetni.

"Nem akkor van baj amikor nincs baj, hanem amikor van!"
Népi bölcsesség

Nem azt mondtam, hogy az én saját levelezésemet kell quantum resistant eljárással kódolni. Hanem azt, hogy egy bank vagy egy ország diplomáciája már nem engedheti meg magának, hogy ne kövesse ezt a témát, ne kérjen az ügyben külső tanácsadót. Ez a kvantumszámítógép meg azért nem olyan, mint a végtelen ciklus. Ez nagy eséllyel 10-20 éven belül itt lesz.

Nyilván nem lehet olyan pontosan megbecsülni az ilyesmiket. Nekem az egész fúziós community gyanús is, abban a témában legközelebb akkor hiszek el valamit, ha nem kell odavezetni a villanyt. De más jóslatok meg bejöttek, pl. van gravitációshullám-obszervatórium. Azt sem volt könnyebb megcsinálni, és azért odaért az emberiség. Nem tudom, hogy a kvantumszámítógép esetén hogy állnak a különböző csoportok a saját régebbi roadmapjeikhez képest, de gyanítom, hogy nem olyan szarul, mint a fúzió.

Én valószínűnek tartom, hogy előbb-utóbb menni fog a fúzió, de azokkal a becslésekkel kapcsolatban, hogy mikor, szkeptikus vagyok. Nem elég bátrak kimondani, hogy "papuskám, ez egy nagyon nehéz téma, nem tudjuk, mikor lesz kész, de azt igen, hogy meg fogja érni".

Azokat pedig el lehet most rakni, és majd akkor elolvasni.

Kérdés, hogy a perfect forward secrecy vajon mennyire van kitéve a kvantumszámítógépes támadásoknak? PFS esetén _elvileg_ hiába capture-ölted le a titkosított forgalmat most, ha ki is kerül a kuccseréhez használt private key (ez az ahol RSA játszik), akkor sem tudod a szimmetrikus session key-t (amit az AES használ) megfejteni.

Régóta vágyok én, az androidok mezonkincsére már!

Nem véd ellene. Ugyanis a kvantumszámítógépes támadás arra jó, hogy meggyorsítja a brute-force támadást.

A PFS az ellen véd, hogy ha nem elég egy kulcsot megtörni egy üzenetváltásnál, a többit is meg kell törnöd mindig egyesével, mert minden üzenetnek más kulcsa van. Magyarán azt nehezíti meg, hogy oké, te megszerzed a küldő fél kulcsait, attól még meg kell törnöd az egyes üzenetkulcsokat egyesével.

De ha brute force-szal meg tudod törni a kulcsokat gyorsan, akkor mindegy, hogy 1 vagy 100 kulcsot kell megtörnöd.

Ez ellen csak azzal lehet védekezni, hogy a kvantumszámítógépes képességek is kevesek legyenek a brute force támadáshoz (a hatásos brute force ellen semmi nem véd), azaz olyan algoritmus, aminél nem párhuzamosítható jól a kulcs megtalálása. 

De ha brute force-szal meg tudod törni a kulcsokat gyorsan, akkor mindegy, hogy 1 vagy 100 kulcsot kell megtörnöd.

Nem mindegy. A gyakorlatban egy tamadas olyan, mint egy munka: a tamado nezi az ar-ertek aranyt.

Persze ha tenyleg 10 masodperc megtorni egy kulcsot egy par ezer euros gepen, akkor ez nem gond. De ha egy par szazmillios gepen kerul fel oraba, akkor csak akkor fogjak megtorni a 100 kulcsot egyesevel, ha tenyleg nagyon fontos.

azt nehezíti meg, hogy oké, te megszerzed a küldő fél kulcsait, attól még meg kell törnöd az egyes üzenetkulcsokat egyesével.

Igen, pont ezért releváns a kérdés. Tudtommal az AES közvetlen törésére nincs hatékony kvantum algoritmus (egyelőre), azt hiszem a legjobb amit elmélteileg, papíron tudnak Grover algoritmusával, hogy a komplexitást négyzetgyökére csökkentik. Ezzel egy AES-256 redukálódna egy AES-128 szintjére, ami még mindig nagyon sok brute-force támadáshoz.

Viszont az RSA-ra van a Shor módszer, így nem kéne brute force-olni az AES kulcsát.

A kérdés, hogy lehetséges-e kvantum-támadás a Galois Counter Mode algoritmus ellen. A TLS1.2 és 1.3-ban a GCM-es ciphersuite-ok adnak perfect forward secrecy-t az RSA kulccseréhez.

Vagyis elméletben ha az AES és a GCM is ellenáll a kvantum támadásoknak, akkor az RSA-t hiába tudják feltörni, a passzívan rögzített sessionök nem lesznek megfejthetőek. Man in the middle támadás persze lehetséges lesz, de "capture now, crack later" szempontból nem releváns.

Régóta vágyok én, az androidok mezonkincsére már!

A Grover-algoritmus az mondjuk nem AES-specifikus, bármely f függvényre működik: n méretű input téren sqrt(n) próbálkozásból megmondja, hogy melyik x input állítja elő az y outputot. Ez megy bármire, nem csak AES-re.
Szóval az még kutatás kérdése, hogy AES-re találnak-e kvantum algoritmust. Jelenleg nem ismert ilyen. De csak jelenleg.

Bankban dologozom, teszteljük a 4096os RSA-t új projektekhez

:) 

Bankok nem a bleeding edge technológiáikról híresek, na de azért az RSA 4096 már ~20 éve is elérhető volt :)

 

De gondolom nem maga az RSA a kérdés, hanem a körétákolt custom - de mission critical -  'abandonware' vackok  ;)

zrubi.hu

azért az RSA 4096 már ~20 éve is elérhető volt

Jah, aztán 10-12 éve még sok windows-os szerver termék (mikroszoftos) is dobálta az elborult, hetekig troubleshootolt animáliákat, amikről a redmondi developer team bevonása után derült ki, hogy PKI hibára volt visszavezethető: az egyik helyen a RootCA certjében olyan RSA algoritmus volt, amit nem sokan használtak, ezért attól elhalt Exchange, OCS stb.

Ugyanígy a 2048-as RSA kulcsok miatt is volt először elhasalások 10-15 éve is. 4096-al is biztos lesznek ilyenek.

( DieHappy | 2023. 01. 16., h – 20:40 )

Ha ez igaz, akkor az tenyleg attores. Bar az IBM aktualis gepe 433 qubites, de a depth nem tul meggyozo rajta, az rajta mert quantum volume kisebb, mint a 127 bites gepeiken... A depth azt jelenti, hogy hany muveletet lehet elvegezni egy qubiten, amig meg zajmentes, koherens a vegeredmeny, a volume a qubit es a depth valamilyen szorzata (mindenki maskepp szamolja). Az IBMnel bitek konnektivitasa sem tul nagy, de lehet a cikk altal minimalisan megkoveletelt LNN-t sem eri el (a Kn, teljes konnektivitastol merfoldekre van), mert harom processzor oszekotesevel ertek el. D-wave gepeknek jo az bitszama es a konnektivitasa, de ugye ott nem lehet futtatni a sem a QAOA-t, sem mas algot, csak annealinget (gy.k. minimalizalast). 

( YleGreg | 2023. 01. 18., sze – 08:55 )

Igazabol engem csak az erdekel, hogy a quantum szamitogepeket meddig kell meg fejleszteni, hogy fusson rajta a Doom? :-)