Ontwerp en Implementatie van een Anoniem E-Cash Systeem voor Computationeel Beperkte Platformen

Ontwerp en Implementatie van een Anoniem E-Cash Systeem voor Computationeel Beperkte Platformen Marijn Scheir

Thesis voorgedragen tot het behalen van de graad van Master of Science in de ingenieurswetenschappen: elektrotechniek, optie Telecommunicatie en telematica Promotoren: Prof. dr. ir. Bart Preneel Prof. dr. ir. Ingrid Verbauwhede Prof. dr. ir. Johan Driesen Assessoren: Prof. dr. ir. Claudia Diaz Prof. dr. ir. Johan Driesen Begeleiders: Ir. Alfredo Rial Ir. Josep Balash

Academiejaar 2011 – 2012

© Copyright KU Leuven Zonder voorafgaande schriftelijke toestemming van zowel de promotoren als de auteur 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 promotoren 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 Kindness is a brief preface to ten volumes of exaction. Ambrose Bierce

In september begon ik met vele vragen en nog weinig antwoorden aan het schrijven van deze masterthesis. Tien maanden later staan mijn bevindingen op papier. Het waren maanden van hard werken, vloeken en nachten wakker liggen, maar ook van ontdekken, groeien en slimmer worden. Op het einde van deze masterproef wil ik graag iedereen bedanken die mij geholpen heeft tijdens de realisatie ervan. Ik had dit resultaat nooit alleen kunnen realiseren en daarom wil ik volgende personen uitdrukkelijk bedanken: Mijn begeleiders Alfredo Rial en Josep Balash voor de begeleiding en de goede raad. Ik waardeer hun inzet en motivatie enorm; Mijn promotoren, prof. dr. ir. Bart Preneel, prof. dr. ir. Ingrid Verbauwhede, prof. dr. ir. Johan Driesen, om me de mogelijkheid te bieden om onderzoek te verrichten binnen het interessante domein van de cryptografie. Extra dank gaat hierbij naar professor Bart Preneel, want het waren zijn lessen Toegepaste Discrete Algebra en Cryptografie die mijn intresse voor cryptografie aanvankelijk gewekt hebben; Mijn ouders, Karen, Liesbet, Mira en Silke voor de morele steun; Alle anderen, voor de hulp en een duwtje in de rug wanneer het eens moeilijk was. Met deze masterthesis sluit ik het hoofdstuk van student Burgerlijk Ingenieur af en ga ik op zoek naar volgende uitdagingen. Ik zal deze tekst koesteren en af en toe nog eens vastnemen, want stiekem ben ik er toch een beetje trots op. Marijn Scheir

i

Inhoudsopgave Voorwoord

i

Samenvatting

iv

Lijst van figuren en tabellen

v

Lijst van notaties

vii

1 Inleiding

1

2 Basisbeginselen 2.1 Notatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Probabiliteitstheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Complexiteitstheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Turingmachines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 De Deterministische Eénbandige Turingmachine als Basismodel 2.4.2 Uitbreidingen op het Basismodel . . . . . . . . . . . . . . . . 2.5 Universal Composability Raamwerk . . . . . . . . . . . . . . . . . . 2.6 Abstracte Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Problemen in de Getallentheorie . . . . . . . . . . . . . . . . . . . . 2.8 Algoritmes in de Getallentheorie . . . . . . . . . . . . . . . . . . . . 2.8.1 Lagrange Voorstelling van een Positief Getal . . . . . . . . . 2.8.2 De Rabin-Miller Test . . . . . . . . . . . . . . . . . . . . . . . 2.8.3 Generatie van Waarschijnlijk Veilige Priemgetallen . . . . . . 2.9 Pseudorandom Functies . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Hash Functies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.11 Verbintenis Schema’s (Commitment Schemes) . . . . . . . . . . . . . 2.12 Zero Knowledge Proofs of Knowledge . . . . . . . . . . . . . . . . . . 2.13 Handtekening Schema’s . . . . . . . . . . . . . . . . . . . . . . . . .

5 6 6 8 9 9 11 12 14 18 19 19 19 19 19 20 21 23 25

3 Anonieme E-Cash 3.1 Systeemoverzicht . . . . . . . . . . . . . . . . . . . . . 3.2 Overzicht van Bestaande Anonieme E-Cash Systemen 3.3 Het Compacte Anonieme E-Cash Systeem . . . . . . . 3.3.1 Specificatie van de Veiligheidseigenschappen . . 3.3.2 Definitie van de Algoritmes . . . . . . . . . . . 3.3.3 Beschrijving van de Constructie . . . . . . . . . 3.3.4 Veiligheidsanalyse . . . . . . . . . . . . . . . .

27 27 31 33 33 34 35 37

ii

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

Inhoudsopgave 4 Anonieme E-Cash voor Computationeel Beperkte Platformen 4.1 Systeemoverzicht . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Het Voorgestelde Systeem . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Motivatie . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Specificatie van de Veiligheidseigenschappen . . . . . . . . 4.2.3 Definitie van de Algoritmes . . . . . . . . . . . . . . . . . 4.2.4 Beschrijving van de Constructie . . . . . . . . . . . . . . . 4.2.5 Veiligheidsanalyse . . . . . . . . . . . . . . . . . . . . . . 5 Gebruikte Tools en Hardware voor de Implementatie van het Voorgestelde E-Cash systeem 5.1 De Gebruikte Hardware . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 De Host . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.2 Het Vertrouwde Element . . . . . . . . . . . . . . . . . . . 5.1.3 De Verkoper en de Bank . . . . . . . . . . . . . . . . . . . 5.2 De Gebruikte Software Tools . . . . . . . . . . . . . . . . . . . . 5.2.1 Software Tools voor Alle Partijen . . . . . . . . . . . . . . 5.2.2 Software Tools voor de Host . . . . . . . . . . . . . . . . . 5.2.3 Software Tools voor het Vertrouwde Element . . . . . . . 5.2.4 Software Tools voor de Verkoper en de Bank . . . . . . . 5.3 De Communicatie tussen de Entiteiten . . . . . . . . . . . . . . . 5.3.1 Communicatie tussen de Host en het Vertrouwd Element 5.3.2 Communicatie tussen Gebruiker en Bank/Verkoper . . . . 6 De 6.1 6.2 6.3 6.4 6.5

Implementatie van het Voorgestelde E-Cash systeem Principe Schema van de Implementatie van de Gebruiker . . . Analyse van de Implementatie van het Vertrouwde Element . Analyse van de Implementatie van de Host . . . . . . . . . . Analyse van de Implementatie van de Verkoper en de Bank . Evaluatie van de realiseerbaarheid van het Voorgestelde E-Cash 6.5.1 Veiligheidsparameters . . . . . . . . . . . . . . . . . . 6.5.2 Performantie van het Gebruikersgedeelte . . . . . . . .

. . . . . . .

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

. . . . . . .

39 40 41 41 42 47 47 56

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

57 57 58 58 60 61 61 62 62 65 65 65 67

. . . . . . . . . . . . . . . . Systeem . . . . . . . .

71 72 72 80 82 82 82 83

7 Besluiten

87

A Aanzet tot een Veiligheidsanalyse in het Ideale/Reële Wereld Paradigma

93

B Overzicht van Enkele Belangrijke Algoritmes

103

C Javadoc van de Implementatie van het Vertrouwd Element

109

D Javadoc van de Implementatie van de Host

115

E Illustratie van de Interface Tussen Host en Vertrouwd Element

133

Bibliografie

137

iii

Samenvatting Sinds 1982 is er in de literatuur heel wat theoretisch onderzoek gedaan naar zogenaamde anonieme E-Cash systemen met als doel deze te gebruiken als digitaal alternatief voor fysiek geld. De omzetting van deze systemen naar bruikbare realisaties bleef uit doordat de performantie van het gebruikersdeel van een E-Cash systeem het knelpunt vormde. Gebruikers moeten namelijk een sabotagebestendig element gebruiken voor het uitvoeren van berekeningen. Het vernieuwende aan deze thesis is dat getracht wordt om dit probleem op te lossen door de berekeningen op het sabotagebestendige element zo minimaal mogelijk te houden. Gebaseerd op het compacte E-Cash systeem van Camenisch et al. hebben we alle operaties die niet dienen om de gebruiker te beschermen tegen corruptiepogingen door andere partijen, overgedragen naar een host systeem. De host is hierbij gebaseerd op een krachtig(er) mobiel apparaat dat niet sabotage bestendig is. Enkel de operaties die de gebruiker beschermen tegen corruptie werden op het sabotage bestendig element behouden. Het resulterende systeem moet uiteraard voldoen aan de eigenschappen die van een bruikbaar anoniem E-Cash systeem verwacht worden. Het systeemconcept is ook zodanig ontworpen dat zelfs indien de host gecorrumpeerd is, transacties onmogelijk zijn zonder het beveiligd element. In deze thesis hebben we, naast de beschrijving van het conceptueel model, een eerste aanzet gegeven om binnen het ‘ideale wereld/reële wereld’ paradigma te analyseren of het voorgestelde systeem de nodige eigenschappen bezit. Hierna hebben we de praktische realiseerbaarheid van het voorgestelde conceptueel model nagegaan. Dit gebeurde door het gebruikersdeel van het E-cash systeem op een gesplitste manier te implementeren. Het transmissie kanaal tussen gebruiker en de verkoper/bank werd eveneens behandeld. Om de doenbaarheid van de voorgestelde oplossing te evalueren werden hierna performantietests uitgevoerd op de implementatie van het gebruikersdeel. Hieruit werd snel duidelijk dat de responstijd van het sabotage beveiligd element ordes van grootte hoger was dan de responstijd van de berekeningen op het host gedeelte en hierdoor de bepalende factor bleef voor de doenbaarheid. Jammer genoeg moet hierbij vastgesteld worden dat, niettegenstaande de doorgevoerde optimalisaties in de berekeningen op het sabotage vrij element, de vastgestelde responstijden niet toe laten om de bestudeerde oplossing te gebruiken als basis voor een aanvaardbare realisatie. Dit betekent ook dat de bestudeerde werkwijze slechts tot succes kan leiden indien ze geïmplementeerd kan worden op snellere hardware, uitgerust met uitgebreide API ondersteuning. iv

Lijst van figuren en tabellen Lijst van figuren 1.1

Structuur van de thesis . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

Basismodel van een Turingmachine. . . . . . . . . . . . . . . . . . . . . Illustratie van het feit dat de omgeving moet beslissen of ze interageert met de reële wereld of met de ideale wereld. P1 en P2 stellen de partijen voor die in de reële wereld het protocol π uitvoeren en in de ideale wereld dummy partijen zijn. Pijlen duiden op input/output communicatie, lijnen zonder pijlen duiden op interactieve communicatie. . . . . . . . . 2.3 Illustratie van een ZKPK P K{(x, d) : y = gx ∧ A = V x Qd ∧ x ∈ Γ} . . .

10

2.1 2.2

3.1 3.2

4.1 4.2 4.3

5.1 5.2 5.3

5.4 5.5

6.1

Overzicht van de partijen die met elkaar interageren in een typisch anoniem E-Cash systeem . . . . . . . . . . . . . . . . . . . . . . . . . . Online versus offline E-Cash systeem. De bovenste figuur geeft het online systeem weer. De onderste figuur het offline systeem . . . . . . . . . . . Overzicht van de partijen die met elkaar interageren in een anoniem E-Cash systeem voor computationeel beperkte platformen . . . . . . . . Overzicht van de deelstappen en van de verzonden boodschappen tijdens het geldafhaling protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . Overzicht van de deelstappen en van de verzonden boodschappen tijdens het gelduitgave protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . Illustratie van de keuze van hardware en type van communicatie van/tussen de partijen van het voorgestelde E-Cash schema . . . . . . . Overzicht van de typische bouwblokken van een Java kaart . . . . . . . Weergave van hoe het RAM geheugen efficiënt wordt ingedeeld in ‘clear on reset’ en ‘clear on deselect’ geheugen. De figuur geeft ook weer hoe verschillende applets in EEPROM van dit geheugen gebruik maken. . . NFC in vergelijking met andere draadloze technologieën. . . . . . . . . . Illustratie van hoe we van de MSC gebruik kunnen maken om contactloos met de host te communiceren. . . . . . . . . . . . . . . . . . Illustratie van het principeschema van de implementatie van de gebruiker. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15 25

28 31

40 48 52

58 59

61 67 68

72 v

Lijst van figuren en tabellen 6.2

Het klassendiagram gebruikt bij het programmeren van de Java kaart. AsecEngine is de hoofdklasse en bevat alle functionaliteit voor het uitvoeren van het geldafhaling en gelduitgave protocol. Om tot een handelbare implementatie te komen, maakt AsecEngine gebruik van de klasse UnsignedBigNumber en Nist931PRNG. . . . . . . . . . . . . . . . 6.3 De NIST-recommanded X9.31 pseudo random nummer generator. . . . 6.4 Het klassendiagram gebruikt bij het programmeren van de Host. . . . .

73 76 81

Lijst van tabellen 4.1

4.2 4.3 5.1 5.2 5.3 5.4 6.1 6.2

Tabel die alle relevante informatie bijhoudt over gebruikers en hun afgehaalde en uitgegeven munten. De afkorting port. staat voor portefeuille. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tabel die alle relevante informatie bijhoudt over verkopers en hun ontvangen en bij de bank gestortte munten. . . . . . . . . . . . . . . . . Tabel die alle relevante gegevens bevat om anonimiteit te garanderen. .

42 42

Illustratie van welke voor ons belangrijke concepten uit de Java Standard editie wel en welke niet ondersteund worden in de Java Card editie. . . Illustratie van de belangrijke pakketten uit de Java Card editie. . . . . . Illustratie van de structuur van een c-APDU. . . . . . . . . . . . . . . . Illustratie van de structuur van een r-APDU. . . . . . . . . . . . . . . .

63 64 65 66

Illustratie van de belangrijke pakketten uit de Java Card editie. . Illustratie van het bereikte resultaat bij de optimalisatie van vermenigvuldigingen. . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Illustratie van de responstijd van de primitieve operaties die door vertrouwde element uitgevoerd moeten worden. . . . . . . . . . . 6.4 Responstijden voor het gebruikersgedeelte . . . . . . . . . . . . .

vi

42

. . . .

82

. . . . het . . . . . . . .

83 84 85

Lijst van notaties Such is the advantage of a well-constructed language that its simplified notation often becomes the source of profound theories. Pierre Laplacee

vii

Lijst van notaties

Afkortingen APDU API c-APDU CBC COD RAM COR RAM CPU CRHF EEPROM ITI ITM IDE MAC MDC MSC NFC OWF OWHF PRNG PID RAM r-APDU ROM SDK SID TM TPDU UC ZKPK

Application Protocol Data Unit Application Programming Interface Command APDU Cipher Block Chaining Clear On Detect RAM Clear On Reset RAM Central Processing Unit Collision Resitant Hash Functie Electrically Erasable Programmable Read-Only Memory Interactive Turingmachine Instantie Interactive Turingmachine Integrated Development Environment Message Authentication Code Manipulation Detection Code Mobile Security Card Near Field Communication One-Way Function One-Way Hash Function Pseudo Random Nummer Generator Partij IDentificatiecode Random Acces Memory response-APDU Read Only Memory Software Development Kit Sessie IDentificatiecode Turingmachine Transmission Protocol Data Unit Universal Composability Zero-Knowledge Proof Of Knowledge

Cryptografische algoritmes 3DES AES DES MD-x RSA RIPEMD SHA-x viii

Tripple DES Advanced Encryption Standard Data Encryption Standard Message Digest x Ron Shamir Adleman RACE Integrity Primitives Evaluation Message Digest Secure Hash-x Algorithm

Hoofdstuk 1

Inleiding The beginning is easy, it’s the continuing that’s hard. Anoniem.

Dagelijks worden er in onze consumptiemaatschappij ontelbare betalingen uitgevoerd via verschillende betalingssystemen. Drie partijen spelen hierbij steeds een belangrijke rol: de gebruikers, de verkopers en de banken. Elk betalingssysteem bevat een aantal mechanismen die de veiligheid en correctheid van betaling voor deze partijen proberen te garanderen. Bij gebruikers groeit steeds meer het besef dat heel wat persoonlijke gegevens uitgewisseld worden tijdens transacties. Deze gegevens worden niet alleen bijgehouden en geanalyseerd, maar kunnen ook zonder toestemming gebruikt worden voor directe marketing technieken en andere legale of illegale doeleinden. Gebruikers ijveren daarom naar de mogelijkheid om betalingen anoniem uit te voeren. Momenteel is er slechts één courant gebruikt betalingsmechanisme dat totaal anonieme betalingen toelaat, namelijk fysiek geld. In onze huidige maatschappij nemen elektronische betalingen echter de bovenhand op betalen met fysiek geld. Het zou dus interessant zijn om elektronische betalingen ook anoniem uit te kunnen voeren. De veel gebruikte elektronische betalingssystemen zoals proton, krediet kaarten en debet kaarten geven de identiteit van de gebruiker weer tijdens betalingen. Zelfs prepaid kaarten garanderen geen volledige anonimiteit vermits meerdere transacties met dezelfde kaart teruggebracht kunnen worden tot éénzelfde entiteit. Het is nochtans niet onmogelijk om een elektronisch betalingssysteem te ontwikkelen waarbij de anonimiteit van gebruikers gevrijwaard wordt. In 1982 bedacht David Chaum namelijk een digitaal alternatief voor fysiek geld: E-Cash [1]. In een E-Cash systeem kunnen gebruikers bij de bank een portefeuille met elektronische munten afhalen en deze munten vervolgens uitgeven aan een verkoper. De verkoper kan de verkregen munten tenslotte storten op zijn rekening bij de bank. Een ideaal E-Cash systeem voldoet aan alle anonimiteitsvereisten van gebruikers: de verkoper leert niets 1

1. Inleiding over de identiteit van gebruikers tijdens transacties, geen twee betalingen kunnen teruggelinkt worden naar dezelfde entiteit en het is voor de bank niet mogelijk om munten uitgegeven bij een geldafhaling te linken aan munten verkregen tijdens een geldstorting. Deze anonimiteit blijft echter enkel bewaard zolang er geen sprake is van een dubbele uitgave van een munt. De introductie van E-Cash door Chaum zette een hele reeks onderzoekers aan het werk om systemen te ontwikkelen die naast de anonimiteit ook rekening houden met andere vereisten van gebruikers zoals het overdragen van geld naar andere gebruikers (transfereerbare E-Cash) en het omzetten van een munt met een bepaalde waarde naar meerdere munten met kleinere waarde (deelbare E-Cash). Omdat de anonimiteit ook misbruikt kan worden door criminelen voor witwaspraktijken, blackmailing en illegale aankopen, werden ook systemen ontwikkeld waarbij een derde partij (bijvoorbeeld de overheid) de anonimiteit van de gebruikers kan terugroepen indien vermoed wordt dat iemand zich frauduleus gedraagt. Theoretisch gezien zijn anonieme E-Cash systemen dus mogelijk, maar omzetting in de praktijk bleek voorlopig niet realiseerbaar. De bestaande theoretische E-Cash schema’s vereisen namelijk dat gebruikers een sabotage bestendig element ter beschikking hebben waarop alle berekeningen die ze moeten uitvoeren tijdens betalingen, geïmplementeerd zijn. Dit sabotage bestendig element (ook vertrouwd element genoemd) is in het schema dat wij zullen gebruiken aanwezig om extra beveiliging te geven aan de gebruiker tegen corruptie pogingen van andere - kwaadwillige - gebruikers. Corruptie kan als gevolg hebben dat er geld gestolen wordt van de eerlijke gebruiker of kan er toe leiden dat hij beschuldigd wordt van dubbele uitgave van een munt. In dit door ons gebruikte schema blijven de veiligheidseigenschappen van de verkoper en de bank (zoals de balanseigenschap en identificatie van dubbele uitgevers) behouden zelfs indien een gebruiker gecorrumpeerd is, dit in tegenstelling met andere - meer efficiënte - schema’s waarbij het totale systeem gecorrumpeerd wordt indien een gebruiker corrupt is (we nemen hierbij als conventie dat een gebruiker corrupt is van zodra hij niet meer beschermd is tegenover andere kwaadwillige personen). Typisch wordt er gebruik gemaakt van een smartcard als sabotage bestendig element. Voor de door ons behandelde E-Cash systemen is het echter onmogelijk om al de operaties die de gebruiker moet uitvoeren, te implementeren op een smartcard. De reden hiervoor is tweeledig. Ten eerste zijn de te implementeren berekeningen zo complex dat het een quasi onmogelijke taak is om ze binnen de geheugen beperkingen van smartcards te laten passen. Ten tweede is het aantal uit te voeren operaties zo groot, dat de responstijden op een in rekenkracht beperkt embedded device zoals een smartcard, onaanvaardbaar zouden zijn. Het vernieuwende aan deze thesis is dat er een anoniem compact E-Cash systeem voorgesteld wordt, dat gebaseerd is op het model van Camenisch et al. [2] en waarbij de sabotage bestendige hardware van de gebruiker zoveel mogelijk ontlast wordt van berekeningen. Dit doel wordt bereikt door alle berekeningen die de gebruiker moet uitvoeren, te splitsen in berekeningen die belangrijk zijn voor de anti-corruptie bescherming van de gebruiker en berekeningen die daar niet belangrijk voor zijn. 2

De berekeningen die van belang zijn, moeten uitgevoerd worden op een veilig sabotage bestendig element en de andere berekeningen kunnen uitgevoerd worden op een krachtiger toestel (de host). In het ideale geval worden de meeste operaties uitgevoerd op de host, waardoor er een grote tijdswinst bekomen zou moeten worden. Bij de splitsing van berekeningen volgden we dezelfde aanpak als deze gekozen bij het DAA protocol [3]. Het voorgestelde E-Cash systeem moet uiteraard voldoen aan de belangrijkste eigenschappen van een ideaal E-Cash systeem, namelijk anonimiteit van gebruikers, onlinkbaarheid van twee betalingen, detectie van een dubbele uitgever, correctheid van het systeem, evenwicht in de balans van de bank en protectie van gebruikers tegen corruptie door andere kwaadwillige gebruikers. Het systeemconcept is ook zodanig ontworpen dat zelfs indien de host gecorrumpeerd is, transacties onmogelijk zijn zonder het beveiligd element. In deze thesis wordt daarom een eerste aanzet gegeven tot een bewijs dat ons schema inderdaad aan deze eigenschappen voldoet. Dit bewijs wordt gevoerd in het ideale wereld/reële wereld paradigma. Om na te gaan in welke mate het voorgestelde E-Cash schema tot praktisch realiseerbare implementaties kan leiden, analyseren we in deze thesis tenslotte de implementatie van het gebruikers gedeelte van het E-Cash systeem. We besteden hierbij ook aandacht aan enerzijds de interface tussen de gebruiker en de andere partijen van het protocol (de verkoper en de bank) en anderzijds aan de interface tussen de twee hardware modules van de gebruiker. Doordat de gebruiker in het voorgestelde E-Cash systeem de obstructie is voor een realistische implementatie, vormt dit het voornaamste onderwerp voor dit werk en wordt de nodige aandacht geschonken aan het evalueren van de gerealiseerde responstijden. De structuur van de thesis wordt schematisch weergegeven in figuur 1.1. Zoals de figuur illustreert, kunnen drie delen onderscheiden worden in de thesis: Het eerste deel geeft een overzicht van de theoretische literatuur studie. Dit deel gaat het effectieve onderzoek vooraf omdat de concepten die er geïntroduceerd worden essentieel zijn om de werking en veiligheidseigenschappen van E-Cash systemen te begrijpen. In het tweede deel wordt de focus gelegd op het ontwerp van een anoniem ECash systeem voor computationeel beperkte platformen. Hoofdstuk 3 introduceert daarom eerst het concept van E-Cash systemen en beschrijft ook het E-Cash systeem waarop we ons in deze thesis gebaseerd hebben (het compacte E-Cash systeem door J. Camenisch et al. [2]). Hoofdstuk 4 baseert zich dan op het compacte E-Cash systeem en illustreert hoe de operaties van het gebruikersgedeelte opgedeeld kunnen worden tussen een onvertrouwd krachtiger toestel en een vertrouwd sabotage bestendig element. Er wordt ook een eerste aanzet gegeven tot het bewijs dat het systeem dat resulteert na deze opdeling, de minimale eigenschappen bezit die we vereisen van een E-Cash systeem.

3

1. Inleiding

Figuur 1.1: Structuur van de thesis In het derde deel gaan we tenslotte na in welke mate het voorgestelde E-Cash systeem tot praktisch realiseerbare implementaties kan leiden. De focus ligt hierbij, zoals gezegd, op het gebruikersgedeelte van het E-Cash systeem. Hoofdstuk 5 introduceert daarom eerst welke hardware modules we voor welke partijen gekozen hebben, hoe deze partijen met elkaar communiceren en welke software tools beschikbaar zijn voor de implementatie. Hoofdstuk 6 overloopt dan gedetailleerd de beslissingen die we maakten en problemen die we hadden bij de implementatie van de twee hardware modules van de gebruiker. Het hoofdstuk sluit af met een evaluatie van de verkregen performantie van het gebruikersgedeelte. Hoofdstuk 7 trekt tenslotte de besluiten van het werk, gebaseerd op de resultaten van deel twee en drie en brengt de belangrijkste problemen in kaart. Het geeft eveneens een aanzet tot verder werk.

4

Hoofdstuk 2

Basisbeginselen Theory is important, at least ... in theory. Keith Martin

In dit hoofdstuk wordt een overzicht gegeven van de cryptografische basisbeginselen die in het verder verloop van de thesis gebruikt zullen worden. Vermits er vanuit wordt gegaan dat de lezer vertrouwd is met de meeste van deze onderwerpen, wordt de uitleg steeds beknopt gehouden. In sectie 2.1 introduceren we de notatie die we in de hele thesis zullen gebruiken. Secties 2.2, 2.3 en 2.4 geven een overzicht van enkele concepten uit respectievelijk de complexiteitstheorie, de theorie van Turingmachines en de probabiliteitstheorie. De concepten die beschreven worden in deze secties zijn noodzakelijk voor een goed begrip van latere definities en eigenschappen. Sectie 2.5 beschrijft het model waarin we de veiligheid van het voorgestelde E-Cash systeem uit hoofdstuk 4 zullen aantonen. Sectie 2.6 introduceert vervolgens belangrijke concepten uit de groepentheorie en in sectie 2.7 en sectie 2.8 analyseren we dan de problemen en algoritmes uit de getallentheorie die gerelateerd zijn aan het werken met groepen. Deze secties zijn belangrijk voor een goed begrip van de werking en de veiligheid van de schema’s besproken in hoofdstuk 3 en 4. Alvorens over te gaan tot de bespreking van enkele belangrijke constructies die in de thesis gebruikt worden, bespreken we in sectie 2.9 en sectie 2.10 twee concepten die in vrijwel alle cryptografische algoritmes (en dus ook in de onze) voorkomen: hash functies en pseudorandom functies. In de laatste drie secties bespreken we dan constructies waarvan we in de schema’s uit hoofdstuk 3 en 4 gebruik zullen maken: sectie 2.11 bespreekt verbintenis schema’s, sectie 2.12 bespreekt schema’s waarin zero-knowledge proofs of knowledge uitgevoerd worden en tot slot bespreekt sectie 2.13 handtekening schema’s. Lezers waarvoor al deze concepten goed gekend zijn, kunnen zonder informatie te verliezen, dit hoofdstuk overslaan. 5

2. Basisbeginselen

2.1

Notatie

Doorheen de thesis wordt dezelfde notatie gebruikt als [4]. Hieronder vermelden we kort enkele vaak voorkomende notaties. • Met de notatie x ∈R [a, b] geven we aan dat x een random element is, gelegen in het interval [a, b]. • De aaneenschakeling van twee getallen x, y wordt genoteerd als xky. • De grootste gemene deler van a, b duiden we aan als ggd(a, b). Het kleinste gemene veelvoud van a, b duiden we aan met kgv(a, b). • Een bitstring van k bits met waarde 1 wordt aangeduid door 1k . De lengte van een bitstring a wordt genoteerd als |a|. De verzameling bitstrings van lengte k wordt genoteerd als {0, 1}k . • Partijen uit het protocol noteren we steeds met een kalligrafische letter, bv. M, N , .... Voor een tegenstander voorzien we twee speciale kalligrafische letters, nl. A en E. Een gewone partij zal dus nooit voorgesteld worden met de letters A, E. • Een partij P die black-box toegang heeft tot een andere partij Q noteren we formeel als P ↔Q • Protocol instanties duiden we aan met een gewone hoofdletter, bv. P. Als P een protocol is tussen M en N dan bedoelen we met P (M(x), N (y) dat M’s input x is en N ’s input y is. • Getallen worden voorgesteld in de Big Endian notatie: x = (xn−1 , · · · , x0 )b is een getal dat bestaat uit n karakters van basis b en waarbij x0 het minst beduidende karakter en xn−1 het meest beduidende karakter is. Twee basissen worden in de thesis veel vuldig gebruikt: b = 2 en b = 256. 1 • Een functie f (n) waarvoor geldt dat |f (n)| < p(n) voor elke polynoom p(n) en voor voldoende grote n noemen we verwaarloosbaar en noteren we met het symbool ν(n).

2.2

Probabiliteitstheorie

In deelsectie 4.2.5 en in een aantal verdere definities gebruiken we concepten uit de probabiliteitstheorie. Vandaar dat het nuttig is om deze concepten hier te introduceren. We beginnen met het geven van enkele definities [5]: Definitie 2.1. (Experiment) Een experiment is een procedure die verschillende mogelijke uitkomsten kan hebben. 6

2.2. Probabiliteitstheorie We gaan er bij de verdere bespreking impliciet vanuit dat het aantal uitkomsten van een experiment steeds eindig is. Definitie 2.2. (Staalruimte) Een staalruimte S = {s1 , ..., sn }, bevat alle mogelijke uitkomsten van een experiment. Een onontbindbaar resultaat van een experiment wordt een staal si genoemd. Definitie 2.3. (Gebeurtenis) Een gebeurtenis G = {g1 , g2 , ..., gm } is een deelverzameling van de staalruimte S en heeft al dan niet plaats. Definitie 2.4. (σ-algebra) Een σ-algebra is een verzameling ξ van deelverzamelingen van S die moet voldoen aan drie voorwaarden: • De staalruimte S ∈ ξ ¯ ∈ ξ waarbij G ¯ het complement is van G. • Als de gebeurtenis G ∈ ξ dan is ook G • Als een telbare reeks G1 , G2 , .., Gk ∈ ξ dan geldt ook dat G1 ∪ G2 ∪ ... ∪ Gk ∈ ξ. Definitie 2.5. (Borel σ-algebra) Een Borel σ-algebra is de kleinst mogelijke σalgebra over R bestaande uit alle open intervallen (a, b) met −∞ ≤ a < b ≤ ∞. Een verzameling B in een Borel σ-algebra noemen we een Borel verzameling. Definitie 2.6. (Waarschijnlijkheidsmaat) Gegeven een staalruimte S en een σalgebra ξ, dan is de waarschijnlijkheidsmaat P een reële functie gedefinieerd op de gebeurtenissen van ξ zodanig dat: 1. P (G) = 2. P (S) = 3. P (

Sx

zijn.

m P

gi ≥ 0,

∀G ∈ ξ

i=1 n P

si = 1

i=1

i=1 Gi )

≤

x P i=1

P (Gi ) waarbij het gelijkheidsteken geldt als G1 , ..., Gx disjunct

Definitie 2.7. (Waarschijnlijkheidsruimte) Een triplet (S, ξ, P ) wordt een waarschijnlijkheidsruimte genoemd. Definitie 2.8. (Random variabele) Een random variabele X is een afbeelding X : S → R zodanig dat X −1 ((−∞, x]) = {z ∈ S : X(z) ≤ x} een gebeurtenis is ∀x ∈ R. Stelling 2.1. Een random variabele X over een waarschijnlijkheidsruimte (S, ξ, P ) induceert een waarschijnlijkheidsmaat Px over de Borel σ-algebra in R door Px (B) = P (X ∈ B) = P (X −1 (B)) = P ({z ∈ S : X(z) ∈ B}). Het gevolg van deze stelling is dat als we ons enkel bezighouden met X en de waarschijnlijkheden P (X ∈ B) dat we dan abstractie kunnen maken van de staalruimte S en dat modelleren op de reële as voldoende is. 7

2. Basisbeginselen Definitie 2.9. (Ensemble van random variabelen) Een ensemble van random variabelen E is een verzameling van geïndexeerde random variabelen en wordt genoteerd als E = {Xn }n∈N . Gewapend met deze definities kunnen we nu een concept uit de probabiliteitstheorie beschrijven dat veelvuldig gebruikt wordt doorheen de thesis: ensembles die niet te onderscheiden zijn. We bespreken zowel perfecte, statistische als computationeel niet te onderscheiden ensembles op basis van [6]. Definitie 2.10. (Niet te onderscheiden ensembles) Beschouw twee ensembles van random variabelen E1 = {Xn } en E2 = {Yn } waarvoor geldt dat Xn en Yn een gemeenschappelijke staalruimte Sn hebben voor alle n. Dan geldt er dat E1 en E2 : Perfect niet te onderscheiden zijn als Xn en Yn dezelfde waarschijnlijkheidsmaat Pn hebben voor alle n. Statistisch niet te onderscheiden zijn als er voor elke polynoom p(.) en voor voldoende grote n geldt dat X

|P r[Xn (s)] − P r[Yn (s)]| ≤

s∈Sn

1 p(n)

Computationeel niet te onderscheiden zijn als er geen efficiënt algoritme bestaat dat met een niet te verwaarlozen kans de twee ensembles kan onderscheiden. Meer formeel wilt dit dus zeggen dat voor elk probabilistisch polynomiale tijd algoritme D, voor elke polynoom p(.) en voor voldoende grote n geldt dat |P r[D(Xn ) = 1] − P r[D(Yn ) = 1]| ≤

2.3

1 p(n)

Complexiteitstheorie

In deze sectie introduceren we zeer kort enkele belangrijke concepten uit de complexiteitstheorie. We geven eerst een classificatie van algoritmes op basis van hun rekentijd. Op basis van deze classificatie komen we vervolgens tot de definitie van een onhandelbaar probleem. Lezers die een diepgaande uiteenzetting over complexiteitstheorie willen worden verwezen naar [7], [4]. In de complexiteitstheorie, worden problemen vaak opgedeeld op basis van de eigenschappen van het meest efficiënte algoritme om hen op te lossen. De efficiëntie van het oplossingsalgoritme kan hierbij bijvoorbeeld bepaald worden op basis van het aantal primitieve stappen of het vereiste geheugen. Onze classificatie richt zich op het vereiste aantal primitieve stappen (vanaf nu de rekentijd genoemd) van een algoritme. Om de (worst-case) rekentijd van algoritmes te vergelijken, gaan we na hoe de rekentijd toeneemt bij een toename van de grootte (n) van het probleem. Vermits de exacte rekentijd van een algoritme moeilijk te bepalen is, gebruikt men bij de 8

2.4. Turingmachines classificatie een asymptotische bovengrens. We gebruiken hiervoor de standaard asymptotische notatie: De uitdrukking f (n) = O(g(n)) drukt uit dat f (n) door g(n) asymptotisch naar boven begrensd is en betekent dat er een positieve constante c en een natuurlijk getal n0 bestaat zodat 0 ≤ f (n) ≤ cg(n), ∀n ≥ n0 . De uitdrukking f (n) = o(g(n)) wordt gebruikt voor een bovengrens die niet asymptotisch nauw is: Voor elke positieve constante c bestaat er een getal n0 zodat 0 ≤ f (n) < cg(n), ∀n ≥ n0 . Op basis van de rekentijd in het slechtste geval, worden algoritmes opgedeeld in klasses. Voor ons belangrijke klasses zijn: polynomiale tijd algoritmes, exponentiële tijd algoritmes en subexponentiële tijd algoritmes. We definiëren deze klasses gelijkaardig aan [8]. Een algoritme voert uit in polynomiale tijd als de toename van de rekentijd in functie van de grootte van de input n, gegeven kan worden door een functie f (n) = O(nk ) voor een constante k. Een algoritme voert uit in exponentiële tijd als de toename van de rekentijd in functie van de grootte van de input asymptotisch begrensd kan worden door O(cn ) voor c > 1. Een subexponentiële tijd algoritme is een algoritme waarvoor de rekentijd naar boven begrensd is door O(exp(c+o(1)nα (ln n)1−α )) waarbij c een positieve constante en 0 < α < 1. Aan de hand van deze classificatie wordt vervolgens een onhandelbaar probleem gedefinieerd. Definitie 2.11. (Onhandelbaar probleem) Een probleem is onhandelbaar als er geen oplossingsalgoritme bestaat dat in polynomiale tijd uitvoert.

2.4

Turingmachines

Turingmachines (TM) werden door Alan Turing voorgesteld als een zuiver theoretisch computationeel apparaat. In het verder verloop van de thesis gaan we ervan uit dat elk van de partijen Turingmachines gebruiken voor het uitvoeren van een protocol. Vandaar dat het nuttig is om te herhalen wat Turingmachines juist zijn. We bespreken eerst een basismodel en beschrijven daarna enkele uitbreidingen op dit basismodel die later in de thesis nuttig zullen zijn.

2.4.1

De Deterministische Eénbandige Turingmachine als Basismodel

De meest elementaire Turingmachine is een éénbandige deterministische Turingmachine. Figuur 2.1 geeft weer uit welke onderdelen deze machine bestaat: 9

2. Basisbeginselen

Figuur 2.1: Basismodel van een Turingmachine.

1. Een lees/schrijfkop. 2. Een oneindig lange band die beschreven en gelezen kan worden. Deze band is onderverdeeld in cellen waarvan er op elk ogenblik slechts een eindig aantal beschreven zijn. De band kan zowel naar links als naar rechts verschoven worden om de lees/schrijfkop boven een andere cel te plaatsen. 3. Een eindige toestandsautomaat die bijhoudt in welke toestand de machine zich momenteel bevindt. 4. Een tabel met toestandsovergangen en bijhorende acties. De tabel wordt geïndexeerd door een tupel (huidige toestand, waarde) en met elke index komt er een tupel (volgende toestand, waarde die geschreven moet worden, richting waarin band moet verschoven worden) overeen. Het typische verloop van de Turingmachine is als volgt: In de huidige toestand H wordt de waarde X (die een element is van het bandalfabet) van de band gelezen. Het tupel (H,X) wordt als index gebruikt in de tabel met toestandsovergangen om zo een tupel (V, X’,R) op te vragen. Aan de hand van dit tupel worden vervolgens volgende stappen uitgevoerd: • Schrijf X’ weg op de huidige positie van de schrijfkop. • Verschuif de band over één positie in de richting R (links, rechts, geen verschuiving). • Ga naar de volgende toestand V. 10

2.4. Turingmachines Bovenstaande handeling wordt herhaald tot de machine in een halt toestand terecht komt. De halt toestand kan zowel een accepterende toestand zijn (dan is de berekening klaar en correct) of kan een afwijzende toestand zijn (dan kan er niet verder gerekend worden en is het resultaat verkeerd). Eens we in een halt toestand terecht komen, stopt de uitvoering. Formeel kan een éénbandige Turingmachine dus beschreven worden als een 7-tupel TM = hQ, Σ, Γ, δ, q0 , qac , qaf i waarvoor geldt dat: • Q een eindige verzameling toestanden is waarin de machine zich kan bevinden. • Σ het invoeralfabet is dat als invoer voor berekeningen gebruikt kan worden. • Γ het bandalfabet is. Γ = Σ ∪ {?} en bestaat dus uit het invoeralfabet plus het blanco karakter ?. • δ is de overgangsfunctie die de toestandsovergangen, de schrijfacties en de kopbewegingen van de eindige toestandsautomaat beschrijft. De mogelijke bewegingen van de schrijfkop zijn: naar links over één cel (L), naar rechts over één cel (R) of geen beweging (G). De overgangsfunctie wordt dan genoteerd als δ : Q × Γ 7→ Q × Γ × {L, R, G}. • q0 de begintoestand is. • qac de accepterende halt toestand is. • qaf de afwijzende halt toestand is.

2.4.2

Uitbreidingen op het Basismodel

We breiden het basismodel van de Turingmachine nu uit door meer specifieke soorten machines te definiëren: Een polynomiale tijd Turingmachine. Dit is een Turingmachine die enkel een polynomiaal aantal stappen gebruikt bij de uitvoering. Niet-deterministische Turingmachine. We hebben gezien dat voor een deterministische Turingmachine er een overgangsfunctie δ bestaat die voor elke combinatie van huidige toestand en huidig gelezen symbool uniek bepaalt wat de volgende actie is. Een niet deterministische Turingmachine laat daarentegen toe dat er voor elke combinatie van huidige toestand en huidig gelezen symbool, een verzameling van toegelaten volgende acties is. Formeel kan de niet deterministische Turingmachine genoteerd worden als een 7 tupel T M = hQ, Σ, Γ, δ, q0 , qac , qaf i waarbij δ nu een overgangsrelatie (geen functie meer) is. Er geldt dat δ ⊆ (Q\{qaf , qac } × Σ) × (Q × Σ × {L, R, G}) 11

2. Basisbeginselen Probabilistische Turingmachine (PTM). Dit is een niet deterministische Turingmachine waarbij er randomweg gekozen wordt tussen de toegelaten overgangen op basis van een waarschijnlijkheidsdistributie. Interactieve Turingmachine (ITM). Een interactieve Turingmachine is een machine die meerdere banden heeft: een read/write werk band, een read-only input band een write-only output band, read-only communicatie band en write-only communicatie band. De write-only communicatie band bevat de boodschappen verzonden naar de andere machines. De read-only communicatie band bevat de boodschappen verkregen van andere machines. Twee interactieve Turingmachines kunnen dus een interactief protocol uitvoeren, waarbij gedurende elke ronde één van hen actief is. Heeft een ITM ook read-only random band, dan wordt het een probabilistische ITM genoemd. De random band bevat een oneindige sequentie van willekeurig geplaatste bits. Tot slot definiëren we nog een belangrijk concept dat in het verder verloop van de thesis gebruikt zal worden: Definitie 2.12. (Orakel toegang tot een partij) Als M en N twee Turingmachines zijn dan zeggen we dat M orakel toegang heeft tot N als voldaan is aan volgende drie vereisten: • N heeft een band b die enkel te gebruiken is als M dit toestaat. • M kan N bevelen om zijn toestand op de band b op te slaan en dit op elk moment van de berekening. • M kan N bevelen om terug te gaan naar een voordien opgeslagen toestand op de band. Als M orakel toegang heeft tot N dan noteren we M ⇔N

2.5

Universal Composability Raamwerk

Bij het ontwikkelen van een cryptografisch protocol is het een belangrijke taak om de veiligheidseigenschappen te definiëren en te bewijzen dat het protocol voldoet aan deze eigenschappen. Bij deze veiligheidsanalyse is het belangrijk op te merken dat er tegelijkertijd meerdere (eventueel gerelateerde) protocol instanties kunnen uitvoeren en dat het mogelijk is om een protocol te gebruiken als een bouwblok van een ander protocol. Om met deze opmerkingen rekening te houden, zijn er reeds een aantal raamwerken voorgesteld. Het Universal Composability (UC) raamwerk van Canettie [9] komt in de literatuur het meeste voor en zullen we ook in deze thesis gebruiken. Het interessante aan dit raamwerk is dat een protocol in isolatie van andere protocol uitvoeringen geanalyseerd kan worden, maar dat het toch zijn veiligheidseigenschappen behoudt als het uit isolatie wordt uitgevoerd. We beschrijven hieronder beknopt het UC framework op basis van [10], [11] en [12]. Voor een uitgebreide introductie 12

2.5. Universal Composability Raamwerk verwijzen we naar [9]. Intuïtie van het raamwerk. Om te bewijzen dat een gegeven protocol voldoet aan bepaalde veiligheidseigenschappen, maakt het raamwerk gebruik van een ideaal proces. Het ideale proces voert dezelfde taak uit als het gegeven protocol, maar dan op een veilige manier. In dat ideale proces geven de partijen hun invoer aan een vertrouwde derde partij die de ideale functionaliteit wordt genoemd. De ideale functionaliteit berekent de correcte uitvoer en geeft deze terug aan de partijen. De ideale functionaliteit kan dus gezien worden als de formele specificatie van de gewenste taak. We zeggen dat een protocol een bepaalde taak op een veilige manier realiseert als de uitvoering van dat protocol het ideale proces van die taak emuleert. Modellering van de partijen. Elk van de partijen wordt gemodelleerd als een Interactieve Turing Machine (ITM). Een ITM kan (meerdere keren) geïnstantieerd worden tot een ITM Instantie (ITI) die een eigen Sessie IDentificatiecode (SID) en een eigen Partij IDentificatiecode (PID) heeft. De SID laat toe om verschillende protocol instanties van elkaar te onderscheiden terwijl de PID het mogelijk maakt om binnen een protocol instantie de verschillende partijen te onderscheiden. ITI’s die verbonden zijn in een netwerk vormen een systeem van Interactieve Turing Machine Instanties (I,C). De uitvoering van het systeem (I,C) komt overeen met een serie van activaties waarbij op elk moment slechts één ITI actief is. In het begin wordt een initiële ITI (I) actief. Deze initiële ITI kan lokale berekeningen uitvoeren en vervolgens één andere ITI actief maken door informatie op zijn invoer band te schrijven. Op het moment dat een nieuwe ITI actief wordt, komt de oude ITI terecht in een wachtstand. Er bestaat een controle functie (C) die bepaalt welke banden van welke ITI beschreven kunnen worden door welke ITI. Het formalisme. Definiëren wat het betekent voor een protocol π om een bepaalde taak veilig te realiseren, gebeurt in drie stappen: • Eerst formuleren we een model voor het uitvoeren van het protocol in de reële wereld. Dit model bestaat uit de partijen die het protocol π uitvoeren en twee andere entiteiten: de omgeving Z en de tegenstander A. De omgeving Z vertegenwoordigt alle protocollen die uitvoeren in het systeem en alle tegenstanders die ermee interageren. De tegenstander en de omgeving kunnen vrij interageren tijdens de uitvoer van het protocol. In het begin van de protocoluitvoering, wordt Z aangeduid als initiële ITI. Er geldt dat de tegenstander A de eerste partij moet zijn die door Z actief gemaakt wordt. Nadien kan Z communiceren met A of kan het de partijen die het protocol uitvoeren van input voorzien. A kan boodschappen in de communicatie banden van een andere partij schrijven, of kan een partij corrupt maken waardoor het vanaf dan de volledige status van die partij kan zien. Als A een partij corrupt maakt, wordt Z hiervan geïnformeerd. De partijen van het protocol π kunnen boodschappen in de communicatie band van A (en enkel in die) schrijven of andere ITI’s invokeren als subroutines. Het is dus duidelijk dat Z enkel toegang heeft tot de input en 13

2. Basisbeginselen output van partijen, maar niet tot de communicatie tussen hen noch tot de inputs en outputs van hun subroutines. A heeft daarentegen enkel toegang tot de communicatie tussen partijen. • In een tweede stap formuleren we het ideale proces dat de gewenste taak uitvoert, maar dan op een ideaal veilige manier. Het ideale proces maakt hiervoor gebruik van een vertrouwde derde partij (de ideale functionaliteit F) en dummy partijen die overeenkomen met de partijen van het protocol π. De dummy partijen zijn zeer simpele ITMs die wanneer ze geactiveerd worden, al hun inputs kopiëren naar de inkomende communicatie band van F en die de output van F kopiëren naar de subroutine output band van hun oproeper. F bevat de instructies om de gewenste outputs te berekenen op basis van gegeven inputs. Daar waar we in het reële wereld model een tegenstander A hadden hebben we in het ideale proces een ideale tegenstander die de simulator E genoemd wordt. E kan een partij corrupt maken door hiervoor een aanvraag naar F te sturen. Nadat een partij corrupt gemaakt werd, wordt Z hiervan geïnformeerd. E kan bovendien boodschappen tussen partijen observeren en vertragen, maar is niet in de mogelijkheid om kennis over inputs/outputs te verkrijgen.

• Tenslotte zeggen we dat protocol π veilig is als π de ideale functionaliteit F veilig realiseert en bijgevolg dus ook het ideale proces emuleert. Emulatie betekent dat voor elke tegenstander A er een simulator E bestaat zodanig dat geen enkele omgeving Z, voor welke input dan ook, een onderscheid kan maken of het interageert met A en partijen die π uitvoeren in de reële wereld of met E en F in de ideale wereld. Dit wordt grafisch geïllustreerd in figuur 2.2. Om dit te bewijzen moeten we dus een simulator E bouwen en aantonen dat de simulatie succesvol is. Tijdens de simulatie speelt E de rol van een corrupte partij P 1∗ en voert het het ideale proces uit samen met een eerlijke partij P 2. Om correcte input aan F te geven, moet E een uitvoering van het protocol π simuleren. Om dat te doen, heeft E toegang tot een kopie van de tegenstander A. Alle boodschappen van Z die geadresseerd zijn voor E worden direct doorgestuurd naar A en alle outputs van A worden teruggegeven aan Z. Tijdens de simulatie van het protocol π speelt E de rol van P2 en A de rol van P 1∗ .

2.6

Abstracte Algebra

In deze sectie introduceren we enkele belangrijke concepten uit de abstracte algebra. We zullen ons focussen op groepen vermits we deze structuren veelvuldig zullen gebruiken in het verloop van de thesis. De bespreking gebeurt gelijkaardig als in [13] Voor we kunnen definiëren wat een groep is, moeten we eerst een aantal basisdefinities vermelden. 14

2.6. Abstracte Algebra

Figuur 2.2: Illustratie van het feit dat de omgeving moet beslissen of ze interageert met de reële wereld of met de ideale wereld. P1 en P2 stellen de partijen voor die in de reële wereld het protocol π uitvoeren en in de ideale wereld dummy partijen zijn. Pijlen duiden op input/output communicatie, lijnen zonder pijlen duiden op interactieve communicatie.

Definitie 2.13. (Een bewerking onder de elementen van een verzameling) Een bewerking ∗ onder de elementen van een verzameling A is een afbeelding van B ⊆ A × A → A. Er geldt dat: • de bewerking ∗ overal bepaald is als en alleen als B = A × A. • de bewerking ∗ associatief is als en alleen als x ∗ (y ∗ z) = (x ∗ y) ∗ z, ∀x, y, z ∈ A. • de bewerking ∗ commutatief is als en alleen als x ∗ y = y ∗ x, ∀x, y ∈ A. • E ⊆ A gesloten is voor ∗ als en alleen als x ∗ y ∈ E, ∀x, y ∈ E. Een verzameling die voorzien is van een bewerking ∗ noteren we als hA, ∗i Definitie 2.14. (Een groep) hG, ∗i is een groep als en alleen als 1. de bewerking ∗ overal bepaald is. 2. de bewerking ∗ associatief is. 3. ∃e ∈ G : ∀x ∈ G : x ∗ e = e ∗ x = x

(neutraal element). 15

2. Basisbeginselen 4. ∀x : ∃x−1 ∈ G : x ∗ x−1 = x−1 ∗ x = e

(inverse).

Definitie 2.15. (Een Abelse groep) hG, ∗i is een Abelse groep als en alleen als het een groep is en er bovendien geldt dat ∗ commutatief is. Voor de eenvoud van notatie noteren we de groep hG, ∗i in wat volgt simpelweg als G. Definitie 2.16. (Orde van een groep) De orde van groep is het aantal elementen waaruit de groep bestaat en wordt genoteerd als |G|. Definitie 2.17. (Orde van een element van een groep) De orde van een element a ∈ G is het kleinste natuurlijk getal r 6= 0 waarvoor ar = e (met e het neutraal element). Als zo een r niet bestaat dan is de orde van a oneindig. Definitie 2.18. (Een cyclische groep) Een groep G is cyclisch als er een element g ∈ G bestaat zodanig dat men de groep G kan beschrijven als G = {g r |r ∈ Z}. Het element g wordt de generator van G genoemd en heeft als orde r = |G|. Stelling 2.2. Als G een cyclische groep is van orde t waarvoor g ∈ G een generator is, dan wordt de orde van een element b = g i gegeven door t/ggd(t, i). Definitie 2.19. (Deelgroep) Een deelverzameling H 6= ∅ is een deelgroep van G als H zelf een groep vormt onder dezelfde bewerking als G. Stelling 2.3. Als G cyclisch is dan is een deelgroep H van G ook cyclisch. Stelling 2.4. (Stelling van Lagrange) Als H een deelgroep is van een eindige groep G, dan is de orde van H een deler van de orde van G. De orde van een eindige groep is dus steeds een veelvoud van de orde van zijn deelgroepen. Definitie 2.20. (Multiplicatieve groep) Gegeven een verzameling Zn , dan is Z∗n = {a ∈ Zn |ggd(a, n) = 1} de multiplicatieve groep modulo n. Definitie 2.21. (Euler’s phi functie) Gegeven een natuurlijk getal n ≥ 1, dan geeft Euler’s phi functie φ(n) het aantal natuurlijke getallen in het interval [1, n] die relatief priem zijn met n. De algemene formule voor n = pe11 ...pemm , wordt gegeven door m Y 1 φ(n) = n. (1 − ) pi i=1

We zijn nu klaar voor de bespreking van de constructies die in deze thesis gebruikt worden. In het protocol maken we gebruik van de groep van kwadratische residus modulo een samengesteld getal en van groepen waarvan de orde een priemgetal is. a) Groepen waarvan de orde een priemgetal is Een efficiënte methode voor het genereren van groepen van priem orde bestaat erin 16

2.6. Abstracte Algebra gebruik te maken van veilige priemgetallen. We definiëren eerst wat veilige priemgetallen zijn en leiden daaruit af hoe ze gebruikt kunnen worden voor de constructie van priem orde groepen en wat de eigenschappen van deze groepen zijn. Definitie 2.22. (Veilig priemgetal) Een priemgetal p0 waarvoor p = 2p0 + 1 ook priem is, noemen we een Sophie-Germain priemgetal. Het priemgetal p noemen we een veilig priemgetal . Definitie 2.23. ( Groep modulo een veilig priemgetal) Stel p = 2p0 + 1 is een veilig priemgetal, dan vormt de verzameling {a|1 ≤ a ≤ (p − 1)} een multiplicatieve groep Z∗p modulo een veilig priemgetal. Uit voorgaande definities en stellingen volgen onmiddellijk volgende eigenschappen voor groepen modulo een veilig priemgetal p. Stelling 2.5. De orde van Z∗p wordt gegeven door φ(p) = p − 1 Stelling 2.6. In Z∗p zijn er φ(φ(p)) = p0 − 1 generatoren. Stelling 2.7. Z∗p heeft twee deelgroepen: één van orde 2 en één van orde p0 . De deelgroep van orde p0 van Z∗p is vormt nu een groep van priem orde Een groep van priem orde kan dus makkelijk gevormd worden door eerst een veilig priemgetal p te genereren en vervolgens de grootste deelgroep van Z∗p te beschouwen. Als we een generator g van de groep van priem orde p0 willen bepalen gaan we als volgt te werk: Eerst kiezen we een generator g 0 van Z∗p waarvoor geldt dat g 0 6= ±1 en g 0q 6= 1 mod p. Vervolgens bepalen we dan de generator g door g = g 02 mod p te berekenen.

b) Groepen van kwadratische residus modulo een samengesteld getal Dit vormt een twee belangrijke groep in het verder verloop van de thesis. We zullen hier enkel het geval beschouwen waarbij het samengesteld getal een speciale RSA modulus is. Dit geval leidt immers tot de meest interessante eigenschappen. We definiëren daarom eerst wat een speciale RSA modulus is en vermelden dan de definitie en eigenschappen van de groep van kwadratische residus modulo een speciale RSA modulus. Definitie 2.24. (Speciale RSA modulus) Een speciale RSA modulus n is een positief getal dat het product van twee veilige priemgetallen a, b is. Definitie 2.25. (Groep van kwadratische residu’s QRn ) Stel Z∗n is een multiplicatieve groep modulo een positief getal n. Een element x ∈ Z∗n wordt een kwadratisch residu genoemd als er een a ∈ Z∗n bestaat zodat a2 = x mod n. De verzameling van alle kwadratische residu’s van Z∗n vormt een cyclische deelgroep van Z∗n die we noteren als QRn . 17

2. Basisbeginselen Als we ervan uitgaan dat n een speciale RSA modulus is dan bekomen we volgende eigenschappen: Stelling 2.8. Beschouw een speciale RSA modulus n = pq = (2p0 + 1)(2q 0 + 1) dan geldt dat |QRn | = p0 q 0 ≤ 14 |Z∗n | Stelling 2.9. Het aantal generatoren in QRn wordt gegeven door φ(φ(n)) = (p0 − 1)(q 0 − 1). Een generator f in QRn kan eenvoudig bepaald worden door eerst een getal a ∈ Z∗q te genereren dat voldoet aan ggd(a ± 1, n) = 1 en vervolgens g = a2 mod n te bepalen. Uit de vorige stelling volgt echter dat elk random element uit QRn een zeer hoge kans heeft om een generator te zijn.

2.7

Problemen in de Getallentheorie

In deze sectie introduceren we enkele onhandelbare problemen uit de getallentheorie die aan de basis liggen van de veiligheid van ons protocol. Eerst definiëren we de Discrete Logaritme Veronderstelling (DL) dat onder meer gebruikt wordt in het verbintenis schema in sectie 2.11. Daarna definiëren we het Decisional Diffie-Helman Inversion(y-DDHI) probleem dat onder meer gebruikt wordt bij het definiëren van pseudorandom functies in sectie 2.9. Tot slot definiëren we het RSA probleem dat gebruikt wordt om de veiligheid te bewijzen van constructies die gebruik maken van de groep van kwadratische residus modulo een speciale RSA modulus. Definitie 2.26. (De Discrete Logaritme veronderstelling) Beschouw een cyclische groep G van orde q en met generator g. Het discreet logaritme probleem stelt dan dat, gegeven het tupel (g, g x ) met x ∈R Zq het moeilijk is om de waarde x te vinden. Definitie 2.27. (De y-DDHI veronderstelling) Beschouw de groep G met priey morde q en waarvoor g een generator is. Gegeven de waarden (g, g x , ..., g (x ) ) voor een random x ∈ Zq en een waarde h ∈ G, dan is het moeilijk om te bepalen of h = g 1/x . Definitie 2.28. (RSA veronderstelling) De RSA veronderstelling stelt dat, gegeven een positief getal e > 1, een RSA modulus n en een random element u ∈ Z∗n , het moeilijk is om het getal v ∈ Z∗n te bereken zodat: v e ≡ u mod n Definitie 2.29. (Sterke RSA Veronderstelling) De sterke RSA veronderstelling stelt dat, gegeven een RSA modulus n en een random element u ∈ Z∗n , het moeilijk is om de waarden e > 1 en v ∈ Z∗n te vinden zodat v e ≡ u mod n 18

2.8. Algoritmes in de Getallentheorie

2.8

Algoritmes in de Getallentheorie

In deze sectie bespreken we enkele belangrijke algoritmes die we nodig hebben in de schema’s van hoofdstuk 3 en hoofdstuk 4.

2.8.1

Lagrange Voorstelling van een Positief Getal

Er kan aangetoond worden dat een positief getal µ voorgesteld kan worden als µ = w12 + w22 + w32 + w42 . Een efficiënt algoritme hiervoor wordt gegeven in [14] en wordt hier overgenomen in algoritme 1 in bijlage B.

2.8.2

De Rabin-Miller Test

De Rabin-Miller test is de in de praktijk meest gebruikte test om na te gaan of een getal priem is. De test is probabilistisch in die zin dat de kans dat n priem is, afhangt van de meegegeven veiligheidsparameter t. Pseudo-code voor het algoritme wordt gegeven in [4] en wordt overgenomen in algoritme 2 in bijlage B.

2.8.3

Generatie van Waarschijnlijk Veilige Priemgetallen

Een naïeve methode voor het genereren van veilige priemgetallen bestaat erin om herhaaldelijk random priemgetallen b van de gewenste grootte te genereren totdat a = 2b + 1 ook priem is. Op basis van [15], [16] kan deze methode echter aanzienlijk versneld worden. Het resulterende algoritme dat we in deze thesis gebruiken is algoritme 3 uit bijlage B.

2.9

Pseudorandom Functies

Pseudorandom functies vormen een basisblok in de constructies van hoofdstuk 3 en 4 vermits ze toelaten om de seriële nummers van de munten te genereren. We definiëren in deze sectie eerst een ideale random functie om vervolgens tot de definitie van een pseudorandom functie te komen. Definitie 2.30. (Random Functie). Een random functie is een functie F (.) die volledig random gekozen wordt uit de verzameling V van alle mogelijke functies G : {0, 1}l → {0, 1}L

Het gedrag van een dergelijke random functie F (.) kan gesimuleerd worden door gebruik te maken van een random orakel. Telkens het orakel opgevraagd wordt met een nieuwe boodschap m ∈ {0, 1}l , kiest het een random getal y ← {0, 1}L en antwoordt het met y. Als het orakel een tweede keer met dezelfde boodschap opgevraagd wordt, kopieert het de toen geantwoorde y. Pseudorandom functies proberen het gedrag van random functies te benaderen. 19

2. Basisbeginselen Informeel gezegd is een pseudorandom functie, een in polynomiale tijd berekenbare functie waarvoor het in/uitgangsgedrag computationeel niet te onderscheiden is van dat van een echte random functie. Dit wordt meer formeel genoteerd in onderstaande definitie [8]. Definitie 2.31. (Pseudorandom functie familie). Een familie van functies F = (fs |s ∈ {0, 1}k )k∈N wordt een familie van (l, L) pseudorandom functies genoemd als • ∀k ∈ N, ∀s ∈ {0, 1}k |fs : {0, 1}l → {0, 1}L • ∀k ∈ N, ∀s ∈ {0, 1}k |fs PPT is • F pseudorandom is. Formeel wordt dat genoteerd als volgt: Voor alle tegenstanders A, |Pr[A↔fs = 1|s ∈R {0, 1}k ] − Pr[A↔F = 1|F ∈R V]| ≤ ν(k) Met de pseudorandom functie familie zijn twee efficiënte polynomiale algoritmes SleutelGen en Eval geassocieerd: SleutelGen(1k ) geeft een geheime seed sk als resultaat die fungeert als index voor de functie familie; Eval(sk, x) evalueert de functie fsk in het punt x en geeft y als resultaat. Opdat de pseudorandom functie veilig zou zijn, mag de tegenstander A slechts met een regeerbare kans het ingangs-uitgangs gedrag van de pseudorandom functie kunnen onderscheiden van die van een ideale random functie. In deze thesis zullen we gebruik maken van de Dodis en Yampolskiy PRF[17] die we DY (x). noteren als F(SK) Constructie 2.1. (Dodis en Yampolskiy pseudorandom functie). Gegeven de groep G waarvoor de q-DDHI veronderstelling geldt, een generator g van G met orde q, de DY (x) = g 1/(s+x) seed s ∈R Zq en de variabele x dan wordt de DY PRF gegeven door F(s) . Deze pseudorandom functie laat efficiënte zero-knowledge proofs toe voor stellingen DY (x) gegeven een verbintenis met de geheime sleutel SK en is van de vorm y = F(SK) veilig onder de q-DDHI veronderstelling.

2.10

Hash Functies

Hash functies zijn functies die gebruikt worden om boodschappen van willekeurige lengte om te zetten tot een vast aantal bits. Het basis idee hierbij is dat het resultaat van de hash functie kan gebruikt worden als identificatiecode van de boodschap. Er bestaan zowel hash functies die gebruik maken van een geheime sleutel als hash functies die geen geheime sleutel gebruiken [18]. In het eerste geval is de hash functie een Message Authentication Code of MAC algoritme, in het tweede geval is het een 20

2.11. Verbintenis Schema’s (Commitment Schemes) Manipulation Detection Code of MDC algoritme. In deze thesis zullen wij enkel gebruik maken van MDC’s. De MDC’s die we in onze algoritmes zullen gebruiken moeten bovendien aan een aantal extra eigenschappen voldoen. Volgens de classificatie die Preneel [18] maakt, vallen de door ons gebruikte MDC’s onder de categorie: collision resistant hash functies (CRHF). Definitie 2.32. Een collision resistant hash functie is een functie h die voldoet aan volgende eigenschappen: 1. De boodschap X kan van willekeurige lengte zijn en het resultaat van de hash functie h(X) heeft een vaste lengte van n bits. 2. Het is computationeel gemakkelijk om h(X) te berekenen op basis van de hash functie h en de boodschap X. 3. De functie h moet pre-image-resistant zijn. Dit wil zeggen dat gegeven het hash resultaat Y, het moeilijk is om de boodschap X te vinden zodat h(X) = Y. 4. De functie h moet second pretimage-resistant zijn. Dit wil zeggen dat gegeven X en h(X), het moeilijk is om een boodschap X 0 6= X zodat h(X 0 ) = h(X). 5. De functie moet collision-resistant zijn. Dit wil zeggen dat het moeilijk is om twee boodschappen X en X 0 met X 6= X 0 te vinden waarvoor geldt dat h(X) = h(X 0 ). Bekende MDC’s zijn SHA-1 (160 bit resultaat), RIPEMD-160 (160 bit resultaat), SHA-256, SHA-512.

2.11

Verbintenis Schema’s (Commitment Schemes)

Verbintenis schema’s laten toe dat een partij een verbintenis aangaat met een bepaalde waarde die geheim gehouden wordt tegenover andere partijen tot beslist wordt om de waarde te onthullen. Het verloop van verbintenis schema’s kan informeel als volgt beschreven worden: Beschouw twee partijen A en B. Partij A kiest een geheime waarde of maakt een bepaalde keuze en schrijft het resultaat neer op een papier. Zij steekt dit papier in een doos en doet de doos op slot met sleutel die enkel zij bezit. Vervolgens overhandigt A deze doos aan B. B kan de doos niet openmaken vermits zij de sleutel niet heeft maar kan er wel over waken dat A de waarden in de doos niet wijzigt. Enkel als A haar private sleutel naar B stuurt, kan B de waarde in de doos controleren. Hierbij is het belangrijk dat A de doos slechts met één sleutel op één enkele manier kan openen waardoor de gesloten doos slechts één enkele waarde kan bevatten. Een algemeen verbintenis schema kan formeel genoteerd worden als volgt: 21

2. Basisbeginselen Definitie 2.33. (Algemeen Verbintenis Schema). Een verbintenis schema bestaat uit drie polynomiale tijd algoritmes: (a) SetupVerbintenis(1k ). Bij invoer van een geheime parameter k, wordt de publieke verbintenis sleutel CK gegenereerd. (b) VerbindCK (m, d). Bij invoer van een boodschap m en een private verbintenis sleutel d, wordt de verbintenis C gegenereerd. (c) OpenVerbintenisCK (C, m0 , d0 ). Bij invoer van een boodschap m0 , een private verbintenis sleutel d0 en een verbintenis C, wordt correct teruggegeven als op basis van m0 en d0 blijkt dat C correct gevormd werd. In het andere geval wordt fout teruggegeven. Het is belangrijk dat tussen de verbind en onthul fase, de zender de verbintenis niet kan wijzigen en de ontvanger niets leert over de geheime waarde. Een goed verbintenis schema voldoet dan ook aan twee eigenschappen die hieronder informeel worden beschreven: de bindingseigenschap (binding property) en de semantische veiligheid eigenschap. We gebruiken dezelfde definities als [6]. Eigenschap 2.1. (Bindingseigenschap) De tegenstander A kan een verbintenis niet openen op twee verschillende manieren. Dit wil zeggen dat voor alle tegenstanders A er een verwaarloosbare functie v bestaat zodat: P r[CK ← SetupVerbintenis(1k ); (C, m0 , d0 , m1 , d1 ) ← A(CK); a = OpenVerbintenisCK (C, m0 , d0 ); b = OpenVerbintenisCK (C, m1 , d1 ) : a = correct ∧ b = correct] ≤ ν(k) Eigenschap 2.2. (Semantische veiligheid eigenschap) De controleur kan geen onderscheid maken tussen twee verbintenissen op twee verschillende waarden zelf als hij die waarden weet. Formeel wilt dit dus zeggen dat voor alle A er een verwaarloosbare functie ν bestaat zodat: P r[CK ← SetupVerbintenis(1k ); (m0 , m1 ) ← A(CK); b ← {0, 1}; d ← D; C = VerbindCK (mb , d); b0 ← A(C) : b0 = b] ≤ 1/2 + ν(k) Voor de constructie van het protocol in hoofdstuk 4 zullen we gebruik maken van het Damgård en Fujisaki verbintenis schema. Dit is een verbintenis schema voor groepen van verborgen orde dat toelaat om een verbintenis aan te gaan met getallen van arbitraire grootte. In [19] hebben Damgård en Fujisaki voorwaarden vermeld waaraan een groep moet voldoen opdat deze kan worden gebruikt in het schema. Als voorbeeld gaven ze aan dat de Abelse groep van kwadratische residus modulo een speciale RSA modulus n, QRn , aan al de voorwaarden voldoet. Hieronder geven we een beschrijving van het Damgård en Fujisaki verbintenis schema. 22

2.12. Zero Knowledge Proofs of Knowledge Constructie 2.2. (Damgård en Fujisaki verbintenis schema). Dit verbintenis schema bestaat uit drie polynomiale tijd algoritmes: (a) SetupVerbintenis(1k ). Dit algoritme wordt uitgevoerd door een vertrouwde derde partij en geeft als resultaat de publieke sleutel CK = (n, g, h) waarbij n een speciale RSA modulus is, h een generator is van QRn en g ∈ hhi. (b) VerbindCK (m, d). Bij invoer van een geheel getal m en d ∈R [1..b n4 c], wordt de verbintenis c = g m hd mod n berekent en als resultaat gegeven. (c) OpenVerbintenisCK (C, m0 , d0 ). Bij invoer van de verbintenis c en de waarden 0 0 m0 , d0 geeft dit algoritme als resultaat ‘correct’ indien c = g m hd mod n. Onder de sterke RSA veronderstelling voldoet dit schema aan de drie eigenschappen. Het schema kan eenvoudig uitgebreid worden voor gevallen waarbij we de waarden (m0 , m1 , ..., mL ) willen verbinden.

2.12

Zero Knowledge Proofs of Knowledge

ZKPK worden gebruikt als fundamentele tool om de privacy en de veiligheid in protocollen te garanderen. Een zero-knowledge proof of knowledge is een protocol dat gevoerd wordt tussen twee partijen, een controleur V en een bewijzende partij P. De bewijzende partij toont aan de controleur dat hij kennis heeft van een bepaald geheim, zonder dat die controleur iets leert over het geheim. Het zijn geen bewijzen in de wiskundige zin van het woord aangezien er steeds een zeer kleine kans bestaat (de kennis fout (knowledge error)) dat het bewijs onterecht geaccepteerd wordt. Een zeer goed geschreven informele introductie tot ZKPK wordt gegeven in [20]. Wij introduceren het concept hieronder formeel op basis van [6] en [21]. Voor we tot de definitie van ZKPK komen, introduceren we een belangrijk concept dat in de definitie gebruikt wordt: een polynomiaal begrensde relatie. Definitie 2.34. (Polynomiaal begrensde relatie) Een relatie R ⊂ {0, 1}∗ × {0, 1}∗ is polynomiaal begrensd als er een polynoom p bestaat zodat voor alle (x, w) ∈ R geldt dat |w| ≤ p(|x|). Als (x, w) ∈ R, dan wordt w de getuige van x genoemd. LR wordt de taal genoemd en duidt op {x|∃w : (x, w) ∈ R}. R(x) is de getuige geassocieerd met x en taal LR . We kunnen nu overgaan tot de definitie van een zero-knowledge proof of knowledge. Bij de definitie gaan we uit van computationele zero-knowledge, maar de definitie kan op triviale wijze aangepast worden voor ideale of statistische zero-knowledge door de laatste eigenschap aan te passen. Onze definitie is gebaseerd op [6]. Definitie 2.35. (Zero-Knowledge Proof Of Knowledge) Een ZKPK voor een polynomiaal begrensde relatie R en met knowledge error κ is een protocol dat uitgevoerd 23

2. Basisbeginselen wordt tussen twee in polynomiale tijd uitvoerende partijen: partij P (de bewijzende partij) en partij V (de controlerende partij). Het protocol moet voldoen aan volgende drie eigenschappen: Volledigheid (completeness). Als P en V eerlijk zijn, dan accepteert V het bewijs. Of formeel: als x ∈ LR dan is P r[ZKPK(P (x), V (x)) → geaccepteerd] = 1. Geldigheid (Validity). Veronderstel dat er een kennis afleider (knowledge extractor) M bestaat die random orakel toegang heeft tot een willekeurige ˜ De geldigheidseigenschap vereist dan dat de kans dat M kwaadaardige partij P. ˜ de controleur een getuige kan afleiden minstens even hoog is als de kans dat P V onterecht kan overtuigen min de kennis fout κ. Deze eigenschap impliceert dus ook dat een bewijzende partij die geen kennis heeft van het geheim, er slechts met een verwaarloosbare kans in slaagt om een eerlijke V te overtuigen. Formeel kan de geldigheidseigenschap genoteerd worden als: ˜ ˜ Pr[M (x)↔P ∈ R(x)] ≥ Pr[ZKPK(P(x), V (x)) → geaccepteerd] − κ(x)

Zero-Knowledge. Er bestaat voor elke probabilistische polynomiale tijd con˜ een simulator S ˜ zodanig dat de ensembles troleur V V ˜ → .}x∈LR en {SV˜ (x) → .}x∈LR computationeel niet te {ZKPK(P (x), V(x)) onderscheiden zijn.

Om een zero-knowledge proof of knowledge aan te duiden, volgen we de notatie die geïntroduceerd werd door Camenisch en Stadler [22]. PK{(α, β, δ) : y = g α hβ ∧ y = g α hδ } slaagt bijvoorbeeld op een zero-knowledge proof of knowledge van de geheimen α, β en δ zodanig dat y = g α hβ en y = g α hδ . De conventie is hierbij dat de Griekse letters tussen haakjes de geheime waarden zijn waarvan de kennis moet bewezen worden, terwijl al de andere waarden publiek gekend zijn.

In deze thesis gebruiken we ZKPK’s gebaseerd op groepen van verborgen orde. Net zoals bij de verbintenis schema’s zal de groep QRn van kwadratische residu’s modulo een RSA modulus gebruikt worden. Daarnaast wordt gebruik gemaakt van de Fiat-Shamir Heuristiek om een normale interactieve ZKPK om te vormen tot een niet interactieve ZKPK. Bij een niet interactieve ZKPK voert enkel de bewijzende partij de berekeningen uit, terwijl bij een interactieve ZKPK beide partijen dat doen. Figuur 2.3 illustreert als voorbeeld een niet interactieve ZKPK die later gebruikt zal worden. We gaan er in dit dit voorbeeld vanuit dat n een speciale RSA modulus is, V, Q generatoren zijn van QRn en g een generator is van Gq met q een priemgetal. Verder veronderstellen we dat P kennis heeft van een bepaald geheim x ∈ Zq en van de waarde d ∈ [1..b n4 c]. Zowel de bewijzende partij als de controlerende partij 24

2.13. Handtekening Schema’s

Figuur 2.3: Illustratie van een ZKPK P K{(x, d) : y = gx ∧ A = V x Qd ∧ x ∈ Γ}

hebben bovendien kennis van y = g x mod p en van de Damgård-Fujisaki verbintenis A = V x Qd mod n. In de ZKPK van de figuur bewijst de bewijzende partij nu dat hij inderdaad kennis heeft van x zodanig dat y = g x mod p en A = V x Qd mod n en dat de waarde x een element is van Γ = {0, 1}lx +lφ +lH . Dit komt dus overeen met volgende proof of knowledge P K{(x, d) : y = gx ∧ A = V x Qd ∧ x ∈ Γ} Merk op dat de waarden rx , rd die de bewijzende partij in het begin van het bewijs kiest, uit een groter interval dan x en d genomen moeten worden. De reden daarvoor is dat zowel de berekening van sx als van sd over de gehele getallen gebeurt en dat er daardoor anders informatie over x of d gelekt zou kunnen worden (bijvoorbeeld de grootte).

2.13

Handtekening Schema’s

Digitale handtekening schema’s leveren niet enkel het elektronische equivalent van een manuele handtekening, maar ze zijn ook een belangrijk bouwblok in cryptografische 25

2. Basisbeginselen protocollen. Ook in deze thesis wordt gebruik gemaakt van een handtekening schema als basiselement voor voorgestelde E-Cash systeem. Een goed handtekening schema moet existentiël fraudebestendig (existentially unforgeable) zijn. Formeel wordt deze eigenschap geformuleerd als volgt: Definitie 2.36. (Existentiël fraudebestendig) Veronderstel dat een polynomiaal aantal paren {(m1 , S(m1 )), (m2 , S(m2 )), · · · , (mp , S(mp )} gegeven is waarbij met S(m) de handtekening op m bedoeld wordt. We zeggen dan dat een handtekening schema existentiël fraudebestendig is als het voor een tegenstander computationeel onmogelijk is om een paar (mk+1 , S(mk+1 )) aan te maken waarbij mk+1 ∈ / {m1 · · · mp } Het handtekening schema dat we in het voorgestelde E-Cash schema uit sectie 4.2 gebruiken moet naast existentiël fraudebestendig ook toelaten om: • Efficiënt een handtekening te plaatsen op een verbonden waarde (zodanig dat degene die de handtekening plaatst, geen informatie heeft over de getekende waarde). • Efficiënt de kennis van een handtekening op een verbonden waarde te bewijzen. Het Camenisch-Lysyanskaya handtekening schema [23] is existentiël fraudebestendig en voldoet aan bovenstaande vereisten. Er zal dan ook van dit schema gebruik gemaakt worden in het protocol. Constructie 2.3. (Camenisch-Lysyanskaya handtekening schema). Het schema bestaat uit drie polynomiale tijd gerandomiseerde algoritmes: Sleutel generatie. Bij invoer van een veiligheidsparameter k, kies een speciale RSA modulus n = pq van lengte ln = 2k. Kies V1 , ..., VL , Q, Z ∈R QRn . Geef als output PK = (n, V1 , ..., VL , Q, Z) en SK = p. Handtekening plaatsen. Bij invoer van een vector van boodschappen {(m1 ...mL ) : mi ∈ {0, 1}lm } , kies een random priemgetal e van lengte le ≥ lm + 2 en een random getal v van lengte lv = ln + lm + lφ waarbij lφ een veiligheidsparameter is. Bereken een waarde d zodat de V1m1 ...VLmL Qv = Z. De handtekening op de vector van boodschappen (m1 ...mL ) is dan het tupel (d, e, v). Verificatie van de handtekening. Om te verifiëren dat een tupel (d, e, v) een handtekening is op een vector van boodschappen (m1 ...mL ) gaan we na of de V1m1 ...VLmL Qv = Z.

26

Hoofdstuk 3

Anonieme E-Cash The problem with losing your anonymity is that you can never go back. Marla Maples

In dit hoofdstuk worden systemen geanalyseerd waarbij elektronisch geld (E-Cash) het betalingsmiddel is. Dit hoofdstuk vormt daarmee de basis voor het vervolg van het werk. In sectie 3.1 wordt een synthese gegeven van wat een anoniem E-Cash systeem juist is. Hierbij zullen de relevante partijen en hun interacties geïntroduceerd worden. In sectie 3.2 wordt vervolgens een historische evolutie van anonieme E-Cash schema’s gegeven. We zullen het hierbij hebben over online/offline, compacte, deelbare, tranfereerbare en eerlijke E-Cash. In sectie 3.3 wordt tenslotte het compacte E-Cash schema van Camenisch et al. [2] besproken, wat de basis is voor hoofdstuk 4.

3.1

Systeemoverzicht

Elektronisch geld (E-Cash) is in 1982 bedacht met als bedoeling dat het een digitaal alternatief van fysiek geld zou vormen. In zijn eenvoudigste vorm bestaat een E-Cash systeem uit drie partijen (de bank B, de gebruiker U en de verkoper M) en vier algoritmes (account aanmaken, geld afhalen, geld uitgeven, geld storten). Figuur 3.1 geeft dit weer. Allereerst maakt een gebruiker een account aan bij de bank. Eens een gebruiker een account heeft bij een bank, kunnen de gebruiker en de bank een geldafhaling protocol uitvoeren waarbij de gebruiker elektronische munten verkrijgt. Deze munten kan hij vervolgens gebruiken gedurende een gelduitgave protocol tussen hem en de verkoper. De verkoper kan de verkregen munten tot slot bij de bank stockeren door het uitvoeren van het geldstorting protocol. Vermits E-Cash bedoeld is als digitaal alternatief van echt geld, moet het systeem van Figuur 3.1 gelijkaardige eigenschappen hebben als een systeem waarbij er echt geld als betalingsmiddel gebruikt wordt. We vermelden hieronder een overzicht van de eigenschappen waaraan een E-Cash systeem moet voldoen. We maken hierbij een 27

3. Anonieme E-Cash

Figuur 3.1: Overzicht van de partijen die met elkaar interageren in een typisch anoniem E-Cash systeem

onderverdeling tussen eigenschappen enerzijds op basis van veiligheid en anderzijds op basis van bruikbaarheid in de praktijk. Een ideaal veilig E-Cash systeem voldoet aan volgende eigenschappen: Correctheid van het systeem Als de gebruiker correct interageert met de bank en vervolgens ook correct interageert met de verkoper, dan moet de verkoper in staat zijn om met een hoge kans, een munt correct te storten bij de bank. Anonimiteit Het moet onmogelijk zijn dat de bank en de verkoper erin zouden slagen (zelfs als ze samenwerken) om een munt die eerlijk verkregen wordt in het geldafhaling protocol te linken aan een munt die eerlijk gebruikt wordt in het gelduitgave protocol. Tijdens het afhalen van geld is de identiteit van de gebruiker immers gekend. Meerdere gelduitgaves zijn niet te linken aan eenzelfde entiteit Het moet onmogelijk zijn dat verschillende uitvoeringen van het uitgaveprotocol 28

3.1. Systeemoverzicht te linken zijn aan eenzelfde entiteit. Merk op dat dit een andere vereiste is als anonimiteit. Bij anonimiteit vereisen we immers dat de identiteit van de gebruiker niet bekend geraakt bij het uitgeven van geld. Volgend voorbeeld maakt het onderscheid tussen onlinkbaarheid en anonimiteit duidelijk: Stel je koopt (volledig vermomd) met cash geld een prepaid telefoonkaart in een krantenwinkel. Deze telefoonkaart is dan anoniem verkregen, maar bevat wel een kaartnummer (dat dan gebruikt wordt als pseudoniem). Telkens je deze telefoonkaart gebruikt om een gesprek te voeren, is de identiteit van degene die belt ongekend voor de telefoonmaatschappij (er is anonimiteit). Ze kunnen wel verschillende oproepen linken aan hetzelfde kaartnummer (er is geen onlinkbaarheid). Identificatie van een dubbele uitgever Een belangrijk verschil tussen elektronisch geld en fysiek geld, is dat elektronisch geld voorgesteld wordt als digitale data. Dit zorgt ervoor dat elektronisch geld, in tegenstelling tot fysiek geld, gemakkelijk te kopiëren is. Het E-Cash systeem moet dus functionaliteit voorzien om te voorkomen dat een gebruiker een door de bank verkregen munt kan kopiëren en vervolgens onopgemerkt kan gebruiken. Typisch wordt dit als volgt gedaan: Eerst wordt het kopiëren van geldig verkregen munten moeilijk gemaakt door aan de gebruiker sabotage bestendige hardware te geven. Slaagt een gebruiker er toch in om een munt te kopiëren, dan wordt ervoor gezorgd dat dit gedetecteerd wordt tijdens het gelduitgave of het geldstorting protocol. Deze detectie gaat dan gepaard met het vrijgegeven van de identiteit van een gebruiker. Op het eerste zicht lijkt het tegenstrijdig dat een betaling die anoniem gebeurt, toch ook de identificatie kan vrijgegeven bij dubbele uitgave van een munt. Volgend voorbeeld geeft echter een eenvoudige manier hoe dit kan gebeuren. Veronderstel dat met elke munt die we willen uitgeven een rechte lijn verbonden is waarvan de richtingscoëfficiënt random bepaald wordt tijdens het afhalen van de munt. De snijding van de lijn met de y-as, komt overeen met de identiteit van de gebruiker die de munt uitgegeven heeft. Als de gebruiker een munt eenmaal uitgeeft, dan wordt één punt op de lijn bekend. Dit is echter niet voldoende om zijn identiteit te leren. Geeft de gebruiker dezelfde munt nog eens uit, dan kennen we twee punten van de lijn en kunnen we ook het snijpunt met de y-as kennen. De gebruiker is dan niet langer anoniem. Traceerbaarheid Wanneer aan deze eigenschap voldaan is, kunnen alle munten uit de portefeuille van een dubbele uitgever geïdentificeerd worden en niet enkel de munt die dubbel uitgegeven werd. Bescherming van de bank (Balanseigenschap) Er moet niet alleen voorkomen worden dat een munt dubbel wordt uitgegeven, er moet ook vermeden worden dat er geld wordt vervalst of bijgemaakt. Geen enkele combinatie van gebruiker en verkoper mag er dus in slagen om het 29

3. Anonieme E-Cash geldstorting protocol succesvol uit te voeren met een munt die aanvankelijk niet door de bank werd uitgegeven of met een munt die reeds gestort is. Bescherming van de gebruiker Geen enkele combinatie van verkoper en bank mag erin slagen om een gebruiker ten onrechte te beschuldigen van een bepaalde munt dubbel uitgegeven te hebben.

Om tot praktische systemen te leiden moet het E-Cash systeem verder voldoen aan volgende vereisten: Transfereerbaarheid van elektronisch geld Het moet mogelijk zijn dat een gebruiker (een deel van) zijn geld kan overdragen naar andere gebruikers. Deelbaarheid van elektronisch geld Een munt met een waarde X moet gewisseld kunnen worden voor meerdere munten met kleinere waarde en waarvoor de som van de waardes terug X levert. Herstellen van afgehaald, maar verloren geld Het is gewenst dat munten die eerlijk afgehaald werden, maar verloren zijn door een hardware fout, terug hersteld kunnen worden. Efficiëntie van het systeem Het E-Cash systeem moet zowel geheugen- als tijdsefficiënt zijn om gebruikt te kunnen worden in praktische toepassingen. Bescherming tegen geldwitwassen, blackmailing Onconditioneel anonieme E-Cash systemen [1] werken criminele praktijken in de hand. Solms en Naccache [24] toonden aan dat in onconditioneel anonieme E-Cash systemen, blackmailing en witwassen van geld mogelijk zijn. Een ideaal E-Cash systeem moet daarom de identiteit van de eerlijke gebruiker verbergen, maar moet wel criminele praktijken als blackmailing en witwassen van geld tegengaan.

Een ideaal E-Cash systeem voldoet aan al de bovenstaande eisen. Het is tot nu toe niet mogelijk gebleken om een E-Cash systeem te beschrijven dat aan al de bovenstaande voorwaarden voldoet. Door de jaren heen zijn er wel verschillende systemen bedacht die een deel van de hierboven beschreven eigenschappen vervullen. Volgende sectie geeft een overzicht van deze systemen. 30

3.2. Overzicht van Bestaande Anonieme E-Cash Systemen

Figuur 3.2: Online versus offline E-Cash systeem. De bovenste figuur geeft het online systeem weer. De onderste figuur het offline systeem

3.2

Overzicht van Bestaande Anonieme E-Cash Systemen

David Chaum introduceerde in 1983 voor het eerst anonieme elektronische betalingssystemen [1]. Hij maakte hierbij voor het eerst gebruik van het idee van blinde handtekeningen: degene die de handtekening plaatst, aanvaardt om een boodschap te tekenen, zonder de boodschap zelf te kennen en zonder later een boodschap/handtekening paar te kunnen linken naar de transactie tijdens dewelke de handtekening geplaatst werd. In een latere paper [25] introduceerde hij samen met Fiat en Naor zijn tweede belangrijk anoniem E-Cash systeem. Het grote verschil tussen beide systemen was het verloop van het geldstorting protocol. In het E-Cash systeem van zijn eerste paper is het noodzakelijk dat er tijdens het uitvoeren van het gelduitgave protocol, contact is met de bank (of een vertrouwde derde partij) voordat een uitgegeven munt aanvaard wordt. Tijdens het contact met de bank, wordt er gecontroleerd of een bepaalde munt reeds uitgegeven is. Systemen waar een dergelijk contact met de bank nodig is, worden online E-Cash systemen genoemd. Zijn tweede paper, waar er geen contact was met de bank tijdens het uitvoeren van een gelduitgave protocol, behoort tot de klasse van offline E-Cash systemen. In een 31

3. Anonieme E-Cash offline E-Cash systeem moet de verkoper wel op geregelde tijd online gaan en het geldstorting protocol met de bank uitvoeren. Eventueel dubbel uitgegeven munten worden dan gedetecteerd en de dubbele uitgever wordt geïdentificeerd. Het spreekt voor zich dat er in online systemen zeer veel interactie met de bank nodig is. Onderzoekers van E-Cash systemen geven daarom tot op vandaag de voorkeur aan systemen van het offline type waarbij er minder interacties met de bank vereist zijn. Sinds het introduceren van E-Cash door Chaum zijn er in de literatuur een groot aantal E-Cash systemen bedacht. Elk van de onderzochte systemen vervult slechts een deel van de eigenschappen uit sectie 3.1. We overlopen de belangrijkste systemen hieronder. Ongeveer twintig jaar na het introduceren van het concept van elektronisch geld, werd door Camenisch, Hohenberger en Lysyanskaya het compacte E-Cash systeem [2] bedacht. In hun paper beschrijven ze twee modellen. Voor ons zal het eerste model het belangrijkste blijken (zie sectie 3.3), dus als we het voortaan over het compacte E-Cash systeem hebben, bedoelen we daar impliciet het eerste model mee. Dit eerste model voldoet aan een aantal belangrijke eigenschappen: het is een offline systeem, het laat toe anonieme en onlinkbare betalingen te doen, het identificeert dubbele uitgevers en het garandeert dat partijen slechts met een verwaarloosbaar kleine kans er onterecht van beschuldigd kunnen worden een bepaalde munt dubbel te storten / uit te geven. De reden dat het systeem compact genoemd wordt is omdat het bovendien geheugen- en tijdsefficiënt is. Als k een voorafbepaalde veiligheidsparameter is, dan vraagt het opslaan van 2L munten O(L + k) geheugenbits. Het uitvoeren van de geldafhaling en gelduitgave protocollen, vraagt O(L + k) stappen. Belangrijke praktische eigenschappen waar het compacte E-cash systeem niet aan voldoet is transfereerbaarheid en deelbaarheid van elektronisch geld. Het is vooral deze laatste eigenschap die ontbreekt bij het compacte E-Cash systeem. Een gebruiker kan namelijk zeer efficiënt een portefeuille met 2L munten afhalen van de bank, maar door het ontbreken van de deelbaarheid eigenschap gebeurt het uitgeven van geld munt per munt. In een poging tot het beschrijven van meer praktisch systemen werden deelbare E-Cash systemen onderzocht. Dergelijke systemen laten toe om betalingen te doen van willekeurige waarde. In de literatuur zijn heel wat voorstellen voor deelbare E-Cash systemen gedaan. Het eerste belangrijke schema was dat van Okomato [26]. Dit schema werd door Chan et al. [27] verbeterd. Het nadeel van beide systemen was echter dat ze niet voldeden aan de onlinkbaarheid eigenschap. Verschillende uitgaves van munten uit eenzelfde portefeuille waren namelijk terug te linken tot eenzelfde entiteit. Canard en Gouget [28] waren in 2007 uiteindelijk de eersten die een deelbaar E-Cash systeem ontwierpen dat gelijkaardige eigenschappen had als het compacte E-Cash systeem. Het door hen voorgestelde systeem liet offline, anonieme, onlinkbare en deelbare betalingen toe. Bovendien bied het bescherming tegen dubbel uitgegeven van munten en tegen het hiervan ten onrechte beschuldigd worden. Het schema levert al deze eigenschappen zonder beroep te doen op een vertrouwde derde partij. 32

3.3. Het Compacte Anonieme E-Cash Systeem De mogelijkheid om fysiek geld door te geven aan anderen is een eigenschap van een E-Cash systeem die ook gewenst is. Denk bijvoorbeeld maar aan applicaties die gebruik maken van E-tickets of E-coupons. In de literatuur is er beduidend minder terug te vinden over deze systemen. Dit valt te verklaren door het feit dat al vlug [29] werd aangetoond dat het onmogelijk is om een munt door te geven zonder zijn op te slagen bitlengte te vergroten en dat perfecte anonieme transfereerbare E-Cash systemen niet mogelijk zijn (een in rekenkracht onbegrensde speler kan altijd zijn eigen geld herkennen als hij het in een latere betaling terugziet). Het grote voordeel van transfereerbaarheid is dat hierdoor het aantal communicaties tussen bank en gebruiker kan verminderen. Het eerste belangrijke schema voor transfereerbare E-Cash werd geïntroduceerd door Tewari, Mahony en Peirce [30]. Twee in efficiëntie verbeterde transfereerbare E-Cash systemen worden bijvoorbeeld gegeven in [31], [32]. Klassieke anonieme E-Cash zoals beschreven door Chaum, geeft nooit de identiteit weg van een gebruiker tenzij die een munt twee keer uitgeeft. Overheden zouden een dergelijk betalingssysteem nooit aanvaarden omdat dit het paradijs zou zijn voor criminelen. In [33], [24] worden enkele voorbeelden van criminele praktijken die mogelijk zijn in een volledig anoniem systeem. Deze problemen stimuleerden een hele reeks onderzoeken naar zogenaamde escrowed en faire E-Cash systemen. Een belangrijke paper in dit verband is [34]. Beide systemen gebruiken vertrouwde derde partijen om de anonimiteit te kunnen revoceren als er een vermoeden is dat de gebruiker criminele praktijken doet.

Merk nogmaals op dat bovenstaand overzicht slechts enkele belangrijke E-Cash systemen overloopt. In de literatuur zijn er echter nog veel andere systemen theoretisch beschreven zoals herstelbare E-Cash systemen [35], [36], ...

3.3

Het Compacte Anonieme E-Cash Systeem

Het protocol dat in deze thesis gebruikt wordt, is gebaseerd op het compacte E-Cash systeem. Daarom wordt in deze sectie het compacte E-Cash systeem verder geanalyseerd. In deelsectie 3.3.1 geven we een overzicht van de veiligheidseigenschappen die het systeem bezit. Deelsectie 3.3.2 beschrijft de input/output specificaties van de algoritmes die gebruikt worden. Tot slot wordt in deelsectie 3.3.3 de constructie besproken van het compacte E-Cash systeem. We linken hierbij de cryptografische primitieven uit hoofdstuk 2, met de algoritmes uit sectie 3.3.2.

3.3.1

Specificatie van de Veiligheidseigenschappen

Het compacte E-Cash systeem voldoet aan volgende eigenschappen: het is correct, het garandeert anonimiteit en onlinkbaarheid van gebruikers, het zorgt ervoor dat dubbele uitgevers geïdentificeerd worden en het beschermt gebruikers en verkopers van onterecht beschuldigd te worden van een bepaalde munt dubbel uit te geven respectievelijk te storten. 33

3. Anonieme E-Cash Voor een formele en volledige specificatie van deze eigenschappen verwijzen we naar [2].

3.3.2

Definitie van de Algoritmes

Het compacte E-Cash protocol bestaat uit 7 algoritmes: BSleutelgen, USleutelgen, MSleutelgen, Geldafhaling, Gelduitgave, Geldstorting, Identificatie. We beschrijven hieronder op basis van [2] de input/output specificaties van deze algoritmes. • BSleutelgen(1k ). Dit algoritme genereert op basis van de veiligheidsparameter k, een private en publieke sleutel voor de bank B. De output van het algoritme noteren we als (skB , pkB ). • USleutelgen(1k ). Dit algoritme genereert op basis van de veiligheidsparameter k, een private en publieke sleutel voor de gebruiker U. De output van het algoritme noteren we als (skU , pkU ). • MSleutelgen(1k ). Dit algoritme genereert op basis van de veiligheidsparameter k, een private en publieke sleutel voor de verkoper M. De output van het algoritme noteren we als (skM , pkM ). • Geldafhaling(U(pkB , skU , n), B(pkU , skB , n)). In dit protocol haalt de gebruiker U een portefeuille W van n munten af bij de bank B. Als gevolg van het afhalen van de portefeuille, zal de bank het geld op de rekening van gebruiker pkU verminderen met n. Indien er niet voldoende geld op de rekening van de gebruiker staat, wordt een foutmelding gegeven. • Gelduitgave(U(W, pkM ), M(skM )). In dit algoritme geeft de gebruiker U een munt uit de portefeuille W aan de verkoper M. Elke munt die aan de verkoper gegeven wordt komt overeen met een tupel (S, π). De waarden in dit tupel hebben volgende betekenis: S is het serieel nummer van de munt, π is een bewijs dat de munt geldig is. Na het uitvoeren van het algoritme verkrijgt de verkoper n dergelijke tupels. Het aantal munten in de portefeuille van de gebruiker wordt daarentegen verminderd met n. Indien de gebruiker niet voldoende munten heeft om uit te geven, wordt een foutmelding gegeven. • Geldstorting(M(skM , S, π, pkB ), B(pkM , skB )). In dit protocol stort de verkoper M een munt (S, π) in een account die hij bij de bank B heeft. Als de bank de munt aanvaardt, geeft het algoritme als output dat de storting geaccepteerd wordt. De bank slaat de munt (S, π) op in een lijst L van gestortte munten. Vermoedt de bank dat een gebruiker een munt tweemaal uitgegeven heeft, dan gebruikt de bank het identificatie algoritme en wordt (pkU , “dubbel uitgegeven munt”) als output gegeven. Vermoedt de bank dat een munt tweemaal gestort wordt door de verkoper dan geeft dit algoritme als output (pkM , “dubbel gestortte munt”). 34

3.3. Het Compacte Anonieme E-Cash Systeem • Identificatie(S, π1 , π2 ). Dit protocol laat toe om dubbele uitgevers te identificeren gebruik makende van twee verschillende bewijzen π1 , π2 horende bij eenzelfde munt. De output van het algoritme is (pkDU , ΠG ) waarbij pkDU de publieke sleutel is van de dubbele uitgever en ΠG het bewijs is dat pkDU de munt S dubbel uitgegeven heeft. In sectie 4.2 geven we een uitbreiding op de hier beschreven versie van het compacte E-Cash systeem. We zullen daar dezelfde algoritmes gebruiken als deze welke hier gegeven zijn.

3.3.3

Beschrijving van de Constructie

In deze deelsectie beschrijven we op een gelijkaardige manier als in [2], de constructie van het E-Cash systeem. We geven voor elk van de algoritmes uit sectie 3.3.2 de gebruikte cryptografische primitieven om, gegeven de input, tot de gespecificeerde output te komen. BSleutelgen(1k ) Dit algoritme geeft als output de private sleutel skB en de publieke sleutel pkB van de bank B. De hiervoor uit te voeren stappen worden hieronder beschreven. Er worden eerst twee groepen aangemaakt: • De groep QRn van kwadratische residu’s modulo een speciale RSA modulus n = ab van 2k bits. • De groep Gq = hgi van priem orde q = O(2k ) waarin het DDH probleem moeilijk is. We kiezen hierbij voor de deelgroep van orde q van Zp waarbij p = 2q + 1 een veilig priemgetal is met bitlengte 2k. Vervolgens worden er twee generatoren Z, Q ∈R QRn en één generator g ∈R Gq gekozen. Daarna worden er vijf elementen Vi ∈R QRn , i=1..5 gekozen. De private en publieke sleutel worden dan gegeven door: (skB , pkB ) = (a, (V1 , V2 , ..., V5 , Q, Z, g, n, q)). We gaan er voor deze thesis vanuit dat er minstens één door iedereen vertrouwde partij de correctheid van de waarden in de publieke sleutel controleert. USleutelgen(1k ) en MSleutelgen(1k ) Deze algoritmes leveren de private en publieke sleutel voor gebruikers en verkopers, maar gaan hierbij gelijkaardig te werk. Telkens wordt er eerst een private sleutel sk ∈ Zq gekozen. De publieke sleutel wordt dan bepaald als pk = g sk mod p. Geldafhaling(U(pkB , skU , n), B(pkU , skB , n)) Tijdens het geldafhaling protocol verkrijgt de gebruiker een portefeuille W met n = 2L elektronische munten. Een portefeuille bestaat uit het tupel (skU , s, t, σ, J). De betekenis van de waarden in het tupel is als volgt: s is een random waarde die gebruikt wordt voor het genereren van een serieel nummer S van een munt, t is een 35

3. Anonieme E-Cash random waarde die gebruikt wordt voor het genereren van een dubbele uitgever identificatie tag T , σ is een blinde CL handtekening van de bank op het tupel (skU , s, t) en J is een L-bit teller die bijhoudt hoeveel munten er nog in de portefeuille zitten. Volgende stappen moeten uitgevoerd worden om tot deze portefeuille W te komen. 1. Er moet een in twee richtingen geauthentiseerd kanaal opgezet worden tussen gebruiker U en bank B. 2. U bepaalt t ∈R Zq . 3. U en B dragen beiden bij aan het bepalen van s ∈R Zq . Dit doen ze door volgende stappen uit te voeren: U selecteert s0 ∈R Zq en zendt de Damgård 0 en Fujisaki verbintenis A0 = V erbind((skU , s0 , t), v) = V1sku V2s V3t Qv mod n met v ∈R [1..b n4 c]. De bank B zendt daarop r0 ∈R Zq naar U. U berekent nu s = s0 + r0 en A = V erbind((skU , s, t), v) = V1sku V2s V3t Qv mod n. De bank is nu ook in de mogelijkheid om A te berekenen. 4. De gebruiker en de bank voeren nu een efficiënt protocol [23] uit om een CL handtekening σ van de bank te bekomen op de waarden bevat in de verbintenis A. 5. De gebruiker slaagt de portefeuille W = (skU , s, t, σ, J) op. 6. De bank vermindert het geld op de rekening van gebruiker pkU met 2L munten.

Gelduitgave(U(W, pkM ), M(skM )) Tijdens het gelduitgave protocol geeft de gebruiker een munt aan de verkoper. Een munt wordt voorgesteld door een tupel (S, π = (R, T, φ)). Hierbij is S het seriële nummer van de munt. R is een waarde die random gegenereerd is door de verkoper bij elke keer een gebruiker een nieuwe munt uitgeeft en zorgt ervoor dat gebruikers niet onterecht beschuldigd kunnen worden. T is een tag die toelaat om bij het dubbel uitgeven van een munt, de publieke sleutel van de dubbele uitgever te achterhalen. φ is een niet interactieve ZKPK van de waarden (J, skU , s, t, σ) zodanig dat er geldt dat DY (J), T = pk (F DY (J))R en dat σ een correcte handtekening 0 ≤ J < 2L , S = Fg,s U g,t is. Dit laatste wordt geverifieerd aan de hand van [23]. Volgende stappen moeten uitgevoerd worden om succesvol een munt te verzenden: 1. Er moet een in één richting geauthentiseerd kanaal zijn van de verkoper M naar de gebruiker U toe (de verkoper is geauthentiseerd). 2. De verkoper kiest R ∈R {0, 1}lH waarbij lH ≥ 160 bit en stuurt R naar de gebruiker. DY (J) en T = pk (F DY (J))R . Hij stuurt S, T 3. De gebruiker berekent S = Fg,s U g,t vervolgens op naar de verkoper.

4. De gebruiker zendt de niet interactieve ZKPK φ naar de verkoper. 36

3.3. Het Compacte Anonieme E-Cash Systeem 5. Als φ klopt, dan slaagt M de munt (S, π) = (S, (R, T, φ)) op in een lijst met ontvangen munten.† 6. De teller J van U wordt aangepast.

Geldstorting(M(skM , S, π, pkB ), B(pkM , skB )) Het storten van een munt gaat als volgt: 1. Zet een in twee richtingen geauthentiseerd kanaal op tussen verkoper M en bank B. 2. De verkoper stuurt een munt (S, π = (S, (R, T, φ))) naar de bank. 3. Als (S, R) nog nooit voorkwamen wordt de munt aanvaard en wordt de rekening van M bij de bank met een munt opgehoogd. Als er reeds een tupel (S2 , R2 ) in de database van de bank staat waarvoor S = S2 en R = R2 , dan wordt de verkoper beschuldigd van een munt dubbel te willen storten. In dat geval wordt de publieke sleutel pkM van M als output gegeven. Als er reeds een tupel (S2 , R2 ) in de database van de bank staat waarvoor S = S2 maar R 6= R2 , dan wordt de gebruiker beschuldigd van een munt dubbel te hebben uitgegeven. In dat geval wordt het identificatie algoritme uitgevoerd en wordt de publieke sleutel pkU van de geïdentificeerde dubbele uitgever als output gegeven.

Identificatie(S, π1 , π2 ) Gegeven π1 , π2 waarvoor geldt dat S1 = S2 = S en R1 6= R2 dan wordt de publieke sleutel van de dubbele uitgever bepaald als: (

3.3.4

T2R1 (R1 −R2 )−1 g uR1 +R1 R2 (J2 +S) (R1 −R2 )−1 ) = ( ) = gu g uR2 +R1 R2 (J1 +S) T1R2

Veiligheidsanalyse

Het compacte E-Cash systeem voldoet aan de eigenschappen uit sectie 3.3.1 als voldaan is aan de sterke RSA en de Decisional Diffe-Hellman Inversion(y-DDHI) veronderstellingen. Voor het bewijs hiervan verwijzen we weer naar [2].

†

Merk op dat de bank enkel (S, R, T ) hoeft op te slaan, als zij niet aan externe partijen moet kunnen bewijzen dat een gebruiker een munt tweemaal uitgegeven heeft. Dit bespaart geheugen.

37

Hoofdstuk 4

Anonieme E-Cash voor Computationeel Beperkte Platformen The desire to economize time and to eliminate human liability to error, is probably as old as the science of arithmetic itself. Howard Aiken.

In dit hoofdstuk geven we een uitbreiding van het anonieme E-Cash systeem uit hoofdstuk 3. Het systeem dat besproken werd in dat hoofdstuk, had interessante veiligheidseigenschappen, maar is met het oog op implementatie niet optimaal. Voor het uitvoeren van het geldafhaling en het gelduitgave protocol, moet de gebruiker immers hardware gebruiken die bestendig is tegen sabotage. Het gaat daarbij typisch om smartcards of mobile security cards (zie hoofdstuk 5). Dergelijke hardware modules zijn in rekenkracht beperkt, hebben beperkte opslagcapaciteiten en hebben een gelimiteerde herschrijfbaarheid. De systemen uit hoofdstuk 3 vereisen echter dat alle code van de gebruiker uitgevoerd wordt op die sabotage bestendige hardware. Het spreekt voor zich dat dit niet optimaal is. Het anonieme E-Cash systeem voor computationeel beperkte platformen dat beschreven wordt in dit hoofdstuk, tracht hier een oplossing voor te bieden. In sectie 4.1 geven we een synthese van wat een anoniem E-Cash systeem voor computationeel beperkte platformen juist is. We beschrijven daarbij de partijen en hun interacties en leggen de link met het systeemoverzicht van het anoniem E-Cash systeem uit sectie 3.1. In sectie 4.2 stellen we tenslotte een eigen systeem voor dat gebaseerd is op het compacte E-Cash systeem uit sectie 3.3. De implementatie van dit systeem op echte hardware modules zal besproken en geanalyseerd worden in hoofdstukken 5 en 6. 39

4. Anonieme E-Cash voor Computationeel Beperkte Platformen

Figuur 4.1: Overzicht van de partijen die met elkaar interageren in een anoniem E-Cash systeem voor computationeel beperkte platformen

4.1

Systeemoverzicht

Een anoniem E-Cash systeem voor computationeel beperkte platformen bestaat uit vier partijen die met elkaar interageren: een host H, een vertrouwd element T P, een bank B en een verkoper M. Zoals op figuur 4.1 weergegeven is, vormen de host en het vertrouwde element samen de gebruiker U. De host is hierbij typisch een relatief krachtig computationeel apparaat van U, zoals bijvoorbeeld een smartphone. Het vertrouwde element is bijvoorbeeld een smartcard die U gebruikt om geheime gegevens op te slaan en er vertrouwelijke bewerkingen op uit te voeren. De interacties tussen U en M en tussen U en B verlopen op net dezelfde manier als in het anonieme E-Cash systeem uit hoofdstuk 3. De gebruiker voert een geldafhaling protocol uit met de bank om munten af te halen. Hij kan deze munten daarna gebruiken in een gelduitgave protocol met de verkoper. De verkoper kan tenslotte de ontvangen munten storten op zijn rekening bij de bank. Het grote verschil met het systeem uit hoofdstuk 3 is dat, tijdens elk van deze protocols, de gebruiker de berekeningen intern opsplitst tussen de host H en het vertrouwde element T P. Deze opsplitsing moet zodanig gebeuren dat deze niet bepalend is voor de veiligheidseigenschappen van het systeem. Een ideaal anoniem E-Cash systeem voor computationeel beperkte platformen voldoet dus aan dezelfde veiligheidseigenschappen als gegeven in sectie 3.1. Daarnaast moet het bovendien onmogelijk zijn dat de host zonder interactie met het vertrouwde element, deelneemt aan een gelduitgave of een geldstorting. 40

4.2. Het Voorgestelde Systeem

4.2

Het Voorgestelde Systeem

In deze sectie stellen we een anoniem E-Cash systeem voor computationeel beperkte platformen voor. Het schema is gebaseerd op het compacte E-Cash systeem uit sectie 3.3. We geven in deze sectie eerst een motivatie waarom we ons op het compacte E-Cash systeem baseerden. Daarna geven we de veiligheidseigenschappen die we vereisen voor het systeem. Dit wordt gevolgd door een gedetailleerde beschrijving van de constructie. Tot slot bewijzen we dat het schema voldoet aan de gewenste veiligheidseigenschappen.

4.2.1

Motivatie

Het is vanzelfsprekend dat indien een bestaand schema uitgebreid wordt, de eigenschappen van dat schema mee de eigenschappen van het nieuwe schema zullen bepalen. Bij het kiezen van een bestaand E-Cash systeem waarop we ons zouden baseren, speelden volgende elementen een belangrijke rol: • Het is interessant dat het systeem van het offline type is. Het aantal interacties met de bank blijft dan beperkt. • We vereisen dat het systeem anonimiteit en onlinkbaarheid van gebruikers voorziet. Daarnaast moet het er ook voor zorgen dat dubbele uitgevers geïdentificeerd worden en dat geen enkele partij er onterecht van beschuldigd wordt met het systeem te knoeien. Tot slot moet het zeker voldoen aan de correctheid eigenschap en de balans van de bank moet in evenwicht zijn. Eigenschappen als deelbaarheid, transfereerbaarheid van elektronisch geld zijn nuttig maar stellen we niet als vereiste. Er bestaan immers toepassingen waar dergelijke eigenschappen niet van belang zijn [37]. • Het systeem moet de gebruiker beschermen tegen corruptie pogingen van andere - kwaadwillige - gebruikers, maar de veiligheidseigenschappen van verkoper en bank moeten behouden blijven zelfs indien een gebruiker gecorrumpeerd is. We nemen hierbij als conventie aan dat we een gebruiker corrupt noemen van zodra andere gebruikers erin slagen om geld van hem te stelen of om ervoor te zorgen dat hij (zonder dat hij zelf kwaadwillige bedoelingen had) geïdentificeerd wordt als dubbele uitgever. • Het systeem moet compact en efficiënt zijn. Deze vereisten zijn belangrijk met het oog op implementatie. De apparaten die de gebruiker te werk stelt tijdens het uitvoeren van transacties, zijn zowel in geheugen als in rekenkracht beperkt. Een systeem waarbij het afhalen en uitgeven van munten efficiënt kan gebeuren en waarbij afgehaalde munten compact opgeslagen kunnen worden, is dus noodzakelijk. • Het systeem moet eenvoudig te implementeren cryptografische bouwblokken bevatten. Dit is ook zeer belangrijk met het oog op implementatie. Er bestaan slecht een beperkt aantal libraries die ontwikkelaars van software helpen bij 41

4. Anonieme E-Cash voor Computationeel Beperkte Platformen .. . Port. 1 Port. 2 ··· Port. x

idUi

··· uitTeGeven:= [· · · ], uitGegeven:= [· · · ], dubberUitGegeven:= [· · · ] uitTeGeven:= [· · · ], uitGegeven:= [· · · ], dubberUitGegeven:= [· · · ] ··· uitTeGeven:= [· · · ], uitGegeven:= [· · · ], dubberUitGegeven:= [· · · ]

.. .

···

Tabel 4.1: Tabel die alle relevante informatie bijhoudt over gebruikers en hun afgehaalde en uitgegeven munten. De afkorting port. staat voor portefeuille. .. . idMi .. .

··· teStorten:= [· · · , (. , .), · · · ], gestort:= [· · · ], dubbelGestort:= [· · · ] ···

Tabel 4.2: Tabel die alle relevante informatie bijhoudt over verkopers en hun ontvangen en bij de bank gestortte munten. .. . Pi .. .

··· (idport , nrmunt )i ···

Tabel 4.3: Tabel die alle relevante gegevens bevat om anonimiteit te garanderen.

het implementeren van cryptografische algoritmes op sabotage bestendige hardware zoals smartcards. Heel wat cryptografische primitieven moeten dus in software zelf geïmplementeerd worden (zonder toegang tot bijvoorbeeld een cryptografische coprocessor) en voeren dus trager uit. • Het systeem moet voldoende potentieel hebben om opgesplist te kunnen worden tussen een host en een vertrouwd element. Bij het vergelijken van de systemen uit sectie 3.2 met de hierboven staande gewenste eigenschappen, bleek dat het anonieme compacte E-Cash systeem de beste keuze was. Het systeem voldoet immers aan elk van bovenstaande vereisten.

4.2.2

Specificatie van de Veiligheidseigenschappen

We definiëren nu welke veiligheidseigenschappen we vereisen voor het voorgestelde systeem. Daartoe beschrijven we een ideale functionaliteit F die effectief de eigenschappen bevat die het systeem in het ideale geval moet hebben. In deelsectie 4.2.5 tonen we dan aan dat het voorgestelde E-Cash systeem de ideale functionaliteit emuleert. 42

4.2. Het Voorgestelde Systeem

De ideale functionaliteit F maakt gebruik van drie tabellen: 1. Tabel 4.1 die alle relevante informatie over gebruikers bijhoudt. Voor elke nieuwe gebruiker wordt er een nieuwe rij aangemaakt in de tabel. In die rij wordt enerzijds de unieke identiteit idUi van de gebruiker genoteerd en anderzijds worden er gegevens genoteerd over welke portefeuilles hij al heeft afgehaald. Met een portefeuille komen steeds twee nummers overeen: een volgordenummer nrport dat uniek is per gebruiker en een identificatie nummer idport dat uniek is in het hele systeem. We nemen idport = (idUi , nrport ). Een portefeuille bevat steeds n munten die ook elk een nummer krijgen dat uniek is per portefeuille. Munten in een portefeuille kunnen tot twee lijsten behoren: een lijst van afgehaalde maar nog niet uitgegeven munten (de uitTeGeven lijst) en een lijst van afgehaalde maar reeds uitgegeven munten (de uitGegeven lijst). Als een portefeuille voor het eerst afgehaald wordt, zitten alle munten in de eerste lijst. Wordt een munt uitgegeven, dan wordt het nummer van die munt uit de eerste lijst genomen en naar de tweede lijst verplaatst. De derde lijst (de dubbelUitGegeven lijst) bevat tenslotte de nummers van munten die meermaals uitgegeven werden. Het is vanzelfsprekend dat als een munt dubbel wordt uitgegeven, dat deze dan al aanwezig is in de lijst met uitgegeven munten en er dus niet nog eens in moet geplaatst worden. 2. Tabel 4.2 die alle relevante informatie over verkopers bijhoudt. Voor elke verkoper is er ook hier een aparte rij in de tabel. Die rij bevat enerzijds de unieke identiteit van de verkoper en bevat anderzijds gegevens over ontvangen en gestortte munten. Als een verkoper een niet dubbel uitgegeven munt verkrijgt van een gebruiker, dan wordt in de lijst met te storten munten een nieuw tupel (. , .) aangemaakt. Het eerste element van dit tupel komt overeen met het unieke portefeuille nummer idport van de portefeuille waarvan de uitgegeven munt afkomstig is. Het tweede element komt overeen met het nummer van de munt. Als de verkoper een munt verkrijgt die wel dubbel uitgegeven is door een gebruiker, dan wordt deze munt niet in de lijst met te storten munten geplaatst. Telkens als een verkoper nu een munt wilt storten bij de bank, dan wordt het tupel horende bij die munt verplaatst naar de lijst met gestortte munten. Wil een verkoper een munt dubbel uitgeven, dan verschijnt het tupel horende bij deze munt, ook in de lijst met dubbel gestortte munten. 3. Tabel 4.3 bevat alle relevante gegevens die nodig zijn om anonimiteit te garanderen. De afkomst van een bepaalde munt wordt geanonimiseerd door met elke munt een verschillend pseudoniem P overeen te laten stemmen. Er moet dan uiteraard bijgehouden worden welk pseudoniem met welke munt overeenkomt. Vermits elke munt uniek geïdentificeerd kan worden door het koppel (idport , nrmunt ), wordt in tabel 4.3 voor elk pseudoniem P het overeenstemmende koppel (idport , nrmunt ) genoteerd. De ideale functionaliteit die hieronder gegeven wordt beschrijft nu hoe er van deze tabellen gebruik gemaakt wordt tijdens de verschillende transacties: set-up, geldaf43

4. Anonieme E-Cash voor Computationeel Beperkte Platformen haling, gelduitgave, geldstorting. In wat volgt noteren we de hier gegeven functionaliteit als FASEC waarbij ASEC staat voor Anonymous Splitted E-Cash.

Functionaliteit FASEC - Bij het binnenkomen van de boodschap (setupUser, idUi ) van T P i 1. Voeg voor de gebruiker Ui met identiteit idUi een nieuwe rij toe aan tabel 4.1. Stuur daarna idUi door naar de corresponderende host Hi . - Bij het binnenkomen van de boodschap (setupMerchant, idMi ) van Mi 1. Voeg de verkoper Mi met identiteit idMi , een nieuwe rij toe aan tabel 4.2. - Bij het binnenkomen van de boodschap (withdraw, n) van host Hi 1. Vraag het bijhorende T P i of het wil deelnemen in een geldafhaling van n munten door er (WithdrawInvolveReq, n) naar te sturen. Als antwoord wordt (WithdrawInvolveAnswer, a) ontvangen. Enkel als a = 1 gaan we met stap 2 verder (anders wordt de transactie gestopt). 2. Vraag de bank B of de host Hi de permissie heeft om n munten af te halen door (WithdrawPermReq,idUi , n) naar B te sturen. Als antwoord wordt (WithdrawPermAnswer, b) ontvangen. Is b = 0, stuur dan (TransactionResult, b) naar Hi en T P i en stop dan de transactie. Is b = 1, update dan de tabel van de gebruikers door een nieuwe portefeuille met nummer nrport toe te voegen voor gebruiker Ui . Informeer Hi en T P i over de gelukte transactie door er (TransactionResult, b, nrport ) naartoe te sturen. -Bij het binnenkomen van de boodschap (spend, idport , nrmunt , idMi , b) van host Hi 1. Stuur (SpendInvolveReq, idport , nrmunt ) naar de bijhorende T P i om te vragen of hij wilt deelnemen in een gelduitgave actie van de munt met nummer nrmunt uit de portefeuille met id idport . Als antwoord wordt (SpendInvolveAnswer, a) ontvangen. Enkel als a = 1 gaan we verder met stap 2. 2. Pas in tabel 4.1 de rij van de bij Hi horende gebruiker Ui aan: als de munt met nummer nrmunt nog in de lijst met uit te geven munten van de portefeuille met id idport staat, verplaatsen we hem naar de lijst met uitgegeven munten. Staat de munt reeds in de lijst met uitgegeven munten, dan markeren we de munt als dubbel uitgegeven door het koppel (idport , nrmunt ) in de lijst met dubbel uitgegeven munten te vermelden.

44

4.2. Het Voorgestelde Systeem

3. Pas in tabel 4.2 de rij van verkoper Mi aan: enkel als er nog geen koppel (idport , nrmunt ) in de lijst met te storten munten of in de lijst met gestortte munten van verkoper Mi staat, plaatsen we dit koppel in de lijst met te storten munten. 4. Pas tabel 4.3 aan: genereer een nieuw pseudoniem P en vermeld in de tabel dat P hoort bij het koppel (idport , nrmunt ). 5. Tot slot wordt de verkoper Mi nog ingelicht over de spend fase. Afhankelijk van of Hi corrupt is of niet, gebeurt dit als volgt: • Als Hi niet corrupt is, wordt (InformSpend, P ) naar Mi gestuurd. • Als Hi corrupt is, hangt het van de waarde b af of de identiteit idUi vrijgegeven of verborgen gehouden wordt. Is b = 0 dan wordt (InformSpend, P ) naar Mi gestuurd en blijft de identiteit verborgen. Is b = 1 dan wordt (InformSpend, idU i , P ) naar Mi gestuurd en wordt de identiteit van U vrijgegeven. - Bij het binnenkomen van een boodschap (deposit, P ) van de verkoper Mi 1. Zoek het koppel (idport , nrmunt ) dat hoort bij het pseudoniem P . Ga enkel naar de stap 2 als er een overeenkomt gevonden is. 2. Pas tabel 4.2 aan: Als er voor Mi in de lijst met gestortte munten reeds een koppel (idport , nrmunt ) staat, dan noteren we dit koppel in de lijst met dubbel gestortte munten (tenzij het er al in staat). In het andere geval verplaatsen we het koppel van de lijst met te storten munten, naar de lijst met gestortte munten. 3. Tot slot informeren we de bank B van een deposit transactie. Afhankelijk van de situatie of er dubbele uitgevers/storters zijn, sturen we volgende boodschap naar B: • Leid uit idport = (idUi , nrport ) de identiteit idUi af van de gebruiker die de munt horende bij het pseudoniem P uitgegeven heeft. Bekijk dan in tabel 4.1 de gegevens over de portefeuille met nummer nrport van gebruiker Ui . Als het muntnummer nrmunt terug te vinden is in de lijst met dubbel uitgegeven munten, stuur dan (NotifyDeposit, idMi , idUi , DoubleSpendAlert, P ) naar B. • Bekijk in tabel 4.2 de gegevens van verkoper Mi . Als het koppel (idport , nrmunt ) terug te vinden is in de lijst van dubbel gestortte munten, stuur dan (NotifyDeposit, idMi , DoubleDepositAlert, P ) naar B. • Indien geen dubbele uitgevers of dubbele storters zijn, sturen we (NotifyDeposit, idMi , P ). 45

4. Anonieme E-Cash voor Computationeel Beperkte Platformen - Bij het binnenkomen van (AccuseDoubleSpend, P , idu ) van B 1. Zoek de combinatie (idport , nrport ) horende bij P . Staat de munt met nummer nrmunt in de lijst met dubbel uitgegeven munten van de portefeuille met identiteit idport . En behoort deze portefeuille bovendien tot gebruiker idu , dan sturen we (guilty) naar B. Anders sturen we (not guilty).

De veiligheidseigenschappen waaraan FASEC voldoet worden hieronder kort samengevat. Voor een meer diepgaande uitleg van deze eigenschappen verwijzen we naar sectie 3.1. - FASEC garandeert anonimiteit van de gebruikers. Zolang de gebruikers eerlijk zijn, kan geen enkele combinatie van bank en verkoper, een munt die afgehaald werd tijdens een geldafhaling linken aan een munt die gebruikt wordt tijdens een gelduitgave. Merk op dat anonimiteit bovendien enkel gegarandeerd is als de Host niet corrupt is. Een corrupte host kan namelijk altijd een boodschap plaatsen achter elk verzonden bericht. - FASEC garandeert dat twee eerlijk uitgevoerde gelduitgaves niet terug te linken zijn tot eenzelfde entiteit. - Het systeem beschreven door FASEC is correct. Als alle partijen in het protocol eerlijk zijn, dan verloopt het systeem als gewenst. - FASEC garandeert dat de identiteit van dubbele uitgevers achterhaald wordt. Er is echter wel geen traceerbaarheid. - FASEC garandeert dat dubbele storters ontmaskerd worden. - FASEC beschermt gebruikers. Deze bescherming is driedelig. Ten eerste worden eerlijke gebruikers niet onterecht beschuldigd van een bepaalde munt dubbel uitgegeven te hebben (dit wordt soms strong exculpability genoemd). Ten tweede kan een kwaadwillige host geen gelduitgave of geldafhaling uitvoeren zonder interactie met het vertrouwde element. Tot slot kan een kwaadwillige host niet voorkomen dat het vertrouwde element een nieuwe portefeuille verkrijgt nadat het geldafhaling protocol succesvol uit werd gevoerd. Deze drie eigenschappen tonen dus aan dat het schema protectie biedt tegen corruptie door andere - kwaadwillige - gebruikers. - FASEC voldoet aan de balanseigenschap. Geen enkele combinatie van verkopers en gebruikers is in staat meer geld te storten bij de bank dat dat ze er afgehaald hebben. Geld kan dus niet gecreëerd worden.

46

4.2. Het Voorgestelde Systeem

4.2.3

Definitie van de Algoritmes

Vermits de interacties tussen de gebruiker U, de bank B en de verkoper M dezelfde zijn als deze voor het compacte E-Cash systeem, gebruiken we hier dezelfde definities als in sectie 3.3.2. De operaties die U in elk van de algoritmes moet uitvoeren worden wel gesplitst tussen een host H en een vertrouwd element T P.

4.2.4

Beschrijving van de Constructie

Het E-Cash protocol bestaat uit 8 algoritmes: BSleutelgen, USleutelgen, MSleutelgen, Geldafhaling, Gelduitgave, Geldstorting, Identificatie, ControleerSchuld. Elk van deze algoritmes wordt nu in detail uitgelegd. BSleutelgen(1k ) De bank B bepaalt haar publieke en private sleutel zoals hieronder weergegeven. We gaan er impliciet vanuit dat er minstens één partij is die iedereen vertouwt en die de correctheid van de publieke sleutel van B nagaat. Dit is nodig om een aanval zoals beschreven in [2] te vermijden. Bepalen (sk,pk) voor de bank - genereer een speciale RSA modulus n = ab van 2k bits en met a, b veilige priemgetallen - genereer een veilig priemgetal p = 2q + 1 van minstens k bits - vind twee generators Z, Q van QRn - vind de elementen V1 , V2 , V3 , V4 , V5 ∈R QRn - vind een generator g van de deelgroep G met orde q van Z∗p . - neem (a, (p, n, g, V1 , V2 , V3 , V4 , V5 , Z, Q)) als (skB , pkB )

USleutelgen(1k ) Het vertrouwde T P bepaalt de publieke en private sleutel van de gebruiker U als volgt: Bepalen (sk,pk) voor een gebruiker - stel sku = u met u ∈R Z∗q - stel pku = g u mod p

MSleutelgen(1k ) De verkoper M bepaalt zijn publieke en private sleutel als volgt: 47

4. Anonieme E-Cash voor Computationeel Beperkte Platformen

Figuur 4.2: Overzicht van de deelstappen en van de verzonden boodschappen tijdens het geldafhaling protocol

Bepalen (sk,pk) voor een verkoper - stel skm = m met m ∈R Z∗q - stel pkm = g m mod p

Geldafhaling(U(pkB , skU , n), B(pkU , skB , n)) In dit algoritme worden de vier stappen van figuur 4.2 uitgevoerd. We gaan er 48

4.2. Het Voorgestelde Systeem bij de bespreking vanuit dat B weet wat de publieke sleutel is van de gebruiker waarmee hij interageert en dat U weet wat de publieke sleutel is van de bank waarmee hij communiceert. Stap 1 Het opzet van de eerste stap is een Damgård en Fujisaki verbintenis A te bekomen op de waarden u, s en t. Zoals zal blijken voegen zowel de bank als de gebruiker willekeurigheid toe aan s. Volgende deelstappen worden hiervoor uitgevoerd: a) T P voert algoritme 1a uit en stuurt vervolgens A00 naar de H. uitvoering 1a: - genereer v 0 ∈R [1..b n4 c] - genereer s0 ∈R Z∗q 0 0 - bereken A00 = V1u V2s Qv mod n b) H voert algoritme 1b uit en stuurt A0 naar B. uitvoering 1b: - genereer t ∈R Z∗q - bereken A0 = A00 V3t mod n c) B voert algoritme 1c uit en stuurt r0 naar H. uitvoering 1c: - genereer r0 ∈R Z∗q 0 - bereken A = A0 V2r mod n d) H ontvangt r0 van B en berekent zelf ook de verbintenis A volgens uitvoering 1d. Vervolgens stuurt hij r0 en A door naar T P. uitvoering 1d: 0 0 - bereken A = A0 V2r = V1u V2s V3t Qv mod n e) T P voert 1e uit. uitvoering 1e - bereken s = s0 + r0 - stockeer A

Stap 2 In een tweede stap voeren U en B een protocol [23] uit om een CL handtekening σ = (d, e, v) te verkrijgen op de waarden bevat in de verbintenis A. 49

4. Anonieme E-Cash voor Computationeel Beperkte Platformen Hiervoor wordt eerst volgende ZKPK gedaan waarbij lx = bitlengteOrde(Zq ) en ly = bitlengteSchattingOrde(QRn ) : 0

ZKP K{(u, s, t) : pku = g u ∧ A = V1u V2s V3t Qv ∧ u, s, t ∈ {0, 1}lx +lφ +lH ∧ v 0 ∈ {0, 1}ly +lφ +lH } Het uitvoeren van de ZKPK vereist volgende deelstappen: a) T P voert 2a uit en stuurt TA0 , TU naar H. uitvoering 2a: - genereer ru , rs ∈R {0, 1}lx +lφ +lH en rv0 ∈R {0, 1}ly +lφ +lH - bereken TA0 = V1ru V2rs Qrv0 mod n - bereken TU = g ru mod p b) H voert 2b uit. uitvoering 2b: - genereer rt ∈R {0, 1}lx +lφ +lH - bereken TA = TA0 V3rt mod n c) H wacht tot hij de nonce ni ∈R {0, 1}lH ontvangt van B en voert vervolgens 2c uit. Daarna stuurt hij c0 naar T P. uitvoering 2c: - bereken Sx = nkV1 kV2 kV3 kQkA en c0 = H(Sx kTA kTU kni ) d) T P voert 2d uit en stuurt (c, nt , su , ss , sv0 ) naar H. uitvoering 2d: - genereer nt ∈ {0, 1}lφ - bereken c = H(c0 knt ) - bereken su = ru − cu, sv0 = rv0 − cv 0 en ss = rs − cs e) H voert 2e uit en stuurt vervolgens (c, nt , su , sv0 , ss , st ) naar B. uitvoering 2e: - bereken st = rt − ct f) B voert 2f uit. uitvoering 2f: - controleer of su , ss , st ∈ {0, 1}lx +lH +lφ en sv0 ∈ {0, 1}ly +lH +lφ - bereken T˜A = Ac V1su V2ss V3st Qsv0 mod n - bereken T˜U = pkuc g su mod p - controleer of c = H(H(Sx kT˜A kT˜U kni )knt ) 50

4.2. Het Voorgestelde Systeem Vervolgens verkrijgt de gebruiker de CL handtekening van de bank via de volgende stappen. g) B voert 2g uit en stuurt (d, e, v 00 , nx ) naar H. uitvoering 2g: 0 - genereer priemgetal e ∈R [2le −1 , 2le −1 + 2le −1 ] met le > lx + 2 en le0 de lengte van het interval waaruit e gekozen wordt. - genereer v 00 ∈ {0, 1}lv met lv = lx + ln + lφ . 1 - bereken d = ( AQZv00 ) e mod n - bereken n0x ∈R {0, 1}lφ en encrypteer nx via de gebruiker zijn publieke sleutel tot nx . h) H voert 2h uit en stuurt (d, e, v 00 , t, J, nx ) naar T P. uitvoering 2h: 0 - controleer of e priem is en e ∈ [2le −1 , 2le −1 + 2le −1 ] 00 - controleer of Z = AQv de mod n - is de controle geslaagd, stockeer dan: (J = 2L , d, e).

Stap 3 In de derde stap maakt T P de portefeuille van de gebruiker compleet door 3 uit te voeren en stuurt au naar de bank. uitvoering 3: - maak W = (u, s, t, σB (u, s, t), J) compleet door v = v 0 + v 00 te berekenen en sla W op. - Decrypteer nx met de private sleutel tot n0x . - Bereken het hash resultaat au = H(pku ||n0x ) Stap 4 Tenslotte, in stap 4, controleert de bank of au = H(pku ||n0x ). Is dit zo dan noteert B een debit van 2L munten voor de rekening van pkU . Is dit niet zo dan lanceert de bank een procedure om de gebruiker als fraudeur te markeren.

51

4. Anonieme E-Cash voor Computationeel Beperkte Platformen Gelduitgave(U(W, pkM ), M(skM , n))

Figuur 4.3: Overzicht van de deelstappen en van de verzonden boodschappen tijdens het gelduitgave protocol

In dit algoritme worden de vijf protocolstappen van figuur 4.3 uitgevoerd. We gaan er bij de bespreking impliciet vanuit dat de gebruiker weet wat de publieke sleutel is van de verkoper waarmee hij interageert. Stap 1 In de eerste stap willen we een uniek identificatie nummer van de gelduitgave bekomen. M voert daartoe 1 uit en stuurt vervolgens R naar H. uitvoering 1: - bereken R ∈R {0, 1}lH Stap 2 In de tweede stap geeft U een munt (S, R, T, φ) aan M. Hiervoor worden volgende deelstappen uitgevoerd: 52

4.2. Het Voorgestelde Systeem a) T P voert 2a uit en stuurt (B, S, J) naar H uitvoering 2a: - genereer ρ6 ∈R [1..b n4 c] - bereken B = V4u V5ρ6 mod n −1 - bereken S = g 1/(J+s) = g (J+s)

mod q

mod p

b) H voert 2b uit en stuurt (S, T, AJ , B, W1 , .., W4 ) naar M uitvoering 2b: P - bepaal wi voor i = 1..4 zodat 4i=1 wi = J12 − (J − J0 )2 (zie sectie 2.8.1) - genereer ρi ∈R [1..b n4 c] met i = 0..4 −1 - bereken T = pku g R/(J+t) mod p = pku g R((J+t) mod q) mod p wi ρi - bereken Wi = V4 V5 mod n met i = 1...4 - bereken AJ = V4J V5ρ0 mod n

Stap 3 In de derde stap dient H nog φ te berekenen om de munt (S, T, R, φ) compleet te maken. Daartoe voert hij volgende ZKPK uit (hierin is α = u(J + t)): φ = ZKP K{(u, s, t, J, α, W 1, .., W 4, ρ0 , ..., ρ7 ) : Z = QvB V1u V2s V3t deB ∧ AJ = V4J V5ρ0 ∧ g = S (J+s) ∧ Wi = V4wi V5ρi ; i = 1..4 (J12 −J02 )

∧ V4

= (AJ V4−2J0 )J (

4 Y

Wiwi )V5ρ5 }

i=1

∧ B = V4u V5ρ6 ∧ 1 = B J B t V4−α V5ρ7 ∧ g R = T (J+t) g −α 0

∧ u, s, t ∈ {0, 1}lx +lH +lφ ∧ e ∈ [2le −1 , 2le −1 + 2le −1 ]} Voor het uitvoeren van deze ZKPK worden volgende deelstappen gedaan: a) T P voert 3a uit en stuurt vervolgens TZ0 , TB , Tg0 , dB naar H. uitvoering 3a: - genereer ru , rs ∈ {0, 1}lx +lH +lφ , rρ6 ∈ {0, 1}ly +lH +lφ en rvB ∈ {0, 1}le +ln +lφ +1 - genereer r ∈ {0, 1}ln +lφ - bereken vB = v + er en dB = dQ−r mod n zodat (dB , e, vB ) ook een geldig certificaat is, maar geblindeerd - bereken TZ0 = V1ru V2rs QrvB mod n rρ - bereken TB = V4ru V5 6 mod n - bereken Tg0 = S rs mod p

53

4. Anonieme E-Cash voor Computationeel Beperkte Platformen b) H voert 3b uit. Vervolgens wacht hij tot ni ∈R {0, 1}lH ontvangt van M en stuurt dan c0 = H(SC kTC kni ) naar T P. uitvoering 3b: - genereer rt ∈ {0, 1}lx +lH +lφ , re ∈ {0, 1}le +lH +lφ , rJ ∈ {0, 1}l+lH +lφ - genereer rρi ∈ {0, 1}ly +lH +lφ , i = 0..5, 7 - genereer rwj ∈ {0, 1}l+lφ , j = 1..4 rρ - bereken TZ = TZ0 V3rt drBe mod n en TAJ = V4rJ V5 0 mod n - bereken Tg = Tg0 S rJ mod p rw rρ - bereken TWi = V4 i V5 i mod n, i = 1..4 rw rw rρ - bereken T J 2 −J 2 = (AJ V4−2J0 )rJ W1 1 ..W4 4 V5 5 mod n V4 1

-

bereken bereken bereken bereken

0

rρ

T1 = B rJ +rt V4−rα V5 7 mod n TgR = T rJ +rt g −rα mod p SC = QkV1 k...kV5 kdB kgkW1 k...kW4 kAJ kBkT TC = TZ kTAJ kTg kTW1 k...kTW4 kT J 2 −J 2 kT1 kTB kTgR V4 1

0

c) T P voert dan 3c uit en stuurt (c, nt , su , svB , sρ6 ) naar H. uitvoering 3c: - genereer nt ∈ {0, 1}lH - bereken c = H(c0 kSknt ) - bereken su = ru − cu , svB = rvB − cvB - bereken ss = rs − cs, sρ6 = rρ6 − cρ6

d) H voert 3d uit en stuurt (dB , sall , c, nt ) naar M uitvoering 3d - bereken st = rt − ct se = re − ce, sJ = rJ − cJ - bereken sρi = rρi − cρi voor i = 0..5, 7 - bereken swj = rwj − cwj voor j = 1..4 -bereken sα = rα − cα - zet sall = (su , ss , st , svB , se , sJ , sρ0 , ..., sρ7 , sα , sw1 , ..., sw4 )

e) M verifieert de ZK proof door 3e uit te voeren 54

4.2. Het Voorgestelde Systeem uitvoering 3e: - bereken T˜z = V1su V2ss V3st dsBe Z c QsvB mod n sρ - bereken T˜AJ = V4sJ V5 0 AcJ mod n - bereken T˜g = S sJ +ss g c mod p sw sρ - bereken T˜Wi = V4 i V5 i Wic mod n voor i = 1..4 sw sw (J 2 −J 2 )c - bereken T˜ J 2 −J 2 = (AJ V4−2J0 )sJ W1 1 ...W4 4 V5ρ5 V4 1 0 mod n V4 1

-

bereken bereken bereken bereken

0

sρ sρ T˜B = V4su V5 6 B c mod n en T˜1 = B sJ +st V4−sα V5 7 mod n T˜gR = T (sJ +st ) g −sα g Rc mod p S˜C = QkV1 k...kV5 kdB kgkW1 k...kW4 kAJ kBkT T˜c = T˜Z kT˜A kT˜g kT˜W kT˜ J 2 −J 2 kT˜B kT˜1 kT˜gR i

V4 1

0

- controleer c = H(H(S˜c kT˜c kni )kSknt ) - controleer su , ss , st ∈ {0, 1}lx +lH +lφ en se ∈ {0, 1}le +lH +lφ

Stap 4 Als de ZKPK juist is, slaat M in stap 4 volgende zaken op: de munt (S, R, T, φ = (dB , AJ , B, W1 , W2 , ..., W4 , rm )) en de challange c

Stap 5 Tot slot update T P zijn teller als volgt: stel J = J − 1

Geldstorting(M(skM , S, π, pkB ), B(pkM , skB )) Dit algoritme wordt uitgevoerd in twee stappen. Stap 1 M stuurt een munt (S, π) naar B. Stap 2 B voert onderstaande procedure uit: uitvoering 1a: if (S and R niet nieuw zijn){ beschuldig M van de munt dubbel te storten } else if (S niet nieuw is){ - beschuldig de gebruiker van dubbele uitgave van een munt, i.e. de gebruiker heeft een munt (S, R, T, φ) betaald terwijl er in de database van B reeds een munt (Sold , Rold , Told , φold ) is waarvoor Sold = S 55

4. Anonieme E-Cash voor Computationeel Beperkte Platformen uitvoering 1 (vervolg): - ga de gebruiker zijn identiteit na met behulp van het identificatie algoritme } else { - verifieer de ZKPK φ als in 3e - stockeer (S, R, T ) in een database }

Identificatie(S, π1 , π2 ) Gegeven π1 , π2 waarvoor geldt dat S1 = S2 = S en R1 = 6 R2 dan wordt de publieke sleutel van de dubbele uitgever bepaald als: (

4.2.5

T2R1 (R1 −R2 )−1 g uR1 +R1 R2 (J2 +S) (R1 −R2 )−1 ) = ( ) = gu g uR2 +R1 R2 (J1 +S) T1R2

Veiligheidsanalyse

We definiëren de veiligheid van het voorgestelde E-Cash schema volgens het idealewereld/reële-wereld paradigma uitgelegd in sectie 2.5. Voor het E-Cash schema geldt dan onderstaand theorema: Theorema 1: Het voorgestelde E-Cash schema ondersteunt de algoritmes (BKeygen, UKeygen, Withdraw, Spend, Deposit, Identify) en realiseert FASEC onder de ’Strong RSA’ en de ’y-DDHI’ veronderstelling in het random oracle model. Bewijs van theorema 1. In bijlage A wordt een eerste aanzet gegeven om de correctheid van dit theorema na te gaan.

56

Hoofdstuk 5

Gebruikte Tools en Hardware voor de Implementatie van het Voorgestelde E-Cash systeem A good idea is about ten percent, implementation and hard work is the remaining 90 percent. Guy Kawasaki

In dit hoofdstuk richten we ons een eerste keer op de implementatie van het E-Cash systeem dat voorgesteld werd in het vorige hoofdstuk. We bespreken de keuze van hardware voor de partijen, de communicatie tussen hen en de aangewende software tools in respectievelijk sectie 5.1, 5.2 en 5.3. De software implementatie van elk van de partijen wordt verder geanalyseerd in hoofdstuk 6. Bij de bespreking van dit hoofdstuk gebruiken we figuur 5.1 als leidraad. Op de figuur werd voor alle partijen telkens de gekozen hardware module tussen haakjes vermeld. Deze keuze wordt in een eerste sectie gemotiveerd. De keuze van hardware bepaalt natuurlijk ook welke software tools aangewend moeten worden om te kunnen programmeren. Daarom wordt in een tweede sectie voor elk van de partijen vermeld, welke software tools vereist zijn. Tot slot moeten de partijen in staat zijn om met elkaar te communiceren. De gekozen vorm van communicatie werd voor de verschillende partijen met een cijfer aangeduid op figuur 5.1. Deze keuze wordt in de laatste sectie gemotiveerd.

5.1

De Gebruikte Hardware

Het voorgestelde protocol uit sectie 4.2 bevat 4 entiteiten die met elkaar interageren: de host H, het vertrouwde element T P, de verkoper M en de bank B. Voor elk van deze modules bespreken en motiveren we de keuze van hardware. 57

5. Gebruikte Tools en Hardware voor de Implementatie van het Voorgestelde E-Cash systeem

Figuur 5.1: Illustratie van de keuze van hardware en type van communicatie van/tussen de partijen van het voorgestelde E-Cash schema

5.1.1

De Host

Deze entiteit voert alle berekeningen van de gebruiker uit die niet van belang zijn om de veiligheidseigenschappen uit 4.2.2 te garanderen. Het is dus gewenst dat deze module, computationeel krachtig is. Anderzijds moet de module voldoende compact zijn zodat deze meegedragen kan worden door gebruikers. Een smartphone lijkt hiervoor dus de ideale keuze. Vermits bovendien steeds meer gebruikers een smartphone hebben, is het systeem praktisch schaalbaar. We hebben in deze thesis gekozen voor een smartphone die het Android besturingssysteem draait (voortaan een Android phone genoemd). Het grote voordeel van een Android phone is dat deze toestellen toelaten in Java te programmeren en dat er heel veel bibliotheken voor software ontwikkelaars beschikbaar zijn. De hier gebruikte Android phone is een Motorola Milestone met volgende belangrijke eigenschappen: Android versie 2.2, 600 MHz processor en Micro SD kaart slot. De Motorola Milestone ondersteunt echter geen NFC (Near Field Communication).

5.1.2

Het Vertrouwde Element

Het vertrouwde element voert in het ideale geval enkel die berekeningen van de gebruiker uit die nodig zijn om hem te beschermen tegen corrumperingspogingen van 58

5.1. De Gebruikte Hardware

Figuur 5.2: Overzicht van de typische bouwblokken van een Java kaart

andere - kwaadwillige - gebruikers. Een vertrouwd element moet sabotage bestendig zijn, maar moet ook een zo laag mogelijke kost hebben. Het zijn dus typisch kleine, in rekenkracht en geheugen beperkte modules. Als vertrouwd platform maken we in deze thesis gebruik van een Mobile Security Card (MSC) van Giesecke en Devrient. De MSC heeft het formaat van een typische Micro SD kaart, maar bevat naast het standaard flash geheugen ook een ingebedde smartcard chip. De chip is voorzien van de nodige functionaliteit om rechtstreeks Java programma’s (applets) te kunnen draaien. Het is dus mogelijk om de MSC in het Micro SD slot van de Android smartphone te steken en hem te gebruiken als Java kaart (een van Java technologie voorziene smartcard). Figuur 5.2 geeft een overzicht van enkele belangrijke bouwblokken in Java kaarten. Java kaarten hebben meestal een 8, 16 en soms 32 bit CPU (Central Processing Unit) met kloksnelheid tot 40 MHz. De CPU communiceert met drie types van geheugen: 1. ROM (Read Only Memory) geheugen. Het ROM geheugen is typisch tussen 32 en 64 KB groot. In dit geheugen wordt onder andere het besturingssysteem van de kaart, de Java Card API en de Java virtuele machine opgeslagen. 2. EEPROM (Electrically Erasable Programmable Read-Only Memory). Het EEPROM geheugen is typisch tussen 30 en 70 KB groot (bij onze kaart 72 KB). Het EEPROM geheugen wordt gebruikt om niet vluchtige data op te slaan (de code van applets, persistente objecten (Java Card heap), referentie tabel naar de objecten, ...). Het schrijven naar EEPROM moet vermeden worden daar waar mogelijk: het gaat immers traag en EEPROM heeft een beperkte herschrijfbaarheid. 3. RAM (Random Acces Memory). Het vluchtige RAM geheugen wordt als werkgeheugen gebruikt en is typisch 1 tot 4 KB groot (bij onze kaart 1,4 KB). Het schrijven naar RAM gaat tot 1000 keer sneller dan naar EEPROM en het aantal schrijfacties naar het geheugen is niet gelimiteerd. In het RAM geheugen 59

5. Gebruikte Tools en Hardware voor de Implementatie van het Voorgestelde E-Cash systeem bevindt zich enerzijds de Java Card Stack en anderzijds zijn er twee types RAM geheugen waar een programmeur toegang toe heeft: ‘clear on reset’ RAM (COR RAM) en ‘clear on deselect’ RAM (COD RAM). Het COD RAM geheugen behoudt zijn data gedurende een volledige kaart sessie (i.e., tot wanneer de kaart niet meer van stroom voorzien wordt). Het COD RAM geheugen wordt leeggemaakt telkens wanneer een andere applet op de kaart geselecteerd wordt en de huidige applet gedeselecteerd wordt. Door de beperkte beschikbaarheid van RAM geheugen wordt de indeling in COD/COR RAM geheugen op een efficiënte manier gedaan (zie figuur 5.3). Het totale beschikbare RAM geheugen wordt in twee delen opgesplitst die naar elkaar toe groeien. Het COR groeit van boven naar beneden en wordt steeds globaal over alle applets gereserveerd. Wilt applet 2 op figuur 5.3 COR RAM gebruiken, dan wordt de gewenste hoeveelheid RAM gereserveerd startende van de eerste niet gereserveerde positie in RAM. In tegenstelling tot het COR groeit het COD van onder naar boven en wordt het niet globaal gereserveerd over de applets. Wilt een applet COD gebruiken, dan wordt het de gewenste hoeveelheid toegekend, startende vanaf de onderste RAM positie. De Java Runtime Environment moet ervoor zorgen dat deze twee ruimtes elkaar niet overlappen. Twee andere bouwblokken van Java kaarten die we hier willen vermelden zijn de cryptografische co-processor en een random nummer generator. Deze zijn nodig om efficiënt cryptografische primitieven zoals RSA encrypties, hash functies uit te voeren. De in deze thesis gebruikte MSC van Giesecke en Devrient is voorzover wij weten, de enige smartcard in Micro SD formaat die kan gebruikt worden in combinatie met een Android phone. Bij de keuze van de hardware voor het vertouwde element hadden we dus weinig keuze. Dat is spijtig omwille van verschillende zaken. Ten eerste is het geweten dat Java Card platformen geen mogelijkheid bieden tot laag-niveau programmeren om code optimalisaties te doen en dat de Java virtuele machine heel wat overhead veroorzaakt. Zoals in hoofdstuk 6 wordt uitgelegd steunen complexe cryptografische algoritmes bovendien zeer sterk op de cryptografische co-processor waar een ontwikkelaar enkel toegang toe heeft via een API. Tenslotte is het ook geweten dat Java kaarten die dezelfde API implementeren maar afkomstig zijn van verschillende fabrikanten, kunnen verschillen in responsie tijden. Als er dus een snellere Java kaart bestaat, maar dat is geen G&D Java kaart, dan kunnen we die momenteel niet gebruiken.

5.1.3

De Verkoper en de Bank

De doelstellingen van deze thesis waren in de eerste plaats gericht op het zo efficiënt mogelijk uitvoeren van de berekeningen van de gebruiker. Daarom werden de bank en de verkoper slechts in die mate geïmplementeerd dat ze de nodige stimuli leverden aan de host en het vertrouwde element. Er werd dan ook geen specifieke hardware toegekend aan deze modules, maar ze worden gewoon uitgevoerd op een standaard computer. In principe hebben beide entiteiten bovendien ook een vertrouwd element 60

5.2. De Gebruikte Software Tools

Figuur 5.3: Weergave van hoe het RAM geheugen efficiënt wordt ingedeeld in ‘clear on reset’ en ‘clear on deselect’ geheugen. De figuur geeft ook weer hoe verschillende applets in EEPROM van dit geheugen gebruik maken.

nodig om hen te beschermen tegen corruptie door anderen. Ook deze vereiste lieten we hier achterwege. Reële implementaties die ook de verkoper en bank volledig implementeren, moeten natuurlijk wel speciale hardware en een vertrouwd element gebruiken.

5.2

De Gebruikte Software Tools

In deze sectie overlopen we voor alle entiteiten van het protocol de gebruikte software tools voor het implementeren, testen en genereren van code.

5.2.1

Software Tools voor Alle Partijen

Vermits alle hardware modules geprogrammeerd zullen worden in Java, gebruiken we Eclipse als IDE (Integrated Development Environment). Enerzijds laat Eclipse toe om eenvoudig en overzichtelijk Java code te kunnen schrijven. Anderzijds biedt Eclipse ondersteuning voor het gebruik van verschillende Software Development Kits (SDK’s). Daardoor kan vanuit Eclipse op een efficiënte manier software geschreven worden die specifiek bedoeld is voor een bepaald besturingssysteem of type hardware. 61

5. Gebruikte Tools en Hardware voor de Implementatie van het Voorgestelde E-Cash systeem

5.2.2

Software Tools voor de Host

Voor het schrijven van Java programma’s op de Android phone wordt gebruik gemaakt van de Android SDK [38]. De SDK biedt tools en API’s om het schrijven van Java programma’s mogelijk te maken. Om deze SDK vanuit Eclipse te kunnen gebruiken, dient de ADT plugin [39] van Eclipse geïnstalleerd te worden. Een goede introductie in het schrijven van Java programma’s op een Android phone, wordt gegeven in [40]. Voor het testen van Android applicaties voorziet de Android SDK twee methodes: testen en debuggen van de code op een virtuele emulator of USB debuggen met een echte GSM. Uiteraard is de tweede methode hierbij aangewezen. Eens de code geschreven en getest is, dient deze op de smartphone geladen te worden. Ook hierbij biedt Eclipse ondersteuning. Via Eclipse kan een project geëxporteerd worden als een .apk bestand. Door gebruik te maken van de adb-tool uit de Android SDK, kan dit .apk bestand vervolgens op de smartphone geladen worden. Tot slot vermelden we nog enkele belangrijke klassen uit de Java API die belangrijk zullen zijn voor het uitvoeren van cryptografische berekeningen. De BigInteger klasse wordt gebruikt om allerhande (modulo)operaties uit te voeren op getallen met zeer grote bitlengte. De MessageDigest klasse laat toe om hash functies te berekenen op basis van welgekende standaarden zoals SHA-1, RIPEMD-160,.. De Random klasse wordt gebruikt voor het genereren van cryptografisch veilige random getallen.

5.2.3

Software Tools voor het Vertrouwde Element

Voor het schrijven van Java programma’s op de Java kaart wordt gebruik gemaakt van de Java Card Software Development Kit 2.2.1 [41]. Deze SDK bevat enerzijds tools voor het genereren en testen van applets. Anderzijds bevat het ook een Java API die aan Java kaarten aangepast is. Om deze Java Card SDK in Eclipse te kunnen gebruiken, dient de Java Card Eclipse plugin geïnstalleerd te worden zoals beschreven in [42]. Het is belangrijk op te merken dat het Java platform dat voor Java kaarten gebruikt wordt (de Java Card editie), sterk afgezwakt is in functionaliteit tegenover het standaard Java platform (de Java Standard editie). Dit is natuurlijk te wijten aan de gelimiteerde rekenkracht van Java kaarten. Tabel 5.1 illustreert welke belangrijke concepten uit de Java Standard editie wel en welke niet ondersteund worden in de Java Card editie. Tabel 5.2 illustreert vier van de zes pakketten van de Java Card API. Deze tabel maakt duidelijk dat het om een sterk afgezwakt versie van de standaard Java API gaat. Anderzijds zijn er ook drie pakketten speciaal ontwikkeld voor het Java Card platform: javacard.framework, javacard.security en javacardx.crypto. Op 62

5.2. De Gebruikte Software Tools Ondersteund - Drie primitieve types: short, byte, boolean - Eéndimensionale arrays - Bepaalde object georiënteerde concepten: pakketten, klassen, overerving, exeptions.

Niet ondersteund - De andere primitieve types zoals: int, long, double, .. - Garbage collection, multi-threading - Zo goed alle klassen uit de Standaard Java API: BigInteger, ..

Tabel 5.1: Illustratie van welke voor ons belangrijke concepten uit de Java Standard editie wel en welke niet ondersteund worden in de Java Card editie.

de functionaliteit van enkele klassen uit het javacard.framework gaan we in sectie 5.3 dieper in. De functionaliteit van de javacard.security en javacardx.crypto pakketten wordt in hoofdstuk 6 besproken.

63

5. Gebruikte Tools en Hardware voor de Implementatie van het Voorgestelde E-Cash systeem Java.lang

Java Card 2.2.1 API Dit pakket voorziet die klassen die fundamenteel zijn voor het bouwen van de Java Card technologie. Belangrijke klassen in het pakket zijn de klasse Object en 10 mogelijke exceptions die opgeroepen kunnen worden.

javacard.framework

Dit pakket voorziet een framework van klassen die gebruikt kunnen worden voor het bouwen en communiceren met Java Card applets. Belangrijke klassen zijn : APDU, ISO7816, OwnerPIN, JCSystem. De eerste twee worden uitgelegd in sectie 5.3. Voor functie van de laatste twee verwijzen we naar [43].

javacard.security en javacardx.crypto

Deze pakketten bevatten klassen en interfaces die toelaten om applets te bouwen die gebruik maken van cryptografische primitieven. De primitieven die wij zullen gebruiken zijn: a) SHA-1 hash functies (met behulp van de MessageDigest klasse), b) symmetrische (AES,3DES) en asymmetrische (RSA) vercijfering met behulp van de Cipher klasse, c) random nummer generatie met behulp van de Random klasse. Op het gebruik van beide pakketten wordt uitvoerig teruggekomen in hoofdstuk 6

Tabel 5.2: Illustratie van de belangrijke pakketten uit de Java Card editie.

Voor het testen van Java kaart applicaties zijn er ook hier twee methodes. Enerzijds kan er gebruik gemaakt worden van een simulator in de SDK om de applets in debug mode uit te voeren. Het nadeel van deze methode is dat heel wat cryptografische algoritmes niet of slechts gedeeltelijk ondersteund worden (bv RSA sleutels zijn slechts beperkt tot 512 bits). De tweede methode bestaat erin om eerst een hele reeks controle methodes in de te testen applet in te bouwen, de applet vervolgens op de smartcard te laden en tot slot de output van de controle methodes na te gaan. Het nagaan van de output van methodes op de Java kaart kan eenvoudig gebeuren aan de hand van de JLoad tool van Giesecke en Devrient [44]. Deze tool draait op een computer en kan commando’s sturen en antwoorden ontvangen van smartcards die via USB verbonden zijn met de pc. Het nadeel van deze methode is dat elke nieuwe reeks testen opnieuw in EEPROM geladen moet worden waardoor er schrijf cycli van het EEPROM verloren gaan aan de testen. In deze thesis hebben we van beide methoden gebruik gemaakt: de eerste methode in de vroegere fase van de 64

5.3. De Communicatie tussen de Entiteiten implementatie, de tweede in een latere fase. Onnodige schrijfcycli werden hierdoor vermeden. Het opladen van Java applets op de smartcard gebeurt als volgt. Eerst moet er van het project een .cap bestand gemaakt worden. Dit kan gedaan worden aan de hand van de JAVA Card SDK plugin voor Eclipse. Het .cap bestand kan vervolgens in het EEPROM van de Java kaart geplaatst worden door gebruik te maken van de JLoad tool van Giesecke en Devrient.

5.2.4

Software Tools voor de Verkoper en de Bank

De bank en verkoper voeren uit op een gewone computer vermits hun functionaliteit bewust beperkt gehouden werd. De software tools die vereist zijn voor het implenteren van deze functionaliteit is standaard in Eclipse ingebouwd.

5.3

De Communicatie tussen de Entiteiten

In deze thesis hadden we enerzijds als doelstelling om na te gaan in welke mate het gebruikersdeel van het voorgestelde E-Cash systeem realiseerbaar is op realistische hardware. Anderzijds hadden we als doelstelling om de interface tussen enerzijds de gebruiker en de verkoper/bank en anders tussen de host en het vertouwde element te analyseren. Aan de interface tussen de twee andere partijen van het E-Cash systeem (de bank en de verkoper) gaven we geen aandacht vermits dit niet relevant was voor het onderzoek van deze thesis. We analyseren hieronder dus enkel de twee interfaces die wel relevant voor ons waren.

5.3.1

Communicatie tussen de Host en het Vertrouwd Element

Als de Mobile Security Card in het SD kaartslot van de Android phone gestoken wordt, kan de MSC gebruikt worden als Java kaart. De communicatie tussen de SD kaartlezer van de Android phone en de Java kaart gebeurt dan zoals beschreven in de ISO 7816-3,4 standaarden [45], [46] en verloopt als volgt: De communicatie gebeurt in master-slave configuratie: de smartcard fungeert als slave, de partij verbonden met de smartcard reader fungeert als master. Master en slave zenden tijdens de communicatie Application Protocol Data Units (APDU’s) naar elkaar volgens een request-response structuur. Hierbij stuurt de master altijd eerst een command-APDU (c-APDU) waarop de slave kan antwoorden met een response-APDU (r-APDU). Het formaat van een c-APDU wordt getoond in tabel 5.3, dat van een r-APDU in tabel 5.4. Verplichte header (4 bytes) CLA INS P1 P2

Optionele body (max. 255 bytes data) Lc Data Le

Tabel 5.3: Illustratie van de structuur van een c-APDU. 65

5. Gebruikte Tools en Hardware voor de Implementatie van het Voorgestelde E-Cash systeem Optionele body (max. 255 bytes data) Data

Verplichte trailer (2 bytes) SW1 SW2

Tabel 5.4: Illustratie van de structuur van een r-APDU.

Een c-APDU kan uit volgende velden bestaan (de eerste 4 zijn verplicht): • CLA (1 byte). Dit veld duidt aan tot welke klasse van instructies de c-APDU behoort. In [46] worden alle klasses vermeld. De gebruikers gedefinieerde klassen (die voor ons belangrijk zijn) zijn bijvoorbeeld 0x80 of 0x90. • INS (1 byte). De INS byte laat toe om instructies binnen een bepaalde klasse van instructies van elkaar te kunnen onderscheiden. • P1 en P2 (elk 1 byte). Kunnen gebruikt worden als parameters in instructies • Lc (1 byte). The length of the data field. • Data (maximum 255 byte). Kan data bevatten die gebruikt wordt door de opgeroepen instructie • Le (1 byte). Geeft de bitlengte weer van het verwachte antwoord. Een r-APDU bestaat uit volgende velden (enkel de laatste twee zijn verplicht): • Data (maximum 255 byte). Kan de output data bevatten die verkregen wordt door het uitvoeren van een instructie. • SW1 en SW2 (elk 1 byte). De concatenatie SW1||SW2 geeft weer wat het status woord is van de instructie. In [46] worden alle mogelijke status woorden opgesomd waarbij ‘9000’ (instructie correct uitgevoerd) de belangrijkste is. APDU’s worden verzonden als Transmission Protocol Data Units (TPDU’s). Het protocol dat hiervoor gebruikt wordt hangt af van de interface. Voor een interface waarbij er contact is tussen smartcard en smartcard reader, wordt het T=0 of T=1 protocol gebruikt zoals gedefinieerd in ISO 7816-3 [45]. Indien er een contactloze interface is tussen smartcard en reader, dan wordt het T=CL protocol gebruikt dat gedefinieerd wordt in ISO 14443-4 [47]. Het protocol dat gebruikt wordt bij het versturen van APDU’s wordt echter altijd verborgen gehouden voor software ontwikkelaars. Het is belangrijk op te merken dat een Android phone niet zomaar elk type van Java kaart kan lezen via zijn SD kaartlezer. Op het moment van schrijven zijn enkel Mobile Security Cards van Giesecke en Devrient ondersteund [48]. Om te kunnen communiceren met de Giesecke en Devrient MSC, moeten software ontwikkelaars in hun Android applicaties de ‘org.simalliance.openmobileapi.jar’ importeren en hun Android phone gebruiksklaar maken zoals beschreven in [48]. 66

5.3. De Communicatie tussen de Entiteiten

Figuur 5.4: NFC in vergelijking met andere draadloze technologieën.

5.3.2

Communicatie tussen Gebruiker en Bank/Verkoper

De communicatie tussen de gebruiker en de bank/verkoper gebeurt in het ideale geval met een laag vermogen draadloze technologie die een zeer kleine reikwijdte, maar toch een voldoende hoge data rate heeft. Near Field Communication lijkt hiervoor de perfecte technologie. We introduceren hieronder eerst kort NFC en geven extra aandacht aan de kaart emulatie mode. Near Field Communication. NFC is een draadloze technologie die toelaat om met andere nabijgelegen toestellen die NFC ondersteunen te communiceren. Zoals figuur 5.4 weergeeft, is de NFC technologie niet bedoeld als vervanging voor andere draadloze technologieën zoals Bluetooth of WIFI. NFC is namelijk bedoeld als laag vermogen draadloze technologie die gebruikt kan worden in applicaties met beperkte datasnelheden en waar de verschillende partijen over een zeer korte afstand met elkaar communiceren. De belangrijkste specificaties die een NFC verbinding karakteriseren zijn: • Methode van communicatie: reactieve nabije-veld magnetische koppeling op 13.56 MHz. • Praktische werkafstand: 4 cm • Datasnelheiden: tot 424 kbits/s Zoals in [49] wordt aangegeven kan een NFC ondersteunend toestel opereren in drie modes: 1. Proximity Coupling Device (PCD) mode: Als een NFC ondersteunend toestel in deze mode opereert, dan is het tot twee acties in staat. Enerzijds kan het dan speciaal ontwikkelde NFC tags lezen. Een gebruiker kan zijn 67

5. Gebruikte Tools en Hardware voor de Implementatie van het Voorgestelde E-Cash systeem

Figuur 5.5: Illustratie van hoe we van de MSC gebruik kunnen maken om contactloos met de host te communiceren.

smartphone tegen zo’n tag houden en de informatie die opgeslagen is in de tag verkrijgen. Anderzijds kan het toestel in deze mode communiceren met contactloze smartcards (via het T=CL protocol van ISO 14443). 2. Proximity Inductive Coupling Card (PICC) mode: Als het NFC toestel in deze mode opereert, dan fungeert het als de PICC van ISO 14443 [47] (i.e. het fungeert als een contactloze smartcard). Deze mode zorgt er dus voor dat een NFC ondersteunend toestel, compatibel is met de contactloze smartcard infrastructuur en dus gebruikt kan worden in betalingsapplicaties. 3. NFC mode. In deze mode kan een NFC ondersteunend toestel communiceren met een ander toestel dat NFC ondersteunt. Dit is handig voor een heel aantal applicaties zoals het delen van telefoonnummers, Bluetooth pairing,..

De Android phone die in deze thesis gebruikt wordt is echter niet NFC compatibel. Daarenboven is er tot nog toe geen enkele smartphone verkrijgbaar die zowel een Micro SD kaartslot heeft én van NFC voorzien is. We kunnen dus niet gebruik maken van de NFC technologie voor de communicatie tussen gebruiker en verkoper/bank.

68

5.3. De Communicatie tussen de Entiteiten Aangezien de Mobile Security Card die we als vertrouwd element gebruiken, een contactloze interface heeft (en dus het T = CL protocol van ISO 14443 ondersteunt), kunnen we wel te werk gaan als in figuur 5.5. Alle boodschappen die van de bank/verkoper naar de host gestuurd moeten worden, kunnen we eerst via APDU’s over de contactloze interface tussen MSC en verkoper/bank sturen. Daarna kan de host de boodschappen verkrijgen door hiervoor een APDU over de contact interface naar het vertrouwde element te sturen. Hoewel deze methode theoretisch perfect werkt, werkt ze in de praktijk niet. De reden daarvoor is dat de contactloze MSC die we gebruiken, niet toelaat om gelijktijdig een kanaal te openen met de verkoper/bank over de contactloze interface en met de host over de contact interface. Het gevolg is dus dat we omwille van gebrek aan gepaste hardware, de communicatie niet via NFC kunnen doen. Zoals geïllustreerd in figuur 5.4 zien we dat de volgende kandidaat technologie die het best bij onze vereisten past, Bluetooth is. Daarom dat er voorgesteld wordt om de communicatie tussen de gebruiker en bank/verkoper over Bluetooth te laten verlopen. Bluetooth is net als NFC een draadloze communicatie technologie die in de 2,4 GHz band, data communicatie op korte afstand (tot 30 meter) mogelijk maakt. Omdat Bluetooth ook weinig stroom verbruikt wordt het veelvuldig gebruikt in mobiele apparaten. Een eerste nadeel van Bluetooth in ons schema ligt in de gebruiksvriendelijk ervan. Gebruikers moeten voor ze een connectie kunnen opzetten manueel aanduiden met welke partij ze willen communiceren. Daarnaast is het al in verschillende gevallen aangetoond dat als een Bluetooth-apparaat niet voldoende beveiligd wordt, dat het dan gevoelig is voor aanvallen als bluejacking, bluesnarfing en bluesmacking. Het gevaar tot dergelijke aanvallen is bij het gebruik van NFC als communicatie middel veel kleiner omdat daar de range van afstand waarin communicatie mogelijk is, beperkt is tot vijf centimeter.

69

Hoofdstuk 6

De Implementatie van het Voorgestelde E-Cash systeem There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies. The other way is to make it so complicated that there are no obvious deficiencies. Antony Hoare

In dit hoofdstuk analyseren we de implementatie van het voorgestelde E-Cash systeem in detail. We concentreren ons hierbij vooral op de host en op het vertrouwde element. Deze aanpak is gekozen omdat het hoofddoel van de thesis was om de uitvoeringstijd van de gebruiker bij het afhalen en uitgeven van geld te optimaliseren. De implementatie problemen zijn namelijk hoofdzakelijk gerelateerd aan de inherente computationele en geheugen beperkingen van de hardware die de gebruiker nodig heeft bij het uitvoeren van betalingen. De verkoper en bank werden hierbij slechts in die mate geïmplementeerd dat ze de nodige stimuli voor de host en het vertrouwde element leveren. De structuur die we gebruiken bij de bespreking is als volgt: Sectie 6.1 beschrijft het principeschema van de implementatie van de gebruiker gevolgd door de behandeling van achtereenvolgens de implementatie van het vertrouwde element en van de host in respectievelijk sectie 6.2 en sectie 6.3. Sectie 6.4 beschrijft vervolgens zeer beknopt de gedeeltelijke implementatie van zowel de verkoper als de bank. In sectie 6.5 wordt tenslotte de realiseerbaarheid van de voorgestelde oplossing besproken. Deze sectie is dus het sluitstuk van deze thesis en zal leiden tot de eindconclusie. 71

6. De Implementatie van het Voorgestelde E-Cash systeem

6.1

Principe Schema van de Implementatie van de Gebruiker

Figuur 6.1: Illustratie van het principeschema van de implementatie van de gebruiker.

In figuur 6.1 wordt het principeschema van de implementatie van de gebruiker weergegeven, met vermelding van de geïmplementeerde klassen voor de host en het vertrouwde element. De overeenstemmende methode beschrijving (Javadoc) van deze klassen wordt in bijlage C en D bijgevoegd. In bijlage E wordt met een voorbeeld de interface tussen de host en het vertrouwde element verduidelijkt. We geven daarbij aan de hand van het geldafhalingsprotocol, een overzicht van de APDU’s die tussen beide modules verstuurd worden.

6.2

Analyse van de Implementatie van het Vertrouwde Element

Een belangrijk resultaat van deze thesis is dat we erin geslaagd zijn om alle berekeningen die het vertrouwde element moet uitvoeren bij betalingstransacties (gelduitgave/geldafhaling) te implementeren op de Java kaart. We hebben hierbij zo goed mogelijk rekening gehouden met de inherente beperkingen van Java kaarten. We overlopen hieronder alle belangrijke beslissingen die we genomen hebben tijdens de 72

6.2. Analyse van de Implementatie van het Vertrouwde Element implementatie. We doen dit door achtereenvolgens alle implementatie-gerelateerde bevindingen op te sommen. Elke bevinding wordt via een probleemstelling afgelijnd en per bevinding wordt een oplossing voorgesteld. Op basis van deze bespreking zal ook duidelijk worden wat het nut is van de verschillende klassen uit het klassendiagram in figuur 6.2.

Figuur 6.2: Het klassendiagram gebruikt bij het programmeren van de Java kaart. AsecEngine is de hoofdklasse en bevat alle functionaliteit voor het uitvoeren van het geldafhaling en gelduitgave protocol. Om tot een handelbare implementatie te komen, maakt AsecEngine gebruik van de klasse UnsignedBigNumber en Nist931PRNG. In het algemeen vragen drie belangrijke bevindingen een oplossing of een methode om de impact van het bijhorende probleem te verminderen: • Het programmeren op een Java kaart impliceert dat er zeer strikte geheugen vereisten zijn op gebied van hoeveelheid geheugen en limitaties in het aantal schrijfacties op EEPROM. • In het te implementeren E-Cash schema is het nodig dat er bewerkingen worden uitgevoerd op getallen met bitlengtes in de grootteorde van 1024 bit. Er moet hier ondersteuning voor zijn. • De Java kaart is zeer beperkt in rekenkracht. Er moet rekening gehouden worden met bepaalde zaken waar een programmeur die op het standaard Java platform programmeert geen rekening mee moet houden. Elk van deze bevindingen wordt nu in detail behandeld.

BEVINDING 1: Een Java Kaart Heeft Strikte Geheugenvereisten PROBLEEMSTELLING. Het vertrouwde element is een module die zeer strikte geheugenvereisten heeft. Enerzijds is het beschikbare RAM en EEPROM geheugen beperkt tot 1,4 KB, respectievelijk 72 KB. Anderzijds moet ervoor gezorgd worden dat er zo weinig mogelijk in EEPROM gewerkt. Het aantal schrijf acties naar dat geheugen is namelijk 73

6. De Implementatie van het Voorgestelde E-Cash systeem beperkt en elke schrijf actie verloopt tot 1000 keer trager dan het schrijven naar RAM. GEKOZEN OPLOSSINGEN. a. Het besparen van EEPROM en RAM geheugen. Om zo zuinig mogelijk met het beschikbare EEPROM en RAM geheugen om te springen, werden drie optimalisaties bedacht: Een eerste optimalisatie is om in beide types van geheugen één grote byte array te creëren waarin we dan werken (berekeningen doen, zaken tijdelijk/permanent opslaan, · · · ). Door op deze manier te werk te gaan sparen we heel wat overhead uit. In Java wordt aan elk object een header toegevoegd die als informatie gebruikt wordt door de Java Runtime Environment. Voor standaard Java objecten is deze header 6 bytes, voor arrays van primitieve types is dit 8 bytes. In ons protocol hebben we nu heel wat elementen die 1024 bit (of 128 byte) groot zijn. Als we voor elk van deze elementen een aparte byte array aanmaken dan introduceert elke byte array ongebruikte overhead. Plaatsen we deze elementen echter op een vaste plaats in een enkele grote array, dan hebben we slechts 1 maal de overhead. De tweede optimalisatie is gebaseerd op het feit dat de Java kaart geen garbage collector heeft (zie sectie 5.2.3). Om dus geen geheugen te verspillen is het belangrijk om nooit de link naar oude objecten te verliezen en deze objecten te hergebruiken. Een object dat onbereikbaar geworden is, blijft namelijk altijd geheugen verbruiken (totdat de applet verwijderd wordt). Merk wel op dat lokale variabelen hier een uitzondering op vormen vermits ze aangemaakt worden op de Java Card Stack die zich in RAM geheugen bevindt. Een derde mogelijke optimalisatie is erop gericht om de beschikbare hoeveel RAM geheugen uit te breiden met 255 byte. Zoals in sectie 5.3.1 werd uitgelegd worden APDU’s gebruikt voor de communicatie tussen een smartcard reader en een smartcard. Hierbij gebruiken de APDU’s een buffer van 255 bytes die globaal gebruikt wordt door de Java kaart en die zich in RAM bevindt. Om over extra RAM geheugen te beschikken kunnen we dus gebruik maken van deze buffer. Het grote gevaar van deze methode is dat de buffer gelezen of gewijzigd kan worden door andere applets op de Java kaart. Het is dus belangrijk dat indien we de buffer als RAM uitbreiding gebruiken, dat we er geen gevoelige data in plaatsen. b. Het beperken van de schrijf acties naar EEPROM. Om het aantal schrijfacties naar EEPROM te verminderen nemen we twee maatregelen: Ten eerste plaatsen we enkel persistente objecten in EEPROM. Berekeningen worden altijd in RAM gedaan en ook tussentijdse resultaten worden daar tijdelijk in opgeslagen. Een tweede belangrijke maatregel heeft te maken met het gebruik van random getallen. In ons E-Cash systeem hebben we heel wat random variabelen nodig. 74

6.2. Analyse van de Implementatie van het Vertrouwde Element Vermits elk van deze random getallen tijdens het uitvoeren van het protocol meermaals gebruikt worden, moet hun waarde ergens bijgehouden worden. Het opslaan van deze random variabelen in EEPROM gaat in tegen de eerste maatregel van hierboven. Het tijdelijk bijhouden van de random variabelen in RAM is onmogelijk vermits het RAM geheugen hiervoor te klein is. Een mogelijke oplossing hiervoor maakt gebruik van twee observaties over het gebruik van random getallen in ons schema: 1) random getallen worden pas hergebruikt wanneer het laatste nieuwe random getal gegenereerd werd en 2) de random getallen worden hergebruikt in dezelfde volgorde als waarin ze aangemaakt werden. We kunnen er dan als volgt voor zorgen dat random variabelen herbruikbaar zijn: In het begin van elke uitvoering van het geldafhaling of het gelduitgave protocol, initialiseren we de PRNG met een nieuwe seed. Telkens we een nieuw random getal nodig hebben, maken we gebruik van de PRNG. Zijn alle te gebruiken random getallen een eerste keer gegenereerd, dan herinitialiseren we de PRNG met dezelfde seed als waarmee hij de vorige maal geïnitialiseerd werd. Dit laat toe om de random getallen te regenereren in dezelfde volgorde als waarin ze de eerste keer aangemaakt werden. Met deze oplossingsmethode is het dus mogelijk om random getallen aan te maken wanneer ze nodig zijn in het E-Cash schema en is enkel de opslag van de gebruikte seed vereist. De oplossing vereist natuurlijk wel dat we een PRNG hebben die met dezelfde seed steeds dezelfde output sequentie genereert. De klasse Random uit de Java Card 2.2.1 API kan daarom niet gebruikt worden. In de specificatie van deze API staat namelijk dat het genereren van een random variabele, zelfs als dezelfde seed gebruikt wordt, andere resultaten oplevert. We zijn dus genoodzaakt om zelf een PRNG te implementeren die wel het gebruik van onze methode toelaat. De PRNG die we kozen is de NIST-Recommanded X9.31 PRNG [50] weergegeven in figuur 6.3. Deze PRNG bestaat uit vier 16 byte velden v, ctn, r, i. Hierbij vormen v en ctn de seed, is i een tussenresultaat en wordt r zowel als output en als tussenresultaat gebruikt. De NIST X9.31 PRNG gebruikt verder een blokcijfer EK () dat geïnitialiseerd wordt met de sleutel K. Als blokcijfer worden zowel AES als 3DES voorgesteld. De werking van de PRNG is als volgt: vooraleer het eerste random getal aangemaakt wordt, wordt de seed (de velden ctn en v) geïnitialiseerd op een random waarde. Vervolgens worden er per te genereren random getal, een aantal iteraties uitgevoerd. Bij elke iteratie gebeuren onderstaande berekeningen. i = EK (ctn) r = EK (i ⊕ v) v = EK (r + i) ctn = ctn + 1 Op het einde van een iteratie wordt r (16 byte) als tussentijdse output genomen. Het gewenste random getal wordt dan gevormd op basis van deze tussentijdse outputs r. Het aantal iteraties dat uitgevoerd moet worden is afhankelijk van de x bitlengte x van het te genereren random getal. Er worden steeds d 128 e iteraties uitgevoerd waarbij r telkens 16 bytes als output geeft. Als de gevraagde bitlengte dus geen veelvoud is van 128, dan worden teveel bits gegenereerd door de PRNG 75

6. De Implementatie van het Voorgestelde E-Cash systeem

Figuur 6.3: De NIST-recommanded X9.31 pseudo random nummer generator.

die dan gewoon weggelaten worden. Voor de implementatie van de functionaliteit van deze X9.31 PRNG hebben we de klasse Nist931PRNG klasse aangemaakt (zie figuur 6.2). In onze implementatie maken we voor het blokcijfer gebruik van AES met 256 bit sleutel en 128 bit blokken. Voor het instellen van de seed maken we gebruik van de Random klasse uit de Java Card API. BEVINDING 2: Bewerkingen Op Grote Getallen PROBLEEMSTELLING. In het E-Cash systeem wordt er gewerkt met getallen met zeer grote bitlengtes (in de grootte orde van 1024 bit). Op deze getallen worden heel wat bewerkingen uitgevoerd: (modulaire) optellingen, (modulaire) aftrekkingen, (modulaire) vermenigvuldigingen, modulaire machtsverheffingen en modulaire multi-base machtsverheffingen. De Java kaart die wij gebruiken voldoet aan de Java Card 2.2.1 standaard en in de bijhorende Java API is er geen ondersteuning voor operaties op grote getallen. We zijn dus genoodzaakt deze operaties zelf te implementeren. † . VOORGESTELDE OPLOSSINGEN. Om alle gewenste operaties op getallen te kunnen uitvoeren, hebben we een UnsignedBigNumber klasse aangemaakt (zie figuur 6.2). Objecten van deze klasse komen overeen met een positief getal dat een willekeurige grootte van bitlengte kan hebben en dat gebruikt kan worden in alle mogelijke operaties. Bij het aanmaken †

De Java Card 2.2.2 en 3.0 standaarden voorzien beperkte ondersteuning voor het uitvoeren van operaties op grote getallen: er is ondersteuning voor optellingen, aftrekkingen en vermenigvuldigingen van grote getallen.

76

6.2. Analyse van de Implementatie van het Vertrouwde Element van een UnsignedBigNumber object, kan de ontwikkelaar kiezen of hij het nummer wilt aanmaken in RAM of in EEPROM. Zoals in de vorige bevinding uitgelegd werd, moeten persistente nummers (zoals publieke sleutels) aangemaakt worden in EEPROM en nummers die gebruikt worden als tussentijdse resultaten in RAM. We bespreken nu voor elk van de operaties die op grote getallen uitgevoerd kunnen worden, de gemaakte keuzes; a. (modulaire) optellingen en (modulaire) aftrekkingen Voor het implementeren van optellingen en aftrekkingen maakten we gebruik van de ‘potlood en papier’ algoritmes gegeven in [4]. De Java pseudo code van beide algoritmes wordt gegeven door algoritme 4 respectievelijk algoritme 5 in bijlage B. Willen we modulaire optellingen en aftrekkingen uitvoeren, dan gebruiken we algoritme 6 respectievelijk algoritme 7 uit bijlage B. Zowel de gewone als de modulaire optellingen en aftrekkingen worden dus volledig in software uitgevoerd zonder gebruik te maken van de cryptografische co-processor. Zoals in sectie 6.5 aangetoond wordt, is de performantie van deze algoritmes daarom vrij laag. Indien we als software ontwikkelaar toch toegang tot de cryptografische processor zouden hebben, dan kan de performantie van deze methodes in grote mate verbeterd worden. Om deze reden werd in de Java Card 2.2.2 standaard het optellen en aftrekken van grote getallen mogelijk gemaakt via een API oproep. Modulaire berekeningen worden wel nog niet ondersteund. b. modulaire machtsverheffingen Om modulaire machtsverheffingen uit te voeren, worden software ontwikkelaars bijgestaan door de Java Card API. Inderdaad, de Java Card API laat toe om RSA encrypties van de vorm me mod n te berekenen op de cryptografische co-processor. Vermits de gebruiker zelf de waarden van n, m en e kan instellen, kunnen we van deze functionaliteit gebruik maken voor het berekenen van modulaire machtsverheffingen. Er zijn wel voorwaarden verbonden aan het gebruik van de methode: • n moet steeds het product zijn van twee priemgetallen en moet één van volgende toegelaten bitlengtes hebben: 512, 736, 768, 896, 1024, 1280, 1536, 1984 of 2048. Hieronder noteren we de bitlengte van n steeds als |n|. • Zowel n als e moeten in EEPROM aangemaakt worden. • De boodschap m moet blok gealigneerd zijn met de modulus n (i.e., m, n) moeten dezelfde bitlengte hebben. • e moet in lengte kleiner dan of gelijk zijn aan de gebruikte bitlengte voor n. De waarde van e mag evenwel niet groter zijn als die van n. • De RSA encryptie moet ingesteld worden op ‘no-padding’. Dit voorkomt dat de boodschap m aangevuld wordt door extra niet gewenste bits. We overlopen hieronder de consequenties van deze voorwaarden. De eerste voorwaarde beperkt het aantal instellingen die we kunnen kiezen voor 77

6. De Implementatie van het Voorgestelde E-Cash systeem de parameters in het E-Cash systeem. De bitlengte van de veilige priemgetallen p, n moet immers gelijk gekozen worden aan één van de toegelaten RSA modulus bitlengtes. De tweede voorwaarde verplicht de programmeur om efficiënt om te springen met het gebruik van de RSA functionaliteit. Telkens er een machtsverheffing met een verschillende n of e wordt uitgevoerd, wordt de nieuwe waarde van n en e naar EEPROM geschreven wat zowel slecht is voor de performantie als voor de levensduur van het EEPROM. In de Java Card 3.0 standaard is dit gelukkig aangepast en kunnen n, e ook naar RAM geschreven worden. De derde voorwaarde verplicht de programmeur om bij elke machtsverheffing ervoor te zorgen dat m steeds (hoe klein de waarde ook is) uit |n| bits bestaat. De vierde voorwaarde beperkt de exponent die per RSA berekening kan gekozen worden. In ons E-Cash systeem zijn echter ook machtsverheffingen nodig waarbij de bitlengte van de exponent groter is dan de bitlengte van de modulus. De machtsverheffing wordt dan als volgt gedaan (we gaan er vanuit dat de lengte van de exponent kleiner is dan twee keer de lengte van de modulus): Eerst verdelen we de bitstring van de exponent e in deeltjes e1 , e2 waarbij e1 een bitlengte heeft van (|n| − 1) bits en e2 maximaal (|n| − 1) bits groot is. Er geldt dan dat bitstring(e) = bitstring(e2 ||e1 ). We kunnen de exponent dan voorstellen als e = e2 .2(|n|−1) + e1 Daarmee verkrijgen we dat de modulaire machtsverheffing me mod n berekend kan worden als (|n|−1) +e 1

me = me2 .2 = me2

.2(|n|−1)

mod n

.me1 mod n (|n|−1)

= (me2 mod n)2

.me1 mod n

In deze laatste formule is de bitlengte van alle machten kleiner dan of gelijk aan de bitlengte van n en kunnen we dus gebruik maken van de RSA functionaliteit voor de berekening. Voor een modulaire machtsverheffing waarvan de exponent e = e2 ||e1 groter is dan de modulus n, berekenen we dus eerst x ˜ = me2 mod n. (|n|−1) 2 e Daarna berekenen we x = x ˜ mod n en y = m 1 mod n. Tot slot gebruiken we een modulaire vermenigvuldiging (zie hieronder) om me = x.y mod n te bekomen. c. (modulaire) vermenigvuldigingen Het (modulair) vermenigvuldigingen van getallen werd eerst volledig in software geïmplementeerd, naar analogie met de optellingen en aftrekkingen. Het algoritme dat gebruikt werd voor de gewone vermenigvuldiging is algoritme 8 uit bijlage B. Voor de modulaire vermenigvuldigingen werd de modulo operator toegepast op het resultaat van de gewone vermenigvuldiging. De performantie van deze methodes (zie sectie 6.5.2) was echter onaanvaardbaar. Een aantal referentie werken [51], [52] hebben aangetoond dat zelfs na het doorvoeren van optimalisaties in de berekeningen, de software implementatie nooit tot aanvaardbare resultaten leidt. Om toch efficiënt 78

6.2. Analyse van de Implementatie van het Vertrouwde Element gewone en modulaire vermenigvuldigingen te kunnen berekenen wordt daarom als oplossing volgende methodes gesuggereerd: Voor het berekenen van modulaire vermenigvuldigingen stelde men voor om gebruik te maken van de formule ab =

(a + b)2 − a2 − b2 mod n 2

(1)

of van

(a + b)2 − (a − b)2 mod n (2) 4 Op het eerste zicht lijkt het tegenstrijdig dat deze formules tot een enorme versnelling van de vermenigvuldigingen kunnen leiden. De reden voor de versnelling is dat de methode toelaat om gedeeltelijk gebruik te maken van de cryptografische co-processor. De kwadraten in formules (1) en (2) kunnen namelijk via de RSA functionaliteit berekend worden zoals hierboven uitgelegd werd. De modulaire optellingen en aftrekkingen worden dan uitgevoerd aan de hand van de reeds beschreven algoritmes 6 en 7. De delingen door 2 en door 4 worden uitgevoerd met algoritme 9 uit bijlage B. Wij hebben beide methodes geïmplementeerd en zoals weergegeven in sectie 6.5.2 is de eerste methode de snelste. Voor het berekenen van gewone vermenigvuldigingen wordt een gelijkaardige methode gebruikt. De gewone vermenigvuldiging wordt namelijk berekent als een modulaire vermenigvuldiging waarvan de modulus zodanig gekozen wordt dat het resultaat van de vermenigvuldiging geen modulaire reductie ondergaat. In dit geval kan men dan weer de berekening doen aan de hand van formules (1) en (2) van hierboven. Zoals sectie 6.5.2 weergeeft, is de performantie van zowel de modulaire als de gewone vermenigvuldiging hierdoor een heel stuk beter. Als men de (modulaire) vermenigvuldiging doet aan de hand van formule (1) of (2) heeft dat wel als nadeel dat beide operanden dan een bitlengte moeten hebben die gelijk is aan de bitlengte van de modulus die gebruikt wordt (kleinere getallen moeten dus aangevuld worden met nullen). De reden daarvoor ligt in de voorwaarden die hierboven genoteerd werden voor het gebruik van de RSA functionaliteit (bij RSA encrypties zonder padding, moeten modulus en grondtal dezelfde bitlengte hebben). ab =

d. multi-base machtsverheffingen Het berekenen van multi-base machtsverheffingen x = V1e1 V2e2 ..Vkek mod n gebeurt door eerst de afzonderlijke machten te berekenen gebruik makende van de beschreven techniek voor modulaire machtsverheffingen. De uitkomsten worden dan met elkaar vermenigvuldigd volgens de hierboven beschreven methode voor modulaire vermenigvuldigingen. Het uitdagende hieraan was om alle berekeningen te doen binnen het beschikbare RAM geheugen.

79

6. De Implementatie van het Voorgestelde E-Cash systeem BEVINDING 3: Een Java Kaart Heeft Een Beperkte Rekenkracht PROBLEEMSTELLING. De Java kaart is een hardware module die zeer beperkt is in rekenkracht. Optimalisaties zijn hier dan ook veel belangrijker dan voor elk ander Java platform. Er wordt zeker niet gesteld dat de hieronder gegeven optimalisaties tot indrukwekkende verbeteringen leiden, maar rekening houden met deze elementen vraagt wel zeer weinig werk voor de programmeur. VOORGESTELDE OPLOSSINGEN. Tijdens de implementatie werd zoveel mogelijk met volgende aspecten van de Java kaart rekening gehouden: • Het is belangrijk op te merken dat het Java Card platform verschillend is van standaard Java. Bij het programmeren op Java kaarten moet namelijk het gebruik van complexe object georiënteerde architecturen vermeden worden omdat dit voor heel wat runtime overhead zorgt. Een programmeur houdt dus best het aantal klassen beperkt. • Er moet zoveel mogelijk gebruik gemaakt worden van static of private methodes. In Java moet de Java Virtuele Machine voor alle public/protected methodes bepalen wat het dynamische type is van een object vooraleer de methode op het object kan aangeroepen worden. Het static of private maken van een methode reduceert de overhead verbonden met het bepalen van het dynamische type van een object. • Er moet zoveel mogelijk gebruik gemaakt worden van de Java API omdat deze methodes gegarandeerd sneller uitvoeren dan zelf geschreven methodes. De Util klasse uit de Java Card API (zie sectie 5.2.3) biedt bijvoorbeeld heel wat interessante operaties voor het werken met arrays van bytes.

6.3

Analyse van de Implementatie van de Host

In deze sectie overlopen we de implementatie van de host. We doen dit aan de hand van het klassendiagram uit figuur 6.4. De hoofdklasse is de klasse MainActivity die de grafische gebruikersinterface verzorgt. Deze klasse laat toe dat gebruikers hun pincode ingeven, dat ze portefeuilles afhalen bij de bank en dat ze een munt uitgeven uit een bepaalde portefeuille. Voor de implementatie van de operaties die de host moet uitvoeren bij het afhalen en uitgeven van geld, maken we gebruik van de klasse AsecHostEngine. In tegenstelling tot de Java kaart, worden we door de beschikbare Java API nu wel zeer sterk geholpen voor het implementeren van complexe algoritmes. De Java API voor het Android platform bevat namelijk de BigInteger klasse die toelaat om (modulaire) 80

6.3. Analyse van de Implementatie van de Host

Figuur 6.4: Het klassendiagram gebruikt bij het programmeren van de Host.

optellingen/aftrekkingen/vermenigvuldigingen/machtsverheffingen uit te voeren op getallen die niet begrensd zijn in bitlengte. Voor de operaties die niet ondersteund worden door de beschikbare Java API maakt AsecHostEngine gebruik van de klasse MathUtils voor wiskundige hulpmethodes en van de klasse DataUtils voor data hulpmethodes. De hulp klasse MathUtils bevat bijvoorbeeld functionaliteit voor het bepalen van de Lagrange voorstelling van een getal (zie sectie 2.8.1). De hulp klasse Misc bevat functionaliteit voor het voorstellen van data in andere formaten (bv. een BigInteger of een byte array omzetten naar de hexadecimale notatie). Er dient ook opgemerkt te worden dat de implementatie van de host niet botst op geheugen beperkingen. In tegenstelling tot het vertrouwde element kunnen op de host wel zonder problemen alle random variabelen als tijdelijke lokale variabelen opgeslagen worden. Zoals besproken in sectie 6.5 vormt de host geen obstructie voor de realiseerbaarheid van E-Cash op mobiele toestellen. In deze thesis hebben we niet alleen geprobeerd om de praktische realiseerbaarheid van het voorgestelde systeem na te gaan, er werd ook getracht om het communicatie kanaal te bestuderen tussen enerzijds de gebruiker en de verkoper/bank en anderzijds intern in de gebruiker tussen de host en het vertrouwde element. De communicatie tussen de host en het vertrouwde element is gebaseerd op APDU’s. De klasse smartcardHelper implementeert deze interface en verzorgt het versturen en ontvangen van APDU’s en het omzetten naar de gewenste data formaten. Voor de interface tussen gebruiker en verkoper/bank werd er, zoals beschreven in het vorige hoofdstuk, eerst een uitgebreide studie gedaan naar de mogelijkheid om NFC te gebruiken als communicatie middel. Uit dit onderzoek bleek uiteindelijk dat NFC communicatie niet mogelijk was omwille van de beperkingen van de beschikbare hardware. Er werd dan geopteerd voor Bluetooth. Deze vorm van communicatie werd 81

6. De Implementatie van het Voorgestelde E-Cash systeem

n p lx ly lH lφ l le

Setup 1024 bit 512 bit 511 bit 1022 bit 120 bit 80 bit 10 bit 513 bit

Tabel 6.1: Illustratie van de belangrijke pakketten uit de Java Card editie.

wel succesvol geïmplementeerd in het project, waardoor er een draadloze connectie met de host mogelijk is. De functionaliteit die de host nodig heeft voor de bluetooth connectie, wordt verzorgd door de klassen BluetoothService en DeviceListActivity.

6.4

Analyse van de Implementatie van de Verkoper en de Bank

Zoals uitgelegd aan het begin van dit hoofdstuk bleef de implementatie van de bank en verkoper modules beperkt tot wat nodig is om de doelstellingen van de thesis te vervullen. Dit betekent dat beide modules enerzijds de functionaliteit hebben om de nodige stimuli te leveren aan de host en het vertrouwde element. Anderzijds bevatten beide modules de nodige functionaliteit voor het opzetten van een communicatie kanaal over Bluetooth.

6.5 6.5.1

Evaluatie van de realiseerbaarheid van het Voorgestelde E-Cash Systeem Veiligheidsparameters

In het voorgestelde schema van sectie 4.2 werden heel wat parameters gebruikt die aanduiden uit hoeveel bits bepaalde variabelen bestaan. Tabel 6.1 geeft voor elk van de parameters de gekozen bitlengte weer. De gekozen waarden voldoen steeds aan onderstaande voorwaarden: • als n een bitlengte van 2k bits heeft, dan moet q een bitlengte van minstens k bits hebben. • le > lx + 2. • lv = lx + ln + lφ . In de testen die we in de volgende deelsectie beschrijven, gebruikten we steeds de setup uit tabel 6.1. 82

6.5. Evaluatie van de realiseerbaarheid van het Voorgestelde E-Cash Systeem

6.5.2

Performantie van het Gebruikersgedeelte

Een implementatie van het oorspronkelijke (niet gesplitste) E-Cash systeem vereiste dat al de operaties die de gebruiker moet uitvoeren tijdens betalingen, geïmplementeerd zijn op een smartcard. Door de uit te voeren operaties te vergelijken met de beperkingen die smartcards hebben, kan men concluderen dat dit een (quasi) onmogelijke taak is. Het voorgestelde E-Cash systeem ontlast de smartcard in grote mate van berekeningen, maar het gebruikersgedeelte van het E-Cash systeem is nog steeds het knelpunt. In deze thesis hebben we daarom voor het gebruikersgedeelte nagegaan in welke mate de implementatie van het voorgestelde E-Cash systeem mogelijk en aanvaardbaar is vanuit performantie oogpunt. We bekeken eerst of het uitvoeren van de berekeningen op de Java kaart een probleem vormde. Daarbij botsten we op een hele reeks beperkingen van Java kaarten (beschreven in sectie 6.2). Bij de implementatie hebben we rekening gehouden met deze beperkingen en werd veel werk gestoken in de optimalisatie van de berekeningen. In tabel 6.2 illustreert het verschil tussen de responstijd vermeld in de eerste lijn en deze vermeld in de tweede lijn, het effect van de uitgevoerde optimalisatie voor de gewone vermenigvuldiging (die aanvankelijk de traagste methode was). We zien dus dat er in dit geval een winst met factor 3.9 is gerealiseerd is door gebruik te maken van de RSA functionaliteit van de cryptografische coprocessor.

1

2

Software vermenigvuldiging

één 128 van Vermenigvuldiging via RSA functio- één naliteit 128 van

operand byte en 20 byte operand byte en 20 byte

van één van één

uitvoeringstijd 5518 ms

1422 ms

Tabel 6.2: Illustratie van het bereikte resultaat bij de optimalisatie van vermenigvuldigingen.

Uiteindelijk slaagden we erin om alle protocolstappen te implementeren binnen de geheugenvereisten van de gebruikte Java kaart: onze implementatie gebruikt hierbij 727 kB RAM en 10853 kB EEPROM terwijl er 1600 kB RAM en 75000 kB EEPROM beschikbaar is. Tabel 6.3 geeft een indicatie van de responstijd voor een aantal verschillende types van operaties die op het vertrouwde element worden uitgevoerd tijdens geldafhalingen en gelduitgaves. 83

6. De Implementatie van het Voorgestelde E-Cash systeem

1

2

Machtsverheffing van de vorm Ge11 Ge22 Ge33 mod n waarbij de grondtallen en de modulus in EEPROM aanwezig zijn en de exponenten random getallen zijn die tijdens de berekening in RAM worden aangemaakt via de NIST PRNG. Enkelvoudige machtsverheffing van de vorm g e mod n waarbij het grondtal en de modulus in EEPROM aanwezig is en de exponent in RAM

3

Genereren van random getallen met de NIST PRNG

4

Genereren van random getallen met de Java Card PRNG

5

6

7

8

Operatie van de vorm ri − ci waarbij ri gegenereerd wordt met de NIST PRNG, c in RAM is en i in EEPROM

Optelling

Hash functie

Modulaire vermenigvuldiging

n = G1 = G2 = G3 = 128 byte, e1 = e2 = 94 byte, e3 = 158 byte n = G1 = G2 = G3 = 128 byte, e1 = e2 = 64 byte, e3 = 128 byte n = g = 64 byte, e = 94 byte n = g = 64 byte, e = 64 byte n = g = 128 byte, e = 158 byte 10 byte 64 byte 128 byte 10 byte 64 byte 128 byte ri = 158 byte, c = 20 byte en i = 128byte ri = 94 byte, c = 20 byte en i = 64 byte Twee operanden van 64 byte Twee operanden van 128 byte Operand van 30 byte Operand van 94 byte 2 operanden van 128 byte 2 operanden van 160 byte

uitvoeringstijd 6231 ms

3856 ms

1670 ms 270 ms 4116 ms 120 ms 252 ms 480 ms 120 ms 130 ms 160 ms 2634 ms

2143 ms

181 ms 341 ms 125 ms 130 ms 1382 ms 1652 ms

Tabel 6.3: Illustratie van de responstijd van de primitieve operaties die door het vertrouwde element uitgevoerd moeten worden.

84

6.5. Evaluatie van de realiseerbaarheid van het Voorgestelde E-Cash Systeem Gebruik makend van deze tabel gaan we nu de responstijden extrapoleren voor de transacties van het E-Cash schema. Indien we hierbij de resultaten van de te evalueren protocols berekenen op basis van een aggregatie van de tijden in tabel 6.3, bekomen we de volgende resultaten voor het vertrouwd element: - Geldafhalingsprotocol: 17.804 s - Geldstortingsprotocol: 23.340 s Hierna zijn we nagegaan wat de uitvoeringstijden zijn voor de host. Zoals in sectie 6.3 werd uitgelegd, werden we bij het implementeren van de host zeer sterk geholpen door de beschikbare API en moest er geen aandacht besteed worden aan eventuele geheugenbeperkingen. Dit liet toe om gemakkelijk alle protocolstappen van het geldafhaling en het gelduitgave protocol te implementeren. Om het aandeel van de host in de berekeningen te bepalen, hebben we de host zowel aan de interface met de verkoper/bank als aan de interface met het vertrouwd element, voorzien van random stimuli en voerden vervolgens het hele geldafhaling en gelduitgave protocol uit. Op deze manier bekwamen we volgende resultaten: • Geldafhalingsprotocol: 0,148 s • Geldstortingsprotocol 1,020 s

Tabel 6.4 geeft de totaalresultaten voor het geëvalueerde gebruikersgedeelte.

Geldafhalingsprotocol Geldstortingsprotocol

Host (s) 1,020 0,148

TP (s) 17,804 23,340

gebruikerstotaal (s) 18,824 23,488

Tabel 6.4: Responstijden voor het gebruikersgedeelte Uit de resultaten van tabel 6.4 kunnen de volgende conclusies worden getrokken: - De totale responstijd voor beide operaties is niet aanvaardbaar voor commerciële systemen gezien we minstens drie tot vier ordes van grootte verwijderd zijn van een voor de gebruiker aanvaardbare responstijd. Het is inderdaad moeilijk denkbaar dat gebruikers zouden aanvaarden om systematisch langer dan vijf seconden te moeten wachten voor één transactie. - De verhouding tussen de responstijd van host en vertrouwd element, toont aan dat een globale oplossing slechts kan bereikt worden door een substantiële verbetering van de responstijden van het vertrouwd element. Indien we nu rekening houden met het feit dat het aantal berekeningen op het vertrouwd element geminimaliseerd werd en dat deze berekeningen reeds maximaal 85

6. De Implementatie van het Voorgestelde E-Cash systeem geoptimaliseerd werden, is het duidelijk dat het voorgestelde anonieme E-Cash systeem slechts praktisch uitvoerbaar wordt indien performantere hardware voor het vertrouwd element beschikbaar wordt. Deze betere hardware moet dan meer rekenkracht bezitten en een betere Java ondersteuning bieden voor de uitvoering van de cryptografische primitieven uit tabel 6.3. Om tot het gewenst resultaat te komen, moet een versnelling van minstens een factor vier gerealiseerd worden. Vanuit technologisch oogpunt is dit haalbaar gezien de bestaande trends. Dit is ook geldig voor de Java ondersteuning waar we zien dat de kaart versies 2.2.2 en 3.0 reeds meer ondersteuning bieden voor het uitvoeren van een aantal operaties (optellen, aftrekken en vermenigvuldigen). Hierdoor kan een veelvuldig gebruikte operatie zoals si = ri − ci reeds verbeterd worden. Dit is spijtig genoeg nog niet het geval voor andere operaties (modulaire vermenigvuldiging, machtsverheffing) zodat hier nog een verdere evolutie vereist is. Natuurlijk is een mogelijke technologische evolutie slechts een nodige voorwaarde en moet er ook voldoende marktdruk aanwezig zijn om fabrikanten aan te zetten om deze krachtigere kaarten ook te realiseren. Een laatste bemerking betreft de impact van de gebruikte kaart. Wegens compatibiliteitsvereisten hebben we de G&D Java kaart gebruikt gezien dit voor zover wij weten de enige werkzame combinatie is met een Android smartphone. Moesten in de toekomst andere combinaties mogelijk worden is het perfect denkbaar dat deze andere responstijden kunnen opleveren gezien het grote impact van de implementatiewijze van de smartcard.

86

Hoofdstuk 7

Besluiten Du choc des idées jaillit la lumière. Nicolas Boileau

Zoals in de inleiding vermeld werd, is het vernieuwende aan deze masterthesis dat er een anoniem E-Cash systeem voorgesteld werd waarbij het sabotage bestendige element van de gebruiker gedeeltelijk ontlast werd van berekeningen. Het idee hierbij was om al de operaties die niet noodzakelijk uitgevoerd moeten worden door een sabotage bestendig element, over te dragen naar een krachtiger toestel. De gebruiker beschikt dan over twee hardware modules waartussen de uit te voeren berekeningen verdeeld worden: een sabotage bestendig element dat beveiliging biedt tegen corruptie pogingen door andere - kwaadwillige - gebruikers en een krachtiger toestel (de host) dat de reken -en geheugen intensieve acties uitvoert die niet bepalend zijn voor de veiligheid van het systeem. Dit alles wordt geïmplementeerd binnen een compact anoniem E-Cash schema dat de veiligheidseigenschappen van het totale systeem bewaart zelfs indien één gebruiker corrupt is. Nadat het verloop van de protocollen van het E-Cash systeem theoretisch volledig werd uitgewerkt, diende het gesplitste E-Cash systeem als basis voor het verdere werk in de thesis. Daarbij werd enerzijds nagegaan of het systeem na de splitsing van de berekeningen nog steeds aan de gewenste eigenschappen van een E-Cash systeem voldoet. We gaven daarom een eerste aanzet tot een veiligheidsbewijs in het ideale/reële wereld paradigma. Anderzijds werd nagegaan in hoeverre het voorgestelde E-Cash schema tot praktisch realiseerbare implementaties kan leiden. We concentreerden ons hierbij voornamelijk op de implementatie van de gebruiker vermits deze partij uiteraard ook in ons systeem het knelpunt vormt. De andere partijen in het E-Cash systeem (de bank en de verkoper) werden daarom slechts in die mate gerealiseerd om de nodige stimuli te leveren aan de gebruiker. Dit betekent dan ook dat het geldstortingsprotocol en de communicatie tussen bank en verkoper, niet uitgewerkt werden. Bij de implementatie van de gebruiker hadden we vier deelopdrachten voor ogen: -Als eerste stelden we ons de vraag welke hardware gebruikt kan worden voor de host en het sabotage bestendige element. Uit het onderzoek dat hiervoor 87

7. Besluiten gevoerd werd, bleek dat een Android phone als host en een Java kaart als sabotage bestendig element, de best beschikbare werkwijze was. -Ten tweede werd nagegaan of de geheugen vereisten van de Java kaart een probleem vormden voor de implementatie. Daartoe implementeerden we al de operaties die op de smartcard uitgevoerd moeten worden en kwamen tot de conclusie dat het voorgestelde E-Cash systeem tegemoetkomt aan de geheugen beperkingen van de Java kaart. Dit is een belangrijk deelresultaat dat we bereikt hebben. -Ten derde werd nagegaan of de rekentijd van de gebruiker aanvaardbaar was. Hiervoor gingen we de uitvoering van de verschillende operaties op de host en het vertrouwde element na. We concludeerden hierbij dat de host geen probleem vormt, maar dat de responstijd van de Java kaart onaanvaardbaar is. Heel wat werk werd besteed aan het optimaliseren van deze responstijd, maar we botsten hierbij op de beperkingen van Java kaarten. De oplossingsmethoden die we implementeerden zijn echter het maximaal haalbare gezien de mogelijkheden die we hadden. Deze oplossingsmethoden werden gedetailleerd besproken in deze thesis en er werden performantie testen gedaan van de berekeningen die erop gebaseerd zijn. -Ten vierde werd aandacht besteed aan de communicatie kanalen tussen enerzijds de twee hardware modules van de gebruiker en anderzijds tussen de gebruiker en de andere partijen in het protocol. De interface die we definieerden tussen de twee hardware modules van de gebruiker is gebaseerd op het uitwisselen van APDU’s. Voor de interface tussen de gebruiker en de andere partijen in het protocol werd aanvankelijk gedacht aan NFC. De mogelijkheden hiervan werden onderzocht, maar door een gebrek aan aangepaste hardware bleek deze werkwijze onmogelijk. Uiteindelijk werd Bluetooth gekozen als tweede beste mogelijkheid. Het is duidelijk dat de gerealiseerde implementatie geen afgewerkt product is, maar dat deze implementatie beperkt is tot de essentiële onderdelen die nodig zijn om de doenbaarheid van E-Cash op computationeel beperkte systeem na te gaan. Als algemeen besluit kunnen we stellen dat dit werk, na het bepalen van de basisbegrippen in hoofdstuk 2 en het uitwerken van het voorgestelde E-Cash systeem in hoofdstukken 3 en 4, bijgedragen heeft aan een opgesplitste implementatie zoals bestudeerd in hoofdstuk 5. In hoofdstuk 6 werd dan een overzicht gegeven van de essentiële keuzes die we maakten om na te gaan in welke mate de implementatie (op realistische hardware) van het gebruikersdeel van het voorgestelde E-Cash systeem mogelijk is. Dit werd aangevuld met de nodige performantie testen op de hardware van de gebruiker. Deze resultaten tonen aan dat een implementatie van het voorgestelde E-Cash systeem mogelijk is, maar de lage uitvoeringssnelheden zijn een indicator dat de onderzochte splitsing ook nu weer botst op de inherente beperkingen van de gebruikte Java kaart. Hierdoor is een onmiddellijk gebruik in reële toepassingen verre van haalbaar. 88

Verder werk op implementatie vlak is dus hoofdzakelijk afhankelijk van een betere ondersteuning bij het implementeren van cryptografische algoritmes op Java kaarten. Dit is immers een conditio sine qua non om een commercieel aanvaardbare snelheid mogelijk te maken. Een betere ondersteuning kan verschillende zaken inhouden: -Ten eerste is er een betere ondersteuning nodig van de Java Card API bij het uitvoeren van operaties op grote getallen. Onze Java kaart implementeert de Java Card 2.2.1 standaard en zoals besproken in hoofdstuk 6, moet een software ontwikkelaar alle operaties (die trouwens in zo goed als alle cryptografische algoritmes gebruikt worden) zelf implementeren. Omdat een volledige implementatie in software hierbij te traag is, moet op een slimme manier gebruik gemaakt worden van de Java API om de performantie te optimaliseren. Ondertussen bestaan er al Java kaarten die de Java Card standaarden 2.2.2 en 3.0 implementeren en daardoor operaties zoals optellingen, aftrekkingen en vermenigvuldigingen ondersteunen. Het gebruik van deze Java kaarten zou de performantie van enkele cryptografische primitieven uit ons algoritme kunnen verbeteren (voorbeeld van de operatie si = ri − ci). -Ten tweede is het ook belangrijk om op te merken dat we verplicht waren een G&D Java kaart te gebruiken vermits dit de enige Java kaart is die compatibel is met Android smartphones. Het is mogelijk dat als deze vereiste zou vervallen, en we eender welke Java kaart konden gebruiken, dat de performantie resultaten eventueel zouden kunnen verbeteren. In [51] werd immers aangetoond dat twee Java kaarten die afkomstig zijn van andere ontwikkelaars, maar die toch eenzelfde standaard implementeren, zeer verschillende responstijden kunnen hebben. Van zodra het gebruikersgedeelte met aanvaardbare responstijden kan uitgevoerd worden, kunnen verdere stappen ondernomen worden. Daarbij moet eerst de implementatie van de bank/verkoper geanalyseerd te worden. Daarnaast is het ook mogelijk dat er Android smartphones op de markt komen die zowel NFC compatibel zijn en een SD-kaart slot hebben. In dat geval dient de interface tussen de gebruiker en de bank/verkoper herzien te worden. Pas als al deze stappen ondernomen zijn heeft het zin om aan een commercieel systeem te denken en kan hier onderzoek naar verricht worden. Daarnaast kan verder werk ook verbeteringen aanbrengen op conceptueel vlak. We denken hierbij aan de volgende mogelijkheid: We zouden het schema kunnen aanpassen om het mogelijk te maken dat de gebruiker portefeuilles kan afhalen waarbij de munten in verschillende portefeuilles ook een verschillende monetaire waarde kunnen hebben. Op deze manier benadert E-Cash nog meer het digitale alternatief van fysiek geld omdat de gebruiker dan bijvoorbeeld een portefeuille met munten van twee euro, en een portefeuille van munten met vijftig cent ter beschikking zou hebben. 89

7. Besluiten Dit zou voornamelijk de efficiëntie van het gelduitgave protocol verbeteren omdat er dan minder iteraties nodig zijn om een bepaald bedrag uit te geven, gezien het bedrag kan samengesteld worden uit meerdere waarden. Ook voor toepassingen waarbij munten gezien worden als jetons (E-coupons) is dit interessant omdat het toelaat om jetons met verschillende waarden te gebruiken.

Door de realisatie van dit werk hopen we een steentje te hebben bijgedragen aan de uiteindelijke verwezenlijking van E-Cash systemen op mobiele apparaten welke finaal zullen deel uitmaken van ons dagelijkse leven.

90

Bijlagen

91

Bijlage A

Aanzet tot een Veiligheidsanalyse in het Ideale/Reële Wereld Paradigma De veiligheid van het voorgestelde E-Cash systeem (ASEC genoemd hier), wordt geanalyseerd door aan te tonen dat het gezichtspunt van de omgeving Z in de reële wereld (waar partijen interageren volgens het protocol en in de aanwezigheid van een reële tegenstander A ) en het gezichtspunt van de omgeving Z in de ideale wereld (die per definitie veilig is), niet verschilt. Hiervoor construeren we een ideale wereld tegenstander (i.e de simulator E ), zodat geen omgeving Z onderscheid kan maken of het interageert met A of met E. Meer formeel genoteerd: we gebruiken een simulator E die een kopie van de tegenstander A start en interageert met FASEC en de omgeving Z op een zodanige manier dat de ensembles IDEALFASEC ,E,Z en REALASEC,A,Z computationeel niet te onderscheiden zijn. We noteren de relatie computationeel niet te onderscheiden met ≡.

We delen ons bewijs op in verschillende beweringen en elk van deze beweringen analyseert het geval waarin een bepaalde verzameling partijen corrupt gemaakt wordt. We gaan er hierbij vanuit dat partijen enkel statisch gebroken kunnen worden, i.e. de ideale tegenstander E bepaalt in het begin van de uitvoering welke verzameling partijen het wenst te breken en kan deze verzameling niet aanpassen tijdens de uitvoering. We beschouwen niet de gevallen waarin: • Alle partijen corrupt zijn • Geen partijen corrupt zijn • Het vertrouwde element T P wel corrupt is maar de corresponderende host H niet. Er wordt immers vanuit gegaan dat het vertrouwde element moeilijker te 93

A. Aanzet tot een Veiligheidsanalyse in het Ideale/Reële Wereld Paradigma breken is dan de host. Een partij die er dan in slaagt het vertouwde element te breken zal ook zeker de host kunnen corrupt maken. De gevallen die we wel analyseren, worden hieronder genoteerd (partijen met hoofdletter zijn niet corrupt, die met kleine letter wel): (se,h,m,B); (se,h,M,B); (SE,H,m,b); (se,h,M,b); (SE,h,m,b); (SE,h,m,B); (SE,h,M,b); (SE,h,M,B); (SE,H,m,B); (SE,H,M,b) Voor elk van de beweringen tonen we aan dat er geen onderscheid te maken is tussen de reële en de ideale wereld door een sequentie van hybride spelletjes Spelletje 0 ... Spelletje n te definiëren. Hierbij correspondeert Spelletje 0 met de reële wereld en Spelletje n met de ideale wereld. Met Pr[Spelletje i] bedoelen we de kans dat de omgeving kan onderscheiden tussen de ensemble van Spelletje i en de echte uitvoering. Daarom geeft |P r[Spelletje i + 1] − P r[Spelletje i]| weer wat de kans is dat de omgeving Z onderscheid kan maken tussen de ensembles van twee opeenvolgende spelletjes. Door al deze kansen op te tellen, bekomen we een bovengrens voor de kans dat de omgeving Z onderscheid kan maken tussen REALASEC,A,Z en IDEALFASEC ,E,Z . Deze bovengrens moet negeerbaar zijn zodat de bewering geldig is. § Bewering 1. Als de verkoper M , de host H en het vertrouwde element T P corrupt zijn, geldt onder de ’strong RSA’ en de ’y-DDHI’ veronderstelling dat IDEALFASEC ,E,Z ≡ REALASEC,A,Z . - Bewijs van Bewering 1. dat het gestelde waar is.

We tonen via een serie van hybriede spelletjes aan

Spelletje 1.0 : Dit spelletje correspondeert met de uitvoering van het echte protocol tussen een eerlijke bank B en de simulator E (die een kopie van de tegenstander A start). Daarom is Pr[Spelletje 0] = 0. Spelletje 1.1 : Dit spelletje gaat te werk als Spelletje 1.0, behalve dat de simulator (u, s, t, v 0 ) extraheert uit de SPK in stap 3 van de withdraw fase. Vermits we voor deze SPK standaard technieken gebruiken waarvoor we weten dat er een extractor bestaat, is de kans dat het extraheren mislukt negeerbaar. Bijgevolg is dus |P r[Spelletje 1.1] − P r[Spelletje 1.0]| ≤ ν(κ)1 . Spelletje 1.2 : Dit spelletje gaat te werk als Spelletje 1.1, behalve dat de simulator de geheime waarden van de SPK van φ uit de deposit fase extraheert. Vermits ook hier standaard technieken gebruikt worden, weten we dat er een extractor bestaat en mislukt extraheren slechts met verwaarloosbare kans. Bijgevolg is dus |P r[Spelletje 1.2] − P r[Spelletje 1.1]| ≤ ν(κ)2 . Spelletje 1.3 : Dit spelletje gaat te werk als Spelletje 1.2, behalve dat de simulator stopt wanneer de bank B een munt (S,π) accepteert waarvoor J ∈ / [0, 2L ] terwijl 94

in de SPK Φ een vals bewijs geleverd wordt dat J ∈ [0, 2L ]. Dit is namelijk een eerste manier hoe de tegenstander A een niet geldige munt aan de bank kan geven en zo de balans eigenschap weet te breken. De kans dat Z een onderscheid kan maken tussen Spelletje 1.3 en 1.2 wordt begrensd door volgend lemma: Lemma 1.1: Als de ’Strong RSA’ veronderstelling houdt, kan de tegenstander A slechts met verwaarloosbare kans het bewijs dat J ∈ [0, 2L ] vervalsen. Bijgevolg is dus |P r[Spelletje 1.3] − P r[Spelletje 1.2]| ≤ ν(κ)3 . Spelletje 1.4 : Dit spelletje gaat te werk als Spelletje 1.3, behalve dat de simulator stopt wanneer de bank B een munt (S,π) accepteert waarvoor A een handtekening op de waarden (u, s, t) nagemaakt heeft. Dit is namelijk een tweede manier waarop de tegenstander A de SPK φ kan vervalsen. De kans dat Z een onderscheid kan maken tussen Spelletje 1.4 en 1.3 wordt begrensd door volgend lemma: Lemma 1.2: Onder de veronderstelling dat CL handtekeningen veilig zijn (hetgeen de ’Strong RSA’ veronderstelling vereist), is |P r[Spelletje 1.4] − P r[Spelletje 1.3]| ≤ ν(κ)4 . Spelletje 1.5 : Dit spelletje gaat te werk als Spelletje 1.4, behalve dat de simulator stopt wanneer de bank B een munt (S,π) accepteert waarvoor T en S niet correct gevormd zijn. Dit is immers een laatste manier waarop A de SPK φ kan vervalsen. Het lemma hieronder begrensd de kans dat Z een onderscheid kan maken tussen Spelletje 1.5 en 1.4. Lemma 1.3: Onder de y-DDHI veronderstelling, is |P r[Spelletje 1.5] − P r[Spelletje 1.4]| ≤ ν(κ)5 .

Als E al de veranderingen uitvoert zoals beschreven in Spelletje 1.5, dan is er een simulatie te maken waarin E boodschappen stuurt/ontvangt naar/van FASEC . Daarvoor hebben we, na sommatie, dat |P r[Spelletje 1.5] ≤ ν(κ)6 . § Bewering 2. Als de host H en het vertrouwde element T P corrupt zijn, geldt onder de ’strong RSA’ en de ’y-DDHI’ veronderstelling dat IDEALFASEC ,E,Z ≡ REALASEC,A,Z . - Bewijs van Bewering 2. We tonen via een serie van hybriede spelletjes aan dat het gestelde waar is. Spelletje 2.0 : Dit spelletje correspondeert met de uitvoering van het echte protocol tussen een eerlijke bank B, een eerlijke verkoper M en de simulator E (die een kopie van de tegenstander A start). Daarom is Pr[Spelletje 0] = 0. 95

A. Aanzet tot een Veiligheidsanalyse in het Ideale/Reële Wereld Paradigma Spelletje 2.1 : Dit spelletje gaat te werk als Spelletje 0 , behalve dat de simulator (u, s, t) extraheert uit de SPK in stap 3 van de withdraw fase. Zoals we reeds zagen in Bewering 1, is de kans dat het extraheren mislukt negeerbaar. Bijgevolg is dus |P r[Spelletje 2.1] − P r[Spelletje 2.0]| ≤ ν(κ)1 Spelletje 2.2 : Dit spelletje gaat te werk als Spelletje 2.1 , behalve dat de simulator stopt wanneer tegenstander A het bewijs van geldigheid van φ in stap 3 van de spendtransactie kan vervalsen. In Bewering 1 is reeds aangetoond dat dit met negeerbare kans gebeurt. We weten nu dat voor een munt (S ,π = (R, T, φ)) de waarden S, R, T, φ met zeer hoge waarschijnlijkheid correct gevormd zijn (wat dus de identificatie eigenschap bevestigd). Bijgevolg is dus |P r[Spelletje 2.2] − P r[Spelletje 2.1]| ≤ ν(κ)2 .

Als E al de veranderingen uitvoert zoals beschreven in Spelletje 2.2, dan is er een simulatie te maken waarin E boodschappen stuurt/ontvangt naar/van FASEC . Daarvoor hebben we, na sommatie, dat |P r[Spelletje 2.2] ≤ ν(κ)3 . § Bewering 3. Als de verkoper M en de bank B corrupt zijn,geldt onder de ’strong RSA’ en de ’y-DDHI’ veronderstelling dat IDEALFASEC ,E,Z ≡ REALASEC,A,Z - Bewijs van Bewering 3. We tonen via een serie van hybriede spelletjes aan dat het gestelde waar is. Met Pr[Spelletje i] bedoelen we de kans dat de omgeving kan onderscheiden tussen de ensemble van Spelletje i en de echte uitvoering. Spelletje 3.0 : Dit spelletje correspondeert met de uitvoering van het echte protocol tussen een eerlijke host H een eerlijk SE en de simulator E (die een kopie van de tegenstander A start). Daarom is Pr[Spelletje 0] = 0. Spelletje 3.1 : Dit spelletje gaat te werk als Spelletje 0 , behalve dat de simulator E stopt als hij tijdens de Withdraw fase iets betekenisvol leert over de waarden (u,s,t). Uit de veiligheid van de CL handtekeningen volgt dat dit slechts met negeerbare kans gebeurt. Random gegenereerde waarden voor s,t zijn dan niet te onderscheiden van die gekozen door echte gebruikers. Bijgevolg is dus |P r[Spelletje 1] − P r[Spelletje 0]| ≤ ν(κ)1 . Spelletje 3.2 : Dit spelletje gaat te werk als Spelletje 3.1 , behalve dat de simulator E stopt als A een bewijs ΠG = (π1 , π2 ) kan voorleggen zodat VerifyGuilt(pku , S, ΠG ) een eerlijke gebruiker vals veroordeeld. In dit geval zou immers de exculpability eigenschap niet gelden. Opdat de simulator E het valse bewijs ΠG zou kunnen construeren, moet hij erin slagen om de onderliggende SPK te vervalsen. Vermits dit laatste slechts met negeerbare kans lukt, is de kans dat de omgeving Z onderscheid kan maken tussen Spelletje 3.2 en Spelletje 3.1 beperkt door |P r[Spelletje 3.2] − P r[Spelletje 3.1]| ≤ ν(κ)2 96

Spelletje 3.3 : Dit spelletje gaat te werk als Spelletje 2 , behalve dat de simulator ˆ Het enige E de SPK Φ in de spend fase vervangt door een gesimuleerde SPK Φ. ˆ is een gesimuleerde PK van een CL handtekening. verschil tussen de SPK Φ en Φ, Zoals in [2] wordt aangetoond, bestaat er een ’CL signature proof simulator’ ˆ niet onderscheidbaar zijn onder de ’Strong RSA’ veronderstelling. zodat Φ en Φ Daarom is da kans dat omgeving Z onderscheid kan maken tussen Spelletje 3 en Spelletje 2 beperkt door |P r[Spelletje 3] − P r[Spelletje 2]| ≤ ν(κ)3 Spelletje 3.4 : Dit spelletje gaat te werk als Spelletje 3 behalve dat de simulator E voor elke spend transactie random waarden (ˆ u, sˆ, tˆ) ∈ Zq , Jˆ ∈ [0, ..., n − 1] DY u ˆ DY R ˆ ˆ ˆ ˆ genereert, S = fg,ˆs (J + 1), T = g fg,tˆ (J + 1) berekent en vervolgens de ˆ Merk op: de simulator E ˆ R, Tˆ, φ). echte munt (S,R,T,φ) vervangt door (S, bezit de macht over het random orakel en berekent elke spend actie een random waarde R. Uit de veiligheid van de DY pseudo random functie, weten we dat de munt waarden S, T computationeel niet te onderscheiden zijn van random elementen. Daarvoor, kunnen ze met gelijke kans gegenereerd zijn door elke gebruiker met pki = guui en met eenderwelke waarde voor J ∈ [0, ..., n − 1]. De kans dat de omgeving Z onderscheid kan maken tussen Spelletje 3.4 en Spelletje 3.3 beperkt door |P r[Spelletje 3.4] − P r[Spelletje 3.3]| ≤ ν(κ)4 . Als E al de veranderingen uitvoert zoals beschreven in Spelletje 3.4, dan is er een simulatie te maken waarin E boodschappen stuurt/ontvangt naar/van FASEC . Daarvoor hebben we, na sommatie, dat |P r[Spelletje 3.4] ≤ ν(κ)5 . § Bewering 4. Als de host H het vertrouwde element T P en de bank B corrupt zijn, geldt onder de ... veronderstelling dat IDEALFASEC ,E,Z ≡ REALASEC,A,Z - Bewijs van Bewering 4. We tonen via een serie van hybriede spelletjes aan dat het gestelde waar is. Spelletje 4.0 : Dit spelletje correspondeert met de uitvoering van het echte protocol tussen een eerlijke verkoper M en de simulator E (die een kopie van de tegenstander A start). Daarom is Pr[Spelletje 0] = 0. Spelletje 4.1 : Dit spelletje gaat te werk als Spelletje 4.0 behalve dat de simulator E stopt wanneer de simulator E erin slaagt om via 2 spend transacties, twee munten met dezelfde waarde voor S,R aan de verkoper M te overhandigen. Vermits de verkoper maakt dat de waarde van R verschilt voor elke transactie is |P r[Spelletje 4.1] − P r[Spelletje 4.0]| ≤ ν(κ)1 Als E al de veranderingen uitvoert zoals beschreven in Spelletje 4.1, dan is er een simulatie te maken waarin E boodschappen stuurt/ontvangt naar/van FASEC . Daarvoor hebben we, na sommatie, dat |P r[Spelletje 4.1] ≤ ν(κ)2 . § Bewering 5.

Als de host H de verkoper M en de bank B corrupt zijn, geldt 97

A. Aanzet tot een Veiligheidsanalyse in het Ideale/Reële Wereld Paradigma onder de ... veronderstelling dat IDEALFASEC ,E,Z ≡ REALASEC,A,Z - Bewijs van Bewering 5 We tonen via een serie van hybriede spelletjes aan dat het gestelde waar is. Spelletje 5.0 : Dit spelletje correspondeert met de uitvoering van het echte protocol tussen een eerlijke SE en de simulator E (die een kopie van de tegenstander A start). Daarom is Pr[Spelletje 0] = 0. Spelletje 5.1 : Dit spelletje gaat te werk als Spelletje 5.0 , behalve dat de simulator E stopt als A een bewijs ΠG = (π1 , π2 ) kan voorleggen zodat VerifyGuilt(pku , S, ΠG ) een eerlijke gebruiker vals veroordeeld. De kans dat Z onderscheid kan maken tussen Spelletje 5.1 en 5.0 wordt begrensd door volgend lemma: Lemma 5.1: |P r[Spelletje 5.1] − P r[Spelletje 5.0]| ≤ ν(κ)1 . Bewijs Lemma 5.1: We hebben reeds gezien dat de kans dat Φ vervalsd kan worden, verwaarloosbaar is. S,T zijn dus correct gevormd. Verder weten we dat een verkoper (corrupt of niet) voor elke transactie een andere waarde voor R kiest omdat hij anders risico loopt om als dubbele storter te worden veroordeeld. Vermits R verschillend is voor elke transactie, is T en de uiteindelijke hash waarde c dit ook! Een verschillende waarde c voor elke transactie, betekent dat het SE in elke spend transactie betrokken moet zijn. Bijgevolg wordt dus elke spend transactie 3.c uitgevoerd, wat de waarde van S vastlegt en waardoor dubbel gebruik van dezelfde S niet geforceerd kan worden. Als E al de veranderingen uitvoert zoals beschreven in Spelletje 5.1, dan is er een simulatie te maken waarin E boodschappen stuurt/ontvangt naar/van FASEC . Daarvoor hebben we, na sommatie, dat |P r[Spelletje 5.1] ≤ ν(κ)2 . § Bewering 6. Als de host H en de verkoper M corrupt zijn, geldt onder de ... veronderstelling dat IDEALFASEC ,E,Z ≡ REALASEC,A,Z - Bewijs van Bewering 6 We tonen via een serie van hybriede spelletjes aan dat het gestelde waar is. Spelletje 6.0 : Dit spelletje correspondeert met de uitvoering van het echte protocol tussen een eerlijke SE, bank B en de simulator E (die een kopie van de tegenstander A start). Daarom is Pr[Spelletje 0] = 0. Spelletje 6.1 : Dit spelletje gaat te werk als Spelletje 6.0 , behalve dat de simulator E stopt als hij erin slaagt om de SPK van de withdraw fase uit te voeren zonder hulp van SE (en dus zonder kennis van u). De kans dat dit gebeurt is verwaarloosbaar. Inderdaad: de bank stuurt elke withdraw transactie een nieuwe nonce ni op waardoor de waarde van c elke withdraw transactie verschillend is. Dit verplicht de corrupte host om het SE te betrekken 98

in de withdraw transactie omdat enkel het SE kennis heeft van u. Bijgevolg is |P r[Spelletje 6.1] − P r[Spelletje 6.0]| ≤ ν(κ)1 Spelletje 6.2 : Dit spelletje gaat te werk als Spelletje 6.1 , behalve dat de simulator E stopt als hij de SPK Φ kan vervalsen ookal is J ∈ / [0, 2L ] of S,T niet goed gevormd of hij geen handtekening van de bank B heeft op de waarden (u,s,t). Zoals gezien in Bewering 1, gebeurt dit met verwaarloosbare kans. Bijgevolg is |P r[Spelletje 6.2] − P r[Spelletje 6.1]| ≤ ν(κ)2 . Spelletje 6.3 : Dit spelletje gaat te werk als Spelletje 6.2 , behalve dat de simulator E stopt als A een bewijs ΠG = (π1 , π2 ) kan voorleggen zodat VerifyGuilt(pku , S, ΠG ) een eerlijk SE vals veroordeeld. Zoals gezien in bewering 5, gebeurt dit met verwaarloosbare kans en is dus |P r[Spelletje 6.3]−P r[Spelletje 6.2]| ≤ ν(κ)3 Als E al de veranderingen uitvoert zoals beschreven in Spelletje 6.3, dan is er een simulatie te maken waarin E boodschappen stuurt/ontvangt naar/van FASEC . Daarvoor hebben we, na sommatie, dat |P r[Spelletje 6.3] ≤ ν(κ)4 . § Bewering 7. Als de host H en de bank B corrupt zijn, geldt onder de ... veronderstelling dat IDEALFASEC ,E,Z ≡ REALASEC,A,Z - Bewijs van Bewering 7 We tonen via een serie van hybriede spelletjes aan dat het gestelde waar is. Spelletje 7.0 : Dit spelletje correspondeert met de uitvoering van het echte protocol tussen een eerlijke SE, verkoper M en de simulator E (die een kopie van de tegenstander A start). Daarom is Pr[Spelletje 0] = 0. Spelletje 7.1 : Dit spelletje gaat te werk als Spelletje 7.0 , behalve dat de simulator E stopt als hij erin slaagt om de SPK van de spend fase uit te voeren zonder hulp van SE (en dus zonder kennis van u). Helemaal analoog aan het bewijs van lemma 5.1, kan aangetoond worden dat het SE (dat kennis heeft van u) betrokken moet zijn in elke spend transactie. Bijgevolg is |P r[Spelletje 7.2] − P r[Spelletje 7.1]| ≤ ν(κ)2 Spelletje 7.3 : Dit spelletje gaat te werk als Spelletje 7.2 , behalve dat de simulator E stopt als hij erin slaagt twee munten (S,R,T) te genereren. De kans dat dit gebeurt is klein omdat R random is (resultaat van een Hash functie en we veronderstellen de hash functie collision resistant). Bijgevolg is |P r[Spelletje 7.3] − P r[Spelletje 7.2]| ≤ ν(κ)3 . Spelletje 7.4 : Dit spelletje gaat te werk als Spelletje 7.2 , behalve dat de simulator E stopt als A een bewijs ΠG = (π1 , π2 ) kan voorleggen zodat VerifyGuilt(pku , S, ΠG ) een eerlijk SE vals veroordeeld. Zoals gezien in bewering 5, gebeurt dit met verwaarloosbare kans en is dus |P r[Spelletje 7.4]−P r[Spelletje 7.3]| ≤ ν(κ)4 99

A. Aanzet tot een Veiligheidsanalyse in het Ideale/Reële Wereld Paradigma Als E al de veranderingen uitvoert zoals beschreven in Spelletje 7.4, dan is er een simulatie te maken waarin E boodschappen stuurt/ontvangt naar/van FASEC . Daarvoor hebben we, na sommatie, dat |P r[Spelletje 7.4] ≤ ν(κ)5 . § Bewering 8. Als de host H corrupt is, geldt onder de ... veronderstelling dat IDEALFASEC ,E,Z ≡ REALASEC,A,Z - Bewijs van Bewering 8 We tonen via een serie van hybriede spelletjes aan dat het gestelde waar is. Spelletje 0 : Dit spelletje correspondeert met de uitvoering van het echte protocol tussen een eerlijke SE, verkoper M , bank B en de simulator E (die een kopie van de tegenstander A start). Daarom is Pr[Spelletje 0] = 0. Spelletje 8.1 : Dit spelletje gaat te werk als Spelletje 8.0 , behalve dat de simulator E stopt als hij erin slaagt om de SPK van de withdraw fase uit te voeren zonder hulp van SE (en dus zonder kennis van u). Zoals reeds gezien in bewering 6 gebeurt dit met negeerbare kans en bijgevolg is |P r[Spelletje 8.1]− P r[Spelletje 8.0]| ≤ ν(κ)1 Spelletje 8.2 : Dit spelletje gaat te werk als Spelletje 8.1 , behalve dat de simulator E stopt als hij erin slaagt om de SPK van de spend fase uit te voeren zonder hulp van SE (en dus zonder kennis van u). Zoals reeds gezien in bewering 7, gebeurt dit met verwaarloosbare kans. Bijgevolg is |P r[Spelletje 8.2] − P r[Spelletje 8.1]| ≤ ν(κ)2 Spelletje 8.3 : Dit spelletje gaat te werk als Spelletje 8.2 , behalve dat de simulator E stopt als hij de SPK Φ kan vervalsen ookal is J ∈ / [0, 2L ] of S,T niet goed gevormd of hij geen handtekening van de bank B heeft op de waarden (u,s,t). Zoals gezien in Bewering 1, gebeurt dit met verwaarloosbare kans. Bijgevolg is |P r[Spelletje 8.3] − P r[Spelletje 8.2]| ≤ ν(κ)3 . Spelletje 8.4 : Dit spelletje gaat te werk als Spelletje 8.3 , behalve dat de simulator E stopt als hij erin slaagt twee munten (S,R,T) te genereren. De kans dat dit gebeurt is klein omdat R random is (resultaat van een Hash functie en we veronderstellen de hash functie collision resistant). Bijgevolg is |P r[Spelletje 8.4] − P r[Spelletje 8.3]| ≤ ν(κ)4 . Spelletje 8.5 : Dit spelletje gaat te werk als Spelletje 8.4 , behalve dat de simulator E stopt als A een bewijs ΠG = (π1 , π2 ) kan voorleggen zodat VerifyGuilt(pku , S, ΠG ) een eerlijk SE vals veroordeeld. Zoals gezien in bewering 5, gebeurt dit met verwaarloosbare kans en is dus |P r[Spelletje 8.5]−P r[Spelletje 8.4]| ≤ ν(κ)5 Als E al de veranderingen uitvoert zoals beschreven in Spelletje 8.5, dan is er een simulatie te maken waarin E boodschappen stuurt/ontvangt naar/van FASEC . Daarvoor hebben we, na sommatie, dat |P r[Spelletje 8.5] ≤ ν(κ)6 . 100

§ Bewering 9. Als de verkoper M corrupt is, geldt onder de ... veronderstelling dat IDEALFASEC ,E,Z ≡ REALASEC,A,Z - Bewijs van Bewering 9 Van deze bewering geven we geen formeel bewijs vermits de bewijsvoering ongeveer analoog is aan bewering 3. § Bewering 10. Als de bank B corrupt is, geldt onder de ... veronderstelling dat IDEALFASEC ,E,Z ≡ REALASEC,A,Z - Bewijs van Bewering 10 Van deze bewering geven we geen formeel bewijs vermits de bewijsvoering ongeveer analoog is aan bewering 3.

101

Bijlage B

Overzicht van Enkele Belangrijke Algoritmes Algorithm 1 Bereken de Lagrange voorstelling van een positief getal µ Input: Een getal µ ≥ 0 Output: (w1 , w2 , w3 , w4 ) zodat µ = w12 + w22 + w32 + w42 . 1: Vind t, k ≥ 0 zodat µ = 2t (2k + 1) 2: Stel γ = 2(2k + 1) q √ 3: Bepaal de random waarden w10 ≤ γ en w20 ≤ γ − w102 zodanig dat w10 + w20 = 1 mod 2. 4: Bereken p = γ − (w102 + w202 ) 5: Ga na of p priem is. Is dit het geval, ga verder. Zo nee, ga terug naar stap 3. 6: Schrijf p als p = w302 + w402 door volgende twee stappen uit te voeren: a) Zoek een oplossing u voor de vergelijking u2 = −1 mod p b) Pas het algoritme van Euclides toe op (u, p) en neem de twee eerste √ resten die kleiner zijn dan p. Noem deze resten respectievelijk w30 en w40 . 7: if t = 1 then 8: Return (w1 , w2 , w3 , w4 ) = (w10 , w20 , w30 , w40 ) 9: else if t = 1 mod 2 then 10: Bereken s = 2(t−1)/2 11: Return (w1 , w2 , w3 , w4 ) = (sw10 , sw20 , sw30 , sw40 ) 12: else if t = 0 mod 2 then 13: Bereken s = 2(t/2)−1 14: Hergroepeer de waarden van (w10 , w20 , w30 , w4 ) onderling zodanig dat w1 = w2 mod 2 en w3 = w4 mod 2 15: Return (w1 , w2 , w3 , w4 ) = (s(w10 +sw20 ), s(w10 −sw20 ), s(w30 +sw40 ), s(w30 −sw40 )) 16: end if

103

B. Overzicht van Enkele Belangrijke Algoritmes

Algorithm 2 Rabin-Miller probabilistische priem test Input: Een oneven getal n ≥ 3 en veiligheidsparameter t ≥ 1. Output: Een Ja/Nee antwoord op de vraag of n priem. De veiligheidsparameter bepaalt de kans op correctheid van de uitkomst. Typisch wordt t= 6 - 8 gekozen. 1: Schrijf n − 1 = 2s r zodanig dat r oneven is. 2: for i = 1 tot t do 3: a) Kies een random getal a, 2 ≤ a ≤ n − 2. 4: b) Bereken y = ar mod n 5: if y 6= 1 en y 6= n − 1 then 6: j←1 7: while j ≤ s − 1 en y 6= n − 1 do 8: y ← y 2 mod n 9: if y = 1 then 10: return “Niet priem” en stop 11: end if 12: j ←j+1 13: end while 14: if y 6= n − 1 then 15: return “Niet priem” en stop 16: end if 17: end if 18: end for 19: return “priem” en stop

Algorithm 3 Generatie van waarschijnlijk veilige priemgetallen Input: 1) Het gewenste aantal bits k > 2 voor het veilige priemgetal. 2) Een veiligheidsparameter t ≥ 5 die bepaalt met welke zekerheid de output een veilig priemgetal is. Output: Een veilig priemgetal van k bits. 1: Genereer een random, oneven getal b van k − 1 bits. 2: Controleer voor alle priemgetallen r kleiner dan een grens B ≤ k O(1) of één van volgende vergelijkingen opgaat: b = 0 mod r, b = (r − 1)/2 mod r. Als dit het geval is, ga dan terug naar regel 1, zo niet ga verder.

104

Algorithm 3 Generatie van waarschijnlijk veilige priemgetallen (vervolg) 3: Test of 2 een Rabin-Miller getuige is van het feit dat b een composiet getal is. Als dit het geval is, ga dan terug naar regel 1. Voor het uitvoeren van de test worden volgende deelstappen uitgevoerd a) Druk b − 1 uit als 2s t met t oneven b) Stel x ← 2t mod b c) Als x = 1 of x = b − 1, ga dan naar regel 1. Ga anders verder. d) For i = 1 tot s do x ← x2 mod b Als x = b − 1 ga dan naar regel 1. Ga verder in het andere geval. Endfor e) Ga naar regel 1 4: Bereken a = 2b + 1 en controleer of 2b ≡ ±1 mod a. Als dat niet zo is, ga dan terug naar regel 1. 5: Pas algoritme 2 toe op b voor t = 6. Als dit algoritme “niet priem” teruggeeft, ga dan terug naar regel 1. 6: Return b.

Algorithm 4 Java pseudo code voor de optelling van twee positieve getallen Input: Twee byte[ ]’s die als operanden gebruikt worden: eersteArray en tweedeArray. De byte[ ]’s moeten op een unsigned manier geïnterpreteerd worden. We gaan er ook vanuit dat de MSB op positie 0 staat in elke array en de LSB op positie array.length -1 Output: byte[ ] som = eersteArray + tweedeArray 1: short lengteSom = (short) (max(eersteArray.length, tweedeArray.length) + 1); 2: short c = 0; 3: byte[ ] som = new byte[lengteSom]; 4: for (short i = 0; i < (lengteSom - 1); i++) do 5: if (i < eersteArray.length) then 6: c += (short) (eersteArray[(short)(eersteArray.length -1 - i)] & 0x00FF); 7: end if 8: if (i < tweedeArray.length) then 9: c += (short) (tweedeArray[(short)(tweedeArray.length -1 - i)] & 0x00FF); 10: end if 11: sum[(short)(lengteSom - 1 - i)] = (byte) (c & 0x00FF) 12: c = (byte) ((c > > > 8) & 0x0001); //bereken de carry 13: end for 14: sum[0] = (byte) c;

105

B. Overzicht van Enkele Belangrijke Algoritmes

Algorithm 5 Java pseudo code voor de aftrekking van twee getallen Input: Twee byte[ ]’s die als operanden gebruikt worden: eersteArray en tweedeArray. De byte[ ]’s moeten op een unsigned manier geïnterpreteerd worden. We gaan er vanuit dat de MSB op positie 0 staat in elke array en de LSB op positie array.length -1. Er moet verder gelden dat nummer(eersteArray) > nummer(tweedeArray), waarbij nummer(.) het unsigned nummer is dat overeenkomt met het argument. Output: byte[ ] som = eersteArray - tweedeArray 1: byte[] verschil = new byte[eersteArray.length]; 2: short c = 0; 3: for (short i = 0; i < eersteArray.length; i++) do 4: c += eersteArray[(eersteArray.length -1 - i) & 0x00FF ]; 5: if (i < tweedeArray.length) then 6: c -= tweedeArray[(tweedeArray.length -1 - i) & 0x00FF);. 7: end if 8: if c < 0 then 9: verschil[(short)(verschil.length -1 - i)] = (byte) (c + 0x0100); 10: c = -1; 11: else 12: verschil[(short)(verschil.length -1 - i)] = (byte) c ; 13: c = 0; 14: end if 15: end for

Algorithm 6 De modulaire optelling van twee getallen. Input: Drie byte[ ]’s die als operanden gebruikt worden: x, y, p. De byte[ ]’s moeten op een unsigned manier geïnterpreteerd worden. We gaan er vanuit dat de MSB op positie 0 staat in elke array en de LSB op positie array.length -1. Er moet verder gelden dat nummer(x), nummer(y) < nummer(p) waarbij nummer(.) het unsigned nummer is dat overeenkomt met het argument. Output: byte[ ] moduloSom = x + y mod p 1: z ← x + y (via algoritme 4). 2: if (nummer(z) > nummer(p)) then 3: z ← z − p (cia algoritme 5. 4: end if

106

Algorithm 7 De modulaire aftrekking van twee getallen. Input: Drie byte[ ]’s die als operanden gebruikt worden: x, y, p. De byte[ ]’s moeten op een unsigned manier geïnterpreteerd worden. We gaan er vanuit dat de MSB op positie 0 staat in elke array en de LSB op positie array.length -1. Er moet verder gelden dat nummer(x), nummer(y) < nummer(p) waarbij nummer(.) het unsigned nummer is dat overeenkomt met het argument. Output: byte[ ] moduloVerschil = x − y mod p 1: if (nummer(x) > ,nummer(y)) then 2: z ← x − y (via algoritme 5. 3: else 4: z ← (x + p) − y (via algoritmes 4 en 5). 5: end if 6: if z > p then 7: z ← z − p (cia algoritme 5. 8: end if

Algorithm 8 Java voorbeeld code voor het in software vermenigvuldigen van twee positieve getallen. Input: Twee byte[ ]’s die als operanden gebruikt worden: eersteArray en tweedeArray. De byte[ ]’s moeten op een unsigned manier geïnterpreteerd worden. We gaan er vanuit dat de MSB op positie 0 staat in elke array en de LSB op positie array.length -1. . Output: byte[ ] multiplication = eersteArray * tweedeArray 1: byte carry = 0; 2: short w = 0; 3: short outLen = (short)(eersteArray.length + tweedeArray.length) 4: multiplication = new byte[outLen]; 5: for (short i = (short) (tweedeArray.length -1); i >= 0; i - -) do 6: carry = 0; 7: for (short j = (short) (this.length-1); j >= 0; j–) do w = (short)( eersteArray.getShortAtPosition((short)(this.offset + j)) * 8: tweedeArray.getShortAtPosition((short)(tweedeArray.offset + i) ) + multiplication.getShortAtPosition((short)( i+j+1)) + (short)(carry & 0x00FF) ); 9: multiplication[(short)( i+j+1)] = (byte) (w & 0x00FF); 10: carry = (byte) ((w > > > 8) & 0x00FF); 11: end for 12: multiplication[(short)(destination.offset + i )] = carry; 13: end for

107

B. Overzicht van Enkele Belangrijke Algoritmes

Algorithm 9 Java voorbeeld code voor het modulair door twee delen van een getal. Input: byte[] number dat gedeeld moet worden door twee en een byte[] n die als modulo operand gebruikt wordt. Output: byte[] output = number / 2 mod n 1: byte[] output = new byte[number.length] 2: if ( ( (short)(0x0001 & number[number.length - 1]) != (short) 0) then 3: output = number + n (volgens algoritme 4) 4: short position = output.length; 5: byte value; 6: for (short i=1 ; i > > 1) ) | ( ((0x01)& output.getByteAtPosition((short)(position-1))) < < 7 ) ); 9: output[position] = value; 10: end for 11: output[0] = (byte) ((0x007F)&(output[0] > > > 1)) 12: output = output.modulo(n); 13: else 14: short position = number.length; 15: byte value; 16: for (short i=1 ; i > > 1) ) | ( ((0x01)& number.getByteAtPosition((short)(position-1))) < < 7 ) ); 19: number[position] = value; 20: end for 21: number[0] = (byte) ((0x007F)&(number[0] > > > 1)) 22: output = number.modulo(n); 23: end if

108

Bijlage C

Javadoc van de Implementatie van het Vertrouwd Element

109

Bijlage D

Javadoc van de Implementatie van de Host

115

Bijlage E

Illustratie van de Interface Tussen Host en Vertrouwd Element

133

We illustreren de werking van de interface tussen host en vertrouwd element aan de hand van het geldafhalingsprotocol:

Bibliografie [1] D. Chaum, “Blind signatures for untraceable payments,” in CRYPTO, pp. 199– 203, 1982. [2] J. Camenisch, S. Hohenberger, and A. Lysyanskaya, “Compact e-cash,” in EUROCRYPT, pp. 302–321, 2005. [3] E. Brickell, J. Camenisch, and L. Chen, “Direct anonymous attestation,” in Proceedings of the 11th ACM conference on Computer and communications security, CCS ’04, (New York, NY, USA), pp. 132–145, ACM, 2004. [4] A. J. Menezes, S. A. Vanstone, and P. C. V. Oorschot, Handbook of Applied Cryptography. Boca Raton, FL, USA: CRC Press, Inc., 1st ed., 1996. [5] E. Dougherty, Random processes for image and signal processing. SPIE/IEEE series on imaging science and engineering, SPIE Optical Engineering Press, 1999. [6]

A. R. Duran Master’s thesis.

[7] O. Goldreich, “Introduction to complexity theory,” Department of Computer Science and Applied Mathematics: notes for a one semester course, 2002. [8] J. Camenisch, Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem. PhD thesis, ETH Zurich, 1998. Reprint as vol. 2 of ETH Series in Information Security and Cryptography, ISBN 3-89649-286-1, Hartung-Gorre Verlag, Konstanz, 1998. [9] R. Canetti, “Universally composable security: A new paradigm for cryptographic protocols,” in Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, FOCS ’01, (Washington, DC, USA), pp. 136–, IEEE Computer Society, 2001. [10] N. Casati, “Universally composable secret handshakes with credentials,” Master’s thesis, IBM ZRL. [11] A. Rial, M. Kohlweiss, and B. Preneel, “Universally composable adaptive priced oblivious transfer,” in Proceedings of the 3rd International Conference Palo Alto on Pairing-Based Cryptography, Pairing ’09, (Berlin, Heidelberg), pp. 231–247, Springer-Verlag, 2009. 137

Bibliografie [12] R. Canetti, “The universal composability framework - definitions,” Lecture 7 of selected topics in cryptography, 2004. [13] R. Cools, J. Vandewalle, A. Bultheel, and B. Preneel, Toegepaste discrete algebra. VTK, 2009. [14] H. Lipmaa, “On diophantine complexity and statistical zero-knowledge arguments,” in ASIACRYPT, pp. 398–415, 2003. [15] M. J. Wiener, “Safe prime generation with a combined sieve.” Cryptology ePrint Archive, Report 2003/186, 2003. http://eprint.iacr.org/. [16] R. Cramer and V. Shoup, “Signature schemes based on the strong rsa assumption,” in ACM Transactions on Information and System Security, p. 2000, ACM press, 1998. [17] Y. Dodis and A. Yampolskiy, “A verifiable random function with short proofs and keys,” in Public Key Cryptography, pp. 416–431, 2005. [18] B. Preneel, Analysis and Design of Cryptographic Hash Functions. PhD thesis, Katholieke Universiteit Leuven (KUL), 1993. [19] I. Damgård and E. Fujisaki, “A statistically-hiding integer commitment scheme based on groups with hidden order,” in ASIACRYPT, pp. 125–142, 2002. [20] J.-J. Quisquater, L. Guillou, M. Annick, and T. Berson, “How to explain zeroknowledge protocols to your children,” in Proceedings on Advances in cryptology, CRYPTO ’89, (New York, NY, USA), pp. 628–631, Springer-Verlag New York, Inc., 1989. [21] M. Bellare and O. Goldreich, “On defining proofs of knowledge,” in CRYPTO, pp. 390–420, 1992. [22] J. Camenisch and M. Stadler, “Efficient group signature schemes for large groups (extended abstract),” in CRYPTO, pp. 410–424, 1997. [23] J. Camenisch and A. Lysyanskaya, “A signature scheme with efficient protocols,” in SCN, pp. 268–289, 2002. [24] S. von Solms and D. Naccache, “On blind signatures and perfect crimes,” Comput. Secur., vol. 11, no. 6, pp. 581–583, 1992. [25] D. Chaum, A. Fiat, and M. Naor, “Untraceable electronic cash,” in Proceedings on Advances in cryptology, CRYPTO ’88, (New York, NY, USA), pp. 319–327, Springer-Verlag New York, Inc., 1990. [26] T. Okamoto, “An efficient divisible electronic cash scheme,” in Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’95, (London, UK, UK), pp. 438–451, Springer-Verlag, 1995. 138

Bibliografie [27] A. Chan, Y. Frankel, and Y. Tsiounis, “Easy come - easy go divisible cash,” pp. 561–575, Springer-Verlag, 1998. [28] S. Canard and A. Gouget, “Divisible e-cash systems can be truly anonymous,” in In EUROCRYPT, pp. 482–497, 2007. [29] D. Chaum and T. P. Pedersen, “Transferred cash grows in size,” in Proceedings of the 11th annual international conference on Theory and application of cryptographic techniques, EUROCRYPT’92, (Berlin, Heidelberg), pp. 390–407, SpringerVerlag, 1993. [30] H. Tewari, D. O’Mahony, and M. Peirce, “Reusable off-line electronic cash using secret splitting,” tech. rep., Trinity College, 1998. [31] S. Canard and A. Gouget, “Anonymity in transferable e-cash,” in ACNS, pp. 207– 223, 2008. [32] O. Blazy, S. Canard, G. Fuchsbauer, A. Gouget, H. Sibert, and J. Traoré, “Achieving optimal anonymity in transferable e-cash with a judge,” in AFRICACRYPT, pp. 206–223, 2011. [33] T. Sander and A. Ta-Shma, “On anonymous electronic cash and crime,” in ISW, pp. 202–206, 1999. [34] J. Camenisch, A. Lysyanskaya, and M. Meyerovich, “Endorsed e-cash,” in IEEE Symposium on Security and Privacy, pp. 101–115, 2007. [35] J. K. Liu, P. P. Tsang, and D. S. Wong, “Recoverable and untraceable e-cash,” in Proceedings of the Second European conference on Public Key Infrastructure, EuroPKI’05, (Berlin, Heidelberg), pp. 206–214, Springer-Verlag, 2005. [36] Y. Xin-song and L. Zhao, “Some improvements on recoverable e-cash,” in Proceedings of the 2010 International Conference on E-Business and E-Government, ICEE ’10, (Washington, DC, USA), pp. 2126–2128, IEEE Computer Society, 2010. [37] T. Nakanishi, N. Haruna, and Y. Sugiyama, “Unlinkable electronic coupon protocol with anonymity control,” in Proceedings of the Second International Workshop on Information Security, ISW ’99, (London, UK, UK), pp. 37–46, Springer-Verlag, 1999. [38] Android SDK: http://developer.android.com/sdk/index.html. [39] Eclipse ADT plugin: http://developer.android.com/sdk/eclipse-adt.html. [40] R. Rogers, J. Lombardo, Z. Mednieks, and B. Meike, Android Application Development: Programming with the Google SDK. O’Reilly Media, Inc., 1st ed., 2009. 139

Bibliografie [41] Java Card Software Development Kit : http://www.oracle.com/technetwork/java /javasebusiness/. [42] J. Vossaert, J. Lapon, and V. Naessens, “Developing secure java card applications,” in Java Card development, p. 5, 2010. [43] Java Card API 2.2.1: http://cs.ru.nl/woj/javacardapi221. [44] Giesecke and Devrient, “How to write java card applets,” in Mobile Security Cards. [45] ISO 7816-3 smart card standard: Cards with contacts — Electrical interface and transmission protocols. [46] ISO 7816-4 smart card standard: Organization, security and commands for interchange. [47] ISO 14443-4 : The transmisson protocol (T=CL). [48] SEEK (Secure Element Evaluation Kit for the Android platform): http://code.google.com/p/seek-for-android/. [49] NFC formum: www.nfc-forum.org/. [50] S. S. Keller, “NIST-recommended random number generator based on ANSI X9.31 Appendix A.2.4 using the 3-key triple DES and AES algorithms,” tech. rep., U.S. DoC/National Institute of Standards and Technology, 2005. See http://csrc.nist.gov/cryptval/rng/931rngext.pdf. [51] M. Sterckx Master’s thesis. [52] P. Bichsel, J. Camenisch, T. Groß, and V. Shoup, “Anonymous credentials on a standard java card,” in Proceedings of the 16th ACM conference on Computer and communications security, CCS ’09, (New York, NY, USA), pp. 600–610, ACM, 2009.

140

KU Leuven Faculteit Ingenieurswetenschappen

2011 – 2012

Fiche masterproef Student: Marijn Scheir Titel: Ontwerp en Implementatie van een Anoniem E-Cash Systeem voor Computationeel Beperkte Platformen Engelse titel: Design and Implementation of an Anonymous E-cash System for Resource Constrained Platforms UDC : 621.3 Korte inhoud: Sinds 1982 is er in de literatuur heel wat theoretisch onderzoek gedaan naar zogenaamde anonieme E-Cash systemen met als doel deze te gebruiken als digitaal alternatief voor fysiek geld. De omzetting van deze systemen naar bruikbare realisaties bleef uit doordat de performantie van het gebruikersdeel van een E-Cash systeem het knelpunt vormde. Gebruikers moeten namelijk een sabotagebestendig element gebruiken voor het uitvoeren van berekeningen. Het vernieuwende aan deze thesis is dat getracht wordt om dit probleem op te lossen door de berekeningen op het sabotagebestendige element zo minimaal mogelijk te houden. Gebaseerd op het compacte E-Cash systeem van Camenisch et al. hebben we alle operaties die niet dienen om de gebruiker te beschermen tegen corruptiepogingen door andere partijen, overgedragen naar een host systeem dat gebaseerd is op een krachtig(er) mobiel apparaat dat niet sabotage bestendig is. Enkel de operaties die de gebruiker beschermen tegen corruptie werden op het sabotage bestendig deel behouden. Het resulterende systeem moet uiteraard voldoen aan de eigenschappen die van een bruikbaar anoniem E-Cash systeem verwacht worden. Het systeemconcept is ook zodanig ontworpen dat zelfs indien de host gecorrumpeerd is, transacties onmogelijk zijn zonder het beveiligd element. In deze thesis hebben we, naast de beschrijving van het conceptueel model, een eerste aanzet gegeven om binnen het ‘ideale wereld/reële wereld’ paradigma te analyseren of het voorgestelde systeem de nodige eigenschappen bezit. Hierna hebben we de praktische realiseerbaarheid van het voorgestelde conceptueel model nagegaan door de realisatie van een -gesplitste- implementatie van het gebruikersdeel van het E-cash systeem. Het transmissie kanaal tussen gebruiker en de buitenwereld (terminal) werd eveneens behandeld. Om de doenbaarheid van de voorgestelde oplossing te evalueren werden hierna performantietests uitgevoerd op de implementatie van het gebruikersdeel. Hieruit werd snel duidelijk dat de responstijd van het sabotage beveiligd element ordes van grootte hoger was dan de responstijd van de berekeningen op het host gedeelte en hierdoor de bepalende factor bleef voor de doenbaarheidsanalyse. Jammer genoeg moet hierbij vastgesteld worden dat, niettegenstaande de doorgevoerde optimalisaties in de berekeningen op het sabotage vrij element, de vastgestelde responstijden niet toe laten om de bestudeerde oplossing te gebruiken als basis voor een aanvaardbare realisatie. Dit betekent ook dat de bestudeerde werkwijze slechts tot succes kan leiden indien ze geïmplementeerd kan worden op snellere hardware, uitgerust met

Bibliografie betere API ondersteuning.

Thesis voorgedragen tot het behalen van de graad van Master of Science in de ingenieurswetenschappen: elektrotechniek, optie Telecommunicatie en telematica Promotoren: Prof. dr. ir. Bart Preneel Prof. dr. ir. Ingrid Verbauwhede Prof. dr. ir. Johan Driesen Assessoren: Prof. dr. ir. Claudia Diaz Prof. dr. ir. Johan Driesen Begeleiders: Ir. Alfredo Rial Ir. Josep Balash 142