Superconductor

Cryptography for Mere Mortals #5

An occasional feature, Cryptography for Mere Mortals attempts to provide clear, accessible answers to questions about cryptography for those who are not cryptographers or mathematicians.

Q: How do we know whether a given encryption solution will produce unique results—that is, that for each unique input, a unique output will result? If, say, two SSNs both encrypt to the same value, we’ll have a huge mess on our hands!

A: This is one of the reasons that a security proof is important. It’s easy to say “Sure, it’ll be unique”, but without a careful, peer-reviewed security proof, such a statement has no meaning. The next question is, obviously, “What is a security proof?”

http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1015_ECIES_report.pdf says, in part:

The security of cryptographic schemes is often witnessed by the absence of attacks: a scheme is considered to be secure if it has been around for a long period, has received widespread attention, and could nonetheless not be significantly weakened by any attack. Famous examples of this “negative” security argument are the Data Encryption Standard (DES) and RSA. As opposed to this, provable security is often considered as a decisive advantage for a cryptographic scheme. In this context, it is proved (in a precise mathematical sense) that the scheme is secure, provided some assumptions are satisfied. These “basic” assumptions are typically the security of the primitives the scheme is based on (e.g., the Diffie-Hellman key agreement), or the difficulty of some well-known problem (e.g., factorization, discrete log computation, … ). Typically, security is proved by exhibiting a reduction that turns a breaking of the scheme into a solution of the underlying problem. By contraposition, this proves that, if the underlying problem is actually hard, then the scheme is secure.

In other words, a security proof is just like the geometric proofs we did back in high school: given some basic assumptions that nobody is likely to argue with (“A straight line segment can be drawn joining any two points” et al.), logically show that a given algorithm has specific properties. Peer review of security proofs simply provides improved assurance that the proof is correct: even without any deliberate misrepresentation, the process is complex enough that it makes sense for other, perhaps smarter people to check for mistakes.

One of the things that a good security proof will demonstrate, for any encryption algorithm that is intended to be reversible (that is, to allow decryption), is uniqueness of outputs. A non-unique output would be a collision. Collisions are not just bad, they’re crossing-the-streams bad, because they mean that you cannot reliably decrypt: if x and y both encrypt to z, then when you decrypt z, will you get x or y? You likely want this to be deterministic!

It’s important to note that “no collisions” does not necessarily translate to “input never equals output”. For example, if you use Format-Preserving Encryption on a gender field (M/F), there are only two possibilities:

· M maps to F

· M maps to M

(and vice-versa for F). This is one of the reasons that Voltage SecureData requires specification of a flag to use FPE on very short data: such cases are considered cryptographically weak, in that methods such as statistical analysis may allow an attacker to figure out the matching plaintext for that field (there are ways around this, which will be covered in a later post).

But this goes beyond such obvious cases: if you use FPE on, say, a four-digit number, then it is possible—not likely, but possible—that at least one of those values will encrypt to itself (a “fixpoint”, in crypto-speak). This is not a flaw in the algorithm: indeed, to a cryptographer, such behavior is not only obvious, but desirable. They even have a fun term for an algorithm that does not contain any fixpoints: a derangement.

Note that the input set of four-digit values has 10,000 elements (0 through 9999); accordingly, the output set must have 10,000 elements, so there’s no obvious action that can be taken if a fixpoint is found—changing the value means a collision. Moreover, if we know that a value can never encrypt to itself, we are actually weakening the encryption, because given a ciphertext, we now only have 9,999 possible values for the matching plaintext.

This might seem like a trivial weakening—but is exactly the kind of thing that security proofs deal with. “A few bits here, a few bits there, pretty soon, you’re talking real weakness”, to misquote Everett Dirksen’s famous line.

The Internet alphabet

Suppose that you’re using Google to find something. Maybe you’re looking for a company that can provide data protection solutions based on identity-based encryption and format-preserving encryption, so you start typing “data protection” into Google. Google actually tries to guess what you’re looking for and provides a list of these guesses that you can use to save having to type your complete query. And because it even does this when you give it the first letter of your query, it seems to make sense to use its top suggestions to make an “Internet alphabet.” I’m sure that someone’s already done this, but I don’t really spend much time looking for random stuff on the Internet, so I haven’t actually come across it. But when I tried each of the letters of the alphabet, here’s today’s Internet alphabet:

Letter	Google’s top suggestion
A	Amazon
B	Bank of America
C	Craigslist
D	Dictionary
E	ESPN
F	Facebook
G	Gmail
H	Hotmail
I	Ikea
J	Jeremy Lin
K	Kayak
L	Linkedin
M	Mapquest
N	NetFlix
O	Orbitz
P	Pinterest
Q	QVC
R	Redbox
S	Southwest
T	Target
U	United Airlines
V	Virgin America
W	Wells Fargo
X	Xfinity
Y	YouTube
Z	Zillow

Why we still have passwords

Many security experts hate, loathe, despise, revile, detest and generally just don't like passwords, although it's not clear exactly why they feel this way. After all, passwords are still very common, and that means that people are still making the decision to use them fairly frequently.

Some people would say that that just shows that people don't make rational choices. I disagree with this assessment. I actually think that people generally make very rational choices, but their criteria for making their decision may not agree with what either experts or so-called experts think that they should use. If that's the case, it's reasonable to assume that passwords really aren't so bad, and this is pretty much what recent research has shown.

In the paper "The Quest to Replace Passwords: A Framework for Comparative Evaluation of Web Authentication Schemes," (pdf) the authors evaluate 36 different authentication schemes using 25 different criteria, and found that none of the schemes that they looked at was superior to passwords in every way. This means that it's certainly possible that whatever decision-making process people are using to pick what authentication scheme to use happens to weight the factors in a way that makes passwords the best alternative.

Here's the abstract for this paper, to give you an idea of what it talks about:

We evaluate two decades of proposals to replace text passwords for general-purpose user authentication on the web using a broad set of twenty-five usability, deployability and security benefits that an ideal scheme might provide. The scope of proposals we survey is also extensive, including password management software, federated login protocols, graphical password schemes, cognitive authentication schemes, one-time passwords, hardware tokens, phone-aided schemes and biometrics. Our comprehensive approach leads to key insights about the difficulty of replacing passwords. Not only does no known scheme come close to providing all desired benefits: none even retains the full set of benefits that legacy passwords already provide. In particular, there is a wide range from schemes offering minor security benefits beyond legacy passwords, to those offering significant security benefits in return for being more costly to deploy or more difficult to use. We conclude that many academic proposals have failed to gain traction because researchers rarely consider a sufficiently wide range of real-world constraints. Beyond our analysis of current schemes, our framework provides an evaluation methodology and benchmark for future web authentication proposals. 

One interesting result of the model used in this paper is that there's no alternative to passwords that's clearly better: "Not a single scheme is dominant over passwords, i.e., does better on one of more benefits and does at least as well on all others."

And because there's no authentication technology that's clearly better than passwords, replacing them with a different technology is really just a case of substituting one set of tradeoffs for a different set of tradeoffs, and when that happens it's not clear that what you get is really an improvement. It might be an improvement, of course, but whether it actually is depends on lots of details: what your threat model is, etc.

This paper is definitely worth looking at if you're interested in authentication. And because the strength of virtually everything that information security provides essentially comes down to the strength of authentication, this should really include anyone interested in any aspect of information security.

A Pattern for Increased Monitoring for Intellectual Property Theft by Departing Insiders

CERT just released A Pattern for Increased Monitoring for Intellectual Property Theft by Departing Insiders. Here's how they summarize what they found:

A research project at the CERT® Program is identifying enterprise architectural patterns to protect against the insider threat to organizations. This report presents an example of such a pattern-Increased Monitoring for Intellectual Property (IP) Theft by Departing Insiders-to help organizations plan, prepare, and implement a means to mitigate the risk of insider theft of IP. Our case data shows that many insiders who stole IP did so within 30 days of their termination. Based on this insight, this pattern helps reduce that risk through increased monitoring of departing insiders during their last 30 days of employment. The increased monitoring suggested by the pattern is above and beyond what might be required for a baseline organizational detection of potentially malicious insider actions. Future work will include development of a library of enterprise architectural patterns for mitigating the insider threat based on the data we have collected. Our goal is for organizational resilience to insider threat to emerge from repeated application of patterns from the library.

This doesn't seem to be one of the more enlightening reports on the insider threat, but it does contain an interesting poinnt or two and is probably worth reading when you get a chance.

Who wrote the Blackwater standard?

An alert reader pointed me to the minutes (PDF) of one of the meetings of the working group that wrote the ANSI/ASIS PSC.1-2012 Management System for Quality of Private Security Company Opertions - Requirements with Guidance. Here's the list of members of the group:

Dr. Marc H. Siegel, ASIS International
Raymond Andersson, Department of Defence - Australian Army
Dennis Blass, CPP, PSP, CFE, CISSP, Children's of Alabama
John Casas, PSP, John Casas & Associates, L.L.C.
Rebecca DeWinter-Schmitt, Amnesty International USA
Robert Hulshouser, CPP, Urban Environmental Research
Tim Lindsey, CPP, Paradigm Security Services, Inc.
Christopher Mayer, Department of Defense
Allan McDougall, PCIP, CMAS, CISSP, CPP, Evolutionary Security Management
Paul Mitchell, GlobalEdge International
William Prentice, Marine Security Initiatives, Inc.
Erik Quist, EOD Technology, Inc. (EODT)
Ian Ralby, Security in Complex Environments Group, A|D|S Group, Ltd.
Jeffrey Slotnick, CPP,PSP, Setracon, Inc.
Nancy Slotnick, SPHR, GPHR, Setracon, Inc.
Christine Tumolo, U.S. Security Care, Inc.
Allan Wick, CFE, CPP, PSP, Tri-State Generation & Transmission

I don't know any of these people so I really can't say anything about how their opinions might or might not have affected how this standard turned out, but there's the list.

How could Yahoo! leak a private key?

According to the blog of hacker Nik Cubrilovic, the most recent version of Yahoo!'s Axis extension for the Chrome browser actually included the PGP private key that Yahoo! used to digitally sign the software.

Seriously.

So if you're a clever hacker, or even just moderately observant, this gives you everything that you'd need to create your own extensions and then sign them so that look they came from Yahoo!

D'oh!

I'm sure that there's a perfectly good explanation for how this happened, but I'm having a hard time thinking of exactly what that could be.

Cubrilovic's blog has a link to a demonstration of how to exploit this bug, and it's something that you should definitely check out if you have even a casual interest in this sort of thing.

A Blackwater security standard?

It looks like ANSI and ASIS just completed their joint standard ANSI/ASIS PSC.1-2012 Management System for Quality of Private Security Company Opertions - Requirements with Guidance. Here's how they describe this:

This Standard builds on the Montreux Document and the International Code of Conduct (ICoC) for Private Security Service Providers to provide requirements and guidance for a management system with auditable criteria for Quality of Private Security Company Operations, consistent with respect for human rights, legal obligations and good practices related to operations of private security service provider companies in conditions where governance and the rule of law have been undermined by conflict or disaster. It provides auditable requirements based on the Plan-Do-Check-Act model for third-party certification of private security service providers working for any client.

So it's roughly a set of standards that companies like the old Blackwater (now Academi) really ought to follow.

And according to a press release(PDF) on the ASIS web site, the US Department of Defense seems to think that this standard is a good idea:

“The United States government supports the principles of the ICoC and Montreux Document,” says Gary Motsek, deputy assistant secretary of Defense, U.S. Department of Defense. “Using its communication platform, ASIS established a community around the world to address a crucial interest of governments and civil society everywhere. PSCs can now demonstrate commitment and accountability to the ICoC and Montreux Document.”

Getting a copy of this standard will cost me $165. I'm not that interested in what it actually has to say, but I'm sort of interested in seeing exactly what organizations participated in the creation of it.

Source Code Analysis Laboratory (SCALe)

The folks at CERT recently released the report Source Code Analysis Laboratory (SCALe) that describes how feasible it is to test source code against secure coding standards. Here's how they describe the contents of this report:

The Source Code Analysis Laboratory (SCALe) is a proof-of-concept demonstration that software systems can be conformance tested against secure coding standards. CERT® secure coding standards provide a detailed enumeration of coding errors that have resulted in vulnerabilities for commonly used software development languages. The SCALe team at the CERT Program, part of Carnegie Mellon University's Software Engineering Institute, analyzes a developer's source code and provides a detailed report of findings to guide the code's repair. After the developer has addressed these findings and the SCALe team determines that the product version conforms to the standard, the CERT Program issues the developer a certificate and lists the system in a registry of conforming systems. This report details the SCALe process and provides an analysis of selected software systems.

Interesting reading if your're intested in secure coding practices, and who isn't?

The Insider Threat Security Reference Architecture

The folks at CERT recently released their Insider Threat Security Reference Architecture. Here's how they describe what's in this document:

The Insider Threat Security Reference Architecture (ITSRA) provides an enterprise-wide solution to insider threat. The architecture consists of four security layers: Business, Information, Data, and Application. Organizations should deploy and enforce controls at each layer to address insider attacks. None of the layers function in isolation or independently of other layers. Rather, the correlation of indicators and application of controls across all four layers form the crux of this approach. Empirical data consisting of more than 700 cases of insider crimes show that insider attacks proved successful in inflicting damage when an organization failed to implement adequate controls in any of three security principles: authorized access, acceptable use, and continuous monitoring. The ITSRA draws from existing best practices and standards as well as from analysis of these cases to provide actionable guidance for organizations to improve their posture against the insider threat.

If insider threats are of intererst to you, this report is probably worth reading. 

Data-centric security

There’s lots of talk these days about the potential for data-centric security and how it will revolutionize the field of information security. While it’s true that data-centric security is a good solution to some problems, it doesn’t solve all problems, and it’s almost certain to coexist with existing security technologies instead of replacing them. It does this in a way that makes it particularly useful in dealing with data breaches, so it should provide a good tool to help fight the massive losses of sensitive data that we're seeing today.

Data-centric security focuses on protecting data rather than protecting the network where the data lives. Traditional security technologies like firewalls establish a security perimeter that's designed to keep hackers out. Everything inside the security perimeter is considered to be more-or-less safe while everything outside the perimeter is considered suspect. Perhaps not exactly Evil, but certainly Bad.

Trends like mobile computing and tighter integration of business partners are making it more and more difficult to define exactly where a security perimeter is. This makes enforcing the traditional model more and more difficult. It's almost impossible to enforce a strong perimeter, after all, if you can't really say exactly where the perimeter is. Because of this, data-centric security is often proposed as an alternative.

With data-centric security, you protect the data instead of the network where the data lives. This is typically done with encryption. In the ideal data-centric model, sensitive date is encrypted and only authorized users can get the cryptographic key needed to decrypt it. To unauthorized users, data looks like a bunch of random bits, and because they can’t get the key needed to turn these random bits into useful information, the data isn’t useful to them.

If a hacker manages to penetrate a network that’s protected by data-centric security, any data that he manages to get will be useless to him. Doing key management correctly is needed to make this a reality, but let’s make a huge leap of faith and assume that that’s possible. This means that a hacker can’t get the decryption keys that he needs to make sense of the encrypted data.

This certainly sounds good, but it probably doesn’t describe a scenario that’s likely to happen, and probably doesn’t describe one that people will pay for. Although they’re far from perfect, existing technologies can create fairly strong security perimeters, after all. So why should we be interested in data-centric security at all?

The real reason that data-centric security will probably become popular is because it provides a way to extend the security perimeter to where it needs to be. Sensitive data is extremely difficult to keep control of. It’s carried outside the security perimeter on a routine basis by people who need to use it. Laptops are routinely lost or stolen. CDs containing sensitive data are lost in the mail. USB drives are also. So keeping sensitive data inside a protected perimeter is virtually impossible. It’s also probably not worth trying to do. People need access to sensitive data to do their jobs, and not letting it leave a protected network probably isn’t practical.

On the other hand, if sensitive data is encrypted, then losing control of it won’t cause any problems because data-centric security extends the security perimeter to wherever the data is. That’s assuming that key management is done correctly, but we’ve assumed that to be the case. The most important use of data-centric security probably won’t be as an additional layer of protection against hackers that manage to penetrate a protected network. Instead, it will probably be used to protect data that leaves the network for legitimate purposes.

The big problem with protecting sensitive data isn’t that hackers get in, it’s that data gets out, and data-centric security has the potential to eliminate the problems that data getting out can cause.

Why I frequently meet NACS lobbyists

I run into lobbyists for NACS, the National Association of Convenience Stores, fairly often at meetings involving credit card payments technology and security and I just learned why this happens.

According to the 2004 article in Payments Source magazine, "Why Gasoline Retailers Are Fuming" (unfortunate registration required), the cost of credit and debit card transactions are the fourth largest cost for gas stations (after labor, rent and utilities), making store owners very interested in lobbying for regulations that lower the fees that they have to pay.

Fascinating Voltage trivia

It turns out that Voltage is different from many other companies. It's even quite different from many Silicon Valley pre-IPO tech companies. In particular, it turns out that at least two Voltage employees are actually ordained ministers and one used to be a professional gambler.

Try to find that particular combinations of backgrounds anywhere else.

Lessons Learned from a Data Breach

I recently read "Heartland Payment Systems: Lessons Learned from a Data Breach." (PDF) This is a discussion paper published by the Philadephia branch of the US Federal Reserve. Bob Carr, the CEO of Heartland Payment Systems, was invited by the Fed's Payment Cards Center to give a talk about the lessons that Heartland had learned from the data breach that affected their systems back in 2008 to 2009. 

Carr talked about the relative strengths and weaknesses of various approaches to protecting sensitive credit card information and  how Heartland decided to use end-to-end encryption to ensure that their systems couldn't suffer another breach like they had just been through. If you're interested in protecting credit card data, you'll probably find Carr's discussion of the various technologies interesting. 

INTERPOL takes on cyber-crime

According to a story on the Washington Post web site, INTERPOL is setting up a facility in Singapore, the INTERPOL Global Complex for Innovation, and a big part of the mission of this new facility is to help fight cyber-crime. I'm not quite sure what to think about this. Lots of government officials are making statements about what an important step this is, but that may or may not actually be the case. I seem to recall INTERPOL being mentioned in The Saint, the '60s TV show that starred Roger Moore as the notorious Simon Templar. It might have been mentioned in one of more James Bond movies, and I seem to recall seeing warnings at the beginning of movies on DVD that tell you that they've expressed concern about copyright infringement. 

But it's not clear to me exactly what INTERPOL does and how their new Global Facility will actually help fight cyber-crime. Interpol's job, after all, is fairly vague: to help coordinate the actions of the world's police forces. And that may not be very useful in the case of cyber-crime because the cyber criminals are fairly clever. 

I've heard stories, for example, of how Russian hackers are very careful to not hack the credit card numbers of other Russians and to not target businesses in Russia. This makes going after them a very low priority for Russian law enforcement agencies who almost always have more pressing issues competing for their attention. And this doesn't seem like the sort of thing that an INTERPOL cyber-crime division would really have much of an effect on.

But here's what INTERPOL wants from their new facility:

The four main components of the Global Complex are as follows:

Innovation, research and digital security

• Boosting cybersecurity and countering  cybercrime;
• A forensic laboratory to support digital crime investigations;
• Research to test protocols, tools and services and to analyse trends of cyber-attacks;
• Development of practical solutions in collaboration with police, research laboratories, academia and the public and private sectors;
• Addressing issues such as Internet security governance.

Capacity building and training

• Research into training and methodology and the transfer of this research into police activities on the ground;
• Classroom, field and online training programmes for  National Central Bureaus; 
• Anti-corruption training, particularly in sport;
• Quality standards and accreditation.

Operational and investigative support

• Identifying and addressing emerging crime threats, for example,  intellectual property crime, environmental crime and  Asian Organized crime;
• A platform for  disaster victim identification;
• A  Command and Coordination Centre operations room; 
• Incident response and major events support.

International partnerships and development 

• Global partnerships with international organizations, governments, public and private sectors;
• Generation of revenue, donations and fundraising.

And although it's probably a good thing that there's an international effort supporting the law enforcement agencies targeting cyber-criminals, I really don't expect this particular organization to actually have much of an effect. That seems to be the nature of most government organizations. But in this case I'd love for the people at INTERPOL to prove me wrong. 

Why the TSA acts the way they do

There's an interesting interview with Kip Hawley, the former head of the much-reviled Transportation Security Administration, on the IEEE Spectrum web site. In this interview Hawley tries to justify some of the things that the TSA has done in recent years as being the legitimate result of reasonable risk management decision making. And although I'd really like to believe Hawley, my experience working for the US government leads me to believe that other explanations of the TSA's actions are probably more likely. But it's definitely an interesting interview that's probably worth reading (or listening to - there's also a podcast of the interview available, the link to which isn't working with this blog for some reason). 

Questionable HR practices yet again

It's probably appropriate that Munch's famous painting The Scream was just sold at action for a record $119.9 million. It's a good representation of how this article about how HR people are fighting a "war for talent" for information security professionals made me feel. The HR people are essentially saying that they want people who are top-notch experts in their fields with lots of deep knowledge. But then they also want those people to be flexible enough to do other things if they're needed. 

Things really don't seem to work very well that way.

HR people tried this back in the dot-com era, and what we learned was that almost all of your top-notch experts will quickly lose interest in working for you if you put them on projects that aren't related to their world-class expertise. So even if you somehow manage to attract good people, you'll probably be extremely unlikely to retain them for long if you do this. Maybe things have changed a lot from the dot-com era and your best people are very different from the ones back then, but I doubt that that's true.  

Best buffer overflow tutorial

Since I mentioned that I revisited buffer overflows on our recent Jack Bauer Day, I've been asked several times what the best way to learn about these is. My rule of thumb is that if I get asked the same thing often enough that I notice it that it's worth doing a blog post about it, so here are my thought on this.

I'd say that the single best way to learn about buffer [that used to say "beffer," which the spell checker oddly didn't flag as being an error] overflows is to worth through the dot-com era tutorial by the hacker that went by the name "Aleph One."

This tutorial is available here as well as other places on the Internet. And although I'd say that this tutorial's description of the segmented architecture of Intel x86 processors isn't as good as it could be, the rest of the tutorial is excellent. It walks you through exactly how buffer overflows work as well as the thought process involved in creating an attack that exploits one.

It doesn't really take that long to walk through the complete tutorial - maybe a couple of hours or so. And if you actually walk through it you'll almost certainly learn something interesting.

The last time I did this it turned out that you had to actually think a bit about what was going on. The tutorial gives detailed examples of code to write and tells you exactly what commands to use to compile it, but what I got wasn't exactly what the tutorial showed. This was actually good because it forced me to look at the differences. This forced me to actually pay attention to the material as I worked through it and this meant that I learned more than I would have otherwise. 

So if you have more that a very casual interest in buffer overflows and have an hour or two of spare time, I'd definitely recommend that you work through this material. You'll probably be surprised at how much you'll learn and how easy it really is to understand.  

Thinking about data-centric security

A breach in which hackers steal 1 million credit card numbers really isn't very exciting these days. You can actually expect to see at least one a month. It's only the very big ones that are newsworthy any more, and there's absolutely no reason to believe that this steady stream of big breaches is going to stop any time soon. 

The good news is that there is a way to solve this problem. The bad news is that doing it isn't easy. It will require a very different approach to protecting data and different IT architectures than are common today. But it's not impossible.

It's going to be hard work, but the alternative is to accept the fact that essentially all sensitive data is going to end up in the hands of hackers. 

The fundamental problem is that security is never perfect. Technology isn't perfect and the people who use it and administer it aren't perfect. The combination means that mistakes happen and that hackers sometimes get sensitive data. But the way in which technology has changed over the past couple of decades has probably made it worse for the security of sensitive information and the direction that technology is moving is probably going to continue this trend.

In the pre-dot-com days, business data typically lived its entire life in a mainframe that protected the data fairly well. The dot-com era saw this data move out of the mainframes and out to where it was more readily accessible by web-enabled applications. Now we’re seeing data move even farther out – into the cloud. At each of these steps there have been huge gains in efficiency, but it also seems that the data has become more vulnerable as this has happened.

And it’s not clear to me that we’ve made the choice to move sensitive data to more and more vulnerable locations fully realizing that when problems with either people or technology happen that more data tends to get lost from the vulnerable locations.

It’s unlikely that we’ll be able to get people to revert to the earlier, more secure architectures, so we need to find a way to work with the existing architectures to protect sensitive data better. The best way to do this is probably with so-called data-centric security, and if I can get people to stop asking me questions about GTH pants, I’ll say more about that tomorrow.

What type of pants?

After yesterday's post I've been asked several times what "GTH pants" are. I believe that the "GTH" stands for some phrase in French. I was terrible in languages in school, so I can't quite figure out what it stands for, but GTH pants are usually very brightly colored and often have unusual designs embroidered on them. Things like bright pink whales or neon green crabs. They're the sort of pants that most people wouldn't even think about wearing.

Unless you're in a contest with your friends to see who has the nerve to wear the most brightly colored and distinctive pants in public.

These contests were never actually openly discussed in any way, but it was clear when a contest was underway, who the eventual winner was and that the winner had earned the respect of his peers in a way that would be hard to do otherwise. There were also other unwritten rules to these contests. Even though your pants might be extremely outlandish, for example, everything else that you wore with them would easily have passed your school's dress code. And any comments on other people's pants had to be restricted to "Nice pants."

Some people seem to like GTH pants. (Note that these people seem to be exclusively men. Women seem to have the good sense to not do these sorts of things.) Lots of the people that I knew when I was younger fell into this category. Maybe it was peer pressure. Maybe it was just the lack of wisdom that often comes with being young. But in any event, I used to wear GTH pants from time to time and even enjoyed doing it.

Come to think of it, this may be why I don't mind talking about cryptography and elliptic curves these days, topics that most people find as annoying as bright green pants with pink whales embroidered on them.

So maybe the lesson to be learned here is that nothing that you do when you're young really ends up being wasted - it just ends up being useful in unexpected ways.

Has PKI met its Waterloo?

[In a previous post, I mentioned how blatantly reusing old blog posts is an idea that I should consider. A person with whom I was recently talking happened to mention how he didn't think that I would actually do that. This person clearly didn't know me when I was in younger, when I was a serious contender in the GTH pants contests that people that I knew would engage in now and then. So without any more explanation, here's a recycled post. Just cut and pasted to ensure that any spelling and grammar errors are also duplicated.

And, no, I don't still have any of my old GTH pants. The closest that I come these days is a pair of orange cargo pants, but they're nowhere near as, uh, distinctive as the madras and embroidered pants that we used to wear in the summer. And to fraternity parties.]

Public key infrastructure (PKI) has found few uses outside national governments due the high costs caused by its high complexity. Has PKI met its Waterloo in these factors?

As Napoleon's defeated Grand Armée withdrew from the battlefield at Waterloo, its retreat was covered by units from the Old Guard, part of a small, elite unit under Napoleon's direct control. The soldiers in this unit were the best and bravest veterans from his previous battles and the most feared soldiers in Europe. In addition to being Napoleon's personal bodyguards, these units were his weapon of last resort, and they were rarely committed in battle.

Eventually the Old Guard's position became untenable, and the English General Charles Colville offered them a chance to surrender and avoid being inevitably destroyed by the vastly superior numbers of Wellington's victorious army. The French General Pierre Cambronne is said to have replied to Colville's request, "La Garde meurt, elle ne se rend pas!" - "The Guard dies, it does not surrender!" Cambronne later denied having said this, but that didn't stop the words from being inscribed on the statue of him that was eventually erected in his home town of Nantes, and they have become one of the legends that are commonly associated with the battle of Waterloo.

Despite its questionable authenticity, Cambronne's defiant reply may be good inspiration for a rallying cry that may be appropriate for supporters of public-key infrastructure (PKI) technology: "PKI dies, it does not surrender!" Except for the single use in implementing SSL, the use of encryption to identify servers and encrypt connections to them, PKI has proven to be extremely difficult to use and expensive to support, but its dedicated advocates insist on continuing its use to the bitter end. They even continue to support its use in the face of many newer technologies that are just as secure, more user-friendly and have a much lower total cost of ownership. PKI's proponents seem to never surrender.

PKI technology was a very innovative idea when it was first introduced. The digital certificates that PKI creates and manages provide the basis for authentication, digital signatures and encryption, all of which are very useful to have. Unfortunately, PKI also turned out to have many practical problems that its inventors didn't anticipate. These practical difficulties made it too difficult for the average user to use, which then resulted in very high support costs. So although it had an extremely promising start, it turned out to be unsuitable for most uses, the most notable exception being the use by government organizations.

Governments have an entirely different set of priorities than commercial enterprises: while businesses need to be profitable in order to survive in the long run, government organizations do not. Staying profitable is of utmost concern to businesses; spending their budgets and keeping people employed are among the highest priorities of most governments, and costs are relatively less important. So while most businesses found PKI to be unsuitable for widespread use, governments didn't find its high costs objectionable. This has led to almost all of the use of PKI being confined to governments and government contractors. And despite the high costs of doing it, governments have continued to move ahead with expensive PKI projects, with the American government alone having spent over $1 billion on the technology to date.

But while this has happened, many recent innovations have made it possible to provide the same benefits that PKI once promised, but at greatly reduced costs. Encrypted e-mail, for example, has recently become fairly popular due to heightened regulatory compliance concerns, so it has become much more widely deployed than it was just a few years ago. But if you look at the secure e-mail solutions that are commonly used today, you'll find that they're usually not based on PKI. Even if a solution does support PKI, that mode of operation is rarely used by customers. But while the use of newer technologies for encrypted e-mail has boomed, governments have continued to use PKI to provide this capability, perhaps attracted by its superior ability to help them spend their budgets and keep additional people employed.

Cost that is caused by unnecessary complexity may turn out to be the battle that PKI can't win when it's pitted against these newer technologies, so it may be somewhat appropriate to refer to it as "PKI's Waterloo." But because its supporters seem to have been inspired by Cambronne's legendary reply to Colville, it may be quite a while until we finally see them admit defeat.

On the other hand, Waterloo was the first time that Napoleon's Guards retreated without being ordered to do so. Perhaps supporters of PKI will suffer a similar change of heart, realize that their battle can't be won, and give governments a chance to realize the same cost savings that the commercial world has already experienced. We can only hope that this happens soon. Although it's often attributed to him, American senator Everett McKinley Dirkson never actually said, "A billion here, a billion there, and pretty soon you're talking real money," but it gives an idea of the savings that this might allow.

Much Ado About Nothing

Attention developers: You must set your text editor to tabs-at-8. There's nothing to discuss, no other viable option, and anything else would be crazy. If you're writing in Python, that is. I only recently discovered this fact, and it adds a new wrinkle to the mostly decomposed dead horse known as The Tab Wars.

For those who aren't familiar with Python, it has the distinction of being one of very few computer languages in which white space is significant. Specifically, the indentation of the code determines the block structure; there are no braces or other clutter to tell the interpreter otherwise. It takes a little getting used to, but is actually quite nice. "Then what about tab characters?" I wondered one day.

For the indentation to be unambiguous, the language must know how to interpret a tab character relative to spaces, and Guido chose tabs-at-8, presumably because that was and remains the most common defacto standard (more on that later).

So let's say you are working on some python code that looks like this:

You're thinking, Cool, I get a bonus! But, as it turns out, you have your tabstop setting at 4, not 8, and moreover the code has been edited by a variety of people with a mix of tabs and spaces and what you really have before you is this mess:

Now we know that python uses tabs-at-8, by definition, so what it will actually see and do is:

and you will only get your bonus when pigs fly. And that's just not right.

How did we come to this? What can we do about it? Sit right down and you'll hear a tale.

Eons ago, early hominids produced text on mechanical devices known affectionately as "type writers". Many of these devices included a cool feature whereby little "tabs" of metal could be put at various places along the "carriage" (the thing holding the "paper") and a special key (the "tab key") would cause the carriage to advance to the next such tab. This was very handy for lining things up vertically (itself an ancient artform, largely forgotten, but I digress).

About one eon ago, things got all modern and teleprinters (literally: print from afar) appeared, followed a few short decades later by the American Standard Code for Information Interchange—the ASCII we know and love to this day. Among it's 128 codes are 33 control codes, most of which are far too powerful and unstable to be used anymore, but Code 9 is our friend The Tab. More properly, the Horizontal Tab (HT), because there is also a Vertical Tab (VT) but let's just pretend there isn't. The tab codes were intended, and in fact used, to cause printing to jump to various places that had been manually configured into the teleprinter for a particular print run—so things would line up nicely on pre-printed forms and whatnot. But people soon realized that this was insane and they stopped doing it.

Now while they could have just used ASCII 32's (space characters) to position things, apparently it seemed too much of a shame to abandon an entire control code, so instead they decided, not entirely formally, that henceforth Code 9 would mean "advance to the next multiple of 8 characters on the current line"—what we today call "tabs-at-8". This also provided a nice 8:1 compression of whitespace, something that mattered to people when each bit cost several dollars to store or send.

"Why 8?" you ask. Interestingly enough, the value 8 was chosen by Satan, because he could see the future and likes to cause trouble.^{[citation needed]} So tabs-at-8 was then widely adopted and for years and years countless computer programs (and programmers) simply assumed that that was what ASCII Code 9 had always meant and would always mean.

Then things got even more modern and someone realized that it wasn't terribly difficult for a given text program to let a User (we've heard about them) select how many characters a tabstop should be! Whoohoo, by simply changing an editor setting you could instantly... mess up all your indentation? Make your text file randomly incompatible with various other programs? I really don't know what the point was but someone thought it was really cool, and the idea spread like hoola hoops in the late 50's.

Despite the Tabs Liberation movement, tabs-at-8 remained a standard of sorts, including things like HTML, CSS, most Unix utilities, and of course the Python programming language, to name a few. So of course the idea of user-selectable-tabstops faded away, everyone settled into living with the devil's tabs-at-8, ASCII files were universally unambiguous, and there's nothing more to say, the end. Well, not quite.

As it happen, we can still find one small exception to the de facto standard interpretation of ASCII code 9 as a horizontal tab aligned on 8-character boundaries. In the mid 1970's a young college dropout started a company called Microsoft. This company has since risen to some prominence in the field of software development, and the designers of its flagship development environment—Visual Studio—were struck by the overwhelming beauty of tabstops matching indentation. Additionally they could see the sheer godliness of indentation at 4 chars. Ergo: Visual Studio comes preconfigured with tabs and indentation set to 4 for all languages. All but XML, that is, which is set to 2 and 2 for reasons I don't want to try to imagine. And of course for Python it... oh, there's no Python configuration for the VS editor. Never mind.

Of course it's very easy to just say "Microsoft is evil". It's also fun, try it! But MS evil or no, countless hoards of developers work in Visual Studio daily, using the editor defaults, because, after all, where are these settings anyway? And they enjoy the sheer godly beauty and perfection of tabs at 4, indentation 4 and all is Good and Just in their sight. If only Everyone could share in this beauty and join with them in peace and harmony oh what a wonderful ASCII world it would be.

Sadly, for some reason there remain hundreds—perhaps thousands—of developers who simply refuse to do all their work in Visual Studio. I can't explain why this is, but they are stubborn. More often than not these troublemakers will not have tabstop set to 4 in their editors. They might even have their editor set to insert spaces instead of ASCII 9 codes. In fact, it turns out in the end that the only way to defeat Satan's tabs-at-8 trickery is precisely to set your editor to never allow those Code 9's into your file in the first place! Replace tabs with spaces. ASCII code 32 is, after all, the only unambiguous sort of space you can put in an ASCII file.

Still, if you are fortunate enough to live in a 100% Pure Microsoft Development World—and you never code in Python—then you are free to retain the myriad and compelling benefits of tabs 4, indent 4, keep tabs. It's a lovely thing and I'm sure you will be very happy, and you'll barely hear Satan laughing if you plug your ears and go la-la-la-la-la. Everyone else will have to suffer with Insert spaces, with whatever indentation is suitable for the language they happen to be using. And they'll survive. Just please be nice and don't touch their code.

One final thing. It pains me but I am compelled to mention the one glaring exception to the No ASCII Code 9's rule: Makefiles. The Makefile grammar specifically requires that ASCII Code 9 be used to introduce command lines; spaces simply will not do. As wikipedia gently states: "This aspect of the syntax of makefiles is often subject to criticism." Count me in on that.

Maybe later we can explore end-of-line characters.

Buffer overflows are cool

Yesterday was one of our quarterly Jack Bauer days, where for 24 hours we (at Voltage) can do anything that we want to do. This time I decided to look at buffer overflows again, and this turned out to be lots of fun.

It had been so long since I had taken a close look at these attacks and how to implement them that I had forgotten most of the tricks, so I got to relearn and rediscover all sorts of interesting things yesterday. I suppose that's one of the big benefits of having an imperfect memory - you get to experience the fun of learning new and exciting things more than once.

So the big lesson of the day (for me) was that although bow ties may be cool, buffer overflows are even cooler.

Implementing cryptographic pairings: a magma tutorial

If you're trying to understand how to implement a pairing, like you might need to do if you're going to implement one of the many forms of pairing-based cryptography, there's a good tutorial available here that's based on the 2009 paper Implementing cryptographic pairings: a magma tutorial by Luis J Dominguez Perez, Ezekiel J Kachisa, and Michael Scott that's available here.  This tutorial seems to do a reasonable job of walking you through the basics of how to calculate a pairing and includes lots of useful magma implementations, but it seems a bit inaccessible to someone who doesn't already know how to implement a pairing.

But that's a very hard problem to overcome. There's a big learning curve involved with getting up to the point where you understand pairings well enough to implement one. I'd say that it probably took me 80 hours or so of reading and thinking about what I had just read before I could comfortably implement the Tate pairing. (Other, smarter people can probably do it in less.) The tutorials that are available on-line these days (like this one) can probably reduce the effort involved in doing this, but I'd still expect it to be a fairly difficult step to make for the first time.

Returning to our regularly-scheduled programming

As many people have noticed, I haven't actually posted anything in a while. Here's roughly why.

Last year at one of meetings of my sons' Boy Scout troop, while shaking hands to say hello to the other fathers who were there, I noticed that the men who had white-collar jobs had extremely weak grips compared to the men who had blue-collar jobs. Being one of the relative weaklings, I decided to see what I could do to get a stronger grip and eventually came across Ironmind's Captains of Crush grippers. The strongest of these, the Number 4, is so hard to close that only a few people have ever done it, and they're the sort of people who win the World's Strongest Man competition. 

I decided on a more modest goal: working up to closing the Captains of Crush Number 1 gripper. After a month or two of training on hand grippers things were going quite well. I couldn't crush a potato in my hand yet. You need the strength needed to close the Number 4 for that. But I was getting noticeably stronger.

But then the ligaments in my hand decided that they had had enough and to let me know that they felt this way they caused extreme pain in my hands if I made common motions with them. Including typing.

Having participated in all sorts of sports as a kid (and being stunningly mediocre in all of them) I've had lots of sports-related injuries over the years, but I was still quite surprised by the reaction of my hands' ligaments, and it ended up being much more painful and taking much longer to recover from than I would have expected. 

But now that the hands are back in reasonable condition, I'll be able to start blogging again. I even have lots of hand-written notes of things that I need to blog about, so we'll be able to return the regular blogging schedule soon. Next Monday at the latest.