Bioinformatics

Tittle: Combining Cryptography with Biometrics for Enhanced Security
Authors: SP.Venkatachalam, P.Muthu Kannan y V.Palanisamy

In the past few years of computer security, biometrics has been used for various types of security problems. The uniqueness of biometrics for any human being makes the identification system more secure. Biometrics is widely used in person identification and verification. The combnation of cryptography with biometrics is a new research area. This technique proves to be more secure than conventional cryptography. This article is about biometric encryption or biometric cryptography approaches and algorithms which use various biometric data.

Conventional cryptography uses encryption keys, which are just bit strings usually 128 bit long. These keys, either “symmetric,” “public,” or “private,” are an essential part of any cryptosystem. A person cannot memorize a long random key, so that the key is generated, after several steps, from a password or a PIN that can be memorized and often made by the user. The password management is the weakest point of any cryptosystem, as the password can be guessed, found with a brute force search, or stolen by an attacker. On the other hand, biometrics provides a person with unique characteristics which are always there. biometric images or templates are variable by nature. An obvious role of biometrics in the conventional cryptosystem is just password management.

The key must be stored in a secure location, this scheme is still prone to the security vulnerabilities, becuase the biometric system and the application are connected via one bit only. Biometric templates stored in a database can be encrypted by conventional cryptographic, this would improve the level of system security, if an attacker gain the access to the encryption keys first. However, there still ome issues because the the database is controlled by a custodian.

User-based cryptographic keys

Cryptographic systems require a secret key or a random number which must be tied to an individual through an identifier. This identifier indeed could be a globally unique user id or biometric data. Generating userID-based key or random number is straightforward and the techniques could easily be found in literature. But generating user-based cryptographic keys includes several of approaches.

User-dependent Key Generation

In cryptography, pseudorandom numbers are generated these numbers can be used directly as a key or adjusted with user-dependent data like an user ID or biometric data. In order to make the key depends on a specific user, two ways could be applied:

• First the key generation algorithm could be modified by using the userdependent data.
• Second the pseudorandom number could be modified. This modification is accomplished using a front-end or back-end approach, in which the pseudorandom numbers are treated as intermediate values and processed further.

Biometric template of user is denoted by T which is a t-bit value. The aim of the authors is to generate an n-bit-long random number or key K, using T.

To generate pseudo random numbers are neccesary, some of them are:

Method 1

This method is based on pairing the biometric data with random numbers. The seed value of the pseudo random number generator consists of a secret random value R and T. In order to eliminate any structure

of a complex function f is applied, so the seed value is defined by seed=f(R, T) where f is the one-to-one mixing function.

Method 2 

In this method R and T are inputs to a more complex function that generates an n-bit pseudorandom number S which could be used directly as a key or as an input to key generation algorithm. The algorithm is as follows:

• Generate a secret pseudorandom number R by using a generator.
• Let Z=H(R,T) || H(R+1,T) || H(R+2,T) || ... || H(R+a,T)
  where a=[n/h]-1. Here H is a strong collision-resistance oneway hash function. H generates an h bit output from any length input. The symbol “||” denotes the concatenation operation. 
• Let S be n specific bits of Z like the leftmost bit.

In practice this method is designed for the user to store the value of R and generate S from R and T on demand. S might be an encryption key; in this case, R might be encrypted and stored within a cryptographic subsystem.

Method 3 

In this method R and T are combined via a simple XOR function to generate an n-bit secret pseudorandom number S. The algorithm is as follows: 

• Let Z=H(R,T) || H(R+1,T) || H(R+2,T) || ... || H(R+a,T)
  where a=[n/h]-1. 
• X = n specific bits of Z. 
• R = n-bit secret pseudorandom number, where R is either specified by the system or generated in his step using a generator.
• S = R (XOR) X.

Method 4

Due to the hash function collision probability the previous three methods do not guarantee that a key or random number derived for a user will be unique. The probability of two users ending up with the same pseudorandom number is still present and will be quite small if n and h are chosen to be large. 

In this method, the user can prove or can't deny that a key is one belonging to his/her designated space of keys or random numbers. It is assume that the value to be generated is n-bit long where (n > t). The algorithm is a two step process:

• Divide the space (2n) into 2t subspaces.
• Choose n-bit value at random from the user’s subspace. The first step of the algorithm is realized by taking the first t bits from the biometric data representation and allow the remaining n - t bits to take any value.

Biometric Encryption Algorithm 

For encription in the biometric part it can be use:

Correlation

This algorithm uses the entire image instead of using a feature based approach. In order to present the biometric input a correlation mechanism is applied. The correlation between the input image and the obtained image during the verification phase is formally defined as, where, FT is the Fourier Transform and F denotes the transformed image. is usually represented by a filter function H(u) and is used as a biometric template. This filter function produces a distinctive correlation peak at the output of the system.

The process of correlation is used as a mechanism for linking and retrieving the digital key. The process of the Biometric Encryption does not extract a simple True/False system it produces a more sophisticated output pattern which is linked during enrolment with a digital key and subsequently regenerated during verification to retrieve the same key. The filter function consistently produces the same output pattern for a legitimate user and tolerant to distortions present in the input image. Storing only the phase of the filter function H(u), satisfies the security requirement for biometric encryption. The magnitude of H(u) is necessary for the discrimination and distortion tolerance properties.

Enrollment

Enrollment phase contains three stages.

• Stage E-1

This stage is responsible for combining a series of input fingerprint images with a random phase array to create two output arrays: Hstored(u) and c0(x).

The objective of this stage is to generate an output pattern to be passed to stage E-2, as well as to generate the stored filter function.

Image Processing at Stage E-1

• Stage E-2

This second stage links a cryptographic key, k0, to the pattern c0(x), via the link algorithm.

This stage is responsible for linking the output pattern with an n-bit key. In this algorithm a lookup table is created and stored for use in key retrieval during verification. Link algorithm first comprises a selection of a portion, then the real and imaginary components of the cropped portion are concatenated to form an enrollment template according to their position in the portion. All these values are stored in a table after they are binarized by a threshold scheme. Then is selected for example  L bits from the template to represent each of the n key bits.

Key link algorithm

• Stage E-3

Finally at this stage the algorithm creates an identification code, id0, derived from the key k0.

The method used for key validation is based on encrypting S bits of data by using the input n-bit key k0, then the encrypted text is hashed by a one-way hash function to create an identification code, which then will be stored.

Overview of the enrollment process

Verification

This session is symmetric to the enrollment session with respect to the linking and retrieving of the digital key. Verification also has three stages:
V-1 - some image processing is applied to combine Hstored(u), from the Bioscrypt, with a new series of input fingerprint images to create an out pattern c1(x).
V-2 - key k1 is retrieved by the retrieval algorithm this key is validated by creating a new identification code, id1 and comparing it with id0. As in enrollment, a set of fingerprints are acquired from the user and Fourier transforms are performed on the images. By using the Hstored(u) retrieved from the Bioscrypt, an output pattern is calculated and passed to the second stage of verification. The key retrieval algorithm takes the output pattern c1(x) and create a binarized verification template.

Overview of the retrieval algorithm

V-3 - The key k1 is released if and only if it precisely matches k0. Although the Biometric Encryption algorithm is first developed for the image type biometric templates it could be easily adapted to the other biometrics as well. Biometric encryption provides convenient and secure widespread use of biometric cryptographic systems.

Using keystroke dynamics for security

In order to generate stronger passwords which can not be easily found, a technique based on keystroke dynamics could be proposed. A stronger password might be generated by using the password’s textual characteristics and the user’s typing patterns. This hardened password then might be used as a cryptographic key.

Keystrokes as a Biometric Cryptographic key 

Legitimate user’s typing patterns consist of durations and latencies between keystrokes. In this scheme these properties are combined to generate a hardened password, but there are several problems in such a system like:

• Identify typing features that the user reliably repeats 
• Use these features when the user types her password to generate the correct hardened password.

If an attacker learns the durations and latencies which are reliably repeated by the user, this will be a catastrophic end. 

This technique improves the hardened password over time by adapting itself to the user’s typing patterns.

Keystroke Patterns for Computer Access Security.

Keystroke patterns are used for authenticating a user. Keystroke rhythms are a method that tries to understand individual’s behaviour. In this method biometric data is assigned to a vector which carries all well-known values of the property. By using a minimum-distance classifier, it will be easy to make a decision by finding the distance between the test pattern and the templates of each individual which are previously determined after a training phase. The main steps are:

• First, parameters of users’ keystroke are collected using a login form and stored in a database. 
• Next, is the validation step where the users’ parameters are processed by an efficient validation algorithm. Also new parameters are generated. 
• Then, is the decision making step, new values calculated during the validation phase are transferred to a decision function. In this step user is accepted or rejected. 
• Finally, the parameters belong to the successful login are updated in the database. 

The system learns user’s keystroke dynamics. Keystroke patterns are low-cost user-specific data especially for biometric authentication and cryptography and it should be noted that they are usually difficult to detect and analyze.

Cryptographic keys generater from voice

Human voice is a good biometric to generate a cryptographic key. The authors focus on focus on a way of generating a key upon its user speaking a chosen password to it.

The keys must be unguessable by attackers and reproducible by intended parties when needed to perform cryptographic operations. For the goal of unguessability, one solution is in which a user utters a password to his/her device and that device would generate a key. Repeated utterance of the same password by the same
user would improve the security of the key after successful matches with his/her previous recorded utterances.

Generating Feature Descriptors from Voice

The algorithm in "Using voice to generate cryptographic keys: A position paper" by F. Monrose, M. K. Reiter, Q. Li and S. Wetzel; represents a user utterance as a sequence of frames, each of which is a 12-dimensional vector of cepstral coefficients characterizing a 30 milliseconds window of the utterance. After the voice is captured, some endpoint detection, silence removal and cepstrum mean subtraction are applied and then speaker and text independent acoustic model is used to segment the sequence of frames into m portions.

The previuos algorithm is as follows:

• For each segment find the centroid in the acoustic model that yields the highest likelihood score for the model. 
• Use the Viterbi algorithm to compute a new segmentation with ‘m’ segments that maximizes the product of segment likelihoods relative to the centroids chosen in the previous step.

Segmentation

Conclusion

In this article are presented a general overview of using biometrics for security purposes and several algorithms that allow users to generate cryptographic keys and random numbers based on their unique biometric information.

Biometrics offer many advantages over current authentication methods, because they are convenient for users and cannot be forgotten or shared between users. They are particularly attractive for use with single sign-on systems, as both the benefits and the costs of the biometric system can be shared across multiple domains. Furthermore, developers of single sign-on systems are realizing that in order to be successful, they must be able to prove that an account belongs to a live person. On the other hand, the need for cryptographic keys and random numbers highly increases by the growing concern over the possible attacks based on the generation of values that lie within a certain undesirable interval or satisfy some other properties that favour the attacker. This article is focused on the trademark encryption algorithm proposed by Mytec Technologies named as Biometric Encryption and Bioscrypt. This method does not propose a two-stage scheme, which first authenticates the user and releases the key. Instead the key is linked with the biometric data during the enrollment phase and later is retrieved at the verification phase. This scheme also uses the image-type patterns and does not present a feature-based representation method because of the prevention of data loss during the extraction. Biometric Encryption could be applied to any biometric image or an array consisting of biometric features.

Using voice instead of keystroke dynamics is another biometric-based cryptography method. This biometric security system uses a similar approach as presented previously in keystroke-based biometric cryptosystem, except for the feature extraction and key generation phases. This algorithm uses cepstral coefficients as voice features and uses Viterbi algorithm to strengthen the key.

Personal Conclusions

Separately the biometrics and cryptography have many vulnerabilities, such keys can be guessed by brute force mechanisms and man in the middle.

Another problem occurs when users choose passwords that are easy or simple when encrypt remain vulnerable.

By combining these two technologies yields a more secure system because even if one of the keys to decrypt would yet another to decipher. Also if you use the encryption using keystrokes or voice encryption this adds more complexity to break the system.

The use of biometrics along with other areas makes you get more robust and complete systems, even if biometrics is still an area that has several faults or is still under investigation.

References

• SP.Venkatachalam, P.Muthu Kannan and V.Palanisamy. Combining Cryptography with Biometrics for Enhanced Security. Control, Automation, Communication and Energy Conservation, 2009. June 2009. http://csis.bits-pilani.ac.in/faculty/murali/netsec-10/seminar/refs/rahul2.pdf

Hamming code

The task for this week was to implement a block code of our choice for a binary channel and simulate a transmission through a noisy channel.

Block codes are error-correcting codes designed to recover from one or more transmission error and allow determining what code word the message corresponds to even in the presence of errors.

For this task I chose Hamming code. This error-correcting code encodes 4 bits of data into 7 bits using a specific matrix, this process add 3 parity bits; Hamming code can only correct errors of 1 bit and if it is an error in 2 bits this code just detect it but it doesn't correct it.

I relied on the Encoding and Decoding with the Hamming Code pdf of the University of Wyoming and with numpy of python was easier.

Hamming Code

This block code uses the following matrix to encode:

The result of the multiplication between the message and this matrix produces a vector of four bits.

Now imagine this message is sent through a noisy channel. To check if the message has errors, first the received message (y) is transposed and multiplied, but now with the decode matrix.

The result of the multiplication between the message and this matrix produces a vector of three bits, if in the vector are just 0's that means that the message has no errors, but if the vector has 1's it tells us that has errors, but it is easy to detect the position of the bit with error because the resultant vector is a binary number and if we transform it we can know in which position is the error.

Test.

The program ask for the total bits in the message (in this case is always 4), the total of repetitions that the program has to simulate the transmissions, the percentage of error (to simulate the noisy channel) and the number of bits that are going to have an error.

Images of the tests:

As you can see I get better results when I test with a single bit error than when it has 2 bits with errors, thats because this block code just detect the errors but doesn't correct them when there are 2 bits with errors.

Code:

References.

University of Wyoming, "Encoding and Decoding with the Hamming Code", 2006, http://www.uwyo.edu/moorhouse/courses/4600/encoding.pdf

Adaptive Coding

For this week's class information theory and coding methods, we were given the task of thinking, implement and evaluate our own adaptive coding method.

An adaptive coding means that the program has no previous knowledge of the distribution of the symbols.

The method that I implement is very simple and dummy, that truth is that I don't understand very well how I have to do this. My method consists in given a file the program read it and takes the first 4 words, pass them to the encoder and for each letter of the words it creates a random code of 8 bits and looks in a table (dictionary) if it is not in this table is added, otherwise another code is created until it is not in the table. This is done until there is no words to encode, then the table and a counter of how many symbols are in the table, are added at the end of the file because it is needed to decompress it.

To decompress the file first reads all the bin file (compressed file) ant takes the last byte that is the counter n. With this counter the program reads the last n lines and makes the table. After this is just look for every byte of the compressed file in the table and get the letter that corresponds it.

This almost works because from the compressed file the program gets the original text, but without spaces, this is a thing that I have to correct.

Code.

Tests

 

As you can see in the images, using a short text in the source file the program doesn't give a compressed file with less kb.

In this one test can be appreciated that using longer file the compressed file is smaller than the original.

Size of the data obtained.

Time taken to decompressed

Huffman coding

Huffman coding is an encoding algorithm used for data compression. The main idea is that from a string we have to count the frequency of use of each letter. For example if we have the string "This is a test" the frequency of the letter would be like this:

letter: s     frequency: 3
letter: t     frequency 3
letter: a     frequency 1
letter: e     frequency 1
letter: h     frequency 1
letter: i      frequency 2
letter:        frequency 3

Then we have to create a binary tree, this could be done by sorting this list by frequency and making the two lowest elements into leaves, creating a parent node with a frequency that is the sum of the two lower element's frequencies. The two elements are removed from the list and the new parent node is inserted into the list by frequency and we have to sort the list again and repeat this process until the there is only one element left in the list, that is the root.

To generate a huffman code we have to traverse the tree to the value you want, outputing a 0 every time we take a left branch, and a 1 every time we take a right branch.

The idea behind Huffman coding is based upon the frequency of a symbol in a sequence. The symbol that is the most frequent in that sequence gets a new code that is very small, in the other hand the symbols that have a small frequency will get a code that is very long.

In my first attempt I was using only list and dictionaries but I get a mess when a I want to get the code of each letter because every time I have 2 nodes with the same value the tree traversal take wrong turns; so I decide to use a structure to create every node. With this structure I know which letter it has, its frequency, its code and the node that is on its left branch and on its right branch.

This implementation was simpler to traverse the tree but at first for me it was confused because I didn't know how to print every node.

This is my implementation in python:

This are some of the tests:

Test text: This is a test

Test text: I would trade all my technology for an afternoon with Socrates.

Test text: I would trade all my technology for an afternoon with Socrates.

Test text:  If you want to live your life in a creative way, as an artist, you have to not look back too much. You have to be willing to take whatever you've done and whoever you were and throw them away.

Fuentes

• Wikipedia
• siggraph.org

Extra Points. Excercise 1.5.1

In this post I will solve the problem 1.5.1 of the book Introduction to Information Theory and Data Compression.

This is the problem:

1. An urn contains five red, seven green, and three yellow balls. Nine are drawn, with replacement. Find the probability that

(a) exactly six of the balls drawn are green;
(b) at least two of the balls drawn are yellow;
(c) at most four of the balls drawn are red.

This is how I solve it:

For the first subsection I used this formula:

In this formula:

• "n" is the number of attempts
• "k" is the number of successes
• "p" is the probability of successes

Substitution and answer:

Now for the second subsection the formula that I used was this:

Where:

• "p" is the probability of successes
• "k" is the number of successes
• "n" is the number of attempts
• "u" is k success

Substitution and answer

And for the last subsection this is the formula:

Where:

• "P" is the probability of the event,
• "C" (n, k) are the combinations of k elements from n elements
• "p" is the probability of success and q = (1-p) the probability of failure
• "n" is the number of times that we repeat the individual case
• "k" is the number of successes

Substitution and answer

Knuth-Morris-Pratt and Boyer-Moore

For this post I made two scripts one for the Knuth-Morris-Pratt and other for Boyer-Moore, both in python.

Knuth-Morris-Pratt.

This algorithm searches in a text T the occurrences of the pattern P, this is made by employing the observation that when a mismatch occurs, the pattern shifts k positions in the text, k is the number of matches (T[i] == P[j]).

For example:

T: a b a c a a b a c c

P: a b a c a b

A mismatch occurs in T[6] and P[6] so k will be equal to 5 and we shift 5 spaces.

T: a b a c a a b a c c
P:              a b a c a b

This is the script:

Boyer-Moore

This algorithm is based on two ideas:

• comparing pattern characters to text from right to left
• Use of two heuristics
• bad-symbol that indicates how much to shift based on the text character that caused a mismatch
• good-suffix that indicates how much to shift based on matched part (suffix) of the pattern

Bad-character

A mismatched character “B” from the text appears only in the beginning of the pattern. Thus we can simply shift the pattern to the right and align both characters B, skipping comparisons.

Good-Suffix

In this case it move the pattern thus the repeated portion must now align with its first occurrence in the pattern.

Again the shift must align the second portion with its first occurrence.

Now it align the left end of the pattern with the rightmost occurrence of “B”.

Here is the script

Since after doing this scripts I was little of time I just take some times

Conclusions

I made more tests I seeing the results I see that the Boyer-Moore algorithm is faster than Knuth-Morris-Pratt.

I have to say that sometimes Boyer-Moore crashes when I use big patterns, that is something I couldn't fix

Sources
iti.fh-flensburg.de
personal.kent.edu
www.iti.fh-flensburg.de
cs.utexas.edu

Word Transmitter

Well this a simple simulator of a word transmitter, it consists of a python script that generates a binary word using a probability of generating a 0, then simulates its transmission through a noisy channel using a probability of transmitting a 0 as a 0 and the probability of transmitting a 1 as a 1. The script gets the success of transmitting a word correctly.

The parameters that the transmitter (python script) needs are:

• Name of the .dat file that will be used
• Number of times that the word will be transmitted                  
• Frequency that a 0 will be added to the new word    
• length = max length of the words                                            
• Probability that a 0 will be transmitted as a 0                     
• Probability that a 1 will be transmitted as a 1

Next I generate a bash file to automate the simulations using different frequencies of generate a 0 and all the parameters that I mentioned above, and with this bash I generate 3 different charts using the different lengths of the words and the average of success of transmitting the word correctly.

This is the python script:

import random,sys,math

class Simulation:

    def __init__(self,frequency,length,nTimes,prob0, prob1, fileName):
        self.freq = frequency
        self.probs = ([prob0, 1-prob0],[1-prob1, prob1])
        
        self.doc = open(fileName,'w')
        
        for i in range(2, (length+1)):
            '''Gets the average of the successes of 
            transmitting a word correctly '''
            self.avrg = (self.simulator(i,nTimes))
            self.doc.write( str(i) + ' ' + str(self.avrg)+ '\n')
            

    def wordGenerator(self, length):
        '''Generate new word using a random number and comparing it
        against the frequency of producing a 0'''
        word = []
        for i in range(length):
            rand = random.uniform(0,1)
            if rand > self.freq:
                word.append(0)
            else:
                word.append(1)
        #print word
        return word
    
    def simulator(self,length, nTimes):
        '''Main function. Makes a new word and simulate its 
        transmission and compare the word against the received word'''
        success = 0
        for i in range(nTimes):
            word = self.wordGenerator(length)
            received = self.transmission(word)
            
            equal = self.comparison(word,received)
            if equal : success +=1
        #print success
        average = float(success)/nTimes
        return average

    def transmission(self,word):
        """Simulates word transmission's using the probabilities
        of transmit a 0 as a 0 and a 1 as a 1"""
        received = []
        for i in word:
            rand = random.uniform(0,1)
            
            if i is 0:
                if rand > 0 and rand < self.probs[0][0]:
                    received.append(0)
                else:
                    received.append(1)
            elif i is 1:
                if rand > 0 and rand <= self.probs[1][1] :
                    received.append(1)
                else:
                    received.append(0)
        #print received
        return received

    def comparison(self,word,received):
        '''Compare the original word against the received word '''
        wrd = ''
        rcv = ''
        for i in range(len(word)):
            wrd += str(word[i])
            rcv += str(received[i])
        #print wrd, "   ", rcv
        if wrd == rcv : return True
        else : return False


def main():
    '''
    fileName = name of the .dat file
    nTimes = number of times that the word will be transmitted 
    frequency = frequency that a 0 will be added to the new word 
    length = max length of the words
    prob0 = probability that a 0 will be transmitted as a 0 
    prob1 = probability that a 1 will be transmitted as a 1'''
    
    fileName = sys.argv[1]
    nTimes = int(sys.argv[2])
    frequency = float(sys.argv[3])
    length = int(sys.argv[4])
    prob0 = float(sys.argv[5])
    prob1 = float(sys.argv[6])
    
    sim = Simulation(frequency, length, nTimes,prob0,prob1, fileName)

if __name__ == "__main__":
    main()

And this is the bash file, here I had to thank my classmate Pedro because he helped me with the part og gnuplot because I had no idea about it.

FILENAME='data'#name of the .dats to be plot
NTIMES=10 #number of times that the word will be transmited
FREQUENCY='0.3 0.6 0.8' #frequencies that a 0 will be added to the new word
LENGTH=30 #max length of the words
PROBZERO=0.7 #probability that a 0 will be transmited as a 0
PROBONE=0.8 #probability that a 1 will be transmited as a 1

for f in $FREQUENCY
do
    for i in 1
    do
 for j in 1
 do
     python simulation.py $FILENAME$f".dat" $NTIMES $f $LENGTH $PROBZERO $PROBONE
     echo python simulation.py $FILENAME$f".dat" $NTIMES $f $LENGTH $PROBZERO $PROBONE
 done
    done
PLOTFILE="graph"$f".plot" #name of the .plot file 
>$PLOTFILE #access to the .plot file
echo set term png >>$PLOTFILE
echo set xlabel \""Length"\" >>$PLOTFILE
echo set ylabel \""Average"\">>$PLOTFILE
echo set output \""chart"$f".png"\">>$PLOTFILE
echo plot \"$FILENAME$f".dat"\" with lines>>$PLOTFILE

gnuplot *.plot
rm *.plot
done

Here some examples that the simulation gives me

bla