Drempelbeveiling mogelijk maken voor RFID

Drempelbeveiling mogelijk maken voor RFID Philippe Jeurissen

Thesis voorgedragen tot het behalen van de graad van Master in de ingenieurswetenschappen: elektrotechniek, optie Geïntegreerde elektronica Promotoren: Prof. dr. ir. Bart Preneel Prof. dr. ir. Ingrid Verbauwhede Assessoren: Dr. ir. Stefaan Seys Prof. dr. ir. Patrick Reynaert Begeleiders: Ir. Roel Peeters Ir. Roel Maes Ir. Junfeng Fan

Academiejaar 2010 – 2011

c Copyright K.U.Leuven

Zonder voorafgaande schriftelijke toestemming van zowel de promotor(en) als de auteur(s) is overnemen, kopiëren, gebruiken of realiseren van deze uitgave of gedeelten ervan verboden. Voor aanvragen tot of informatie i.v.m. het overnemen en/of gebruik en/of realisatie van gedeelten uit deze publicatie, wend u tot ESAT, Kasteelpark Arenberg 10 postbus 2440, B-3001 Heverlee, +32-16-321130 of via e-mail [email protected]. Voorafgaande schriftelijke toestemming van de promotor(en) is eveneens vereist voor het aanwenden van de in deze masterproef beschreven (originele) methoden, producten, schakelingen en programma’s voor industrieel of commercieel nut en voor de inzending van deze publicatie ter deelname aan wetenschappelijke prijzen of wedstrijden.

Voorwoord Deze masterproef was een unieke ervaring en heeft me op vele vlakken nieuwe dingen bijgebracht. Via deze weg wil ik een aantal mensen bedanken die me bijgestaan hebben in heel deze ervaring. Zonder hen was het resultaat nooit hetzelfde geweest. Allereerst wil ik mijn dagelijkse begeleiders, Roel Maes, Roel Peeters en Junfeng Fan, bedanken voor de vele uren die zij hebben gestoken in mijn begeleiding. Zonder jullie hulp had ik dit resultaat nooit kunnen bereiken. Ook wil ik mijn promotors Prof. Dr. Ir. Bart Preneel en Prof. Dr. Ir. Ingrid Verbauwhede bedanken voor het mogelijk maken van deze thesis. Alsook mijn assessoren Dr. Ir. Stefaan Seys en Prof. Dr. Ir. Patrick Reynaert voor het lezen en beoordelen van deze thesis. Via deze weg zou ik ook graag mijn ouders en de rest van mijn familie willen bedanken voor hun grote steun tijdens mijn gehele opleiding. Zonder hen had ik dit nooit bereikt. Ten slotte wil ik ook mijn klasgenoten en vrienden bedanken voor hun steun en de broodnodige ontspanning tussen het werken door. Philippe Jeurissen

i

Inhoudsopgave Voorwoord

i

Samenvatting

v

Lijst van figuren en tabellen

vi

Lijst van afkortingen en symbolen 1 Inleiding 1.1 Een nieuwe aanpak . . . 1.2 Probleemstelling . . . . 1.3 Bijdrage van deze thesis 1.4 Aanpak van de thesis . .

. . . .

. . . .

. . . .

viii . . . .

. . . .

. . . .

. . . .

2 Cryptografie 2.1 Symmetrische sleutel cryptografie . . 2.2 Publieke sleutel cryptografie . . . . . 2.2.1 Versleuteling . . . . . . . . . 2.2.2 Authenticatie . . . . . . . . . 2.3 Sterkte van cryptografische systemen 2.3.1 Het factorisatieprobleem . . . 2.3.2 Discrete logaritmeprobleem . 2.3.3 Het Diffie-Hellmanprobleem .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

3 Wiskundige concepten 3.1 Elliptische krommen . . . . . . . . . . . . . . . . . . . 3.1.1 Elliptische kromme discrete logaritmeprobleem 3.2 Paringen . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Wiskundige problemen gebaseerd op paringen . 4 Drempelcryptografie 4.1 Drempelschema’s . . . . . . . . . . . . . . . 4.1.1 De verdelingsfase . . . . . . . . . . . 4.1.2 De verificatiefase . . . . . . . . . . . 4.1.3 De reconstructiefase . . . . . . . . . Nulkennisbewijzen . . . . . . . . . . Langrangeveelterminterpolatie . . . 4.1.4 Gebruik in cryptografische systemen Elgamalversleutelingsschema . . . . ii

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . .

1 1 3 3 4

. . . . . . . .

5 6 7 8 8 9 10 10 10

. . . .

11 11 13 14 16

. . . . . . . .

17 17 18 19 20 21 22 22 22

Inhoudsopgave

4.2

Schnorr digitale handtekeningsschema . . . . 4.1.5 Gedistribueerde sleutelgeneratie . . . . . . . . Het basisdrempelschema voor de implementatie . . . 4.2.1 Kenmerken van het schema . . . . . . . . . . 4.2.2 Publiek verifieerbaar geheimverdelingsschema 4.2.3 Gedistribueerde sleutelgeneratieschema’s . . . 4.2.4 Versleuteling en ontsleuteling . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

23 23 24 24 25 25 26

5 Ontwerp 5.1 Praktische aspecten en ontwerpbeslissingen . 5.1.1 Soorten apparaten . . . . . . . . . . . 5.1.2 Het verificatieprobleem . . . . . . . . 5.1.3 Het inverteringsprobleem . . . . . . . 5.2 Programmaverloop . . . . . . . . . . . . . . . 5.2.1 De initialisatiefase . . . . . . . . . . . 5.2.2 De gedistribueerde sleutelgeneratiefase 5.2.3 De toepassingsfase . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

29 29 30 30 31 32 32 32 33

6 Implementatie 6.1 Implementatie op PC . . . . . . . . . . . 6.1.1 Programeertaal . . . . . . . . . . 6.1.2 Softwarebibliotheken . . . . . . . 6.1.3 Programmaontwerp . . . . . . . Apparaten . . . . . . . . . . . . . Modulariteit . . . . . . . . . . . Inkapseling . . . . . . . . . . . . 6.2 Implementatie op FPGA . . . . . . . . . 6.2.1 Field-programmable Gate Array . Opbouw FPGA . . . . . . . . . . Xilinx Microblaze . . . . . . . . . 6.2.2 Implementatie . . . . . . . . . . Compileren van de bibliotheken . Communicatie met de computer

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

35 35 35 35 37 37 37 37 38 38 38 39 40 41 42

7 Radio Frequency Identification 7.1 Algemene kenmerken . . . . . . . . 7.1.1 Huidige ontwikkelingen . . 7.2 ECC coprocessor . . . . . . . . . . 7.3 Integratie met het drempelschema

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

43 43 44 44 45

. . . . . .

47 47 47 47 48 48 48

8 Resultaten 8.1 Testplatformen . . . . 8.2 Tijdsmetingen . . . . . 8.2.1 Initialisatie van 8.2.2 Paringen . . . . 8.3 Integratietest . . . . . 8.3.1 Situatieschets .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . de elliptische kromme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

iii

Inhoudsopgave 8.3.2

. . . .

49 49 51 51

9 Besluit 9.1 Vervolgwerk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53 53

Bibliografie

55

iv

Testopstellingen Test 1 . . . . . . Test 2 . . . . . . Test 3 . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Samenvatting Tegenwoordig heeft men steeds meer intelligente apparaten op zak. Dit zorgt ervoor dat de mogelijkheden ervan uitgebreider worden. Een GSM is bijvoorbeeld geëvolueerd naar een zakcomputer met de mogelijkheid om draadloos op het internet te surfen, je e-mailberichten te lezen of berichten achter te laten op je favoriete sociale netwerksite. Deze evolutie zorgt echter voor nieuwe uitdagingen zoals bijvoorbeeld het beveiligen van de persoonlijke informatie opgeslagen op deze apparaten. Dremplecryptografie kan een alternatief vormen voor de beveiliging van deze mobiele apparaten. Hierbij gaan apparaten samenwerken om zo één beveiliging te creëren voor alle apparaten. Commerciële implementaties van zulke drempelcryptografische schema’s voor het beveiligen van mobiele apparaten zijn echter nog niet opgedoken. Dit is onder andere te wijten aan het feit dat deze drempelschema’s gebruik maken van rekenintensieve technieken die slechts op een beperkt aantal van de huidige ingebedde mobiele apparaten kunnen uitgevoerd worden. Ze vereisen ook de aanwezigheid van veilige opslagruimte op deze apparaten die niet door buitenstaanders uitgelezen kan worden. Zulke opslag is echter kostelijk. Deze twee factoren belemmeren de opkomst van drempelschema’s. Deze thesis toont aan dat het echter toch mogelijk is om apparaten met een beperkte hoeveelheid rekenkracht en zonder beveiligde opslag te laten deelnemen aan drempelschema’s. Om dit te bewijzen wordt een bestaand drempelschema geanalyseerd en wordt er op basis daarvan een praktische implementatie geschreven. Ook wordt er specifiek gekeken naar de mogelijkheid om RFID tags te laten deelnemen aan drempelschema’s. RFID tags kunnen immers goedkoop gefabriceerd worden en makkelijk in kleding of schoenen verwerkt worden. De implementatie van het schema gebeurt op PC en de apparaten met beperkte rekenkracht worden gesimuleerd op FPGA met behulp van een soft core processor. Om te bewijzen dat de implementatie werkt, werd het drempelschema gebruikt om de gebruiker te identificeren aan een gesimuleerd toegangskaartsysteem. Ook werd de snelheid van de implementatie geanalyseerd in functie van het aantal apparaten dat deelneemt. Uit deze thesis kan dus besloten worden dat het praktisch mogelijk is apparaten met beperkte rekenkracht en zonder veilige opslag, zoals bijvoorbeeld RFID tags, deel te laten nemen aan drempelschema’s.

v

Lijst van figuren en tabellen Lijst van figuren 1.1

Identificatie aan een toegangsdeur met behulp van verschillende apparaten die je op zak hebt. . . . . . . . . . . . . . . . . . . . . . . . .

2

2.1 2.2 2.3

Een overzicht van een symmetrische sleutel cryptografie schema. . . . . Een overzicht van een asymmetrische sleutel cryptografie schema. . . . . Een overzicht van een asymmetrische sleutel authenticatie schema. . . .

6 8 9

3.1 3.2 3.3 3.4

Elliptische kromme. . . . . . . . . . . . . . . . . . . . . . . . . . . . Elliptische kromme. . . . . . . . . . . . . . . . . . . . . . . . . . . . Geometrische optelling van twee punten op een elliptische kromme . Geometrische verdubbeling van een punt op een elliptische kromme.

. . . .

. . . .

12 13 14 15

4.1 4.2 4.3 4.4 4.5

. . . .

18 19 22 25

.

26

4.7

Veeltermen door 1 punt . . . . . . . . . . . . . . . . . . . . . . . . . . Visuele voorstelling van Shamir’s geheimverdelingsschema . . . . . . . De grot van Ali Baba. . . . . . . . . . . . . . . . . . . . . . . . . . . . Het publiek verifieerbaar geheimverdelingsschema van [24]. . . . . . . Fase 1 van het gedistribueerde sleutelgeneratieschema van Simoens et al. [24] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fase 2 van het gedistribueerde sleutelgeneratieschema van Simoens et al. [24] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . De aangepaste versie van het ElGamalversleutelingsschema van [24]. .

. .

27 28

5.1

Opstelling van de verschillende apparaten . . . . . . . . . . . . . . . . .

31

6.1 6.2 6.3

Schakelmatrix met logische blokken van een FPGA. . . . . . . . . . . . 38 Schema van een Configurable Logic Blok van een Xilinx Spartan 3E FPGA. 40 Schema van de Xilinx Microblaze architectuur. . . . . . . . . . . . . . . 41

7.1 7.2

Voorbeeld van een passsieve RFID tag. . . . . . . . . . . . . . . . . . . . Layout van de ECC coprocessor ontworpen door Lee et al. [13]. . . . . .

44 45

8.1 8.2 8.3

De resultaten van de variatie van het aantal apparaten in testsituatie 1. De resultaten van de variatie van de drempelwaarde in testsituatie 1. . . De resultaten van de variatie van het aantal apparaten in testsituatie 2.

50 50 52

4.6

vi

Lijst van figuren en tabellen 8.4

De resultaten van de variatie van de drempelwaarde in testsituatie 2. . .

52

Lijst van tabellen 6.1 6.2

De waardes van de parameters van de gebruikte curve van type D81 [14]. Specificaties van de Xilinx Spartan 3ES250 FPGA [29]. . . . . . . . . .

36 39

7.1

Specificaties van de elliptische kromme cryptografische processor van [13]. 45

8.1 8.2

Testresulaten van de ECC initialisatie. . . . . . . . . . . . . . . . . . . . Resultaten van de snelheidstest van paringen. . . . . . . . . . . . . . . .

48 48

vii

Lijst van afkortingen en symbolen

Symbolen

G1 G2 GT Z∗p P P0 P 00 Q Di si Si t n g Ci Ai,k Bi,k Zi λi m kP e viii

Cyclische groep van orde p Cyclische groep van orde p Cyclische groep van orde p Cyclische groep van de gehele getallen van orde p Generator van G1 Generator van G1 Generator van G1 Generator van G2 Apparaat i De geheime sleutel van apparaat i De publieke sleutel van apparaat i De drempel van het drempelschema Het totaal aantal apparaten Paring e(P, Q) Sleuteldeel van apparaat i Verbintenis k van apparaat i Verbintenis k van het nulkennisbewijs van apparaat i Nulbewijsfactor van apparaat i Interpolatiefactor van apparaat i Het te versleutelen of ontsleutelen bericht De willekeurigheid of randomness gebruikt bij het ElGamalschema De versleutelde boodschap

Afkortingen RFID FPGA VSS PVSS DKG DLOG DH PBC ECC GMP

Radio frequentie identificatie Field-programmable gate array Verifieerbare geheimverdeling Publiek verifieerbare geheimverdeling Gedistribueerde sleutelgeneratie Discreet logaritmeprobleem Diffie-Hellmanprobleem Paringgebaseerde cryptografie Elliptische kromme cryptografie GNU Multiple Precision Arithmetic Library

ix

Hoofdstuk 1

Inleiding Technische vooruitgang heeft ervoor gezorgd dat mobiele apparaten steeds krachtiger worden. GSM’s bijvoorbeeld hebben een hele weg afgelegd van de onhandige apparaten toen ze net op de markt kwamen tot de multifunctionele zakcomputers van tegenwoordig. Deze zakcomputers geven bijvoorbeeld de mogelijkheid om onderweg je e-mailberichten te lezen, berichten te plaatsen op je favoriete sociale netwerksite of je bankzaken te regelen. Zakcomputers bevatten dus een zeer grote hoeveelheid aan persoonlijke informatie. Ook laptops verschijnen met steeds meer opslagcapaciteit die gebruikt kan worden om persoonlijke gegevens in op te slaan. Deze ontwikkelingen brengen echter ook een nieuw probleem met zich mee, met name de beveiliging van al deze data. Immers door de mobiliteit van deze apparaten worden ze vaker blootgesteld aan beveiligingsrisico’s dan bijvoorbeeld je PC op je bureau thuis of op het werk. Zo kan je je zakcomputer verliezen, kan hij gestolen worden of kan je hem onbewaakt achterlaten,... Dat dit regelmatig voorkomt, kan afgeleid worden uit de vele nieuwsberichten over de diefstal of het verlies van apparaten waar zeer gevoelige informatie zoals persoonsgegevens in opgeslagen zijn. De beveiliging van deze apparaten is dan ook essentieel. Een veelgebruikte techniek tegenwoordig is het individueel beveiligen van deze apparaten [30]. Zo heeft je zakcomputer bijvoorbeeld een PIN code en je laptop een gebruikersnaam en wachtwoord. Dit zorgt er echter voor dat je steeds verschillende wachtwoorden en pincodes moet onthouden. Immers hetzelfde wachtwoord kiezen voor al je apparaten zal al deze apparaten compromitteren als het wachtwoord geraden wordt. Als het wachtwoord verloren gaat verlies je ook toegang tot het apparaat. Deze aanpak heeft dus inherent een aantal nadelen.

1.1

Een nieuwe aanpak

Recentelijk duiken er echter nieuwe technieken op om deze mobiele apparaten te beveiligen [30], [19]. Deze technieken maken gebruik van het feit dat men er vanuit kan gaan dat de gebruiker steeds meerdere apparaten op zak heeft en wordt drempelbeveiliging genoemd. Men gaat apparaten combineren om zo een totale beveiliging 1

1. Inleiding

Figuur 1.1: Identificatie aan een toegangsdeur met behulp van verschillende apparaten die je op zak hebt. (Met dank aan Roel Peeters voor de afbeelding)

van alle apparaten te creëren. Drempelbeveiliging werkt met een parameter t, de drempel genoemd. Deze parameter geeft weer hoeveel apparaten minstens moeten samenwerken om ze bijvoorbeeld te ontgrendelen. De waarde van de parameter t ligt lager dan het totaal aantal apparaten, die beveiligd moeten worden, zodat niet alle apparaten noodzakelijk zijn om de beveiliging te laten werken [30]. Dit laat toe dat de gebruiker een aantal apparaten thuislaat als bijvoorbeeld de batterij ervan moet opgeladen worden of in het slechtste geval hij er eentje verliest. Zolang hij over meer dan t apparaten beschikt is er geen probleem en kan hij de apparaten ontgrendelen en gebruiken. Dit heeft als gevolg dat een buitenstaander enkel toegang krijgt tot de apparaten als hij minstens t apparaten bezit. Door t te verhogen kan dus de graad van veiligheid verhoogd worden. [30]. Deze techniek kan niet alleen gebruikt worden voor de beveiliging van apparaten. Laat ons bijvoorbeeld een toegangskaartsysteem aan een deur bekijken. Huidige technieken vereisen dat de gebruiker zijn toegangskaart gebruikt om zich te identificeren en de deur te openen. Verliest hij echter deze toegangskaart, dan kan hij de deur niet meer openen. Een kwaadwillige gebruiker heeft ook genoeg aan de toegangskaart van iemand met toegang om de deur te openen, tenzij er extra (fysieke) veiligheidsmaatregels getroffen worden. Als we echter drempelbeveiliging gaan gebruiken om de gebruiker te identificeren dan moet de gebruiker minstens t apparaten bij zich hebben voor een juiste identificatie. Dit biedt een grotere flexibiliteit en veiligheid. Immers het verlies van de toegangskaart kan opgevangen worden indien de gebruiker minstens t andere apparaten bij zich heeft. Een aanvaller daarentegen moet minstens t apparaten stelen vooraleer hij de deur kan openen. Een andere toepassing van drempelbeveiliging kan het beveiligen van data op de harde schijf van een computer zijn. Normaal wordt de data op de harde schijf beveiligd met 2

1.2. Probleemstelling een wachtwoord. Dit vormt ook weer een risico voor de gebruiker. Immers indien dit wachtwoord verloren gaat, is de data niet meer toegankelijk. Gebruiken we echter drempelbeveiliging dan kan het wachtwoord vervangen worden door een identificatie met minstens t apparaten. Het is dus makkelijk in te zien dat drempelbeveiliging vele vormen kan aannemen en een belangrijk onderzoeksdomein vormt. Het biedt dus een hogere graad van veiligheid en een grotere flexibiliteit naar de gebruiker toe. Bovendien kan men ook stellen dat als er meer en verschillende apparaten gebruikt worden voor de identificatie, de flexibiliteit stijgt [30].

1.2

Probleemstelling

De huidige implementaties van drempelbeveiligingsschema’s hebben echter een aantal nadelen. Er zijn voorwaarden waaraan de deelnemende apparaten moeten voldoen. We kunnen twee belangrijke voorwaarden onderscheiden [24]: • De apparaten moeten beschikken over genoeg rekenkracht. Drempelschema’s gebruiken zeer rekenintensieve bewerkingen die niet door alle mobiele apparaten kunnen uitgevoerd worden. • De apparaten moeten beschikken over beveiligde opslag. Dit wil zeggen dat er opslagruimte moet zijn die afgeschermd is van de buitenwereld om belangrijke parameters van het drempelschema in op te slaan die niet publiek gemaakt mogen worden. Dit vormt een zeer beperkende factor voor zulke schema’s want de graad van flexibiliteit en veiligheid wordt bepaald door het aantal en het soort apparaten dat eraan deelneemt [30]. Enkel de duurdere apparaten met genoeg rekenkracht en beveiligde opslag komen in aanmerking. Als er een manier kan gevonden worden om goedkope apparaten die niet over bovenstaande eigenschappen beschikken, toch te laten deelnemen in drempelbeveiligingsschema’s, zou dit een enorme vooruitgang zijn. Dit zou de deur openen om zeer eenvoudige en goedkope apparaten zoals bijvoorbeeld Radio Frequentie Identificatie (RFID) tags te gebruiken in deze schema’s.

1.3

Bijdrage van deze thesis

Er is reeds een artikel verschenen met een theoretisch drempelbeveiligingsschema dat gebruikt kan worden om de integratie van apparaten met beperkte rekenkracht en zonder beveiligde opslag in deze schema’s mogelijk te maken [24]. De bijdrage die deze thesis wil leveren bestaat uit drie delen: 1. Deze thesis zal analyseren als het praktisch haalbaar is om goedkope apparaten met beperkte rekenkracht en zonder beveiligde opslag in drempelschema’s te integreren. 3

1. Inleiding 2. Er zal een praktische implementatie van zulk een drempelbeveiligingsschema ge¨ımplementeerd worden. Praktische aspecten en problemen die tevoorschijn komen, zullen geadresseerd worden. 3. Als specifiek voorbeeld van een goedkoop apparaat met beperkte rekenkracht en zonder beveiligde opslag wordt een RFID tag gebruikt. Er wordt gekeken als dit soort apparaten kunnen deelnemen aan drempelschema’s. De doelstelling van deze thesis kan dus als volgt samengevat worden:

Het aantonen dat apparaten met beperkte rekenkracht en zonder veilige opslag, zoals bijvoorbeeld RFID tags, kunnen deelnemen aan drempelbeveiligingsschema’s en dit door een effectieve implementatie van zo een drempelbeveiligingsschema te schrijven.

1.4

Aanpak van de thesis

Allereerst zal een studie van het vakgebied van de cryptografie gebeuren in hoofdstuk 2. Hierin zal de evolutie van cryptografie besproken worden alsook een aantal basisconcepten die noodzakelijk zijn om het verdere verloop van de thesis te kunnen volgen. Deze studie wordt gevolgd door een kort overzicht van een aantal wiskundige concepten in hoofdstuk 3 die een wiskundige basis geven voor drempelschema’s en cryptografie in het algemeen. Vervolgens zal drempelcryptografie uitgebreid besproken worden alsook het drempelschema waarop de implementatie gebaseerd is. Dit gebeurt in hoofdstuk 4. Hoofdstuk 5 geeft de ontwerpbeslissingen weer die genomen zijn bij het ontwerp van het drempelbeveiligingsprogramma. Het eerste deel van hoofdstuk 6 bespreekt de effectieve implementatie op de PC en de praktische aspecten die hierbij naar boven kwamen. In het tweede deel van dit hoofdstuk worden de praktische aspecten van de implementatie op FPGA bekeken. Hoofdstuk 7 bekijkt Radio frequentie identificatie (RFID) als een specifiek voorbeeld van een apparaat met beperkte rekenkracht en zonder veilige opslag, alsook de integratie van een specifieke RFID met de implementatie van het drempelschema. Hoofdstuk 8 bespreekt een opstelling van verschillende apparaten gemaakt met de implementatie van het drempelschema die alle aspecten van de implementatie test. De resultaten van deze test worden in dit hoofdstuk ook besproken alsook mogelijke verbeteringen die in de toekomst eraan zouden kunnen worden toegevoegd. Ten slotte wordt een kort overzicht gegeven van de bekomen resultaten.

4

Hoofdstuk 2

Cryptografie In dit inleidende hoofdstuk willen we een overzicht geven van een aantal belangrijke cryptografische begrippen om de lezer een achtergrond te geven bij het lezen van deze thesis. Allereerst wordt het begrip cryptografie zelf bekeken en geschetst in de geschiedenis. Vervolgens wordt symmetrische en publieke sleutel cryptografie besproken. Cryptografie is de wetenschap van de beveiliging van informatie. Het woord is afgeleid van het Griekse kryptos dat verborgen betekent. Onderzoek naar systemen om informatie te beveiligen, gebeurt al geruime tijd. Al reeds ten tijde van de heerschappij van Julius Caesar werd er informatie beveiligd. Het Caesarcijfer zal iedere letter van een bericht vervangen door de letter die drie plaatsen verder in het alfabet staat. Deze parameter(iedere letter vervangen door een andere letter) wordt de sleutel van het cijfer genoemd. Deze sleutel bevat dus de parameters die nodig zijn om het bericht te ’versleutelen’ of ’ontsleutelen’. Een discipline nauw verwant aan de cryptografie is de cryptologie. Deze houdt zich bezig met het achterhalen van de werking van cryptografische systemen om zo de berichten die ermee versleuteld zijn te kunnen ”kraken”. De opkomst van de computer rond de Tweede Wereldoorlog heeft gezorgd voor een grote vooruitgang van deze wetenschap. Een van de bekendste voorbeelden van cryptologie stamt ook uit deze periode. Het kraken van de Duitse Enigma machine, een elektromechanische rotormachine, die gebruikt werd om militaire communicatie te versleutelen leverde de Geallieerden belangrijke informatie over de Duitse militaire beslissingen. Dit was een belangrijke bijdrage tot de uiteindelijke overwinning van de Geallieerden. Nu volgt een overzicht van de moderne cryptografische systemen. Moderne cryptografische systemen hebben één of meerdere doelen voor ogen [12]: • Vertrouwelijkheid. Informatie beveiligingen zodat enkel de partij voor wie ze bedoeld is deze kan lezen. • Integriteit. Garanderen dat de beveiligde informatie niet door andere partijen aangepast is. 5

2. Cryptografie

Figuur 2.1: Een overzicht van een symmetrische sleutel cryptografie schema.

• Onloochenbaarheid. Ervoor zorgen dat de maker van het bericht niet kan ontkennen dat hij het bericht verzonden heeft. • Authenticatie. De oorsprong van de informatie valideren. Deze systemen kunnen worden ingedeeld naargelang het aantal verschillende sleutels dat gebruikt wordt: • Symmetrische sleutel cryptografie. Er wordt slechts één sleutel gebruikt. • Asymmetrische sleutel cryptografie. Er worden twee sleutels gebruikt. Eén publieke, die door iedereen gekend is, en een private. • Hashfuncties. De versleuteling gebeurt via een éénwegs hashfunctie en is niet omkeerbaar. In de volgende paragrafen worden symmetrische en asymmetrische cryptografie verder besproken.

2.1

Symmetrische sleutel cryptografie

Symmetrische sleutel algoritmes gebruiken dezelfde sleutel voor versleutelen als ontsleutelen van een boodschap. Er wordt dus één gedeelde sleutel gebruikt door beide partijen. Figuur 2.1 geeft een overzicht van de werking van dit soort algoritmes. Alice wil een bericht m verzenden aan Bob zonder dat Eve dit kan lezen. Ze kiest een 6

2.2. Publieke sleutel cryptografie geheime sleutel k en past deze toe op haar bericht en krijgt het versleutelde bericht c door Ek (m) = c. Dan zorgt ze ervoor dat die sleutel via een veilig kanaal tot bij Bob geraakt. Het bericht zendt ze over het onveilige kanaal waarop Eve meeluistert. Bob kan met deze sleutel het versleutelde bericht ontsleutelen: Dk (c) = m. Eve kan het versleutelde bericht c wel lezen maar zonder de geheime sleutel k kan ze het niet ontsleutelen [1]. Alhoewel symmetrische cryptografische algoritmes in het algemeen zeer efficiënt grote hoeveelheden informatie kunnen versleutelen hebben ze een groot nadeel nl. sleutelbeheer. Men moet immers in staat zijn een veilig kanaal te creëren om de gedeelde sleutel k uit te wisselen. Immers iedereen die in het bezit is van deze sleutel kan het bericht ontsleutelen. Zo zou Eve in het schema op figuur 2.1 het bericht ook kunnen ontsleutelen als ze tijdens de fase van het uitwisselen van de sleutel k deze kan bemachtigen. Symmetrische sleutel cryptografie voor het versturen van berichten wordt zelden meer gebruikt in zijn originele vorm wegens het sleuteluitwisselingsprobleem. Bij het versleutelen van data zonder dat deze verzonden wordt, wordt symmetrische sleutel cryptografie wel nog toegepast. Een voorbeeld hiervan is het versleutelen van data op de harde schijf van een computer.

2.2

Publieke sleutel cryptografie

Tot midden jaren 70 waren er geen alternatieven voor symmetrische sleutel cryptografie. In 1976 echter kwamen Diffie en Hellman met een cryptografisch systeem dat het veilig uitwisselen van de geheime sleutel k sterk vereenvoudigde [3]. Dit nieuwe systeem was de asymmetrische of publieke sleutel cryptografie. Hierbij wordt er gebruik gemaakt van 2 verschillende soorten sleutels voor het versleutelen en ontsleutelen. • De publieke sleutel kan over een onveilig kanaal verdeeld worden en kan een bericht versleutelen of een handtekening verifiëren. • De private of geheime sleutel wordt geheim gehouden en kan een bericht ontsleutelen of handtekenen. Een asymmetrisch schema kan vergeleken worden met een brievenbus. Iedereen kan brieven in de brievenbus steken, maar enkel de persoon met de sleutel van de brievenbus, de geheime sleutel, kan de brieven lezen. Dit is een andere aanpak dan symmetrische sleutel cryptografische systemen die gezien kunnen worden als een kist met een slot op. Iedereen die iets in de kist wil achterlaten moet de sleutel van het slot hebben. En iedereen die de sleutel heeft kan alle brieven in de kist lezen. Bij asymmetrische sleutel cryptografische schema’s is een veilig kanaal voor sleutelbeheer dus niet langer vereist. De sleutels worden gegenereerd met behulp van éénwegs valluik functies. Deze éénwegs valluik functies kunnen makkelijk worden toegepast in één richting. De omgekeerde richting is echter zeer rekenintensief. In paragraaf 2.3 worden zulke functies verder uitgediept. Men kan deze functies zien als de sleuf van de brievenbus. Deze kan maar in één richting openzwaaien. 7

2. Cryptografie

Figuur 2.2: Een overzicht van een asymmetrische sleutel cryptografie schema.

2.2.1

Versleuteling

Allereerst kunnen publieke sleutelschema’s gebruikt worden om berichten te versleutelen en te ontsleutelen. Het versleutelingsschema van een publieke sleutelalgoritme bevat een aantal belangrijke wijzigingen ten opzichte van een symmetrische sleutelalgoritme. Figuur 2.2 geeft hier een voorbeeld van. Alice kiest met behulp van een trapdoor functie haar geheime en publieke sleutelpaar (d, e). Vervolgens zendt ze haar publieke sleutel e naar Bob. Dit mag over een onbeveiligd kanaal waarop Eve meeluistert. Het bericht m dat Bob aan Alice wil verzenden wordt versleuteld door de publieke sleutel e van Alice erop toe te passen: Ee (m) = c en daarna over het onbeveiligde kanaal naar Alice gestuurd. Alice past haar geheime sleutel d toe op het versleutelde bericht c en bekomt zo terug het originele bericht: Dd (c) = m [1]. Dit schema maakt het sleutelbeheer veel eenvoudiger aangezien enkel de publieke sleutel dient uitgedeeld te worden. Eve kan echter het bericht niet ontsleutelen als ze in het bezit is van de publieke sleutel. De geheime sleutel is nodig om het bericht te ontsleutelen en deze wordt niet uitgewisseld.

2.2.2

Authenticatie

In het schema dat beschreven werd in paragraaf 2.2.1 kan de ontvanger (Alice) niet verifiëren of het ontvangen bericht effectief van Bob afkomstig is. In vele gevallen is deze informatie even belangrijk dan de boodschap zelf. Publieke sleutel cryptografie voorziet een schema om een bericht te handtekenen en zo te bevestigen dat het bericht van de juiste afzender afkomstig is. Figuur 2.2 geeft een overzicht van het verificatieproces. Bob stuurt een bericht m aan Alice maar wil haar verzekeren dat het bericht van hem afkomstig is. Hij kiest daartoe een privaat, publiek sleutelpaar 8

2.3. Sterkte van cryptografische systemen

Figuur 2.3: Een overzicht van een asymmetrische sleutel authenticatie schema.

(d, e). Het bericht tekent hij door zijn geheime sleutel d erop toe te passen: Sd (m) = c. Alice ontvangt het getekende bericht c en past de publieke sleutel e van Bob toe op het bericht om te verifiëren of het afkomstig is van Bob. Deze digitale handtekeningen worden zeer veel gebruikt bij communicatie waar de afkomst van het bericht zeer belangrijk is. Zo kunnen e-mailberichten voorzien worden van een digitale handtekening of transacties over het internet,...

2.3

Sterkte van cryptografische systemen

Cryptografische systemen worden ingedeeld in twee categorieën: • Informatietheoretisch veilige systemen; • Getaltheoretisch veilige systemen (computationally secure systems). Informatietheoretisch veilige systemen berusten op een wiskundige onmogelijkheid om een sleutel te achterhalen of een bericht te ontsleutelen. Getaltheoretische veiligheid berust op het ontbreken van een efficiënt algoritme om het gebruikte wiskundige probleem op te lossen. Deze systemen zijn dus in theorie te kraken indien men over een oneindige hoeveelheid rekenkracht beschikt. In de praktijk is de hoeveelheid rekenkracht die men beschikbaar heeft echter beperkt en hier maken getaltheoretisch veilige systemen gebruik van om informatie te beveiligen. De volgende paragraaf beschrijft enkele van deze numeriek veilige systemen die gebruikt worden in cryptografische systemen. 9

2. Cryptografie

2.3.1

Het factorisatieprobleem

Het factorisatieprobleem stelt dat het zeer moeilijk is om een product van heel grote priemgetallen terug in zijn factoren te ontbinden: Definitie: Het geheel getal factorisatieprobleem: gegeven een positief geheel getal n, schrijf n als: n = pe11 pe22 . . . pekk , waar pi paarsgewijze unieke priemfactoren zijn en elke ei ≥ 1. (2.1) Dit probleem wordt veelvuldig in de cryptografie gebruikt. Het bekendste systeem gebaseerd op het factorisatieprobleem is het RSA algoritme. Dit algoritme is genoemd naar de de bedenkers ervan: Rivest, Shamir en Adleman. Het is één van de eerste publieke sleutelschema’s dat zowel versleuteling als authenticatie toelaat [21]. In het algemeen wordt dit probleem als voldoende getaltheoretisch veilig beschouwd als men een sleutellengte van minstens 1024 bit kiest [11].

2.3.2

Discrete logaritmeprobleem

Een ander wiskundig probleem dat vaak gebruikt wordt, is het discrete logaritmeprobleem. De discrete logaritme is de inverse operatie van een machtsverheffing in een eindige cyclische groep. Beschouwen we een cyclische groep G van orde p met generator α en een vermenigvuldigingsoperatie ∗. Dan is de machtsverheffing gedefinieerd als: αx = α | ∗ α ∗{z. . . ∗ α} = b mod p.

(2.2)

x

De discrete logaritme is vervolgens gedefinieerd als: logα b = x mod p.

(2.3)

Het discrete logaritmeprobleem is dan: Definitie: Het discrete logaritmeprobleem: gegeven een priemgetal p, generator α van G van orde p en een element b ∈ Z∗p , vind het geheel getal x,0 ≤ x ≤ p − 2, zodat αx = b mod p.

2.3.3

(2.4)

Het Diffie-Hellmanprobleem

Een laatste wiskundig probleem dat besproken wordt is het Diffie-Hellmanprobleem. Dit is gerelateerd aan het discrete logaritmeprobleem. Definitie: Het Diffie-Hellmanprobleem: gegeven een priemgetal p, generator α van G en αa ,αb mod p met a, b ∈ Z∗p , vind αab mod p.

10

(2.5)

Hoofdstuk 3

Wiskundige concepten In dit hoofdstuk wordt een kort overzicht gegeven van een aantal wiskundige begrippen die vaak gebruikt worden in de cryptografie en die veelvuldig in deze thesis aan bod komen. Dit hoofdstuk wil zeker geen volledig beeld geven van de achterliggende wiskunde van de cryptografische systemen. Voor een volledigere uiteenzetting verwijs ik naar [8], [2] en [16]. Allereerst worden elliptische krommen besproken en ook paringen. Daarna worden deze concepten gelinkt aan de wiskundige problemen die de veiligheid van cryptografische systemen garanderen.

3.1

Elliptische krommen

Elliptische krommen worden reeds lange tijd bestudeerd. In 1985 echter kwamen ze op de voorgrond door de voorstelling van een publieke sleutel cryptografisch schema op basis van elliptische krommen [8]. Sindsdien is er veel vooruitgang geboekt en worden ze stilaan ook gebruikt in commerciële applicaties. Eén van de belangrijkste redenen waarom elliptische krommen zo populair aan het worden zijn in cryptografische systemen, is dat de sleutellengte nodig om eenzelfde graad van veiligheid te bieden met bijvoorbeeld RSA veel kleiner kan zijn. Als RSA een sleutellengte van 1024 bit vereist, dan volstaat een sleutellengte van 160 bit voor eenzelfde graad van veiligheid [11].

Definitie: Een elliptische kromme E over een veld K is gedefinieerd door de vergelijking: E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a5

(3.1)

waar a1 , a2 , a3 , a4 , a5 ∈ K en Λ 6= 0, met Λ de discriminant van E gedefinieerd als volgt: 11

3. Wiskundige concepten

Figuur 3.1: E1 = y 2 = x3 − x (Het auteursrecht op deze afbeelding behoort toe aan [8]).

Λ = −d22 d8 − 8d34 − 27d26 + 9d2 d4 d6 d2 = a21 + 4a2 d4 = 2a4 + a1 a3 d6 = a23 + 4a5 2 d8 = a1 a5 + 4a2 a5 − a1 a3 a4 + a2 a23 − a24 .

(3.2)

Figuur 3.1 en 3.2 zijn voorbeelden van elliptische krommen die aan deze definitie voldoen. Op deze elliptische krommen kunnen een aantal bewerkingen gedefinieerd worden zoals een puntsoptelling, puntsverdubbeling en een scalar puntsvermenigvuldiging: Definitie: Puntsoptelling: Neem P = (x1 , y1 ) ∈ E(K) en Q = (x2 , y2 ) ∈ E(K), met P 6= ±Q. Dan is P + Q = (x3 , y3 ), met y2 − y1 2 y2 − y1 x3 = ( ) − x1 − x2 en y3 = ( )(x1 − x3 ) − y1 . (3.3) x2 − x1 x2 − x1 Dit wordt visueel weergegeven op figuur 3.3. Definitie: Puntsverdubbeling: Neem P = (x1 , y1 ) ∈ E(K), met P 6= −P . Dan is 2P = (x3 , y3 ), met x3 = ( 12

3x21 + a 2 3x2 + a 2 ) − 2x1 en y3 = ( 1 ) (x1 − x3 ) − y1 . 2y1 2y1

(3.4)

3.1. Elliptische krommen

Figuur 3.2: E2 = y 2 = x3 + 14 x + 54 (Het auteursrecht op deze afbeelding behoort toe aan [8]).

Dit wordt visueel weergegeven op figuur 3.4. Definitie: Scalar puntsvermenigvuldiging: Neem P ∈ E(K), en k ∈ Z∗p . Dan is kP = P | +P +P {z+ . . . + P} .

(3.5)

k

De scalar puntsvermenigvuldiging kan dus herleid worden naar een aantal puntsverdubbelingen.

3.1.1

Elliptische kromme discrete logaritmeprobleem

Cryptografische systemen gebaseerd op elliptische krommen (ECC) gebruiken rekenkundige bewerkingen op punten van deze krommen. Er kunnen dankzij deze elliptische krommen nieuwe wiskundige problemen gebruikt worden om getaltheoretisch veilige cryptografische systemen te ontwikkelen. Men kan nu een elliptische kromme discrete logaritmeprobleem definiëren waarvoor geen efficiënt algoritme bestaat om het op te lossen: Definitie: Het elliptische kromme discrete logaritmeprobleem: gegeven een elliptische kromme E gedefinieerd over een eindig veld Fq , een punt P ∈ E(Fq ) van orde n en een punt Q ∈ hP i, zoek het geheel getal l ∈ [0, n − 1] zodat Q = lP . 13


Figuur 3.3: Geometrische optelling van twee punten op een elliptische kromme: P + Q = R (Het auteursrecht op deze afbeelding behoort toe aan [8]).

l wordt dan de discrete logaritme van Q over de basis P genoemd. Het voordeel van dit probleem is dat sleutels van een beperkte lengte toch een grote graad van veiligheid kunnen garanderen. Waar RSA , dat gebruikt maakt van het factorisatieprobleem, een sleutellengte van minstens 1024 bit nodig heeft om veilig te zijn, heeft elliptische kromme cryptografie gebaseerd op de aangepaste versie van het discrete logaritmeprobleem al genoeg aan sleutels met een lengte van 160 bit om dezelfde graad van veiligheid te geven [11].

3.2

Paringen

Een tweede concept is de paring of pairing. Paringen werden initieel gebruikt om het elliptische kromme discrete logaritmeprobleem efficiënt op te lossen (De MOV-aanval) [17]. Paringen kunnen echter ook constructief ingezet worden in cryptografische systemen aangezien ze toelaten dat er nieuwe wiskundige problemen mee kunnen gebouwd worden om getaltheoretische cryptografische systemen te beveiligen. Definitie: Laat G1 en G2 additieve cyclische groepen zijn van orde p en Gt een multiplicatieve cyclische groep van orde p met P ∈ G1 , Q ∈ G2 generators van hun respectievelijke groepen. Dan is een paring een niet degeneratieve bilineaire mapping 14

3.2. Paringen

Figuur 3.4: Geometrische verdubbeling van een punt op een elliptische kromme: P + P = R (Het auteursrecht op deze afbeelding behoort toe aan [8]).

van: e : G1 × G2 → Gt .

(3.6)

Waarvoor volgende eigenschappen gelden:

1. Bilineair:

∀P, P 0 ∈ G1 en ∀Q, Q0 ∈ G2 : e(P + P 0 , Q) = e(P, Q)e(P 0 , Q) en e(P, Q + Q0 ) = e(P, Q)e(P, Q0 )

,

2. Niet degeneratief: e(P, Q) 6= 1, 3. e moet efficient te berekenen zijn. (3.7) De bilineairiteitseigenschap kan ook anders geformuleerd worden(additieve notatie voor G1 en G2 ): ∀a, b ∈ Z∗p : e(aP, bQ) = e(P, Q)ab .

(3.8)

Deze formulering van de eigenschap zal later gebruikt worden bij het bespreken van wiskundig moeilijke problemen met paringen. Indien G1 = G2 , dan spreken we van een symmetrische paring. 15


3.2.1

Wiskundige problemen gebaseerd op paringen

Paringen laten toe een grote groep van nieuwe wiskundige problemen te definiëren die gebruikt kunnen worden in cryptografische systemen. De meeste hiervan zijn gebaseerd op het Diffie-Hellmanprobleem dat reeds besproken werd in paragraaf 2.3. Eén van de varianten is het co-bilineaire Diffie-Hellmanprobleem: Definitie: Het co-bilineaire Diffie-Hellmanprobleem: gegeven P ∈ G1 ,Q ∈ G2 ,aP en bP met a, b ∈ Z∗p , bereken e(P, Q)ab . (3.9)

16

Hoofdstuk 4

Drempelcryptografie Na een inleiding van cryptografie in hoofdstuk 2 en een bespreking van elliptische krommen en paringen in hoofdstuk 3 wordt nu het concept drempelcryptografie besproken. Eerst wordt het algemene concept uitgelegd en worden de voordelen ervan besproken. Vervolgens wordt er verder ingegaan op iedere fase van drempelschema’s. Als laatste wordt het drempelschema van Simoens et al. [24] bekeken aangezien dit de basis vormt van de implementatie in deze thesis.

4.1

Drempelschema’s

Drempelcryptografische schema’s zijn een variant van publieke sleutel cryptografische systemen. Ze zorgen ervoor dat een aantal verschillende partijen kunnen samenwerken en als één entiteit kunnen deelnemen aan een publieke sleutel cryptografisch systeem. De geheime sleutel van de entiteit zal verdeeld worden over deze verschillende partijen. Echter niet alle partijen zijn tegelijk vereist om te kunnen deelnemen. Als n het totaal aantal partijen is dan wordt gesteld dat t het aantal partijen is dat minstens aanwezig moet zijn om de entiteit bijvoorbeeld een ontsleuteling uit te laten voeren. Deze parameter t wordt de drempel genoemd en men spreekt van een (t, n) drempelschema. De reden voor het ontwikkelen van deze drempelschema’s zit in de veiligheidsvoordelen ervan. Door de geheime sleutel over verschillende apparaten te verdelen en een juiste parameter t te kiezen, verbetert de veiligheid van publieke cryptografische systemen en ook de flexibiliteit ervan. Immers: • Het verlies van aantal delen van de sleutel kan opgevangen worden indien n > t. Zolang men beschikt over t delen van de sleutel kan men deze reconstrueren en berichten ontsleutelen. n − t stukken van de sleutel kunnen dus verloren gaan. Dit zorgt voor een verhoogde betrouwbaarheid en flexibiliteit, want niet alle apparaten moeten ten alle tijde aanwezig zijn voor een cryptografische actie. Problemen met defecte of gestolen apparaten kunnen dus opgevangen worden, alsook bijvoorbeeld apparaten met een lege batterij. 17

4. Drempelcryptografie

Figuur 4.1: Door 2 punten kunnen oneindig veel veeltermen van graad 2 getekend worden (Het auteursrecht op deze afbeelding behoort toe aan Vlsergey).

• Een aanvaller moet over minstens t stukken van de sleutel beschikken om de volledige sleutel te reconstrueren. Dit verhoogt de veiligheid van het cryptografische systeem. Bij drempelschema’s is het de bedoeling dat een geheim (secret), bijvoorbeeld de geheime sleutel, verdeeld wordt over een aantal partijen of apparaten. De partij die het geheim verdeelt wordt deler (dealer ) genoemd en de deelnemende partijen ontvangen elk een deel (share), ook sleuteldeel genoemd. Deze schema’s zijn opgebouwd uit een aantal fases: • De verdelingsfase. De deler kiest een geheim en berekent de sleuteldelen voor alle partijen. Deze sleuteldelen worden verstuurd naar deze partijen. • De verificatiefase. Iedere partij verifieert het verkregen sleuteldeel. Indien deze verificatie mislukt, betekent dit dat er iets misgelopen is bij het verdelen van het geheim en zal het drempelschema afgebroken worden. • De reconstructiefase. Het geheim wordt gereconstrueerd uitgaande van de verschillende sleuteldelen. • De toepassingsfase. Met het gereconstrueerde geheim wordt een cryptografische actie uitgevoerd zoals een versleuteling of ontsleuteling van een bericht.

4.1.1

De verdelingsfase

In de verdelingsfase wordt het geheim, bijvoorbeeld een private sleutel, verdeeld in sleuteldelen voor alle partijen. Shamir ontwierp een systeem om een geheim te verdelen over verschillende partijen dat voldoet aan bovenstaande voorwaarden [23]. Het is gebaseerd op het feit dat een functie f (x) van graad t − 1 volledig bepaald is door t punten ervan. Figuur 4.1 toont dat door 2 punten oneindig veel veeltermen van graad 2 getekend kunnen worden. Om deze veelterm volledig te bepalen zijn dus minstens 3 punten vereist. Deze eigenschap werd door Shamir uitgebuit.

18

4.1. Drempelschema’s

Figuur 4.2: Visuele voorstelling van Shamir’s geheimverdelingsschema (Het auteursrecht op deze afbeelding behoort toe aan Michael Frei).

Voor een (t, n) drempelschema wordt een veelterm van graad t − 1 gekozen: f (x) = a0 +a1 x+a2 x2 +. . .+at xt−1 . a0 wordt gelijkgesteld aan het te verdelen geheim. Dit is het punt waar de veelterm de y-as snijdt. Vervolgens krijgt iedere partij die deelneemt een punt op de veelterm toegewezen: (x1 , f (x1 )), (x2 , f (x2 )), . . . , (xn , f (xn )). Iedere verzameling van t punten kan de veelterm en vervolgens het geheim reconstrueren. Bovendien is het onmogelijk iets over de veelterm of het geheim te zeggen indien men over minder dan t punten beschikt zoals reeds bleek uit figuur 4.1. Figuur 4.2 geeft het schema van Shamir visueel weer.

4.1.2

De verificatiefase

De tweede fase van drempelschema’s is de verificatiefase. Deze fase is vereist om sleuteldelen die fouten bevatten te kunnen ontdekken. Deze fouten kunnen ontstaan bij het versturen van de sleuteldelen of kunnen ook opzettelijk gemaakt worden door een partij die het drempelschema wil verstoren. Om ervoor te zorgen dat de sleuteldelen die de deler uitzendt naar de ander partijen geen fouten bevatten, werd door Feldman een systeem voorgesteld om deze sleuteldelen te verifiëren op hun correctheid [5]. Zulke schema’s worden verifieerbare geheimverdelingschema’s genoemd(VSS schema’s). De geheime sleutel wordt verdeeld met het schema van Shamir uit paragraaf 4.1.1. De coëfficiënten a0 , a1 , . . . , at van de gekozen veelterm worden echter gepubliceerd, verborgen in de exponent van een generator g van de groep Zp waarin een discreet logaritmeprobleem gedefinieerd kan worden. Deze verbintenissen of commitments Ak = g ak mod p voor k = 0, . . . , t worden dan door de andere partijen gebruikt om te verifiëren of het sleuteldeel dat ze gekregen hebben geen fouten bevat door na te gaan dat g f (zi ) =

t Y

k

(Ak )i mod p.

(4.1)

k=0

19

4. Drempelcryptografie Een probleem van dit schema is dat het gekozen geheim a0 ook indirect uitgezonden wordt in de vorm g a0 . Indien men dus over een oneindige hoeveelheid rekenkracht beschikt, kan men dus alle waardes van a0 afgaan en kijken of één van deze overeenstemt met g a0 . Dit schema is dus enkel getaltheoretisch veilig. Pedersen publiceerde om deze reden een variant op dit schema dat informatietheoretisch veilig is indien de aanvaller logg h niet kan berekenen [18]. Het gebruikt twee willekeurig P P gekozen veeltermen f (x) = k ak z k en f 0 (x) = k a0k z k van graad t − 1. f (0) bevat het geheim a0 . De coëfficiënten worden verborgen in de exponent van de generator g van de groep Zp en h ∈ Z∗p , een subgroep van Zp en vormen zo de verbintenissen: 0

Ak = g ak hak mod p voor k = 0, . . . , t.

(4.2)

Alle partijen kunnen hun verkregen sleuteldeel verifiëren door volgende vergelijking te controleren: g

f (zi ) f 0 (zi )

h

=

t Y

k

(Ak )i mod p.

(4.3)

k=0

De voorgaande verificatiesystemen vereisen een beveiligd kanaal tussen de deler en de andere partijen. Dat maakt dat een deelnemende partij enkel zijn eigen verkregen sleuteldeel kan verifiëren. Een partij kan dus niet weten of de deler aan alle partijen juiste sleuteldelen gegeven heeft. Heidarvand en Villar stelden een publiek verifieerbaar geheimverdelingschema (PVSS schema) op dat toelaat dat alle partijen alle sleuteldelen kunnen verifiëren [9]. Dit schema vereist ook geen beveiligd kanaal meer tussen de deler en de andere partijen. De sleuteldelen worden dus over publieke kanalen verstuurd en de deler kan door elke partij gecontroleerd worden alsook door een derde partij die buiten het drempelschema staat. Dit zorgt ervoor dat alle partijen eenzelfde onveilig kanaal kunnen gebruiken om te communiceren. Er wordt gebruik gemaakt van paringen om deze publieke verifieerbaarheid mogelijk te maken. De verdelingsfase van het schema is gebaseerd op het schema van Shamir uit paragraaf 4.1.1 met de aanpassing dat het sleuteldeel verborgen wordt in de exponent van de publieke sleutel van het apparaat waarvoor het deel bedoeld is: f (xi )

Ci = S i

.

(4.4)

Iedereen kan deze sleuteldelen verifiëren door de volgende gelijkheid te verifiëren: e(Xi , Si ) = e(P, Ci ) met Xi =

t−1 Y

k

Aii .

(4.5)

k=0

Indien deze verificatie mislukt, wordt het drempelschema gestopt.

4.1.3

De reconstructiefase

Als een geheime sleutel verdeeld is over de verschillende partijen moet deze ook kunnen gereconstrueerd worden om gebruikt te kunnen worden voor het versleutelen of ontsleutelen van berichten. Hiertoe dient de reconstructiefase. In deze fase worden 20

4.1. Drempelschema’s minstens t apparaten bij elkaar gebracht om de geheime sleutel te reconstrueren. Ze bestaat uit twee delen: • De apparaten die hun sleuteldelen ter beschikking stellen moeten bewijzen dat deze overeenkomen met de sleuteldelen van de verdelingsfase. Dit kan gebeuren met dezelfde test als tijdens de verificatiefase [7] of met een nulkennisbewijs; • t delen van het geheim worden terug gecombineerd tot het totale geheim. Hiervoor kan Lagrangeveelterminterpolatie gebruikt worden. Nulkennisbewijzen Nulkennisbewijzen (zero knowledge proofs) worden gebruikt om informatie te verifiëren zonder dat deze informatie bekend gemaakt dient te worden. Zulke bewijzen moeten aan drie kenmerken voldoen: 1. Volledigheid: Als het bewijs positief is, zal een eerlijke verifieerder overtuigd zijn van de juistheid. 2. Soliditeit: Als het bewijs negatief is, kan een eerlijke verifieerder niet overtuigd worden dat het bewijs toch positief is. 3. Nulkennis: Als het bewijs positief is, zal een eerlijke verifieerder niet meer weten dan dat het bewijs positief is. Dit kan ge¨ıllustreerd worden met het voorbeeld van de grot van Ali Baba. Deze grot is cirkelvormig. Er zijn dus twee paden die in de grot samenkomen en een magische deur voorkomt dat je van de ene gang naar de andere kan(Figuur 4.3). Om de deur te openen, heb je een wachtwoord nodig. Peggy kent dit wachtwoord en Victor wil het wachtwoord van Peggy kopen, maar enkel als ze het juiste wachtwoord heeft. Peggy wil het wachtwoord pas geven als Victor betaald heeft. Een nulkennisbewijs kan Peggy en Victor uit hun impasse helpen: • Victor wacht buiten de grot als Peggy naar binnen gaat en een willekeurige gang kiest. • Victor gaat nu aan de ingang van de grot staan en roept welke gang Peggy moet uitkomen. • Peggy heeft nu 50 procent kans dat ze al in de juiste gang is. Is ze echter in de verkeerde gang en kent ze het wachtwoord, dan kan ze toch nog naar de juiste gang indien ze het wachtwoord kent. Kent ze het wachtwoord niet en zit ze in de verkeerde gang, dan kan ze Victor er niet van overtuigen dat ze het wachtwoord heeft. • Dit kan zoveel keer herhaald worden als Victor nodig acht om ervan overtuigd te zijn dat Peggy het wachtwoord kent.

21


Figuur 4.3: De grot van Ali Baba. Dit is een voorbeeld van een nulkennisbewijs(Het auteursrecht op deze afbeelding behoort toe aan Michael Frei).

Langrangeveelterminterpolatie Lagrangeveelterminterpolatie laat toe om aan de hand van een aantal punten van een veelterm deze veelterm te reconstrueren. Er zijn zoveel punten nodig als de graad van de veelterm +1. De reconstructie van de veelterm is dan: f (x) =

t X

yj lj (x),

(4.6)

j=1

met lj (x) =

Y 0≤m≤k m6=j

4.1.4

x − xm . xj − xm

(4.7)

Gebruik in cryptografische systemen

Tot nu toe werd er enkel gesproken over het verdelen en reconstrueren van een geheim tussen verschillende partijen. Als echter een private sleutel verdeeld wordt, kan deze gebruikt worden in publieke sleutel cryptografische systemen zoals besproken in hoofdstuk 2. Deze cryptografische systemen hoeven zelfs niet te weten dat de sleutel die gebruikt wordt, verdeeld is opgeslagen. Voorbeelden van zulke publieke sleutel cryptografische systemen die met drempelschema’s kunnen samenwerken zijn het ElGamalversleutelingsschema of het Schnorr digitale handtekeningsschema. Elgamalversleutelingsschema Het ElGamalversleutelingsschema [4] is een publieke sleutel versleutelingsschema zoals besproken in paragraaf 2.2.1.

22

4.1. Drempelschema’s De partij die een bericht m wil handtekenen kiest een private sleutel x : 0 ≤ x ≤ q − 1 en de overeenkomstige publieke sleutel y is dan y = g x . • Versleuteling: De verzender van het bericht m kiest een willekeurige k : 0 ≤ k ≤ q − 1 en berekent de willekeurigheid R = g k . Vervolgens wordt s berekend: s = y k . Het versleutelde bericht is dan e = ms = my k . • Ontsleuteling: Het versleutelde bericht e wordt ontsleuteld met s: m = es−1 . Schnorr digitale handtekeningsschema Het Schnorr digitale handtekeningsschema [22] kan gedefinieerd worden in een cyclische multiplicatieve groep G van orde q met generator g waarin het discrete logaritmeprobleem moeilijk oplosbaar is. Er moet ook een hashfunctie H beschikbaar zijn. De partij die een bericht m wil handtekenen kiest een private sleutel x : 0 < x < q en de overeenkomstige publieke sleutel y is dan y = g x . • Handtekening: Kies een willekeurige k : 0 < k < q, bereken r = g k en e = H(mkr) (waar k concateneren is). De handtekening s is dan s = (k−xe) mod q. • Verificatie: Bereken rver = g s y e en ever = H(mkrver ). Als e = ever dan is de handtekening geverifieerd.

4.1.5

Gedistribueerde sleutelgeneratie

De tot nu toe besproken drempelschema’s hebben één partij die het volledige geheim bewaart, deler, en stukken ervan verdeelt naar de andere partijen. In sommige gevallen wil men voorkomen dat 1 partij het volledige geheim kent. Dit kan het geval zijn als we een geheime sleutel van een publieke sleutel cryptografisch systeem willen verdelen zonder dat iemand deze sleutel volledig in zijn bezit heeft. Gedistribueerde sleutelgeneratie (DKG) is een drempelschema waarbij dit niet het geval is. Voor deze schema’s is dus geen vertrouwde partij nodig die het volledige geheim in bewaring houdt en het schema initieert. Gedistribueerde sleutelgeneratieschema’s volgen een gelijkaardige werkwijze als voorgaande drempelschema’s met het verschil dat iedere partij die deelneemt, een VSS of PVSS uitvoert ( [7]) zoals in de voorgaande paragraaf gedefinieerd. Iedereen wordt dus als deler beschouwd. Men spreekt dus over n delers in een DKG schema: • De verdelingsfase. Iedere partij initieert een VSS-schema door een geheim te kiezen en dit te verdelen naar de andere partijen. Er worden dus n VSS-schema’s opgestart die tegelijkertijd kunnen lopen. • De verificatiefase. Iedere partij verifieert de verkregen sleuteldelen van de andere partijen. Per apparaat zijn er dus n sleuteldelen die geverifieerd moeten 23

4. Drempelcryptografie worden. Als alle sleuteldelen van een deler correct verifiëren, wordt de deler aan een lijst met gekwalificeerde delers (QUAL) toegevoegd. Nadien telt ieder apparaat de correct geverifieerde sleuteldelen Cj,i uit QUAL bij elkaar op om zo één totaal sleuteldeel Ci per apparaat i te krijgen:

Ci (x) =

X

Cj,i , met Cj,i het sleuteldeel van deler j voor apparaat i .

i∈QU AL

(4.8) • De reconstructie- en toepassingsfase. Het geheim wordt gereconstrueerd uitgaande van de verschillende totale sleuteldelen Ci als dit het vereist is voor een versleuteling of ontsleuteling zoals reeds uitgelegd in paragraaf 4.1.3 en 4.1.4.

4.2

Het basisdrempelschema voor de implementatie

Tot nu toe werd een algemeen overzicht gegeven van drempelcryptografie en geheimverdelingsschema’s. In deze paragraaf wordt een specifiek drempelschema, ontwikkeld door Simoens et al. [24] besproken. Dit schema heeft een aantal kenmerken dat het ideaal maakt om als basis te dienen voor de implementatie in deze thesis. Deze kenmerken hebben betrekking tot de deelname van apparaten met een beperkte hoeveelheid rekenkracht en zonder veilige opslag aan drempelschema’s. Allereerst worden deze kenmerken besproken en ook hoe dit schema het mogelijk maakt voor zulke apparaten met beperkingen om aan drempelschema’s deel te nemen. Vervolgens wordt het publiek verifieerbaar geheimverdelingsschema dat ze ontwikkelden besproken en daarna het volledige gedistribueerde sleutelgeneratieschema. Ten slotte wordt het versleutelen en ontsleutelen van berichten met dit schema besproken.

4.2.1

Kenmerken van het schema

Er zijn reeds vele theoretische geheimverdelingsschema’s gepubliceerd( [23], [18], [5] en [9]). Het schema van Simoens et al. [24] maakt gebruik van elliptische krommen om de benodigde sleutellengtes klein te houden. Om publieke verifieerbaarheid te creëren, wordt er gebruikgemaakt van paringen. Het schema biedt echter ook twee belangrijke kenmerken die voor de implementatie in deze thesis zeer relevant zijn: • Door een aanpassing van het Elgamalversleutelingsschema kunnen apparaten met beperkte rekenkracht deelnemen aan ontsleutelingsacties. Ze moeten hiervoor slechts één scalar puntsvermenigvuldiging uitvoeren en een eigen private publieke sleutelpaar kunnen aanbieden. Dit wordt verder besproken in paragraaf 4.2.4. • Het verhullen van de sleuteldelen in de exponent van de publieke sleutel van het apparaat in kwestie zorgt dat de sleuteldelen over publieke kanalen verstuurd kunnen worden, alsook opgeslagen op plaatsen die voor iedereen toegankelijk zijn. Een speciale reconstructiefase zorgt er ook voor dat het sleuteldeel nooit 24

4.2. Het basisdrempelschema voor de implementatie De deler verdeelt het geheim xQ, met een willekeurig gekozen x ∈R Z` : 1. De deler construeert twee veeltermen f (z) en f 0 (z) van graad t door willekeurige coëfficiënten ck , c0k ∈R Z∗` te kiezen voor k = 0 . . . t , behalve c0 , want c0 = x : f (z) = c0 + c1 z + · · · + ct z t

,

f 0 (z) = c00 + c01 z + · · · + c0t z t .

De deler zendt de verbintenissen uit Ak = ck P + c0k P 0

,

k = 0...t .

2. Voor ieder apparaat Di , berekent en zendt de deler xi Si , x0i Si

met

xi = f (i) , x0i = f 0 (i)

,

i = 1...n .

3. Ieder apparaat verifieert de uitgezonden sleuteldelen voor alle Di door volgende vergelijking na te gaan: eˆ(P, xi Si ) · eˆ(P 0 , x0i Si ) =

t Y

k

eˆ(Ak , Si )i .

(4.9)

k=0

Als deze test mislukt wordt het schema afgebroken. Figuur 4.4: Het publiek verifieerbaar geheimverdelingsschema van [24].

in onbeveiligde vorm, niet verhult in de exponent van de publieke sleutel, benodigd is. Deze aanpassingen worden besproken in paragraaf 4.2.3.

4.2.2

Publiek verifieerbaar geheimverdelingsschema

Het publiek verifieerbaar geheimverdelingsschema dat in de paper gebruikt wordt in [24] is gebaseerd op het publiek verifieerbaar schema van Pedersen zoals uitgelegd in 4.1.2. Figuur 4.4 geeft de verschillende stappen aan. Na afloop van het schema zal ieder apparaat een sleuteldeel hebben gekregen van de deler.

4.2.3

Gedistribueerde sleutelgeneratieschema’s

Vervolgens wordt het PVSS-schema gebruikt in een gedistribueerde sleutelgeneratieschema. In de eerste fase voert iedere partij die deelneemt een PVSS schema uit en stuurt naar elke partij een sleuteldeel. Dit wordt besproken in figuur 4.5. Deze sleuteldelen worden vervolgens gevalideerd. In de tweede fase wordt een nulkennisbewijs uitgevoerd om de sleuteldelen die aangeleverd worden te verifiëren. Een overzicht van deze tweede fase wordt gegeven in figuur 4.6. 25

4. Drempelcryptografie Alle deelnemende apparaten Di voeren gelijktijdig een PVSS schema uit. De beveiligde subdelen worden enkel uitgestuurd als alle verbintenissen van alle apparaten ontvangen zijn. 1. Elke Di kiest twee veeltermen fi (z) en fi0 (z) van graad t door willekeurige coëfficiënten ci,k , c0i,k ∈R Z∗` voor k = 0 . . . t: fi (z) = ci,0 + ci,1 z + · · · + ci,t z t

,

fi0 (z) = c0i,0 + c0i,1 z + · · · + c0i,t z t ,

en zendt de verbintenissen uit Ai,k = ci,k P + c0i,k P 0

,

k = 0...t .

2. Voor ieder apparaat Dj , berekent en zendt Di xij Sj , x0ij Sj

met

xij = fi (j) , x0ij = fi0 (j) .

3. Ieder apparaat verifieert de uitgezonden delen voor alle Di door te testen dat eˆ(P, xij Sj ) · eˆ(P 0 , x0ij Sj ) =

t Y

eˆ(Ai,k , Sj )j

k

.

k=0

Elke Di die niet gediskwalificeerd is, wordt toegevoegd aan de lijst met gekwalificeerde P apparaten, QUAL. De private sleutel van de groep is gedefinieerd als xQ = i∈QUAL ci,0 Q . Voor elke Di wordt zijn beveiligde sleuteldeel als volgt berekend X Ci = x i S i = xji Si . j∈QUAL

Figuur 4.5: Fase 1 van het gedistribueerde sleutelgeneratieschema van Simoens et al. [24]

4.2.4

Versleuteling en ontsleuteling

Na een gedistribueerde sleutelgeneratiefase is er een publieke sleutel beschikbaar waarmee berichten versleuteld kunnen worden. Er wordt gebruik gemaakt van een gewijzigde versie van het ElGamalschema uitgelegd in paragraaf 4.1.4. Een overzicht van het gewijzigde schema wordt gegeven in figuur 4.7. • De versleutelingsfase blijft ongewijzigd. Een bericht m wordt versleuteld met de publieke sleutel y en een willekeurig gekozen k ∈ Z∗p : e = my k .

(4.10)

• De ontsleutelingsfase is herschreven om ervoor te zorgen dat totale geheime sleutel niet gereconstrueerd hoeft te worden. Er wordt rechtstreeks gebruik 26

4.2. Het basisdrempelschema voor de implementatie De gekwalificeerde apparaten stelleng xi ter beschikking om de publieke sleutel y = g x te berekenen. 1. Elke Di in QUAL zendt g xi en si P 00 . Men kan eenvoudig verifiëren dat eˆ(si P 00 , Q) = eˆ(P 00 , Si ) . Ook kiest elke Di een willekeurige ri ∈R Z∗` en zendt de verbintenissen g ri en ri Si . 2. Generatie van de uniforme uitdaging, nodig in het nulkennisbewijs. • Apparaten QUAL voeren een gedeelde PVSS uit en bekomen beveiligde delendi Si en d0i Si , die worden verzonden en geverifieerd. De verbintenissen van van de gedeelde PVSS worden genoteerd als Bi,k . • Open reconstructie van dQ. Apparaten in QUAL zenden di Q en d0i Q. Deze worden geverifieerd door te testen dat eˆ(P, di Q) · eˆ(P

0

, d0i Q)

=

t Y

eˆ(Bk , Q)j

k

k=0

for

Bk =

X

Bi,k .

i∈QU AL

• Als d˜ = ψ(dQ), waar ψ een bijective mapping is van G2 naar Z` . ˜ ˜ 3. Elke Di zendt Zi = s−1 i (ri Si + dCi ) = (ri + dxi )Q. Ieder apparaat kan verifiëren dat ˜

eˆ(P, Zi ) = g ri (g xi )d

˜

and eˆ(si P 00 , Zi ) = eˆ(P 00 , ri Si ) · eˆ(P 00 , Ci )d .

xi 4. De publieke Q xi λi sleutel y wordt berekend van t + 1 correct geverifieerde g als y= g .

Figuur 4.6: Fase 2 van het gedistribueerde sleutelgeneratieschema van Simoens et al. [24]

gemaakt van de sleuteldelen van de verschillende partijen. De private sleutel van het deelnemende apparaat wordt gebruikt om samen met de willekeurigheid R een partiële ontsleuteling te berekenen: Di = s−1 i R.

(4.11)

Vervolgens zal één apparaat deze partiële ontsleutelingen ontvangen en verifiëren door de volgende vergelijking te testen: eˆ(Di , Si ) = eˆ(R, Q).

(4.12)

Dit apparaat zal ook de uiteindelijke ontsleuteling uitvoeren aan de hand van Langrangeinterpolatie met de sleuteldelen van t + 1 apparaten.

27


• Versleuteling: Om een bericht m ∈ GT met de publieke sleutel y te versleutelen, wordt een willekeurige k ∈R Z∗` gekozen en dan is de versleutelde boodschap: (R, e) = (kP, my k ) ∈ G1 × GT . • Ontsleuteling: Om de boodschap (R, e) te ontsleutelen, levert ieder apparaat Di een partiële ontsleuteling −1 Di = s−1 i R = si kP ∈ G1 .

Het combinerend apparaat ontvangt alle Di en verifieert eˆ(Di , Si ) = eˆ(R, Q). Daarna combineert hij t + 1 bijdrages om het bericht te ontsleutelen: Y e met d = eˆ(Di , Ci )λi . m= d Figuur 4.7: De aangepaste versie van het ElGamalversleutelingsschema van [24].

28

Hoofdstuk 5

Ontwerp Zoals reeds eerder aangegeven is het doel van deze thesis het analyseren van de praktische aspecten van een implementatie van een drempelschema voor apparaten met beperkte rekenkracht en zonder veilige opslag. De voorgaande hoofdstukken boden een theoretische inleiding in de drempelcryptografie. Ook werd één specifiek drempelschema besproken in paragraaf 4.2. Dit drempelschema van Simoens et al. [24] wordt ge¨ımplementeerd in deze thesis. In dit hoofdstuk wordt deze praktische zijde van het schema belicht en zullen er oplossingen gezocht worden om deze praktische problemen op te lossen. Ook wordt er een overzicht gegeven van het gehele programmaverloop.

5.1

Praktische aspecten en ontwerpbeslissingen

De keuze voor het schema van Simoens et al. [24] als basis voor het programma vloeit voort uit het feit dat hierdoor de twee belangrijkste problemen, die deze thesis probeert aan te pakken, omzeild kunnen worden: • De beperking op de rekenkracht van de apparaten wordt omzeild door een aanpassing van de ontsleuteling uitgelegd in paragraaf 4.2.4. Een apparaat moet slechts één scalar puntsvermenigvuldiging kunnen uitvoeren om aan het ElGamalschema te kunnen deelnemen. • De noodzaak voor veilige opslag wordt omzeild door het sleuteldeel eerst te verhullen in de exponent van de publieke sleutel van het apparaat waarvoor het bestemd is. Ook is het schema zo geschreven dat het sleuteldeel nooit onverhuld nodig is. Deze kenmerken zorgen ervoor dat dit schema een goede basis vormt voor onze implementatie. Er blijven echter nog een aantal praktische problemen. Deze praktische problemen worden in deze paragraaf besproken alsook de oplossingen die ervoor ontworpen zijn. 29

5. Ontwerp

5.1.1

Soorten apparaten

Het drempelschema van Simoens et al. [24] is gebaseerd op bilineaire paringen voor de verificaties. Deze paringen zijn echter rekenintensief. Om het mogelijk te maken voor apparaten met beperkte rekenkracht om aan dit schema deel te nemen moet een gedeelte van de verificatie door een externe partij gedaan worden of moet ze weggelaten worden. Aangezien voor de veiligheid van het schema getracht moet worden om bij zo weinig mogelijk apparaten de verificatiefase weg te laten, is er gekozen om drie categorien van apparaten te creëren: • Apparaten met een grote hoeveelheid aan rekenkracht. Zij kunnen vlot paringen uitvoeren en kunnen deelnemen aan het volledige schema en voeren zelf de verificatie van de delers uit. Deze categorie van apparaten is ook de enige die een reconstructie van de publieke sleutel of een ElGamalontsleuteling kan initialiseren, omdat voor beide operaties een veelvoud aan paringen moet uitgerekend worden. • Apparaten met een gemiddelde hoeveelheid rekenkracht. Zij nemen deel aan het volledige schema maar laten de verificatieberekeningen over aan een vertrouwde derde partij omdat het uitvoeren van paringen traag is. • Apparaten met een beperkte hoeveelheid rekenkracht. Deze apparaten kunnen geen paringen uitvoeren. Aangezien er bij het gedistribueerde sleutelgeneratieschema van paragraaf 4.2.3 buiten de verificatiefase nog steeds één paring uitgevoerd moet worden, kunnen deze apparaten niet actief aan de reconstructiefase van het gedistribueerde sleutelgeneratieschema deelnemen. Ze zullen wel een totaal sleuteldeel ontvangen maar kunnen dat niet inzetten om de publieke sleutel te reconstrueren. Zij kunnen enkel deelnemen aan de ElGamalontsleuteling zoals uitgelegd in paragraaf 4.2.4 voor de ontsleuteling van berichten en niet aan het gedistribueerde sleutelgeneratieschema. Apparaten uit deze drie categorieën kunnen dus samen deelnemen aan het drempelschema dat ge¨ımplementeerd is mits in achtneming van de voorgaande voorwaarden. Er zijn echter nog 2 extra voorwaarden. Voor de reconstructie van de publieke sleutel moet minstens één apparaat uit eerste categorie aanwezig zijn om de sleuteldelen te combineren tot de publieke sleutel. Dezelfde voorwaarde geldt voor de ElGamalontsleuteling. Dit is nodig omdat beide fases paringen gebruiken voor het combineren van de sleuteldelen.

5.1.2

Het verificatieprobleem

Er is dus gekozen om voor bepaalde apparaten de verificatie over te laten aan een onafhankelijke vertrouwelijke derde partij. Deze partij zal dan de verificatie uitvoeren met behulp van paringen en vervolgens een oordeel vellen over de deler in kwestie. Dit antwoord wordt dan verstuurd naar de apparaten die hierom gevraagd hadden. Deze werkwijze is mogelijk aangezien alle sleuteldelen publiek verifieerbaar zijn. De 30

5.1. Praktische aspecten en ontwerpbeslissingen

Figuur 5.1: Opstelling van de verschillende apparaten invoering van deze onafhankelijke vertrouwelijke verificatiepartij brengt twee nieuwe problemen met zich mee: • Er moet kunnen aangetoond worden dat het ontvangen antwoord effectief afkomstig is van de verificator en niet van een buitenstaander die probeert het drempelschema te verstoren. Om dit probleem op te lossen zijn er meerdere oplossingen mogelijk. De verificator zou via lampjes kunnen aangeven of een deler eerlijk is of niet. De gebruiker moet dan zelf de oneerlijke delers verwijderen uit het schema. Een andere oplossing kan gevonden worden in het handtekenen van de berichten die de verificator uitzendt. De berichten zouden bijvoorbeeld met een Schnorr handtekeningsschema zoals besproken in paragraaf 4.1.4 gehandtekend kunnen worden. Dit zorgt wel voor een extra overhead in het schema omdat het apparaat deze handtekening moet verifiëren. • De verificator wordt eerlijk verondersteld. Indien de verificator valsspeelt in het schema kan dit ernstige gevolgen hebben. We gaan er in deze thesis vanuit dat deze onafhankelijke partij eerlijk werkt. Figuur 5.1 geeft een overzicht van de opstelling en de communicatie tussen de verificator en de verschillende categorieën van apparaten. Voor de implementatie in deze thesis is gekozen om de oneerlijke delers met lampjes aan te geven op de verificator en ze door de gebruiker te laten verwijderen.

5.1.3

Het inverteringsprobleem

Het gedistribueerde sleutelgeneratieschema van Simoens et al. [24] definieert de publieke sleutel van een apparaat i als si Q met si de private sleutel van het apparaat 31

5. Ontwerp en Q een generator van G2 . Deze notatie zorgt er echter voor dat bij de ontsleuteling van een bericht ieder apparaat dat hieraan deelneemt de inverse van zijn private sleutel moet berekenen, want de partiële ontsleuteling, zoals besproken in paragraaf 4.2.4, is Di = s−1 (5.1) i R. Inverteren is echter een operatie die veel rekenkracht vergt en we wensen de benodigde rekenkracht tot een minimum te herleiden. Om deze reden is ervoor gekozen om de publieke sleutel te definiëren als s−1 Q. Dit maakt dat de inverse van de private sleutel niet meer vereist is in de ontsleutelingsfase van het aangepaste ElGamalschema, want de partiële ontsleuteling is nu Di = si R. (5.2) Deze aanpassing maakt dat er wel een inversie vereist is bij het berekenen van de publieke sleutel tijdens de gedistribueerde sleutelgeneratiefase. Deze stap gebeurt echter slechts eenmaal en dit vormt dus geen grote extra rekenkost.

5.2

Programmaverloop

Het verloop van het programma, dat het drempelschema uitvoert, wordt nu geschetst: Allereerst kan het programma in drie belangrijke delen opgesplitst worden: 1. De initialisatiefase; 2. De gedistribueerde sleutelgeneratiefase; 3. De toepassingsfase.

5.2.1

De initialisatiefase

De initialisatiefase voert twee belangrijke taken uit: • De publieke paramaters zoals de generators van de verschillende groepen worden gekozen en verdeeld naar alle partijen. • Er wordt een lijst gemaakt van alle apparaten die binnen bereik zijn en willen deelnemen aan het drempelschema.

5.2.2

De gedistribueerde sleutelgeneratiefase

Deze fase verzorgt de gedistribueerde sleutelgeneratie. 1. De PVSS fase. Ieder apparaat dat deelneemt, kiest zijn veeltermen en berekent voor alle partijen een sleuteldeel. Deze sleutel wordt dan verhult in de exponent van de publieke sleutel van de bestemmeling. 2. De verificatiefase. Alle sleuteldelen worden geverifieerd door de partijen die daartoe in staat zijn of door een onafhankelijke derde partij. 32

5.2. Programmaverloop 3. De samenvoegfase. Iedereen telt de sleuteldelen van de geverifieerde delers op om zo één sleuteldeel te bekomen. 4. De nulkennisfase. De apparaten die willen deelnemen aan de publieke sleutel reconstructie voeren een nulkennisbewijs uit om aan te tonen dat hun sleuteldeel correct is. 5. De publieke sleutel reconstructie. De publieke sleutel wordt gereconstrueerd uit t sleuteldelen via Langrangeveelterminterpolatie zoals besproken in paragraaf 4.1.3. Op het einde van deze fase is er een geheime en publieke sleutelpaar verdeeld over de apparaten. Er kan nu deel genomen worden aan cryptografische toepassingen met dit sleutelpaar.

5.2.3

De toepassingsfase

Als laatste wordt het sleutelpaar gebruikt in een ElGamalversleuteling zoals besproken in paragraaf 4.2.4. Een bericht wordt versleuteld met de gereconstrueerde publieke sleutel. Vervolgens stellen t apparaten hun sleuteldeel ter beschikking om het bericht te ontsleutelen. Indien het ontsleutelde bericht overeenstemt met verzonden bericht werkt het programma correct.

33

Hoofdstuk 6

Implementatie In dit hoofdstuk wordt de effectieve implementatie van het ontwerp uit hoofdstuk 5 besproken. Er wordt stilgestaan bij de opbouw van het programma en de gebruikte software bibliotheken die de implementatie vereenvoudigd hebben. In het eerste deel wordt de implementatie op PC bekeken en in het tweede deel wordt de implementatie op FPGA besproken.

6.1 6.1.1

Implementatie op PC Programeertaal

De keuze van de programmeertaal kan de implementatie van een programma heel erg be¨ınvloeden. Voor dit programma werd de taal C1 gebruikt. Deze taal is ontstaan als een taal om systeemsoftware en programma’s voor ingebedde systemen te schrijven. Ze biedt laag niveau procedures aan om het geheugen en andere hardware rechtstreeks aan te spreken. Dit maakt dat er eenvoudig zeer krachtige en efficiënte code mee geschreven kan worden. Aangezien het uiteindelijke doel was om de code werkende te krijgen op zulke ingebedde systemen, zoals zakcomputers, leek C de meest voor de hand liggende keuze. Ook de beschikbaarheid van meerdere cryptografische software bibliotheken vormde een pluspunt.

6.1.2

Softwarebibliotheken

Softwarebibliotheken vereenvoudigen het schrijven van programma’s. Ze maken abstractie van de onderliggende functionaliteit door methodes aan te bieden die gebruikt kunnen worden door andere programma’s om deze functionaliteit op te roepen. De programmeur heeft dus geen kennis van de onderliggende algoritmes nodig om deze te gebruiken. Er bestaan verschillende bibliotheken die methodes specifiek voor cryptografische 1

Meer informatie over C is te vinden op http://www.open-std.org/jtc1/sc22/wg14/

35

6. Implementatie P arameter

Waarde

a b q r

17946557270010392439606013 13747689455785428065471621 24195439571169018236015557 3456491367309157050000913

Tabel 6.1: De waardes van de parameters van de gebruikte curve van type D81 [14].

systemen implementeren. Voor de implementatie van dit drempelschema werd gekozen voor de Pairing-Based Cryptography bibliotheek (PBC) geschreven door Ben Lynn aan de universiteit van Stanford [14]. Deze bibliotheek is gebaseerd op de GMP bibliotheek(GNU Multi-Precision Library) [20]. Dit is de standaard bibliotheek in Linuxsystemen om bewerkingen op grote getallen uit te voeren. De PBC-bibliotheek implementeert volgende methodes: • Rekenkundige bewerkingen over elliptische krommen. • Paringen over elliptische krommen. Er zijn 5 verschillende categorieën van elliptische krommen ge¨ımplementeerd in deze bibliotheek [15]. • Type A krommen hebben de vergelijking y 2 = x3 + x over het veld Fq voor een priemgetal q, de ingebedde graad k = 2 en de paringen over deze kromme zijn symmetrisch. • Type D krommen met de vergelijking y 2 = x3 + ax + b met een ingebedde graad k = 6. • Type E krommen met de vergelijking y 2 = x3 + ax + b met ingebedde graad k = 1. • Type F krommen met de vergelijking y 2 = x3 + b met ingebedde graad k = 12. • Type G krommen met de vergelijking y 2 = x3 + ax + b met ingebedde graad k = 10. Tabel 6.1 toont de gekozen parameters voor de krommen van het type D die gekozen is in het programma. Deze parameters werden gekozen omwille van beperkingen op de grootte van de punten van de elliptische kromme op het FPGA platform. Voor elliptische krommen wordt een r van ±160 bit vooropgesteld om de veiligheid van een RSA systeem met een sleutellengte van 1024 bit te evenaren [11]. Deze kromme heeft echter een r van ±81 [15]. Ze is dus niet veilig genoeg. Echter indien een geoptimaliseerde ECC coprocessor gebruikt zou worden op FPGA in plaats van een Microblaze processor, kunnen krommen die veilig genoeg zijn wel in deze implementatie gebruikt worden [13]. 36

6.1. Implementatie op PC

6.1.3

Programmaontwerp

Apparaten Om het geheel overzichtelijk te houden wordt ieder apparaat intern voorgesteld door een datastructuur Device die alle parameters van het apparaat bevat zoals het geheime en publieke sleutelpaar en de sleuteldelen die eraan zijn toegewezen. Indien het schema gebruikt gaat worden met effectieve apparaten, kan de informatie van deze datastructuren gewoon naar hen worden doorgespeeld. Modulariteit Het programma is modulair geschreven. Functionaliteit is gegroepeerd zodat enkel het benodigde deel van het programma dient ingeladen te worden om een functie uit te voeren. Dit maakt de code overzichtelijk en voorkomt dat er fouten in het programma sluipen. De volgende modules kunnen onderscheiden worden: • De ECC-module initialiseert de elliptische krommen en verzorgt alle rekenkundige operaties over deze krommen. • De paringmodule biedt een methode aan om paringen uit te voeren over deze elliptische krommen. • De interpolatiemodule zorgt voor het berekenen van de Lagrangeveelterminterpolatie. • De versleutelings- en ontsleutelingsmodule implementeert de ElGamalversleuteling en ontsleuteling van berichten. • De nulkennisbewijsmodule biedt methodes aan om nulkennisbewijzen uit te voeren. • De DKG-module of gedistribueerde sleutelgeneratiemodule zorgt voor het uitvoeren van de PVSS schema’s en de DKG schema’s • De IO-module of input- outputmodule biedt methodes aan om te communiceren met de gebruiker. Ook heeft deze module methodes om via een ethernet netwerk te communiceren met andere apparaten. De modules kunnen onafhankelijk van elkaar werken. Enkel de modules die de gebruiker nodig heeft dienen ingeladen te worden. Dit beperkt de programmagrootte. Inkapseling De softwarebibliotheek is volledig ingekapseld in het programma. Dit wil zeggen dat methodes van de bibliotheek niet rechtstreeks worden aangeroepen maar via zelfgeschreven inkapselingsmethodes. Dit zorgt ervoor dat er eenvoudig van bibliotheek gewisseld kan worden of zelfs speciale coprocessoren ingezet kunnen worden om de bibliotheek te vervangen. Ook is de functionaliteit om te communiceren tussen 37

6. Implementatie

Figuur 6.1: Schakelmatrix met logische blokken van een FPGA (Het auteursrecht op deze afbeelding behoort toe aan Xilinx).

apparaten ingekapseld zodat eenvoudig andere manieren van communiceren gebruikt kunnen worden.

6.2

Implementatie op FPGA

Na de implementatie van het programma op computer is er een programma geschreven dat een apparaat met een beperking in rekenkracht en opslag simuleert. Deze simulatie gebeurde op FPGA. In deze paragraaf wordt een overzicht gegeven van de kenmerken van het programma alsook van het FPGA platform dat gebruikt werd om deze apparaten te simuleren.

6.2.1

Field-programmable Gate Array

Een Field-programmable Gate Array(FPGA) is een ge¨ıntegreerd circuit dat na fabricatie geprogrammeerd en geherprogrammeerd kan worden. Zo kan de functionaliteit van het circuit eenvoudig aangepast worden. Ze bestaan uit verschillende logische blokken. De interactie tussen deze blokken wordt met behulp van een hardwarebeschrijvingstaal geprogrammeerd. Voorbeelden van zulke talen zijn VHDL en Verilog. FPGA’s worden vaak in de industrie gebruikt omdat dit de ontwikkelingstijd van producten kan verkorten, want de ontwikkeling van specifieke hardware is overbodig. Ook kan de FPGA geherprogrammeerd worden als na verkoop van het product een probleem gevonden wordt. Opbouw FPGA Een FPGA is hoofdzakelijk opgebouwd uit een matrix met volgende blokken [26]: 38

6.2. Implementatie op FPGA

Specif icatie

Waarde ($)

Klokf requentie RAM geheugen CLB 0 s Slices T echnologie

20 MHz 64 Mbyte 612 2448 90 nm

Tabel 6.2: Specificaties van de Xilinx Spartan 3ES250 FPGA [29].

• IOB’s of Input and Output Blokken. Deze blokken zorgen voor de verbinding tussen de interne logica en externe signalen die via de vele input- en outputpinnen toekomen. • CLB’s of Configurable Logic Blokken. CLB’s worden gebruikt om logische functies op te bouwen. Ze bestaan uit zogenaamde slices. Een slice bevat programmeerbare lookuptables, multiplexers, flipflops, e.d. De FPGA die in deze thesis gebruikt werd, heeft CLB’s met telkens vier slices zoals getoond in figuur 6.2. • RAM of Random Access Memory. RAM wordt gebruikt om gegevens in op te slaan tijdens het uitvoeren van bewerkingen. Deze blokken zijn gegroepeerd in een schakelmatrix met in het midden CLB’s en aan de rand ervan IOB’s. De RAM modules zijn gegroepeerd in twee banken tussen de CLB’s. Dit is zichtbaar in figuur 6.1. De connecties tussen de verschillende blokken kunnen geprogrammeerd worden om de functionaliteit te bepalen. Deze blokken worden gecombineerd door de programmacode om de gewenste functionaliteit te creëren. De taak van de programmeur is de beperkte hoeveelheid logische blokken zo efficiënt mogelijk te benutten. De FPGA die voor deze thesis gebruikt is, is een Xilinx Spartan 3ES250 [29]. Deze FGPA is ontworpen in een 90nm fabricatieproces. Enkele belangrijke specificaties zijn te vinden in tabel 6.2. Xilinx Microblaze Xilinx Microblaze [28] is een zogenaamde soft core processor. Dit wil zeggen dat de processor gesimuleerd wordt op de FPGA met de standaard logische blokken die er voor handen zijn. Figuur 6.3 geeft een schematische voorstelling van de verschillende delen van de processor. De prestaties van deze processor liggen echter ver onder die van een processor die rechtstreeks in aangepaste hardware ontwikkeld is, maar het voordeel is dat men met deze Microblaze zonder al te veel moeite rechtstreeks C-code kan uitvoeren op een FPGA. De implementatie van Microblaze wordt geleverd bij de Software Development Toolkit van Xilinx [28]. De processor kan volledig zelf samengesteld worden door modules die niet vereist zijn weg te laten. Dit zorgt ervoor dat de processor minder CLB’s inneemt. Het is een 32bit processor gebaseerd op een 39

6. Implementatie

Figuur 6.2: Schema van een Configurable Logic Blok van een Xilinx Spartan 3E FPGA (Het auteursrecht op deze afbeelding behoort toe aan Xilinx).

Reduced Instruction Set (RISC) architectuur. Deze instructieset verschilt van de x86 instructieset die gebruikt wordt in bijna alle processoren voor PC’s. Om deze reden moeten de softwarebibliotheken, die vereist zijn op FPGA, gecompileerd worden naar deze andere instructieset.

6.2.2

Implementatie

Zoals in hoofdstuk 5 uitgelegd, moet een apparaat met een beperkte hoeveelheid rekenkracht enkel één scalar puntsvermenigvuldiging uitvoeren. Om zo een apparaat te simuleren op FPGA moet deze een scalar puntsvermenigvuldiging kunnen uitvoeren. Aangezien de implementaties op computer en op FPGA samen eenzelfde drempelschema bepalen, moet de elliptische kromme, waarover de scalar puntsvermenigvuldiging op FPGA gebeurt, dezelfde zijn als op de computer. Er werd dan ook gekozen om de PBC-bibliotheek uit hoofdstuk 6 om te bouwen zodat deze op FPGA kon uitgevoerd worden. Xilinx biedt immers een hardware-ontwerp voor een processor die ge¨ımplementeerd kan worden op FPGA die de mogelijkheid biedt om C-code uit te voeren. Deze processor heeft de naam Microblaze. 40

6.2. Implementatie op FPGA

Figuur 6.3: Schema van de Xilinx Microblaze architectuur (Het auteursrecht op deze afbeelding behoort toe aan www.eetimes.com).

Compileren van de bibliotheken Zoals reeds eerder besproken in paragraaf 6.1.2 maakt de PBC-bibliotheek gebruik van GMP. Dus allereerst moet de GMP-bibliotheek gecompileerd worden voor de Microblaze processor. De Xilinx Software Development Toolkit gebruikt een compiler die code rechtstreeks kan vertalen naar instructies voor de Microblaze processor. Deze compiler is gebaseerd op GCC [25]. GCC is een compiler die geschreven is voor linux en die naar verschillende architecturen kan compileren. Met het volgende commando kan de broncode van GMP gecompileerd worden voor Microblaze: . / c o n f i g u r e −−d i s a b l e −s h a r e d −−b u i l d=x868−gcc−l i n u x −gnu −−h o s t=none−unknown−gnu CC=mb−g c c make make i n s t a l l Zulk een soort compilatie wordt een crosscompilatie genoemd. Er wordt immers op een x86 architectuur code gecompileerd die uitgevoerd kan worden op een andere architectuur nl. de Microblaze architectuur.

41

6. Implementatie Ook de PBC bibliotheek is vereist op FPGA om de puntsvermenigvuldiging uit te voeren. Van deze bibliotheek werden echter enkel de methodes die vereist waren om de elliptische kromme te initialiseren en om de scalar puntsvermenigvuldiging uit te voeren gecompileerd voor Microblaze. Communicatie met de computer Voor de communicatie met de computer is gekozen voor een ethernetverbinding 2 . Op deze manier kunnen alle apparaten eenvoudig met elkaar spreken en informatie uitwisselen. Dit is mogelijk omdat, zoals uitgelegd in hoofdstuk 4, geen private kanalen vereist zijn tussen de apparaten. Voor de implementatie van de ethernet-interface op FPGA werd een door Xilinx aangeboden Intellectual Property blok gebruikt, lwIP genoemd [27]. Het voordeel van het gebruik van een ethernet verbinding is dat vele mobiele apparaten deze verbinding reeds ondersteunen. Ook is het ethernetprotocol geschikt om meerdere apaparaten over één kanaal te laten communiceren.

2

42

Meer informatie over het ethernetprotocol kan gevonden worden op http://www.ieee802.org/3/

Hoofdstuk 7

Radio Frequency Identification In dit hoofdstuk wordt een voorbeeld van een apparaat met beperkte rekenkracht besproken nl. de RFID of Radio frequentie identificatie tag. De kenmerken ervan worden besproken alsook de reden waardoor deze ingebedde apparaten gebruikt worden voor talloze doeleinden. De RFID tags die voor de thesis van belang zijn, bevatten een implementatie van een scalar puntsvermenigvuldiging over een elliptische kromme. Er wordt van deze soort een specifiek ontwerp [13] bekeken en er wordt getracht deze te integreren in de implementatie van hoofdstuk 6.

7.1

Algemene kenmerken

RFID of Radio frequentie identificatie is een technologie die bestaat uit een lezer en tag die over korte afstanden via radiogolven met elkaar communiceren. Het communicatieprotocol begint telkens op dezelfde manier: de lezer zendt een signaal uit dat opgevangen wordt door de tag en deze zal een reactie versturen. Men kan twee soorten RFID tags onderscheiden [10]: • Passieve RFID tags halen hun energie uit de radiogolf uitgezonden door de lezer via inductie. Ze zijn dus afhankelijk van de lezer voor hun energie en dit maakt dat de afstand waarop ze uitgelezen kunnen worden zeer beperkt is. Dit legt ook een zware beperking op aan het maximale vermogenverbruik van de tag en zorgt ervoor dat de beschikbare rekenkracht zeer beperkt is. • Actieve RFID tags hebben zelf een energiebron. Dit maakt ze minder afhankelijk van de lezer en laat toe dat ze vanop een grotere afstand uitgelezen kunnen worden en krachtigere berekeningen kunnen uitvoeren. Actieve tags zijn echter duurder in productie dan passieve en ook hun energiebron is geen eeuwig leven beschoren. RFID tags kunnen zeer goedkoop gefabriceerd worden. Ze worden tegenwoordig veel gebruikt in de logistieke sector om bijvoorbeeld producten te traceren in magazijnen. Ze bieden meer functionaliteit dan het oudere barcodesysteem omdat ze meer productkenmerken kunnen opslaan. 43

7. Radio Frequency Identification

Figuur 7.1: Een voorbeeld van een passieve RFID tag met de circulaire metaalbanen aan de zijkant voor inductieve energieopwekking (Deze afbeelding is eigendom van SecuringPharma.com).

7.1.1

Huidige ontwikkelingen

De vooruitgang in de ontwikkeling van ge¨ıntegreerde circuits heeft ervoor gezorgd dat de RFID tags steeds ingewikkeldere operaties kunnen uitvoeren. Dit opent de deur voor nieuwe toepassingen met RFID. Zo duiken er elliptische kromme cryptografische implementaties voor RFID op in de literatuur [13], [6]. Zulke systemen kunnen ge¨ıntegreerd worden in het ge¨ımplementeerde drempelschema in deze thesis. RFID tags zullen onder de categorie van de apparaten met een beperkte hoeveelheid rekenkracht vallen die enkel kunnen deelnemen aan de ontsleutelingsfase. Het gebruik van RFID tags in het schema heeft als voordeel dat men goedkoop het aantal deelnemende apparaten kan verhogen. Deze tags kunnen in schoenen gestopt worden of in kleren bevestigd worden. De veiligheid en flexibiliteit van het schema kan dus goedkoop verhoogd worden met RFID tags.

7.2

ECC coprocessor

Op de afdeling COSIC van het departement Elektrotechniek van de Katholieke Universiteit Leuven is een elliptische kromme cryptografische coprocessor ontworpen die zeer compact is en uitermate weinig energie verbruikt [13]. Om deze redenen kan deze coprocessor gebruikt worden in RFID tags. Tabel 7.1 geeft een overzicht van de belangrijkste specificaties van de ECC processor. Deze ECC processor maakt het mogelijk voor deze RFID tag om publieke sleutelcryptografie toe te passen. De processor implementeert de volgende elliptische curve: 44

7.3. Integratie met het drempelschema

Figuur 7.2: Layout van de ECC coprocessor ontworpen door Lee et al. [13]. Specif icatie

Waarde

Klokf requentie Bewerkingen V ermogenverbruik RekentijdvoorSchnorrhandtekening T echnologie

323 kHz ECC Puntsmul. en mod bewerk. 10 µW 243.17 ms 130 nm

Tabel 7.1: Specificaties van de elliptische kromme cryptografische processor van [13].

y 2 + xy = x3 + ax2 + b, met b = 1 en a ∈ GF (2163 ).

(7.1)

De ECC processor is in staat een elliptische kromme scalar puntsvermenigvuldiging uit te voeren over deze curve alsook modulaire bewerkingen (additie en multiplicatie) in GF (2163 ).

7.3

Integratie met het drempelschema

Op het eerste zicht lijkt de ECC processor aan de eisen van het drempelschema te voldoen. Er is echter een probleem. De elliptische kromme die gebruikt wordt in de processor is echter niet paringvriendelijk. Dit betekent dat een paring over deze curve zeer moeilijk te implementeren is. En aangezien op verschillende plaatsen in het schema paringen ingezet worden, kan deze kromme dus niet gebruikt worden in onze implementatie. Een elliptische kromme wordt paringvriendelijk genoemd als 45

7. Radio Frequency Identification de ingebedde graad k van de kromme klein is. Deze ingebedde factor k bepaalt de orde van de elliptische kromme. Het is dus zo een waardemeter voor de complexiteit van de kromme en dus ook voor de bewerkingen over deze kromme. Vaak wordt een lage k waarde vooropgesteld [15]. Bij grote waardes van k kan de paring theoretisch gedefinieerd worden, maar een efficiënte implementatie is niet mogelijk. Voor deze kromme is k ≈ 1046 . Deze ECC processor kan dus geen paringen efficiënt uitrekenen en niet in het ontwerp gebruikt worden. Een andere ECC processor ontworpen voor RFID die een paringvriendelijke elliptische kromme implementeert, zou wel in het schema opgenomen kunnen worden. Tot op heden heb ik echter in de literatuur geen ontwerp van zo een ECC processor gevonden die dit toelaat binnen de vermogenbeperkingen van een RFID tag.

46

Hoofdstuk 8

Resultaten In dit hoofdstuk worden de verschillende testen besproken die uitgevoerd werden op de implementatie uit hoofdstuk 6. Allereerst worden een aantal meetresultaten besproken van belangrijke rekenintensieve delen van de implementatie. Vervolgens wordt een integratietest besproken die de implementatie toepast op een situatie uit het echte leven en worden de resultaten hiervan besproken.

8.1

Testplatformen

De platformen waarop de testen uit de volgende paragrafen uitgevoerd worden: • PC: Intel Core i5 460M met 4GB DDR3 RAM-geheugen en een 5400tpm SATA harde schijf. • FPGA: Xilinx Spartan 3E waarvan de specificaties te vinden zijn in tabel 6.2.

8.2

Tijdsmetingen

Om een idee te krijgen van de performantie van ingebedde systemen en ook van de complexiteit van bepaalde operaties zijn er een aantal testen uitgevoerd.

8.2.1

Initialisatie van de elliptische kromme

Het initialiseren van de elliptische krommen vergt zeer veel rekenkracht. Indien deze initialisatie niet mogelijk is, kunnen verdere operaties over deze krommen ook niet uitgevoerd worden. Om deze reden zijn er een aantal tests uitgevoerd om te zien of en hoe snel bepaalde elliptische krommen op FPGA en op PC kunnen ge¨ınitialiseerd worden. Tabel 8.1 geeft de resultaten van deze tests. Op de computer is gebleken dat de initialisatie van elliptische krommen geen probleem vormt en ook zeer snel gebeurt. Op FPGA echter is gebleken dat de initialisatie vele grootteordes trager is. Ook staan er strengere beperkingen op de grote van de getallen waarmee gewerkt wordt. Dit vormde een probleem bij de initialisatie van de elliptische kromme van 47

8. Resultaten P latf orm

Type D159

Type D81

PC F P GA

72ms -

60ms 35s

Tabel 8.1: Testresulaten van de ECC initialisatie. P latf orm

Type D159

Type D81

Type F

PC F P GA

4.5ms -

4.2ms −s

57ms -

Tabel 8.2: Resultaten van de snelheidstest van paringen.

het type D159 [14]. Om deze reden is dan ook gekozen voor de kromme van type D81 zoals beschreven in paragraaf 6.1.2. Deze kromme werkt met kleinere coëfficiënten.

8.2.2

Paringen

Paringen zijn ook rekenintensieve operaties. Om deze reden werden er ook een aantal snelheidstesten gedaan om te zien of ze binnen redelijke termijnen uitgevoerd konden worden op de testplatformen. Ook hier werden de testen uitgevoerd voor elliptische krommen van type D159 alsook type D81 en type F. De resultaten van de testen zijn terug te vinden in tabel 8.2. Op FPGA bleken paringen niet uitvoerbaar door de beperkingen van de Microblaze processor. Het grote snelheidsverschil tussen paringen van type D en type F ligt erin dat paringen over krommen van type F meer rekenintensief zijn maar hierdoor ook wel een hogere veiligheid geven [14].

8.3

Integratietest

Deze integratietest combineert de verschillende implementaties van deze thesis om zo een drempelschema te simuleren. Aangezien het doel van de thesis het analyseren en het implementeren van drempelcryptografie op RFID tags was, bestaan de testen uit opstellingen met meerdere apparaten,waaronder RFID tags, die een cryptografische actie uitvoeren.

8.3.1

Situatieschets

Als cryptografische actie is er gekozen voor het identificeren van een persoon aan een deur die beveiligd is met een toegangskaartsysteem. De deur heeft een lijst met publieke sleutels van personen waaraan toegang verleend moet worden. Deze personen gebruiken het drempelschema dat in deze thesis ge¨ımplementeerd is. Het identificatieproces bestaat uit de volgende stappen: 1. De persoon die zich wil identificeren maakt zich kenbaar aan de deur door zijn publieke sleutel te sturen. 48

8.3. Integratietest 2. Het toegangssysteem zal kijken of deze publieke sleutel in de lijst met toegelaten publieke sleutels zit. Indien dit het geval is, zal het een willekeurige boodschap m kiezen en deze versleutelen met de verkregen publieke sleutel via een ElGamalversleuteling en deze versleuteling uitsturen naar de persoon. 3. De persoon combineert t apparaten om het bericht te ontsleutelen met de aangepaste versie van het ElGamalschema uit paragraaf 4.2.4 en stuurt het ontsleutelde bericht terug naar het toegangssysteem. 4. Het toegangssysteem verifieert of het verkregen bericht overeenstemt met het willekeurig gekozen bericht m. Indien dit het geval is, wordt de persoon correct ge¨ıdentificeerd en krijgt hij toegang.

8.3.2

Testopstellingen

De testopstellingen zijn gebaseerd op het hierboven beschreven toegangskaartsysteem. Er zijn drie opstellingen gemaakt met telkens een andere samenstelling van apparaten om zo verschillende combinaties van apparaten met en zonder beperkte rekenkracht te hebben zoals gedefinieerd in paragraaf 5.1.1. Test 1 De eerste test bestond uit twee categorieën van apparaten: apparaten met een grote en een gemiddelde hoeveelheid rekenkracht. Deze apparaten werden allen op PC gesimuleerd. De verificatiefase bij de apparaten met een gemiddelde hoeveelheid rekenkracht werd uitgevoerd door een vertrouwde verificator zoals beschreven in paragraaf 5.1.2. Het verloop van deze eerste test kan in drie delen gesplitst worden: • Er wordt getest of de functionaliteit die gevraagd was, aangeboden wordt. Eerst worden alle apparaten gecombineerd en wordt er zo een publieke sleutel gereconstrueerd. Vervolgens worden er apparaten weggelaten totdat men onder de drempelwaarde zit. Zo wordt er getest of het drempelschema dan effectief faalt. • De hoeveelheid apparaten die deelnemen aan het drempelschema wordt gevarieerd. Zo wordt er gekeken welke invloed dit heeft op de totale rekentijd. Resultaten van deze testen kunnen teruggevonden worden op figuur 8.1. Er werd gewerkt met een vaste drempelwaarde van 4. Er kan geconstateerd worden dat de rekentijd ongeveer lineair stijgt met de hoeveelheid apparaten die deelnemen. Dit komt door het toenemend aantal paringen die uitgevoerd moeten worden in de verificatiefase. • De drempelwaarde wordt gevarieerd om te zien welke invloed dit heeft op de benodigde rekentijd. Er wordt getest met een vaste hoeveelheid apparaten nl. 20. De resultaten van deze test zijn te zien op figuur 8.2. Merk hier op dat de 49

8. Resultaten

Figuur 8.1: De resultaten van de variatie van het aantal apparaten in testsituatie 1.

Figuur 8.2: De resultaten van de variatie van de drempelwaarde in testsituatie 1.

benodigde rekentijd niet zo snel stijgt als in de vorige test. De reden hiervoor is dat het aantal paringen dat uitgevoerd moet worden tijdens de verificatiefase hetzelfde blijft. De stijging is dus te wijten aan andere berekeningen zoals bijvoorbeeld het aantal paringen dat tijdens de reconstructie van de publieke sleutel dient uitgevoerd te worden.

50

8.3. Integratietest Test 2 De tweede test combineert apparaten uit alle drie de categorieën. Een apparaat met beperkte rekenkracht en zonder veilige opslag werd gesimuleerd op FPGA. De FPGA communiceert met de PC via een ethernetverbinding zoals besproken in paragraaf 6.2.2 Het verloop van deze tweede test kan ook weer in drie delen gesplitst worden: • Er wordt getest of de implementatie op FPGA effectief een scalar puntsvermenigvuldiging kan uitvoeren. De test bestaat uit het versturen van een punt op de elliptische kromme naar de FPGA via ethernet. Het vermenigvuldigen van dit punt met een scalar en vervolgens het terugzenden van de uitkomst naar de PC. Deze test nam 9s in beslag. Dit is verschillende grootteordes meer dan dezelfde operatie op PC. • De hoeveelheid apparaten met veel rekenkracht die deelnemen aan het drempelschema wordt gevarieerd zoals reeds eerder gedaan in testsituatie 1. Zo wordt er gekeken welke invloed dit heeft op de totale rekentijd. Resultaten van deze testen kunnen teruggevonden worden op figuur 8.3. Er werd gewerkt met een vaste drempelwaarde van 4. Er kan geconstateerd worden dat de rekentijd ongeveer lineair stijgt met de hoeveelheid apparaten die deelnemen. Ook is de benodigde tijd veel groter dan in testsituatie 1. Men kan zien dat het telkens ongeveer 9s langer duurt. Dit is de tijd die in de eerste situatie opgemeten werd bij het uitvoeren van een scalar puntsvermenigvuldiging op FPGA. Men kan dus veronderstellen dat wanneer er veel apparaten met beperkte hoeveelheid rekenkracht deelnemen aan het schema de benodigde rekentijd sterk stijgt. • De drempelwaarde wordt gevarieerd om te zien welke invloed dit heeft op de benodigde rekentijd. Er wordt getest met een vaste hoeveelheid apparaten nl. 20. De resultaten van deze test zijn te zien op figuur 8.2. Men kan dezelfde conclusies trekken als bij eenzelfde test in testsituatie 1. Merk ook hier weer het verschil op dat de testen ongeveer 9s langer duren dan in testsituatie 1. Dit is weer het gevolg van de de scalar puntsvermenigvuldiging op FPGA.

Test 3 Een laatste test met een hardware implementatie van een RFID ECC processor bleek onmogelijk omdat de gebruikte elliptische kromme van de ECC processor niet paringvriendelijk was zoals reeds besproken in paragraaf 7.2.

51

8. Resultaten

Figuur 8.3: De resultaten van de variatie van het aantal apparaten in testsituatie 2.

Figuur 8.4: De resultaten van de variatie van de drempelwaarde in testsituatie 2.

52

Hoofdstuk 9

Besluit Deze thesis toont aan dat het mogelijk is voor apparaten met een beperkte hoeveelheid rekenkracht om deel te nemen aan drempelschema’s. Om dit te bewijzen werd een implementatie van een drempelschema geschreven en werden er simulaties uitgevoerd die situaties uit het echte leven nabootsen zoals het identificeren van een persoon die toegang wil krijgen tot een deur beveiligd met een toegangskaartsysteem. Deze testen werden met succes volbracht, maar er moeten een aantal kanttekeningen bij gemaakt worden. Het is met deze implementatie bijvoorbeeld niet mogelijk om enkel apparaten met beperkte rekenkracht te gebruiken. Er is dus nog steeds minstens één apparaat nodig uit de eerste categorie van apparaten. Niettegenstaande deze beperkingen kunnen implementaties zoals in deze thesis toch al op korte termijn ingezet worden. Ze kunnen zo het beveiligingsprobleem van mobiele apparaten en informatie op een vernieuwende en goedkope manier oplossen.

9.1

Vervolgwerk

Onderzoek naar drempelschema’s is een vrij jong onderzoeksdomein. Er is dan ook zeer veel ruimte voor vervolgonderzoek op deze thesis mogelijk. Dit kan opgesplitst worden in twee richtingen: • Verbeteringen van de implementatie. Er werd gebruik gemaakt van een software bibliotheek die via een Microblaze processor op FPGA gesimuleerd werd. Deze softwarebibliotheek is echter niet geoptimaliseerd voor ingebedde apparaten zoals een FPGA. Indien men gebruik zou maken van een coprocessor die de scalar puntsvermenigvuldiging zou uitvoeren, zou dit minder logische blokken op de FPGA innemen. Een andere verbetering kan doorgevoerd worden in de verificatiefase. Er wordt hier voor bepaalde apparaten een vertrouwde verificator gebruikt. Indien echter deze verificator gecompromitteerd wordt, kan deze foutieve berichten uitsturen. In de huidige implementatie is er geen manier om te testen of de 53

9. Besluit verificator wel degelijk eerlijk is. Het schema zou echter kunnen aangepast worden zodat een apparaat uit de tweede categorie niet enkel op de verificator vertrouwt, maar ook op de verificaties van de apparaten uit de eerste categorie, die zelf de sleuteldelen controleren. Indien er dan een inconsistentie is tussen de antwoorden van de verificator en die van de andere aparaten, dan kan het schema afgebroken worden. Ook kan er verder onderzoek gedaan worden naar ECC coprocessoren die paringvriendelijke elliptische krommen implementeren met een laag vermogenverbruik voor RFID. Onderzoek naar het efficiënte implementaties van paringen die verenigbaar zijn met RFID is ook een mogelijk vervolgwerk. • Uitbreidingen van de functionaliteit. Het schema zelf zou kunnen uitgebreid worden door apparaten te categoriseren en bij bepaalde categorieën een maximumaantal apparaten die tegelijk kunnen deelnemen te bepalen. Als bijvoorbeeld je schoenen een RFID tag bevatten, zou een dief al je schoenen kunnen stelen en zo eenvoudig genoeg apparaten hebben om de drempel te bereiken. Als het schema echter rekening houdt dat je altijd maar maximaal twee schoenen draagt kan je de dief te slim af zijn. Ook kunnen bepaalde apparaten die extra beveiligingen ingebouwd hebben, zoals bijvoorbeeld biometrische beveiliging, een hogere waardering krijgen in het schema zodat er minder apparaten benodigd zijn om de drempel te bereiken.

54

Bibliografie [1] P. C. v. O. Alfred J. Menezes and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. ISBN: 0-8493-8523-7. [2] P. S. L. M. Barreto. The pairing-based crypto lounge. URL: http://www.larc. usp.br/~pbarreto/pblounge.html, laatst nagekeken op 2011-05-07. [3]

W. Diffie and M. E. Hellman. New directions in cryptography, 1976.

[4] T. El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In Proceedings of CRYPTO 84 on Advances in cryptology, pages 10–18, New York, NY, USA, 1985. Springer-Verlag New York, Inc. [5] P. Feldman. A practical scheme for non-interactive verifiable secret sharing. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, SFCS ’87, pages 427–438, Washington, DC, USA, 1987. IEEE Computer Society. [6] F. Frbass and J. Wolkerstorfer. Ecc processor with low die size for rfid applications. In 2007 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS (ISCAS 2007), pages 1835–1838. IEEE, 2007. [7] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Secure distributed key generation for discrete-log based cryptosystems. J. Cryptology, 20(1):51–83, 2007. [8] D. Hankerson, A. J. Menezes, and S. Vanstone. Guide to Elliptic Curve Cryptography. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2003. [9] S. Heidarvand and J. L. Villar. Public verifiability from pairings in secret sharing schemes. In Selected Areas in Cryptography, pages 294–308, 2008. [10] S. Holloway. Rfid: An introduction. URL: http://msdn.microsoft.com/ en-us/library/aa479355.aspx, laatst nagekeken op 2011-05-07. [11] E. II. Ecrypt ii yearly report on algorithms and key lengths (2010). URL: http://www.ecrypt.eu.org/documents/D.SPA.13.pdf, laatst nagekeken op 2011-05-07. [12] G. C. Kessler. An overview of cryptography. URL: http://www.garykessler. net/library/crypto.html#purpose, laatst nagekeken op 2011-05-07. 55

Bibliografie [13] Y. K. Lee, K. Sakiyama, L. Batina, and I. Verbauwhede. Elliptic-curve-based security processor for rfid. IEEE Trans. Comput., 57:1514–1527, November 2008. [14] B. Lynn. Pairing-based cryptography library. URL: http://crypto.stanford. edu/pbc/, laatst nagekeken op 2011-05-07. [15] B. Lynn. on the implementation of pairing-based cryptosystems, 2007. [16] A. Menezes. An introduction to pairing-based cryptography. notes from lectures given in, 2005. [17] A. Menezes, T. Okamoto, and S. A. Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory, 39(5):1639–1646, 1993. [18] T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’91, pages 129–140, London, UK, 1992. Springer-Verlag. [19] R. Peeters, M. Kohlweiss, and B. Preneel. Threshold things that think: Usable authorisation for resharing [poster abstract soups 2009]. [20] T. G. Project. Gnu multi-precision library. URL: http://gmplib.org/, laatst nagekeken op 2011-05-07. [21] R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21:120–126, 1978. [22] C.-P. Schnorr. Efficient identification and signatures for smart cards. In Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’89, pages 239–252, London, UK, UK, 1990. SpringerVerlag. [23] A. Shamir. How to share a secret. Commun. ACM, 22:612–613, November 1979. [24] K. Simoens, R. Peeters, and B. Preneel. Increased Resilience in Threshold Cryptography: Sharing a Secret with Devices That Cannot Store Shares. In M. Joye, A. Miyaji, and A. Otsuka, editors, Pairing-Based Cryptography Pairing 2010, volume 6487 of Lecture Notes in Computer Science, pages 116– 135, Yamanaka Hot Spring,JP, 2010. Springer-Verlag. [25] T. G. team. Gcc, the gnu compiler collection. URL: http://gcc.gnu.org/, laatst nagekeken op 2011-05-07. [26] .-C. Technologies. Fpga logic cells comparison. URL: http://www.1-core.com/ library/digital/fpga-logic-cells/, laatst nagekeken op 2011-05-07. 56

Bibliografie [27] Xilinx. Lightweight ip (lwip) application examples. URL: http://www.xilinx. com/support/documentation/application_notes/xapp1026.pdf, laatst nagekeken op 2011-05-07. [28] Xilinx. Microblaze processor reference guide. URL: http://www.xilinx. com/support/documentation/sw_manuals/xilinx13_1/mb_ref_guide.pdf, laatst nagekeken op 2011-05-07. [29] Xilinx. Spartan-3e fpga family data sheet. URL: http://www.xilinx.com/ support/documentation/data_sheets/ds312.pdf, laatst nagekeken op 201105-07. [30] R. S.-N. Yvo Desmedt, Mike Burmester and H. Wang. Threshold things that think(t4): security requirements to cope with theft of handheld/handless internet devices, 2001.

57

Drempelbeveiling mogelijk maken voor RFID

Recommend Documents