Symmetrische versleuteling voor RFID-Tags

Faculteit Ingenieurswetenschappen Departement Elektrotechniek – ESAT KATHOLIEKE UNIVERSITEIT LEUVEN

Symmetrische versleuteling voor RFID-Tags

Eindwerk voorgedragen tot het behalen van het diploma van Burgerlijk Elektrotechnisch Ingenieur, optie ICT-multimedia en signaalverwerking (Master in de ingenieurswetenschappen: elektrotechniek (ICT))

Gauthier Van Damme Promotors:

Prof. dr. ir. Bart Preneel Prof. dr. ir. Ingrid Verbauwhede Dagelijkse begeleiding:

dr. ir. Orr Dunkelman ir. Miroslav Knezevic ir. Roel Maes

2007 – 2008

c Copyright by K.U.Leuven

Zonder voorafgaande schriftelijke toestemming van zowel de promotor(en) als de auteur(s) is overnemen, kopiëren, gebruiken of realiseren van deze uitgave of gedeelten ervan verboden. Voor aanvragen tot of informatie i.v.m. het overnemen en/of gebruik en/of realisatie van gedeelten uit deze publicatie, wendt U tot de K.U.Leuven, Departement Elektrotechniek – ESAT, Kasteelpark Arenberg 10, B-3001 Heverlee (België). Telefoon +32-16-32 11 30 & Fax. +32-16-32 19 86 of via email: [email protected]. Voorafgaande schriftelijke toestemming van de promotor(en) is eveneens vereist voor het aanwenden van de in dit afstudeerwerk 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.

c Copyright by K.U.Leuven

Without written permission of the promotor(s) and the author(s) it is forbidden to reproduce or adapt in any form or by any means any part of this publication. Requests for obtaining the right to reproduce or utilize parts of this publication should be addressed to K.U.Leuven, Departement Elektrotechniek – ESAT, Kasteelpark Arenberg 10, B-3001 Heverlee (Belgium). Tel. +32-16-32 11 30 & Fax. +32-16-32 19 86 or by email: [email protected]. A written permission of the promotor(s) is also required to use the methods, products, schematics and programs described in this work for industrial or commercial use, and for submitting this publication in scientific contests.

i

Voorwoord Eerst en vooral wil ik mijn promotors, Prof. Preneel en Prof. Verbauwhede bedanken voor de kans die ze mij hebben gegeven om dit eindwerk te maken. Zonder hen had ik niet kunnen kennismaken met de wondere wereld van lichtgewicht cryptografie. Vervolgens wil ik Orr Dunkelman, Miroslav Knezevic en Roel Maes hartelijk danken voor hun beschikbaarheid. Ze stonden steeds voor mij klaar en zonder hen zou dit eindwerk nooit gelukt zijn. Langs deze weg zou ik ook mijn familie, waar het altijd thuiskomen is, willen bedanken voor de kansen die ze me gaven. En ondertussen zie ik mijn papa al fronsen... Dank je wel voor al je commentaar bij het lezen van mijn thesis, maar de vorige zin, hoe slecht ook geschreven, heb ik toch laten staan! Tenslotte bedank ik ook mijn vrienden om me te doen lachen en me van tijd tot tijd van het leven te doen genieten. Gauthier mei 2008

iii

Abstract De groei van het gebruik van lage-kost RFID-toepassingen gaat gepaard met een vraag naar zeer compacte beveiliging van dit type communicatie. Door de lage kost die de tags in RFIDtoepassingen moeten hebben, moet de beveiliging eveneens een lage kost hebben. Momenteel bestaat er nog geen algemeen gebruikt, symmetrisch cijfer, dat zeer compact in hardware en tegelijk veilig is. Er bestaan wel compacte implementaties van het AES-blokcijfer maar deze zijn nog steeds te groot om op lage-kost RFID-tags te worden gebruikt. Dit eindwerk stelt het symmetrisch blokcijfer EFES (Encryption Function for Embedded Systems) voor. Bij het ontwerp werden zowel hardware-efficiëntie als veiligheid binnen RFIDtoepassingen in acht genomen, om tot een zeer compacte cryptografische primitieve te komen. EFES gaat een 64 bit datablok in 64 klokcycli versleutelen aan de hand van een 80 bit geheime sleutel. Deze sleutel wordt door de lezer en de tag van de RFID-toepassing gedeeld zodat beide entiteiten kunnen communiceren zonder dat een buitenstaander de uitgewisselde data kan achterhalen. Er wordt aangenomen dat generische aanvallen de meest efficiënte aanvallen op EFES zijn. Differentiële en lineaire cryptanalyse werden gebruikt als het uitgangspunt voor de veiligheid van het cijfer. Dit zijn ook de meest voorkomende aanvallen op blokcijfers. Geen enkele differentiële of lineaire aanval kan het blokcijfer EFES vlugger kraken dan wanneer exhaustief naar de sleutel wordt gezocht. Met zijn hardware-implementatie in 1328.5 GE, is EFES het meest compacte blokcijfer tot nu toe gepubliceerd. Het is 241.5 GE kleiner dan het kleinste blokcijfer (Present). Daarenboven moet EFES niet onderdoen voor stroomcijfers die tot nu toe, onterecht, als meestal compacter dan blokcijfers werden beschouwd. Het aantal GE dat de implementatie van EFES nodig heeft, is namelijk op een dertigtal GE na even klein als het kleinste stroomcijfer (Grain). Bovendien wordt aangetoond dat stroomcijfers geen veilige oplossing bieden voor gebruik binnen RFID-toepassingen. Het blokcijfer dat in dit eindwerk wordt voorgesteld voldoet dus aan de eisen van veiligheid en van zeer compacte hardware-implementatie en zou dus kunnen worden gebruikt bij de beveiliging van lage kost RFID-communicaties. Dit weliswaar pas na een grondige periode van analyse van het cijfer.

v

Inhoudsopgave Voorwoord Abstract Inhoudsopgave Lijst van symbolen Lijst van figuren Lijst van tabellen 1 Inleiding 1.1 RFID-communicaties en hun beveiliging . . . . . . . 1.2 Symmetrische cryptografie . . . . . . . . . . . . . . . 1.2.1 Stroomcijfers . . . . . . . . . . . . . . . . . . 1.2.2 Blokcijfers . . . . . . . . . . . . . . . . . . . . 1.3 De Structuur van het eindwerk . . . . . . . . . . . . 2 De algemene structuur van het symmetrisch cijfer 2.1 Keuze tussen stroom- of blokcijfer . . . . . . . . . . 2.1.1 Oppervlaktegebruik . . . . . . . . . . . . . . 2.1.2 Veiligheid . . . . . . . . . . . . . . . . . . . . 2.1.3 Flexibiliteit van het cijfer . . . . . . . . . . . 2.1.4 Vermogenverbruik van het cijfer . . . . . . . 2.1.5 Keuze symmetrisch cijfer . . . . . . . . . . . 2.2 Keuze sleutellengte . . . . . . . . . . . . . . . . . . . 2.2.1 De bestaande onderzoeken . . . . . . . . . . . 2.2.2 De gewijzigde aanpak . . . . . . . . . . . . . 2.3 Toestands- en bloklengte . . . . . . . . . . . . . . . . 2.4 De algemene structuur . . . . . . . . . . . . . . . . . 3 De invalshoek van het ontwerp 3.1 Differentiële cryptanalyse . . . . . . . . . . . . . . . 3.1.1 Het principe van differentiële cryptanalyse . . 3.1.2 De uitwerking van een differentiële aanval . . 3.1.3 De efficiëntie van differentiële cryptanalyse . 3.2 Lineaire cryptanalyse . . . . . . . . . . . . . . . . . . 3.2.1 Het principe van lineaire cryptanalyse . . . . 3.2.2 De uitwerking van een lineaire aanval . . . . 3.2.3 De efficiëntie van lineaire cryptanalyse . . . . 3.3 De invalshoek . . . . . . . . . . . . . . . . . . . . . . 4 Het blokcijfer EFES 4.1 De Substitutie-boxen . . . . . . . . . . . . . . . . . . vi

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

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

iii v vi viii x xi 1 1 4 4 5 8 9 9 10 10 11 12 12 13 13 13 16 17 21 21 21 23 24 25 25 26 27 28 29 30

4.2 De Mix-box . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 De deelsleutel optelling . . . . . . . . . . . . . . . . . . . . . . 4.4 De rotatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 De key scheduling . . . . . . . . . . . . . . . . . . . . . . . . 5 Motivatie van de ontwerpkeuzes 5.1 De Substitutiefunctie . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 De kans DP en de bias ε . . . . . . . . . . . . . . . . 5.1.2 S-boxen veilig tegen differentiële en lineaire aanvallen 5.1.3 De functie S7 [X] . . . . . . . . . . . . . . . . . . . . . 5.1.4 De functie S5 [X] . . . . . . . . . . . . . . . . . . . . . 5.2 Optimalisatie van het aantal actieve S-boxen . . . . . . . . . 5.2.1 Een permutatie gebruiken . . . . . . . . . . . . . . . . 5.2.2 Het aantal rondes verhogen . . . . . . . . . . . . . . . 5.2.3 Efficiëntere S-boxen gebruiken . . . . . . . . . . . . . 5.2.4 Een lineaire combinatie gebruiken . . . . . . . . . . . 5.3 De Rotatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 De key scheduling . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Related-key aanvallen . . . . . . . . . . . . . . . . . . 5.4.2 Slide aanvallen . . . . . . . . . . . . . . . . . . . . . . 5.4.3 Voorwaarden voor een veilige key scheduling . . . . . 5.4.4 De veiligheid van de key scheduling van EFES . . . . 6 Veiligheid van het blokcijfer EFES 6.1 Veiligheid tegen differentiële cryptanalyse . . . . . . . . . . . 6.1.1 De eerste ronde van EFES . . . . . . . . . . . . . . . . 6.1.2 De eerste 7 rondes van EFES . . . . . . . . . . . . . . 6.1.3 De veiligheid van EFES tegen differentiële aanvallen . 6.1.4 Het totaal aantal rondes van EFES . . . . . . . . . . . 6.2 Veiligheid tegen lineaire cryptanalyse . . . . . . . . . . . . . . 7 Performantie van het blokcijfer EFES 7.1 Oppervlaktegebruik van het blokcijfer EFES . . . . . . . . . . 7.2 Vergelijking van de hardware-performantie van EFES met dat metrische cijfers . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Vermogenverbruik van het blokcijfer EFES . . . . . . . . . . 8 Besluit Bibliografie A Testvectoren B De GEZEL implementatie van EFES

vii

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

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

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

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

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

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

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

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

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

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

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

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . . . . . . van andere sym. . . . . . . . . . . . . . . . . . . .

32 33 33 34 36 36 37 38 38 39 39 40 40 40 42 43 43 43 43 44 44 46 46 47 48 49 51 51 53 53 54 55 57 59 63 64

Lijst van symbolen ⊕ K f g n k r u en p Ki P pi C y d xi yi X Y ∆X ∆Y DP S[X] Z zi Ksub Nd c Xi Yi

De modulo-2-optelling of exclusive or -poort De sleutel van een cijfer Een niet-lineaire functie Het aantal LFSR’s in een stroomcijfer De lengte van een blok bij blokcijfers De sleutellengte van het blokcijfer Het aantal rondes van een blokcijfer Het aantal gebruikte S-boxen De deelsleutel van ronde i van een blokcijfer De ingang van het blokcijfer of klaartekst Een bit i van de klaartekst De uitgang van het blokcijfer of cijfertekst Het jaar tot wanneer het blokcijfer veilig moet zijn Het aantal bits waarover wordt geroteerd Een ingangsbit i van een functie Een uitgangsbit i van een functie Een ingangsvector van een functie Een uitgangsvector van een functie Een ingangsverschilwaarde Een uitgangsverschilwaarde De kans dat een differentieel optreedt De substitutiefunctie De inverse van de laatste ronde van het blokcijfer Een bit i van de inverse van de laatste ronde van het blokcijfer Een deelsleutelbitcombinatie van de laatste ronde van het blokcijfer Het aantal gekozen (klaartekst, cijfertekst)-paren nodig bij een differentiële aanval Een kleine constante Een boolean die duidt op het al dan niet aanwezig zijn van ingang i in de lineaire benadering Een boolean die duidt op het al dan niet aanwezig zijn van uitgang i in de lineaire benadering

viii

ΓX ΓY ε P [F ] q Nl m S5 [X] S7 [X] bi M kji ti l C B

Een vector van de verschillende ingangselementen uit de lineaire benadering Een vector van de verschillende uitgangselementen uit de lineaire benadering De bias waarmee een lineaire benadering afwijkt van een 50% kans van optreden De kans dat een functie F juist is Een kans tussen 0 en 1 Het aantal gekende (klaartekst, cijfertekst)-paren nodig bij een lineaire aanval Het aantal bits die een S-box niet-lineair verandert De substitutiefunctie van de 5 bit S-box De substitutiefunctie van de 7 bit S-box Een willekeurige bit i De matrixvoorstelling van de M-box Bit j van de deelsleutel Ki Bit i van de rondeteller Een getal gebruikt bij het zoeken naar S-boxen Een 5 bit vector gelijk aan [00110] met de rechtse bit de minst significante De matrixvoorstelling van een binaire lineaire combinatie

ix

Lijst van figuren 1.1

RFID-communicatie: in een eerste stap zal de lezer de tag ondervragen en mogelijk van vermogen voorzien(1). Daarna zal de tag hierop antwoorden(2). . . . . . . . . 1.2 Stroomcijfer voorbeeld: de databits worden bit per bit opgeteld bij de sleutelstroom bekomen uit de sleutel K. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 SP-netwerken: de datablokken ondergaan verschillende rondes van permutatie, substitutie en optelling van een deelsleutel Ki . . . . . . . . . . . . . . . . . . . . . 1.4 De Feistel-structuur met 2 deelblokken: elke ronde wordt de permutatie, substitutie en de deelsleuteloptelling slechts op de helft van het blok toegepast. . . . . . . . . 2.1

2 5 7 7

2.2

SP-netwerk gebruik makend van multiplexers met twee ingangen om de grootte van de substitutie- en diffusiefuncties te halveren. . . . . . . . . . . . . . . . . . . . . . De algemene structuur van het te ontwerpen blokcijfer. . . . . . . . . . . . . . . . .

19 20

4.1 4.2

Het blokcijfer EFES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . De key scheduling van het blokcijfer EFES. . . . . . . . . . . . . . . . . . . . . . .

30 34

5.1

Evolutie van de bits (in grijs) die niet-lineair afhankelijk zijn van de oorspronkelijke sleutelbits over de rondes heen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

Evolutie van de potentieel actieve nibbles (in grijs) in functie van de keuze van de aanvaller over de rondes heen. De beschouwde nibbles worden genummerd van 0 tot en met 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

6.1

x

Lijst van tabellen 2.1

De eigenschappen van stroom- en blokcijfers. . . . . . . . . . . . . . . . . . . . . .

12

4.1 4.2 4.3

De lookup table van de functie S5 [X] . . . . . . . . . . . . . . . . . . . . . . . . . . De uitkomsten van de functie S7 [X] . . . . . . . . . . . . . . . . . . . . . . . . . . De lookup table van de functie S3 [X] . . . . . . . . . . . . . . . . . . . . . . . . . .

31 32 35

7.1 7.2

Oppervlaktegebruik van het blokcijfer EFES in aantal GE. . . . . . . . . . . . . . Vergelijking tussen compacte symmetrische cijfers. . . . . . . . . . . . . . . . . . .

54 55

xi

Hoofdstuk 1

Inleiding Computers kunnen vandaag met nooit geziene en steeds groeiende rekenkracht problemen op een steeds efficiëntere en goedkopere manier oplossen. Deze evolutie is wellicht noodzakelijk maar daarom nog niet voldoende om voor bepaalde toepassingen een adequate oplossing te bieden. Zo bijvoorbeeld hebben ingebedde systemen zoals de veel besproken RFID tags of andere smart cards enorme potentiële voordelen en toepassingsmogelijkheden. Naargelang de toepassing stellen deze systemen echter specifieke, beperkende eisen wat betreft de grootte, de kost, de snelheid en het vermogenverbruik. Terwijl de belangstelling voor het gebruik van ingebedde systemen met de dag toeneemt, rijst ook de vraag naar hun beveiliging. Deze beveiliging zorgt voor bijkomende uitdagingen om deze eveneens op een zo compacte, goedkope, snelle en vermogen-efficiënte manier te implementeren op deze ingebedde systemen. Een voor de hand liggende keuze om te kunnen voldoen aan deze voorwaarden is het gebruik van symmetrische cryptografische cijfers. Deze bestaan namelijk uit een combinatie van bouwblokken die efficiënt in hardware kunnen worden ge¨ımplementeerd en men kan ze derhalve zeer compact maken. In dit eindwerk wordt een compact en veilig symmetrisch cijfer gebouwd, specifiek voor RFIDtoepassingen, maar dat in het algemeen ook uitbreidbaar moet zijn voor gebruik bij allerhande andere ingebedde systemen. In deze inleiding worden in een eerste deel de basisbegrippen over RFID-communicaties en hun beveiliging besproken. Een tweede deel bevat uitleg over symmetrische cryptografie. Tenslotte beschrijft een laatste deel de structuur van dit eindwerk.

1.1

RFID-communicaties en hun beveiliging

RFID staat voor Radio Frequency Identification en is een draadloze communicatie-techniek over kleine afstanden tussen aan de ene kant de radio frequency (RF)-tags of transponders en aan de andere kant RF-tag lezers of tranceivers. 1

1. Inleiding

Figuur 1.1: RFID-communicatie: in een eerste stap zal de lezer de tag ondervragen en mogelijk van vermogen voorzien(1). Daarna zal de tag hierop antwoorden(2).

De werking van RFID-communicatie De lezer zal de tag ondervragen door er een hoogfrequent signaal naar toe te sturen waarop de tag zal antwoorden met de gevraagde data die er in opgeslagen zitten (zie figuur 1.1). De afstand waarover dit kan gebeuren kan variëren van minder dan één meter tot enkele honderden meters, voornamelijk afhankelijk van de zendkracht van de tag en dus van zijn energiebron. De lezer wordt immers verondersteld een relatief onbeperkt vermogen ter beschikking te hebben. Zo zijn er de passieve RFID-tags die hun vermogen halen uit het uitgezonden signaal van de lezer. Hierdoor hebben deze tags slechts een beperkt vermogen ter beschikking en kunnen dus enkel op kortere afstanden met een lezer communiceren. Het voordeel van dit type RFID-tags is wel dat ze doorgaans goedkoper zijn. Actieve RFID-tags daarentegen bevatten een ingebouwde batterij en hebben zodoende een groter vermogen ter beschikking dan passieve tags. Hun bereik kan hierdoor worden vergroot tot enkele tientallen tot zelfs enkele honderden meters. Het inbouwen van een batterij leidt echter wel tot een aanzienlijke meerkost. In deze thesis wordt ervoor gekozen om enkel de passieve RFID-tags in beschouwing te nemen daar het minimaliseren van de algemene kost van een tag het uitgangspunt van het eindwerk is. De toepassingen van RFID-communicatie De toepassingsmogelijkheden van dit type tags zijn enorm groot. Door hun kleine kost kunnen ze voor allerhande producten gebruikt worden. Zo gebruikt de industrie al langer RFID-tags ter vervanging van de barcodes op producten. Bij barcodes onderscheiden producten van hetzelfde type zich niet. Door de invoering van RFID-tags kan élk product een unieke identiteit krijgen zoals bijvoorbeeld de Electronic Product Code (EPC) [49]. Deze overgang brengt enorme voordelen met zich mee. Zo wordt het beheren van opslagplaatsen of grootwarenhuizen veel efficiënter doordat de bewegingen van elk product op elk moment kunnen worden gevolgd. Ook in het openbaar vervoer en in andere publieke of private sectoren zoals bibliotheken, waar 2

RFID-communicaties en hun beveiliging

de toegang tot de gebouwen of diensten vlug maar veilig moet kunnen gebeuren, hebben de RFID-tags hun diensten al bewezen [3].

De beveiliging van RFID-communicatie Het lijkt evident dat bij de net aangehaalde toepassingen de communicatie op een veilige manier moet gebeuren. Het moet een buitenstaander onmogelijk worden gemaakt om de echte identiteit van de tag te achterhalen of om de verzonden data te bemachtigen. Hiervoor wordt gebruik gemaakt van een cryptografische primitieve. Dit is een algoritme die de verstuurde data zal versleutelen zodat enkel bevoegde personen deze informatie kunnen achterhalen. Om bij RFID-tags de algemene kost laag te houden moet de beveiliging eveneens zeer goedkoop en dus compact gebeuren. Uit onderzoek blijkt dat wanneer men RFID-tags wil gebruiken op alle type producten en niet enkel op luxe-goederen met een hoge eenheidsprijs zoals schoonheidsproducten, de kost van de cryptografische primitieve op de tags niet veel groter mag zijn dan U S$ 0.05 (e 0.03) [55, 50]. Tegenwoordig kost de beveiliging van dergelijke tag ruim U S$ 0.50 (e 0.3) en kunnen RFID-tags nog steeds niet voor alle producten worden gebruikt. Een kost tussen U S$ 0.05 en U S$ 0.5 voor de beveiliging van een RFID-tag komt momenteel overeen met een cryptografisch cijfer met een oppervlaktegebruik van ongeveer 500 a 5000 Gate Equivalenten (GE). Deze GE worden gelijk gesteld aan NAND-poorten in CMOS-standaardcel-hardware. Een vraag die kan worden gesteld is of het wel nodig is om de tags in de goedkopere producten te beveiligen. Het antwoord hierop is ja. Ten eerste voorkomt een dergelijke beveiliging dat het product wordt gestolen of nagebootst (bijvoorbeeld bij gebruik van RFID-tags in het openbaar vervoer). Ten tweede zal de beveiliging van de RFID-tags de privacy van de gebruikers garanderen. Doordat de communicatie draadloos gebeurt kan namelijk, wanneer de tag niet beveiligd is, om het even wie de tag lezen en dus de identiteit ervan achterhalen. De privacy van de eigenaar van het object verbonden aan de tag komt hierdoor in gedrang. Een buitenstaander zou de identiteit van een persoon kunnen achterhalen aan de hand van de unieke verzameling van tags die hij met zich meedraagt. Zo kan hij het doen en laten van deze persoon volgen. Daarom is het belangrijk dat ook de RFID-tags bedoeld voor gebruik bij goedkopere producten worden beveiligd.

De communicatie-protocollen van RFID-communicatie Om de zonet omschreven problemen te vermijden, moeten naast het beveiligen (versleutelen) van de verzonden informatie, zowel tag als lezer zich op een veilige manier wederzijds kunnen identificeren en authenticeren. Dit wil zeggen dat tag en lezer een reeks afspraken maken waardoor ze niet enkel op een veilige manier hun identiteit kunnen uitwisselen, maar ook kunnen aantonen dat de identiteit die ze beweren te hebben daadwerkelijk de hunne is. Dit is het authenticatie-proces. Op die manier is de lezer zeker dat hij met de juiste tag communiceert en omgekeerd is de tag zeker dat hij aan een bevoegde lezer zijn identiteit prijsgeeft. Hiervoor moeten veilige communicatie protocollen worden gekozen. Hierop wordt verder ingegaan in hoofdstuk 2.4. 3

1. Inleiding

Symmetrische cryptografie voor RFID-communicatie Wegens het grote belang om de kost van de RFID-tags laag te houden, kunnen niet alle cryptografische primitieven gebruikt worden ter beveiliging. Zo zal men moeten afstappen van publieke sleutel cryptografie zoals RSA [47]. Deze primitieven vergen te grote sleutels en te complexe berekeningen om met een beperkt aantal poorten ge¨ımplementeerd te worden. Andere algoritmes zoals AES (Advanced Encryption Standaard) [16] zijn al beter geschikt voor dit type toepassingen maar zijn helaas niet specifiek ontworpen voor een zeer compacte implementatie waardoor het minimum aantal poorten die ze verbruiken relatief hoog blijft. Bij symmetrische cryptografie bestaat de mogelijkheid om compacte tot zeer compacte implementaties te bekomen. Met de groeiende populariteit van RFID-tags en de bijhorende nood aan beveiliging groeide ook het aantal al dan niet succesvolle voorstellen tot compacte symmetrische cijfers. Dit eindwerk gaat dus op zoek naar een symmetrisch cijfer dat voldoende veilig zowel als zeer compact is.

1.2

Symmetrische cryptografie

Bij symmetrische cryptografie delen twee partijen eenzelfde sleutel. Beide partijen gebruiken deze sleutel om data (de klaartekst) te beveiligen door deze aan de hand van de cryptografische primitieve te encrypteren met de gedeelde sleutel. Omgekeerd kan de andere partij de geëncrypteerde data (de cijfertekst) lezen door deze te decrypteren met diezelfde sleutel aan de hand van de inverse van de cryptografische primitieve. Er bestaan twee types symmetrische cijfers: stroomcijfers en blokcijfers. Beide types worden besproken in de volgende secties.

1.2.1

Stroomcijfers

Bij stroomcijfers [42] vercijfert het cijfer de klaartekst bit per bit door deze bits modulo-2 op te tellen met bits uit een sleutelstroom. Dit modulo 2 optellen komt overeen met een exclusive or (XOR) poort in hardware en wordt voorgesteld door het symbool ⊕. Er wordt getracht om aan de hand van een sleutel met vaste lengte een sleutelstroom met een grote periode te bekomen die als pseudo-willekeurig kan worden beschouwd. Hiermee benadert het cijfer de perfecte, onvoorwaardelijke veiligheid van een volledig willekeurige sleutelstroom of one time pad zoals beschreven door Shannon [51] zonder hiervoor een oneindig lange sleutel nodig te hebben.

De Sleutelstroom De sleutelstroom wordt bekomen door een geheugen, bestaande uit flip-flops, elke klokslag te hernieuwen aan de hand van sommige waarden uit de vorige toestand en mogelijk ook vercijferde bits uit vorige klokslagen. Het type bouwblok dat hiervoor het meest gebruikt wordt is het Linear Feedback Shift Register (LFSR) dat goede periodieke eigenschappen heeft. Door de lineariteit van LFSR’s moeten de resultaten ervan echter gecombineerd worden met een sterk niet-lineaire functie. Zoniet zou een aanvaller uit de sleutelstroom en de gekende structuur van het cijfer een stelsel van lineaire vergelijkingen kunnen oplossen om tot de sleutel te komen 4


Figuur 1.2: Stroomcijfer voorbeeld: de databits worden bit per bit opgeteld bij de sleutelstroom bekomen uit de sleutel K. [42, 17]. Figuur 1.2 toont een voorbeeld van een stroomcijfer-structuur. Deze bestaat uit een reeks van g LFSR’s waarvan de outputs worden gecombineerd met een niet-lineaire functie f. Compacte stroomcijfers Door de relatieve eenvoud van stroomcijfers gaat men er dikwijls van uit dat deze op een zeer compacte manier kunnen worden ge¨ımplementeerd. Bestaande stroomcijfers bevestigen dit ook. Zo werd het A5/1-cijfer gebruikt op de SIM-kaarten van GSM’s om de communicaties te beveiligen en had het hiervoor slechts 752 Gate Equivalenten (GE) nodig. Verder werd het E0-cijfer gebruikt in Bluetooth-communicaties en had het slechts 1637 GE nodig [9]. Achteraf is echter gebleken dat deze cijfers onvoldoende veiligheid bieden en werd een paar jaar geleden het eSTREAM project opgestart [2]. Dit project is een wedstrijd die onder andere op zoek gaat naar een standaard voor compacte symmetrische beveiliging, gebruik makend van stroomcijfers. Hieruit zijn al heel wat compacte stroomcijfers voortgekomen zoals Grain [25] of Trivium [15] met respectievelijk 1294 en 2599 GE [8]. Ook zijn er heel wat nieuwe invalshoeken voor het ontwerpen van stroomcijfers gevonden zoals het gebruik van onregelmatig klokken in de Mickey-familie van stroomcijfers [7], jump registers zoals in het Pomaranch-cijfer [33] of nog het gebruik van de quasigroepentheorie zoals in Edon80 [22]. Maar ook hier blijken de stroomcijfers dikwijls zwakheden in hun veiligheid te bevatten [41, 29].

1.2.2

Blokcijfers

Een blokcijfer [42] gaat de klaartekst opdelen in blokken van vaste lengte om deze dan blok per blok te vercijferen. Hiervoor maakt het cijfer gebruik van een sleutel met vaste lengte. De encryptie (en omgekeerd de decryptie) is een bijectie van een n bit klaartekstblok naar een n bit cijfertekstblok. Hierbij is de bijectie idealiter verschillend voor elke mogelijke sleutel. Om hieraan te voldoen moet er volgens Shannon [51] naast een onbekende, in de vorm van de sleutel, ook diffusie zijn van de originele klaartekst bits zodat elke cijfertekstbit afhankelijk is van alle klaartekstbits of omgekeerd dat het veranderen van één klaartekstbit alle cijfertekstbits met een kans 12 verandert. Verder zegt Shannon ook dat er confusie moet plaatsvinden. Deze confusie is een niet-lineaire functie die het lineariseren van het cijfer moet tegengaan. 5

1. Inleiding

De structuur van blokcijfers De voorgaande voorwaarden worden ge¨ımplementeerd door gebruik te maken van verschillende iteraties over een blok van n bits. Deze iteraties worden in de cryptografie rondes genoemd. In elke ronde wordt de toestand van een blok door een diffusie- en confusiestap gestuurd om daarna bit per bit, modulo-2, te worden opgeteld bij de sleutel van de ronde in kwestie, ook wel deelsleutel genoemd. De bekomen toestand wordt dan terug in het geheugen geschreven. Hierbij wordt meestal de oude toestand overschreven. Het totaal aantal rondes r dat nodig is zal afhangen van de kwaliteiten van de diffusie- en confusiestap en de veiligheid die het cijfer moet bieden. Na ronde r wordt het resultaat en dus de n bit cijfertekst weggeschreven naar de uitgang van het cijfer. De diffusie wordt meestal ge¨ımplementeerd door een permutatie over de n bits van een blok. De substitutie gebeurt aan de hand van een niet-lineaire functie of substitutie die meestal wordt ge¨ımplementeerd door een reeks kleinere parallel werkende functies, de Substitutie- of S-boxen genaamd. Deze u S-boxen gaan elk een deel van de n bits van een blok niet-lineair combineren. Eerst vindt altijd de confusiestap plaats, gevolgd door de diffusiestap en uiteindelijk de deelsleutel optelling. Enkel in het begin van de eerste ronde moet v´ oór de confusiestap al een deelsleutel worden opgeteld bij de data. Uit deze manier van werken zijn twee gelijkaardige structuren van blokcijfers gegroeid [48] die beiden gebruik maken van permutaties om te voldoen aan de diffusievoorwaarde en van substituties om te voldoen aan de confusievoorwaarde. Beide structuren maken ook gebruik van verschillende rondes waarbij telkens een deelsleutel, afgeleid uit de originele sleutel, wordt gebruikt. De volgende twee paragrafen lichten deze structuren nader toe.

De SP-netwerken De eerste structuur, de Substitutie-Permutatie- of SP-netwerken gaan bij elke ronde i van de encryptie, de diffusie, de confusie en de optelling met de deelsleutel Ki toepassen op de volledige bloklengte (zie figuur 1.3). Elke ronde of iteratie komt overeen met één klokcyclus. Voor de decryptie wordt gebruik gemaakt van de inverse van de permutatieen substitutiefuncties (voor de deelsleutel optelling is dit niet nodig daar er modulo-2 wordt gewerkt1 ).

De Feistel-structuren Feistel-structuren daarentegen gaan in elke ronde de verschillende stappen slechts op een deel van het blok toepassen. De meest voorkomende vorm is wanneer in elke ronde telkens de helft van een blok wordt gebruikt, maar men kan in principe het blok indelen in elke macht van twee. Ook hier komt elke ronde overeen met een klokcyclus (zie figuur 1.4). Het voordeel van dit type systeem is dat door de bewerkte helft elke ronde op te tellen bij de andere helft en daarna dit resultaat samen met de oorspronkelijke toestand door te sturen naar de volgende ronde, bij de decryptie de inverse van de substitutiefuncties niet nodig is. Stel f : GF (2n/2 ) → GF (2n/2 ) de niet-lineaire functie die elke ronde optreedt, waarin de substitutie, de permutatie en optelling van de deelsleutel Ki verwerkt zitten. Stel verder Pl de linkerhelft en Pr de rechterhelft van de input van een ronde dan heeft men voor een Feistel: 1

6

In GF (2) en dus bij modulo-2 optelling, is de inverse van de optelling gelijk aan de optelling zelf.


Figuur 1.3: SP-netwerken: de datablokken ondergaan verschillende rondes van permutatie, substitutie en optelling van een deelsleutel Ki .

Figuur 1.4: De Feistel-structuur met 2 deelblokken: elke ronde wordt de permutatie, substitutie en de deelsleuteloptelling slechts op de helft van het blok toegepast.

7

1. Inleiding

Cl = Pr

(1.1)

Cr = Pl ⊕ f(Pr )

(1.2)

Waarbij Pl en Pr kunnen worden gevonden uit de outputs Cl en Cr van één ronde via:

Pl = Cr ⊕ f(Cl )

(1.3)

P r = Cl

(1.4)

Logischerwijs zijn er bij dit systeem voor eenzelfde veiligheid dan wel meer rondes nodig, aangezien in elke ronde maar een deel van de totale bloklengte verandert. Compacte blokcijfers Door het historisch gegroeid belang van blokcijfers zijn deze, in tegenstelling tot stroomcijfers veel beter gestandaardiseerd en gekend. Het blokcijfer dat hiervoor verantwoordelijk is en tot voor kort algemeen werd gebruikt, is de Data Encryption Standard (DES) [42]. Dit cijfer wordt door zijn te kleine sleutellengte echter niet meer als veilig beschouwd en is ondertussen vervangen door het Advanced Encryption Algorithm (AES) [16], maar heeft er toe geleid dat de veiligheid van blokcijfers vandaag veel beter kan worden nagegaan. Beide algoritmes zijn hardware georiënteerde blokcijfers die relatief compact kunnen worden ge¨ımplementeerd. Zo bestaat er een implementatie van AES die slechts 3400 GE nodig heeft [21]. Verder werd via lichte aanpassingen aan het DES-algoritme, het DESL-algoritme gedefinieerd dat met 1848 GE kan worden gebouwd [46]. Daarnaast zijn er ook nog enkele blokcijfers die specifiek voor ingebedde systemen zoals RFIDtags werden ontworpen en die trachten de zeer compacte resultaten van stroomcijfers zoals Grain (1294 GE) te verbeteren zonder de veiligheid in gedrang te brengen. Het cijfer dat hier het best in slaagt is Present met 1570 GE [4] maar er zijn nog veel andere blokcijfers die goede resultaten behalen op het vlak van oppervlaktegebruik zoals TEA [56], HIGHT [28], mCrypton [37], MISTY [40] en SEA [52].

1.3

De Structuur van het eindwerk

In hoofdstuk 2 worden de eerste, ontwerp-onafhankelijke keuzes gemaakt omtrent onder andere het type cijfer en de nodige sleutellengte. Daarna wordt in hoofdstuk 3 de invalshoek van de specifieke implementatie uitgelegd waarbij de veiligheid tegen de meest gekende aanvallen wordt besproken. Vervolgens wordt het blokcijfer EFES (Encryption Function for Embedded Systems) met al zijn deelblokken voorgesteld in hoofdstuk 4. In hoofdstuk 5 worden de ontwerpkeuzes van deze deelblokken en van het blokcijfer EFES in het algemeen gemotiveerd. In hoofdstuk 6 wordt de veiligheid van EFES tegen de aanvallen uit hoofdstuk 3 beschouwd. Vervolgens worden in hoofdstuk 7 de resultaten vergeleken met deze van andere compacte symmetrische cijfers. Tenslotte worden in een besluit de resultaten nog eens samengevat en worden een aantal denkpistes uitgestipt voor verder onderzoek. 8

Hoofdstuk 2

De algemene structuur van het symmetrisch cijfer Ondanks de verschillende voorstellen en mogelijkheden voor zowel stroom- als blokcijfers, is het nog niet duidelijk welk type cijfer het meest geschikt is voor toestellen met beperkte rekencapaciteit zoals RFID-tags. Op het eerste zicht lijken stroomcijfers net iets betere resultaten te boeken op vlak van het aantal Gate Equivalenten dat ze gebruiken. Wel blijkt dit type encryptie vaak problemen te vertonen die de veiligheid van het cijfer kunnen verzwakken. In een eerste deel van dit hoofdstuk wordt er dus gekeken naar welk type cijfer het meest geschikt is voor RFID-toepassingen. Elk blokcijfer bezit ook een sleutellengte. Hoe groter de lengte van de sleutel in bits, hoe veiliger het cijfer, maar hoe meer het kost om deze sleutel te bewaren. Er moet dus een goed afgewogen keuze worden gemaakt tussen de veiligheid die de toepassing vereist en de nood aan een compacte implementatie. Dit gebeurt in het tweede deel van dit hoofdstuk. Verder wordt bij symmetrische encryptie steeds gewerkt met een bepaald geheugen, de toestand van het cijfer genoemd. Dit geheugen wordt elke klokcyclus gewijzigd en ook voor de grootte van dit geheugen moet de ontwerper een beredeneerde keuze maken tussen de kost in hardware en de veiligheid die een bepaalde toestandslengte biedt. Uiteindelijk moet dan een beslissing worden genomen over de algemene structuur van het te ontwerpen cijfer, in functie van de noden bij de specifieke RFID-toepassingen en bijhorende communicatie tussen lezer en tag.

2.1

Keuze tussen stroom- of blokcijfer

Na een literatuurstudie rond symmetrische cryptografie in het algemeen en voor toestellen met beperkte rekencapaciteit zoals RFID-tags in het bijzonder, is het niet meteen duidelijk of stroomcijfer dan wel blokcijfers de beste keuze zijn voor dit type applicaties. De voor- en nadelen van beide structuren ten opzichte van enkele belangrijke vereisten van RFID-tags worden nu verder beschouwd. 9

2. De algemene structuur van het symmetrisch cijfer

2.1.1

Oppervlaktegebruik

Stroomcijfers blijken tot op heden, in het algemeen compacter gemaakt te kunnen worden. Zo is het kleinste cijfer van dit type, Grain [25], met zijn 1284 GE ook algemeen het kleinste symmetrisch cijfer dat tot nu toe gepubliceerd werd. Hier moet wel worden genoteerd dat er met zorg moet worden gehandeld wanneer het aantal Gate Equivalenten tussen verschillende cijfer-implementaties wordt vergeleken. Door gebruik te maken van verschillende bibliotheken kunnen elementen met dezelfde functie mogelijk met meer of minder logische poorten worden ge¨ımplementeerd. Verder moet worden vermeld dat blokcijfers niet echt moeten onderdoen voor stroomcijfers. Zo is er bijvoorbeeld het blokcijfer Present [4] die met 1570 GE wordt ge¨ımplementeerd en dus kleiner is dan veel compacte stroomcijfers.

2.1.2

Veiligheid

In dit deel worden beide type symmetrische cijfers vergeleken op het vlak van de veiligheid die ze in het algemeen kunnen bieden. In een eerste deel gebeurt deze vergelijking op het vlak van hun interne structuur. In een tweede deel gebeurt de vergelijking ten opzichte van de manier waarop de data vercijferen en hoe dit gebruikt wordt in communicatie-protocollen.

Veiligheid van het cijfer Het grootste probleem bij stroomcijfers is dat ze veel minder bestudeerd zijn dan blokcijfers. Hierdoor bezitten stroomcijfers een minder vaste structuur waardoor er na hun publicatie, dikwijls zwakke punten in hun veiligheid ontdekt worden [23]. Dit probleem is onder andere historisch gegroeid door het langdurig gebruik en dus ook de langdurige analyse van het blokcijfer DES als standaard voor symmetrische vercijfering. Dit zorgt er voor dat veel stroomcijfers de fase waar naar aanvallen op het cijfer wordt gezocht (de cryptanalyse fase) niet overleven. Doordat er veel minder gekend is over stroomcijfers en door de verscheidenheid aan architecturen ervan, hebben aanvallers potentieel veel meer mogelijkheden om in het cijferontwerp zwakheden te vinden. Deze aanvallen kunnen dan dikwijls de sleutel vlugger vinden dan wanneer alle mogelijke sleutels exhaustief worden nagegaan. Dit exhaustief zoeken wordt gezien als een trage aanval, de zogenaamde brute force-aanval1 . Zo zijn er al heel wat voorstellen van stroomcijfers voor het eSTREAM-project die zwakke punten vertoonden, waardoor de ontwerpers dikwijls hun cijfer hebben moeten aanpassen [2]. Bij blokcijfers is dit veel minder het geval door hun goed gedefinieerde structuur waarvan de mogelijkheden op het gebied van cryptanalyse beter gekend zijn.

Veiligheid binnen de communicatie-protocollen Een groter probleem bij het gebruik van stroomcijfers bij RFID-toepassingen is de eenvoud waarmee delen van de sleutelstromen kunnen achterhaald worden. Bij stroomcijfers worden de boodschappen namelijk vercijferd door er bit per bit de sleutelstroom bij op te tellen. Wanneer 1 Hier moet worden vermeld dat om na te gaan of een bepaalde sleutel de juiste is, er uiteraard enkele (klaartekst, cijfertekst)-paren van de echte sleutel moeten gekend zijn.

10

Keuze tussen stroom- of blokcijfer

delen van de vercijferde data gekend zijn, kunnen deze bits modulo-2 worden opgeteld bij de bijhorende cijferstroom om zo tot de sleutelstroom te komen. Afhankelijk van de gekozen communicatiemiddelen (zie deel 2.4), kan het vinden van verstuurde data al dan niet eenvoudig zijn. Afhankelijk van het cijfer kan het bekomen van delen van de sleutelstroom natuurlijk een gevaar vormen. Met delen van de sleutelstroom kan een aanvaller mogelijk de sleutel achterhalen. Door ditzelfde principe van modulo-2-optellen bestaat er nog een gevaar bij het gebruik van stroomcijfers. Bij elke communicatie zal namelijk dezelfde sleutelstroom worden gebruikt. Wanneer cijferstromen van twee communicaties worden opgeteld zal de sleutelstroom door het modulo-2-optellen wegvallen. Enkel de modulo-2 optelling van beide datastromen blijft dan over. Wanneer de data niet perfect willekeurig zijn kan een ervaren aanvaller zich hiermee informatie over beide datastromen verschaffen. Dit probleem kan deels worden weggewerkt door gebruik te maken van een IV (Initialisatie Vector)-uitwisselingsprotocol [42] die na elke communicatie een nieuwe IV geeft aan de tag. Deze IV wordt dan samen met de sleutel gebruikt bij het berekenen van een nieuwe sleutelstroom. Hierdoor zullen de sleutelstromen in elke communicatie verschillen. Het gebruik van een IV-uitwisselingsprotocol zorgt jammer genoeg wel dat de communicaties ingewikkelder worden en kan mogelijk zwakheden doen ontstaan in het systeem. Bij blokcijfers vormt dit probleem zich niet daar volledige blokken van bits tegelijk worden versleuteld en dus de uitgangsbits binnen elke blok geen eenduidig verband hebben met de oorspronkelijke data. Ook kan de gebruiker van een blokcijfer indien nodig kiezen tussen verschillende operatiemodes [42] zoals onder andere de Cipher-Block-Chaining-mode (CBCmode) die naast de bits ook de blokken onder elkaar afhankelijk kan maken waardoor het verband tussen de oorspronkelijke en de vercijferde data nog complexer wordt. Verder kan men zich zich hier afvragen of het voor stroomcijfers niet eenvoudiger en compacter is om een vaste sleutelstroom op te slaan in goedkoop ROM-geheugen. De sleutelstroom die bij elke nieuwe communicatie wordt gebruikt is namelijk steeds dezelfde. Voor korte communicaties zoals bij RFID-communicaties zou ROM-geheugen bijgevolg efficiënter kunnen zijn op het vlak van hardware kost. Een stroomcijfer werkt bij korte communicaties namelijk als een one time pad die voor eenzelfde sleutel in elke communicatie dezelfde is.

2.1.3

Flexibiliteit van het cijfer

Het voordeel bij blokcijfers op het vlak van veiligheid, wordt wel een nadeel als het gaat om op een originele manier tot een nieuw ontwerp te komen. Door de minder vaste structuur van stroomcijfers kan men veel meer mogelijkheden beschouwen bij het zoeken naar een compact ontwerp. Dit werd in de inleiding al aangehaald en valt sterk op bij de kandidaat-stroomcijfers van het eSTREAM-project. Ook bestaan stroomcijfers dikwijls uit minder complexe bouwblokken die hierdoor minder oppervlakte gebruiken. Deze bouwblokken vallen dan ook beter te combineren tot een compact en flexibel cijfer. 11


2.1.4

Vermogenverbruik van het cijfer

Een probleem dat zich voordoet bij stroomcijfers is het grote vermogenverbruik dat deze met zich meebrengen. De LFSR’s die worden gebruikt in stroomcijfers om pseudo-willekeurige bitstromen te bekomen verbruiken namelijk een groot vermogen [14]. Dit komt doordat de vele flip-flops van een LFSR sterk met elkaar verbonden zijn. Hierdoor ontstaat een grote parasitaire capaciteit in en tussen elke flip-flop. Deze capaciteit laadt of ontlaadt zich wanneer de waarde van de flip-flop verandert. Bij een LFSR gebeurt dit regelmatig, na elke klokcyclus, omdat de waarde van elke flip-flop in een LFSR dikwijls verandert. Hierdoor gaat veel energie verloren. Bij blokcijfers is dit niet het geval omdat de flip-flops van het geheugen niet rechtstreeks met elkaar verbonden zijn. Voor toepassingen als RFID waar de tag zijn vermogen uit een door de lezer uitgezonden signaal moet halen (zie hoofdstuk 1.1), is het van groot belang dat het vermogenverbruik beperkt blijft. Het gebruik van LFSR’s is dus niet aangeraden. Er bestaan weliswaar LFSR’s die vermogenbesparend werken maar deze zijn niet algemeen bruikbaar voor cryptografische doeleinden [9].

2.1.5

Keuze symmetrisch cijfer

Tabel 2.1 vat de verschillen tussen stroom- en blokcijfers samen. Hier worden de kwaliteiten van het type cijfer voor de verschillende eigenschappen aangeduid op een schaal gaande van −− tot ++.

Eigenschap Oppervlaktegebruik Veiligheid Gebruik van modes Flexibiliteit Complexiteit Vermogenverbruik

Stroomcijfer

Blokcijfer

++ − n.v.t + + −−

+ + ++ − − +

Tabel 2.1: De eigenschappen van stroom- en blokcijfers. Voor RFID-toepassingen lijken de voordelen van stroomcijfers niet op te wegen tegen de nadelen met betrekking tot veiligheid en vermogenverbruik. Gezien de voordelen van blokcijfers op deze domeinen en het niet al te significant verschil in hardware verbruik tussen de twee types symmetrische cijfers, wordt daarom geöpteerd voor het ontwerpen van een blokcijfer. Hierbij kan, indien nodig, het blokcijfer via de Cipher-Feedback-mode (CFB-mode) [42] ook als stroomcijfer worden gebruikt. Het uitgangspunt van dit eindwerk is om een blokcijfer te vinden dat kan worden ge¨ımplementeerd in minder Gate Equivalenten dan het blokcijfer Present, maar toch voldoende veiligheid biedt voor gebruik bij RFID-communicaties. Daarnaast zal ook worden gekeken naar het verschil met het stroomcijfer Grain dat van alle momenteel gepubliceerde stroomcijfers het minst GE gebruikt. 12

Keuze sleutellengte

2.2

Keuze sleutellengte

Bij de keuze van de sleutellengte k van het blokcijfer moet een afweging plaatsvinden tussen aan de ene kant de hardwarekost van de implementatie van het cijfer en aan de andere kant de veiligheid van het cijfer voor de toepassingen waarvoor het ontworpen is. Deze veiligheid moet bovendien niet enkel vandaag kunnen gegarandeerd worden maar ook wanneer het cijfer wordt gebruikt in de toekomst. Hoe groter k, hoe veiliger het cijfer omdat een potentiële aanvaller dan veel meer mogelijk sleutels zal moeten nagaan, alvorens de juiste wordt gevonden. Dit is natuurlijk in de veronderstelling dat het cijfer niet vlugger kan worden gebroken dan wanneer exhaustief elke mogelijke sleutel wordt nagegaan. Maar een grote k zorgt er ook voor dat een groter aantal geheugenelementen of flip-flops nodig zijn om de toestand van de sleutel bij te houden. Eerst worden de resultaten van de bestaande onderzoeken naar veilige sleutellengtes uit de doeken gedaan om in een tweede deel de gewijzigde aanpak bij het zoeken naar de sleutellengte van het blokcijfer uit te leggen.

2.2.1

De bestaande onderzoeken

In [36] en vooral in [35] gaan de auteurs, voor een bepaalde sleutellengte en stand van technologie, na hoe lang het zal duren om de juiste sleutel van een symmetrisch cijfer te vinden, wanneer alle sleutels exhaustief worden nagegaan. In functie van de snelheid waarmee één sleutel kan worden getest met de gekozen technologie, kan worden nagegaan hoe lang het zal duren om alle sleutels af te lopen en dus met zekerheid de juist sleutel te vinden. In zijn paper stelt Lenstra [35] dat met de technologie uit 1982 het toen veel gebruikte DES-cijfer met een effectieve sleutellengte van 56 bit, in dat jaar als veilig kon worden beschouwd. Om het concept ‘veilig’ eenduidig te definiëren wordt de term dollardays ge¨ıntroduceerd. Deze eenheid wordt gedefinieerd als het product van de investering in hardware (in dollar) nodig om een sleutel te kraken en de tijd (in dagen) die deze hardware daarvoor nodig heeft. Voor volledig paralleliseerbare processoren is deze waarde een constante en kunnen er dus in functie van de middelen, dollars gespaard worden ten koste van tijd en omgekeerd. Er moet worden opgemerkt dat het kraken van één sleutel bij exhaustief zoeken, de taak om een volgende sleutel te kraken niet vereenvoudigt. Voor het DES-cijfer waren er in 1982, 40 miljoen dollardays nodig om één sleutel te kraken en deze waarde wordt in de paper van Lenstra als de norm voor ‘veilig’ gebruikt. In diezelfde paper stelt Lenstra dat een sleutellengte van 80 bit een symmetrisch cijfer veilig zou moeten houden tot in het jaar 2018. Hiervoor maakt hij een schatting van de evolutie van de technologie over de jaren heen en dus van de investeringskost, door gebruik te maken van de wet van Moore. Deze ‘wet’ voorspelt dat om de 18 maanden een verdubbeling van de rekenkracht (of halvering van de kost) van computers zal plaatsvinden.

2.2.2

De gewijzigde aanpak

Omdat de paper van Lenstra wat achterhaald is wordt het model aangepast en hernieuwd. Zo moet de definitie van veiligheid afhankelijk zijn van de beoogde toepassing en moet de gebruikte technologie bij het zoeken van de sleutel aangepast worden aan wat vandaag beschikbaar is. 13


Definitie van veiligheid De veiligheid wordt nu gedefinieerd in functie van het aantal dollarday die een aanvaller maximaal zou willen investeren in tijd en hardware om een sleutel voor een bepaalde toepassing te bemachtigen, zodat hij er een zekere winst uit kan halen. Voor RFID-toepassingen waarvoor het cijfer zo compact en dus goedkoop mogelijk moet zijn neemt men als norm dat de waarde van een product dat door het cijfer en dus de sleutel moet worden beveiligd niet groter is dan US$ 3000 (of e 2000). Ook wordt een periode van maximaal twee jaar vastgelegd, waarin een product met eenzelfde sleutel beveiligd moet blijven. Wil men over langere periodes werken dan zal de sleutel op tijd moeten worden vervangen of dan zal de prijslimiet van de te beveiligen producten moeten verlagen. Analoog gaat een product met een waarde groter dan US$ 3000 minder lang als ‘veilig’ kunnen worden beschouwd. Dit geeft dat de aanvaller maximaal US$ 3000 · 2 jaar · 365 dagen/jaar = 2190 · 103 dollardays zal willen investeren per te kraken sleutel.

De technologische referentie Voor de technologische referentie wordt op zoek gegaan naar hedendaagse technologie die gespecialiseerd is in het kraken van cryptografische cijfers. Er wordt gekozen voor de CAPACABANA multiprocessor [1], gespecialiseerd in het kraken van paralleliseerbare cijfers zoals blokcijfers. Op 15 maart 2007 vond deze processor in 6,4 dagen, voor een kostprijs van US$ 10 000, de 56 bit sleutel van een DES-cijfer. Dit geeft met deze technologie, een vaste investeringskost van 64 000 dollardays per 56 bit sleutel.

Het aangepast model Gebruik makend van de wet van Moore en van het feit dat per definitie bij elke extra bit die de sleutel langer wordt, het aantal berekeningen nodig om hem te vinden verdubbelt, wordt een formule afgeleid voor de nodige sleutellengte van het cijfer in functie van de gewenste levensduur. Dit geeft dat om in het jaar y een k bit sleutel te kraken, de nodige investering gelijk zal zijn aan:

64 · 103 · 2k−56 2

2(y−2007) 3

dollardays

(2.1)

Dit bedrag wordt gelijk gesteld aan de maximale investering die een aanvaller gaat willen maken om een sleutel van een door het cijfer beveiligd product te bekomen. Voor RFID-toepassingen waarvoor het te ontwerpen cijfer moet dienen is dit zoals vermeld 2190 ∗ 103 dollardays. Uiteindelijk geeft dit de formule van de sleutellengte k in functie van de levensduur van het cijfer: 14

Keuze sleutellengte

k = 56 + log2

2190 · 103 2 + (y − 2007) 64 · 103 3

2 = 61.1 + (y − 2007) 3

(2.2) (2.3)

Wetende dat het enkele jaren kan duren eer een cijfer als veilig wordt beschouwd door de cryptologische gemeenschap en dat het cijfer toch enkele jaren bruikbaar moet zijn wordt er gekozen om een cijfer te ontwerpen dat tot in het jaar 2028 (20 jaar) veilig moet zijn. Als deze waarde dan in de formule wordt ingevuld, wordt een nodige sleutellengte k van 75 bit bekomen. Dit is een veel beter en meer accuraat resultaat dan de 82 bit sleutel die volgens Lenstra in zijn paper nodig zou zijn om een cijfer tot in 2028 te beveiligen. Dit komt doordat de gewenste veiligheid hier veel beter gedefinieerd is door deze toepassingsgericht te maken en doordat het technologisch referentiepunt veel actueler gekozen werd. De vereenvoudigingen in het model In formule (2.2) werd uiteraard niet alles in rekening gebracht. Er bestaan een hele reeks varianten op de brute force aanval waar exhaustief wordt gezocht naar de sleutel en deze worden generische aanvallen genoemd. Deze aanvallen zoals de TimeMemory data Trade-Off (TMTO) aanvallen gaan de nodige rekentijd om alle sleutels na te gaan verkleinen [26, 30]. Ze doen dit door op voorhand klaarteksten te vercijferen met verschillende sleutels en het resultaat vervolgens in een geheugen op te slaan. In functie van het aantal klaarteksten en het aantal sleutels die op deze manier worden opgeslaan, kan de rekentijd van het zoeken naar een welbepaalde sleutel al dan niet sterk worden verkleind. Bij het afleiden van vergelijking 2.2 werd enkel rekening gehouden met de brute force aanval. Er wordt aangenomen dat voor de gekozen maximale prijs van een te beveiligen product, de investering in snel geheugen om de rekentijd te verkleinen, niet rendabel kan zijn. Dit zou weliswaar in de toekomst verder kunnen worden onderzocht. Ook de inflatie werd bij het bekomen van de vorige resultaten niet in rekening gebracht. Er wordt wel aangenomen dat de inflatie weinig verschil zal maken: wanneer de prijs van de hardware stijgt, wordt aangenomen dat de prijs van de te beveiligen producten ongeveer evenredig zal stijgen. Verder werd geen rekening gehouden met de opportuniteitskost van de tijd. Wanneer een aanvaller namelijk een investering maakt in hardware en in tijd zal hij het ge¨ınvesteerde geld in die tijd niet op een andere manier kunnen aanwenden. Het geld dat hij investeert in het breken van een sleutel zou hij bijvoorbeeld kunnen investeren op de beurs of beleggen in bankproducten. Hiermee zou hij mogelijk meer winst kunnen maken dan bij het kraken van een sleutel ter waarde van maximum US$ 3000. Dit brengt dus, bij de keuze van de sleutellengte, een extra veiligheidsmarge voor de ontwerper met zich mee. Ook zal, wanneer slechts één sleutel wordt gekraakt, de maximale investering gebruikt om de formule af te leiden kloppen. Maar bij het breken van een tweede sleutel zal de investering in hardware al gebeurd zijn. Hierbij zal dan enkel een vaste tijdskost plaats vinden. Formule (2.2) houdt hier geen rekening mee. Er wordt aangenomen dat dit geen probleem vormt, doordat 15


pas na het laatste levensjaar van het cijfer investeren in tijd en hardware rendabel zal zijn voor een aanvaller. Een aanvaller die vóór dat jaar zal investeren gaat een veel grotere investering moeten maken. Per extra sleutel die de aanvaller wil kraken, gaat hij zijn investering een bepaalde periode moeten vervroegen om zo genoeg bruikbare rekentijd te hebben eer het cijfer onveilig wordt verklaard. Hierdoor wordt de kost van de hardware investering per extra sleutel groter en er wordt aangenomen dat deze groter zal zijn dan de winst die het kraken van de extra sleutel zal opleveren. Ten slotte moet worden genoteerd dat het verschil in snelheid tussen het evalueren van een sleutel voor de DES en voor het eigen ontwerp door de CAPACABANA niet in rekening is gebracht. Dit verschil zal weliswaar weinig veranderen aan de uiteindelijke lengte die de sleutel moet hebben. Zo zal wanneer het ontworpen cijfer twee keer zo vlug werkt als DES, de sleutellengte maar met 1 bit moeten worden verhoogd [35]. De sleutellengte van het blokcijfer Doordat een 75 bit sleutel geen veel voorkomende sleutellengte is en om een grotere zekerheidsmarge in te bouwen wordt beslist om een sleutellengte van 80 bit te handhaven. Gebruik makend van de inverse van vergelijking (2.2) kan berekend worden dat het cijfer daarmee theoretisch veilig zal zijn tot in 2035. Een keuze van een 80 bit sleutel wordt eveneens door het ECRYPT project als veilig verondersteld voor kortetermijnbeveiliging tegen grote organisaties en voor langetermijnbeveiliging tegen kleinere organisaties [6]. Ook zal een standaardisatie van de sleutellengte op 80 bit voor alle cijfers gebruikt in dit type toepassingen, de sleutel-beheersystemen, die heel complex kunnen worden bij symmetrische cryptografie, vereenvoudigen.

2.3

Toestands- en bloklengte

De keuze van de toestandslengte is, in tegenstelling tot die van de sleutellengte, veel minder bestudeerd. Wel is duidelijk dat ook hier een afweging moet plaatsvinden tussen een grotere toestandslengte, die een grotere veiligheid kan garanderen en een kleinere toestandslengte, die de kost in hardware klein houdt. Voor blokcijfers komt de toestandslengte overeen met de bloklengte en deze wordt elke ronde gewijzigd en moet dus worden bijgehouden in het geheugen. Voor een grote bloklengte n en een goed cijferontwerp zal een aanvaller 2n (klaartekst, cijfertekst)-paren nodig hebben alvorens hij voor alle mogelijke cijferteksten de bijhorende klaartekst gaat kunnen terugvinden. Een aanvaller n kan eveneens gebruik maken van de birthday paradox om met slechts 2 2 (klaartekst, cijfertekst)n paren en nog eens 2 2 cijferteksten, met een grote kans voor één van deze cijferteksten de bijhorende klaartekst te kunnen vinden [42]. Algemeen wordt ook aangenomen dat de bloklengte niet te klein mag zijn ten opzichte van de sleutellengte. Daar n = 64 dikwijls wordt gebruikt bij het beveiligen van ingebedde systemen zoals RFIDcommunicaties en dus min of meer gestandaardiseerd is, wordt er gekozen om deze lengte eveneens te handhaven. Verder is het voor de toepassingen waarvoor het cijfer ontworpen n n is, zeer onwaarschijnlijk dat 2 2 (klaartekst, cijfertekst)-paren en nog eens 2 2 cijferteksten kunnen worden bekomen. De RFID-tags zullen namelijk voor een bepaalde sleutel, slechts een 16

De algemene structuur

levensduur van maximaal twee jaar hebben. In die tijd is het onwaarschijnlijk dat zoveel data worden vercijferd omdat de producten die de tags beveiligen niet dikwijls een communicatie aangaan. Verder is het nog minder waarschijnlijk dat een aanvaller zoveel oorspronkelijke data of klaarteksten met bijhorende cijferteksten zal kunnen bemachtigen. Wanneer, bij de keuze van een RFID-communicatieprotocol, blokken voorkomen die kleiner of groter dan n bit zijn, worden ze aangevuld met willekeurige data om alsnog blokken van n bit te bekomen.

2.4


In dit deel wordt op zoek gegaan naar de structuur van het te ontwerpen blokcijfer. Zoals gezien in de inleiding bestaan er hiervoor twee type structuren. Aan de ene kant zijn er de Feistel-structuren waarbij dezelfde, kleinere, functies kunnen worden gebruikt bij zowel decryptie als encryptie en die op deze manier tot een besparing in hardware kunnen leiden. Hierbij moet wel in rekening gebracht worden dat er om de deelblokken bij elkaar op te tellen, extra hardware nodig is in de vorm van modulo-2-optellers of XOR-poorten. Aan de andere kant zijn er de SP-netwerken waar de encryptiefuncties groter zijn doordat meer bits tegelijk in elke ronde worden verwerkt. Om ook decryptie te implementeren zal er een extra kost in hardware zijn doordat hiervoor de inverse van de substitutie- en permutatiefuncties nodig is. Om een beslissing te nemen over de structuur van het cijfer wordt eerst wat dieper ingegaan op wat van een blokcijfer voor RFID-tags verwacht wordt. Eerst worden RFIDcommunicatieprotocollen besproken. Daarna wordt gekeken naar welke eigenschappen het cijfer moet bezitten om deze protocollen te kunnen toepassen bij lage kost RFID-toepassingen. Hieruit wordt vervolgens de algemene structuur van het te ontwerpen blokcijfer afgeleid. In een laatste deel worden verschillende aspecten van communicatieprotocollen besproken, waarvoor het blokcijfer een oplossing kan bieden. RFID-communicatieprotocollen RFID-communicatieprotocollen zijn de afspraken die worden gemaakt over hoe de RFID-tag op een veilige manier gaat communiceren met de lezer. Het gaat hier niet over hoe de data moet worden versleuteld maar over de manier waarop de tag en de lezer data gaan uitwisselen. In het bijzonder gaat het over hoe ze elkaar kunnen identificeren en vooral authenticeren. Deze protocollen leggen dan voorwaarden op aan het cijfer. Men wil namelijk dat het cijfer voor allerhande toepassingen van RFID-tags kan worden gebruikt en dat het bijgevolg geen beperkingen gaat opleggen aan de keuze van het te gebruiken protocol. Het cijfer moet dus kunnen worden gebruikt bij de meest voorkomende en complexe protocollen voor RFIDcommunicaties, zoals bijvoorbeeld de Electronic Product Code (EPC)[49] of nog de ISO/IEC 18000-familie van standaarden [32]. De belangrijkste voorwaarde hiervoor is dat het cijfer wederzijdse authenticatie via challengeresponse-protocollen moet toelaten2 . Het cijfer van de tag moet bijgevolg de mogelijkheid 2 Zie bijvoorbeeld de ISO/IEC 9798-2-standaard voor challenge-response-protocollen gebruik makend van symmetrische encryptie [31].

17


bieden om zowel zichzelf te kunnen authenticeren aan een lezer om vervalsing tegen te gaan als om de lezer te kunnen authenticeren om zo de privacy problemen die gepaard gaan met RFID-tags tegen te gaan. Voorwaarden opgelegd door RFID-communicatieprotocollen Het implementeren van een decryptiemechanisme naast een encryptiemechanisme brengt veel problemen met zich mee, onder andere een extra kost in hardware. Zo moeten inverse functies en extra controle logica worden voorzien. Daar het cijfer wordt ontworpen voor gebruik bij lage kost RFID-toepassingen, kunnen we er van uitgaan dat behalve voor de sleutel, een tag geen wijzigbaar geheugen heeft. De lezer zal namelijk nooit geheime informatie naar de tag sturen aangezien het enige doel van elke communicatie het sturen van de identiteit (ID) van de tag naar de lezer zal zijn. Uit de verschillende challenge-respons-protocollen gebruikt voor wederzijdse authenticatie die terug te vinden zijn in de literatuur blijkt dat hiervoor een cijfer met enkel een encryptiemechanisme, maar zonder decryptie mogelijkheden voldoende is [19, 18, 20, 53]. Doordat de tag geen data moet ontvangen, kan de authenticatie van de lezer door de tag gebeuren door de lezer data die de tag ter beschikking heeft te laten encrypteren en dit dan naar de tag te sturen. Deze kan dan de lezer authenticeren door na te gaan of de ontvangen encryptie wel met de gedeelde sleutel gebeurd is door zelf zijn versie van de data te encrypteren met zijn sleutel en het resultaat te vergelijken met de ontvangen encryptie. De lezer zal daarentegen wel decryptie moeten kunnen toepassen om de verstuurde identiteit te kunnen achterhalen. Dit principe wordt authenticated encryption genoemd. Aangezien voor RFID-toepassingen een cijfer op een tag die enkel het encryptiemechanisme implementeert voldoende is om wederzijdse authenticatie te verzekeren, wordt bijgevolg gekozen om enkel het encryptiedeel te voorzien in het cijfer voor de RFID-tag. De structuur van het blokcijfer Wanneer enkel encryptie wordt ge¨ımplementeerd, biedt een Feistel-structuur geen meerwaarde en kan ze zelfs een negatieve invloed op het hardwaregebruik hebben door de extra kost in hardware van de optelling van de deelblokken in elke ronde. Een SP-netwerk wordt dus op het eerste zicht verkozen. Helaas heeft dit type structuur een grote kost in hardware door de grotere substitutie- en diffusiefuncties die nodig zijn. Dit kan wel deels worden weggewerkt door elke ronde over verschillende klokcycli te spreiden en in elke cyclus slechts een deel van de toestandbits door de cryptografische functies te sturen. Doordat dan in elke cyclus slechts een deel van de toestandbits wordt verwerkt, kan de substitutiefunctie in minder S-boxen worden ge¨ımplementeerd en zal deze dus minder hardware nodig hebben. Hiervoor moeten dan wel multiplexers (MUX’en) worden gebruikt zoals weergegeven in figuur 2.1 waar het aantal S-boxen p gehalveerd is ten opzichte van het oorspronkelijke aantal u, door gebruik te maken van multiplexers met twee ingangen. Helaas brengen deze multiplexers zelf ook een niet te onderschatten hardwarekost met zich mee, zeker wanneer het aantal cycli per ronde en dus de controlelogica in de vorm van de multiplexers groot wordt. Geen van beide bestaande structuren biedt dus een ideale oplossing voor cryptografische cijfers voor RFID-toepassingen, maar ze bevatten wel allebei elementen die de hardware-efficiëntie 18


Figuur 2.1: SP-netwerk gebruik makend van multiplexers met twee ingangen om de grootte van de substitutie- en diffusiefuncties te halveren.

kunnen verbeteren. Feistel-structuren zijn namelijk een variant op SP-netwerken met multiplexers. In Feistelstructuren wordt geen gebruik gemaakt van multiplexers maar worden deze vervangen door een permutatie over de toestandsbits. Op die manier moeten er minder niet-lineaire functies worden gebruikt, zonder de kost van de multiplexers te moeten betalen. In elke ronde worden door de permutatie steeds andere toestandsbits door de niet-lineaire functies gestuurd. Om tussen de gewijzigde en niet gewijzigde delen van de toestand diffusie te hebben wordt gebruik gemaakt van een lineaire combinatie van alle toestandsbits. Bij Feistel-structuren komt dit in de vorm van een modulo-2-optelling van de verschillende delen van de toestand zoals reeds vermeld in de inleiding en voorgesteld in figuur 1.4. De permutatie komt in Feistel-structuren dikwijls voor in de vorm van een rotatie over de toestandsbits. Het te ontwerpen cijfer gaat nu datzelfde principe toepassen door een rotatie te gebruiken om te bepalen welke bits door de substitutiefunctie worden gestuurd. De diffusie over de verschillende bits wordt dan op twee manieren bekomen. Ten eerste gaat wordt geroteerd over een aantal bits d. Dit aantal is geen deler van de toestandslengte n. Zo zullen nooit dezelfde groepen bits tegelijk door de substitutiefunctie gaan en wordt daardoor de invloed van de bits over de verschillende cycli heen verspreid over de volledige toestand van het cijfer. Ten tweede worden de bits die door de substitutiefunctie worden gestuurd daarna lineair gecombineerd om tussen deze bits diffusie te bekomen. Deze nieuwe structuur wordt voorgesteld in figuur 2.2. Doordat een rotatie zuiver via bedrading kan worden ge¨ımplementeerd zal het in tegenstelling tot multiplexers geen hardwarekost met zich meebrengen. De lineaire combinatie zal wel een extra hardwarekost vormen, maar deze is klein ten opzichte van de kost van een grotere substitutie functie of de kost van multiplexers. Hoofdstuk 4 gaat verder in op deze structuur door de specifieke implementatie van het cijfer voor te stellen. Verder moet bij dit type structuur met veel zorg worden nagegaan of de veiligheid niet in gedrang komt. In hoofdstuk 6 wordt hier dieper op ingegaan. 19


Figuur 2.2: De algemene structuur van het te ontwerpen blokcijfer.

Gebruik van het blokcijfer binnen RFID-communicatieprotocollen Nu de algemene structuur van het cijfer bepaald is, wordt nog kort gekeken naar andere voorwaarden die de protocollen met zich meebrengen en waarin het cijfer een belangrijke rol kan spelen. Elke tag deelt een unieke sleutel met de database waaraan de lezers verbonden zijn. Om botsingen te vermijden moeten de verschillende tags de lezer kunnen aangeven welke sleutel ze met de database delen, zonder hiervoor onbeveiligd hun identiteit te moeten versturen. Dit vormt geen bijkomend probleem wanneer een cryptografisch cijfer op de tag aanwezig is vermits hiervoor technieken bestaan zoals singularisatie [54, 34]. Deze techniek gaat, via een pseudo-identiteit (pseudo-ID) die onbeveiligd wordt verstuurd naar een lezer, de database van deze lezer toelaten de specifieke tag en bijhorende sleutel te onderscheiden van andere tags in de omgeving van de lezer, zonder dat de tag zijn echte identiteit moet vrijgeven. Deze pseudo-ID die in de database gelinkt is met de sleutel van de bijhorende tag, wordt na elke communicatie in functie van de sleutel via het cijfer gewijzigd in zowel de tag als de database. Op die manier is deze pseudo-ID nooit dezelfde en onvoorspelbaar voor een buitenstaander zodat hij de tag niet kan traceren. Een ander probleem dat de meeste wederzijdse communicatie-protocollen met zich meebrengen is de nood aan een generator van willekeurige getallen in zowel de lezer als de tag. Dergelijke generator brengt uiteraard een extra kost in hardware met zich mee. Om dit probleem te omzeilen kan de ontwerper gebruik maken van een generator van pseudo-willekeurige getallen gebaseerd op een willekeurig getal dat wordt meegegeven aan de tag bij zijn initialisatie. De generator van de tag maakt dan gebruik van het cijfer om een reeks pseudo-willekeurige getallen te bekomen uit dit initiële willekeurig getal. Hiervoor wordt het resultaat van de vorige encryptie opgeteld aan het vorige willekeurige getal [53]. Voor de gekozen structuur zal het cijfer dus geen beperkingen opleggen wanneer het wordt gebruikt in RFID-communicaties en zal het cijfer zelfs kunnen gebruikt worden om de meest ingewikkelde protocollen te implementeren zonder dat hiervoor een te grote extra kost in hardware moet betaald worden. 20

Hoofdstuk 3

De invalshoek van het ontwerp Nadat de algemene eigenschappen en de structuur van het cijfer zijn bepaald, moet worden gezocht naar een specifieke architectuur die het cijfer veilig moet maken tegen niet-generische aanvallen. Niet-generische aanvallen zijn aanvallen die de inwendige architectuur van het cijfer gaan uitbuiten. De architectuur moet dus zo opgebouwd zijn dat ze geen aanvallen mogelijk maakt die toelaten de sleutel vlugger te vinden dan wanneer er exhaustief naar gezocht wordt. De verschillende cryptografische bouwblokken van de architectuur moeten hiervoor zorgen. Zo moet een rotatie, verschillende S-boxen die samen de substitutiefunctie vormen en een lineaire combinatie die zorgt voor extra diffusie worden gevonden (zie hoofdstuk 2.4). De meest voorkomende aanvallen op de inwendige architectuur van blokcijfers maken gebruik van differentiële cryptanalyse die Biham en Shamir ontwikkelden [11, 12] en lineaire cryptanalyse die Matsui ontwikkelde [38]. Niettegenstaande nog veel meer andere type aanvallen op blokcijfers bestaan, zijn dit de twee belangrijkste en efficiëntste en worden ze dan ook gebruikt als invalshoek voor het ontwerpen van de architectuur van het cijfer. Eerst worden de differentiële en lineaire aanvallen bondig uitgelegd en worden de eigenschappen van het cijfer die ze uitbuiten aangekaart. Achteraf wordt dan afgeleid hoe de architectuur van het cijfer op een veilige en compacte manier kan worden ge¨ımplementeerd, dankzij oppervlakteefficiënte en veilige bouwblokken.

3.1

Differenti¨ ele cryptanalyse

Differentiële cryptanalyse is een type van gekozen-klaartekstaanvallen die kan worden toegepast op allerhande blokcijfers. Eerst wordt het algemeen principe van deze aanvallen uitgelegd. Daarna wordt uitgelegd hoe een aanvaller op deze wijze informatie over de sleutel kan bemachtigen. Uiteindelijk worden de voorwaarden tot een efficiënte aanval bepaald.

3.1.1

Het principe van differenti¨ ele cryptanalyse

Zoals bondig uitgelegd in [27] proberen differentiële aanvallen gebruik te maken van verbanden tussen de verschilwaarde van twee ingangen van het cijfer en de verschilwaarden van de 21

3. De invalshoek van het ontwerp

bijhorende uitgangen. Verschilwaarden betekent in de meeste gevallen, het modulo-2-optellen of het door een exclusive-or -poort (XOR-poort) sturen van de signalen. Ook voor het cijfer EFES zal met de verschilwaarde het modulo-2-optellen bedoeld worden. Het modulo-2-optellen van de deelsleutel Ki met de toestand van het cijfer die in elke ronde van de encryptie voorkomt kan hierdoor namelijk omzeild worden. Bij gebruik van dit type verschilwaarden zal de deelsleutel zichzelf optellen en dus wegvallen: Stel ∆X = [∆x1 ∆x2 ∆x3 . . . ∆xn ] de n bit verschilwaarde van de n bit invoer X 0 en X 00 van een ronde van het cijfer en ⊕ de exclusive-or -bewerking:

∆X = X 0 ⊕ X 00

(3.1)

Met:

∆Xi = x0i ⊕ x00i

∀ bits i ∈ X 0 en X 00

(3.2)

Door de eigenschappen van de exclusive-or -bewerking wordt dan bekomen dat:

(X 0 ⊕ Ki ) ⊕ (X 00 ⊕ Ki ) = X 0 ⊕ X 00 ⊕ Ki ⊕ Ki = X 0 ⊕ X 00 = ∆X

(3.3)

Deze aanvalsmethode brengt gelukkig ook een nadeel met zich mee. Een niet-lineaire substitutiefunctie in de vorm van een aantal parallel werkende S-boxen treedt namelijk elke ronde op. Dit zorgt er voor dat bij het toepassen van dergelijke ronde op de invoer verschilwaarde, het resultaat verschillend is van de verschilwaarde van het toepassen van de ronde op de twee ingangen apart. Hierdoor ontstaat, wanneer enkel de ingangsverschilwaarde gekend is, een onzekerheid over de uitkomst van de verschilwaarde aan de uitgang van elke ronde. Een (∆X, ∆Y )-paar, met ∆Y de uitgangsverschilwaarde, zal dus slechts met een bepaalde kans optreden. De ontwerper gaat dit gebruiken om dit type aanval tegen te werken. Stel ∆Y = [∆y1 ∆y2 ∆y3 . . . ∆yn ] de verschilwaarden van de uitgang van de n bit ingang X 0 en X 00 na één ronde: ∆Y = Y 0 ⊕ Y 00

(3.4)

Met:

∆Yi = yi0 ⊕ yi00

∀ bits i ∈ Y 0 en Y 00

(3.5)

Dan kan worden aangetoond dat voor een niet-lineaire functie S : GF (2n ) → GF (2n ) :

S(X 0 ) ⊕ S(X 00 ) = ∆Y 6= S(∆X) 22

(3.6)

Differentiële cryptanalyse

Hoewel de data invoer bij een gekozen-klaartekstaanval vrij kan worden gekozen (en dus ook het verschil van twee invoeren), worden deze vóór de eerste effectieve ronde al modulo-2-opgeteld met de eerste deelsleutel van het cijfer. Hierdoor is enkel nog de verschilwaarde aan het begin van de eerste ronde gekend en niet de ingangen zelf. Een aanvaller zal dus nooit met zekerheid de uitgangen kunnen bepalen.

3.1.2

De uitwerking van een differenti¨ ele aanval

De aanvaller zal desalniettemin trachten aan de hand van de eigenschappen van de S-boxen en dus van de niet-lineaire functies van het cijfer, n bit ingangsverschilwaarde te zoeken die met een grote kans een bepaalde n bit uitgangsverschilwaarde zal geven over één ronde van het cijfer. Daarna zal hij trachten een combinatie van ingangs-uitgangsverschilwaarden te vinden over alle rondes heen waarbij de ingangsverschilwaarde van een ronde de uitgangsverschilwaarde van de vorige ronde is, tot aan de ingang van de laatste ronde. Het paar (∆X, ∆Y ) bestaande uit de gekozen klaartekst verschilwaarde ∆X en de verschilwaarde ∆Y aan de ingang van de laatste ronde wordt een differentieel genoemd en het pad tussen deze uiteinden over de verschillende rondes heen, een differentieelkarakteristiek. Hierbij is de kans dat deze karakteristiek zich voordoet gelijk aan het product van de kansen dat een karakteristiek optreedt over één ronde. Gebruik makend van een dergelijke differentieelkarakteristiek met een relatief grote kans van optreden en de uitgang van de laatste ronde kan een aanvaller informatie trachten te bemachtigen over de deelsleutel gebruikt in de laatste ronde. Die informatie kan dan mogelijk leiden tot het vinden van de originele sleutel en dus het kraken van het cijfer. De bits van de deelsleutel van de laatste ronde die overeenkomen met de posities in ∆Y van de differentieel die niet nul zijn worden door de aanvaller nader beschouwd. Het cijfertekstpaar (C 0 , C 00 ), horende bij de gekozen klaartekstverschilwaarde ∆X, wordt exclusief opgeteld met alle mogelijke combinaties van deze bits. Hierbij krijgen de bits uit de deelsleutel die niet worden beschouwd een nul waarde. Daarna wordt het resultaat omgekeerd door de S-boxen gestuurd om de n bit combinaties Z 0 en Z 00 te bekomen. Dit gebeurt voor alle beschikbare klaarteksten bijhorende cijfertekstparen. Voor elke combinatie van de specifieke deelsleutelbits wordt dan telkens het resultaat van de verschilwaarde van Z 0 en Z 00 overeenkomt met de gekozen differentieel, een teller verhoogd. Dus wanneer voor de deelsleutelbitcombinatie Ksub , S −1 : GF (2n ) → GF (2n ) de inverse van de niet-lineaire S-boxfunctie en voor:

Z 0 = S −1 (C 0 ⊕ Ksub ) 00

Z =S

−1

00

(C ⊕ Ksub )

(3.7) (3.8)

Geldt dat:

Z 0 ⊕ Z 00 = ∆Y

(3.9)

Dan wordt de teller van de combinatie Ksub verhoogd. 23


De combinatie van deze bits die na het aflopen van alle klaarteksten cijfertekstparen het meest overeen kwam met de differentieel (en dus de hoogste waarde op zijn teller staan heeft) wordt verondersteld met grote kans de juiste deelsleutelbits te bevatten. Deze veronderstelling klopt: wanneer het aantal gekende klaartekstparen groot genoeg is ten opzichte van de kans dat een differentieel optreedt, kan verondersteld worden dat de gekozen differentieel een paar keer zal optreden. Bijgevolg gaat de goede deelsleutelbitcombinatie kunnen onderscheiden worden van de slechte. Wanneer de differentieel optreedt, zal de juiste combinatie namelijk altijd de teller doen verhogen, terwijl bij foute combinaties de teller niet wordt verhoogd. Wanneer de differentieel niet optreedt kan men veronderstellen dat de combinaties van de deelsleutelbits die toch tot de juiste waarde ∆Z = ∆Y kunnen leiden, een willekeurige verdeling hebben. De combinatie waarvan de teller het grootst is na afloop van alle gekende paren, zal bijgevolg met een grote kans de juiste zijn.

3.1.3

De effici¨ entie van differenti¨ ele cryptanalyse

Om realistische resultaten te bekomen moet de aanvaller minstens evenveel gekozen klaarteksten bijhorende cijfertekstparen hebben als een enkele keer de inverse van de kans dat de gekozen differentieel optreedt. Op die manier zal de differentieel met een hoge kans meer dan één keer optreden en kunnen de foute deelsleutelbitcombinaties van de juiste worden onderscheiden. Met Nd het nodige aantal paren om differentiële cryptanalyse te kunnen toepassen, c een kleine constante groter dan 1 en DP de kans van de differentieel met de grootste kans van optreden, wordt gesteld dat :

Nd ≈

c DP

(3.10)

Het is duidelijk dat hoe meer S-boxen worden betrokken in de differentieelkarakteristiek van de gekozen differentieel, hoe kleiner de kans van optreden van de karakteristiek zal zijn. Deze S-boxen hebben een niet-nul verschilwaarde aan hun ingang. De aanvaller moet dus op zoek gaan naar niet-triviale differentieelkarakteristieken die zo weinig mogelijk actieve S-boxen, zoals deze S-boxen worden genoemd, bevatten. De Markovian cipher assumption [45] toont namelijk aan dat wanneer de S-boxen onafhankelijk worden beschouwd:

DP =

s Y

DPi

(3.11)

i=1

Met s het aantal actieve S-boxen in de differentieelkarakteristiek en DPi de kans dat de bepaalde differentieel over deze S-box plaatsvindt. Belangrijk te melden is dat de onafhankelijkheid van de S-boxen in elke differentieelkarakteristiek een benadering is die niet noodzakelijk altijd van toepassing is. DP is dus een schatting. Deze schatting blijkt weliswaar meestal een goede te zijn [27]. Een laatste opmerking betreft het feit dat er verschillende differentieelkarakteristieken kunnen bestaan die tot dezelfde differentieel leiden. Deze kunnen dan mogelijk gecombineerd worden 24

Lineaire cryptanalyse

zodat de kans dat de differentieel optreedt groter kan zijn dan DP en dus het nodige aantal paren, Nd , kleiner. Het is bijgevolg belangrijk om een marge in te bouwen in elk cijfer om zo mogelijke problemen te vermijden.

3.2


Naast differentiële cryptanalyse kan ook lineaire cryptanalyse worden toegepast op alle type blokcijfers. Het gaat hier echter niet om een gekozen-klaartekstaanval maar een gekendeklaartekstaanval. Eerst wordt het algemeen principe van deze aanvallen uitgelegd. Daarna wordt uitgelegd hoe een aanvaller met deze aanval informatie over de sleutel kan bemachtigen. Uiteindelijk worden de voorwaarden tot een efficiënte aanval bepaald.

3.2.1

Het principe van lineaire cryptanalyse

Zoals Heys het goed uitlegt [27] probeert een aanvaller bij dit type aanvallen delen van het cijfer te lineariseren over GF (2) of dus gebruik makend van exclusive-or -optellingen. Er wordt op zoek gegaan naar een uitdrukkingen van de uitvoer van de rondes van het cijfer in functie van de invoer. Hierbij moet de niet-lineaire substitutie dus worden gelineariseerd. De uitdrukking die men wil bekomen met ΓX = [X1 X2 X3 . . . Xn ] een vector van ingangselementen en ΓY = [Y1 Y2 Y3 . . . Yn ] een vector van uitgangselementen van de S-boxen in elke ronde, is van de vorm:

X1 ⊕ X2 ⊕ . . . ⊕ Xn ⊕ Y1 ⊕ Y2 ⊕ . . . ⊕ Yn = 0

(3.12)

Net doordat de S-boxen per definitie niet-lineair zijn, zullen de lineaire benaderingen uit de vorige vergelijking met een kans van ongeveer 50% optreden. Hoe minder de componenten van het cijfer zich niet-lineair gedragen, hoe meer een lineaire benadering van deze vorm zal aanleunen bij de echte uitdrukking van het cijfer. Hierdoor zal de lineaire benadering de realiteit beter of net minder goed weerspiegelen en zal de kans dat de lineaire benadering klopt meer en meer afwijken van 50%. Het cijfer zal dan niet meer veilig zijn vermits de willekeur die het cijfer zou moeten toevoegen aan de data hierdoor wegvalt. Een perfect veilig cijfer daarentegen zal ervoor zorgen dat elke uitdrukking van deze vorm met een kans van 50% voorkomt waardoor er geen verband kan gelegd worden tussen de invoer en de uitvoer van het cijfer. In lineaire cryptanalyse zal de aanvaller gebruik maken van de afwijking van het cijfer ten opzichte van deze perfecte verdeling om een lineaire uitdrukking te bekomen tussen ingangswaarden en uitgangswaarden van het cijfer die met een kans groter of kleiner dan 12 voorkomen. Deze afwijking wordt de ‘bias’ ε genoemd en het is uitsluitend de niet-lineaire functie en dus de reeks S-boxen die deze waarde bepalen. Uitdrukkingen die een grote bias in absolute waarde hebben zullen dus een relatief grotere (of kleinere naargelang het teken van de bias) kans hebben om op te treden. De aanvaller kan dit gebruiken om het cijfer vlugger te kraken dan bij exhaustief zoeken naar de sleutel. 25


3.2.2

De uitwerking van een lineaire aanval

Net als bij differentiële cryptanalyse gaat de aanvaller een uitdrukking zoeken tussen de data ingangen van het cijfer en de uitgang van de voorlaatste ronde. Vergelijking (3.12) wordt dan een uitdrukking van klaartekstingangsbits Xi en de ingangsbits Yi van de laatste ronde van het cijfer met zo mogelijk een relatief grote bias. Hierbij zullen uiteraard de ingangsbits gebruikt in de uitdrukking van één ronde van het cijfer, de uitgangsbits zijn van de uitdrukking van de vorige ronde zodat deze wegvallen in de gecombineerde uitdrukking. Dankzij deze uitdrukking en de cijferteksten die bij de gekende klaarteksten horen zal de aanvaller dan trachten informatie te achterhalen over sommige bits van de deelsleutel van de laatste ronde. Die informatie kan dan mogelijk leiden tot het vinden van de originele sleutel en dus tot het kraken van het cijfer. Ook hier maakt de aanvaller gebruik van het feit dat de deelsleutel telkens wegvalt in de tussenuitdrukkingen. Het rechterlid in vergelijking (3.12) over één ronde van het cijfer moet namelijk in principe ook de som van sommige bits van de deelsleutel van die ronde bevatten. Doordat het resultaat van deze sleutelbit som slechts ‘1’ of ‘0’ kan zijn, zal in het geval van een ‘0’ als resultaat, vergelijking (3.12) dezelfde zijn als zonder deze sleutelbit som en in het geval van een ‘1’ als resultaat, zal vergelijking (3.12) dezelfde zijn op het teken van de bias na1 . Uitdrukking (3.12) is dus, op het teken van de bias, algemeen geldig. De bits van de deelsleutel van de laatste ronde die overeenkomen met de Yi bits gebruikt in vergelijking (3.12) worden door de aanvaller nader beschouwd. De bits uit de deelsleutel die niet worden beschouwd krijgen een nul waarde. De cijfertekst C horende bij de gekozen klaartekst wordt modulo-2 opgeteld met alle mogelijke combinaties van deze bits om daarna het resultaat omgekeerd door de S-boxen te sturen om het n bit woord Z te bekomen. Dit gebeurt voor alle beschikbare cijferteksten waarvan de klaartekst gekend is. Voor elke combinatie van de specifieke deelsleutelbits wordt een teller verhoogd, telkens het resultaat Z van de bewerking, samen met de bijhorende klaartekst P , de lineaire benadering doet kloppen. Dus wanneer voor de deelsleutelbitcombinatie Ksub , S −1 : GF (2n ) → GF (2n ) de inverse van de niet-lineaire S-box functie en voor:

[p1 p2 p3 . . . pn ] = P

(3.13)

[z1 z2 z3 . . . zn ] = Z = S −1 (C ⊕ Ksub )

(3.14)

geldt dat:

p1 · X1 ⊕ p2 · X2 ⊕ . . . ⊕ pn · Xn ⊕ z1 · Y1 ⊕ z2 · Y2 ⊕ . . . ⊕ zn · Yn = 0

(3.15)

Wordt de teller van de combinatie Ksub verhoogd. De combinatie van deze bits waarvan de teller, na het aflopen van alle klaarteksten en bijhorende cijferteksten, het meest afwijkt van de andere tellers, wordt verondersteld met grote kans de 1

Wanneer voor een uitdrukking S(X) = 0 over het gesloten veld GF (2): P [S(X) = 0] = q. Met q de kans dat de uitdrukking geldt, dan heeft men : P [S(X) = 1] = 1 − q. Indien S(X) = 0 geldt ε = (1/2 − q) en indien S(X) = 1, geldt ε = (−1/2 + q) = −(1/2 − q).

26


juiste deelsleutelbits te bevatten. Dit wel enkel wanneer het aantal gekende klaarteksten groot genoeg is. Net zoals bij differentiële cryptanalyse klopt deze veronderstelling. Wanneer het aantal gekende klaarteksten groot genoeg is ten opzichte van de bias van de lineaire uitdrukking, kan de aanvaller veronderstellen dat voor de goede deelsleutelbitcombinatie, de gekozen lineaire benadering met een kans verschillend van 12 zal kloppen. Hij gaat dus de goede deelsleutelbitcombinatie kunnen onderscheiden van de slechte die niet sterk zullen afwijken van de 12 kans van optreden. De juiste combinatie zal namelijk de lineaire benadering, wanneer deze optreedt, in meer of minder dan 50% van de gevallen doen kloppen en de teller van deze combinatie zal dan overeenkomen met deze afwijking. Wanneer de deelsleutel combinatie niet de juiste is kan men veronderstellen dat het resultaat van de lineaire benadering willekeurig wordt en dat de benadering met een kans 12 zal kloppen. De combinatie waarvan de teller het meest afwijkt van de helft van het totaal aantal gebruikte klaarteksten zal dus met een grote kans de juiste zijn.

3.2.3

De effici¨ entie van lineaire cryptanalyse

In zijn originele paper toont Matsui [38] aan dat voor een gekozen lineaire benadering tussen de ingangen van het cijfer en de invoer van de laatste ronde van dat cijfer met een bias ε het nodige aantal gekende klaarteksten benaderd kan worden door ε12 . Om met zekerheid realistische resultaten te bekomen gaat men minstens dit aantal gekende klaarteksten nodig hebben. Met Nl het nodige aantal klaarteksten om lineaire cryptanalyse te kunnen toepassen, c een kleine constante groter dan 1 en ε de bias van de gekozen lineaire benadering, wordt dus gesteld dat:

Nl ≈

c ε2

(3.16)

Het is duidelijk dat hoe meer S-boxen worden betrokken in de lineaire benaderingen over de rondes heen, hoe kleiner de totale bias van de benadering zal zijn. De S-boxen die hierin worden betrokken noemt men de actieve S-boxen en dit zijn de S-boxen waarvan de ingangsbits voorkomen in de benadering. Het Piling-Up Lemma zoals beschreven door Matsui in zijn originele paper, toont namelijk aan dat wanneer de S-boxen onafhankelijk worden beschouwd, de bias van de benadering over twee S-boxen gelijk is aan:

ε1,2 = 2ε1 ε2

(3.17)

Met ε1,2 de bias van de som van de benaderingen van de twee S-boxen met respectievelijke bias ε1 en ε2 . De aanvaller moet dus op zoek gaan naar niet-triviale lineaire benaderingen die zo weinig mogelijk actieve S-boxen bevatten. Over s actieve S-boxen met bias εi bekomt men uit de vorige vergelijking de bias ε van de totale lineaire benadering:

ε = 2s−1

s Y

εi

(3.18)

i=1

27


Net als bij differentiële cryptanalyse is het belangrijk te melden dat het aannemen van de onafhankelijkheid van de S-boxen een benadering is die niet noodzakelijk altijd van toepassing is en dat ε dus een schatting is. Deze schatting blijkt weliswaar meestal nauwkeurig te zijn [27]. Een laatste opmerking betreft het feit dat er mogelijk verschillende combinaties van S-boxen over de rondes heen kunnen bestaan die tot dezelfde algemene lineaire benadering kunnen leiden. Deze kunnen dan mogelijk gecombineerd worden zodat de bias groter kan worden dan wanneer slechts één enkele lineaire benadering door de S-boxen heen wordt beschouwd. Men noemt dit fenomeen de linear hull [44]. Het is dus opnieuw belangrijk om een marge in te bouwen in het cijfer om zo mogelijke problemen te vermijden.

3.3

De invalshoek

Het cijfer moet het een aanvaller onmogelijk maken de net omschreven aanvallen toe te passen. Het is hiervoor zeer belangrijk om goede S-boxen te kiezen en vooral om er voor te zorgen dat telkens genoeg van deze S-boxen actief zijn in elke differentieelkarakteristiek en lineaire benadering over de verschillende rondes van het cijfer. De invalshoek van het ontwerp zal dus zijn om eerst en vooral S-boxen te vinden die efficiënt zijn tegen deze aanvallen maar tegelijk ook compact kunnen ge¨ımplementeerd worden in hardware. Hiervoor zal gekeken worden hoe de kans dat een differentieel over een S-box optreedt kan berekend en geoptimaliseerd worden. Hetzelfde moet dan gebeuren voor de bias van een lineaire benadering van een S-box. Uiteindelijk moet gezocht worden naar een methode om eveneens op een hardware besparende manier een goede diffusie van de actieve S-boxen over de rondes heen te hebben. Op deze manier wordt de kans DP van optreden van een differentieel of de bias ε van een lineaire benadering, over alle rondes van het cijfer, minimaal gehouden. Een aanvaller zou uiteindelijk, om deze aanvallen uit te voeren, meer gekozen of gekende (klaartekst,cijfertekst)paren nodig moeten hebben dan het cijfer maximaal kan hebben, namelijk 264 (zie hoofdstuk 2.3).

28

Hoofdstuk 4

Het blokcijfer EFES Dit hoofdstuk stelt het blokcijfer EFES (Encryption Function for Embedded Systems) voor. De gemaakte keuzes zullen vervolgens in hoofdstuk 5 gemotiveerd worden. Zoals hoofdstuk 2 vermeldt, is het een blokcijfer met een bloklengte van 64 bit en een sleutellengte van 80 bit dat lichtjes afwijkt van de klassieke blokcijfer-structuren. Het cijfer dat gebouwd is vanuit het perspectief van veiligheid tegen lineaire en differentiële aanvallen (zie hoofdstuk 3), versleutelt in 64 klokcycli (rondes) een 64 bit datablok. Elke ronde bestaat uit een niet-lineaire substitutiefunctie in de vorm van twee parallel werkende S-boxen, een lineaire combinatie van de uitgang van deze S-boxen, een deelsleuteloptelling en een permutatie over alle 64 bits van de toestand, in de vorm van een rotatie. De lineaire combinatie wordt de Mix- of M-box genoemd. Na elke ronde wordt de tussentoestand opgeslagen in een 64 bit register en na de 64ste ronde kan het resultaat worden uitgelezen. Op elk moment kan een nieuw 64 bit data blok worden ingelezen door gebruik te maken van het ‘start’ signaal. Hierbij wordt de oorspronkelijke sleutel eveneens geladen in het sleutelregister. De algemene werking van het cijfer is beschreven in figuur 4.1 waar de rotatie van de minst significante bits naar de meest significante bits wordt voorgesteld door het symbool << gevolgd door het aantal bits waarover er wordt geroteerd. In de figuur en in de rest van dit eindwerk stelt de kleinste index steeds de minst significante bit voor. De pseudocode van het cijfer is de volgende:

if start = 0, laadt klaartekst; else for i = 1 to 64, Keyschedule(Sleuteltoestand); Substitutie(Toestand[11 : 0]); M − box(Toestand[11 : 0]); Sleuteloptelling(Toestand[11 : 0], Ki ); Rotatie(Toestand); end for end if 29

4. Het blokcijfer EFES

Figuur 4.1: Het blokcijfer EFES.

De verschillende delen van dit hoofdstuk lichten elke stap uit de rondes nader toe. In een eerste deel worden de S-boxen voorgesteld. Daarna stelt een tweede deel de M-box voor. Een derde en een vierde deel leggen vervolgens respectievelijk de deelsleuteloptelling en de rotatie uit. Uiteindelijk licht een vijfde deel toe hoe uit de 80 bit sleutel, de 64 deelsleutels gebruikt in elke ronde worden bekomen. Dit wordt de key scheduling genoemd.

4.1

De Substitutie-boxen

Daar in elke ronde van het cijfer EFES slechts 12 bits worden gewijzigd en zodoende door de substitutiefunctie worden gestuurd, kan het cijfer ge¨ımplementeerd worden met minder en kleinere S-boxen. Er werd voor het blokcijfer EFES gekozen om de substitutiefunctie op te delen in twee parallel werkende S-boxen. De eerste S-box is een niet-lineaire functie S5 [X] met S5 : GF (25 ) → GF (25 ) en X een 5 bit ingangsvector. De tweede S-box is een niet-lineaire functie S7 [X] met S7 : GF (27 ) → GF (27 ) en X een 7 bit ingangsvector. Op deze manier zal de totale substitutie een niet-lineaire transformatie zijn over GF (212 ) waardoor in elke ronde de bits b11 b10 . . . b1 b0 van de toestandsbits b63 b62 . . . b1 b0 op een niet-lineaire manier wijzigen. Beide S-boxen worden nu nader toegelicht.

De 5 bit S-box Om de functie S5 [X] te implementeren wordt gebruik gemaakt van een lookup table. Dit is een tabel waarin alle 25 mogelijke uitkomsten van de functie worden opgeslaan. In functie van de ingangsbits van de functie die overeenkomen met de indexen van de tabel, kunnen dan op een eenvoudige manier de bijhorende uitgangen uit de tabel worden gehaald. Het voordeel van een lookup table is dat het in een goedkoop ROM geheugen kan worden opgeslagen. Hierdoor blijft de hardwarekost van de S-box beperkt. De functie S5 [X] wordt in tabel 4.1 weergegeven. Het zijn de 5 minst significante bits van het toestandsregister die door deze S-box worden gestuurd en dus de ingang ervan vormen. Van de bits b63 b62 . . . b1 b0 van het toestandsregister 30

De Substitutie-boxen

X S5 [X] X S5 [X]

0 6 16 10

1 7 17 0

2 3 18 17

3 16 19 9

4 23 20 22

5 31 21 21

6 2 22 29

7 24 23 12

8 25 24 8

9 30 25 4

10 20 26 27

11 1 27 5

12 18 28 14

13 28 29 11

14 15 30 13

15 19 31 26

Tabel 4.1: De lookup table van de functie S5 [X]

zijn het de bits b4 b3 b2 b1 b0 die door deze functie worden gestuurd en die bijgevolg niet-lineair worden gewijzigd.

De 7 bit S-box Om de functie S7 [X] te implementeren wordt in tegenstelling tot de functie S5 [X] geen lookup table gebruikt. De niet-lineaire functie S7 [X] wordt ge¨ımplementeerd door gebruik te maken van poort logica bestaande uit AND- en XOR-poorten. Het komt voor deze functie namelijk goedkoper uit in hardware om via poortlogica te werken dan via een lookup table. Hoofdstuk 7.1 toont namelijk aan dat het aantal GE nodig voor de implementatie van S7 [X] als lookup table groter is dan het aantal GE nodig voor de implementatie in poort logica. Op deze manier wordt elke uitgangsbit van de functie door middel van deze poorten, een niet-lineaire combinatie van de ingangsbits. Een XOR-operatie wordt zoals voorheen voorgesteld door het ⊕ symbool en een AND-operatie komt overeen met een vermenigvuldiging in GF (2). Met yi de uitgangsbit i van de uitgangsbitvector Y in functie van de ingang bits xj voor i en j gaande van 0 tot en met 6, is de functie S7 [X] = Y , equivalent aan:

y0 = x0 ⊕ x1 x3 ⊕ x0 x3 x4 ⊕ x1 x5 ⊕ x0 x2 x5 ⊕ x4 x5 ⊕ x0 x1 x6 ⊕ x2 x6 ⊕ x0 x5 x6 ⊕ x3 x5 x6 ⊕ 1 y1 = x0 x2 ⊕ x0 x4 ⊕ x3 x4 ⊕ x1 x5 ⊕ x2 x4 x5 ⊕ x6 ⊕ x0 x6 ⊕ x3 x6 ⊕ x2 x3 x6 ⊕ x1 x4 x6 ⊕ x0 x5 x6 ⊕ 1 y2 = x1 x2 ⊕ x0 x2 x3 ⊕ x4 ⊕ x1 x4 ⊕ x0 x1 x4 ⊕ x0 x5 ⊕ x0 x4 x5 ⊕ x3 x4 x5 ⊕ x1 x6 ⊕ x3 x6 ⊕ x0 x3 x6 ⊕ x4 x6 ⊕ x2 x4 x6 y3 = x0 ⊕ x1 ⊕ x0 x1 x2 ⊕ x0 x3 ⊕ x2 x4 ⊕ x1 x4 x5 ⊕ x2 x6 ⊕ x1 x3 x6 ⊕ x0 x4 x6 ⊕ x5 x6 ⊕ 1 y4 = x2 x3 ⊕ x0 x4 ⊕ x1 x3 x4 ⊕ x5 ⊕ x2 x5 ⊕ x1 x2 x5 ⊕ x0 x3 x5 ⊕ x1 x6 ⊕ x1 x5 x6 ⊕ x4 x5 x6 ⊕ 1 y5 = x0 ⊕ x1 ⊕ x2 ⊕ x0 x1 x2 ⊕ x0 x3 ⊕ x1 x2 x3 ⊕ x1 x4 ⊕ x0 x2 x4 ⊕ x0 x5 ⊕ x0 x1 x5 ⊕ x3 x5 ⊕ x0 x6 ⊕ x2 x5 x6 y6 = x0 x1 ⊕ x3 ⊕ x0 x3 ⊕ x2 x3 x4 ⊕ x0 x5 ⊕ x2 x5 ⊕ x3 x5 ⊕ x1 x3 x5 ⊕ x1 x6 ⊕ x1 x2 x6 ⊕ x0 x3 x6 ⊕ x4 x6 ⊕ x2 x5 x6 De uitkomsten van deze S-box voor alle 27 mogelijke ingangswaarden worden voorgesteld in tabel 4.2. 31


X S7 [X] X S7 [X] X S7 [X] X S7 [X] X S7 [X] X S7 [X] X S7 [X] X S7 [X]

0 27 16 31 32 11 48 14 64 25 80 89 96 1 112 80

1 50 17 36 33 70 49 85 65 18 81 72 97 109 113 34

2 51 18 19 34 32 50 9 66 101 82 3 98 110 114 17

3 90 19 108 35 13 51 54 67 47 83 87 99 99 115 6

4 59 20 55 36 123 52 116 68 48 84 124 100 24 116 71

5 16 21 46 37 53 53 12 69 57 85 79 101 119 117 22

6 23 22 63 38 68 54 103 70 8 86 98 102 35 118 82

7 84 23 74 39 66 55 83 71 104 87 60 103 5 119 78

8 91 24 93 40 43 56 40 72 95 88 29 104 38 120 113

9 26 25 15 41 30 57 10 73 120 89 33 105 118 121 62

10 114 26 64 42 65 58 126 74 42 90 94 106 0 122 105

11 115 27 86 43 20 59 56 75 76 91 39 107 49 123 67

12 107 28 37 44 75 60 2 76 100 92 106 108 45 124 52

13 44 29 81 45 121 61 7 77 69 93 112 109 122 125 92

14 102 30 28 46 21 62 96 78 117 94 77 110 127 126 88

15 73 31 4 47 111 63 41 79 61 95 58 111 97 127 125

Tabel 4.2: De uitkomsten van de functie S7 [X]

Het zijn de bits b11 b10 b9 b8 b7 b6 b5 van het toestandsregister die door deze S-box worden gestuurd en die bijgevolg niet-lineair worden gewijzigd.

4.2

De Mix-box

Een eerste deel van de totale diffusie gebeurt elke ronde over de 12 minst significante bits van de toestand, namelijk over de bits aan de uitgang van de S-boxen. Deze diffusie die de naam Mix- of M-box krijgt, is geen permutatie maar een inverteerbare lineaire combinatie van de 12 uitgangsbits van de S-boxen. Deze lineaire bijectie moet er voor zorgen dat de uitgangen van de S-boxen met elkaar worden gecombineerd. Op die manier zal het, zoals zal worden aangetoond in hoofdstuk 6, voor een aanvaller veel moeilijker zijn om lineaire of differentiële aanvallen op te stellen. De werking van de M-box wordt voorgesteld door een matrixbewerking in GF (2). De binaire matrix M stelt dan de lineaire combinatie of M-box voor en de 12 bit uitgangsvector Y van deze functie dan met een 12 bit ingangsvector X = [b0 b1 ... b10 b11 ]T worden gevonden uit:

Y =M·X

32

(4.1)

De deelsleutel optelling

Waarbij de 12 op 12 matrix M gelijk is aan:

           M=         

1 0 0 0 0 1 0 0 1 0 0 0

0 1 0 0 0 0 1 0 0 1 0 0

0 0 1 0 0 0 0 1 0 0 1 0

0 0 0 1 1 0 0 0 0 0 0 1

1 0 0 0 1 0 0 0 0 1 0 0

0 1 0 0 0 1 0 0 0 0 1 0

0 0 1 0 0 0 1 0 0 0 0 1

1 0 0 1 0 0 0 1 0 1 0 0

0 1 0 0 1 0 0 0 1 0 0 0

0 0 1 0 0 1 0 0 0 1 0 0

0 0 0 1 0 0 1 0 0 0 1 0

1 0 0 0 1 0 0 1 0 0 0 1

                    

(4.2)

De M-box zal dus de uitgangen van de 5 bit S-box en van de 7 bit S-box combineren en spreiden over de bits b11 b10 . . . b1 b0 van de toestand. In hoofdstuk 5 en 6 zal duidelijk worden waarom deze lineaire combinatie werd gekozen.

4.3

De deelsleutel optelling

De deelsleutel optelling vindt in elke ronde plaats net na de M-box bewerking en bestaat uit het modulo-2-optellen van de 12 uitgangsbits van de M-box met de 12 bit deelsleutel van elke ronde. i k i . . . k i k i de 12 bit deelsleutel van ronde i, en b b . . . b b de 12 uitgangsbits Met Ki = k11 11 10 1 0 10 1 0 van de M-box heeft men in elke ronde i voor j gaande van 0 tot en met 11:

bj = bj ⊕ kji

(4.3)

In elke ronde worden dus enkel de bits b11 b10 . . . b1 b0 van de toestand bewerkt met een deelsleutel, afgeleid uit de oorspronkelijke sleutel. De andere bits ondergaan geen verandering.

4.4

De rotatie

Het tweede deel van de diffusie gebeurt over alle bits van de toestand door gebruik te maken van een rotatie. Deze rotatie zal eenvoudigweg alle bits over 12 posities verschuiven zodat in de volgende ronde andere bits door de cryptografische functies worden gestuurd. Met b63 b62 . . . b1 b0 de bits aan de ingang van de rotatie bekomt men aan de uitgang van de rotatie b51 b50 . . . b1 b0 b63 b62 . . . b53 b52 . 33


Figuur 4.2: De key scheduling van het blokcijfer EFES.

4.5

De key scheduling

Zoals vermeld in de vorige delen maakt het blokcijfer EFES gebruik van een 80 bit sleutel waarvan in elke ronde of klokcyclus een 12 bit deelsleutel moet worden afgeleid. Daar EFES 64 rondes nodig heeft om een 64 bit lange datablok te versleutelen zijn er dus 64 deelsleutels nodig. Deze deelsleutels Ki voor i gaande van 1 tot en met 64 worden volgens de volgende pseudocode uit de 80 bit sleutel van het cijfer berekend:

if start = 0, laadt sleutel; else for i = 1 to 64, Substitutie(Sleuteltoestand[2 : 0]); T ellerOptelling(Sleuteltoestand[11 : 10], Teller[2 : 1]); Ki = Sleuteltoestand[11 : 0]; Rotatie(Sleuteltoestand); end for end if De implementatie van de key scheduling wordt grafisch voorgesteld in figuur 4.2. De deelsleutel Ki van ronde i komt overeen met de 12 minst significante bits van het sleutelregister nadat een deel van deze bits door bepaalde functies zijn gestuurd. Dit zijn dus de bits b11 b10 . . . b1 b0 van de bits b79 b78 . . . b1 b0 aan de ingang van de 13 bit rotatie in figuur 4.2. Elke deelsleutel wordt tegelijk met de ronde waarin hij zal worden gebruikt berekend uit de waarde van de vorige sleuteltoestand. De gewijzigde versie van de sleuteltoestand vervangt vervolgens de oude toestand. In elke ronde worden sommige bits uit het sleutelregister net als bij de versleuteling van het toestandsregister door een substitutiefunctie, bestaande uit een 3 bit S-box, gestuurd. Deze S-box wordt in de volgende paragraaf nader toegelicht en in hoofdstuk 5.4 zal de keuze ervan gemotiveerd worden. Uiteraard is er geen deelsleuteloptelling maar vindt er wel een modulo-2optelling plaats met 2 van de 6 bits van de teller. Deze teller wordt gebruikt om de 64 rondes van het cijfer bij te houden. De exacte implementatie van deze optelling wordt in een tweede 34

De key scheduling

paragraaf voorgesteld. De redenering achter deze optelling zal eveneens in hoofdstuk 5.4 volgen. De diffusie gebeurt hier door een rotatie over de toestand van de 80 bit sleutel. Dit keer vindt de rotatie plaats over 13 bits zoals aangegeven in een derde paragraaf. De 3 bit S-box De substitutiefunctie van de key scheduling bestaat dit keer uit een niet-lineaire functie S3 [X] met S3 : GF (23 ) → GF (23 ) en X een 3 bit ingangsvector. Om deze S-box te implementeren wordt net als voor de functie S5 [X] gebruik gemaakt van een lookup table dat in een goedkoop ROM-geheugen kan worden opgeslagen. Deze tabel wordt in tabel 4.3 weergegeven. X S3 [X]

0 0

1 5

2 6

3 7

4 4

5 3

6 1

7 2

Tabel 4.3: De lookup table van de functie S3 [X] Het zijn de 3 minst significante bits van het sleutelregister die door deze S-box worden gestuurd en dus de ingang ervan vormen. Van de bits b79 b78 . . . b1 b0 van het sleutelregister zijn het dus de bits b2 b1 b0 die door deze functie worden gestuurd en die bijgevolg niet-lineair worden gewijzigd. De optelling van de tellerbits In de key scheduling worden er ook twee bits van de teller opgeteld bij de bits b11 en b10 van het sleutelregister. Dit zijn respectievelijk de bits t2 en t1 van de 6 bits t5 t4 t3 t2 t1 t0 van de rondeteller. De bits t2 en t1 hebben een periode van 8 klokcycli, waarin ze om de twee klokcycli of rondes veranderen. Zo zal t2 t1 bijvoorbeeld in de rondes 1, 2, 9, 10, ... gelijk zijn aan 00 en in de rondes 3, 4, 11, 12, ... gelijk zijn aan 01. De bewerking die in elke ronde optreedt is:

b11 = b11 ⊕ t2

(4.4)

b10 = b10 ⊕ t1

(4.5)

De key scheduling rotatie Uiteindelijk bestaat de diffusie er in om alle bits uit het sleutelregister over 13 posities te roteren zodat in de volgende ronde andere bits uit het register worden bewerkt en als deelsleutel zullen fungeren. In hoofdstuk 5.4 wordt het effect van deze rotatie op de deelsleutels over de rondes heen nader uitgelegd. Met b79 b78 . . . b1 b0 de bits aan de ingang van de rotatie zal de uitgang van deze rotaties gelijk zijn aan b69 b68 . . . b1 b0 b79 b78 . . . b67 b68 .

35

Hoofdstuk 5

Motivatie van de ontwerpkeuzes In hoofdstuk 2 werd reeds een groot aantal eigenschappen van het blokcijfer EFES bepaald aan de hand van de noden van de RFID-toepassingen waarvoor EFES is ontworpen. Zo gebruikt EFES een 80 bit sleutel in combinatie met een 64 bit toestand, wat voldoende veiligheid biedt tot in het jaar 2028. Ook de globale structuur die lichtjes afwijkt van de klassieke blokcijferstructuren werd toen bepaald. De beslissingen over de specifieke bouwblokken voor de implementatie van EFES werden vervolgens in het vorig hoofdstuk (hoofdstuk 4) aangekaart. De keuze van deze bouwblokken moet ervoor zorgen dat de veiligheid tegen niet-generische aanvallen gegarandeerd is. Hiervoor moeten de bouwblokken de weerbaarheid van het cijfer tegen dergelijke aanvallen dermate verhogen dat deze aanvallen niet efficiënter zullen zijn dan het exhaustief zoeken naar de sleutel. In dit hoofdstuk worden de verschillende keuzes die in het vorige hoofdstuk werden gemaakt, gemotiveerd op basis van dit veiligheidscriterium. De bouwblokken en de combinatie ervan werden optimaal gekozen in functie van hun sterkte tegen cryptografische aanvallen. Meer specifiek is het blokcijfer EFES ontworpen om weerstand te bieden tegen de lineaire en differentiële cryptanalyses die in hoofdstuk 3 werden uitgelegd. Een belangrijke keuze hierin is de keuze van de substitutiefunctie in de vorm van de S-boxen. Maar ook de diffusiefuncties alsook de key scheduling moeten met zorg worden gekozen. In een eerste deel worden de substitutiefuncties besproken. Een tweede deel behandelt het optimaliseren van het aantal actieve S-boxen over de rondes heen. Het derde deel van dit hoofdstuk gaat over de keuze van de rotatie. Het laatste deel gaat uiteindelijk over de keuze van de key scheduling.

5.1

De Substitutiefunctie

In hoofdstuk 3 werd uitgelegd waarom de S-boxen goed moeten worden gekozen om het cijfer veilig te maken tegen lineaire en differentiële cryptanalyse. De S-boxen moeten er immers voor zorgen dat hun lineaire benadering en differentieel, met respectievelijk een zo klein mogelijke bias ε en kans DP , optreden. Zolang de lineaire benadering en de differentieel over alle rondes steeds genoeg actieve S-boxen bevatten en zolang de bias ε en de kans DP van deze S-boxen klein genoeg is, zal de bias ε en kans DP over alle rondes van EFES minimaal zijn en zal het 36

De Substitutiefunctie

voor een aanvaller onmogelijk zijn deze aanvallen uit te voeren. Een eerste deel gaat uitleggen hoe de kans van optreden van een differentieel over en de bias van een lineaire benadering van een S-box kan worden berekend. Een tweede deel gaat op zoek naar S-boxen die aan beide voorwaarden voldoen. In een derde en een vierde deel worden de twee S-boxen, gebruikt in EFES, afgeleid.

5.1.1

De kans DP en de bias ε

Zowel het berekenen van de kans DP dat een differentieel plaatsvindt, als het berekenen van de bias ε waarmee een lineaire benadering afwijkt van de willekeurige 12 kans van optreden, worden hier behandeld. De kans DP van een differentieel over een S-box Zoals uitgelegd in hoofdstuk 3.1 gaat een aanvaller bij differentiële cryptanalyse gebruik maken van de verschilwaarde ∆X van twee ingangen van de S-boxen om met een bepaalde kans een verschilwaarde ∆Y van de uitgangen van deze S-boxen te schatten. De kans dat een bepaald (∆X, ∆Y ) paar of differentieel over één enkele m bit S-box optreedt kan worden afgeleid uit de definitie van de S-boxen zoals die in hoofdstuk 4.1 werd omschreven. Voor elke ingangsverschilwaarde wordt gekeken hoeveel van de 2m mogelijke ingangsparen (X 0 , X 00 ) tot de uitgangsverschilwaarde ∆Y zullen leiden. De kans DP van optreden van een (∆X, ∆Y ) differentieel is dan gelijk aan dit aantal gedeeld door het totaal aantal ingangsparen [39]:

DP (∆X, ∆Y ) =

#{X|S(X) ⊕ S(X ⊕ ∆X) = ∆Y } 2m

(5.1)

De bias ε van een lineaire benadering van een S-box Om de bias te berekenen van een lineaire benadering van een S-box wordt op een gelijkaardige manier te werk gegaan. Zoals uitgelegd in hoofdstuk 3.2 gaat een aanvaller bij lineaire cryptanalyse een lineaire benadering van de S-boxen zoeken. Deze benadering over GF (2), in de vorm van vergelijking (3.12), treedt op met een bepaalde kans. Hoe sterker deze kans afwijkt van 12 , hoe groter de bias ε en hoe meer lineair de S-boxen zich gedragen. Een grote bias maakt het voor een aanvaller gemakkelijker om dit type aanvallen op te zetten. Deze bias van één enkele m bit S-box wordt berekend door voor de gekozen benadering na te gaan hoeveel combinaties van de 2m mogelijke ingangswaarden en bijhorende uitgangswaarden de benadering doen kloppen. De bias van de benadering is dan gelijk aan [39]:

ε(ΓX, ΓY ) =

#{X|X • ΓX = S(X) • ΓY } 1 − 2m 2

(5.2)

Waar ΓX een m bit woord is, waarvan de niet-nul bits overeen komen met de ingangselementen gebruikt in de lineaire benadering (3.12) en ΓY een m bit woord die overeenkomt met de 37

5. Motivatie van de ontwerpkeuzes

niet-nulelementen van de uitgang. A • B stelt de pariteit van het bit-product van de woorden A en B voor.

5.1.2

S-boxen veilig tegen differenti¨ ele en lineaire aanvallen

Vervolgens wordt gezocht naar S-boxen die zowel de DP als de ε minimaliseren voor alle mogelijke differentiëlen over en lineaire benaderingen van de S-box. In zijn paper [43] stelt Nyberg voor om als niet-lineaire functies die de S-boxen gaan implementeren, machtsfuncties in GF (2m ) te gebruiken. Deze functies worden gedefinieerd als een veelterm:

l

S(X) = X2 +1

(5.3)

Waar X de veelterm voorstelling is van de m bit ingangsvector X van de S-box en ggd(l, m) = 1. Hier staat ggd voor grootste gemene deler. Deze functies hebben over alle 22m mogelijke differentiëlen (∆X, ∆Y ) een maximale DP van 2−(m−1) . Wanneer m oneven wordt gekozen is de maximale bias ε over alle 22m mogelijke lineaire benaderingen eveneens optimaal en gelijk −(m+1) aan 2 2 . Het is dan ook duidelijk dat een S-box met een groter aantal ingangs- en uitgangsbits m betere resultaten zal opleveren. Jammer genoeg zal de S-box bij zijn hardware-implementatie ook een veel grotere kost hebben. Er werd voor EFES gekozen om met S-boxen te werken met ingangen van 5 en 7 bit om een evenwicht te vinden tussen hardwarekost en veiligheid. Verder gaat het gebruik van meerdere S-boxen het nodige aantal rondes verkleinen maar eveneens meer kosten in hardware. Hier moet opnieuw een afweging worden gemaakt. Wanneer slechts één enkele S-box wordt gebruikt, zou het aantal rondes sterk moeten worden verhoogd om genoeg actieve S-boxen te bekomen. Drie S-boxen hebben dan weer een te grote kost in hardware. Uiteindelijk werd voor EFES geopteerd voor twee ‘Nyberg’ S-boxen die relatief goedkoop kunnen worden ge¨ımplementeerd in hardware.

5.1.3

De functie S7 [X]

Omdat vanaf een bepaald aantal bit m, de lookup table die dikwijls wordt gebruikt om de m bit S-box in hardware te implementeren, veel te groot wordt, wordt voor de 7 bit S-box gebruik gemaakt van poort logica. Het vinden van een machtsfunctie over GF (27 ) zoals Nyberg het voorstelt, die efficiënt in poortlogica te implementeren valt, is een tijdrovende taak. Daarom werd op zoek gegaan naar bestaande S-boxen die hieraan voldoen. In het blokcijfer MISTY [40] wordt een 7 bit S-box van het ‘Nyberg’-type voorgesteld. Deze S-box heeft van alle 7 bit S-boxen van het ‘Nyberg’-type, de meest hardware-efficiënte implementatie in poortlogica. Deze wordt dan ook gebruikt in het blokcijfer EFES en zoals zal worden gezien in hoofdstuk 7 is deze implementatie inderdaad behoorlijk hardware-efficiënt. De DP en de ε van deze S-box worden ter controle nagegaan. De 7 bit S-box gebruikt in EFES heeft een 38

Optimalisatie van het aantal actieve S-boxen

maximale DP gelijk aan 2−6 en een maximale bias ε gelijk aan 2−4 . Dit klopt inderdaad met wat Nyberg in zijn paper aantoont voor machtsfuncties1 .

5.1.4

De functie S5 [X]

Voor de 5 bit S-box werd een nieuwe S-box gezocht. Dit gebeurde door op zoek te gaan naar een machtsfunctie in GF (25 ) zoals voorgesteld in de paper van Nyberg. Hiervoor werd een willekeurige functie gekozen met l = 2 en met F (X) = 1 + X2 + X5 als irreduceerbare veelterm in GF (25 ). Verder werd er een willekeurige constante C opgeteld aan de uitvoer van de S-box. Op deze manier zal een nulvector invoer niet resulteren in eenzelfde nulvector uitvoer. De machtsfunctie die uiteindelijk gebruikt werd om de niet-lineaire functie S5 [X] te vinden is:

S5 (X) = X5 + C

(5.4)

Met C = [00110] waar de minst significante bit aan de rechterkant staat en C de veeltermvoorstelling van deze constante. In hoofdstuk 7 zal worden aangetoond dat een implementatie in hardware aan de hand van een lookup table voor deze S-box efficiënt kan gebeuren. De DP en de ε van deze S-box worden ter controle nagegaan. Deze 5 bit S-box heeft inderdaad een maximale DP gelijk aan 2−4 en een maximale bias ε gelijk aan 2−3 .

5.2


Een differentiële of lineaire aanval op een blokcijfer wordt efficiënt wanneer de differentieelkarakteristiek of lineaire benadering van de invoer tot en met de voorlaatste ronde, slechts een klein aantal actieve S-boxen bevat. In het geval van EFES gaat een aanvaller trachten een karakteristiek of benadering te vinden waarin vooral de minder ‘veilige’ 5 bit S-boxen voorkomen. Hierbij gaat hij ervoor zorgen dat na elke ronde de uitgangen van de differentieelkarakteristiek of van de lineaire benadering bestaan uit een minimum aantal niet-nul bits. Deze niet-nul bits worden de actieve bits genoemd. Het zijn namelijk deze bits die in de volgende rondes, wanneer ze door de substitutiefunctie worden gestuurd, de S-boxen zullen activeren. De aanvaller zal er ook proberen voor te zorgen dat de volgende keer dat een actieve bit door een S-box wordt gestuurd, dit door de minder ‘veilige’ 5 bit S-box is. Om dit tegen te gaan moet de ontwerper er voor zorgen dat het aantal actieve bits na elke ronde wordt gemaximaliseerd en dat deze bits in de volgende rondes zoveel mogelijk verschillende S-boxen activeren. Er bestaan verschillende manieren om dit te realiseren. Ze worden één voor één besproken in de volgende delen. Uiteindelijk zal de laatste oplossing worden gekozen voor het blokcijfer EFES en zal dit leiden tot de M-box zoals gedefinieerd in hoofdstuk 4.2. 1

Deze DP is dezelfde als die van de 8 bit S-boxen gebruikt in het blokcijfer AES [16]. De bias ε is voor EFES zelf een factor 2 kleiner. Betere eigenschappen worden dus bekomen voor een S-box dat kleiner is dan dat gebruikt in AES.

39


5.2.1

Een permutatie gebruiken

De meest hardware-efficiënte oplossing om het aantal actieve S-boxen te verhogen is door te zorgen dat voor één enkele actieve bit aan de ingang van de S-box, er steeds minstens 2 actieve bits aan de uitgang zijn. Deze actieve uitgangsbits kunnen dan gepermuteerd worden over alle toestandsbits, om elk een verschillende S-box te activeren in de volgende rondes. De permutatie bestaat enkel uit bedrading en heeft daarom geen kost in hardware. Dit is de methode die het blokcijfer Present [4] toegepast. Voor differentiële cryptanalyse betekent dit dat voor een ingangsverschilwaarde met slechts één enkele niet-nul bit, de S-box moet zorgen dat er altijd minstens twee niet-nul bits zijn in de uitgangsverschilwaarde. Voor de gekozen S-boxen S5 [X] en S7 [X] is dit jammergenoeg niet het geval. Voor deze S-boxen bestaan namelijk veel ingangsverschilwaarden met één enkele actieve bit die met een niet-nul kans een uitgangsverschilwaarde geven met eveneens slechts één enkele actieve bit. Eenzelfde redenering kan gevolgd worden voor de lineaire benadering van de S-boxen en opnieuw voldoen de gekozen S-boxen niet aan deze eigenschap. Er is bijgevolg een willekeurige verdeling van de kansen dat een bepaalde differentieel of lineaire benadering al dan niet optreedt. Deze oplossing kan hierdoor niet worden gebruikt voor de gekozen S-boxen.

5.2.2

Het aantal rondes verhogen

De eenvoudigste oplossing is om het aantal rondes van het cijfer te verhogen. Op deze manier, en ondanks het minimum aantal actieve S-boxen per ronde (één in het slechtste geval), gaat het blokcijfer EFES na verloop van tijd genoeg actieve S-boxen bevatten. Dit is weliswaar de minst efficiënte oplossing ten opzichte van de encryptiesnelheid van het cijfer.

5.2.3

Effici¨ entere S-boxen gebruiken

De meest voor de hand liggende oplossing voor het probleem zou zijn om andere S-boxen te kiezen. Op die manier kan alsnog een permutatie worden gebruikt om het aantal actieve S-boxen te verhogen. De nieuwe S-boxen moeten met dezelfde kost in hardware en zonder verlies aan veiligheid, een grotere efficiëntie bekomen op het vlak van de actieve bits. Deze S-boxen moeten namelijk betere ingangs-uitgangskarakteristieken voor de verschilwaarden en de lineaire benaderingen bezitten. Dit werd in deel 5.2.1 reeds uitgelegd. Voor de 7 bit S-box zal een betere S-box vinden moeilijk worden doordat de gekozen 7 bit S-box reeds de meest optimale is op het vlak van veiligheid en vooral hardware-implementatie. Een andere 7 bit S-box zou dus bijna zeker leiden tot een grotere kost in hardware. Toch worden enkele mogelijkheden bij het zoeken naar betere S-boxen voorgesteld in de volgende paragrafen. De extra kost in hardware moet steeds worden afgewogen tegen de winst in aantal actieve S-boxen over de rondes heen. 40


Lineaire transformatie van de bestaande S-boxen Aan de S-boxen gebouwd aan de hand van machtsfuncties in GF (2m ) zoals Nyberg voorstelt in zijn paper [43], kunnen zonder de maximale DP en ε te veranderen toch aanpassingen gebeuren. Op deze manier kunnen verschillende ingangs-uitgangseigenschappen worden bekomen zonder de veiligheid in gedrang te brengen. Er kan namelijk steeds een bijective lineaire combinatie worden genomen van de uitgangen van de bestaande S-boxen om tot een nieuwe S-box te komen [40]. Er moet dus een m op m binaire matrix B gevonden worden die, wanneer vermenigvuldigd met de huidige S-box uitvoer, een nieuwe S-box zal geven. Om dit te garanderen moet de matrix B een bijectie zijn en zodoende moet zijn determinant modulo-2, verschillend zijn van nul. De nieuwe S-box Sm0 [X] is dan gelijk aan:

k +1

Sm0 (X) = B · (X2

+ C)

= B · Sm (X)

(5.5) (5.6)

Hierbij gaan de DP en de ε van de S-boxen niet veranderen. Wel gaan er verschillende differentiëlen al dan niet optreden en gaan verschillende lineaire benaderingen al dan niet een bias vertonen. Het is de bedoeling om een dergelijke lineaire combinatie te vinden die voldoet aan de eisen die werden gesteld in het begin van dit deel. Het resultaat moet zorgen dat één actieve bit aan de ingang van de S-box zal leiden tot minstens 2 actieve bits aan de uitgang. Jammergenoeg zijn er voor m gelijk aan 5 of m gelijk aan 7 respectievelijk 225 en 249 mogelijke lineaire combinaties B. Door de grote rekentijden die gepaard gaan bij het zoeken van de DP en vooral de ε waarden van elke S-box wordt het zoeken naar een B die tot voldoende goede resultaten leidt zeer omslachtig2 . Deze methode wordt hierdoor niet verder beschouwd.

Nieuwe machtsfuncties gebruiken Door een andere waarde voor l en een andere irreduceerbare veelterm te kiezen in GF (2m ) geeft de formule van de machtsfuncties van Nyberg [43] andere S-boxen. Ook hier bestaan er echter een heel groot aantal combinaties waardoor op deze manier zoeken naar een S-box met een betere ingangs-uitgangskarakteristiek eveneens omslachtig wordt.

Een omgekeerde redenering toepassen Een laatste methode zou zijn om te starten met de gewenste ingangs-uitgangskarakteristieken van de S-box en daaruit dan de S-box trachten te vinden. Dit wil zeggen dat twee 2m op 2m matrices moet worden gekozen. De rijen van de eerste matrix bevatten de verschillende ∆X waarden en de kolommen de verschillende ∆Y waarden. De elementen van de matrix bestaan 2

Enkele duizenden willekeurige lineaire combinaties werden getest. Sommige gaven betere resultaten dan de gekozen S-boxen maar geen ervan zorgde ervoor dat één actieve ingangsbit altijd voor minstens twee actieve uitgangsbits zorgt.

41


uit de kansen dat de bijhorende differentiëlen (∆X, ∆Y ) over de S-box voorkomen. Analoog bestaan de rijen van de tweede matrix uit de ΓX waarden en de kolommen uit de ΓY waarden. De elementen van deze matrix stellen de bias van de bijhorende lineaire benaderingen van de S-box voor. Deze matrices moeten voldoen aan enkele voorwaarden opgelegd door de voorwaarde van het bijectief zijn van de S-boxen [39]. Uiteindelijk moet een methode worden gevonden om uit deze matrices de bijhorende S-box terug te vinden. Het zoeken naar dit complex verband wordt niet verder beschouwd binnen het kader van dit eindwerk.

5.2.4

Een lineaire combinatie gebruiken

Een laatste manier om het probleem van het aantal actieve S-boxen op te lossen, is door net als in het blokcijfer AES [16], gebruik te maken van lineaire combinaties van de uitgangen van alle S-boxen (de MixColumn in AES). Op deze manier kan de ontwerper met één actieve bit aan de uitgang van één van de S-boxen, verschillende andere bits actief maken na het toepassen van de lineaire combinatie. De actieve bit kan namelijk gebruikt worden in het berekenen van meer dan één uitgangsbit van deze lineaire combinatie.

De voor- en nadelen van een lineaire combinatie Wanneer deze lineaire combinatie op een goed bestudeerde manier gekozen wordt, kan de ontwerper ervoor zorgen dat het activeren van één S-box in een bepaalde ronde, steeds welbepaalde groepen bits zal activeren. Deze bits gaan de volgende keer dat ze door een substitutiefunctie worden gestuurd zoveel mogelijk S-boxen activeren. Zo zorgt een lineaire combinatie over alle uitgangen van de substitutiefunctie dat het aantal actieve S-boxen over de verschillende rondes sterk vergroot wordt. De diffusie van de toestandsbits zal hierdoor eveneens verbeteren. Jammergenoeg brengt dit type lineaire combinatie een zekere hardwarekost met zich mee.

De lineaire combinatie van EFES Doordat de vorige oplossingen niet evident zijn, en omdat de extra hardwarekost van een lineaire combinatie beperkt blijft wanneer met slechts 2 relatief kleine S-boxen wordt gewerkt, wordt deze oplossing naar voren geschoven als zijnde de momenteel meest haalbare. EFES maakt gebruik van een lineaire combinatie van de 12 bit uitgang van de twee S-boxen om het aantal actieve S-boxen over de verschillende rondes te maximaliseren. Deze lineaire combinatie wordt de Mix- of M-box genoemd. Het is een lineaire functie in GF (212 ) die kan worden voorgesteld door een binaire matrix M zoals gedefinieerd in hoofdstuk 4.2. De voorwaarde hiervoor is dat de modulo-2 waarde van de determinant van M gelijk is aan 1. Zoals uitgelegd in hoofdstuk 6, werd deze lineaire combinatie zo gekozen dat, over de 64 rondes van het blokcijfer EFES, er steeds een minimum aantal actieve S-boxen zal zijn. Dit minimum betekent dat er genoeg actieve S-boxen zullen zijn om veiligheid van EFES tegen lineaire en differentiële cryptanalyse, zoals uitgelegd in hoofdstuk 3, te garanderen. 42

De Rotatie

5.3

De Rotatie

Voor de rotatie werd gekozen om in elke ronde de toestand van de data over 12 bits te roteren. Onder andere omdat 12 geen deler is van 64 zal hierdoor extra diffusie optreden. De verschillende bits van het toestandsregister zullen namelijk niet steeds gepaard met dezelfde bits door de substitutiefunctie worden gestuurd. Het kleinst gemeen veelvoud van 64 en 12 is gelijk aan 192 en hierdoor zal het 16 rondes duren voor de 12 bits die in een eerste ronde door de S-boxen werden gestuurd opnieuw tegelijk door deze S-boxen worden gestuurd.

5.4

De key scheduling

Tot nu toe is er nog maar weinig gekend rond veilige key scheduling. Wel werden er reeds enkele aanvallen met succes uitgevoerd waardoor een paar eigenschappen waaraan de key scheduling moet voldoen, bekend zijn. De meest voorkomende en bekende aanvallen zijn de slide-aanvallen [13] en de related key-aanvallen [10]. In een eerste deel worden de related key-aanvallen en de voorwaarden die ze opleggen aan de key scheduling kort besproken. Een tweede deel behandeld dan de slide-aanvallen. Een derde deel behandeld de algemene voorwaarden waaraan een veilige key scheduling moet voldoen. Een laatste deel handelt over de veiligheid van de gekozen key scheduling voor EFES.

5.4.1

Related-key aanvallen

De related-key-aanvallen maken gebruik van het feit dat wanneer het key scheduling-algoritme precies hetzelfde is in elke ronde, de verschillende deelsleutels eenduidig verbonden zijn aan elkaar. Gegeven een bepaalde sleutel, kunnen alle deelsleutels van deze sleutel gevonden worden. Door deze set deelsleutels allemaal een ronde terug te draaien kan dan een nieuwe set deelsleutels bekomen worden die hoort bij een nieuwe sleutel. Dit proces kan telkens opnieuw worden herhaald en de bekomen sleutels worden dan related sleutels genoemd. Om deze aanvallen, die voorkomen in verschillende vormen, tegen te gaan moet, net als in bijvoorbeeld het DES-cijfer [42], het berekenen van de deelsleutels in elke ronde afhankelijk zijn van een parameter die om de zoveel rondes verandert. Hierdoor zijn de verschillende deelsleutels niet eenduidig verbonden met elkaar en kunnen geen related sleutels worden gevonden. In de key scheduling van het DES-blokcijfer wordt hiervoor gebruik gemaakt van een rotatie over de sleuteltoestand waarbij het aantal bit waarover wordt geroteerd afhangt van de ronde waarin het cijfer zich bevindt. In het blokcijfer Present [4] en in vele andere blokcijfers wordt hiervoor gebruik gemaakt van de toestand van de teller van het aantal rondes. Bits van deze teller worden in elke ronde opgeteld bij de sleuteltoestand om zo rondes te differentiëren.

5.4.2

Slide aanvallen

Slide-aanvallen buiten het feit uit dat bepaalde rondes van een blokcijfer dezelfde deelsleutel gaan gebruiken of dat de deelsleutels periodiek herhaald worden binnen het totaal aantal rondes van het blokcijfer. Ook van dit type aanvallen bestaan veel varianten. Om deze aanvallen tegen 43


te gaan moet de key scheduling van het blokcijfer bij het aanmaken van de deelsleutels geen ‘zwakke’ verbanden hebben tussen de vorige sleuteltoestand en de nieuwe. De ontwerper moet er zodoende voor zorgen dat de key scheduling bestaat uit sterke cryptografische functies zoals bijvoorbeeld S-boxen.

5.4.3

Voorwaarden voor een veilige key scheduling

In het algemeen moet er bij het ontwerpen van een key scheduling zeker voldaan zijn aan vijf voorwaarden [4]: 1. De verschillende deelsleutels moeten sterk niet-lineaire functies zijn van de oorspronkelijke sleutel en deze niet-lineaire verbanden moeten zich doorheen de rondes verspreiden over de sleuteltoestand. Om aan deze voorwaarde te voldoen wordt in EFES gebruik gemaakt van een S-box en een rotatie over de sleuteltoestand. 2. De key scheduling moet gebruik maken van een externe parameter die veranderlijk is over de verschillende rondes. Om aan deze voorwaarde te voldoen zal gebruik worden gemaakt van de toestand van de teller van de rondes. 3. Elke bit in het sleutelregister is na ronde r een niet-lineaire functie van de initiële sleutel. Daartoe wordt een S-box en een rotatie gebruikt. 4. Elke bit in het sleutelregister is na ronde r afhankelijk van zoveel mogelijk bits uit de oorspronkelijke sleutel. Opnieuw wordt aan deze voorwaarde voldaan door gebruik te maken van een S-box en een rotatie. 5. Het minimum aantal actieve S-boxen waardoor de bits van de sleuteltoestand na de laatste ronde doorgingen is maximaal. Hiervoor is een optimale keuze van het aantal bit waarover zal worden geroteerd, in functie van de gekozen S-box, belangrijk.

5.4.4

De veiligheid van de key scheduling van EFES

De key scheduling van EFES voldoet aan de vorige voorwaarden door gebruik te maken van 3 bouwblokken die in de volgende paragrafen worden toegelicht.

De 3 bit S-box De keuze van de te gebruiken S-box viel omwille van hardware besparende reden op een 3 bit S-box die zeer compact kan worden ge¨ımplementeerd. Wel moet er met zorg worden omgegaan met S-boxen van deze grootte. Hun niet-lineariteit laat namelijk dikwijls te wensen over. Daarom werd er ge¨ opteerd om gebruik te maken van een bestaande S-box die reeds geoptimaliseerd werd in zijn lineaire en differentiële eigenschappen ε en DP . In het blokcijfer SEA [52] wordt gebruik gemaakt van een 3 bit S-box waarvan de maximale bias ε van de lineaire benaderingen gelijk is aan 2−1 en de maximale kans op een differentieel DP gelijk is aan 2−2 . Dit komt overeen met wat zou worden bekomen met een ‘Nyberg’ S-box3 . 3 Deze S-box biedt gelijkwaardige veiligheid tegen lineaire en differentiële cryptanalyse dan de grotere 4 bit S-box gebruikt in de key scheduling van het blokcijfer Present [4].

44

De key scheduling

Figuur 5.1: Evolutie van de bits (in grijs) die niet-lineair afhankelijk zijn van de oorspronkelijke sleutelbits over de rondes heen.

De ronde-afhankelijke parameter Om het key scheduling-algoritme over de rondes heen afhankelijk te maken van een externe parameter werd gekozen om de bits t2 en t1 van de teller met toestandbits t5 t4 t3 t2 t1 b0 in elke ronde op te tellen bij de sleuteltoestand. Omdat de deelsleutel slechts 12 bits heeft, werd gekozen om er slechts twee tellerbits bij op te tellen. De twee tellerbits die werden gekozen zorgen ervoor dat twee opeenvolgende rondes dezelfde externe parameter hebben. Het voordeel om de bits t2 en t1 van de teller te gebruiken is dat de externe parameter om de twee rondes verandert en dit over een periode van 8 rondes. Omdat het 6 rondes duurt eer alle toestandsbits een deelsleuteloptelling ondergaan, zullen hierdoor geen twee opeenvolgende blokken van 6 rondes de externe parameter in dezelfde volgorde gebruiken. De niet-lineariteit van de key scheduling Met de gekozen key scheduling en bijhorende 13 bit rotatie over de sleuteltoestand in elke ronde wordt bekomen dat na 42 rondes alle bits uit de sleuteltoestand een niet-lineaire functie zijn van de oorspronkelijke sleutelbits (zie figuur 5.1). Ook zal er intussen een sterke diffusie onder de sleutelbits hebben plaatsgevonden. Hierdoor zullen de deelsleutels na een bepaald aantal rondes sterk afhankelijk zijn van een groot aantal oorspronkelijke sleutelbits.

45

Hoofdstuk 6

Veiligheid van het blokcijfer EFES Bij het ontwerpen van het blokcijfer EFES werd zoals uitgelegd in hoofdstuk 3 de veiligheid tegen lineaire en differentiële cryptanalyse naar voren geschoven, als zijnde de invalshoek voor het ontwerp. Dit hoofdstuk zal aantonen dat het cijfer EFES met zijn 64 rondes effectief veilig is tegen dit type aanvallen. Hier moet wel worden vermeld dat naast deze twee veel voorkomende aanvallen ook veel andere aanvallen op blokcijfers bestaan. Deze werden niet in rekening genomen bij het ontwerpen van het blokcijfer EFES. Zo bestaat bijvoorbeeld een heel grote variëteit aan algebra¨ısche aanvallen [5]. Deze aanvallen maken gebruik van overgedetermineerde stelsels van veeltermbenaderingen van het cijfer. Vermoed wordt dat deze aanvallen, door de relatieve grootte van de S-boxen die werden gebruikt, moeilijk uit te voeren zijn op EFES. Deze aanvallen worden in dit eindwerk echter niet verder beschouwd wegens hun complexiteit en verscheidenheid. Verder bestaan er ook aanvallen die specifiek gebruik maken van de parameters van het cijfer zoals aangehaald in hoofdstuk 2.2. Deze aanvallen zoals de Time-Memory data Trade-Off (TMTO) aanvallen zijn varianten op de brute force aanval en maken bijgevolg geen gebruik van de inwendige structuur van het cijfer [26, 30]. Enkel de toestands- en sleutellengte van het cijfer bepalen de snelheid waarmee ze een sleutel kunnen kraken. Ze worden generische aanvallen genoemd en kunnen zodoende op elk symmetrisch cijfer worden toegepast. Gegeven de parameters van EFES, worden deze aanvallen beschouwd als de beste die een aanvaller ter beschikking heeft. In een eerste deel van dit hoofdstuk wordt de veiligheid van het blokcijfer EFES tegen differentiële cryptanalyse nagegaan. Een tweede deel gaat de veiligheid van EFES tegen lineaire cryptanalyse na.

6.1

Veiligheid tegen differenti¨ ele cryptanalyse

Een aanvaller gaat zoals vermeld in hoofdstuk 3, op zoek naar de meest optimale differentieelkarakteristiek. Dit is een differentieelkarakteristiek die met een zo groot mogelijk kans DP optreedt. Deze differentieelkarakteristiek bevat hiervoor, over de verschillende rondes van het cijfer, een minimum aan actieve S-boxen. De kans DP dat een differentieelkarakteristiek optreedt is namelijk omgekeerd evenredig met het aantal gekozen (klaartekst, cijfertekst)-paren 46

Veiligheid tegen differentiële cryptanalyse

dat nodig is om de aanval te doen werken. Het blokcijfer EFES zal veilig zijn tegen dit type aanvallen wanneer het totaal aantal gekozen (klaartekst, cijfertekst)-paren die nodig zijn om de aanval op te stellen, groter is dan het maximaal aantal beschikbaar, namelijk 264 . Vanuit het standpunt van de aanvaller wordt nu op zoek gegaan naar de beste differentieel die voor EFES te vinden is. Zoals uitgelegd in hoofdstuk 5.2 hebben de gebruikte S-boxen een willekeurig verdeling van het al dan niet optreden van een bepaalde differentieel. Bij het vinden van de beste differentieelkarakteristiek wordt dus aangenomen dat de aanvaller steeds kan kiezen welke uitgangsverschilwaarde met een kans DP voorkomt wanneer een willekeurige ingangsverschilwaarde wordt aangelegd aan een S-box. Het is dus de M-box zoals gedefinieerd in vergelijking (4.1) en vergelijking (4.2) die ervoor zal zorgen dat de aanvaller er niet steeds voor kan kiezen om in elke ronde maximum één actieve S-box te hebben. Doordat in elke cyclus een rotatie over 12 bits plaatsvindt en in elke ronde 12 bits door de substitutiefunctie worden gestuurd, kan met een totale bloklengte van 64 bit, gewerkt worden met blokken van 4 bit. Deze 4 bits of nibble zullen namelijk steeds in dezelfde ronde door de S-boxen worden gestuurd. In de volgende delen wordt er ronde na ronde nagegaan welke de differentieelkarakteristiek is die met de grootste kans kan optreden. Een eerste deel gaat over de eerste ronde en de bijhorende keuzes die de aanvaller kan maken. Een tweede deel overloopt de 7 eerste rondes van EFES. Een derde deel beschouwt de veiligheid van EFES tegen deze aanval. Uiteindelijk toont een vierde deel aan dat het blokcijfer EFES met 64 rondes, veilig is tegen differentiële cryptanalyse.

6.1.1

De eerste ronde van EFES

In een eerste ronde worden de 12 minst significante bits van de toestand door de S-boxen gestuurd zoals voorgesteld in figuur 6.1.a. In deze figuur krijgen de verschillende nibbles ook een nummer toegekend. Nibbles die in een bepaalde ronde mogelijk actief kunnen zijn worden in het grijs aangeduid. Welke van deze nibbles precies actief zijn hangt af van de keuze van de aanvaller en wordt nu nader toegelicht. Normaal gezien gaat een aanvaller voor deze eerste ronde de ingangsverschilwaarde zo kiezen dat enkel de 5 bit S-box geactiveerd wordt. Dit zou leiden tot een voorlopig optimale differentieel over één ronde. Hierna kan hij kiezen welke van de 5 bits van de uitgangsverschilwaarde van deze S-box actief zijn. Hij kan evenwel ook de 7 bit S-box activeren om daarna uit de bijhorende 7 uitgangsbits te kunnen kiezen welke actief zijn. In beide gevallen kan hij uitgangsbits activeren zodat na het toepassen van de M-box, het aantal actieve nibbles minimaal is. Het is duidelijk dat de aanvaller hiervan gebruik zal maken. Actieve nibbles houden namelijk in dat ze in latere rondes S-boxen gaan activeren. Uit de M-box kan worden gehaald dat wanneer de aanvaller slechts één enkele S-box activeert, het onmogelijk is om minder dan twee actieve nibbles te bekomen aan de uitgang van deze M-box. Elke actieve bit aan de ingang van de M-box komt namelijk overeen met een kolom uit de matrixvoorstelling M van deze M-box. De uitgangsbits van de M-box worden bekomen door de kolommen van M, horende bij de actieve ingangsbits, modulo-2 aan elkaar op te tellen. Door enkel de 5 minst significante of enkel de 7 meest significante bits van de ingang te combineren 47

6. Veiligheid van het blokcijfer EFES

Figuur 6.1: Evolutie van de potentieel actieve nibbles (in grijs) in functie van de keuze van de aanvaller over de rondes heen. De beschouwde nibbles worden genummerd van 0 tot en met 5.

kan de som van de bijhorende kolommen uit M nooit meer dan één niet actieve nibble hebben1 . De toestand van de data na de eerste ronde wordt voorgesteld in de figuur 6.1.b waar 2 van de 3 aangeduide nibbles die door de S-boxen werden gestuurd actief zijn. De aanvaller heeft dus drie keuzes tijdens de eerste ronde. Een aanvaller kan weliswaar ook slechts één actieve nibble aan de uitgang van de M-box bekomen door beide S-boxen in de eerste ronde te activeren. Hierdoor kan hij namelijk alle 12 de ingangsbits van de M-box aanwenden. Deze situatie wordt later beschouwd.

6.1.2

De eerste 7 rondes van EFES

Logischerwijs gaat een aanvaller een ingangsverschilwaarde kiezen waar enkel de 12 minst significante bits mogelijk actief zijn. De andere bits van de ingangsverschilwaarde worden door de aanvaller gedesactiveerd. Hierdoor zullen in de 4 rondes die volgen op de eerste ronde geen extra S-boxen worden geactiveerd. Na ronde 5 zullen nibble nummer 2 en 3 uit de eerste ronde opnieuw aan de ingang van de substitutie-functie staan. Nibble nummer 1 uit de eerste ronde zal zich dan uiterst links in het toestandsregister bevinden. Dit wordt afgebeeld in figuur 6.1.c. Tijdens de 6de ronde zullen dan zowel nibble 2 en 3 veranderen, maar zal nibble 1 enkel van plaats verschuiven. De eerste ronde geeft de aanvaller zoals eerder vermeld drie keuzes: 1

48

Dit werd gevonden door alle mogelijke combinaties exhaustief na te gaan.

Veiligheid tegen differentiële cryptanalyse

1. De aanvaller kan kiezen om nibble nummer 3 inactief te maken tijdens de eerste ronde. Tijdens ronde 6 zal nibble nummer 2 die actief zal zijn, de 5 bit S-box activeren. De differentieelkarakteristiek over 6 rondes zal dan minstens twee actieve 5 bit S-boxen bevatten. 2. De aanvaller kan ook nibble nummer 2 desactiveren. Nibble 3 kan dan mogelijk leiden tot het activeren van de 5 bit S-box, de 7 bit S-box of beiden. De 5 bit S-box zal als enige S-box worden geactiveerd wanneer enkel de minst significante bit van nibble 3 actief is. Hiervoor moet de aanvaller zorgen dat na de eerste ronde enkel de negende uitgangsbit actief is. Maar het desactiveren van een nibble maakt het onmogelijk om slechts één actieve bit in nibble nummer 3 te bekomen. De minst significante bit van nibble 3 zal dus nooit als enige bit uit deze nibble actief zijn. Nibble nummer 3 zal hierdoor tijdens de 6de ronde minstens de 7 bit S-box activeren en mogelijk ook de 5 bit S-box. De differentieelkarakteristiek over 6 rondes zal dan minstens één actieve 5 bit S-box en één actieve 7 bit S-box bevatten. 3. De derde keuze die een aanvaller heeft is om nibble nummer 1 inactief te maken. Uit de redenering van keuze 2 kan dan worden besloten dat nibble 2 en 3 zowel de 5 bit als de 7 bit S-box zullen activeren. De differentieelkarakteristiek over 6 rondes zal dan minstens twee actieve 5 bit S-boxen en één actieve 7 bit S-box bevatten. Een aanvaller gaat voorlopig kiezen om keuze 1 te maken zodat de differentieel over de 6 rondes met een zo groot mogelijke kans optreedt. Dit blijkt een slechte keuze te zijn omdat nibble nummer 1 die bij deze keuze actief is, tijdens ronde 7 een extra 7 bit S-box gaat activeren zoals voorgesteld in figuur 6.1.d. Na ronde 7 zal hierdoor de differentieel voor keuze 1 met een even grote maximale kans voorkomen als bij keuze 3. Daarbij komt nog dat na ronde 7, bij keuze 1 en 2, in totaal minstens 4 nibbles actief gaan zijn, tegen 1 nibble bij keuze 3. Het activeren van beide S-boxen bij keuze 3 maakt het de aanvaller namelijk mogelijk de 12 ingangsbits van de M-box zo aan te wenden dat slechts één nibble actief is aan de uitgang van de M-box. Hierdoor blijkt keuze 3 algemeen de beste keuze te zijn. De aanvaller zal er dus voor kiezen om in de eerste ronde, nibble nummer 1 te desactiveren om zo, over 7 rondes, een optimale differentieelkarakteristiek te bekomen met een minimum van 2 actieve 5 bit S-boxen en één actieve 7 bit S-box.

6.1.3

De veiligheid van EFES tegen differenti¨ ele aanvallen

Tijdens ronde 6 en bij keuze 3 zal een aanvaller gebruik maken van het actief worden van beide S-boxen om de uitgangen zo aan te wenden dat slechts 1 nibble nog actief is aan de uitgang van de M-box. Dit kan nibble nummer 2, 3 of 4 zijn en opnieuw heeft de aanvaller drie keuzes: 1. De aanvaller kiest er voor om nibble nummer 3 actief te maken. Na ronde 10 zal deze nibble aan de ingang van de 5 bit S-box staan zoals te zien in figuur 6.1.e. Dezelfde situatie als aan het begin van de eerste ronde doet zich nu voor en de vorige redeneringen kunnen dus worden doorgetrokken over de verdere rondes met dit keer nibbles nummer 3, 4 en 5 in plaats van nibbles nummer 1, 2 en 3. 2. De aanvaller maakt nibble nummer 4 actief waardoor deze tijdens ronde 11 de 5 bit S-box, de 7 bit S-box of beide zal activeren. Deze keuze resulteert niet in een differentieelkarakteristiek met een grotere kans van optreden dan bij keuze 1 en zal door een aanvaller niet genomen worden. 49


3. Een derde keuze die de aanvaller kan maken is om nibble nummer 2 actief te maken. Aan het einde van ronde 11 zal deze nibble aan de ingang van de 7 bit S-box staan waardoor deze in de twaalfde ronde zal geactiveerd worden. Hierbij kunnen opnieuw de vorige redeneringen gevolgd worden dit keer met nibbles nummer 0, 1 en 2 in plaats van nibbles nummer 1, 2 en 3, zoals voorgesteld op figuur 6.1.f. Zoals beschreven in vergelijking 3.10 moet om differentiële aanvallen tegen te gaan, de kans DP dat een differentieel over het hele cijfer optreedt groter zijn dan de inverse van het maximaal aantal beschikbare (klaartekst, cijfertekst)-paren. Deze kans moet voor het blokcijfer EFES dus groter zijn dan 2−64 . Bij de eerste en tweede keuze zal de differentieelkarakteristiek over 10 rondes, steeds minstens twee actieve 5 bit S-boxen en één actieve 7 bit S-box bevatten. Deze 5 bit en 7 bit S-boxen hebben respectievelijk een DP van 2−4 en 2−6 . De grootste kans waarmee een differentieel kan optreden over deze 10 rondes is dus via formule (3.11) gelijk aan 2−14 . Wanneer de aanvaller het aantal actieve S-boxen minimaliseert via keuze 1, zijn dus 5 keer 10 rondes nodig om genoeg veiligheid te bieden. Over deze 50 rondes zijn dan tien 5 bit S-boxen en vijf 7 bit S-boxen actief. De kans dat een differentieel optreedt over 50 rondes is dan maximaal gelijk aan 2−70 . Bij de derde keuze kan zal de differentieelkarakteristiek over 11 rondes, steeds minstens één actieve 5 bit S-box en twee actieve 7 bit S-boxen bevatten. Enkel de eerste cyclus van 11 rondes van het cijfer is hierop een uitzondering, waarbij minimum twee 5 bit S-boxen en minimum één 7 bit S-box geactiveerd worden. Dit komt omdat er aan de start van deze cyclus kan worden gekozen welke nibbles actief zijn. Daarna bepaald de keuze van de aanvaller zoals hierboven vermeld, welke niblles actief zijn en kan de aanvaller niet meer rechtstreeks kiezen welke niblles actief zijn. Aan het begin van elke extra cyclus van 11 rondes zal namelijk altijd een 7 bit S-box geactiveerd worden (zie keuze 3). De grootste kans waarmee een differentieel kan optreden over deze eerste 11 rondes is gelijk aan 2−14 . De kans waarmee een differentieel kan optreden voor de daarop volgende blokken van 11 rondes zal per blok maximaal gelijk zijn aan 2−16 . Bij keuze 3 zijn er 44 rondes nodig om tot een differentieelkarakteristiek te komen met een maximale kans DP van optreden gelijk aan 2−62 . Dit komt doordat in deze 44 rondes minstens vijf 5 bit S-boxen en zeven 7 bit S-boxen geactiveerd worden. Dit in niet voldoende om veiligheid tegen dit type aanvallen te garanderen en er moeten dus nog extra rondes worden toegevoegd. Na elke blok van 11 rondes zal in de volgende ronde van het cijfer steeds een 7 bit S-box worden geactiveerd. Daarna duurt het nog eens 4 rondes om de actieve nibbles terug aan de ingang van de S-boxen te brengen. Met 5 extra rondes wordt hierdoor een differentieel over 49 rondes bekomen die met een maximale kans van 2−68 optreedt. De veiligheid van het blokcijfer EFES tegen differentiële cryptanalyse kan worden herleid tot volgend theorema: Theorema 1 Elke differentieelkarakteristiek over 11 rondes van EFES heeft een minimum van drie actieve S-boxen waarvan minimum één 5 bit S-box en minimum twee 7 bit S-boxen. Enkel de eerste cyclus van 11 rondes van het cijfer is hierop een uitzondering, waarbij minimum twee 5 bit S-boxen en minimum één 7 bit S-box geactiveerd worden.

50

Veiligheid tegen lineaire cryptanalyse

6.1.4

Het totaal aantal rondes van EFES

Wanneer het blokcijfer EFES minstens 49 rondes telt zal de beste differentieelkarakteristiek die te vinden valt, met geen grotere kans dan DP gelijk aan 2−68 optreden. Na 50 rondes zal de beste differentieel met een kans 2−70 optreden. Bij deze rondes moeten dan wel nog eens 5 rondes worden bijgeteld omdat de aanvaller ervoor kan kiezen om de actieve bits van de ingangsverschilwaarde in nibble nummer 4 te kiezen. Deze nibble heeft 5 rondes nodig voordat hij aan de ingang van de substitutie-functie terecht komt. Dit is te zien in figuur 6.1.a en 6.1.b. Verder moeten nog eens 6 extra rondes worden bijgeteld omdat de eerste 6 rondes van het blokcijfer EFES enkel dienen om een eerste reeks deelsleutels aan de toestand van de data op te tellen. Deze rondes zorgen er dus voor dat aan het begin van dit type aanvallen, enkel de ingangsverschilwaarden gekend zijn en niet de ingangen zelf. Dit werd reeds in hoofdstuk 2.4 aangehaald. Uiteindelijk moet er dan nog 1 laatste ronde worden toegevoegd omdat een differentieelkarakteristiek wordt gebouwd tot aan de voorlaatste ronde. Hiervoor is maar 1 extra ronde nodig omdat na 49 of 50 rondes, afhankelijk van de keuzes van de aanvaller, de gekozen actieve nibbles steeds in de volgende ronde al door de substitutie-functie worden gestuurd. In totaal zijn dus minstens 62 rondes nodig om het cijfer EFES tegen differentiële cryptanalyse te beveiligen. Voor een maximale DP van 268 zullen er volgens vergelijking 3.10 namelijk minstens 268 (klaartekst, cijfertekst)-paren nodig zijn om een differentiële aanval op te zetten. Dit is zeker niet efficiënter dan de 264 paren die nodig zijn om de gebruikte sleutel volledig te kenmerken. Uiteindelijk wordt voorgesteld om EFES te implementeren met 64 rondes per 64 bit encryptie zodat geen extra controle logica nodig is voor de 6 bit teller.

6.2

Veiligheid tegen lineaire cryptanalyse

Een aanvaller gaat zoals vermeld in hoofdstuk 3, op zoek naar de meest optimale lineaire benadering. Dit is een lineaire benadering die met een zo groot mogelijk bias ε afwijkt van een 50% kans van optreden. Hiervoor bevat deze benadering, over de verschillende rondes van het cijfer, een minimum aan actieve S-boxen. Zoals uitgelegd in vergelijking 3.16 is de bias ε van een lineaire benadering namelijk kwadratisch omgekeerd evenredig met het aantal gekozen (klaartekst, cijfertekst)-paren die nodig zijn om de aanval te doen werken. Het blokcijfer EFES zal veilig zijn tegen dit type aanvallen wanneer het totaal aantal gekozen (klaartekst, cijfertekst)-paren die nodig zijn om de aanval op te stellen, groter is dan het maximaal aantal beschikbaar, namelijk 264 . Vanuit het standpunt van de aanvaller wordt nu op zoek gegaan naar de beste lineaire benadering die voor EFES te vinden is. Zoals uitgelegd in hoofdstuk 4.2 hebben de gebruikte S-boxen een willekeurige verdeling van het al dan niet optreden van een niet-nul bias van een bepaalde lineaire benadering. Bij het vinden van de beste lineaire benadering wordt dus aangenomen dat de aanvaller steeds kan kiezen welke lineaire benadering van de S-box met een bias ε optreedt. Net als bij het vinden van een optimale differentieelkarakteristiek is het daarom de M-box zoals gedefinieerd in vergelijking (4.1) en vergelijking (4.2) die ervoor zal zorgen dat de aanvaller niet steeds kan kiezen voor een lineaire benadering met slechts één actieve S-box per ronde. 51


Dezelfde veronderstellingen over de S-boxen worden dus aangenomen als bij het afleiden van de beste differentieelkarakteristiek in het vorige deel. Het aantal actieve S-boxen over alle rondes zal bijgevolg dezelfde zijn voor de beste lineaire benadering als voor de beste differentieelkarakteristiek. Over 62 rondes wordt hiermee bekomen dat de lineaire benadering met de grootste bias ε een bias heeft die gelijk is aan 2−56 . Dit werd bekomen uit formule (3.18) wanneer geweten is dat over deze 62 rondes minstens vijf 5 bit S-boxen en acht 7 bit S-boxen actief zijn met respectievelijk een bias van 2−3 en 2−4 . Uit formule (3.16) kan dan worden gevonden dat 272 gekende (klaartekst, cijfertekst)-paren nodig zijn om een lineaire aanval op te zetten. Dit is veel meer dan de 264 paren die nodig zijn om de gebruikte sleutel volledig te kenmerken.

52

Hoofdstuk 7

Performantie van het blokcijfer EFES Nadat het blokcijfer EFES werd ontworpen en de veiligheid van dit cijfer werd aangetoond, moet nu ook worden gekeken naar de performantie van EFES. Het uitgangspunt van dit eindwerk was namelijk een symmetrisch cryptografisch cijfer te bouwen met een zeer lage kost in hardware. Het cijfer heeft dan een zeer klein oppervlakte nodig wanneer het wordt gebruikt op een RFID-tag. De vooropgestelde doelstelling was om het blokcijfer Present [4] te verslaan op het vlak van oppervlaktegebruik, zonder daardoor de veiligheid van het ontworpen cijfer in gevaar te brengen. In een eerste deel wordt gekeken hoeveel Gate Equivalenten (GE) de hardware-implementatie van EFES nodig heeft. Daarna wordt dit resultaat in een tweede deel vergeleken met de resultaten van andere blokcijfers en in het bijzonder met het blokcijfer Present. In deze vergelijking wordt EFES eveneens met enkele stroomcijfers zoals Grain [25] vergeleken. Ten slotte wordt in een laatste deel kort het vermogenverbruik van EFES besproken en vergeleken met andere symmetrische cijfers.

7.1

Oppervlaktegebruik van het blokcijfer EFES

De hardware-implementatie van EFES gebeurde aan de hand van de GEZEL-omgeving en is terug te vinden in bijlage B. Deze code werd vervolgens eerst naar VHDL overgezet om dan aan de hand van Synopsys Design Vision, met een 0.13 µm CMOS Low Leakage UMC standard cell library, te worden gecompileerd. Het 12 bit datapad van EFES werd reeds voorgesteld in figuur 4.1 en figuur 4.2 waar in elke klokcyclus een ronde van het cijfer wordt uitgevoerd. In tabel 7.1 wordt het oppervlaktegebruik in aantal GE van de verschillende componenten van EFES samengevat. Hardwarekost van de bouwblokken van EFES De grootste kost gaat bij EFES naar de registers waarin de sleuteltoestand en de datatoestand na elke ronde worden opgeslaan. Deze bestaan namelijk uit flip-flops die per bit die wordt 53

7. Performantie van het blokcijfer EFES

Component

Aantal GE

% Totaal

Datatoestand S7 [X] S5 [X] M-box Deelsleuteloptelling Rotatie

399.5 201.75 85 60 30 0

30.1 15.2 6.4 4.5 2.2 0

Sleuteltoestand S3 [X] Telleroptelling Rotatie

499.3 10.5 5 0

37.6 0.8 0.4 0

Teller Totaal

37.45 1328.5

2.8 100

Tabel 7.1: Oppervlaktegebruik van het blokcijfer EFES in aantal GE.

opgeslagen een kost van gemiddeld 6.24 GE hebben. Hier moet wel bij worden gemeld dat deze flip-flops ook de multiplexers bevatten die nodig zijn om bij de start van elke encryptie de 64 bit data en 80 bit sleutel in te laden. Naast deze registers verbruikt de 7 bit S-box eveneens een niet te verwaarlozen oppervlakte. De andere componenten hebben een veel kleiner kost in hardware en de rotaties hebben helemaal geen kost omdat deze rechtstreeks via bedrading ge¨ımplementeerd worden.

De implementatie van de S-boxen Wanneer de 7 bit S-box wordt ge¨ımplementeerd via een lookup table wordt meteen duidelijk waarom een implementatie via poort logica werd verkozen. In ROM ge¨ımplementeerd zal de 7 bit S-box namelijk 369.75 GE kosten tegen 201.75 GE in poortlogica. Omdat de kost van de 5 bit S-box met zijn 85 GE al zeer klein is, werd niet verder gezocht naar een implementatie in poort logica. Dit zou evenwel in de toekomst nog kunnen gebeuren om een extra winst in oppervlaktegebruik te bekomen. Voor de 3 bit S-box uit het key scheduling algoritme kan dezelfde redenering worden gemaakt.

7.2

Vergelijking van de hardware-performantie van EFES met dat van andere symmetrische cijfers

In tabel 7.2 wordt het blokcijfer EFES vergeleken met andere blok- en stroomcijfers. Om een juist beeld te krijgen van de verschillen wordt niet alleen hun respectievelijk oppervlaktegebruik vergeleken maar ook andere eigenschappen. Zo wordt ook de sleutellengte, de bloklengte, het aantal klokcycli nodig voor de versleuteling van één blok, de doorvoer in kilobits per seconde (kbps) bij een kloksnelheid van 100 kHz en de gebruikte technologie van de implementatie gegeven. 54

Vermogenverbruik van het blokcijfer EFES

Blokcijfers: EFES Present [4] AES [21] HIGHT [28] DES [46] DESXL [46] Stroomcijfers: Grain [25] Trivium [15]

Sleutellengte

Bloklengte

Klokcycli

Doorvoer

80 80 128 128 56 184

64 64 128 64 64 64

64 32 1032 34 144 144

100 kbps 200 kbps 12.4 kbps 188.2 kbps 44.4 kbps 44.4 kbps

80 80

1 1

1 1

100 kbps 100 kbps

Technologie 0.13 0.18 0.35 0.25 0.18 0.18

µm µm µm µm µm µm

0.13 µm 0.13 µm

GE 1328.5 1570 3400 3048 2309 2168 1294 2599

Tabel 7.2: Vergelijking tussen compacte symmetrische cijfers.

Op het vlak van oppervlaktegebruik is het blokcijfer EFES het meest compacte van alle blokcijfers. Onafhankelijk van de gebruikte technologie zal EFES minder GE nodig hebben dan de andere blokcijfers. EFES heeft zelfs 241.5 minder GE nodig dan Present dat tot nu toe het kleinste, gepubliceerde, blokcijfer was. De doelstelling van het eindwerk werd dus met verve gehaald. Wel blijkt dat EFES twee keer trager is dan Present. Door het aantal S-boxen te vergroten en de M-box aan te passen kan weliswaar een grotere snelheid worden behaald. De eenvoudigste manier om dit te doen is door twee keer zoveel S-boxen en twee M-boxen te gebruiken. Door de rotatie in elke ronde te verdubbelen kan dan in parallel twee keer zo vlug worden gewerkt, zonder dat de vercijfering verschilt ten opzichte van de oorspronkelijke versie van EFES. De aangepaste versie van EFES zou dan wel ongeveer 100 GE meer nodig hebben dan Present. Dit komt door de grote kost die een extra 7 bit S-box met zich mee brengt. Ook in vergelijking met stroomcijfers moet EFES niet onderdoen. Terwijl men er meestal van uit gaat dat stroomcijfers compacter kunnen gemaakt worden dan blokcijfers, bewijst EFES dat het verschil kan geminimaliseerd worden. Het stroomcijfer Grain, dat tot nog toe, het kleinste gepubliceerde symmetrische cijfer is, heeft namelijk slecht 34.5 GE minder nodig dan EFES en dit voor eenzelfde doorvoer. Hier komt nog bij dat Grain zwakke punten bevat op het gebied van veiligheid terwijl dat bij EFES voorlopig niet het geval is. Ook bestaan heel wat bezwaren om stroomcijfers toe te passen op RFID-communicaties, zoals besproken in hoofdstuk 2.1. Omwille van de voorgaande redenen, lijkt EFES voorlopig de beste keuze te zijn bij gebruik van een symmetrisch cijfer voor RFID-toepassingen.

7.3

Vermogenverbruik van het blokcijfer EFES

Voor het berekenen van het vermogenverbruik van EFES werd net als voor het berekenen van het aantal GE gebruik gemaakt van Synopsys Design Vision nadat de VHDL-code werd gecompileerd met een 0.13 µm CMOS Low Leakage UMC standard cell library. Hiervoor werd gebruik gemaakt van een 1.2 V vermogenbron voor de standaardcellen en een 3.3 V vermogenbron voor de ingangs/uitgangscellen bij een klokfrequentie van 1 MHz. Hieruit blijkt 55

7. Performantie van het blokcijfer EFES

dat EFES een dynamisch vermogenverbruik heeft van ongeveer 5.23 µWatt en een lekvermogen van 5.56 nWatt. EFES verbruikt bijgevolg een totaal vermogen van 5.235 µWatt. Dit is vergelijkbaar met het vermogenverbruik van het blokcijfer Present (5 µWatt [4]) en veel kleiner dan dat van het stroomcijfer Grain (109.45 µWatt [24]). Dit zeer laag vermogenverbruik is zodoende klein genoeg is om bruikbaar te zijn voor RFID toepassingen, zoals uitgelegd in hoofdstuk 1.1.

56

Hoofdstuk 8

Besluit In dit eindwerk werd op zoek gegaan naar een compact symmetrisch cijfer, bestemd voor gebruik in lage kost RFID-toepassingen. Het symmetrisch cijfer EFES (Encryption Function for Embedded Systems) werd hiertoe ontworpen. Eerst worden kort de belangrijkste eigenschappen van EFES nog eens samengevat om daarna de mogelijkheden tot verder onderzoek en aanpassingen aan te stippen.

Het blokcijfer EFES Eerst en vooral werd gekozen om met een blokcijferstructuur te werken. Deze beslissing werd genomen nadat in hoofdstuk 2.1 gebleken was dat stroomcijfers, om verschillende reden, niet geschikt zijn voor RFID-toepassingen. Vervolgens werden de algemene eigenschappen van het blokcijfer EFES afgeleid in functie van de voorwaarden die RFID-communicaties en in het bijzonder RFID-tags opleggen. Zo bestaat EFES uit een 80 bit sleutel en word de data in blokken van 64 bit versleuteld. Voor de structuur van het blokcijfer werd lichtjes afgeweken van de bestaande structuren. Op die manier kan het cijfer voldoende compact in hardware worden ge¨ımplementeerd. Verder moest het blokcijfer EFES veilig zijn tegen aanvallen vlugger dan exhaustief zoeken naar de sleutel. De bouwblokken en hun onderlinge werking werden zo gekozen dat het cijfer veiligheid garandeert tegen de meest voorkomende aanvallen op blokcijfers, met name lineaire en differentiële cryptanalyse. Nadat de bouwblokken gedefinieerd waren, werd aangetoond dat de 64 rondes, die EFES nodig heeft om een 64 bit blok te versleutelen, voldoende zijn om de veiligheid tegen deze aanvallen te garanderen. Ten slotte werd de performantie van het blokcijfer EFES nagegaan. Zo heeft het blokcijfer slechts 1328.5 GE nodig wanneer het in hardware wordt ge¨ımplementeerd. Dit is beter dan alle bestaande blokcijfers en zo goed als even compact als het kleinste stroomcijfer. Verder wordt het vermogenverbruik van EFES geschat op ongeveer 5 µWatt. De resultaten van het blokcijfer EFES bewijzen dat het cijfer een zeer compacte, veilige en bruikbare oplossing biedt voor gebruik bij de beveiliging van RFID-communicaties. Hierbij moet wel worden vermeld dat, zoals bij elk nieuw voorstel tot cryptografische primitieven, aangeraden wordt het cijfer eerst een verdere periode van cryptanalyse te laten ondergaan. Als 57

8. Besluit

het blokcijfer daarna nog steeds veilig blijkt te zijn, kan het in de praktijk worden gebruikt. Wat de toekomst kan brengen De veiligheid van het cijfer tegen aanvallen verschillend van lineaire en differentiële aanvallen moet verder onderzocht worden. Hierbij kunnen, indien nodig, de gebruikte S-boxen en het totaal aantal rondes per versleuteling worden aangepast, zonder dat het oppervlaktegebruik sterk toeneemt. De nieuwe structuur die in dit eindwerk wordt voorgesteld zou in de toekomst kunnen worden uitgebreid. Een algemene methode zou kunnen worden opgesteld om gegeven de sleutel- en bloklengte van het gewenste cijfer en het aantal rondes waarin een blok zou moeten worden geëncrypteerd, het type S-boxen en de bijhorende lineaire combinatie en rotatie te bekomen. Op die manier zou bij nood aan compacte beveiliging voor een bepaalde toepassing, steeds een op maat gemaakt blokcijfer worden berekend. Een ander punt waaraan in de toekomst zou kunnen worden gewerkt is een methode voor het zoeken naar nog efficiëntere S-boxen. Zoals vermeld in hoofdstuk 5.1 kan een goed gekozen S-box vermijden dat een lineaire combinatie nodig is. Dit zorgt bijgevolg, zonder verlies aan veiligheid, voor een kleiner oppervlaktegebruik bij de hardware-implementatie van het cijfer. Zonder een te grote extra kost in hardware kan EFES mogelijk versneld worden. Hiervoor moet worden gebruik gemaakt van een grotere M-box die naast de bits aan de uitgang van de S-boxen, ook andere bits van de datatoestand combineert. Hierdoor kan het aantal actieve nibbles in elke ronde worden verhoogd. Zoals uitgelegd in hoofdstuk 6 zal het aantal actieve S-boxen hierdoor eveneens verhogen en zullen in totaal minder rondes nodig zijn. Ten slotte zou een blokcijfer met de structuur van EFES mogelijk nog compacter kunnen worden ge¨ımplementeerd, indien gebruik wordt gemaakt van kleinere S-boxen. Om de veiligheid te blijven garanderen zouden dan wel meer rondes van het cijfer nodig zijn. Er moet dus een afweging gebeuren tussen snelheid en oppervlaktegebruik. Zo zou de substitutiefunctie bijvoorbeeld kunnen vervangen worden door een 3 bit S-box in combinatie met een 4 bit S-box en een 5 bit S-box.

58

Bibliografie [1]

COPACOBANA: A Codebreaker for DES and other Ciphers. last checked: 16/4/2008.

[2]

The ECRYPT Stream Cipher Project. last checked: 14/4/2008.

[3]

Transport for London: The Oyster Card. last checked: 30/4/2008.

[4] A.Bogdanov, L. Knudsen, G. Leander, C. Paar, A. Poschmann, M. Robshaw, Y. Seurin, and C. Vikkelsoe. PRESENT: An Ultra-Lightweight Block Cipher. In CHES, pages 450–466, 2007. [5] C. Adams. Designing against a class of algebraic attacks on symmetric block ciphers. Appl. Algebra Eng., Commun. Comput., 17(1):17–27, 2006. [6] S. Babbage, D. Catalano, L. Granboulan, A. Lenstra, C. Paar, J. Pelzl, T. Pornin, B. Preneel, M. Robshaw, A. Rupp, N. Smart, and M. Ward. ECRYPT Yearly Report on Algorithms and Keysizes. Christian Gehrmann and Mats Näslund, 2006. [7]

S. Babbage and M. Dodd. MICKEY 2.0, 2006.

[8]

L. Batina, S. Kumar, J. Lano, K. Lemke, N. Mentens, C. Paar, B. Preneel, K. Sakiyama, and I. Verbauwhede. Testing Framework for eSTREAM Profile II Candidates. In SASC, 2006. ¨ B. Preneel, and I. Verbauwhede. Energy, perfor[9] L. Batina, J. Lano, N. Mentens, S. Ors, mance, area versus security trade-offs for stream ciphers. In In The State of the Art of Stream Ciphers, pages 302–310, 2004. [10] E. Biham. New Types of Cryptanalytic Attacks Using Related Keys. LNCS, 765:398, 1994. [11] E. Biham and A. Shamir. Differential Cryptanalysis of the Data Encryption Standard. LNCS, 576:156, 1991. [12] E. Biham and A. Shamir. Differential Cryptanalysis of the Full 16-Round DES. In CRYPTO, page 487, 1992. [13] A. Biryukov and D. Wagner. Advanced Slide Attacks. LNCS, 1807:589–, 2000. [14] M. Brazzarola and F. Fummi. Power Characterization of LFSRs. In DFT ’99: Proceedings of the 14th International Symposium on Defect and Fault-Tolerance in VLSI Systems, pages 139–147, 1999. [15] C. De Cannière. Trivium: A Stream Cipher Construction Inspired by Block Cipher Design Principles. In ISC, pages 171–186, 2006. [16] J. Daemen and V. Rijmen. Rijndael for AES. In AES Candidate Conference, pages 343–348, 2000. 59

Bibliografie

[17] M. Dichtl. On Nonlinear Filter Generators. In FSE ’97: Proceedings of the 4th International Workshop on Fast Software Encryption, pages 103–106, 1997. [18] D. Dobkin. A Radio-Oriented Introduction to RFID-Protocols, Tags and Applications. In High Frequency Electronics, Summit Technical Media, 2005. [19] M. Feldhofer, M. Aigner, and S. Dominikus. An application of RFID tags using secure symmetric authentication. In Security, Privacy and Trust in Pervasive and Ubiquitous Computing, 2005. [20] M. Feldhofer, S. Dominikus, and J. Wolkerstorfer. Strong authentication for RFID systems using the AES algorithm. In Proceedings of CHES, LNCS, volume 3156, pages 357–370, 2004. [21] M. Feldhofer, J. Wolkerstorfer, and V. Rijmen. AES Implementation on a Grain of Sand. In IEEE Proc, volume 152, pages 13–20, 2005. [22] D. Gligoroski, S. Markovski, L. Kocarev, and M. Gusev. Edon80, 2005. [23] J. Golic. On the Security of Nonlinear Filter Generators. In Proceedings of the Third International Workshop on Fast Software Encryption, pages 173–188, 1996. [24] T. Good and M. Benaissa. Hardware Results for Selected Stream Cipher Candidates. In Workshop Record State of the Art of Stream Ciphers (SASC 07), 2007. [25] M. Hell, T. Johansson, and W. Meier. Grain: a stream cipher for constrained environments. Int. J. Wire. Mob. Comput., 2(1):86–93, 2007. [26] M. Hellman. A Cryptanalytic Time-Memory Trade-off. IEEE Transactions on Information Theory,, 26(4):401–406, 1980. [27] H. Heys. A Tutorial on Linear and Differential Cryptanalysis. Cryptologia, 26(3):189–221, 2002. [28] D. Hong, J. Sung, S. Hong, J. Lim, S. Lee, B. Koo, C. Lee, D. Chang, J. Lee, K. Jeong, H. Kim, J. Kim, and S. Chee. HIGHT: A New Block Cipher Suitable for Low-Resource Device. In CHES, pages 46–59, 2006. [29] J. Hong. Remarks on the Period of Edon80, 2005. [30] J. Hong and P. Sarkar. Rediscovery of Time Memory Tradeoffs, 2005. [31] International Organisation for Standardisation. ISO/IEC 9798-2: Information Technology - Security techniques - Entity Authentication Mechanisms Part 2: Entity authentication using symmetric techniques., 1993. [32] International Organisation for Standardisation. ISO/IEC 18000-3. Information Technology AIDC Techniques - RFID for Item Management, 2003. [33] C. Jansen, T. Helleseth, and A. Kholosha. Cascade jump controlled sequence generator, 2005. [34] A. Juels, R. Rivest, and M. Szydlo. The Blocker Tag: Selective Blocking of RFID Tags for Consumer Privacy, 2003. [35] A. Lenstra. Key Lengths. In Contributions Paper on Cryptographic Key Lengths to the Information Security Management Handbook. Harold F. Tipton, 2004. [36] A. Lenstra and E. Verheul. Selecting Cryptographic Key Sizes. Journal of Cryptology: the journal of the International Association for Cryptologic Research, 14(4):255–293, 2001. 60

[37] C. Lim and T. Korkishko. mCrypton - A Lightweight Block Cipher for Security of Low-Cost RFID Tags and Sensors. In WISA, pages 243–258, 2005. [38] M. Matsui. Linear Cryptanalysis Method for DES Cipher. LNCS, 765:386, 1994. [39] M. Matsui. New Structure of Block Ciphers with Provable Security against Differential and Linear Cryptanalysis. In Proceedings of the Third International Workshop on Fast Software Encryption, pages 205–218, 1996. [40] M. Matsui. New Block Encryption Algorithm MISTY. In FSE ’97: Proceedings of the 4th International Workshop on Fast Software Encryption, pages 54–68, 1997. [41] A. Maximov. Cryptanalysis of the ‘Grain’ family of stream ciphers. In ASIACCS ’06: Proceedings of the 2006 ACM Symposium on Information, computer and communications security, pages 283–288, 2006. [42] A. Menezes, P. van Oorschot, and S. Vanstone. Handbook of Applied Cryptography. Number ISBN: 0849385237. CRC Press, 1996. [43] K. Nyberg. Differentially uniform mappings for cryptography. In EUROCRYPT ’93: Workshop on the theory and application of cryptographic techniques on Advances in cryptology, pages 55–64, 1994. [44] K. Nyberg. Linear approximation of block ciphers. In Advances in Cryptology - EUROCRYPT’94, volume 950 of LNCS, pages 439–444, 1995. [45] L. O’Connor and J. Golic. A Unified Markov Approach to Differential and Linear Cryptanalysis. 917:385, 1995. [46] A. Poschmann, G. Leander, K. Schramm, and C. Paar. New Lighweight Crypto Algorithms for RFID. In Proceedings of The IEEE International Symposium on Circuits and Systems – ISCAS, pages 1843–1846, 2007. [47] B. Preneel. An Introduction to Modern Cryptology. Cursus B-KUL-H05E1A: Cryptografie en netwerkbeveiliging, 2007. [48] B. Preneel, V. Rijmen, and A. Bosselaers. Recent Developments in the Design of Conventional Cryptographic Algorithms. LNCS, 1528:105–130, 1998. [49] S. Sarma, D. Brock, and D. Engels. Radio Frequency Identification and the Electronic Product Code. IEEE Micro, 21(6):50–54, 2001. [50] S. Sarma, S. Weis, and D. Engels. RFID Systems and Security and Privacy Implications. In Workshop on Cryptographic Hardware and Embedded Systems, volume 2523 of LNCS, pages 454–470, 2002. [51] C. Shannon. Communication Theory of Secrecy Systems. Bell System Technical Journal, 28(4):656–715, 1949. [52] F. Standaert, G. Piret, N. Gershenfeld, and J. Quisquater. SEA: a Scalable Encryption Algorithm for Small Embedded Applications. In CARDIS, pages 222–236, 2006. [53] B. Toiruul and K. Lee. An Advanced Mutual-Authentication Algorithm Using AES for RFID Systems. In IJCSNS, volume 6, pages 156–162, 2006. [54] S. Weis. Security and Privacy in Radio-Frequency Identification Devices. Master’s thesis, Massachusetts Institute of Technology, 2003. [55] S. Weis, S. Sarma, R. Rivest, and D. Engels. Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems. In SPC, pages 201–212, 2003. 61

Bibliografie

[56] D. Wheeler and R. Needham. TEA, a Tiny Encryption Algorithm. In FSE, pages 363–366, 1994.

62

Bijlage A

Testvectoren De testvectoren voor EFES worden in hexadecimale notatie weergegeven. De minst significante bits komen overeen met de meest rechtse bits van elk woord. Klaartekst 00000000 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF EFFFFFFF FFFFFFFF

Sleutel 00000000 FFFFFFFF 00000000 EFFFFFFF FFFFFFFF FFFFFFFF

00000000 FFFFFFFF 00000000 FFFFFFFF FFFFFFFF FFFFFFFF

63

0000 FFFF 0000 FFFF FFFF FFFF

Cijfertekst 707198C2 D068D83E BFD3B78D 6608F73A 52A6AB61 F49FB459 055ECF9E 3978E269 ACC48F64 D153FC0D 6379ED13 3ADE216B

Bijlage B

De GEZEL implementatie van EFES dp efes(in plain : ns(64) ; in key : ns(80) ; in start : ns(1); out cipher : ns(64) ; out finish out : ns(1)) { reg dataregister : ns(64); reg keyregister : ns(80); reg cnt : ns(6); lookup s3 : ns(3) = {0, 5, 6, 7, 4, 3, 1, 2}; lookup s5 : ns(3) = {6, 7, 3, 16, 23, 31, 2, 24, 25, 30, 20, 1, 18, 28, 15, 19, 10, 0, 17, 9, 22, 21, 29, 12, 8, 4, 27, 5, 14, 11, 13, 26}; sig sig sig sig sig sig

mbox out : ns(12); cipher out : ns(12); finish : ns(1); key xor : ns(12); shift12 in : ns(64); shift12 out : ns(64);

//s-box signalen: sig s5x : ns(5); sig s5y : ns(5); sig s71x0, s71x1, s71x2, s71x3, s71x4, s71x5, s71x6 : ns(1); sig s71y0, s71y1, s71y2, s71y3, s71y4, s71y5, s71y6 : ns(1); //m-box signalen: sig a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12 : ns(1); sig m51y0, m51y1, m51y2, m51y3, m51y4 : ns(1); sig m71y0, m71y1, m71y2, m71y3, m71y4, m71y5, m71y6 : ns(1); //keyscheduling signalen: sig shift3 out : ns(80); sig subkey : ns(12); sig counter xor : ns(2); sig s3x : ns(3); sig s3y : ns(3); 64

sig shift19 in, shift19 out : ns(80); sfg encrypt{ //datapad: cipher = shift12 out; dataregister = start ? plain : shift12 out; cipher out = dataregister[11:0]; //s-boxdeel s5x = cipher out[4:0]; s5y = s5(s5x); s71x0 s71x1 s71x2 s71x3 s71x4 s71x5 s71x6

= = = = = = =

cipher cipher cipher cipher cipher cipher cipher

out[5]; out[6]; out[7]; out[8]; out[9]; out[10]; out[11];

s71y0 = s71x0 ˆ s71x1&s71x3 ˆ s71x0&s71x3&s71x4 ˆ s71x1&s71x5 ˆ s71x0&s71x2&s71x5 ˆ s71x4&s71x5 ˆ s71x0&s71x1&s71x6 ˆ s71x2&s71x6 ˆ s71x0&s71x5&s71x6 ˆ s71x3&s71x5&s71x6 ˆ 1; s71y1 = s71x0&s71x2 ˆ s71x0&s71x4 ˆ s71x3&s71x4 ˆ s71x1&s71x5 ˆ s71x2&s71x4&s71x5 ˆ s71x6 ˆ s71x0&s71x6 ˆ s71x3&s71x6 ˆ s71x2&s71x3&s71x6 ˆ s71x1&s71x4&s71x6 ˆ s71x0&s71x5&s71x6 ˆ 1; s71y2 = s71x1&s71x2 ˆ s71x0&s71x2&s71x3 ˆ s71x4 ˆ s71x1&s71x4 ˆ s71x0&s71x1&s71x4 ˆ s71x0&s71x5 ˆ s71x0&s71x4&s71x5 ˆ s71x3&s71x4&s71x5 ˆ s71x1&s71x6 ˆ s71x3&s71x6 ˆ s71x0&s71x3&s71x6 ˆ s71x4&s71x6 ˆ s71x2&s71x4&s71x6; s71y3 = s71x0 ˆ s71x1 ˆ s71x0&s71x1&s71x2 ˆ s71x0&s71x3 ˆ s71x2&s71x4 ˆ s71x1&s71x4&s71x5 ˆ s71x2&s71x6 ˆ s71x1&s71x3&s71x6 ˆ s71x0&s71x4&s71x6 ˆ s71x5&s71x6 ˆ 1; s71y4 = s71x2&s71x3 ˆ s71x0&s71x4 ˆ s71x1&s71x3&s71x4 ˆ s71x5 ˆ s71x2&s71x5 ˆ s71x1&s71x2&s71x5 ˆ s71x0&s71x3&s71x5 ˆ s71x1&s71x6 ˆ s71x1&s71x5&s71x6 ˆ s71x4&s71x5&s71x6 ˆ 1; s71y5 = s71x0 ˆ s71x1 ˆ s71x2 ˆ s71x0&s71x1&s71x2 ˆ s71x0&s71x3 ˆ s71x1&s71x2&s71x3 ˆ s71x1&s71x4 ˆ s71x0&s71x2&s71x4 ˆ s71x0&s71x5 ˆ s71x0&s71x1&s71x5 ˆ s71x3&s71x5 ˆ s71x0&s71x6 ˆ s71x2&s71x5&s71x6; s71y6 = s71x0&s71x1 ˆ s71x3 ˆ s71x0&s71x3 ˆ s71x2&s71x3&s71x4 ˆ s71x0&s71x5 ˆ s71x2&s71x5 ˆ s71x3&s71x5 ˆ s71x1&s71x3&s71x5 ˆ s71x1&s71x6 ˆ s71x1&s71x2&s71x6 ˆ s71x0&s71x3&s71x6 ˆ s71x4&s71x6 ˆ s71x2&s71x5&s71x6; //mbox deel: a1 = s5y[0]; a2 = s5y[1]; a3 = s5y[2]; a4 = s5y[3]; a5 = s5y[4]; a6 = s71y0; a7 = s71y1; a8 = s71y2; 65

B. De GEZEL implementatie van EFES

a9 = s71y3; a10 = s71y4; a11 = s71y5; a12 = s71y6; m51y0 m51y1 m51y2 m51y3 m51y4 m71y0 m71y1 m71y2 m71y3 m71y4 m71y5 m71y6

= = = = = = = = = = = =

a1 a2 a3 a4 a4 a1 a2 a3 a1 a2 a3 a4

ˆ ˆ ˆ ˆ ˆ ˆ ˆ ˆ ˆ ˆ ˆ ˆ

a5 ˆ a6 ˆ a7 ˆ a8 ˆ a5 ˆ a6 ˆ a7 ˆ a8 ˆ a9; a5 ˆ a6 ˆ a7 ˆ

a8 ˆ a12; a9; a10; a11; a9 ˆ a12; a10; a11; a12; a8 ˆ a10; a11; a12;

mbox out = m71y6 # m71y5 # m71y4 # m71y3 # m71y2 # m71y1 # m71y0 # m51y4 # m51y3 # m51y2 # m51y1 # m51y0; //alles samenbrengen en 12 keer roteren: shift12 in = dataregister[63:12] # key xor; shift12 out = (shift12 in ¡¡ 12) ˆ shift12 in[63:52]; //keyscheduling deel: keyregister = start ? key : shift19 out; shift3 out = (keyregister << 3) ˆ keyregister[79:77]; s3x = shift3 out[2:0]; s3y = s3(s3x); counter xor = shift3 out[11:10] ˆ (cnt[2] # cnt[1]); shift19 in = shift3 out[79:12] # counter xor # shift3 out[9:3] # s3y; shift19 out = (shift19 in << 19) ˆ shift19 in[79:61]; subkey = shift19 in[11:0]; //counter deel: 64 klokcycli of rondes: cnt = start ? 00 : (cnt + 1); finish = (cnt == 63) ? 1 : 0; finish out = finish; } } hardwired h efes(efes){encrypt;}

66

Symmetrische versleuteling voor RFID-Tags

Recommend Documents