Entries Tagged "academic papers"

Page 76 of 77

NIST Hash Workshop Liveblogging (2)

In the morning we had a series of interesting papers: “Strengthening Digital Signatures via Randomized Hashing,” by Halevi and Krawczyk; “Herding Hash Functions and the Nostradamus Attack,” by Kelsey and Kohno; and “Collision-Resistant usage of MD5 and SHA-1 via Message Preprocessing,” by Szydlo and Yin. The first and third papers are suggestions for modifying SHA-1 to make it more secure. The second paper discusses some fascinating and cool, but still theoretical, attacks on hash functions.

The last session before lunch was a panel discussion: “SHA-1: Practical Security Implications of Continued Use.” The panel stressed that these are collision attacks and not pre-image attacks, and that many protocols simply don’t care. Collision attacks are important for digital signatures, but less so for other uses of hash functions. On the other hand, this difference is only understood by cryptographers; there are issues if the public believes that SHA-1 is “broken.”

Niels Ferguson pointed out that the big problem is MD5, which is still used everywhere. (Hell, DES is still everywhere.) It takes much longer to upgrade algorithms on the Internet than most people believe; Steve Bellovin says it takes about one year to get the change through the IETF, and another five to seven years to get it depoloyed. And that’s after we all figure out which algorithm they should use.

Georg Illies gave a perspective from Germany, where there is a digital-signature law in effect. In addition to the technology, there are legal considerations that make it harder to switch.

The panel seemed to agree that it’s still safe to use SHA-1 today, but that we need to start migrating to something better. It’s way easier to change algorithms when you’re not in the middle of a panic.

There was more talk about algorithm agility. This problem is larger than SHA. Our Internet protocols simply don’t have a secure methodology for migrating from one cryptographic algorithm to another.

Bottom line: Don’t use SHA-1 for anything new, and start moving away from it as soon as possible. To SHA-256, probably.

And now it’s lunchtime.

Posted on October 31, 2005 at 11:50 AMView Comments

NIST Hash Workshop Liveblogging (1)

I’m in Gaithersburg, MD, at the Cryptographic Hash Workshop hosted by NIST. I’m impressed by the turnout; a lot of the right people are here.

Xiaoyun Wang, the cryptographer who broke SHA-1, spoke about her latest results. They are the same results Adi Shamir presented in her name at Crypto this year: a time complexity of 263.

(I first wrote about Wang’s results here, and discussed their implications here. I wrote about results from Crypto here. Here are her two papers from Crypto: “Efficient Collision Search Attacks on SHA-0” and “Finding Collisions in the Full SHA-1 Collision Search Attacks on SHA1.”)

Steve Bellovin is now talking about the problems associated with upgrading hash functions. He and his coauthor Eric Rescorla looked at S/MIME, TLS, IPSec (and IKE), and DNSSEC. Basically, these protocols can’t change algorithms overnight; it has to happen gradually, over the course of years. So the protocols need some secure way to “switch hit”: to use both the new and old hash functions during the transition period. This requires some sort of signaling, which the protocols don’t do very well. (Bellovin’s and Rescorla’s paper is here.)

Posted on October 31, 2005 at 9:02 AMView Comments

SMS Denial-of-Service Attack

This is a clever piece of research. Turns out you can jam cell phones with SMS messages. Text messages are transmitted on the same channel that is used to set up voice calls, so if you flood the network with one, then the other can’t happen. The researchers believe that sending 165 text messages a second is enough to disrupt all the cell phones in Manhattan.

From the paper:

ABSTRACT: Cellular networks are a critical component of the economic and social infrastructures in which we live. In addition to voice services, these networks deliver alphanumeric text messages to the vast majority of wireless subscribers. To encourage the expansion of this new service, telecommunications companies offer connections between their networks and the Internet. The ramifications of such connections, however, have not been fully recognized. In this paper, we evaluate the security impact of the SMS interface on the availability of the cellular phone network. Specifically, we demonstrate the ability to deny voice service to cities the size of Washington D.C. and Manhattan with little more than a cable modem. Moreover, attacks targeting the entire United States are feasible with resources available to medium-sized zombie networks. This analysis begins with an exploration of the structure of cellular networks. We then characterize network behavior and explore a number of reconnaissance techniques aimed at effectively targeting attacks on these systems. We conclude by discussing countermeasures that mitigate or eliminate the threats introduced by these attacks.

There’s a New York Times article and a thread on Slashdot.

Posted on October 7, 2005 at 7:43 AMView Comments

Research in Behavioral Risk Analysis

I very am interested in this kind of research:

Network Structure, Behavioral Considerations and Risk Management in Interdependent Security Games

Interdependent security (IDS) games model situations where each player has to determine whether or not to invest in protection or security against an uncertain event knowing that there is some chance s/he will be negatively impacted by others who do not follow suit. IDS games capture a wide variety of collective risk and decision-making problems that include airline security, corporate governance, computer network security and vaccinations against diseases. This research project will investigate the marriage of IDS models with network formation models developed from social network theory and apply these models to problems in network security. Behavioral and controlled experiments will examine how human participants actually make choices under uncertainty in IDS settings. Computational aspects of IDS models will also be examined. To encourage and induce individuals to invest in cost-effective protection measures for IDS problems, we will examine several risk management strategies designed to foster cooperative behavior that include providing risk information, communication with others, economic incentives, and tipping strategies.

The proposed research is interdisciplinary in nature and should serve as an exciting focal point for researchers in computer science, decision and management sciences, economics, psychology, risk management, and policy analysis. It promises to advance our understanding of decision-making under risk and uncertainty for problems that are commonly faced by individuals, organizations, and nations. Through advances in computational methods one should be able to apply IDS models to large-scale problems. The research will also focus on weak links in an interdependent system and suggest risk management strategies for reducing individual and societal losses in the interconnected world in which we live.

Posted on September 15, 2005 at 7:05 AMView Comments

Snooping on Text by Listening to the Keyboard

Fascinating research out of Berkeley. Ed Felten has a good summary:

Li Zhuang, Feng Zhou, and Doug Tygar have an interesting new paper showing that if you have an audio recording of somebody typing on an ordinary computer keyboard for fifteen minutes or so, you can figure out everything they typed. The idea is that different keys tend to make slightly different sounds, and although you don’t know in advance which keys make which sounds, you can use machine learning to figure that out, assuming that the person is mostly typing English text. (Presumably it would work for other languages too.)

Read the rest.

The paper is on the Web. Here’s the abstract:

We examine the problem of keyboard acoustic emanations. We present a novel attack taking as input a 10-minute sound recording of a user typing English text using a keyboard, and then recovering up to 96% of typed characters. There is no need for a labeled training recording. Moreover the recognizer bootstrapped this way can even recognize random text such as passwords: In our experiments, 90% of 5-character random passwords using only letters can be generated in fewer than 20 attempts by an adversary; 80% of 10-character passwords can be generated in fewer than 75 attempts. Our attack uses the statistical constraints of the underlying content, English language, to reconstruct text from sound recordings without any labeled training data. The attack uses a combination of standard machine learning and speech recognition techniques, including cepstrum features, Hidden Markov Models, linear classification, and feedback-based incremental learning.

Posted on September 13, 2005 at 8:13 AMView Comments

Tamper-Evident Paper Mailings

We’ve all received them in the mail: envelopes from banks with PINs, access codes, or other secret information. The letters are somewhat tamper-proof, but mostly they’re designed to be tamper-evident: if someone opens the letter and reads the information, you’re going to know. The security devices include fully sealed packaging, and black inks that obscure the secret information if you hold the envelope up to the light.

Researchers from Cambridge University have been looking at the security inherent in these systems, and they’ve written a paper that outlines how to break them:

Abstract. Tamper-evident laser-printed PIN mailers are used by many institutions to issue PINs and other secrets to individuals in a secure manner. Such mailers are created by printing the PIN using a normal laser, but on to special stationery and using a special font. The background of the stationery disguises the PIN so that it cannot be read with the naked eye without tampering. We show that currently deployed PIN mailer technology (used by the major UK banks) is vulnerable to trivial attacks that reveal the PIN without tampering. We describe image processing attacks, where a colour difference between the toner and the stationary “masking pattern” is exploited. We also describe angled light attacks, where the reflective properties of the toner and stationery are exploited to allow the naked eye to separate the PIN from the backing pattern. All laser-printed mailers examined so far have been shown insecure.

According to a researcher website:

It should be noted that we sat on this report for about 9 months, and the various manufacturers all have new products which address to varying degrees the issues raised in the report.

BBC covered the story.

Posted on August 30, 2005 at 7:59 AMView Comments

New Cryptanalytic Results Against SHA-1

Xiaoyun Wang, one of the team of Chinese cryptographers that successfully broke SHA-0 and SHA-1, along with Andrew Yao and Frances Yao, announced new results against SHA-1 yesterday at Crypto’s rump session. (Actually, Adi Shamir announced the results in their name, since she and her student did not receive U.S. visas in time to attend the conference.)

Shamir presented few details—and there’s no paper—but the time complexity of the new attack is 263. (Their previous result was 269; brute force is 280.) He did say that he expected Wang and her students to improve this result over the next few months. The modifications to their published attack are still new, and more improvements are likely over the next several months. There is no reason to believe that 263 is anything like a lower limit.

But an attack that’s faster than 264 is a significant milestone. We’ve already done massive computations with complexity 264. Now that the SHA-1 collision search is squarely in the realm of feasibility, some research group will try to implement it. Writing working software will both uncover hidden problems with the attack, and illuminate hidden improvements. And while a paper describing an attack against SHA-1 is damaging, software that produces actual collisions is even more so.

The story of SHA-1 is not over. Again, I repeat the saying I’ve heard comes from inside the NSA: “Attacks always get better; they never get worse.”

Meanwhile, NIST is holding a workshop in late October to discuss what the security community should do now. The NIST Hash Function Workshop should be interesting, indeed. (Here is one paper that examines the effect of these attacks on S/MIME, TLS, and IPsec.)

EDITED TO ADD: Here are Xiaoyun Wang’s two papers from Crypto this week: “Efficient Collision Search Attacks on SHA-0” and “Finding Collisions in the Full SHA-1Collision Search Attacks on SHA1.” And here are the rest of her papers.

Posted on August 17, 2005 at 2:06 PMView Comments

Plagiarism and Academia: Personal Experience

A paper published in the December 2004 issue of the SIGCSE Bulletin, “Cryptanalysis of some encryption/cipher schemes using related key attack,” by Khawaja Amer Hayat, Umar Waqar Anis, and S. Tauseef-ur-Rehman, is the same as a paper that John Kelsey, David Wagner, and I published in 1997.

It’s clearly plagiarism. Sentences have been reworded or summarized a bit and many typos have been introduced, but otherwise it’s the same paper. It’s copied, with the same section, paragraph, and sentence structure—right down to the same mathematical variable names. It has the same quirks in the way references are cited. And so on.

We wrote two papers on the topic; this is the second. They don’t list either of our papers in their bibliography. They do have a lurking reference to “[KSW96]” (the first of our two papers) in the body of their introduction and design principles, presumably copied from our text; but a full citation for “[KSW96]” isn’t in their bibliography. Perhaps they were worried that one of the referees would read the papers listed in their bibliography, and notice the plagiarism.

The three authors are from the International Islamic University in Islamabad, Pakistan. The third author, S. Tauseef-Ur-Rehman, is a department head (and faculty member) in the Telecommunications Engineering Department at this Pakistani institution. If you believe his story—which is probably correct—he had nothing to do with the research, but just appended his name to a paper by two of his students. (This is not unusual; it happens all the time in universities all over the world.) But that doesn’t get him off the hook. He’s still responsible for anything he puts his name on.

And we’re not the only ones. The same three authors plagiarized this paper by French cryptographer Serge Vaudenay and others.

I wrote to the editor of the SIGCSE Bulletin, who removed the paper from their website and demanded official letters of admission and apology. (The apologies are at the bottom of this page.) They said that they would ban them from submitting again, but have since backpedaled. Mark Mandelbaum, Director of the Office of Publications at ACM, now says that ACM has no policy on plagiarism and that nothing additional will be done. I’ve also written to Springer-Verlag, the publisher of my original paper.

I don’t blame the journals for letting these papers through. I’ve refereed papers, and it’s pretty much impossible to verify that a piece of research is original. We’re largely self-policing.

Mostly, the system works. These three have been found out, and should be fired and/or expelled. Certainly ACM should ban them from submitting anything, and I am very surprised at their claim that they have no policy with regards to plagiarism. Academic plagiarism is serious enough to warrant that level of response. I don’t know if the system works in Pakistan, though. I hope it does. These people knew the risks when they did it. And then they did it again.

If I sound angry, I’m not. I’m more amused. I’ve heard of researchers from developing countries resorting to plagiarism to pad their CVs, but I’m surprised see it happen to me. I mean, really; if they were going to do this, wouldn’t it have been smarter to pick a more obscure author?

And it’s nice to know that our work is still considered relevant eight years later.

EDITED TO ADD: Another paper, “Analysis of Real-time Transport Protocol Security,” by Junaid Aslam, Saad Rafique and S. Tauseef-ur-Rehman”, has been plagiarized from this original: Real-time Transport Protocol (RTP) security,” by Ville Hallivuori.

EDITED TO ADD: Ron Boisvert, the Co-Chair of the ACM Publications Board, has said this:

1. ACM has always been a champion for high ethical standards among computing professionals. Respecting intellectual property rights is certainly a part of this, as is clearly reflected in the ACM Code of Ethics.

2. ACM has always acted quickly and decisively to deal with allegations of plagarism related to its publications, and remains committed to doing so in the future.

3. In the past, such incidents of plagarism were rare. However, in recent years the number of such incidents has grown considerably. As a result, the ACM Publications Board has recently begun work to develop a more explicit policy on plagarism. In doing so we hope to lay out (a) what constitutes plagarism, as well as various levels of plagarism, (b) ACM procedures for handling allegations of plagarism, and (c) specific penalties which will be leveled against those found to have committed plagarism at each of the identified levels. When this new “policy” is in place, we hope to widely publicize it in order to draw increased attention to this growing problem.

EDITED TO ADD: There’s a news story with some new developments.

EDITED TO ADD: Over the past couple of weeks, I have been getting repeated e-mails from people, presumably faculty and administrators of the International Islamic University, to close comments in this blog entry. The justification usually given is that there is an official investigation underway so there’s no longer any reason for comments, or that Tauseef has been fired so there’s no longer any reason for comments, or that the comments are harmful to the reputation of the university or the country.

I have responded that I will not close comments on this blog entry. I have, and will continue to, delete posts that are incoherent or hostile (there have been examples of both).

Blog comments are anonymous. There is no way for me to verify the identity of posters, and I don’t. I have, and will continue to, remove any posts purporting to come from a person it does not come, but generally the only way I can figure that out is if the real person e-mails me and asks.

Otherwise, consider this a forum for anonymous free speech. The comments here are unvetted and unverified. They might be true, and they might be false. Readers are expected to understand that, and I believe for the most part they do.

In the United States, we have a saying that the antidote for bad speech is more speech. I invite anyone who disagrees with the comments on the page to post their own opinions.

Posted on August 1, 2005 at 6:07 AMView Comments

SHA Cryptanalysis Paper Online

In February, I wrote about a group of Chinese researchers who broke the SHA-1 hash function. That posting was based on short notice from the researchers. Since then, many people have written me asking about the research and the actual paper, some questioning the validity of the research because of the lack of documentation.

The paper did exist; I saw a copy. They will present it at the Crypto conference in August. I believe they didn’t post it because Crypto requires that submitted papers not be previously published, and they misunderstood that to mean that it couldn’t be widely distributed in any way.

Now there’s a copy of the paper on the web. You can read “Finding Collisions in the Full SHA-1,” by Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, here.

Posted on June 24, 2005 at 12:46 PMView Comments

Sidebar photo of Bruce Schneier by Joe MacInnis.