Entries Tagged "authentication"

Page 26 of 26

Cryptanalysis of SHA-1

On Tuesday, I blogged about a new cryptanalytic result—the first attack faster than brute-force against SHA-1. I wrote about SHA, and the need to replace it, last September. Aside from the details of the new attack, everything I said then still stands. I’ll quote from that article, adding new material where appropriate.

One-way hash functions are a cryptographic construct used in many applications. They are used in conjunction with public-key algorithms for both encryption and digital signatures. They are used in integrity checking. They are used in authentication. They have all sorts of applications in a great many different protocols. Much more than encryption algorithms, one-way hash functions are the workhorses of modern cryptography.

In 1990, Ron Rivest invented the hash function MD4. In 1992, he improved on MD4 and developed another hash function: MD5. In 1993, the National Security Agency published a hash function very similar to MD5, called SHA (Secure Hash Algorithm). Then, in 1995, citing a newly discovered weakness that it refused to elaborate on, the NSA made a change to SHA. The new algorithm was called SHA-1. Today, the most popular hash function is SHA-1, with MD5 still being used in older applications.

One-way hash functions are supposed to have two properties. One, they’re one way. This means that it is easy to take a message and compute the hash value, but it’s impossible to take a hash value and recreate the original message. (By “impossible” I mean “can’t be done in any reasonable amount of time.”) Two, they’re collision free. This means that it is impossible to find two messages that hash to the same hash value. The cryptographic reasoning behind these two properties is subtle, and I invite curious readers to learn more in my book Applied Cryptography.

Breaking a hash function means showing that either—or both—of those properties are not true.

Earlier this week, three Chinese cryptographers showed that SHA-1 is not collision-free. That is, they developed an algorithm for finding collisions faster than brute force.

SHA-1 produces a 160-bit hash. That is, every message hashes down to a 160-bit number. Given that there are an infinite number of messages that hash to each possible value, there are an infinite number of possible collisions. But because the number of possible hashes is so large, the odds of finding one by chance is negligibly small (one in 280, to be exact). If you hashed 280 random messages, you’d find one pair that hashed to the same value. That’s the “brute force” way of finding collisions, and it depends solely on the length of the hash value. “Breaking” the hash function means being able to find collisions faster than that. And that’s what the Chinese did.

They can find collisions in SHA-1 in 269 calculations, about 2,000 times faster than brute force. Right now, that is just on the far edge of feasibility with current technology. Two comparable massive computations illustrate that point.

In 1999, a group of cryptographers built a DES cracker. It was able to perform 256 DES operations in 56 hours. The machine cost $250K to build, although duplicates could be made in the $50K-$75K range. Extrapolating that machine using Moore’s Law, a similar machine built today could perform 260 calculations in 56 hours, and 269 calculations in three and a quarter years. Or, a machine that cost $25M-$38M could do 269 calculations in the same 56 hours.

On the software side, the main comparable is a 264 keysearch done by distributed.net that finished in 2002. One article put it this way: “Over the course of the competition, some 331,252 users participated by allowing their unused processor cycles to be used for key discovery. After 1,757 days (4.81 years), a participant in Japan discovered the winning key.” Moore’s Law means that today the calculation would have taken one quarter the time—or have required one quarter the number of computers—so today a 269 computation would take eight times as long, or require eight times the computers.

The magnitude of these results depends on who you are. If you’re a cryptographer, this is a huge deal. While not revolutionary, these results are substantial advances in the field. The techniques described by the researchers are likely to have other applications, and we’ll be better able to design secure systems as a result. This is how the science of cryptography advances: we learn how to design new algorithms by breaking other algorithms. Additionally, algorithms from the NSA are considered a sort of alien technology: they come from a superior race with no explanations. Any successful cryptanalysis against an NSA algorithm is an interesting data point in the eternal question of how good they really are in there.

For the average Internet user, this news is not a cause for panic. No one is going to be breaking digital signatures or reading encrypted messages anytime soon. The electronic world is no less secure after these announcements than it was before.

But there’s an old saying inside the NSA: “Attacks always get better; they never get worse.” Just as this week’s attack builds on other papers describing attacks against simplified versions of SHA-1, SHA-0, MD4, and MD5, other researchers will build on this result. The attack against SHA-1 will continue to improve, as others read about it and develop faster tricks, optimizations, etc. And Moore’s Law will continue to march forward, making even the existing attack faster and more affordable.

Jon Callas, PGP’s CTO, put it best: “It’s time to walk, but not run, to the fire exits. You don’t see smoke, but the fire alarms have gone off.” That’s basically what I said last August.

It’s time for us all to migrate away from SHA-1.

Luckily, there are alternatives. The National Institute of Standards and Technology already has standards for longer—and harder to break—hash functions: SHA-224, SHA-256, SHA-384, and SHA-512. They’re already government standards, and can already be used. This is a good stopgap, but I’d like to see more.

I’d like to see NIST orchestrate a worldwide competition for a new hash function, like they did for the new encryption algorithm, AES, to replace DES. NIST should issue a call for algorithms, and conduct a series of analysis rounds, where the community analyzes the various proposals with the intent of establishing a new standard.

Most of the hash functions we have, and all the ones in widespread use, are based on the general principles of MD4. Clearly we’ve learned a lot about hash functions in the past decade, and I think we can start applying that knowledge to create something even more secure.

Hash functions are the least-well-understood cryptographic primitive, and hashing techniques are much less developed than encryption techniques. Regularly there are surprising cryptographic results in hashing. I have a paper, written with John Kelsey, that describes an algorithm to find second preimages with SHA-1 ­—a technique that generalizes to almost all other hash functions—in 2106 calculations: much less than the 2160 calculations for brute force. This attack is completely theoretical and not even remotely practical, but it demonstrates that we still have a lot to learn about hashing.

It is clear from rereading what I wrote last September that I expected this to happen, but not nearly this quickly and not nearly this impressively. The Chinese cryptographers deserve a lot of credit for their work, and we need to get to work replacing SHA.

Posted on February 18, 2005 at 11:24 PMView Comments

Pirated Windows to Remain Unpatched

From the Associated Press:

Microsoft Corp. plans to severely curtail the ways in which people running pirated copies of its dominant Windows operating system can receive software updates, including security fixes.

The new authentication system, announced Tuesday and due to arrive by midyear, will still allow people with pirated copies of Windows to obtain security fixes, but their options will be limited. The move allows Microsoft to use one of its sharpest weapons—access to security patches that can prevent viruses, worms and other crippling attacks—to thwart a costly and meddlesome piracy problem.

I’ve written about this before. Unpatched Windows systems on the Internet are a security risk to everyone. I understand Microsoft wanting to fight piracy, but reducing the security of its paying customers is not a good way to go about it.

Posted on February 17, 2005 at 8:00 AMView Comments

The Curse of the Secret Question

It’s happened to all of us: We sign up for some online account, choose a difficult-to-remember and hard-to-guess password, and are then presented with a “secret question” to answer. Twenty years ago, there was just one secret question: “What’s your mother’s maiden name?” Today, there are more: “What street did you grow up on?” “What’s the name of your first pet?” “What’s your favorite color?” And so on.

The point of all these questions is the same: a backup password. If you forget your password, the secret question can verify your identity so you can choose another password or have the site e-mail your current password to you. It’s a great idea from a customer service perspective—a user is less likely to forget his first pet’s name than some random password—but terrible for security. The answer to the secret question is much easier to guess than a good password, and the information is much more public. (I’ll bet the name of my family’s first pet is in some database somewhere.) And even worse, everybody seems to use the same series of secret questions.

The result is the normal security protocol (passwords) falls back to a much less secure protocol (secret questions). And the security of the entire system suffers.

What can one do? My usual technique is to type a completely random answer—I madly slap at my keyboard for a few seconds—and then forget about it. This ensures that some attacker can’t bypass my password and try to guess the answer to my secret question, but is pretty unpleasant if I forget my password. The one time this happened to me, I had to call the company to get my password and question reset. (Honestly, I don’t remember how I authenticated myself to the customer service rep at the other end of the phone line.)

Which is maybe what should have happened in the first place. I like to think that if I forget my password, it should be really hard to gain access to my account. I want it to be so hard that an attacker can’t possibly do it. I know this is a customer service issue, but it’s a security issue too. And if the password is controlling access to something important—like my bank account—then the bypass mechanism should be harder, not easier.

Passwords have reached the end of their useful life. Today, they only work for low-security applications. The secret question is just one manifestation of that fact.

This essay originally appeared on Computerworld.

Posted on February 11, 2005 at 8:00 AMView Comments

Authentication and Expiration

There’s a security problem with many Internet authentication systems that’s never talked about: there’s no way to terminate the authentication.

A couple of months ago, I bought something from an e-commerce site. At the checkout page, I wasn’t able to just type in my credit-card number and make my purchase. Instead, I had to choose a username and password. Usually I don’t like doing that, but in this case I wanted to be able to access my account at a later date. In fact, the password was useful because I needed to return an item I purchased.

Months have passed, and I no longer want an ongoing relationship with the e-commerce site. I don’t want a username and password. I don’t want them to have my credit-card number on file. I’ve received my purchase, I’m happy, and I’m done. But because that username and password have no expiration date associated with them, they never end. It’s not a subscription service, so there’s no mechanism to sever the relationship. I will have access to that e-commerce site for as long as it remembers that username and password.

In other words, I am liable for that account forever.

Traditionally, passwords have indicated an ongoing relationship between a user and some computer service. Sometimes it’s a company employee and the company’s servers. Sometimes it’s an account and an ISP. In both cases, both parties want to continue the relationship, so expiring a password and then forcing the user to choose another is a matter of security.

In cases with this ongoing relationship, the security consideration is damage minimization. Nobody wants some bad guy to learn the password, and everyone wants to minimize the amount of damage he can do if he does. Regularly changing your password is a solution to that problem.

This approach works because both sides want it to; they both want to keep the authentication system working correctly, and minimize attacks.

In the case of the e-commerce site, the interests are much more one-sided. The e-commerce site wants me to live in their database forever. They want to market to me, and entice me to come back. They want to sell my information. (This is the kind of information that might be buried in the privacy policy or terms of service, but no one reads those because they’re unreadable. And all bets are off if the company changes hands.)

There’s nothing I can do about this, but a username and password that never expire is another matter entirely. The e-commerce site wants me to establish an account because it increases the chances that I’ll use them again. But I want a way to terminate the business relationship, a way to say: “I am no longer taking responsibility for items purchased using that username and password.”

Near as I can tell, the username and password I typed into that e-commerce site puts my credit card at risk until it expires. If the e-commerce site uses a system that debits amounts from my checking account whenever I place an order, I could be at risk forever. (The US has legal liability limits, but they’re not that useful. According to Regulation E, the electronic transfers regulation, a fraudulent transaction must be reported within two days to cap liability at US$50; within 60 days, it’s capped at $500. Beyond that, you’re out of luck.)

This is wrong. Every e-commerce site should have a way to purchase items without establishing a username and password. I like sites that allow me to make a purchase as a “guest,” without setting up an account.

But just as importantly, every e-commerce site should have a way for customers to terminate their accounts and should allow them to delete their usernames and passwords from the system. It’s okay to market to previous customers. It’s not okay to needlessly put them at financial risk.

This essay also appeared in the Jan/Feb 05 issue of IEEE Security & Privacy.

Posted on February 10, 2005 at 7:55 AMView Comments

Bank Sued for Unauthorized Transaction

This story is interesting:

A Miami businessman is suing Bank of America over $90,000 he says was stolen from his online banking account in a case that highlights the thorny question of who is responsible when a customer’s computer is hacked into.

The typical press coverage of this story is along the lines of “Bank of America sued because customer’s PC was hacked.” But that’s not it. Bank of America is being sued because they allowed an unauthorized transaction to occur, and they’re not making good on that mistake. The transaction happened to occur because the customer’s PC was hacked.

I know nothing about the actual suit and its merits, but this is a problem that is not going away. And while I think that banks should not be held responsible for what’s on their customers’ machines, they should be held responsible for allowing unauthorized transactions to occur. The bank’s internal systems, however set up, for whatever reason, permitted the fraudulent transaction.

There is a simple economic incentive problem here. As long as the banks are not responsible for financial losses from fraudulent transactions over the Internet, banks have no incentive to improve security. But if banks are held responsible for these transactions, you can bet that they won’t allow such shoddy security.

Posted on February 9, 2005 at 8:00 AMView Comments

Flying on Someone Else's Airline Ticket

Slate has published a method for anyone to fly on anyone else’s ticket.

I wrote about this exact vulnerability a year and a half ago.

The vulnerability is obvious, but the general concepts are subtle. There are three things to authenticate: the identity of the traveler, the boarding pass, and the computer record. Think of them as three points on the triangle. Under the current system, the boarding pass is compared to the traveler’s identity document, and then the boarding pass is compared with the computer record. But because the identity document is never compared with the computer record—the third leg of the triangle—it’s possible to create two different boarding passes and have no one notice. That’s why the attack works.

Posted on February 8, 2005 at 9:11 AMView Comments

DHS Biometric ID Cards

The Department of Homeland Security is considering a biometric identification card for transportation workers:

TWIC is a tamper-resistant credential that contains biometric information about the holder which renders the card useless to anyone other than the rightful owner. Using this biometric data, each transportation facility can verify the identity of a worker and help prevent unauthorized individuals from accessing secure areas. Currently, many transportation workers must carry a different identification card for each facility they access. A standard TWIC would improve the flow of commerce by eliminating the need for redundant credentials and streamlining the identity verification process.

I’ve written extensively about the uses and abuses of biometrics (Beyond Fear, pages 197-200). The short summary is that biometrics are great as a local authentication tool and terrible as a identification tool. For a whole bunch of reasons, this DHS project is a good use of biometrics.

Posted on January 19, 2005 at 8:55 AMView Comments

Canadian Airport Security Loses Uniforms

From CBC News:

1,127 uniform items belonging to Canadian airport screeners were lost or stolen in a nine-month period.

I’m not sure if this is an interesting story or not. We know that a uniform isn’t necessarily a reliable authentication tool, yet we use them anyway.

Losing 1,127 uniforms is bad, because they can be used to impersonate officials. But even if the 1,127 uniforms are found, they can be faked. Can you tell the difference between a legitimate uniform and a decent fake? I can’t.

The real story is the informal nature of most of our real-world authentication systems, and how they can be exploited.

I wrote about this in Beyond Fear (page 199):

Many authentication systems are even more informal. When someone knocks on your door wearing an electric company uniform, you assume she’s there to read the meter. Similarly with deliverymen, service workers, and parking lot attendants. When I return my rental car, I don’t think twice about giving the keys to someone wearing the correct color uniform. And how often do people inspect a police officer’s badge? The potential for intimidation makes this security system even less effective.

Uniforms are easy to fake. In the wee hours of the morning on 18 March 1990, two men entered the Isabella Stuart Gardner Museum in Boston disguised as policemen. They duped the guards, tied them up, and proceeded to steal a dozen paintings by Rembrandt, Vermeer, Manet, and Degas, valued at $300 million. (Thirteen years later, the crime is still unsolved and the art is still missing.) During the Battle of the Bulge in World War II, groups of German commandos operated behind American lines. Dressed as American troops, they tried to deliver false orders to units in an effort to disrupt American plans. Hannibal used the same trick—to greater success—dressing up soldiers who were fluent in Latin in the uniforms of Roman officials and using them to open city gates.

Spies actually take advantage of this authentication problem when recruiting agents. They sometimes recruit a spy by pretending to be working for some third country. For example, a Russian agent working in the U.S. might not be able to convince an American to spy for Russia, but he can pretend to be working for France and might be able to convince the person to spy for that country. This is called “false flag recruitment.” How’s the recruit going to authenticate the nationality of the person he’s spying for?

There’s some fascinating psychology involved in this story. We all authenticate using visual cues, and official uniforms are a big part of that. (When a policeman, or an employee from the local electric company, comes to your door and asks to come in, how to you authenticate him? His uniform and his badge or ID.)

Posted on December 29, 2004 at 8:37 AMView Comments

Phishing by Cell Phone

From an alert reader:

I don’t know whether to tell you, or RISKS, or the cops, but I just received an automated call on my cellphone that asked for the last four digits of my Social Security number. The script went:

Hello! This is not a solicitation! We have an important message for J-O-H-N DOE (my first name was spelled out, but the last name was pronounced). If this is J-O-H-N Doe, Press 1 now!

(after pressing 1:)

For your security, please enter the last four digits of your Social Security Number!

I have no idea who it was, because I’ll be—damned—if I’d give out ANY digits of my SSN to an unidentified party. My cell’s display is broken so I’m not sure whether there was any caller ID information on it, but I also know that can be forged. What company expects its customers to give up critical data like that during an unidentified, unsolicited call?

Sadly, there probably are well-meaning people writing automatic telephone scripts that ask this sort of question. But this could very well be a phishing scheme: someone trying to trick the listener into divulging personal information.

In general, my advice is to not divulge this sort of information when you are called. There’s simply no way to verify who the caller is. Far safer is for you to make the call.

For example, I regularly receive calls from the anti-fraud division of my credit card company checking up on particular charges. I always hang up on them and call them back, using the phone number on the back of my card. That gives me more confidence that I’m speaking to a legitimate representative of my credit card company.

Posted on December 7, 2004 at 1:58 PMView Comments

Hacking Faxes

Prisoner is freed from jail based on a forged fax:

In West Memphis District Court yesterday, Tristian Wilson was set to appear on the docket for a bond hearing on the charges. When he did not appear, Judge William “Pal” Rainey inquired about his release and found that a jail staff member released Wilson by the authority of a fax sent to the jail late Saturday night.

According to Assistant Chief Mike Allen, a fax was sent to the jail which stated “Upon decision between Judge Rainey and the West Memphis Police Department CID Division Tristian Wilson is to be released immediately on this date of October 30, 2004 with a waiver of all fines, bonds and settlements per Judge Rainey and Detective McDugle.”

Jail Administrator Mickey Thornton said that these faxes are part of a normal routine for the jail when it comes to releasing prisoners, however, this fax was different.

Faxes are fascinating. They’re treated like original documents, but lack any of the authentication mechanisms that we’ve developed for original documents: letterheads, watermarks, signatures. Most of the time there’s no problem, but sometimes you can exploit people’s innate trust in faxes to good effect.

Posted on November 8, 2004 at 7:12 AMView Comments

1 24 25 26

Sidebar photo of Bruce Schneier by Joe MacInnis.