The H has reported that the default WPA key settings for the Speedport W 700V ADSL Wi-Fi routers are weak since at most 4096 guesses are required to recover the key. The key is mostly populated with a collection of fixed fields (for example keys always begin with the prefix "SP-") and other public information such as the MAC address of the router. The devices are apparently supported by all major German Telecoms, and presumably popular amongst the 26 million or so German households that have wireless. Of course the owners of the routers can change the default WPA key, but its a safe bet to assume that most people probably need to be reminded of this precaution. Germany's top criminal court recently made it illegal to offer wireless services that are not protected by a password, which is not a good sign that strong passwords are the norm.
Showing posts with label Entropy. Show all posts
Showing posts with label Entropy. Show all posts
Wednesday, August 25, 2010
Sunday, March 7, 2010
Passwords for USB Keypads
Bruce Schneier recently posted about a new USB stick that comes with its own on-board numeric keypad, permitting a password consisting of digits to be entered directly into the USB device to authorize unlocking. Such a stick and keypad would circumvent the recent USB password vulnerability that was derived from a poor implementation of password verification on the desktop.
The stick in question from Corsair (shown above) also uses AES-256 encryption to protect the data on the stick. The AES-256 key for the stick is then likely to be derived from the user-supplied password (say using PKCS #5 or RFC 2898), or used to protect a file which contains a full-length 256-bit key. In either case the 256-bit key will be derived from, or protected by, a password which has a much lower entropy.
Bruce points out that a 77-digit password would be needed to produce the same entropy as a 256-bit key (since the logarithm to the base 10 of 2^{256} is about 77 ). I made the same point in Are AES 256-bit keys too large? where I calculated that a password based on the 94 printable ASCII characters would need to be 40 characters in length to achieve the same entropy of a 256-bit key (since the logarithm to the base 94 of 2^{256} is about 40). Deriving or bootstrapping AES keys from passwords is really an exercise in self-deception, especially when considering 256-bit keys. The discrepancy between the low entropy of passwords and the astronomical keyspace of AES-256 simply cannot be reconciled.
Perhaps the situation would improve if a biometric such as a fingerprint was used to bootstrap a 256-bit key. I did some research about a year ago and posted what I found in On the Entropy of Fingerprints. Some work has been done by IBM researchers who estimate the entropy of fingerprints to be at most 85 bits, or approximately the same as a length 13 password based on the 94 printable ASCII characters. An improvement, but still a long way from 256 bits of entropy.
Friday, February 12, 2010
Another source of USB Randomness
Back in December I posted about a new USB device with dedicated hardware for producing a continuous stream of high entropy bits based on sampling P-N junctions. Another lower tech randomness source with a USB interface is described at this site, and is shown below
The device is a prototype, and as yet not for sale, but costs about $100 to produce. The advantage of the hourglass method over other more sophisticated and higher yielding devices is simplicity and transparency. Perhaps so, and you can read more about the design here, and the entropy of the output here. Finally
While the hourglass is not precise, accurate, or repeatable as a timekeeper, and has been almost completely supplanted by better devices, it is a good source of random entropy. It is still manufactured in quantity at low cost, and it is clean, compact, durable, and uses little energy. The source of the random entropy can be easily understood, and observed to be functioning correctly without instruments. An off-the-shelf photointerrupter can be employed to electronically observe the random entropy, and an open-source, standardized microcontroller can be used to control the process and interface it with a host computer.
Sunday, December 13, 2009
A USB Entropy Drive
A UK company called Simtec Electronics has created a USB thumb drive device with dedicated hardware for producing a continuous stream of high entropy bits, suitable for mixing into an existing entropy pool on your device or feeding directly into applications and protocols that require sources of randomness. The product is called Entropy Key and and can be ordered from the website for £36.00, with further discounts for bulk orders
An overview of the process for producing the entropy is given in the diagram below. There are two independent noise generators based on P-N junctions that are sampled at a high rate to produce a stream of bytes. The output of each generator and their XOR are subjected to the universal statistical bit test devised by Ueli Maurer. If the sequences pass this test then von Neumann’s debias trick is applied, and then another round of universal testing, followed by hashing with Skein. This process blocks at any stage if the computed statistics fall outside conservative estimates of the properties of random generators.
These steps are repeated until 20,000 bit have been collected, upon which the statistical tests recommended by FIPS 140-2 are applied. The 20,000 bit pool is then parcelled into blocks of 256 bits, and Simtec estimates that each such bock has been generated from about 5,000 bits of noisy hardware samples.
There is quite a reliance on Maurer’s universal statistical bit test, and perhaps justifiably so since this test is specifically designed to detect deviations from expected statistical properties in a bit generator by computing an estimate of the generator’s entropy using ideas from universal data compression algorithms. The test is quite simple, and there is a reasonable description and parameterization given in NIST SP-800 22, which also contains a description of a large number of other statistical tests. A research paper on a finer analysis of Maurer’s test can be found here.
The output rate is, by its nature, variable but an average rate of more than 30 kilobits per second is expected. The complete client daemon source is provided under an MIT license which means everyone is free to examine the code for themselves. SimTec also notes that the Entropy Key can automatically detect various different physical attacks, such as temperature changes (by using a built-in temperature sensor), and opening of the case. The device is currently undergoing testing with "select customers” but is available for general ordering. There is an IRC channel #ekey on the oftc network if you want to discuss any of this further.
(Thanks to Vincent Sanders for providing some more technical details)
Monday, November 16, 2009
Tuesday, April 14, 2009
On the Entropy of Fingerprints
A biometric is just a long password, that is easy to remember and easy to enter (with the right hardware support). But just how long a password? Can we measure and compare the “something you are” against the “something you know” authentication criteria? I went looking on the web and yes there are some answers.
In An Analysis of Minutiae Matching Strength three IBM researchers outline how to measure the entropy of fingerprints and their resistance to brute force attacks as compared to passwords. The authors state that sampled biometrics are much longer than passwords (several hundred bytes to over a megabyte) and typically have a high information content. A password of equivalent length would be difficult to remember.
The authors use two models to arrive at these conclusions. In both models they assume that an extracted fingerprint sample can be represented as an image of 300 x 300 pixels, which can be divided into 400 non-overlapping sites of 20 x 20 pixels. Each site holds a minutia detailing a ridge and valley pattern of a fingerprint, and each minutia point has an angle of orientation represented by d = 4, 8 or 16 values. A sample fingerprint is considered a match against a template if a minimum number of N sites match where N is 10, 12, 14, 16 or 18.
So this is like saying that you have a password of length 400 where each character takes on at least d values and you accept a candidate password as correct if it matches the true password in at least N positions. Letting N = 10 and d = 4 yields just over 2^85 possible fingerprint configurations. So attempting to randomly guess a correct fingerprint template in this model only succeeds with one chance in 2^{-85}. This is very low indeed and corresponds to a random length 13 password based on the 94 printable ASCII characters.
What we have described is called the simple model by the authors, which does not account for certain minutia dependencies. A more complex model is proposed to compensate which also shows that the entropy is still as high as 80 bits with additional matches. Even with the complex model there were quite a few caveats, and a revised model was reported in the excellent 2008 survey paper Biometrics: A Tool for Information Security.
In section V.A of the survey paper the amount of discriminating information in a fingerprint is discussed. The revised model is somewhat more conservative in its comparisons to passwords. The authors now state that randomly matching on at least 20 from 36 minutia is at least as difficult as guessing a length 6 case-sensitive alphanumeric password (about 10^{11} in total).
The revised model was motivated by the desire to quantify the uniqueness of fingerprints due to their importance in determining guilt in court cases. And just like DNA tests, the assumed power of fingerprints to uniquely discriminate between individuals is being downgraded.
So in summary a biometric is just a long password, that is easy to remember and easy to enter (with the right hardware support). But you need to check the parameters of the matching algorithm and its assumptions to determine how strong your fingerprint as compared to a password.
Related Posts
Wednesday, April 8, 2009
NIST, Passwords and Entropy
Passwords still remain the principal security mechanism to protect information assets. To make passwords harder to guess, security policies usually specify baseline requirements concerning password length (say at least 6 characters), composition rules (say all alphanumeric characters with at least one digit) and further content guidelines on avoiding dictionary words and personal references. The intent of such policies is to gain some assurance that users will not select passwords, either willingly or unintentionally, from a potentially small fraction of all possible passwords.
An interesting approach to specifying password policies is taken by NIST in the Electronic Authentication Guide (SP800-63), a document which has been evolving since early 2006. In SP800-63 entropy-based arguments are used to create password policies that provide a bound on the maximum number of password guesses that an attacker can make while still having only a small probability of success. Entropy is a classical measure of information content of an event with an uncertain outcome. In SP800-63 the approach is to specify policies which yield passwords with a minimum amount of entropy, and then to translate this uncertainty measure into a minimum amount of work (that is, guesses) that must be performed by an attacker to recover the password.
An interesting approach to specifying password policies is taken by NIST in the Electronic Authentication Guide (SP800-63), a document which has been evolving since early 2006. In SP800-63 entropy-based arguments are used to create password policies that provide a bound on the maximum number of password guesses that an attacker can make while still having only a small probability of success. Entropy is a classical measure of information content of an event with an uncertain outcome. In SP800-63 the approach is to specify policies which yield passwords with a minimum amount of entropy, and then to translate this uncertainty measure into a minimum amount of work (that is, guesses) that must be performed by an attacker to recover the password.
The SP800-63 approach to Password Policies
The main threat being addressed SP800-63 is online password guessing, assuming that the attacker has online access to the target system or (web) application for the lifetime of the password (typically several months at least). This focus seems to hark back to the 1985 US DoD Password Management Guidelines which considered resistance to online guessing as the fundamental metric of password security.
The SP800-63 approach to selecting passwords can be outlined in the following 5 steps.
- Set a threshold of success for an online attack to 2^{-k}
- Model the textual properties of user selected passwords as English text.
- Use known results on entropy estimates for English to select password policies that yield a minimum amount of entropy in user passwords.
- Derive a bound M on the number of online guesses for an attacker to recover a password generated according the policies in Step 3 and the threshold in Step 1.
- Verify that the attacker will be limited to a number of online guesses m such that m < M.
In Step 1 a threshold is set for the success of online guessing attacks which is acceptable to the system owner. As suggested by SP800-63 this value should be at least k = 10 (about 1 in 1000) and preferably k = 14 (about 1 in 16,000). These probabilities are taken over the number of possible guesses that the attacker can make over the lifetime of the password. If these odds look too high for the attacker then the system designer should use a stronger authentication mechanism.
In Step 2 it is assumed that user-selected passwords have the same characteristics as English text. This is a somewhat conservative (even reasonable some might say) and permits previously known results on the entropy of English to be applied The basic results here are due to the experiments of Claude Shannon, the inventor of information entropy, and many other significant discoveries. Based on these results, password policies are selected to ensure that user passwords will contain a minimum amount of entropy.
In Step 3 the entropy implied in password policies is converted into work (the number M of online guesses) to recover a password according to the bound stated in Step 1. Finally in Step 5 the system is designed to ensure that the number of possible online guesses m over the lifetime of the password is less than M.
To clarify this approach, we recount an example from Appendix 1 of SP800-63. Consider a password policy that mandates passwords of length 8, selected from the 94 printable keyboard characters, required to include at least one lower case, upper case, digit and special character, and is finally scanned to remove dictionary words. SP800-63 asserts that such passwords contain at least 30 bits of entropy, and conclude that if the number of online guesses mounted by an attacker is less than 2^{16}, then the likelihood that the password will be guessed is less 2^{-14}.
In this case passwords will be considered secure against online guessing if the attacker can be limited to less than about 64,000 guesses over the lifetime of the password. The graph below and its associated table in Appendix 1 of SP800-63 show measures of entropy for passwords up to length 30.
Such arguments may end up being influential with security policy makers as exemplified by How Strong is Your Password? NIST has some formulas. For example, the US Railroad Retirement Board includes the following statement in its authentication policies (level 2 corresponds to a threshold of k = 14)
For level 2 protection against on-line guessing, NIST recommends guessing entropy of 30. Guessing entropy is an indication of the amount of work to determine, or guess, a password. Alternately, NIST indicates that any system that required passwords to be changed at least every two years and limited trials by locking an account for 24 hours after six failed attempts would satisfy the targeted guessing attack requirements for level 2.
Converting Entropy into Guessing Work
This seems like magic – pump up the entropy in passwords and you get resistance to online guessing attacks. To understand what is happening here let’s make the following definitions. We will assume that there are N possible passwords defined by a policy
and that a given user U will select these passwords according to the probability distribution
Lastly let’s assume for simplicity that the passwords are ordered such that
which just means that password P1 is the mostly likely choice of the user with probability p1, password P2 is the next most likely choice with probability p2, and so on. The SP800-63 approach is to find the largest value of M such that
and to ensure that an attacker cannot make M online guesses over the lifetime of the password. Here we make the conservative assumption that an attacker is searching the passwords in the same order of likelihood as the user will select them.
The big trick in the SP800-63 analysis is to derive the value of M from the entropy in the passwords rather than finding the password distribution explicitly. Using standard definitions, the password entropy is given as
Now this does not seem to help us much. Say for example that the password entropy is determined to be 30 bits, what can we than say about the number of acceptable password guesses M? Well what SP800-63 does is to assume that a password with 30 bits of entropy represents the same difficulty to guess as a random 30-bit number. What this assumption means is that
and M can be evaluated as
.png)
So when the entropy is 30 bits and k = 14, then if the number of online guesses mounted by an attacker is less than M = 2^{16} = 2^{30 - 14}, the likelihood that the password will be guessed is less than 2^{-14}.
The Flaw of Averages
Unfortunately there is a flaw in this argument. Imagine that you have a random number generator for AES-128 keys, and that you determined that the entropy of the keys produced by the generator was only 80 bits rather than the expected 128 bits. What could you say about the probabilities of the keys being produced by such a generator?
Well it could be the case that there is a subset of 2^{80} keys that are produced uniformly (each with probability 2^{-80} ) and that the remaining keys (the vast majority) are produced with probability zero. Such a distribution would produce an entropy of 80 bits.
So what SP800-63 does in its analysis is to use the same logic but in reverse. If the set of user passwords has an entropy of 30 bits then SP800-63 concludes that there are effectively 2^{30} uniformly distributed passwords, each selected by users with probability of 2^{-30}. Trying to guess the correct password is then like trying to guess a random 30-bit number.
But having a uniform subset of 2^{30} passwords is only one possible distribution that could produce an entropy of 30 bits. It is entirely possible that there could be passwords which have a much higher probability of 2^{-30} of being selected (and others with a much lower probability) while still maintaining an overall entropy of 30 bits. And this would lead a smaller value of M as implied by the analysis above.
The problem here is that the entropy is a single summary statistic (an average in fact) computed over the password distribution, and as such, detail on the distribution itself is lost. The logic of the Sp800-63 analysis is to hypothesize into existence a uniform distribution as the source of the entropy value, when in fact other non-uniform distributions may well have been responsible. And these other non-uniform distributions may provide less security against online guessing than is implied by the hypothesized uniform distribution.
In fact it has been observed before by several authors that entropy is not a good indicator of work, which in our case means the number of guesses to recover a password. To understand this statement further you will need to take the time to read some research. The best papers on the topic are written by John O. Pliam, starting with On the Incomparability of Entropy and Marginal Guesswork in Brute Force Attacks. Eric Verhuel has done some more recent research, presented at RSA 2007.
The Gordian Knot Remains
Setting effective password policies really depends on having good knowledge of how users choose passwords, in particular, the form of the probability distribution for their password selection
In short no one seems to know how to unravel the Gordian Knot surrounding user password habits. SP800-63 attempted to get at these probabilities via entropy arguments, but in the entropy we have already lost too much information concerning the password distribution. Even so, the SP800-63 password policy recommendations are good – just take their online guessing bounds with a potentially large grain of salt. Appendix 1 of SP800-63 makes very interesting reading nonetheless.
Related Articles
Subscribe to:
Posts (Atom)
Posts
