Security analysis of RFID authentication protocols based on symmetric cryptography and implementation of a forward private scheme

Abstract

This M.Sc. thesis is mainly two folds: First part includes the the theoretical securityanalysis of privacy-friendly radio frequency identification (RFID) protocols that arebased on symmetric cryptography and sub-linear complexity. Second part is a practicalpart dedicated to an implementation of forward secure RFID authentication protocol.RFID technology provides wireless communication with an object or someone toidentify or authenticate by using radio waves with neither physical nor visual contact.RFID is one of the most promising technologies deployed in many applications such ascontactless payment systems, public transportation, electronic passports, access cards,logistic tracking systems etc. In fact RFID has entered in our lives, however, securityand privacy concerns have become controversial as a social demand. Moreover, thecost of RFID tags is an other obstacle to technological advance. Many works havebeen dedicated to this specific area to mitigate these issues. The large body of literatureRFID Security and Privacy demonstrates that designing a privacy friendly and efficientprotocol is still a challenging task and finding the appropriate one is quite awful forindustrials. Indeed, although many protocols have been proposed over the years, nonecan be deemed as ideal. Motivated by this need, in this work we examine most of theproposals in the field, categorize them according to common features analyze them,compare their properties and discuss about which can be considered as the best onesto date. We also provide new attacks on several of these protocols and some patches.First, this work includes a comprehensive analysis of privacy-friendly authenticationprotocols devoted to RFID that: (i) are based on well-established symmetric-keycryptographic building blocks; (ii) require a reader complexity lower than O(N)where N is the number of provers in the system. These two properties are sine quanon conditions for deploying privacy-friendly authentication protocols in large-scaleapplications, e.g., access control in mass transportation. We describe existing protocolsfulfilling these requirements and point out their drawbacks and weaknesses. Weespecially introduce new attacks and raise that some protocols are not resistant totiming attacks. We also suggest a number of new solutions to ameliorate some ofthe existing protocols and provide guidelines for those schemes. We have extensivelyevaluated and compared all the candidates according to their security, and performance.The security properties that we investigated include user privacy and as well as forwardprivacy, impersonation resiliency and desynchronization resistance. Furthermore, weexamined thoroughly their performance, in terms of computational and storage cost.According to our analysis by means of security and efficiency, we selected the mostappropriate candidates for practical uses.Second, this thesis includes an implementation of a real RFID system which is efficientand secure with respect to the first part of this work. We implemented one of the bestcandidate that is, according to our analysis and criteria, the most appropriate one forpractical uses. To the best of our knowledge, this is the first complete implementationof a forward-private RFID system based on time-memory trade-off. This methodis already introduced but never tried to implemented in a real RFID system. Weshow that our implementation practically allows achieving a high performance bymeans of search complexity and memory usage without degrading privacy. We haverun several experiments on the implemented real RFID system and we observedthat the experimental outputs are very close to the theoretical bounds. Finally, theauthentication speed and effective memory usage put forth that this forward-privateRFID system is ready to be used for practical proposes.

Bu Yüksek Lisans tezi genel olarak iki kısımdan oluşmaktadır: Birinci kısımda"simetrik anahtarlı kriptografik sistem" tabanlı RFID (radyo frekansı tanımlama)protokollerinin teorik güvenlik ve mahremiyet analizi ele alınmıştır. İkinci kısımdaise ileri mahremiyet sağlayan bir RFID kimlik doğrulama protokolünün "zaman belleködünleşim" metodu kullanılarak gerçeklenmesi yapılmış ve sonuçları teorik sonuçlarile karşılaştırılmıştır. Aşağıda öncelikle RFID teknolojisi hakkında kısa bilgilerverilerek bu konudaki güvenlik ve mahremiyet gereksinimlerine değinilmiş daha sonrabu tezdeki yapılan çalışmalar özetlenmiştir.RFID teknolojisi, fiziksel temasa gerek olmaksızın radyo dalgalarıyla etiket taşıyanbir nesne ya da kişinin kimliğinin belirlenmesini veya doğrulanmasını sağlar. RFIDsistemi temel olarak etiket (tag), okuyucu (reader) ve etiket hakkında bilgileri güvenlibir şekilde depolayan veri tabanı sunucusundan (back-end server) oluşmaktadır. RFIDetiketi, okuyucudan gelen sorguları almaya ve cevaplamaya olanak tanıyan bir silikonyonga, anten ve kaplamadan meydana gelir. Yonga, etiketin üzerinde bulunduğunesne ile ilgili bilgileri saklar. Anten, radyo frekansı kullanarak kimlik bilgileriniokuyucuya iletir. Kaplama ise etiketin bir nesne üzerine yerleştirilebilmesi içinyonga ve anteni çevreler. Hafıza, okuma mesafesi, okuma/yazma kapasitesine görefarklılıklar göstermektedir. Etiketler okuma sırasında kullanılan frekans aralığına bağlıolarak da LF, HF, UHF ve mikrodalga frekans olmak üzere çeşitlendirilebilirler.RFID ilk defa ikinci dünya savaşında dost savaş uçaklarını düşman savaş uçaklarındanayırmak için geliştirilmiş ve kullanılmış bir teknolojidir. Günümüzde ise çok genişbir kullanım alanı vardır. RFID teknolojisi temassız ödeme, toplu taşıma, elektronikpasaport, giriş kontrol sistemleri, lojistik takip sistemleri, kütüphaneler, taşıt otomatikgeçiş sistemleri, otomatik tanıma ve bilgi toplama sistemleri gibi birçok alanda yaygınolarak uygulanmış ve ileride de daha birçok alanda gelecek vaat eden bir teknolojidir.Hayatımızın hemen hemen her alanına giren bu yeni teknoloji güvenlik ve kullanıcımahremiyeti gibi toplumsal endişeleri de beraberinde getirmiştir. Bu teknoloji güngeçtikçe önem kazanıp üzerinde yapılan çalışmaların da arttırılmasına rağmen gizlilikve güvenlik ile ilgili sorunları tam olarak çözülememiştir. İnsan mahremiyetininihlal edilmesi konusunda oluşan çekincelerle Eylül 2003'de bazı insan hakları vesivil toplum organizasyonları RFID teknolojisi kullanan marketleri dava etmiştir. Busistemin kötü yollar için kullanılabileceği öne sürülmüştür. RFID teknolojisinin birparçası olan RFID etiketlerin her biri yalnızca kendine özgü ve ait olduğu kişiyeyönelik bilgiler taşımaktadır. Bu durumda bu etiketleri taşıyan kişiler de adetabu aygıtlarla birlikte etiketlenmiş olmaktadırlar. Ayrıca, yaygın olarak kullanılanRFID etiketleri sorgulandıklarından haberi olmayan ve her türlü sorguya yanıt verenyapıdadırlar. Bunun sonucu olarak RFID etiketlerini taşıyan kişilerin habersiz olarakizlenmesi, özel hayatları hakkında istemedikleri bilgilerin ortaya dökülmesi durumuortaya çıkmaktadır.RFID teknolojisinin insanların özel yaşamlarının gizliliğine karşı oluşturduğu tehditlerönemli bir sorun olmakla beraber asıl büyük tehdit ve problem bu sistemlerinkontrolünün, protokoldeki güvenlik açıklarından ve teknik savunma zafiyetlerindenistifade edilerek istenmeyen kişiler tarafından elde edilmesi sonucu ortaya çıkmaktadır.Çünkü yukarıda bahsedilen kullanım alanlarında da görüldüğü gibi RFID sistemleriartık insan hayatının önemli bir parçasını oluşturmakta ve insanlar kendileri için çokbüyük önem taşıyan faaliyetlerini (ödemeler, sahip oldukları mülklerin korunması,kimlik denetim sistemleri ile kendilerini tanıtmaları vb.) bu sistemler üzerindengerçekleştirmektedirler.Tüm bu süreç esnasında ise RFID sistemlerinin güvenli olduğunu varsayarak hareketetmektedirler. Bir RFID sisteminin güvenliği sistemi oluşturan bileşenlerin (etiket,okuyucu ve veri tabanı) parçanın da güvenli olması ile doğrudan ilgilidir. RFIDetiketlerinin, özellikle de daha yaygın kullanılan pasif RFID etiketlerinin devre alanıve enerji tüketimi gibi kaynaklarının kısıtlı olduğu göz önünde bulundurulduğunda, bucihazlarda mevcut kriptografik algoritmaları kullanarak güvenlik sağlamanın zorluğuortadadır. RFID etiketlerinin düşük enerji tüketimi ile etkin çalışmasını sağlamak buçalışmanın ortaya konulmasının başlıca hedeflerindendir.Bu ihtiyaçlardan dolayı son zamanlarda akademik ve endüstriyel çalışmalar bu özelalanda ortaya konulmuştur. Literatürdeki RFID güvenlik ve gizlilik çalışmalarınınbüyük çoğunluğu, hem kullanıcı mahremiyetini sağlayacak hem de verimli olacakbir protokol dizaynının oldukça zor olduğu konusunda ortak fikirdedirler. Bu kadargeniş ve hızlı değişen literatürde uygun protokolün seçilmesi işi sanayiciler için de birproblemdir. Gerçekten de yıllar boyunca önerilen birçok protokol olmasına rağmen,hiçbiri ideal olarak kabul edilmemiştir. Bu çalışmada bahsedilen ihtiyaçlardan yolaçıkarak, bu alanda önerilen protokoller güvenlik ve verimlilik ortak özelliklerine görekategorize edilmiş ve kendi aralarında karşılaştırılmıştır.Bu çalışma ilk olarak mahremiyet özelliğini sağlayan protokollerin kapsamlı analiziniiçerir. Bu çalışmada ele alınan RFID kimlik doğrulama protokolleri şu iki özelliğitaşımaktadır: (i) Simetrik kriptografi yapı taşları ile oluşturulmuş olması, (ii) Nsistemdeki etiket sayısı olmak üzere O(N)'den daha düşük karmaşıklık ile kimlikdoğrulama işlemlerini yapabilmesi. Büyük ölçekli gerçek hayattaki uygulamalar(örn. toplu taşıma vb.) göz önüne alındığında bu iki koşul RFID sisteminintaşıması gereken olmazsa olmaz özelliklerindendir. Bu çalışmada bu özelliklerisağlayan protokoller ele alınmış ve bunların kapsamlı olarak teorik güvenlik analizleryapılmış, eksiklikleri ve zayıf noktaları ortaya konulmuştur. Bu protokoller üzerineyeni kriptografik ataklar yapılmış, özellikle zamanlama ataklarının birçok protokolüzerinde nasıl gerçekleştirilebileceği bu çalışma ile ortaya konulmuştur. Ayrıca bazımevcut protokolleri iyileştirmek için çözüm önerileri sunulmuş ve bu protokolleriçin bazı kılavuz bilgiler verilmiştir. Tüm aday protokolleri güvenlik ve performanskriterleri değerlendirilerek karşılaştırılmıştır. Protokollerin güvenlik olarak; kullanıcımahremiyeti, taklit edilmeye karşı dayanıklılık, desenkronize edilip takip edilmeyekarşı dayanıklılık ve iz sürülme tehlikesine karşı güvenirlik özellikleri ele alınmıştır. Performans olarak, etiket ve veri tabanı üzerinde az işlem yapma ve düşük yer kaplamakriterleri göz önüne alınmıştır. Böylece ortaya konular çalışmalar sonucunda pratikdünyada kullanılabilecek en uygun adaylar seçilmiştir.Bu çalışmada ikinci olarak, güvenliği ve performansı birinci bölümde değerlendirilenen uygun protokolün gerçek bir RFID sistemi üzerinde gerçeklenmesi yapılmıştır.Bildiğimiz kadarıyla zaman-hafıza ödünleşim metoduna dayalı ve ileri mahremiyetözelliği taşıyan ilk RFID sisteminin gerçeklenmesi bu çalışma ile ortaya konulmuştur.Daha önce teorik olarak tasarlanan bu sistemin şimdiye kadar gerçeklenmesiyapılmamıştı. Bu gerçeklemenin mahremiyet özellikler korunarak yüksek veritabanı arama hızı ve düşük bellek kullanılarak yüksek performans sağladığı yapılandeneyler ile ortaya konulmuştur. Ayrıca deney sonuçlarının teorik sınırlara yakınolması bu çalışmanın doğruluğunu ve olumlu etkisini göstermektedir. Sonuç olarakbu çalışmanın pratik olarak da kullanılabilecek hazır bir sistem olduğu ortayakonulmuştur.