All Posts on AES and A5/1

I have collected my AES and A5/1 posts here for convenient reference

• AES-128 versus AES-256
• The Luxembourg Attacks and AES-256
• AES-256 and Reputational Risk
• The spin on passwords for AES
• Are AES 256-bit keys too large?

• The Last Days of A5/1
  
• Another crack at open Rainbow Tables for A5/1
• Long Tail of Vulerability for A5/1
• MasterCard Bets on A5/1

All Posts on Passwords

I have collected all my passwords posts here for convenient reference

• Faster Rainbow Tables
  
• Passwords for USB Keypads
  
• The USB Password Vulnerability
• Fast Computations on FPGAs
  
• Outline of a book on Passwords
• How will my loved ones break my password?
• Enterprise Password Management Guidelines from NIST
• The Boys are Back in Town – the return of L0PHT
• Rethinking Thresholds for Account Lockouts
• Password Roundup #2
• NIST, Passwords and Entropy
• Password Roundup #1
• Downadup's Password Cracking List
• The spin on passwords for AES
• More on Counting Restrictive Password Spaces
• Counting Restricted Password Spaces

Security Muggles

The question of “How secure are we?”, essentially a perennial security conundrum, was on the agenda of the recent CSI meeting in Washington, as reported by Dark Reading. What was on offer from a collection of senior security professionals was advice – and perhaps this is the best that can be expected. Christopher Michael, director of information assurance at defence contractor BAE Systems, went as far as basically saying that security status can’t be measured yet security professionals are obliged to do so. So what is to be done? The article has a few ideas, which as presented, don’t flow together particularly well, but some interesting points were made.

The first of which is that security people are predisposed to detail, accuracy and correctness. Donald Knuth, the famous computer scientist, has stated that the reason programming is so hard, therefore so interesting to excel at, is that as a discipline it does not admit approximations – everything must be exact and correct – the processor will not interpret your intentions only execute your commands. And while the traits of detail, accuracy and correctness are necessary for IT activities, they are fundamentally at odds with the type of messages and opinions that senior managers are expecting. Detail, accuracy and correctness can be sacrificed to an extent for the benefits of conciseness, meaning and actionable recommendations. They don’t want to hear about packets, firewall rules or buffer overflows.

I have a soft spot for threat modelling, and appreciate the detail and insights it uncovers, but I often wonder how far up the managerial chain this type of analysis in its raw form can be propagated. Sooner or later you will reach a managerial layer populated by security muggles who will require (or demand) less complicated analyses.

Bill Mann, senior vice president of security product strategy at CA, remarked that “these guys [the muggles] think in spreadsheets”, which is the same sentiment I expressed in Does IT Security Matter? - “Excel is your new best friend - make your spreadsheets work with their (business) spreadsheets”. You perhaps need not take this Excel advice literally but at least think of Excel as the underlying business platform for marshalling data, numbers and money towards business cases. Security, or any other activity, needs to figure prominently in this space to be taken seriously – or at least to get a serious hearing.

This is the same point that Marcus Ranum raised not too long ago, about security people, and their arguments (often objections) being over-ruled by more business-savvy types. We perhaps need to develop skills in one-way hash arguments

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.

In Some Black Swans in IT Security I argued that the the most pernicious problem facing IT Security today

We have called this Black Swan "Good Enough Security" but we may also have chosen risk-based security, the transition from risk to assurance, the diminishing returns of security, or knowing your security posture. Managers and other stakeholders want to know that their IT assets are adequately protected, and it is up to the IT Security person to define that level of adequacy and provide assurance that it is reached and maintained. Most security people are woefully ill-equipped to define and deliver such assurance in convincing business or managerial language.

It is not so much that we must deal with security muggles but rather IT Security people are seen as business muggles.

Quadratic Football Revisited

Just on a year ago now (almost a birthday!) I posted about the birthday paradox, with a review of general results and then some remarks on erroneous conclusions from DNA matching. In the post there is a subheading called Quadratic Football, referring to the facts that the median of the birthday paradox distribution is 23, the same as the number of players on pitch for a football match (two teams of 11 plus the referee), and this number is surprisingly small due to the quadratic (growing as the square) number of possible birthday matches.

I recently uploaded Methods for studying coincidences to Scribd and found an auto-linked document that presents a small study of birthday coincidences in actual British football fixtures. The conclusion – good agreement between theory and practice. This short paper is well-worth a read.

Recent uploads to Scribd

I have been going through some interesting documents I have been collecting, and added them to Scribd. The topics vary but basically security and (IT) risk one way or the other.

• Methods for studying coincidences
• Tornado modelling
• FSA on Data Security controls
• Hotel Network security in the US
• GAO report on Pandemic bandwidth risks
• Key findings MS Security Intel report H109
• Entrust whitepaper on quantum crypto and computation
• Facebook: Threats to Privacy
• What led to the financial meltdown?

Outline of a book on Passwords

I have uploaded to my Google site an outline of a book I started to write in 2003 on passwords. At the time I had a few months away from work and I decided to return to some basics in security, and I started with passwords in Windows. I was surprised at how complex, or at least detailed, this topic turned out to be. I was somewhat inspired by also reading Richard Smith’s nice book Authentication: from Passwords to Public keys. You will find many references to his book in my draft.

My draft does have some good references, a list of passwords threats and a nice glossary. Looking at the TOC you get some idea of how much there is to cover.

I am not sure I will get back to completing the book, though I would surely like to. I make regular posts on passwords and they are certainly one of my pet security topics. However time has eluded me (so far) and perhaps you can use the material.

Upcoming Black Swan talk at ZISC

I will be giving a talk in mid December at the Zurich Information Security Colloquium (ZISC) on one of my favourite topics, Some Black Swans in IT Security. Details can be found on the ZISC site.

Security FreeMind map sources

I have started to upload the FreeMind source of my MindMaps to my Google site here.  I will eventually upload all my maps, including those that were used just for reference and storing links (17 have been uploaded at the moment).

Focus on securing business processes not the process of securing

The title comes from a list of conclusions I gave at a presentation called Does IT Security Matter? just before Christmas in 2007. The wonderful thing about the writing process is that every now and again you hit upon a pithy phrase like that which communicates so much. But it's like mining for gold - you have to move a lot of earth to find the nuggets.

The full presentation is available on Sribd as shown below. There have been about 1200 reads and 240 downloads. Re-reading it now, the presentation could do with an update, however the core messages are still valid. My main conclusions were

• There is a dependency between IT and IT Security but not a strategic relation
• IT and IT Security are good neighbours but not good friends
• IT Security is one area competing for attention and funding, amongst many
• If you don’t make IT security matter, it won’t
• Focus on securing business processes not the process of securing
• •Excel is your new best friend - make your spreadsheets work with their (business) spreadsheets

Does IT Security Matter?

The Size of our Security World

I was sent a link from StumbleUpon that referred to a post which showed the relative sizes of planets in our solar system, then compared them to our Sun, and moved onto comparisons with much larger other stars. Surprisingly much larger stars - in fact in the final screen-size graphic our Sun is just represented as a single pixel as compared to the Antares, a red supergiant star in the Milky Way. My 15-year-old daughter was impressed by this, and if you have a 15-year-old, then you can appreciate what a momentous achievement this is.

I started out my post-university life working in cryptography, then I spent a long time in IT Security, then IT Risk and most recently in Enterprise Risk Management (ERM). When I look back at crypto now it seems of similar consequence to the proportions of the Sun and Antares - not merely because my professional interests have changed, but in the vast equation that constitutes ERM, crypto is a variable with minor weighting. Its gravitational force is largely exerted on specialists, and rapidly declines (much faster than the inverse square law) beyond that sphere. It's just a pixel on the football-field sized collage of ERM.

Risk Analysis Rising

In June I posted on a paper called A Risk Analysis of Risk Analysis, and from that post

The title of this post is taken from a both sobering and sensible paper published last year by Jay Lund, a distinguished professor of civil engineering at the University of California (Davis), who specialises in water management. The paper presents a discussion of the merits of Probabilistic Risk Assessment (PRA), which is a “systematic and comprehensive methodology to evaluate risks associated with a complex engineered technological entity”. PRA is notably used by NASA (see their 320 page guide) as well as essentially being mandated for assessing the operational risks of nuclear power plants during the 80’s and 90’s.

It  is a wonderfully insightful paper that I uploaded to Scribd, who recently informed me that the paper is now on their hotlist. You can get to the paper from the link below. Highly recommended!

Post Number 100

This is post number 100 since the beginning of the No Tricks blog in September 2007. I have not been collecting statistics from Google Analytics over this whole period, but since April 2008 my site has had just over 12,700 visits by people who have viewed close to 21,000 pages. My bounce rate and new visitor rate stubbornly hover around 75%. The majority of visits are to the main page, but after a post gets off the main page we can get some measure of its popularity. The top 10 posts by the number of visits are

1. Are AES 256-bit keys too large? (2,558)
2. Examples of Risk Profile Graphs (1,164)
3. Entrust PKI v5 Overview (743)
4. The cost of SHA-1 collisions reduced to 2^{52} (590)
5. AES-256 and Reputational Risk (514)
6. Weapons of Math Instruction: The Birthday Paradox (458)
7. The spin on passwords for AES (421)
8. The Wisdom of a Random Crowd of One(416)
9. Goodbye Yellow Brick Road (412)
10. Long Tail of Vulnerability for A5/1 (362)

The top two posts account for a large number of visits, which I called my Pareto Posts back in my assessment last Christmas . The post on AES-256 and Reputational Risk may yet reach towards the top as it is a relatively recent post that is getting more hits. On the other hand, if we rank posts by the average time spent reading the post, then a different picture emerges. Below I list the top 10 posts that have had at least 20 views by largest average visit time

1. Excellent Awareness talk from British Airways (8:35)
2. Self-Destructing Digital Data with Vanish (7:38)
3. Marcus Ranum and the Points of No Return (7:23)
4. Twitter in the Land of Power Laws (6:42)
5. ENISA and Security Awareness (5:41)
6. Quantum Computing: are you Shor? (5:30)
7. The Sub-Time Crisis in Web 2.0 (5:11)
8. AES-256 and Reputational Risk (4:45)
9. Weapons of Math Instruction: The Birthday Paradox (4:43)
10. A tie between Long Tail of Vulnerability for A5/1 and Zero Knowledge Proofs (4:20)

The posts on AES reputational risk and attacks on A5/1 are perhaps the best examples of posts that are both well-visited and well-read. Thanks to everyone for visiting the No Tricks blog!

My Top 10 Security and Risk Uploads to Scribd

I have been reading and uploading to Scribd for several years now. It is really a vast source of documents and its seems that it has been a victim of its own popularity since now so many varied and inconsequential documents are finding their way to to site. The search function is not quite as effective as it was, and as always been true, the site itself is quite slow.

Over the last couple of years I have slowly uploaded just over 40 documents and presentations, mostly in the area of security and risks. For the last few months I have been getting just over 100 hits per day, and about 12 downloads per day. The total number of hits is now getting close to 20,000, and will reach that mark in the next week. Here is a list of the top 10 visited documents that I have uploaded – the number of reads is in parentheses, and documents in bold type are written by me

1. A Data Centric Security Model (1529)

2. ISACA Risk Framework (1498)

3. How much is enough? A Risk Management Approach to Computer Security (1290)

4. Does IT Security Matter? (1127)

5. Entropy Bounds for Traffic Confirmation (886)

6. Risk Analysis of Power Station survival of Cyber (712)

7. Password Authentication on Mac OS X from Dave Dribin (704)

8. An analysis of the Linux Random Number Generator (702)

9. The Core Components of the Entrust PKI v5 (677)

10. Canadian Government 1999 Threat and Risk Assessment Guide (628)

The Luxembourg Attacks and AES-256

There have been several attacks on AES-256 in the last few months, referred to as the "Luxembourg Attacks". I had hoped to write about the attack announced in June before I went on summer holiday, but ran short on time - and then another attack was announced in July. It is the first attack that I wish to address here to emphasize some points I made in an earlier post.

In May I wrote about the topic of AES-256 and Reputational Risk where I argued that the huge 256-bit key makes it possible for someone to construct an attack which has "big savings" over exhaustive search yet still does not effectively change the margin of security. What suffers in this case is the reputation of AES-256, and the post concluded with

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.

So the first Luxembourg attack gives you an example of the type of arguments that can be proposed when working with 256-bit keys. The attack needs to work with 2^{119} plaintext/ciphertext pairs, requiring about 2^{77} storage, all to yield 156 bits of the key. The remaining 100 unknown bits of the key are guessed, at an average cost of 2^{99} encryptions. This guessing step is hardly worth mentioning as compared to the main 2^{119} computation, since it represents something like one part in a million of the total work.

Some Details of the Attack

The basis of the attack is called differential cryptanalysis (DC), a powerful attack method that gained widespread popularity in the late 80's, and was standard fare by the time AES was announced. In this attack the cryptanalyst finds a pair of values (~P, ~C) such that two plaintexts P1 and P2 of difference ~P  = P1 + P2 are biased towards producing ~C as the difference C1 + C2 of their corresponding ciphertexts (here the difference operator + usually means XOR but it varies according to how the key is combined internally in a cipher). In short, plaintexts of difference ~P produce ciphertexts of difference ~C with some probability that is much higher than 2^{-N} where N is the block size of the cipher. Given such a pair of differences (~P, ~C) an attacker can use statistical methods to gain information about parts of the key that were used in the last or next to last round for example. The remaining bits are then guessed.

DC is typically quite data intensive. Even though plaintexts of difference ~P may be biased towards producing ciphertexts of difference ~C, this may only happen with probability 2^{-50} for example, which sounds quite low but it is much higher than you would expect for a 128-bit block cipher. Therefore the attacker will need to obtain  2^{50} plaintext pair encryptions of difference ~P to get on average just one ciphertext pair of difference ~C. Part of a successful DC attack is designing a filtering strategy to discard most ciphertext pairs that don't have ~C as a difference before they are spuriously used as the basis to give information about some part of the key. So a large number of encryptions are needed, where the majority will be winnowed away, leaving a precious few that lead to information about the key.

In the  first Luxembourg attack (LA1), the basic DC attack is upgraded to a boomerang attack which eliminates the need to thread the differences (~P, ~C) to each other through all the intermediate rounds of the cipher. LA1 also uses related keys to coerce differences into a desired form - in the vanilla DC attack we are trying to keep plaintext differences in a known state, but by using related keys, the key can also be used to bring the internal state of the cipher into a known difference.

The basic step of LA1 is to obtain 2^{61} encryptions of specially crafted quartets (4 related values), and then combine these values amongst themselves to generate the required internal differences. It is this combination process and its associated filtering which drives up the cost of the attack to 2^{119}. The result is that the remaining unfiltered quartets identify all but 100 bits of the key which, as we mentioned above, can be guessed at a small marginal cost.

Luxembourg 2.0

Even though the attack has unrealistic resource requirements, it works on the full-version of AES-256, which is a significant result – something that no other researchers has been able to do – and that’s not due to lack of trying. And the reputation of AES-256? Well the Register for example  reported that LA1 represents an improvement over brute force search for AES-256. Well even that is debatable since you need a huge amount of plaintext/ciphertext encrypted under several keys to mount the attack, while brute force  needs just a few blocks to execute. What’s in the future then? Well I guess its here already in the second Luxembourg attack, which is on my reading list.

Related Posts

• Are AES 256-bit keys too large?

• AES-256 and Reputational Risk

• The Spin on AES Passwords

Thoughts on the Cult of Schneier

Earlier in the year John Viega wrote a short opinion article called The Cult of Schneier, referring to the near-religious following that Bruce Schneier has acquired over his long and successful career in IT Security, and the biblical authority that the Applied Cryptography book has attained. Viega's main issue with the book as it currently stands is that "It's fine and fun to read it, just don't build from it".

I think that Applied Cryptography was a very well-crafted book. It contains an excellent mix of mathematics, exposition, security intrigue and executable code. However for me, and a few other cryptographers I know, the Handbook of Applied Cryptography is a best source of general cryptography information. The book does not enjoy anywhere near the same general recognition as Applied Cryptography, seemingly because it is viewed as a "math book" - correct, factual, thorough and therefore unappealing to a wide audience, as most technical books are. In short it lacks the narrative woven into Applied Cryptography. On the other hand, no one would really confuse the Handbook with a solution manual for designing and implementing secure systems.

Earlier in the year I made a post on Some Black Swans in IT Security, and I listed Bruce as an unexpected phenomenon in the following way

Bruce Schneier is the best known security authority in the world. His blog has hundreds of thousands of readers, his posts can yield hundreds of comments, and his books are bestsellers. His opinions hold sway over both technical people and executives, as well as all the layers in between. He is the Oprah of security - a public figure and a leading opinion maker. The Black Swan aspect of Mr. Schneier is that he has achieved this status through excellent communication (and yes cunning publicity as well) rather than technical prowess. Of course he has technical prowess but that is rather common in security and cryptography. What is uncommon, or even uncanny, is the ability to explain security in terms that can be understood by non-specialists whether it be programmers, professionals, managers or executives. Bruce has literally written himself into the modern history books of security. He has shown, once again, that communication is king - the security explanation is mightier than the security deed.

I don’t really think that there is a cult in operation over Bruce Schneier, but rather a hero was found when security as an industry needed to believe in heroes.