D-kriptik Blog

Well, a cool, successfully employed in the real world attack leveraging weaknesses in MD5 (and CAs) has been making the rounds. [via just about everyone]

Our attack takes advantage of a weakness in the MD5 cryptographic hash function that allows the construction of different messages with the same MD5 hash. This is known as an MD5 “collision”. Previous work on MD5 collisions between 2004 and 2007 showed that the use of this hash function in digital signatures can lead to theoretical attack scenarios. Our current work proves that at least one attack scenario can be exploited in practice, thus exposing the security infrastructure of the web to realistic threats.

As a result of this successfull attack, we are currently in possession of a rogue Certification Authority certificate. This certificate will be accepted as valid and trusted by all common browsers, because it appears to be signed by one of the root CAs that browsers trust by default. In turn, any website certificate signed by our rogue CA will be trusted as well. If an unsuspecting user is a victim of a man-in-the-middle attack using such a certificate, they will be assured that the connection is secure through all common security indicators: a “https://” url in the address bar, a closed padlock and messages such as “This certificate is OK” if they chose to inspect the certificate.

The team built a list of CAs that issued certificates using MD5, and, of these CAs, picked one in particular that used predictable values for fields in the certificate that were not fully under their control (the latter reminded me a bit of the DNS implementation flaw a few months back). To generate the collision, the team appears to have pushed the state of the art for chosen prefix collision attacks for MD5, although details will be published later.

The chosen-prefix collision construction method is basically described in our EuroCrypt 2007 paper [SLW]. However, some crucial improvements to this method have been developed that made the present application possible. Details of those improvements will be published in a forthcoming academic paper. The basic idea of the method is twofold. In the second part of the method differential paths are constructed that are capable of eliminating special bit differences in the IHVs with certain probabilities. This can be called a search for near collisions. In a few consecutive “near collision blocks” thus special combinations of bit differences can be eliminated. For each bit difference a fresh differential path has to be constructed, so it is crucial to have an automated way to produce differential paths.

As a result, the few remaining CAs using MD5 seem to be kicking the habit now.

Q: Does that mean VeriSign has discontinued use of MD5?
A: We have been in the process of phasing out the MD5 hashing algorithm for a long time now. MD5 is not in use in most VeriSign certificates for most applications, and until this morning our roadmap had us discontinuing the last use of MD5 in our customers’ certificates before the end of January, 2009. Today’s presentation showed how to combine MD5 collision attacks with some other clever bits of hacking to create a false certificate. We have discontinued using MD5 when we issue RapidSSL certificates, and we’ve confirmed that all other SSL Certificates we sell are not vulnerable to this attack. We’ll continue on our path to discontinue MD5 in all end entity certificates by the end of January, 2009.

Anyway, I noted the following paragraph in this summary of the attack,

The growth of trusted root CAs included in standard browsers has been an issue for a while. Every root CA is equal in the eyes of the browser, thus the end-user’s security is equivalent to the security of the weakest root CA. The default Firefox install will accept a Yahoo cert signed by “TurkTrust”, or any other of more than 100 root certs. I don’t know how good each of those companies are at securing their keys, implementing strict cert chain validation, and checking the identity of every submitter. So, it’s a good bet that putting crypto authority in the hands of that many people will result in some failures, repeatedly.

It served as a reminder that this is today’s world, [via Cryptography mailing list]

Code signed malicious code results from either malicious code being mistakenly signed, stolen private keys issued to other entities or been issued certificates from a Certification Authority (CA). The MMPC has not confirmed any cases of private keys being stolen and used on detected code, or any cases of mistaken signing by a legitimate entity, but has confirmed many cases of CAs issuing code signing certificates to malware authors. In most cases, CAs participating in the Microsoft Root Certificate Program issue code signing certificates to a software publisher who uses the certificate to sign malware. In some cases, the CA is owned and operated by the malware authors, and the first step in infection is tricking users into installing a root certificate. In most cases, CAs participating in the Microsoft Root certificate program are tricked into issuing a valid certificate to the malware author.

In the first six months of 2008, the MMPC received reports of 22M instances of distinct malware files, of which about 173,000 were distinct malware files with code signatures. Of this malware with code signatures, about 38,000 were not validly code signed, so approximately 135,000 validly signed malware files were reported to Microsoft. Approximately 0.6% of detected malware were validly code signed.

-
Unrelated, a new version of the CAVS tool has been released.

[12-24-2008] — New release of the CAVS algorithm validation testing tool to the CMT Laboratories (CAVS7.0). Version 7.0 of the CAVS tool adds testing for NIST SP 800-56A Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography and NIST SP 800-38D Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC.

In addition, file formating changes have been made to the CCM Decrypt-Verification Process Test.

The transition period ends March 24, 2009.
[...]
Prior to the release of CAVS7.0, the CMVP allowed vendor affirmation for SP800-56A implementations(IG1.12) and vendor affirmation for SP800-38D implementations (IG.1.13). During the transition period, the vendor has the option of either providing the vendor affirmation in FIPS140-2 IG1.12 or IG1.13 or going through the validation testing now available in CAVS7.0. The transition period for accepting vendor affirmation for SP800-56A is being determined but will exceed the 3 months specified above. Please see the CMVP Announcements for further information.

-

Have a happy new year!

So, the FIPS 186-3 is getting closer to finalization, and a new draft has been published for public comment.

As stated in today’s (Nov. 12, 2008) Federal Register Notice, NIST requests final comments on FIPS 186-3, the proposed revision of FIPS 186-2, the Digital Signature Standard. The draft defines methods for digital signature generation that can be used for the protection of messages, and for the verification and validation of those digital signatures using DSA, RSA and ECDSA. [...] The comment period closes on Friday, December 12, 2008.

Along with a draft of SP 800-102 being announced for public comment.

NIST requests comments on SP 800-102, Recommendation for Digital Signature Timeliness. This Recommendation provides methods for obtaining assurance about the time that a message was signed. The concepts in this Recommendation were presented in the original public comment draft of FIPS 186,3, The Digital Signature Standard. Please provide comments [...] by December 19, 2008 [...]

A summary of the changes between this draft and the earlier ones, as well as a brief summary of the changes between FIPS 186-2 between 186-3, can be found in the Federal Register notice. In the notice, the changes between drafts are covered in a comments received and NIST response format. For those that will be specifically dealing with this future standard, I found the most interesting NIST responses to be…

A.1.1.3 is intentionally different from A.1.1.1. The change in the use of the hash function (no XORing) was in response to a cryptanalytic attack that showed how to select a set of domain parameters generated in the A.1.1.1 fashion in such a way that two ‘‘messages’’ with the same DSA signature could be found. Note that A.1.1.1 still allows domain parameters generated using the older method to be verified.

The length of the larger keys has a huge impact on communications and storage requirements. The strategy of the U.S. government is to transition to elliptic curve algorithms in order to reduce the key sizes.

NIST has chosen to base the number of tests on the key sizes and provided separate requirements for each. An implementer can choose to combine the requirements into fewer categories, as long as the number of rounds for each key size are equal to or greater than the numbers provided in the FIPS.

The only other NIST document containing approved methods for random number generation is FIPS 186–2. With the approval of FIPS 186–3, those methods will no longer be approved, subject to a transition period posted by the Cryptographic Module Validation Program (CMVP).

My comments on the draft proposed back in 2006 plus feedback from readers can be found here. I was happy to see the focus refined to be solely on the digital signature algorithms, and other information migrated elsewhere. Even so, I do have a little concern about the complexity of the document – it almost feels like there is too much information and too many options to make a clear standard, but maybe not.

Update: As with RSA digital signatures, the world has been using RSA for key exchange for years, even in FIPS-validated modules. So, a draft of SP800-56B has been released for public comment.

NIST requests comments on Draft SP 800-56B, Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography. This Recommendation provides the specifications of asymmetric-based key agreement and key transport schemes that are based on the Rivest Shamir Adleman (RSA) algorithm.

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 = 36⁸ possible passwords.

Flipping through “The Mathematical Theory of Communication”, Shannon defined entropy, or the measure of uncertainty, for a set of probabilities p₁,…,p_n, as H = -∑ p_i log p_i, where p_i is the probably of an event i.

Looking at SP800-90, min-entropy, another measure of uncertainty, for a set of probabilities p₁,…,p_n is defined as H = -log₂(p_max), where p_max is the maximum p in p₁,…,p_n.

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 p_i for each digit of the password, and our Shannon H = -∑ p_i log p_i = -1 log 1 = 0 and our min-entropy H = -log₂1 = 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 = -∑ p_i log p_i = -((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 = -log₂(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/(36⁸)=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.