image

TU Eindhoven doet voorstellen voor toekomstige encryptie

zaterdag 23 december 2017, 12:37 door Redactie, 10 reacties

De Technische Universiteit Eindhoven heeft verschillende voorstellen gedaan voor toekomstige encryptie die de komst van kwantumcomputers moet overleven. Deze week publiceerde het Amerikaanse National Institute of Standards and Technology (NIST), een organisatie die de cryptografische standaarden vaststelt die wereldwijd worden gebruikt, een lijst met 69 voorstellen van toekomstige encryptie.

Zes van deze voorstellen zijn ingediend door onderzoekers van de Coding Theory en Cryptology onderzoeksgroep van de TU Eindhoven. De afgelopen jaren is er veel onderzoek gedaan naar kwantumcomputers, die volgens experts grote gevolgen voor de huidige encryptie-algoritmes zullen hebben. Veel van de cryptosystemen die momenteel in gebruik zijn kunnen namelijk doorbroken worden door de rekenkracht van kwantumcomputers. Om die reden is het NIST gestart met een langlopend proces om te komen tot één of meer kwantumbestendige public-key cryptografische algoritmen.

Cryptograaf Andreas Hülsing van de TU Eindhoven is de leider van één van de voorstellen met de naam SPHINCS+, dat zich richt op het veilig ondertekenen van documenten. "Elk digitaal ondertekeningssysteem maakt gebruik van een hash-functie gecombineerd met een moeilijk wiskundig probleem. SPHINCS+ heeft niets anders nodig dan een hashfunctie", aldus Hülsing. "SPHINCS+ is uniek in het beveiligingsniveau dat het biedt." De zes voorstellen van de TU Eindhoven zullen begin 2018 tijdens de eerste Post Quantum Cryptology (PQC) standaardisatieconferentie worden gepresenteerd. Wetenschappers werken op verzoek van het NIST ondertussen al aan de volgende fase van de 'competitie'.

"Onze Eindhovense cryptografen zijn nu bezig met het analyseren van de andere voorstellen en hebben in twee voorstellen al ernstige beveiligingsfouten gevonden". zegt Tanja Lange, hoogleraar Cryptology bij de faculteit Wiskunde en Informatica. Deze analysefase duurt nog 3 tot 5 jaar, waarin het de bedoeling is dat alle voorstellen uitvoerig geanalyseerd en getest worden. Vervolgens worden één of enkele voorstellen vastgelegd als dé nieuwe standaarden voor post-kwantum cryptografie.

Reacties (10)
23-12-2017, 17:32 door Anoniem
stateless hash-based signature is het magische begrip, in de toekomstige wijze van encryptie, althans voor het ondertekenen van documenten zonder dat dit door kwantumcomputers kan worden gebroken
SPHINCS – Stateless, practical, hash-based, incredibly nice cryptographic signatures.

https://sphincs.cr.yp.to/slides-sphincs-20150421.pdf

De vraag hier is, wie kan dit principe in gewoon Nederlands uitleggen, en waarom kwantumcomputers dit niet kunnen kraken.
23-12-2017, 19:50 door Anoniem
Kwantumcomputers kunnen maar een beperkt aantal algoritmes verwerken, dus zoeken ze naar methodes die buiten het bereik van zo'n apparaat liggen.
23-12-2017, 20:52 door Krakatau
23-12-2017, 22:04 door Anoniem
Door Anoniem: stateless hash-based signature is het magische begrip, in de toekomstige wijze van encryptie, althans voor het ondertekenen van documenten zonder dat dit door kwantumcomputers kan worden gebroken
SPHINCS – Stateless, practical, hash-based, incredibly nice cryptographic signatures.

https://sphincs.cr.yp.to/slides-sphincs-20150421.pdf

De vraag hier is, wie kan dit principe in gewoon Nederlands uitleggen, en waarom kwantumcomputers dit niet kunnen kraken.

En _bewezen_ "waarom niet" gaat niet in Nederlands, maar in wiskunde.

Quantum computers doen 'symmetrische crypto' (AES, SHA e.a.) sqrt(N) sneller [Grover's algorithm - 2^(n) doorzoeken in 2^(0.5n) ) . Het verdubbelen van sleutellengte (N^2) brengt je weer waar je was qua moeilijkheidsgraad .

Alleen doen ze asymmetrische cryptografie gebaseerd op factorisatie (RSA), discrete logarithmen (DIiffie-Hellman) of Elliptic curves zoveel sneller [Shor's algorithm] dat het vergroten van de sleutellengtes daar geen oplossing voor biedt .

Zo'n beetje alle crypto die je praktisch gebruikt (ssl, signatures op software packages of documenten) gebruikt [ook] asymmetrische algorithmen .

Dus zoek je naar andere wiskundige problemen die bruikbaar zijn voor asymmetrische encryptie waar Shor's algorithm _niet_ voor werkt . En dat zijn de voorstellen voor post-quantum cryptography.
Zie verder https://pqcrypto.org/

Je hebt naast 'veilig' nog andere eisen voor een cryptosysteem in de meeste toepassingen, en dat is 'voldoende snel op de gebruikelijke hardware' . Een systeem waarbij het het openen van een HTTPS_PQ pagina een paar minuten duurt is niet geschikt , ook als het voldoet aan een veiligheidseis.

Overigens: er is tussen alle hype en mooie promoties van research nog bij lange geen quantum computer die crypto op praktijk schaal aankan . En de sectie 'hoe kunnen we ons resultaat opschalen' is in de papers die ik soms zie wel erg mager .
Ik moet zeggen dat ik wel parallellen zie met de beloften van praktische kernfusie - al vijftig jaar lang 'binnen 20 jaar' .

Het is mij niet duidelijk of Shor's algorithme het 'bewezen best mogelijke' is op een quantum computer, en van de diverse kandidaat post-quantum opties weet ik nog minder hoe 'bewezen resistent tegen elk mogelijk quantum algorithme' ze zijn.
(wil niet zeggen dat niemand dat weet, ik volg dit veld niet in heel diep detail.)

Overigens geldt dat ook voor 'klassieke' algorithmen om de onderliggende problemen van asymmetrische cryptografie op te lossen - er is geen wiskundig bewijs dat die problemen "fundamenteel moeilijk" zijn .
24-12-2017, 00:03 door Anoniem
Als quantum (of is het kwantum) computing niet sneller kan rekenen, maar wel heel snel vergelijkingen kan oplossen,
moeten we juist dat aspect van de kracht van kwantum aanvallen.

Het gaat om een voorspelbaarheidscurve, die is bij ons weer ongewisser als bij een mathematische extrapolatie.

De komst van predatoren tijdens de explosie van soorten in het cambrium door een ongewisse ontwikkeling was ook vrij onvoorspelbaar. Het grote aantal predatoren, die na dit gebeuren met een enkele cambrium garnaal optraden,
was een bewijs van deze a priori niet-voorspelbaarheid.
24-12-2017, 02:39 door beatnix - Bijgewerkt: 24-12-2017, 02:40
Door Anoniem: stateless hash-based signature is het magische begrip, in de toekomstige wijze van encryptie, althans voor het ondertekenen van documenten zonder dat dit door kwantumcomputers kan worden gebroken
SPHINCS – Stateless, practical, hash-based, incredibly nice cryptographic signatures.

https://sphincs.cr.yp.to/slides-sphincs-20150421.pdf

De vraag hier is, wie kan dit principe in gewoon Nederlands uitleggen, en waarom kwantumcomputers dit niet kunnen kraken.

omdat, niet alleen quantum computers, de te versleutelen content niet zouden kunnen voorspellen. wat overigens niet helemaal waar is bij deze cryptografische vorm maar dan moet ik dat op later tijdstip eens verder gaan uitkauwen al deze voorstellen.

deze lijkt overigens op een al ouder voorstel wat niet eerder is uitgekristalliseerd, weten jullie ook weer wie dat was, waar ie vandaan kwam en hoe dat heette?
24-12-2017, 10:43 door Anoniem
Quantumcomputers lopen vast op simpele algoritmes die gesplitst zijn. hierdoor is het feitelijk onmogelijk om modellen te ontwikkelen die leiden tot een juiste instructiereeks,
24-12-2017, 11:47 door Anoniem
Door Anoniem: Quantumcomputers lopen vast op simpele algoritmes die gesplitst zijn. hierdoor is het feitelijk onmogelijk om modellen te ontwikkelen die leiden tot een juiste instructiereeks,
Simpele algoritmes die gesplitst zijn...

Ik heb geen verstand van quantumcomputers maar programmeren doe ik al zo'n 35 jaar. Ik heb alleen geen idee waar je precies op doelt als je het over gesplitste algoritmes hebt. Kan je uitleggen wat dat is?
25-12-2017, 10:53 door Bitwiper - Bijgewerkt: 25-12-2017, 10:59
De meest gebruikte asymmetrische cryptografische algoritmes, RSA en Diffie-Hellman, zijn erop gebaseerd dat het voor een aanvaller, met de nu in gebruik zijnde computers, extreem tijdrovend is om een zeer groot getal "n" te ontbinden in factoren.

Voor degenen wiens wiskundekennis van de middelbare school wat is weggezakt: ontbinden in factoren is het zoeken naar de kleinst mogelijke gehele getallen die, allemaal met elkaar vermenigvuldigd, het oorspronkelijke getal opleveren. As je bijv. het getal 30 in factoren moet ontbinden, zie je meteen dat het deelbaar is door 2 (ondat 30 een even getal is). De helft daarvan is 15, en iedereen weet dat dit deelbaar is door 3. Dan hou je 5 over. M.a.w. 30 = 2 x 3 x 5.

Die 2, 3 en 5 zelf zijn niet "kleiner te maken" omdat ze alleen maar deelbaar zijn door 1 (en daar wordt het resultaat niet kleiner van) en door zichzelf (maar dat levert 1 op, en daar schiet je ook niks mee op). Dit soort getallen noemen we priemgetallen. Ontbinden in factoren is dus het zoeken naar priemgetallen.

Bij zowel RSA als Diffie-Hellman genereert de "versleutelaar" (of genereren de "versleutelaars") twee zeer grote random priemgetallen en vermenigvuldigen die met elkaar om eerder genoemd getal "n" te krijgen. Om de encryptie te kraken moet de aanvaller, die alleen "n" kent, dat getal ontbinden in factoren. Omdat de versleutelaar(s) twee priemgetallen met elkaar hebben vermenigvuldigd om "n" te bepalen, is de enige mogelijke uitkomst (van het ontbinden in factoren van "n") die twee priemgetallen.

Hoe groter "n", hoe moeilijker het is om het te kraken (lees: zoeken naar de twee priemgetallen die, met elkaar vermenigvuldigd, "n" opleveren). Aanvankelijk werd de orde van grootte van "n" uitgedrukt in het aantal decimale cijfers, tegenwoordig geven we dat weer in bits. Momenteel bestaat, bij RSA, "n" meestal uit 2048 of 4096 bits.

Volgens [1] is in 2009 aangetoond dat "n" met een lengte van 768 bits met conventionele computers kon worden gekraakt. Het duurde nog erg lang voordat het gebruik van "n" met een lengte van 1024 bits werd uitgefaseerd [2].

Van quantum computers heb ik geen verstand. Wat ik erover gelezen heb, is dat daarmee symmetrische encryptie en cryptografische hashes sneller gekraakt kunnen worden dan met conventionele computers, maar dat het snelheidsverschil niet spectaculair is; het simpelweg vergroten van sleutel-/hashlengtes voorkomt -naar verwachting- problemen. Naar verluidt "volstaat" het om bitlengtes te verdubbelen: i.p.v. AES-128 zou je AES-256 moeten gebruiken. Bij cryptografische hashes is e.e.a. afhankelijk van de toepassing, maar van SHA-256 naar SHA-512 is geen moeilijke stap.

Het algoritme van Shor, dat kennelijk niet effectief is op conventionele computers, zou echter op quantum computers astronomisch grote getallen spectaculair sneller kunnen ontbinden in factoren. Het vergroten van "n" zou hierbij onvoldoende helpen; vandaar de zoektocht naar alternatieve algoritmes voor asymmetrische cryptografie (zowel encryptie als digitale handtekeningen).

Meer info over post-quantum-crypto: [3]

[1] https://en.m.wikipedia.org/wiki/RSA_Factoring_Challenge
[2] https://www.ncsc.nl/actueel/factsheets/factsheet-certificaten-met-1024-bit-rsa-worden-uitgefaseerd.html
[3] https://www.ncsc.nl/actueel/factsheets/factsheet-postkwantumcryptografie.html
25-12-2017, 22:46 door ej__
Misschien handig om ook eens naar Suite B algoritmes [1] te kijken. Volgens de theorie van NIST en NSA is dat vooralsnog de standaard voor quantum aanval resistentie.

Het blog van Bruce Schneier uit 2015 is volgens mij ook nog steeds relevant. [2] In 2015 dacht Bruce dat het nog 30-40 jaar zou duren voordat quantum computers relevant zouden worden. Dat heeft hij inmiddels aangepast, zie datzelfde blog.

[1] https://www.iad.gov/iad/programs/iad-initiatives/cnsa-suite.cfm
[2] https://www.schneier.com/blog/archives/2015/08/nsa_plans_for_a.html
Reageren

Deze posting is gelocked. Reageren is niet meer mogelijk.