Jens Hermans

The security and privacy risks of lightweight devices have been a growing concern over the past years. Lightweight devices, such as RFID tags, are being used on a large scale in various applications, even if their presence is rarely noticed. Since these devices are so ubiquitous and communication goes unnoticed they can however easily be abused. Information stored on the devices could be compromised, the device could be faked or it could be tracked, compromising the privacy of the product or user.

To solve the above security and privacy issues, cryptographic algorithms and protocols can be used. However, given the constraints on chip area, time, power and energy conventional cryptographic solutions can usually not be applied. An additional problem is that these devices are out in the open, so they can be easily tampered with, revealing the internals of the device. Lightweight cryptography is put forward as a solution to still obtain sufficiently secure cryptography on these devices.

This thesis focuses on several aspects of lightweight public key cryptography. A first question that is put forward is the security of existing lightweight public key primitives. While the computational power for cryptographic attacks is growing, one tries to shrink cryptography to fit on lightweight devices. As a first contribution, we present fast parallel implementations of NTRU encryption and lattice enumeration on GPU. Our implementation of NTRU shows that an extremely high throughput can be achieved even with public key cryptography. This throughput can also be used for the cryptanalysis of NTRU. Our lattice enumeration implementation demonstrates that GPUs can be used for improving the performance of cryptanalysis.

The remainder of the thesis deals with the security and privacy of lightweight protocols for RFID tags. We present new attacks on the security and privacy of several existing protocols. These protocols came without a formal security or privacy proof and were just some of the many protocols that were broken in the literature.

For the development of our own protocols, we choose an approach using sound protocol design based on provable security. To this end, we analyze several existing RFID privacy models and show poor design choices in several models. Previous proposals also did not allow for strong privacy. We propose a new RFID privacy model that solves these issues and closely models the real world privacy properties a system requires. Finally we propose new, provably secure and private RFID identification protocols and grouping proofs based on public key cryptography. These protocols achieve the strongest security and privacy properties at a minimal cost compared to other proposals with similar properties.

Beknopte samenvatting

De bezorgheid om de veiligheids- en privacyrisico’s van lichtgewicht apparaten is de laatste jaren sterk toegenomen. Lichtgewicht apparaten, zoals RFID tags, worden op grote schaal gebruikt in uiteenlopende toepassingen, ook al merken we hun aanwezigheid zelden op. Aangezien deze apparaten zo alomtegenwoordig zijn en de communicatie ermee onopgemerkt blijft kunnen ze echter eenvoudig misbruikt worden. Informatie opgeslagen op deze apparaten kan gestolen worden, het apparaat kan geïmiteerd worden of het kan getraceerd worden, wat de privacy schendt van het apparaat of de gebruiker ervan.

Cryptografische algoritmes en protocollen kunnen gebruikt worden om de bovenstaande veiligheids- en privacyproblemen op te lossen. Conventionele cryptografische oplossingen kunnen meestal niet gebruikt worden aangezien er beperkingen zijn op de oppervlakte van de chip, rekentijd, vermogen en energie. Een bijkomend probleem is dat deze apparaten vlot toegankelijk zijn, zodat ze gemakkelijk gemanipuleerd kunnen worden om de interne gegevens te extraheren. Lichtgewicht cryptografie wordt daarom voorgesteld als oplossing om toch voldoende veilige cryptografie te realiseren op deze apparaten.

Deze thesis focust op verschillende aspecten van lichtgewicht publieke sleutel cryptografie. Een eerste vraag die naar voren wordt gebracht is de veiligheid van bestaande lichtgewicht publieke sleutel primitieven. Terwijl de rekenkracht voor cryptografische aanvallen toeneemt probeert men de cryptografie in te krimpen om op lichtgewicht apparaten te  passen. In een eerste bijdrage stellen we een snelle parallelle implementie voor van NTRU encryptie en roosterenumeratie op een GPU. Onze implementatie van NTRU toont aan dat een extreem hoge doorvoer mogelijk is, zelfs voor publieke sleutel cryptografie. Deze doorvoer kan ook gebruikt worden voor de cryptanalyse van NTRU. Onze implementatie van roosterenumeratie toont aan dat GPU’s gebruikt kunnen worden om de performantie van cryptanalyse te verbeteren.

De rest van deze thesis is gewijd aan de veiligheid en privacy van lichtgewicht protocollen voor RFID tags. We stellen nieuwe aanvallen voor op de veiligheid en privacy van verscheidene bestaande protocollen. Er was geen formeel bewijs
van de veiligheid en privacy van deze protocollen. Deze protocollen zijn dan ook slechts enkele van de vele die reeds gebroken zijn in de literatuur.

Voor het ontwikkelen van onze eigen protocollen kozen we voor een benadering gebaseerd op bewijsbare veiligheid. Met dit doel in het achterhoofd analyseerden we verscheidene bestaande RFID privacymodellen en ontdekten we slechte ontwerpkeuzes in verscheidene modellen. Eerdere voorstellen lieten ook geen sterke privacy toe. We stellen zelf een nieuw RFID privacymodel voor dat deze problemen oplost en de werkelijke privacyvereisten voor een systeem dicht benadert.

Tot slot stellen we nieuwe, bewijsbaar veilige en private RFID identificatieprotocollen en groeperingsbewijzen voor gebaseerd op publieke sleutel cryptografie. Deze protocollen hebben de sterkste veiligheids- en privacyeigenschappen tegen een minimale kostprijs vergeleken met eerdere voorstellen met gelijkaardige eigenschappen.