Dragan on Security

It seems that bad days came for MD5 and those who based hashes on it. It is possible to create two executable programs with different functionalities with identical MD5 hash. Therefore, it is possible to create malicious executable which has same MD5 hash as regular program. This can be done just by using public Internet information and tools.

Here is short story and list of resources that you can be interested in to try.

In March 2005, Xiaoyun Wang and Hongbo Yu of Shandong University in China published paper “How to Break MD5 and Other Hash Functions” in which they described an algorithm that can find two different sequences of 128 bytes with the same MD5 hash. That article originally was here, but it seems as it not anymore. You can buy it from SpringerLink (here) for price of $25, or download based on subscription to it. There is free Power Point presentation here.

Abstract of paper “How to Break MD5 and Other Hash Functions” says:

MD5 is one of the most widely used cryptographic hash functions nowadays. It was designed in 1992 as an improvement of MD4, and its security was widely studied since then by several authors. The best known result so far was a semi free-start collision, in which the initial value of the hash function is replaced by a non-standard value, which is the result of the attack. In this paper we present a new powerful attack on MD5 which allows us to find collisions efficiently. We used this attack to find collisions of MD5 in about 15 minutes up to an hour computation time. The attack is a differential attack, which unlike most differential attacks, does not use the exclusive-or as a measure of difference, but instead uses modular integer subtraction as the measure. We call this kind of differential a modular differential. An application of this attack to MD4 can find a collision in less than a fraction of a second. This attack is also applicable to other hash functions, such as RIPEMD and HAVAL.

In meantime, Peter Selinger from Department of Mathematics and Statistics, Dalhousie University, published the tool that you can download for free and which he used to create MD5-colliding executable files. He calls it the “evilize” library. This software is based on Patrick Stach’s implementation of Wang and Yu’s algorithm. You can find his original implementation here.

Eduardo Diaz has described a scheme by which two programs could be packed into two archives with identical MD5 hash. A special “extractor” program turns one archive into a “good” program and the other into an “evil” one.

Almost three years ago I had published blog post on MD5 Online Cracking. Also, I have written about NIST new hash competition here and here.

[Thanks to Zeljko for pointing me to this implementation of tool.]

I had already written the post about NIST Competition for New Cryptographic Hash Function on my blog. Here are updates based on article by William E. Burr, “A New Hash Competition”, IEEE Security and Privacy, vol. 6,  no. 3,  pp. 60-62,  May/Jun,  2008.

Author says in abstract:

Since the discovery of collision attacks against several well-known cryptographic hash functions in 2004, a rush of new cryptanalytic results cast doubt on the current hash function standards. The relatively new NIST SHA-2 standards aren’t yet immediately threatened, but their long-term viability is now in question. The US National Institute of Standards and Technology (NIST) has therefore begun an international competition to select a new SHA-3 standard. This article outlines the competition, its rules, the requirements for the hash function candidates, and the process that NIST will use to select the final winning SHA-3 standard.

And then, in article:

NIST expects to launch a Hash Competition Conference to review the initial submissions in February 2009; the second conference will occur roughly a year later in 2010 to review public comments submitted on the submissions and their analysis. Following this second conference, NIST will select a small number of finalist candidates (probably five or so) for intensive review by the community. If, as we expect, we get 20 or more initial submissions, we’ll inevitably hear some disagreements about the finalists, but we can only intensively analyze a small number of algorithms, and, as in the AES competition, all the finalists will be good hash functions, although we might have to drop some worthy submissions.

Cryptanalysis of the finalists will be the tricky part—the time that skilled cryptanalysts can donate is the limiting resource here.

NIST is building up its limited cryptanalytic resources, but will rely heavily on the global cryptographic research community to do the bulk of the cryptanalysis. If the AES competition is any model, many analysis papers on the candidates will be submitted to various conferences. NIST will tentatively review the cryptanalysis results and review performance in a third workshop scheduled for 2012, after which they will select a winner.

The winning team might get nothing but glory for their huge effort. NIST expects the best people in the world to participate, as they did in the AES competition, because the community believes an open competition is the best way to select cryptographic standards. NIST expects to work hard, have fun, and significantly advance the state of the art while giving the world a valuable, secure hash function standard.

If you’ve thought your data are secure on encrypted hard disk, read: Lest We Remember: Cold Boot Attacks on Encryption Keys. Researchers with Princeton University and the Electronic Frontier Foundation (EFF) have found a flaw that renders disk encryption systems useless if an intruder has physical access to your computer - say in the case of a stolen laptop or when a computer is left unattended on a desktop in sleep mode or while displaying a password prompt screen. The attack takes only a few minutes to conduct and uses the disk encryption key that’s stored in the computer’s RAM.

There is also full research paper and YouTube video about this attack.

Abstract says:

Contrary to popular assumption, DRAMs used in most modern computers retain their contents for seconds to minutes after power is lost, even at operating temperatures and even if removed from a motherboard. Although DRAMs become less reliable when they are not refreshed, they are not immediately erased, and their contents persist sufficiently for malicious (or forensic) acquisition of usable full-system memory images. We show that this phenomenon limits the ability of an operating system to protect cryptographic key material from an attacker with physical access. We use cold reboots to mount attacks on popular disk encryption systems — BitLocker, FileVault, dm-crypt, and TrueCrypt — using no special devices or materials. We experimentally characterize the extent and predictability of memory remanence and report that remanence times can be increased dramatically with simple techniques. We offer new algorithms for finding cryptographic keys in memory images and for correcting errors caused by bit decay. Though we discuss several strategies for partially mitigating these risks, we know of no simple remedy that would eliminate them.

[Thanks to colleague Sanida O. for bringing this to my attention].

Go to Paper Enigma Machine, download this one-page PDF file; print it using heavy card stock (recommended).  You can then cut out the strips, and follow the directions on the page to build your own fully functional Enigma machine. Author says:

This machine is compatible with the original 3-rotor German Enigma used during World War II.  For simplicity it omits the “ring settings” and plug board, but the primary workings of the machine are captured in this model.  Great as an educational tool, or just for fun!

Read more about Enigma here.

Also see Enigma Simulation in Flash.

The secret cipher that secures Mifare Classic RFID tags used in access control systems, subway tickets, and various other security-related applications has recently been disclosed.

The attack works against the Mifare Classic, a wireless card made by Netherlands-based NXP Semiconductors. It is used by transit operators in London, Boston and the Netherlands and by organizations in the public and private sectors to control access to sensitive areas, according to Karsten Nohl, a PhD candidate at the University of Virginia and one of the cryptographers who discovered the weakness. NXP says it’s sold 1 billion to 2 billion of the cards.

There’s another hack of that system published in PC World. Press release from Radboud University is here, and there is also a short video demo  that shows hack in action.

The Dutch government has issued a warning about the security of access keys that are based on the widely used Mifare Classic RFID chip.  Government institutions plan to take “additional security measures to safeguard security,” Guusje ter Horst, minister of interior affairs, wrote in a letter to parliament on Wednesday.

It is interesting to read what Bruce Schneier said in August 1999 issue of Crypto-Gram newsletter about Cryptography: The Importance of Not Being Different.

Many companies still fail to learn principles of cryptography.

The Enigma was an electro-mechanical cipher machine used by the German Military during WW II. The following link shows Enigma Simulation done in Adobe Flash 8 by Dr. Frank Spiess. You will have chance to see how it worked. Highlighted wires show steps of encryption.

This Enigma simulation is part of Cryptool.com, a great collection of cryptographic tools and demos.

If you are interested in cryptography, there is very good YouTube video: Theory and Practice of Cryptography. You’ll need one hour of time to watch it.

Topics include: Introduction to Modern Cryptography, Using Cryptography in Practice and at Google, Proofs of Security and Security Definitions and A Special Topic in Cryptography.

This talk is one in a series hosted by Google University. Speaker is Steve Weis. He received his PhD from the Cryptography and Information Security group at MIT, where he was advised by Ron Rivest. He is a member of Google’s Applied Security (AppSec) team and is the technical lead for Google’s internal cryptographic library, KeyMaster.

The Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone is available online - legitimately. This is a good book, and well worth downloading. I also would recommend Applied Cryptography by Bruce Schneier which is not free yet, but is very good and considered as bible of cryptography.

A recent paper found a flaw in the Windows 2000 random-number generator. Another paper found flaws in the Linux random-number generator. Back in 1996, an early version of SSL was broken because of flaws in its random-number generator.

Bruce Schneier discussed this problem on his blog and said:

Which is why you should worry about a new random-number standard that includes an algorithm that is slow, badly designed and just might contain a backdoor for the National Security Agency.

Also there is post “NSA Helps Microsoft and Apple for Better Security” on this blog and it has couple of links that confirm this possibility in some way.

Neal Koblitz published paper “The Uneasy Relationship Between Mathematics and Cryptography” at Notices of the American Mathematical Society. This article has been commented on Bruce Schneier’s blog on security and rebuttals came from Oded Goldreich, Hugo Krawczyk, Jonathan Katz, Luca Trevisan, and Boaz Barak. This is long reading, if you are going to read all mentioned articles and reactions, but very interesting for everyone who want to know more about concepts and misconceptions of cryptography and mathematic with different points of view.