Biyometrik verilerin polinom interpolasyonu ile saklanması
Storing biometric data via polynomial interpolation
Yazar: ASLIHAN AKPINAR
Danışman: DOÇ. DR. ERGÜN YARANERİ ; DOÇ. DR. ENVER ÖZDEMİR
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Mühendisliği Ana Bilim Dalı / Matematik Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2019
Konu: Matematik = Mathematics

Özet:
Kimlik doğrulama, bilgilere ulaşmak isteyen kişinin yetkisi olduğunu ispatlamasıdır. Genelde kullanılan kimlik doğrulama, kullanıcı adının ve şifrenin doğru girilmesi ile gerçekleştirilir. Bu yöntem dışında insanların biyometrik özellikleri kullanılarak da doğrulama yapılabilmektedir.   

Biyometrik verilerin kişiye özgü olmasından dolayı, bu verilerin kimlik doğrulamada kullanılması kişinin kendisini ispatlaması için diğer yöntemlere göre daha güvenilirdir. Şifreler veya kimlik doğrulama için kullanılan araçlar unutulabilir, kötü niyetli kişiler tarafından çalınabilir. Biyometrik veri unutulamaz, başka biri tarafından fiziksel olarak çalınamaz. Bu açıdan bakınca biyometrik veri kullanımı daha avantajlı gibi görünsede şifre veya donanıma bir zarar geldiğinde bu verileri değiştirip kimlik doğrulama sağlanabilirken biyometrik verinin zarar görmesi veya kopyalanması durumunda değiştirilebilecek bir veri olmadığından kimlik doğrulama sağlanamaz. 

Biyometrik veriler bilgilere ulaşmak üzere kişinin kendisini ispatlamak için kullanılmasının yanı sıra ulusal kimlik belgesi olarak kullanımı ve suçluların tespit edilmesi gibi alanlarda kullanılmaktadır. Biyometrik verilerin bilimsel olarak kullanılması 19. yüzılın başlarında Alphonse Bertillon, "Bertillonage" adıyla bilinen insan vücudunun boyutlarını fiziksel olarak ölçerek suçluları belirlemek için kullanılan bir tekniği geliştirmesiyle olmuştur. 20. yüzyılın başlarında ise William James Herschel, parmak izlerinin zamanla değişmediği sonucuna vararak parmak izlerini sözleşmelerin reddedilmesini önlemek amacıyla kullanmıştır. Günümüzde ise düzensiz sınır geçişlerini tanımlamak için oluşturulan Avrupa Birliği parmak izi veri tabanı olan ilk çok uluslu biyometrik sistem EURODAC (European Dactyloscopy), Amerika Birleşik Devletleri'ne giren ve çıkan insanların biyometrik verilerinin tutulduğu IDENT (Automated Biometric Identification System), Hindistan'da kullanılan biyometrik veriler ile oluşturulan kimlik numarası olan Aadhaar'ın veri tabanı gibi veri tabanları çok fazla biyometrik veri barındırır. Bunlar gibi veri tabanlarından biyometrik veri çalındığı zaman o biyometrik verinin sahibiymiş gibi birçok işlem yapılabileceğinden ve biyometrik veri inkar edilemeyeceğinden dolayı bu veriler veri tabanlarında yalın halde saklanamaz. Diğer yandan her ölçümde farklı değerler gelebileceğinden şifrelerin saklandığı gibi bir bitin bile değişikliklere yol açtığı özet fonksiyonlar biyometrik verilere direkt olarak uygulanamaz. Bu yüzden biyometrik verilerin saklanması önemli bir meseledir.

Bu çalışmada, iki küme arasında karşılaştırma yaparken orjinal kümeye ait hiçbir veri kaydedilmeyerek biyometrik verilerin saklanması için önerilen algoritma incelenmiştir. Algoritma, orjinal kümenin elemanlarından üretilmiş polinomun özet değeri ve bu polinomu üretmek için $\mathbb{F}_q$'dan rastegele seçilmiş elemanları saklar. Algoritmada polinom oluşturmak için Newton polinom interpolasyonu ve polinomun özet değerini oluşturmak için SHA-1 algoritması kullanılır. Çalışmanın $1$. bölümünde güvenli haberleşmenin özellikleri, kimlik doğrulamada kullanılan yöntemler ve biyometrik verilerin kimlik doğrulamada nasıl kullanıldığı kısaca anlatılmıştır. $2$. ve $3$. bölümde sırasıyla kriptografik özet fonksiyonları ve polinom interpolasyonu açıklanmıştır. Sonrasında algoritmanın işleyişi anlatılmış, algoritmanın güvenlik analizi yapılmış ve SAGE kütüphanesinden faydalanılarak Python programlama dili ile gerçeklenen algoritma kodu paylaşılmıştır.

Abstract:
Since the internet is widely used, it has become important to exchange data securely. Secure communication ensures that the data of the communication cannot be accessed or changed by unauthorized persons during the communication of the parties.  Confidentiality, integrity and authentication are the most important requirements for secure communication. Confidentiality ensures that data remains confidential to unauthorized persons and integrity is used to determine if data has changed since it was created, transmitted, or stored. Confidentiality is provided by symmetric and asymmetric encryption algorithms, while integrity is provided by cryptographic hash functions.

Authentication is a process that the person proves authority in case he or she wants to access data. Authentication is used wherever there is a user account or when communicating between machines. For example, authentication is used when trading on bank sites, logging into an email account, buying airline tickets, logging in to games. The authentication method that is commonly used is performed by entering the user name and password correctly. Apart from this method, biometric data and smartphones,computers,etc. are also used for authentication.

Because biometric data is personal, it is more reliable than other methods to use in authentication for proving one's authority. Passwords or hardware used for authentication can be forgotten or stolen by malicious persons. Biometric data cannot be forgotten and physically stolen by anyone else. From this point of view, the use of biometric data seems to be more advantageous, but when the password or hardware is damaged, the data that is used for authentication can be exchanged, while the biometric data can not be exchanged because it is not unalterable.

As well as biometric data is used to prove the person's identity, it is used in the fields of identification of criminals and used as a national identity document.The scientific use of biometric data was in the early 19th century when Alphonse Bertillon developed a technique used to identify criminals by physically measuring the dimensions of the human body known as "Bertillonage". At the beginning of the 20th century, William James Herschel used fingerprints to prevent rejection of agreements after he discovered that fingerprints did not change over time. Some of the current uses of biometric data are EURODAC(European Dactyloscopy) that is the first multinational biometric system established for the purpose of to identify irregular border crossing jobs, IDENT(Automated Biometric Identification System) that is a system that saves biometric data of people that entering and leaving the United States of America, The Aadhaar that is used as a unique identification document or number that would capture all the details, including demographic and biometric information, of every resident Indian individual. Their databases contain a lot of biometric data.

Biometric data cannot be stored in the databases as plain beacuse when biometric data is stolen from such databases containing biometric data, malicious persons can be act as the owner of that biometric data and biometric data cannot be denied. On the other hand, Its hash value which affected by even change of one bit can not be stored because different values can be obtained in measurements so different hash values are obtained. Therefore, the storage of biometric data is an important issue.

Biometric data is stored via helper data, which must not provide information about the original biometric data. Systems using biometric data are divided into two types according to the way they produce helper data. First type is key-binding schemes which an appropriate algorithm is applied to the biometric data then the result and key are used for generate helper data. To obtain keys, apply an appropriate key retrieval algorithm to the helper data and biometrics at authentication. Second type is key-generation schemes which helper data are only derived from the biometric data and keys are generated from the helper data.

When storing the helper data, irreversibility and unlinkability are described in ISO/IEC FCD 24745 as two properties to be considered. Irreversibility is requires it should not be possible to access the original biometric data from the stored helper data and unlinkability is requires the helper data corresponding to this data should not overlap each other when biometric data is used in various locations. ARM(Attack via record multiplicity),which is the attack resulting from the diversity of records from which the original points of the biometric data were obtained by capturing two or more biometric data used by the user in different locations, is aplicable when unlinkability is not provided. If irreversibility is not provided, the original biometric data is also reached as soon as helper data is accessed.

Most known algorithm in key-binding schemes is the fuzzy vault algorithm presented by Juels and Sudan store the key in biometric data with the help of polynomials. ARM, stolen key inversion and blended substitution attacks to fuzzy vault are presented by Scheirer and Boult.

In this thesis, algorithm that is used for comparing biometric data sets have been investigated. Algorithm checks if there is at least $\%t$ match between two biometric data sets. Also algorithm is designed for the scenerio that attacker knows the $s$ elements of biometric data set. The algorithm stores hash of polynomial degree of $s$ which generated from $s+1$ elements of set and values which randomly chosed from $\mathbb{F}_q$, values which randomly chosed from $\mathbb{F}_q$ for generating polynomial and values of polynomial in remaining elements of set. When generating polynomial, algorithm use Newton polynomial interpolation and use SHA-1 algorithm when generate hash values of polynomials. Algorithm is based on two idea. First idea is for $(x_i,y_i)$ where $i = 0,1,\cdots,n$ are on the unique polynomial which at most degree is $n$ and the second is cryptographic hash algorithms features. When polynomial generated from elements of set and elements of $\mathbb{F}_q$ and applying cryptographic hash function to polynomial, the result is unique. When comparing another biometric data with orjinal biometric data, same procedure, generating polynomial and apply the cryptographic hash function to polynomial, will apply and the result of hash function to polynomial is compared with the stored one. If hash values are same, the algorithm checks if there is at least $\%t$ matching between value of polynomial in remaining elements of set and stored values.

The details of polynomial interpolation, hash function and algorithm have been explained. Then security analysis of the algorithm has been presented. SageMath and Python programming language have been used for written a code of algorithm.