Entries Tagged "academic papers"

Page 67 of 80

Non-Randomness in Coin Flipping

It turns out that flipping a coin has all sorts of non-randomness:

Here are the broad strokes of their research:

  1. If the coin is tossed and caught, it has about a 51% chance of landing on the same face it was launched. (If it starts out as heads, there’s a 51% chance it will end as heads).
  2. If the coin is spun, rather than tossed, it can have a much-larger-than-50% chance of ending with the heavier side down. Spun coins can exhibit “huge bias” (some spun coins will fall tails-up 80% of the time).
  3. If the coin is tossed and allowed to clatter to the floor, this probably adds randomness.
  4. If the coin is tossed and allowed to clatter to the floor where it spins, as will sometimes happen, the above spinning bias probably comes into play.
  5. A coin will land on its edge around 1 in 6000 throws, creating a flipistic singularity.
  6. The same initial coin-flipping conditions produce the same coin flip result. That is, there’s a certain amount of determinism to the coin flip.
  7. A more robust coin toss (more revolutions) decreases the bias.

The paper.

Posted on August 24, 2009 at 7:12 AM • View Comments

Modeling Zombie Outbreaks

The math doesn’t look good: “When Zombies Attack!: Mathematical Modelling of an Outbreak of Zombie Infection.”

An outbreak of zombies infecting humans is likely to be disastrous, unless extremely aggressive tactics are employed against the undead. While aggressive quarantine may eradicate the infection, this is unlikely to happen in practice. A cure would only result in some humans surviving the outbreak, although they will still coexist with zombies. Only sufficiently frequent attacks, with increasing force, will result in eradication, assuming the available resources can be mustered in time.

Furthermore, these results assumed that the timescale of the outbreak was short, so that the natural birth and death rates could be ignored. If the timescale of the outbreak increases, then the result is the doomsday scenario: an outbreak of zombies will result in the collapse of civilisation, with every human infected, or dead. This is because human births and deaths will provide the undead with a limitless supply of new bodies to infect, resurrect and convert. Thus, if zombies arrive, we must act quickly and decisively to eradicate them before they eradicate us.

The key difference between the models presented here and other models of infectious disease is that the dead can come back to life. Clearly, this is an unlikely scenario if taken literally, but possible real-life applications may include allegiance to political parties, or diseases with a dormant infection.

This is, perhaps unsurprisingly, the first mathematical analysis of an outbreak of zombie infection. While the scenarios considered are obviously not realistic, it is nevertheless instructive to develop mathematical models for an unusual outbreak. This demonstrates the flexibility of mathematical modelling and shows how modelling can respond to a wide variety of challenges in ‘biology’.

In summary, a zombie outbreak is likely to lead to the collapse of civilisation, unless it is dealt with quickly. While aggressive quarantine may contain the epidemic, or a cure may lead to coexistence of humans and zombies, the most effective way to contain the rise of the undead is to hit hard and hit often. As seen in the movies, it is imperative that zombies are dealt with quickly, or else we are all in a great deal of trouble.

Posted on August 24, 2009 at 5:57 AM • View Comments

Too Many Security Warnings Results in Complacency

Research that proves what we already knew:

Crying Wolf: An Empirical Study of SSL Warning Effectiveness

Abstract. Web users are shown an invalid certificate warning when their browser cannot validate the identity of the websites they are visiting. While these warnings often appear in benign situations, they can also signal a man-in-the-middle attack. We conducted a survey of over 400 Internet users to examine their reactions to and understanding of current SSL warnings. We then designed two new warnings using warnings science principles and lessons learned from the survey. We evaluated warnings used in three popular web browsers and our two warnings in a 100-participant, between-subjects laboratory study. Our warnings performed significantly better than existing warnings, but far too many participants exhibited dangerous behavior in all warning conditions. Our results suggest that, while warnings can be improved, a better approach may be to minimize the use of SSL warnings altogether by blocking users from making unsafe connections and eliminating warnings in benign
situations.

Posted on August 4, 2009 at 10:01 AM • View Comments

Another New AES Attack

A new and very impressive attack against AES has just been announced.

Over the past couple of months, there have been two (the second blogged about here) new cryptanalysis papers on AES. The attacks presented in the papers are not practical—they’re far too complex, they’re related-key attacks, and they’re against larger-key versions and not the 128-bit version that most implementations use—but they are impressive pieces of work all the same.

This new attack, by Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich, and Adi Shamir, is much more devastating. It is a completely practical attack against ten-round AES-256:

Abstract.
AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). In the case of AES-128, there is no known attack which is faster than the 2128 complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2176 and 2119 time, respectively. While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems.

In this paper we describe several attacks which can break with practical complexity variants of AES-256 whose number of rounds are comparable to that of AES-128. One of our attacks uses only two related keys and 239 time to recover the complete 256-bit key of a 9-round version of AES-256 (the best previous attack on this variant required 4 related keys and 2120 time). Another attack can break a 10 round version of AES-256 in 245 time, but it uses a stronger type of related subkey attack (the best previous attack on this variant required 64 related keys and 2172 time).

They also describe an attack against 11-round AES-256 that requires 270 time—almost practical.

These new results greatly improve on the Biryukov, Khovratovich, and Nikolic papers mentioned above, and a paper I wrote with six others in 2000, where we describe a related-key attack against 9-round AES-256 (then called Rijndael) in 2224 time. (This again proves the cryptographer’s adage: attacks always get better, they never get worse.)

By any definition of the term, this is a huge result.

There are three reasons not to panic:

  • The attack exploits the fact that the key schedule for 256-bit version is pretty lousy—something we pointed out in our 2000 paper—but doesn’t extend to AES with a 128-bit key.
  • It’s a related-key attack, which requires the cryptanalyst to have access to plaintexts encrypted with multiple keys that are related in a specific way.
  • The attack only breaks 11 rounds of AES-256. Full AES-256 has 14 rounds.

Not much comfort there, I agree. But it’s what we have.

Cryptography is all about safety margins. If you can break n round of a cipher, you design it with 2n or 3n rounds. What we’re learning is that the safety margin of AES is much less than previously believed. And while there is no reason to scrap AES in favor of another algorithm, NST should increase the number of rounds of all three AES variants. At this point, I suggest AES-128 at 16 rounds, AES-192 at 20 rounds, and AES-256 at 28 rounds. Or maybe even more; we don’t want to be revising the standard again and again.

And for new applications I suggest that people don’t use AES-256. AES-128 provides more than enough security margin for the forseeable future. But if you’re already using AES-256, there’s no reason to change.

The paper I have is still a draft. It is being circulated among cryptographers, and should be online in a couple of days. I will post the link as soon as I have it.

UPDATED TO ADD (8/3): The paper is public.

Posted on July 30, 2009 at 9:26 AM • View Comments

Social Security Numbers are Not Random

Social Security Numbers are not random. In some cases, you can predict them with date and place of birth.

Abstract:

Information about an individual’s place and date of birth can be exploited to predict his or her Social Security number (SSN). Using only publicly available information, we observed a correlation between individuals’ SSNs and their birth data and found that for younger cohorts the correlation allows statistical inference of private SSNs. The inferences are made possible by the public availability of the Social Security Administration’s Death Master File and the widespread accessibility of personal information from multiple sources, such as data brokers or profiles on social networking sites. Our results highlight the unexpected privacy consequences of the complex interactions among multiple data sources in modern information economies and quantify privacy risks associated with information revelation in public forums.

Full paper, and FAQ.

I don’t see any new insecurities here. We already know that Social Security Numbers are not secrets. And anyone who wants to steal a million SSNs is much more likely to break into one of the gazillion databases out there that store them.

Posted on July 24, 2009 at 10:36 AM • View Comments

Mapping Drug Use by Testing Sewer Water

I wrote about this in 2007, but there’s new research:

Scientists from Oregon State University, the University of Washington and McGill University partnered with city workers in 96 communities, including Pendleton, Hermiston and Umatilla, to gather samples on one day, March 4, 2008. The scientists then tested the samples for evidence of methamphetamine, cocaine and ecstasy, or MDMA.

Addiction specialists were not surprised by the researchers’ central discovery, that every one of the 96 cities—representing 65 percent of Oregon’s population—had a quantifiable level of methamphetamine in its wastewater.

“This validates what we suspected about methamphetamine use in Oregon,” said Geralyn Brennan, addiction prevention epidemiologist for the Department of Human Services.

Drug researchers previously determined the extent of illicit drug use through mortality records and random surveys, which are not considered entirely reliable. Survey respondents may not accurately recall how much or how often they use illicit drugs and they may not be willing to tell the truth. Surveys also gathered information about large regions of the state, not individual cities.

The data gathered from municipal wastewater, however, are concrete and reveal a detailed snapshot of drug use for that day. Researchers placed cities into ranks based on a drug’s “index load” – average milligrams per person per day.

These techniques can detect drug usage at individual houses. It’s just a matter of where you take your samples.

Posted on July 23, 2009 at 6:09 AM • View Comments

Cybercrime Paper

“Distributed Security: A New Model of Law Enforcement,” Susan W. Brenner and Leo L. Clarke.

Abstract:
Cybercrime, which is rapidly increasing in frequency and in severity, requires us to rethink how we should enforce our criminal laws. The current model of reactive, police-based enforcement, with its origins in real-world urbanization, does not and cannot protect society from criminals using computer technology. This article proposes a new model of distributed security that can supplement the traditional model and allow us to deal effectively with cybercrime. The new model employs criminal sanctions, primarily fines, to induce computer users and those who provide access to cyberspace to employ reasonable security measures as deterrents. We argue that criminal sanctions are preferable in this context to civil liability, and we suggest a system of administrative regulation backed by criminal sanctions that will provide the incentives necessary to create a workable deterrent to cybercrime.

It’s from 2005, but I’ve never seen it before.

Posted on July 20, 2009 at 6:43 AM • View Comments

Privacy Salience and Social Networking Sites

Reassuring people about privacy makes them more, not less, concerned. It’s called “privacy salience,” and Leslie John, Alessandro Acquisti, and George Loewenstein—all at Carnegie Mellon University—demonstrated this in a series of clever experiments. In one, subjects completed an online survey consisting of a series of questions about their academic behavior—”Have you ever cheated on an exam?” for example. Half of the subjects were first required to sign a consent warning—designed to make privacy concerns more salient—while the other half did not. Also, subjects were randomly assigned to receive either a privacy confidentiality assurance, or no such assurance. When the privacy concern was made salient (through the consent warning), people reacted negatively to the subsequent confidentiality assurance and were less likely to reveal personal information.

In another experiment, subjects completed an online survey where they were asked a series of personal questions, such as “Have you ever tried cocaine?” Half of the subjects completed a frivolous-looking survey—”How BAD are U??”—with a picture of a cute devil. The other half completed the same survey with the title “Carnegie Mellon University Survey of Ethical Standards,” complete with a university seal and official privacy assurances. The results showed that people who were reminded about privacy were less likely to reveal personal information than those who were not.

Privacy salience does a lot to explain social networking sites and their attitudes towards privacy. From a business perspective, social networking sites don’t want their members to exercise their privacy rights very much. They want members to be comfortable disclosing a lot of data about themselves.

Joseph Bonneau and Soeren Preibusch of Cambridge University have been studying privacy on 45 popular social networking sites around the world. (You may not have realized that there are 45 popular social networking sites around the world.) They found that privacy settings were often confusing and hard to access; Facebook, with its 61 privacy settings, is the worst. To understand some of the settings, they had to create accounts with different settings so they could compare the results. Privacy tends to increase with the age and popularity of a site. General-use sites tend to have more privacy features than niche sites.

But their most interesting finding was that sites consistently hide any mentions of privacy. Their splash pages talk about connecting with friends, meeting new people, sharing pictures: the benefits of disclosing personal data.

These sites do talk about privacy, but only on hard-to-find privacy policy pages. There, the sites give strong reassurances about their privacy controls and the safety of data members choose to disclose on the site. There, the sites display third-party privacy seals and other icons designed to assuage any fears members have.

It’s the Carnegie Mellon experimental result in the real world. Users care about privacy, but don’t really think about it day to day. The social networking sites don’t want to remind users about privacy, even if they talk about it positively, because any reminder will result in users remembering their privacy fears and becoming more cautious about sharing personal data. But the sites also need to reassure those “privacy fundamentalists” for whom privacy is always salient, so they have very strong pro-privacy rhetoric for those who take the time to search them out. The two different marketing messages are for two different audiences.

Social networking sites are improving their privacy controls as a result of public pressure. At the same time, there is a counterbalancing business pressure to decrease privacy; watch what’s going on right now on Facebook, for example. Naively, we should expect companies to make their privacy policies clear to allow customers to make an informed choice. But the marketing need to reduce privacy salience will frustrate market solutions to improve privacy; sites would much rather obfuscate the issue than compete on it as a feature.

This essay originally appeared in the Guardian.

Posted on July 16, 2009 at 6:05 AM • View Comments

Strong Web Passwords

Interesting paper from HotSec ’07: “Do Strong Web Passwords Accomplish Anything?” by Dinei Florêncio, Cormac Herley, and Baris Coskun.

ABSTRACT: We find that traditional password advice given to users is somewhat dated. Strong passwords do nothing to protect online users from password stealing attacks such as phishing and keylogging, and yet they place considerable burden on users. Passwords that are too weak of course invite brute-force attacks. However, we find that relatively weak passwords, about 20 bits or so, are sufficient to make brute-force attacks on a single account unrealistic so long as a “three strikes” type rule is in place. Above that minimum it appears that increasing password strength does little to address any real threat If a larger credential space is needed it appears better to increase the strength of the user ID’s rather than the passwords. For large institutions this is just as effective in deterring bulk guessing attacks and is a great deal better for users. For small institutions there appears little reason to require strong passwords for online accounts.

Posted on July 13, 2009 at 5:38 AM • View Comments

Homomorphic Encryption Breakthrough

Last month, IBM made some pretty brash claims about homomorphic encryption and the future of security. I hate to be the one to throw cold water on the whole thing—as cool as the new discovery is—but it’s important to separate the theoretical from the practical.

Homomorphic cryptosystems are ones where mathematical operations on the ciphertext have regular effects on the plaintext. A normal symmetric cipher—DES, AES, or whatever—is not homomorphic. Assume you have a plaintext P, and you encrypt it with AES to get a corresponding ciphertext C. If you multiply that ciphertext by 2, and then decrypt 2C, you get random gibberish instead of P. If you got something else, like 2P, that would imply some pretty strong nonrandomness properties of AES and no one would trust its security.

The RSA algorithm is different. Encrypt P to get C, multiply C by 2, and then decrypt 2C—and you get 2P. That’s a homomorphism: perform some mathematical operation to the ciphertext, and that operation is reflected in the plaintext. The RSA algorithm is homomorphic with respect to multiplication, something that has to be taken into account when evaluating the security of a security system that uses RSA.

This isn’t anything new. RSA’s homomorphism was known in the 1970s, and other algorithms that are homomorphic with respect to addition have been known since the 1980s. But what has eluded cryptographers is a fully homomorphic cryptosystem: one that is homomorphic under both addition and multiplication and yet still secure. And that’s what IBM researcher Craig Gentry has discovered.

This is a bigger deal than might appear at first glance. Any computation can be expressed as a Boolean circuit: a series of additions and multiplications. Your computer consists of a zillion Boolean circuits, and you can run programs to do anything on your computer. This algorithm means you can perform arbitrary computations on homomorphically encrypted data. More concretely: if you encrypt data in a fully homomorphic cryptosystem, you can ship that encrypted data to an untrusted person and that person can perform arbitrary computations on that data without being able to decrypt the data itself. Imagine what that would mean for cloud computing, or any outsourcing infrastructure: you no longer have to trust the outsourcer with the data.

Unfortunately—you knew that was coming, right?—Gentry’s scheme is completely impractical. It uses something called an ideal lattice as the basis for the encryption scheme, and both the size of the ciphertext and the complexity of the encryption and decryption operations grow enormously with the number of operations you need to perform on the ciphertext—and that number needs to be fixed in advance. And converting a computer program, even a simple one, into a Boolean circuit requires an enormous number of operations. These aren’t impracticalities that can be solved with some clever optimization techniques and a few turns of Moore’s Law; this is an inherent limitation in the algorithm. In one article, Gentry estimates that performing a Google search with encrypted keywords—a perfectly reasonable simple application of this algorithm—would increase the amount of computing time by about a trillion. Moore’s law calculates that it would be 40 years before that homomorphic search would be as efficient as a search today, and I think he’s being optimistic with even this most simple of examples.

Despite this, IBM’s PR machine has been in overdrive about the discovery. Its press release makes it sound like this new homomorphic scheme is going to rewrite the business of computing: not just cloud computing, but “enabling filters to identify spam, even in encrypted email, or protection information contained in electronic medical records.” Maybe someday, but not in my lifetime.

This is not to take anything away anything from Gentry or his discovery. Visions of a fully homomorphic cryptosystem have been dancing in cryptographers’ heads for thirty years. I never expected to see one. It will be years before a sufficient number of cryptographers examine the algorithm that we can have any confidence that the scheme is secure, but—practicality be damned—this is an amazing piece of work.

Posted on July 9, 2009 at 6:36 AM • View Comments

1 … 65 66 67 68 69 … 80

Sidebar photo of Bruce Schneier by Joe MacInnis.