The Sub-Time Crisis in Web 2.0

A few months ago I came across Steve Rubel's post on Attention Crash, where he predicts an imminent bursting of the Web 2.0 information bubble since there is no Moore's Law of exponential growth for our attention. This was a provocative remark, which I worked through more thoroughly in Moore's Lore and Attention Crash. Actually, I spent a few days off my laptop scribbling down various ideas and observations on paper, whatever came to mind. I surprised myself with filling 12 pages in a few hours on a Sunday afternoon and a few train rides. Some of the smaller asides will find their way into other posts, like the The Restaurant at the End of the Web. Here I will continue with the Attention Crash theme.

The worst case scenario for Web 2.0 is that we are heading for a singularity, precipitated by dividing our attention into informational units effectively rated at zero content. Using available streaming and aggregation tools we can quickly and effortlessly create an overwhelming flood of information. It is clear that we are building social computing structures that we do not comprehend. Social computing joins two areas that have the potential for massive scaling - computing technology and social interaction. The Sub-Time crisis lies at this intersection. In fact it is the intersection.

After reading Rubel's original post I subscribed to his blog and even his FriendFeed, and soon found that while he is concerned about Attention Crash, he is also a major contributor to the pot of Web 2.0 tidbits (links, comments, posts, pictures and so on). He is typical of other Web 2.0 luminaries who produce content but then also produce “content” on there being too much content.

But is there really a coming Attention Crash? Well certainly not informational equivalents to the Great Crash of 1929 or the Subprime crisis we are currently experiencing. If there is such a thing it will be very unevenly distributed and localised. It is clear that certain people are going to get rain on their personal web parades, but this is not global deluge.

When I was a boy my father regularly asked me “stimulating” questions. He belonged to the generation of Australian men for whom intense argument over inconsequential matters was considered both relaxing and invigorating. Apart from the perennial favourite of "How long is a piece of string?", usually recounted when someone asked how much does a reasonable quality car cost (I come from a long line of car people), and "Did you know you can sink a tractor in a lake of average depth of 1 inch?", he did ask me one time "What is the difference between a crash and a collision?" And the answer is that a collision involves two moving objects (say two cars) while a crash involves one moving object and one stationary object (say a car hitting a tree).

So when we speak of Attention Crash we may think of our information intake hitting up against our stationary capacity to absorb it. This capacity varies from person to person, but there are always hard bounds.

But as with the Great Crash, Rubel is probably using Attention Crash to mean a general or systemic collapse - an event that is widespread, foundational and severe. But the coming Attention Crash will not be of this form - there will be enough localised warnings. Unlike our current financial structures, the web is not at threat of collapsing, though many foot soldiers will fall by the way (they see themselves as pioneers, but in fact they are easily replaced). Our informational structures are not hierarchical but relational, and as such, are much more resilient to the removal of individuals. It is not the case that there are eager underlings waiting to replace leaders – the underlings are here and functioning already.

Web 2.0 losses will largely go unnoticed. New users/readers, whose information experience begins today, are being added constantly. They are essentially unaware of what happened last month and will remain that way. Joining is not a generational wait, no corporate ladder to be climbed. Everyone joins and progresses simultaneously. This turnover goes largely unnoticed since leavers are dwarfed by joiners.

Returning to Rubel, his tips on handling Web 2.0 overload are not very helpful - know what you want, be selective, apply the same ruthlessness that you do to your inbox. In short, organise your way out of the Web 2.0 glut. But this advice is nothing much more than platitudes. If at some point you used to receive 20 emails a day, whatever method you used to process those messages is probably not going to help you when you start receiving 50, 100 or 200 emails a day. But perhaps we are not really talking about scale here. If you buy a car for 4 people and then try to transport 50, this is not a matter of scale but just simply miscalculation.

The tools we have are simply the wrong ones. But ironically we seem to rely on web 2.0 to solve the problem it has created. This is surely like hoping that the fast food industry will take steps to help their customers lose weight. The point is that we face a disinterested informational adversary, that for the foreseeable future operates in a scale-free environment. In the information battle we have some sharp spears with occasional impressive horseback riding. However our adversary has the power to create a data mushroom cloud. Your best fallout shelter is abstinence.

Rethinking Thresholds for Account Lockouts

One of my colleagues informed me that Conficker caused quite a few password lockout of administrator accounts at his company. The worm used a list of about 200 strings to perform a quick password-guessing attack on privileged accounts. Unless an account had no lockout policy set, then such accounts would be either compromised or locked out by Conficker. We can add DoS to the list of Conficker achievements.

But its not just Conficker that is locking users out of their accounts – in fact, users can do that all by themselves. We all know that quite a few help desk calls are simply requests for password resets of infrequently used applications, or even for frequently used applications where our recall has inexplicably failed us. NetWrix estimates that 30% of all help desk calls are for password resets. One is tempted to think that security policy is more concerned with keeping help desk people occupied than realistically addressing password guessing attacks.

Automatic account lockout is a counter-measure (or control in modern security parlance) for detecting and preventing password guessing attacks. Setting the account lockout threshold to be a small number such as 3 or 5 attempts is part of the conventional wisdom of security. The less number of permitted password guessing attempts the better. But we need to strike some balance here between our own unreliable memories and the persistence of hackers.

As is often the case, a little notation will help the discussion. Let’s assume that a policy defines N possible passwords, which we may represent as

A given user U will select these passwords according their personal preferences, and let the probability distribution

denote these preferences. Lastly let’s assume for simplicity that the passwords are ordered such that

which just means that password P1 is the mostly likely choice of the user with probability p1, password P2 is the next most likely choice with probability p2, and so on.

Now if we have a 3-strikes-you’re-out lockout policy then what does this mean in terms of our probabilities? Well, assuming the attacker follows the preferences of the user, then the policy states that we are prepared to live with three password guesses with a success of

but not with four password guesses with a success of

So the critical value here is p4 since it tips the scale from what is acceptable to what is not acceptable. We can represent this state of affairs in the diagram below.

But are our password policies really so brittle that we cross a security threshold from allowing 3 to 4 password guesses? I don’t think so. There is a threshold but it is certainly higher than 3 guesses.

I recently blogged about the approach taken by NIST to this issue. Their formulation of the problem was to find the smallest value of M for which

which leads to the following graph

That is, the NIST approach is to tolerate M password guesses as long as the likelihood of success is less than the threshold 2^{-k}. The particular values chosen for NIST were k = 10 (1 in 1,000) and k = 14 (1 in 16,000), depending on the desired level of security. It is challenging to compute the exact value of M but NIST has some estimates based on deploying policies which guarantee a minimum amount of entropy in user passwords (see Appendix 1 of this document).

AES-256 and Reputational Risk

Reputational risk is something that everyone understands, particularly businesses who regard their brand as one of their most critical assets. As there is considerable trust in the security of AES-256 both in the public and commercial sectors, reputational risk to AES-256 has a very high impact, and we therefore hope, a very low likelihood of occurrence.

But I will argue in this post that the likelihood of reputational damage to AES-256 is far from low, and perhaps even quite high. AES-256 keys are so large that it is next to impossible to argue that a cryptanalyst will not be able to find some shortcut to recovering keys that saves time over exhaustive search – simply because the cryptanalyst has so much time to play with.

For example, an attack that requires 2^{200} operations is a “huge” saving over the 2^{255} operations for a full exhaustive search of a 256-bit key space. But is a cryptanalyst with a computational arsenal of 2^{200} operations any more of a credible threat than one armed with 2^{255} operations? I think not. But the 2^{200} attack will seem quite menacing since it “saved” a massive 2^{55} operations, and there will be reputational damage to AES-256.

In short 256-bit keys are simply not defensible within the framework of traditional notions of security. I have been intending to post on this topic for sometime, and thanks to Eric Rescorla’s post for prompting me to action.

Let's start by talking about absolute and relative breaks on ciphers. Absolute breaks (like the name suggests) signal the end-of-life for a cipher, while relative breaks signal improvements over exhaustive search. Reputational risk for a cipher starts gaining momentum in the latter case.

Absolute Breaks

By an absolute break we mean, for a family of ciphers or for a cipher at a given key length, a known method to efficiently recover keys. We can measure efficiency in several ways. RSA, like other public key systems, represents a family of ciphers since key generation can be scaled to an arbitrary size. RSA keys can have lengths of 512, 1024 or 2048 bits, and even larger lengths in principle. In practice computational cost is the limiting factor that prevents public keys from becoming arbitrarily large. So to break a public key cipher in some absolute sense we require an attack that works efficiently for all potential key sizes. Or put anther way, an absolute break prevents the cipher designer from simply escaping the attack by increasing the key length.

Many of the early public key systems based on the knapsack problem (including the famous Merkle-Hellman system) were broken efficiently for all key sizes by applying the LLL basis reduction algorithm (you can read a detailed history here). Knapsack ciphers have essentially disappeared from the cryptographic landscape, as their reputation has been damaged beyond repair. Another example of an absolute break is Shor's algorithm, which assuming a large scale quantum computer, can factor an RSA N-bit modulus in time proportional to N^3 operations. Since doing an RSA decryption today requires N^3 bit operations we can say that Shor's algorithm breaks RSA in time proportional to what it costs to setup up an SSL session today. Now we may be very far away from having quantum computers, but even the remote threat of such a device has caused enduring reputational damage for popular public key ciphers in use today.

Absolute Breaks for Symmetric Ciphers

The other way to demonstrate an absolute break of a cipher is to show that a fixed key of a given length can be recovered in a short amount of elapsed time. So the 56-bit key length of DES was conclusively shown to be too short in 1998 by the EFF DES Cracker device which demonstrated key recovery in 56 hours (a bit an hour!). When we have a symmetric key cipher with a fixed key length, then this is what an absolute attack usually means – key recovery in a few weeks or months (or even days) when the expected time was thousands of years. When such an attack is successful the cipher is deemed broken or we must move to a variant, or an entirely new cipher with a longer key length.

Relative Breaks

Well-designed ciphers will typically not succumb to absolute breaks (barring a breakthrough attack), but even the best ciphers have some blemishes which reduce the effort of brute forcing key recovery. By a relative break we mean an attack which is faster than exhaustive search of the key space (the set of all possible keys), but not does break the cipher in any absolute sense. Relative breaks show that the implied margin of security for the key length is not as large as we thought. But what is the implied margin of security?

When a symmetric key cipher has a key length of n bits this is interpreted to mean that, in the absence of any weaknesses, the security of the cipher is proportional to the cost of a brute force attack on a key space of size 2^{n}. That is, a needle-in-a-haystack search problem where there are of 2^{n} pieces of hay. In the worst case an attacker will have to try all possible keys to find the right one (he guesses the right key last) but on average he will need only examine half the possible keys since

So we lose one bit of security from the key length in the average case of exhaustive search. Many attacks on symmetric ciphers are of the relative type, identifying a weakness which can be translated into some computational saving over exhaustive search. Let's translate the saving into R bits over the average case of exhaustive search

The question here is how large should R be before we think a relative attack is worth worrying about?

In the case of DES the complementary property gave us R = 1 for free. In the 70's, when DES was essentially the only commercial cipher in town, shaving off just a few bits was significant. This was true because many people thought that a 56-bit key was already teetering on the brink of feasible recovery, and saving a few more bits would definitely tip the scale towards an absolute break. But while saving say 5 bits for DES was significant, the same 5 bits of cryptanalytic advantage means less for a 128-bit cipher and practically nothing for AES-256. Nothing more than a mosquito hitting a bullet train.

Relative breaks can point to small cracks in the design of a cipher which can potentially be developed into absolute breaks. This is what we are now seeing with SHA-1 where the idea behind an initial saving in the cost of finding collisions of just a few bits has been developed into serious attacks. The relative is on the verge of being converted to the absolute.

This is the period of reputational damage for a cipher, since for a given relative attack we cannot be certain if it will be converted into an absolute break over time. In February last year a new attack on the 64-bit key space of the A5/1 cipher used in GSM devices was announced, with some fanfare, at a Black Hat conference. The attack claimed to provide a relative break by pre-computing a special “rainbow table” of size 2^{58}, but the promised details have yet to materialize.

Relative breaks for AES-256

Let us now turn specifically to AES-256. AES-256 should be secure against an attacker who has materially less than 2^{255} = 10^{76} resources at their disposal. Since 10^{76} is to within a few powers of 10 of the estimated number of atoms in the known universe, then it is essentially impossible for AES-256 to succumb to pure computational attacks on its key space.

So ruling out absolute breaks (in the absence of discovering a major weakness in AES), this only leaves relative breaks for consideration. Again, how big should the relative computational saving R be before we have a serious or material relative break?

Well let’s be generous and assume that when R = 55 we have a material relative break. This means that the cryptanalyst has saved a computational effort on the order of recovering a DES key. With this saving the cryptanalyst still has 2^{255-55} = 2^{200} resources at their disposal to break an AES-256 key.

You could read the headlines now “AES-256 Broken - researcher knocks off 17 zeroes from exhaustive search”, where 2^{55} is approximately 10^{17}. But would this result really imply a meaningful threat? All that has been done is change an absolutely absurd large computational task to a slightly less absurdly large computational task.

We are ceding too much to the cryptanalyst here by a giving them a massive 2^{200} sandbox for toying around with how to break AES-256. Every scrap of current computing power in the world running for a year would amount to less than 2^{100} operations and we are postulating that our cryptanalyst has access to 2^{100} times that power, or 10^{29} centuries of continuous computation at current rates.

Something is wrong here in the analysis – no one will have 2^200 resources up their sleeve. The problem with a 256-bit key is that it can shed 55 bits and still lose no real effective security. So the reputational risk is that someone emerges from this sandbox with a 2^{200}-idea that has credence.

Managing the reputation of AES-256

Google Trends is a service which estimates search and news activity for a given keyword. For “AES 256” the graph below was produced

It is evident that there has been a considerable increase in search and news activity since 2007. The letters in the upper graph are links to news stories, which are mainly product announcements for AES-256 support. Vendors are certainly adopting AES-256, and in a previous post I wrote that

… AES-256 is being widely deployed since it conveniently lies at the intersection of good marketing and pragmatic security. In upgrading from AES-128 to AES-256 vendors can legitimately claim that their products use maximum strength cryptography, and key lengths can be doubled (thus squaring the effort for brute force attacks) for a modest 40% performance hit.

However the only possible security threat which would warrant the deployment of 256-bits keys is the existence of large scale quantum computing devices. If this were the case then there is a quantum algorithm that effectively reduces the key space to 128-bits. But if this is the case, then we will be living in a very different world from the one we inhabit now.

Imagine you posed the following question to a group of top physicists. You asked them to present you with ideas for new research projects where they could assume that the budget included all the money that we have, all the money that has ever been, and the total financial assets of the world for the next 10 million years. Would the resulting proposals be credible?

AES-256 puts cryptanalysts on the same research agenda.

Related Posts

• Are AES 256-bit keys too large?
• The Spin on AES Passwords

Password Roundup #2

Password issues remain a regular item in security news over the last few weeks. In this roundup I report on the fruits of password harvesting, a new policy from NIST, a kerfuffle between Elcomsoft and PGP, and lastly, how to pass the hash.

Unveiling Selma Hayek

Graham Cluely reported that the public email account of Selma Hayek was hacked, leading to screen shots of her messages being published along with other private details. Allegedly the hack was achieved by resetting her password after “guessing” her date of birth and the name of her most famous film role. Not exactly examples of “high entropy” information.

Fruits of the Password Harvest

Techradar reports on the exposure of The Great Password Scandal. The incident involved a site called My Name is E that lured new users with the promise to integrate multiple social networks if they handed over enough passwords. And people did, spurred by recommendations from Twitter. But these tweets were actually authored by My Name is E using harvested Twitter passwords via the autotweet function acting as a viral marketing vector. The lead developer from My Name is E claims that this was a development feature which was mistakenly left activated in the production version of the site.

A precedent is being established by well-known social networking sites to request people to supply their email username and password so that their contacts may be automatically added as friends. Sites following this approach include Get Satisfaction, Linked In, Yelp, Plaxo, Ning, FriendFeed, Orkut, iLike, MySpace and Facebook. Users are being sent the message that it’s ok to handover these credentials to simplify your social networking experience. Both Twitter and My Name is E know that OAuth is a better solution but they are not quite there yet. Joining up the social fabric web 2.0 still trumps security.

Some large scale harvesting was also reported by researchers from the University of California Santa Barbara, who infiltrated a botnet for 10 days earlier this year. The researchers have just published a paper on their findings where they report that they were able to access 70 GB of harvested data which included a massive 56,000 passwords.

NIST Password Policies

NIST has released a new draft document called Guide to Enterprise Password Management, SP 800-118. The 38-page document ¨provides recommendations for password management, which is the process of defining, implementing, and maintaining password policies throughout an enterprise. Effective password management reduces the risk of compromise of password-based authentication systems”. You can read a brief review of the document here.

Still with NIST, I recently blogged about their approach to making passwords harder to guess by using entropy arguments. At the E-Authentication site you can download a spreadsheet for calculating the entropy of explicit policies (as well as a few other interesting tools and documents).

The Elcomsoft and PGP Kerfuffle

The Register reported an incident at the recent InfoSec 2009 conference where an Elcomsoft poster with the by-line "the only way to break into PGP" was removed as a result of an official complaint lodged by PGP. Unfortunately the PGP and Elcomsoft vendor stands were facing each other in the exhibit hall. "The sign was factually inaccurate and lies about PGP," said Jon Callas, CTO of PGP. "They're not breaking into PGP, they're doing password cracking. There's a difference”. But naturally, if a password is protecting your PGP private key, then their protection is no stronger than a password. You can read more about he incident (and see the offending poster) on the Elcomsoft blog.

Pass the Hash

At the RSA 2009 conference the Register asked two security experts to rate the world’s most dangerous exploits. Near the top of the list for Ed Skoudis, a well-known security practitioner and author, was a powerful exploit that has evolved from an old attack known as pass the hash. Attackers exploit an unpatched browser or application vulnerability to capture a Windows password hash and then use it to create a valid login session on another machine with someone else’s password (for Windows only the hash of the password is required, not the password itself). For the attack to be successful the hash must be injected into memory and you can read about the details in this post from Marcus Murray.

Related Posts

• Password Roundup #1
• NIST, Passwords and Entropy
• The Spin on AES Passwords
• Counting Restricted Password Spaces

The Half-life of Vulnerabilities is still 30 Days

Wolfgang Kandek, CTO of Qualys, recently gave an update on the Laws of Vulnerabilities research that Qualys initiated in 2004. Based on scanning 3 million IP addresses, and considering 2 million vulnerabilities, the initial results found that the half-life of unpatched vulnerabilities was 30 days. That is, the observed rate of patching halved the number of open vulnerabilities each month.

Kandek repeated this exercise on a grander scale in 2008, scanning 80 million IP addresses for over 870 million vulnerabilities, including 72 million that were critical. The data confirmed that the vulnerability half-life was 29.5 days, essentially unchanged from the initial finding 4 years before. This was an average taken over several 5 industry sectors, where the service sector had the lowest half-life at 21 days and the manufacturing sector had the highest at 51 days. The health sector weighed in at 38 days. Topping the list of the chronically under-patched were MS Office, Windows 2003 SP2, the Sun Java Plugin and Adobe Acrobat.

While the average half-life has remained essentially constant over the last 4 years, Kandek notes that the time from discovery to exploiting a vulnerability is going down. Qualys is aware of 56 zero-day exploits, and the availability of exploits is now measured in single digit days. Even though the half-life measure suggests that a given set of vulnerabilities will rapidly become “extinct”, in practice their threat lives on indefinitely since most vulnerabilities are never fully patched. Further, this patching rate is offset by a 60% replacement rate by new vulnerabilities.

Kandek concludes that

“Security is getting more difficult with attackers becoming extremely sophisticated and the window of exploitation shrinking to days for most critical vulnerabilities … Our goal with this research is to help organizations across different industries understand the broader trends, the potential for damage and the priority of vulnerabilities, so they can make more effective and more immediate decisions to protect their networks. With research like that outlined in the Laws of Vulnerabilities 2.0, we can provide the industry with a statistical look at threat trends in real-time."

Also, take a look at some recent advice from Tenable Security on how to read vulnerability reports, which will help you interpret Kandek's charts.

Total Internet computational power = 2^{85} operations per year?

I am currently reading the ECRYPT Yearly Report on Algorithms and Keysizes for 2007-08, the last report in this European project started in 2004. The list of authors includes many well-known and respected cryptographers.

A remark on page 14 caught my eye:

In [55] it is estimated that the total computational power of the Internet is about 2^{85} operations per year.

Reference [55] is to another ECRYPT document that mentions the 2^{85} figure without justification or further reference.

Does anyone have any evidence that this 2^{85} figure is true or even approximately correct?

The $28,000 Question: Project vs. Production Risk

The average cost of an American wedding in 2007 was $28,000. Jeremiah Grossman recently posted that for the same money you could fix the critical vulnerabilities lurking at your website.

In his experience the average number of serious flaws per website is 7, each of which will take an average of 40 hours to fix - confirmed by 1000-strong Twitter poll. Then assuming a programming cost of $100/hour you arrive at the figure of

$28,000 = 7 x 40 x $100

in “outstanding insecure software debt” per website. Of course there will be sites that are in much worse shape. As Grossman observes, this figure is not very high, and he asks whether this estimate really supports the implementation of a costly secure software development life cycle ?

I think that the key point here is to distinguish between project risks and production risks. A project manager (PM) is concerned naturally with project risks, whose impact can be broadly classified as increased costs, delivery delays and reduced functionality. If we express a risk as a threat, vulnerability and an impact, then for the PM impacts reduce to cost overruns, time overruns and functionality “underruns” (plus combinations thereof). In general, expending time and resources to identify and fix potential security vulnerabilities is not effective in the PM’s risk model, since the vulnerabilities are unlikely to impact required functionality. Software with significant security vulnerabilities may function perfectly well, right up to, and including, the point of exploitation. As such, security vulnerabilities are not high on the risk radar of the PM.

When we move to the production risk model then potential impacts change dramatically, which for web applications, Grossman lists as

… down time, financial fraud, loss of visitor traffic and sales when search engines blacklist the site, recovery efforts, increased support call volume, FTC and payment card industry fines, headlines tarnishing trust in the brand, and so on are typical. Of course this assumes the organization survives at all, which has not always been the case.

The “meaningful” impact costs are therefore situated in the production risk model rather than the project risk model. A source of misunderstanding (and possibly friction) between security and project people is the difference in risk models or outlooks, since most security people assume the view of production risks – it is their role in fact. When Marcus Ranum recently remarked

I don’t know a single senior security practitioner who has not, at some point or other, had to defend an estimated likelihood of a bad thing happening against an estimated business benefit.

I believe that he was talking about the dichotomy between project and production risk. So returning the Grossman’s original issue, the $28,000 to fix web vulnerabilities does not support the deployment of a secure SDL in the project risk model, but it makes much better sense in the production risk model.

Related Posts

• The Relegation of Security to NFR Status
• Marcus Ranum and the Points of No Return

The cost of SHA-1 collisions reduced to 2^{52}

Australian researchers Cameron McDonald, Philip Hawkes and Josef Pieprzyk have announced a new attack to find collisions in SHA-1 requiring only 2^{52} operations. This new result decreases the cost of a collision attack by a factor of over 2000 as compared to previous methods. The researchers note that “practical collisions are within resources of a well funded organisation”.

SHA-1 produces a 160-bit output, which according to the birthday paradox, implies that a collision attack should require approximately 2^{80} operations to succeed. However in early 2005, three Chinese researchers announced a collision attack on SHA-1 that required only 2^{69} operations. Since then a series of cryptanalytic results has weakened confidence in the strength of SHA-1 and other hash functions in the SHA family. The new attack builds on these previous results.

The 2^{52} announcement came at the informal session of the Eurocrypt 2009 conference, where works-in-progress and results completed too late for submission are discussed. The full details of the attack will be published in due course on the eprint service of the IACR.

On a personal note, Phil Hawkes was my first (and perhaps only) PhD student. He is a gifted mathematician and I am very glad to see him producing world class research results. My thanks to Eric Rescorla for posting this result on his blog.

Related Posts

• Weapons of Math Instruction: The Birthday Paradox

“One Way Hash” Arguments

Julian Sanchez has made an excellent post on Climate Change argument fallacies where he coins the term “one way hash” arguments. The context of the post is a discussion about the difficulties of refuting false arguments concerning the state of climate change (the politically correct term for global warming), in particular, the difficulties of lay people to understand the arguments of specialists.

Sometimes the arguments are such that the specialists can develop and summarize them to the point that an intelligent layman can evaluate them. But often—and I feel pretty sure here—that’s just not the case. Give me a topic I know fairly intimately, and I can often make a convincing case … I need only worry about what sounds plausible. If my opponent is trying to explain what’s true, he may be constrained to introduce concepts that take a while to explain and are hard to follow, trying the patience (and perhaps wounding the ego) of the audience.

from which he concludes that

… there’s a certain class of rhetoric I’m going to call the “one way hash” argument. Most modern cryptographic systems in wide use are based on a certain mathematical asymmetry: You can multiply a couple of large prime numbers much (much, much, much, much) more quickly than you can factor the product back into primes. A one-way hash is a kind of “fingerprint” for messages based on the same mathematical idea: It’s really easy to run the algorithm in one direction, but much harder and more time consuming to undo. Certain bad arguments work the same way—skim online debates between biologists and earnest ID aficionados armed with talking points if you want a few examples: The talking point on one side is just complex enough that it’s both intelligible—even somewhat intuitive—to the layman and sounds as though it might qualify as some kind of insight. … The rebuttal, by contrast, may require explaining a whole series of preliminary concepts before it’s really possible to explain why the talking point is wrong. So the setup is “snappy, intuitively appealing argument without obvious problems” vs. “rebuttal I probably don’t have time to read, let alone analyze closely.”

I found a link to Sanchez’s analysis in a post by Eric Rescorla, who was correcting Sanchez, somewhat pedantically, on the point that hash functions aren’t based on factoring. Sanchez defended himself by stating that he was constructing a metaphor not giving a cryptography lesson.

In any case, crypto nitpicks aside, I like the metaphor, as did others in the comments to Sanchez’s post. I think “one way hash” argument might be a bit wordy, and I would prefer simply a “hashed” argument (but this could be a botched argument), or a even a “product” argument (referring to factoring).

When Sanchez says above that arguments can often reduce to “snappy, intuitively appealing argument without obvious problems” vs. “rebuttal I probably don’t have time to read, let alone analyze closely”, I am reminded of some recent remarks from Marcus Ranum, The Anatomy of Security Disasters, where he observes that

Since we’re not working in a field where the probabilities are simple, like they are on a roulette wheel, we’ve had to resort to making guesses, and trying to answer unanswerable questions … I don’t know a single senior security practitioner who has not, at some point or other, had to defend an estimated likelihood of a bad thing happening against an estimated business benefit.

Often business has the “snappy intuitively appealing arguments without obvious problems” - plus Excel - while if the security practitioner objects, then by contrast, the “rebuttal may require explaining a whole series of preliminary concepts before it’s really possible to explain why the talking point (i.e. business case) is wrong”. Snappy and plausible usually wins out over lengthy, detailed and correct. There is asymmetry at work here, a “one way hash” argument, and security people have ended up with the hard inversion problem.

Related Posts

• Marcus Ranum and the Points of No Return

ENISA and Security Awareness

In June I will be speaking at an ENISA conference in London on security awareness. The conference theme is the “growing requirement for information security awareness across public and private organisations". ENISA is quite active in the space of security awareness, and you can see their portfolio of work here. Better security awareness might have prevented the loss of an unencrypted USB stick by an MI6 agent, which as reported recently, lead to a £100 million anti-narcotics operation being abandoned due to compromised data.

One interesting awareness report from ENISA is a survey on current awareness practices and success criteria. The report is short at 24 pages given the generous margins and large graphical embellishments. I have included an important chart below that shows a list of techniques and their effectiveness at raising awareness (as determined by the survey participants)

Classroom training (face-to-face interaction) was judged to be the most effective method, and by some margin. Promotional material had no redeeming features, and CBT courses were only slightly ahead of leaflets and just on par with regular mail outs. But please read the whole report to get the whole picture. In any case, the chart is a good discussion point for your next security team meeting.

Related Posts

• My ENISA Awareness presentation
  

The Relegation of Security to NFR Status

In this post I wish to continue exploring some of the points raised by Marcus Ranum in his recent piece The Anatomy of Security Disasters, commenting on what I see as security being relegated to the status of a non-functional requirement (NFR). That is, a potentially perplexing yet necessary task that needs to be done by some group of specialists to complete a project.

The Ranum disaster cycle looks like this. Management comes up with a new idea with significant business benefits that requires support from IT to be deployed. For sake of argument, let’s say the idea is to bring a customer application online through a web interface that has traditionally only been accessed by internal staff as a back office function. Typically the project has one or several champions, convinced of its importance and certain success, who with their “can do” track records will see the project through.

IT (let alone IT Security) is often not involved in the early stages of developing the project business case and deployment timeframe. By the time IT security does get sight of the project they are nonchalantly requested to “make it secure”. In this manner IT security has become a non-functional requirement (NFR) - not worth explicitly stating - because we have security people and their job is to, well, make IT secure.

From the point of view of the project manager securing the solution is not qualitatively different from ensuring that there is sufficient network capacity, that the servers are adequately sized for peak loads, help desk support is created, back-up and recovery is deployed, the web interface is friendly, and so on. There are specialists who perform these tasks and they will be called upon by the project manager as and when an NFR requires attention.

Once a project (or just its idea) gains a minimum amount of support it becomes very difficult to abort it based on purely technical objections. Ranum speaks of zombie projects that, despite repeated technical strafing, still manage to stagger towards design and deployment. At this point the power of veto over the project for technical reasons is effectively rescinded, and the security people need only resign themselves to “making it secure”, or even perhaps “making it PCI secure”. Ditto for the other NFR specialists. So what is delivered is the best solution under the circumstances – Just-In-Time Security.

The observation here is that the security function is no longer called upon to critically underwrite the security risks of a project, with the option to reject. Their assumed role is to support the delivery of an appropriate solution for the stated business purpose - just like everyone else. Ranum makes the point that bringing IT systems and associated data online carries tremendous inherent security risks - risks which management appear to have lost sight of, and security practitioners have effectively lost their voice to surface.

Ranum predicts that only an epic failure on the scale of the 1986 Space Shuttle Challenger disaster will close the reality gap between management and IT, and save security from being banished into NFR limbo. Ranum hopes that he is wrong, as we all do.

Related Posts

• Marcus Ranum and the Points of No Return

Marcus Ranum and the Points of No Return

Marcus Ranum has written another poignant piece (labelled as a rant) on the state of IT security, called The Anatomy of Security Disasters. You might think from the title that Ranum was embarking on a microscope and tweezers dissection of a recent security incident, which is normally the reason security people get anatomical. However in this case the disaster for Ranum is not a single discrete event but rather the cumulative effect of many business-driven IT decisions taken over the last three decades that have rendered a grand IT failure all but inevitable. For Ranum, we have passed the point(s) of no return in avoiding this disaster, and tragically, the disaster may be a necessary trauma to reset the current complacency towards IT (security) risks.

Ranum sees many similarities with the epic failure of the Space Shuttle Challenger which broke-up shortly after take-off on its tenth mission in 1986, killing all seven crew members. His simple and brutal explanation for the disaster is that “space travel is dangerous”, but the public, as well as many in senior management at NASA had forgotten the inherent risks in the space program. An independent analysis by Nobel Laureate Richard Feynman (who was dying of cancer at the time) on the Challenger incident made a telling observation

It appears that there are enormous differences of opinion as to the probability of a failure with loss of vehicle and of human life. The estimates range from roughly 1 in 100 to 1 in 100,000. The higher figures come from the working engineers, and the very low figures from management. What are the causes and consequences of this lack of agreement? Since 1 part in 100,000 would imply that one could put a Shuttle up each day for 300 years expecting to lose only one, we could properly ask "What is the cause of management's fantastic faith in the machinery?"

Returning to IT, Ranum is essentially asking the same question - what is the cause of management’s fantastic faith in IT? Putting critical IT assets online is simply dangerous.

Business decision-makers are clearly not listening to security engineers, and a huge reality gap has developed between management expectations and IT reality. So much so, that when problems arise management righteously claim that they were lied to. Ranum quotes one of his colleagues as basically believing that any IT thing that is worth doing can be done securely. Security people should stop being “whiners” and just do their job of securely enabling IT for business.

Compound this disconnect between management and technical people over hundreds of thousands of projects at the corporate, national and international levels, spanning the last 3o years, and you have the disaster Ranum is describing (and lamenting). You also have the coming disaster that he is fearing (and loathing), since we have passed the point of no return. Those project decisions cannot be undone - only contained.

A predictable Black Swan is gestating.

I have developed a FreeMind map of Ranum 's article here which gives you some navigational freedom for reading.

Related Posts

• The Relegation of Security to NFR Status
  

On the Entropy of Fingerprints

A biometric is just a long password, that is easy to remember and easy to enter (with the right hardware support). But just how long a password? Can we measure and compare the “something you are” against the “something you know” authentication criteria? I went looking on the web and yes there are some answers.

In An Analysis of Minutiae Matching Strength three IBM researchers outline how to measure the entropy of fingerprints and their resistance to brute force attacks as compared to passwords. The authors state that sampled biometrics are much longer than passwords (several hundred bytes to over a megabyte) and typically have a high information content. A password of equivalent length would be difficult to remember.

The authors use two models to arrive at these conclusions. In both models they assume that an extracted fingerprint sample can be represented as an image of 300 x 300 pixels, which can be divided into 400 non-overlapping sites of 20 x 20 pixels. Each site holds a minutia detailing a ridge and valley pattern of a fingerprint, and each minutia point has an angle of orientation represented by d = 4, 8 or 16 values. A sample fingerprint is considered a match against a template if a minimum number of N sites match where N is 10, 12, 14, 16 or 18.

So this is like saying that you have a password of length 400 where each character takes on at least d values and you accept a candidate password as correct if it matches the true password in at least N positions. Letting N = 10 and d = 4 yields just over 2^85 possible fingerprint configurations. So attempting to randomly guess a correct fingerprint template in this model only succeeds with one chance in 2^{-85}. This is very low indeed and corresponds to a random length 13 password based on the 94 printable ASCII characters.

What we have described is called the simple model by the authors, which does not account for certain minutia dependencies. A more complex model is proposed to compensate which also shows that the entropy is still as high as 80 bits with additional matches. Even with the complex model there were quite a few caveats, and a revised model was reported in the excellent 2008 survey paper Biometrics: A Tool for Information Security.

In section V.A of the survey paper the amount of discriminating information in a fingerprint is discussed. The revised model is somewhat more conservative in its comparisons to passwords. The authors now state that randomly matching on at least 20 from 36 minutia is at least as difficult as guessing a length 6 case-sensitive alphanumeric password (about 10^{11} in total).

The revised model was motivated by the desire to quantify the uniqueness of fingerprints due to their importance in determining guilt in court cases. And just like DNA tests, the assumed power of fingerprints to uniquely discriminate between individuals is being downgraded.

So in summary a biometric is just a long password, that is easy to remember and easy to enter (with the right hardware support). But you need to check the parameters of the matching algorithm and its assumptions to determine how strong your fingerprint as compared to a password.

Related Posts

• NIST, Passwords and Entropy
• Weapons of Math Instruction: The Birthday Paradox

NIST, Passwords and Entropy

Passwords still remain the principal security mechanism to protect information assets. To make passwords harder to guess, security policies usually specify baseline requirements concerning password length (say at least 6 characters), composition rules (say all alphanumeric characters with at least one digit) and further content guidelines on avoiding dictionary words and personal references. The intent of such policies is to gain some assurance that users will not select passwords, either willingly or unintentionally, from a potentially small fraction of all possible passwords.

An interesting approach to specifying password policies is taken by NIST in the Electronic Authentication Guide (SP800-63), a document which has been evolving since early 2006. In SP800-63 entropy-based arguments are used to create password policies that provide a bound on the maximum number of password guesses that an attacker can make while still having only a small probability of success. Entropy is a classical measure of information content of an event with an uncertain outcome. In SP800-63 the approach is to specify policies which yield passwords with a minimum amount of entropy, and then to translate this uncertainty measure into a minimum amount of work (that is, guesses) that must be performed by an attacker to recover the password.

The SP800-63 approach to Password Policies

The main threat being addressed SP800-63 is online password guessing, assuming that the attacker has online access to the target system or (web) application for the lifetime of the password (typically several months at least). This focus seems to hark back to the 1985 US DoD Password Management Guidelines which considered resistance to online guessing as the fundamental metric of password security.

The SP800-63 approach to selecting passwords can be outlined in the following 5 steps.

1. Set a threshold of success for an online attack to 2^{-k}
2. Model the textual properties of user selected passwords as English text.
3. Use known results on entropy estimates for English to select password policies that yield a minimum amount of entropy in user passwords.
4. Derive a bound M on the number of online guesses for an attacker to recover a password generated according the policies in Step 3 and the threshold in Step 1.
5. Verify that the attacker will be limited to a number of online guesses m such that m < M.

In Step 1 a threshold is set for the success of online guessing attacks which is acceptable to the system owner. As suggested by SP800-63 this value should be at least k = 10 (about 1 in 1000) and preferably k = 14 (about 1 in 16,000). These probabilities are taken over the number of possible guesses that the attacker can make over the lifetime of the password. If these odds look too high for the attacker then the system designer should use a stronger authentication mechanism.

In Step 2 it is assumed that user-selected passwords have the same characteristics as English text. This is a somewhat conservative (even reasonable some might say) and permits previously known results on the entropy of English to be applied The basic results here are due to the experiments of Claude Shannon, the inventor of information entropy, and many other significant discoveries. Based on these results, password policies are selected to ensure that user passwords will contain a minimum amount of entropy.

In Step 3 the entropy implied in password policies is converted into work (the number M of online guesses) to recover a password according to the bound stated in Step 1. Finally in Step 5 the system is designed to ensure that the number of possible online guesses m over the lifetime of the password is less than M.

To clarify this approach, we recount an example from Appendix 1 of SP800-63. Consider a password policy that mandates passwords of length 8, selected from the 94 printable keyboard characters, required to include at least one lower case, upper case, digit and special character, and is finally scanned to remove dictionary words. SP800-63 asserts that such passwords contain at least 30 bits of entropy, and conclude that if the number of online guesses mounted by an attacker is less than 2^{16}, then the likelihood that the password will be guessed is less 2^{-14}.

In this case passwords will be considered secure against online guessing if the attacker can be limited to less than about 64,000 guesses over the lifetime of the password. The graph below and its associated table in Appendix 1 of SP800-63 show measures of entropy for passwords up to length 30.

Such arguments may end up being influential with security policy makers as exemplified by How Strong is Your Password? NIST has some formulas. For example, the US Railroad Retirement Board includes the following statement in its authentication policies (level 2 corresponds to a threshold of k = 14)

For level 2 protection against on-line guessing, NIST recommends guessing entropy of 30. Guessing entropy is an indication of the amount of work to determine, or guess, a password. Alternately, NIST indicates that any system that required passwords to be changed at least every two years and limited trials by locking an account for 24 hours after six failed attempts would satisfy the targeted guessing attack requirements for level 2.

Converting Entropy into Guessing Work

This seems like magic – pump up the entropy in passwords and you get resistance to online guessing attacks. To understand what is happening here let’s make the following definitions. We will assume that there are N possible passwords defined by a policy

and that a given user U will select these passwords according to the probability distribution

Lastly let’s assume for simplicity that the passwords are ordered such that

 

which just means that password P1 is the mostly likely choice of the user with probability p1, password P2 is the next most likely choice with probability p2, and so on. The SP800-63 approach is to find the largest value of M such that

and to ensure that an attacker cannot make M online guesses over the lifetime of the password. Here we make the conservative assumption that an attacker is searching the passwords in the same order of likelihood as the user will select them.

The big trick in the SP800-63 analysis is to derive the value of M from the entropy in the passwords rather than finding the password distribution explicitly. Using standard definitions, the password entropy is given as

Now this does not seem to help us much. Say for example that the password entropy is determined to be 30 bits, what can we than say about the number of acceptable password guesses M? Well what SP800-63 does is to assume that a password with 30 bits of entropy represents the same difficulty to guess as a random 30-bit number. What this assumption means is that

and M can be evaluated as

So when the entropy is 30 bits and k = 14, then if the number of online guesses mounted by an attacker is less than M = 2^{16} = 2^{30 - 14}, the likelihood that the password will be guessed is less than 2^{-14}.

The Flaw of Averages

Unfortunately there is a flaw in this argument. Imagine that you have a random number generator for AES-128 keys, and that you determined that the entropy of the keys produced by the generator was only 80 bits rather than the expected 128 bits. What could you say about the probabilities of the keys being produced by such a generator?

Well it could be the case that there is a subset of 2^{80} keys that are produced uniformly (each with probability 2^{-80} ) and that the remaining keys (the vast majority) are produced with probability zero. Such a distribution would produce an entropy of 80 bits.

So what SP800-63 does in its analysis is to use the same logic but in reverse. If the set of user passwords has an entropy of 30 bits then SP800-63 concludes that there are effectively 2^{30} uniformly distributed passwords, each selected by users with probability of 2^{-30}. Trying to guess the correct password is then like trying to guess a random 30-bit number.

But having a uniform subset of 2^{30} passwords is only one possible distribution that could produce an entropy of 30 bits. It is entirely possible that there could be passwords which have a much higher probability of 2^{-30} of being selected (and others with a much lower probability) while still maintaining an overall entropy of 30 bits. And this would lead a smaller value of M as implied by the analysis above.

The problem here is that the entropy is a single summary statistic (an average in fact) computed over the password distribution, and as such, detail on the distribution itself is lost. The logic of the Sp800-63 analysis is to hypothesize into existence a uniform distribution as the source of the entropy value, when in fact other non-uniform distributions may well have been responsible. And these other non-uniform distributions may provide less security against online guessing than is implied by the hypothesized uniform distribution.

In fact it has been observed before by several authors that entropy is not a good indicator of work, which in our case means the number of guesses to recover a password. To understand this statement further you will need to take the time to read some research. The best papers on the topic are written by John O. Pliam, starting with On the Incomparability of Entropy and Marginal Guesswork in Brute Force Attacks. Eric Verhuel has done some more recent research, presented at RSA 2007.

The Gordian Knot Remains

Setting effective password policies really depends on having good knowledge of how users choose passwords, in particular, the form of the probability distribution for their password selection

In short no one seems to know how to unravel the Gordian Knot surrounding user password habits. SP800-63 attempted to get at these probabilities via entropy arguments, but in the entropy we have already lost too much information concerning the password distribution. Even so, the SP800-63 password policy recommendations are good – just take their online guessing bounds with a potentially large grain of salt. Appendix 1 of SP800-63 makes very interesting reading nonetheless.

Related Articles

• The Spin on AES Passwords
• Counting Restricted Password Spaces
• Password Roundup #1

The Data Centric Security Model (DCSM)

(Repost from July 2007)

While at IBM I worked on a concept which we called the Data Centric Security Model (DCSM), with the basic idea being that security people will have more fruitful interaction with IT managers if discussions centered on their data rather than on our technology. After I left IBM, several people continued to work on the DCSM resulting in a paper presented at the Business Driven IT Workshop in May 2007, which has now been posted on Scribd.

A Data Centric Security Model

Publish at Scribd or explore others: School Work security data centric securit