Secure Use of Biometrics

February 14, 2012 1 comment

I just spend a good deal of time answering a question over on Security.StackExchange and wanted to repost it here.

Fingerprints can be viewed as a fuzzy source of data. Given the same finger, a reader might never read exactly the same print. That is why most readers require the user to scan a finger multiple times during the registration phase.

During the authentication phase, the system tries to determine if the scan it just acquired is “close enough” to the trained data to allow access. This leads to two problems.

  1. Remote authentication
  2. Keeping biometric private

Remote Authentication

Assume I keep my biometric private (we’ll deal with that problem later). Can I give another party enough information to correctly authenticate me without requiring them to store enough information to impersonate me (i.e., if someone steals the database, I don’t want them to be able to impersonate me)?

It turns out you can. The functions needed are called secure sketches and fuzzy extractors. A secure sketch (SS) is given some data (w) and returns string (s) in other words SS(w)=s. A secure sketch also has a recovery function (Rec). Rec takes as input w’ (a noisy copy of w) and s. If w’ is sufficiently close to w (where closeness is measured by some distance metric such as hamming distance), then Rec(w’,s)=w. Now the server and I share a secret value (namely w) which we can each prove knowledge of to authenticate each other (mutual authentication).

The cool thing about this is that even if someone steals s, they won’t be able to impersonate me. There are a few problems with this, however. What if the attacker modifies the copy of s that the server is storing. Could they do that in such a way that w is leaked? In the original work, there were no guarantees that this couldn’t happen. Later research, however, removed this restriction by developing what is called a robust secure sketch, which is secure even in the presence of an active adversary (i.e., an adversarial controlled channel).

Keeping biometric private

The above ideas all assumed that w (and w’) were kept private. This is probably not a good assumption as seen on MythBusters. So, researchers went back to the drawing board and said “Hey what if my fingerprint was my public key” and thus Fuzzy Identity-Based Encryption (FIBE) was born.

Closely related to this is Identity Based Encryption, where my identity (e.g., email address) is my public key. Someone uses my email address to encrypt a message. I then prove to a third party that I own the email address, whereupon I am able to retrieve the corresponding private key and decrypt the encrypted message. It is important to note that the sender only needs some public information from the third party to enable her to encrypt messages to any identity. The receiver must at some point (either before or after the encrypted message is actually sent) retrieve his private key.

FIBE builds upon this idea for fuzzy identities. You read my fingerprint (w), I use w’ to get my private key and as long as w and w’ are close enough, I am able to retrieve the message you send to me (I still have to contact the third party at some time though). An authentication protocol could be built on this so that I need not keep my biometric private.

The major problem with this system (and IBE in general) is the requirement of a third party and the fact that that third party can impersonate me once they have seen a copy of my biometric. The latter problem can be removed by having multiple third parties who all contribute to the process. Thus, no single one can impersonate me. But, then I have to contact multiple people in order to encrypt or decrypt messages.


I’m not sure if any commercial products implement these ideas. So, I cannot speak to commercially available products, but if you are not limited to commercially available products, you could implement these systems yourself and they would probably be pretty secure.

Categories: Cryptography

Cost of Brute-force

November 9, 2011 Leave a comment

Over at someone asked a question about the cost in dollars of brute-forcing a 256 bit key. In my answer, I estimated it to be about 8 octodecillion dollar ($8 * 10^57). And that is for the electricity only! Some of the answers were pretty interesting and I learned a few things. For example, I never knew exactly how a quantum computer would affect symmetric-key cryptography. It turns out that it would halve the key space, which is optimal (i.e., you cannot do better). If one could do better with a quantum computer, then that would prove that the key could be brute forced in less than 2^n time. I won’t pretend to understand exactly why that is, but it is a pretty interesting result that I had wondered about for some time.

Categories: Cryptography Tags: , ,

PHP crypt() bug

August 22, 2011 Leave a comment

A serious (and kind of funny) bug was reported in PHP crypt() today. Under certain circumstances, crypt() with an MD5 salt would only return the salt (no hash of the password). The bug was introduced on 7 Aug by rasmus.

Take a look at the diff:

That’s right, only one line was changed. Can you spot the problem (vulnerable code on the left)?

Take a look at the man page for strlcat, specifically, what is the third parameter? “Unlike those functions [strncpy and strncat], strlcpy() and strlcat() take the full size of the buffer (not just the length) and guarantee to NUL-terminate the result (as long as size is larger than 0 or, in the case of strlcat(), as long as there is at least one byte free in dst).” So, line 380 in the incorrect code is saying that passwd is only one byte in length.This messes everything up which leads to:

If crypt() is executed with MD5 salts, the return value conists of the salt only.
DES and BLOWFISH salts work as expected.

I tested with php from openSUSE PHP5 repository

> php -v
PHP 5.3.7RC6-dev (cli)
> rpm -q php5

Test script:
printf("MD5: %s\n", crypt('password', '$1$U7AjYB.O$'));

Expected result:
MD5: $1$U7AjYB.O$L1N7ux7twaMIMw0En8UUR1

Actual result:
MD5: $1$U7AjYB.O


So, what is the takeaway? If you look at the commit logs in svn, the bug actually started before the commit shown in the diff above. The author of that change changed a strcat to a strncat in order to “Make static analyzers happy”. The very next commit changed the strncat to strlcat with the comment “…let’s use strlcpy/strlcat instead for these static string copies”. NOTE: same author for both of those commits. So, it was a combination of trying to make a static analyzer happy and not understanding the difference between two function calls. The real kicker though is the most recent commit that fixes the bugs. It has the following commit message “If you want to remove static analyzer messages, be my guest, but please run unit tests after”. It turns out that the PHP unit tests would have found this bug, but someone didn’t run them before committing a fix to the repository. An interesting lesson in software development.

Intro to GNURadio and the USRP (part 5, simple transceiver)

April 26, 2011 7 comments

This is going to be a short and sweet lesson. You want to communicate data across two USRPs. You’ll need a transceiver. Below (and in the source repository) you’ll find the GnuRadio-Companion blocks.

This is a pretty basic setup. You have two UHD blocks (a source and sink), a number of parameters to control things from the command line, modulator and demodulator, etc. One thing that is different is that this graph is not complete. The message source and sink are each missing something. The nice thing is, GnuRadio-Companion will still compile this to a python file. Then you can do as we learned in part 4, and modify the python code to interact with those message queues. There are, however, a few other changes you will need to make in the source. The creation of the message sink is not complete, as the constructor expects a message queue. You can easily create one (self.sink_queue = gr.msg_queue()).

There is something else about this block diagram. What are the two probes (probe avg mag^2 and probe signal)? Probes are used to allow the program to access certain information. For example. lets say you want to implement a MAC protocol (say CSMA/CA). You could use the probe signal (which is giving you access to complex to mag^2) to see the instantaneous received signal strength. This could be a good way to do the carrier sensing (something like db_val = 10 * math.log10(self.raw_mag_sqrd_probe.level())). If db_val is below threshold, then the channel is clear. Using the probe avg mag^2, you could get an estimate of the last received packet (since it is an average over the last few received samples). This would work well for an RSSI value which could be stuffed into a packet header and passed up the networking stack.

There are many possibilities. Given the state of the current block diagram, I’d start by writing a send_pkt and recv_pkt function for the simple_transceiver class which puts a message in the source queue or removes a message from the sink queue respectively (note, in the code above all messages must be 512 bytes in length).


Categories: GNURadio and USRP

Intro to GNURadio and the USRP (Part 4, message blocks)

April 19, 2011 9 comments

This week I started playing with the message source and sink blocks within GNURadio and found them quite useful. Especially for accessing (sending and receiving) data outside of the actual GNURadio code. Below is the code, but let me explain what is going on (you can get the code from the source repository, see part 0). I create a top block which has a message_source and a message_sink (and a queue for each). Then I created two functions in the top block, one for sending a packet, and the other for receiving. The code should be fairly simple.

Then in the main portion of the code, I show how this is used. You can interact directly with the queues or by using the two functions.

from gnuradio import gr
from time import sleep

class msg_blocks(gr.top_block):

    def __init__(self):
        gr.top_block.__init__(self, 'Message Blocks Test')

        # initialize the queues
        self.sink_queue = gr.msg_queue()
        self.source_queue = gr.msg_queue()

        # initialize the blocks
        self.msg_source = gr.message_source(gr.sizeof_char, self.source_queue)
        self.msg_sink = gr.message_sink(gr.sizeof_char, self.sink_queue, False)

        self.connect((self.msg_source, 0), (self.msg_sink, 0))

    def send_pkt(self, payload):

    def recv_pkt(self):
        pkt = ""

        if self.sink_queue.count():
            pkt = self.sink_queue.delete_head().to_string()

        return pkt            

if __name__=="__main__":
    tb = msg_blocks()

    # operate on queues directly
    print 'operating on the queues directly'
    print 'sink queue count:', tb.sink_queue.count()

    print 'inserting:', 'a'

    sleep(1) # sleep to yield to tb thread

    print 'sink queue count:', tb.sink_queue.count()

    print 'received:', tb.sink_queue.delete_head().to_string()

    # operate using methods
    print 'operating with fuctions supplied by the top block'
    print 'sending:', 'a'*512

    print 'received:', tb.recv_pkt()
Categories: GNURadio and USRP

Intro to GNURadio and the USRP (Part 3, UHD)

April 14, 2011 1 comment

UHD is the way of the future. Read about it here. Unfortunately, UHD is not in the Ubuntu packages. Furthermore, the gnuradio in Ubuntu packages does not support UHD. That said, there is a way to get it working. This script will install UHD and GNURadio from source. In my next post, I’ll be doing an example which uses UHD, so install it!

Categories: GNURadio and USRP

Intro to GNURadio and the USRP (Part 2, Visualizing the Waves)

January 29, 2011 3 comments

Ever wonder what data looks like as it propagates through space as a waveform? In this second part of my introduction to GNURadio and the USRP, we will find out. For this part, we will again build a simulated setup in gnuradio-companion. The basic setup will be as follows: source -> modulator -> amplifier -> channel model -> throttle -> sink. In the picture below you can see our setup. The actual setup is fairly complicated, but instructions to download the source can be found in part 0.

In this example I am using a random source to generate random blocks of size 512. The OFDM modulator automatically packetizes the data. The Multiply Const block will act as an amplifier, which will be controlled from the mult_const variable. The channel model is the same as in part 1, but I’ve added a noise_voltage slider to control the noise. The throttle block was added to slow things down. Last, the FFT sink is a graphical sink that plots the FFT of the signal. The FFT converts from the time domain to the frequency domain. If you want to see what things look like in the time domain, use the Scope  graphical sink.

Running It and Experimentation

To run the code in gnuradio-companion, just generate the python code (F5) and execute it (F6). You should get something that looks like this:

This is what the random source looks like in the frequency domain. You can see the noise floor is about -30 dB and the bandwidth is about 7kHz. Using the GUI you can play with 2 variables. The noise voltage and the multiplication constant. Increasing the noise voltage should cause something like this:

As you can see, the noise floor goes up, but the level of the actual signal stays the same. This could make it hard for a decoder to be able to extract the data, we’d need to amplify the signal. That would look like this:

A signal like this should be much easier to decode.

Another interesting thing to play with is the “Occupied Tones” of the OFDM modulator. In the figure below, I’ve changed the tones from 200 to 50. You’ll need to stop the code, make the change, regenerate the python code, and run it (F7, F5, F6 are the hotkeys). What happened?

What now?

There is a lot to understand and play with here. Here are some things to look at.

  • Using the default parameters, what happens to the noise floor if you change the multiplier from 1 to 10? Why does this happen? (Checking Peak Hold can help you see exactly what is happening)
  • Try a few different modulators (change the Modulation Technique in the OFDM modulator, replace OFDM with something different and add a packet encoder if necessary). Does the view of signal change with different modulators?
Categories: GNURadio and USRP Tags: , ,