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.

Poll “Primary motives for hacking are” which was open on this blog since December 21, 2007 to March 31, 2008 is closed now. Based on answers of visitors, who took opportunity to vote in the poll, main reason why hackers (malicious ones) are attacking is because they take it as intellectual challenge. Next reason is money etc.

Here is summary of results.

As it was said in introductory post for poll, it is based on Australian government Institute of Criminology i.e. its High tech crime centre classification. You can see paper (linked in blog post also) here.

There were polemic about definition of hackers and is that correct to say that hackers are malicious. Many people think that definition of hackers mean that they “wear white hat” i.e. hackers are not driven by malicious motives. However, crackers are ones who “wear black hat” i.e. they are supposed to be malicious, according that opinion. Also, some people mentioned that poll lacks precise definition of hacking and description of hacker and cracker difference for sake of this poll.

This poll is about public opinion - what people think about hackers and their motives, so it was left to opinions and thoughts of everyone and a little bit imprecise (intentionally). :)

You can look into Merriam-Webster’s dictionary definition of hacker – it may be interesting.

There is interesting call for papers for an Elsevier’s special issue of Electronic Commerce Research and Applications on Social Networks and Web 2.0. You can submit your manuscripts online. Papers will be reviewed and published depending of reviewers’ decisions.

It will cover many of relevant topics related to this hot and fast evolving area. I’m particularly interested in privacy and protections issues of social networks and Web 2.0.

Important dates are:

• Optional abstracts: April 15, 2008
• Initial submission: June 15, 2008
• First round reviews: August 15, 2008
• Resubmission by: October 15, 2008
• Final acceptance: December 15, 2008

I’ve put poll on this blog to find out what is public opinion on primary motives for hacking.  There are six possible choices and you can choose one according your opinion. Answers are based on Australian government Institute of Criminology i.e. its High tech crime centre classification. You can see paper here and vote in box with yellow background at right sidebar.

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.

Paper Reduction of False Positive Intrusions by using Neural Nets, which I worked on with colleagues, is now available at IEEE Digital Library.

Abstract

The main idea of this paper is to propose a new solution for a Wireless Intrusion Detection Prevention System (WIDPS). The proposed WIDPS has a high degree of autonomy in tracking suspicious activity and detecting positive intrusions. Our focus was the reduction of detected false positive intrusion by implementing adaptive self-learning neural net in the system. Once it is fully developed and tested, this WIDPS would enable real-time response against threats, even to zero-day attacks.

Remark: Subscription to IEEE Digital Library required to download full paper in PDF format.

Foreign-born researchers are significant contributors to U.S. science and technology endeavors.  In fact, between 1990 and 2004, more than one-third of all Nobel prizes in the United States have gone to foreign-born recipients.  The success of many U.S. universities and research institutions depends on attracting the best and brightest students both at home and abroad.  After tighter visa restrictions were enforced following the Sept. 11 attacks, international student enrollment decreased dramatically.  Although some visa restrictions have been lifted and foreign enrollment is again on the rise, the visa clearance process should continue to be monitored, the report says. Report: Science and Security in a Post 9/11 World: A Report Based on Regional Discussions Between the Science and Security Communities.

To strengthen the essential role that science and technology play in maintaining national and economic security, the United States should ensure the open exchange of unclassified research despite the small risk that it could be misused for harm by terrorists or rogue nations, says a new report by the National Research Council.  Because science and technology are truly global pursuits, U.S. universities and research institutions must continue to welcome foreign-born science and engineering students, said the committee of former national security leaders and senior university researchers and administrators that wrote the report.

Prediction markets are speculative markets created for the purpose of making predictions. Assets are created whose final cash value is tied to a particular event (e.g., will the next US president be a Republican) or parameter (e.g., total sales next quarter). The current market prices can then be interpreted as predictions of the probability of the event or the expected value of the parameter. Other names for prediction markets include information markets, decision markets, idea futures, event derivatives, and virtual markets. Hewlett-Packard pioneered applications in sales forecasting and now uses prediction markets in several business units. Above text is mostly based on Wikipedia article on predictive markets.

Few days ago I’ve got message from Qmarkets to try their system and create question about a future event, and invite people to provide you with answers. Here is my question:

How much will your company / organization (or you as individual) invest in security in year 2008 in relation to 2007?

• Try Qmarkets here >>.

P.S. This question, I put there, is probably not best suited question for prediction markets, but I just exercise. Noam from Qmarkets will support me, I’m sure. :)

An excellent series of blog posts by Microsoft’s Larry Osterman about threat modeling with links to all 13 posts is here. Someone who signed comment as Bill Gates (it might be real Bill?) wrote:

Larry, keep up the good work, I wish we had more people like you in Redmond.

This series of posts is pretty long, detailed, and complicated, but well worth reading.