I found this post interesting having just had yet another discussion about entropy in this seed, key, password, etc. world of mine.
The term “Mind Projection Fallacy” was coined by the late great Bayesian Master, E. T. Jaynes, as part of his long and hard-fought battle against the accursèd frequentists. Jaynes was of the opinion that probabilities were in the mind, not in the environment – that probabilities express ignorance, states of partial information; and if I am ignorant of a phenomenon, that is a fact about my state of mind, not a fact about the phenomenon.
Of course, this speaks to entropy. In our seed, key, password, etc. world, entropy is a measure of uncertainty. It is what someone does not know. As such, entropy is subjective. If I know a password, it has no entropy; however, to someone that knows close to absolutely nothing about a password, it has close to maximum entropy.
So, when we talk about the entropy of things like passwords, what we generally mean is the amount of uncertainty, or the lack of information, about that password given some set of assumptions of the information available about that password. And, since entropy is subjective, any measurement of this uncertainty that we produce will likely just be a bound (e.g., an estimate of the maximum possible value) based on particular assumptions.
Ok, lets look at a very simple example with passwords (I banged this out quickly, so hopefully I didn’t make any obvious mistakes)…
Consider the set of passwords exactly 8 digits in length and composed of case-insensitive, repeatable, alphanumeric characters. Given that, each digit of the password can be 1 of 36 characters (i.e., 0-9 or a-z), and, given the passwords are 8 digits in length, there are 36*36*36*36*36*36*36*36 = 368 possible passwords.
Flipping through “The Mathematical Theory of Communication”, Shannon defined entropy, or the measure of uncertainty, for a set of probabilities p1,…,pn, as H = -∑ pi log pi, where pi is the probably of an event i.
Looking at SP800-90, min-entropy, another measure of uncertainty, for a set of probabilities p1,…,pn is defined as H = -log2(pmax), where pmax is the maximum p in p1,…,pn.
Now, lets say you choose a password from this set using a selection method that ensures that the probability of any character being chosen for a digit of the password is 1/36 (i.e., each digit of the password is equally likely to contain any of the 36 possible characters). Once you have chosen and know your password, what is the entropy of that password to you? Well, 0, as you know the password.
In other words, each digit of the password is known to you, meaning the probably of one particular character being in each digit of the password is 1, while the probably of any other characters being in that same digit is 0. So, there is only one pi for each digit of the password, and our Shannon H = -∑ pi log pi = -1 log 1 = 0 and our min-entropy H = -log21 = 0. So, for each digit of our password, H=0. And, treating the digits of our password as independent, the entropy of our password is sum of the individual entropy we calculated for each digit, namely 0+0+0+0+0+0+0+0=0.
Another way of looking at this is that the chance that you will guess your password given you know your password is 1/1=1. Translating that to percent, 1*100 = 100%.
Now, lets say an outside observer comes along who knows nothing about the password you selected above except that it is in this set of possible passwords we have defined. For this attacker, the entropy of the password is quite different, as there is quite a bit uncertainty about your password.
As stated, each digit of the password can be 1 of 36 characters, and this outsider has no information that would bias them towards any particular character being in any particular digit of the password. So, the probably of a particular digit in the password being a particular character is 1/n, where n is the number of potential characters, or 1/36.
Plugging that into H, we get Shannon H = -∑ pi log pi = -((1/36)*log(1/36) + (1/36)*log(1/36) + …repeat 32 more times… + (1/36)*log(1/36) + (1/36)*log(1/36)) = log(36) ≈ 1.5563 (5.1699 bits) or our min-entropy H = -log2(1/36) ≈ 5.1699. So, for each digit of our password, H ≈ 1.5563 (5.1699 bits). And, since this observer knows nothing to imply any dependence between the digits of the password, the digits can be treated as independent and so the total entropy for the password will equal the sum of the entropy of each digit, or roughly 1.5563+1.5563+1.5563+1.5563+1.5563+1.5563+1.5563+1.5563=1.5563*8=≈12.4504 (5.1699+5.1699+5.1699+5.1699+5.1699+5.1699+5.1699+5.1699=5.1699*8=≈41.3594 bits)
Another way of looking at this is that the chance this outside observer will guess our password is 1/(368)=1/2821109907456≈.00000000000035447. Translating that to percent, .00000000000035447*100 = .000000000035447%.
This situation is actually the maximum measure of uncertainty for a password taken from our set of passwords, as it assumes that every character from our character set to be equally likely in every digit of the password and that each digit is independent of the others. (When people ask if their passwords are strong, generally they are asking whether they are near this maximum bound.)
Of course, there is a large range in between the two entropy extremes in this example, and where someone’s uncertainty about a password falls in that range depends on what they know about the password. For example, if they know the password is an English word but not what word exactly, the entropy slides over towards the minimum end. If they know your password is the name of someone very close to you but not what name exactly, then the entropy likely drops to close to zero.
Since I mentioned it above, Appendix A of of SP800-90 (Recommendation for Random Number Generation Using Deterministic Random Bit Generators) discusses the subjectiveness of entropy.
The word “entropy” is used to describe a measure of randomness, i.e., a description of how hard a value is to guess. Entropy is a measure of uncertainty or unpredictability and is dependent on the probabilities associated with the possible results for a given “event” (e.g., a throw of a die or flip of a coin).
Entropy is relative to an adversary and his ability to observe or predict a value. If the adversary has no uncertainty about the value, then the entropy is zero (and so is the security of the consuming application that relies on the DRBG). Any assessment of the entropy of a particular value is actually an assessment of how much of the value is unknown to the adversary.
That document also discusses calculating entropy, recommending min-entropy over Shannon entropy. In the example calculations here, both result in the same entropy estimate, but, in general, min-entropy will produce a more conservative (i.e., less than or equal to) estimate of entropy than Shannon entropy.
***
A new version of mixmaster has been released. [via remops and others]
Mixmaster 3.0 has been released this week. This is the first major version release since 2.9, and a continuation of that code, though it incorporates numerous improvements, feature enhancements, and bug-fixes. It is recommended that you upgrade your remailers to this version.
The next major version of Tor is in the release candidate phase too.
-
For the wannabe gargoyles amongst us… [via tt]
Researchers at the University of Tokyo have developed a smart video goggle system that records everything the wearer looks at, recognizes and assigns names to objects that appear in the video, and creates an easily searchable database of the recorded footage. Designed to function as a high-tech memory aid, these “Cyber Goggles” promise to make the act of losing your keys a thing of the past, according to head researcher professor Tatsuya Harada.
And, yes, I would wear those.
-
Finally, if you build it, they will come.
Abstract—Our study analyzes the security and privacy properties of an implantable cardioverter defibrillator (ICD). Introduced to the U.S. market in 2003, this model of ICD includes pacemaker technology and is designed to communicate wirelessly with a nearby external programmer in the 175 kHz frequency range. After partially reverse-engineering the ICD’s communications protocol with an oscilloscope and a software radio, we implemented several software radio-based attacks that could compromise patient safety and patient privacy. Motivated by our desire to improve patient safety, and mindful of conventional trade-offs between security and power consumption for resource constrained devices, we introduce three new zero-power defenses based on RF power harvesting. Two of these defenses are humancentric, bringing patients into the loop with respect to the security and privacy of their implantable medical devices (IMDs). Our contributions provide a scientific baseline for understanding the potential security and privacy risks of current and future IMDs, and introduce human-perceptible and zero-power mitigation techniques that address those risks. To the best of our knowledge, this paper is the first in our community to use general-purpose software radios to analyze and attack previously unknown radio communications protocols.