Superconductor

Classic interactive fiction and standards meetings

Before PCs had the flashy graphics that they have today, computer games were much different. Back in the '70s and '80s, the most popular type of computer game was interactive fiction, like the classic games Adventure and Zork. If you've a fan of these games, then the following ought to look familliar:

YOU ARE STANDING AT THE END OF A ROAD BEFORE A SMALL BRICK
BUILDING . AROUND YOU IS A FOREST. A SMALL
STREAM FLOWS OUT OF THE BUILDING AND DOWN A GULLY.

Before the days of the Internet, college students had to find other ways to waste time instead of studying, and interactive fiction was one of the most popular ways to do this, at least with students studying science or engineering.

One of the more memorable interactive fiction games was Bureaucracy. In this game you tried to get to Paris for the weekend, but ended up being thwarted by bureaucratic obstacles at every step in your journey. The part that I remember most clearly about Bureaucracy is it's innovative scoring system. As each bureaucratic obstacle thwarted you, the score that represented your blood pressure increased. If it got too high, you'd die and lose the game.

Bureaucracy was the only Infocom game that I bought but never actually finished.

The title of this post is "Classic interactive fiction and standards meetings," but I think that the reason for that should be fairly clear at this point, so I won't bother explaining it in more detail.

Degenerate elliptic curves

Suppose that we have an elliptic curve of the form

y² = 4 x³ - g₂ x - g₃

Many mathematicians require that the right hand side of that equation have no repeated roots and insist that you really don't have an elliptic curve if this happen. The benefit of doing this is that it saves a few words. If you don't do that then you need to be careful to say something like a "non-singular elliptic curve" instead of just an "elliptic curve" in most contexts. Because this post is about the cases where you have repeated roots, I won't follow this convention here.

What happens if we do have repeated roots?

Two repeated roots

For an example of this, consider the elliptic curve

y² = 4 (x - 1)² (x + 2)

= 4 x³ - 12 x + 8

or where

g₂ = 12

and

g₃ = -8

This corresponds to the Weierstrass ℘-function with periods

ω₁ = -π i / √3

and

ω₂ = ∞

or really only being having one period instead of two. If we plot the magnitude of this ℘-function, this is fairly obvious. Here's what that looks like.

Three repeated roots

There's essentially only one way to get three repeated roots, and that's the case when we have an elliptic curve that looks like

y² = 4 x³

or that

g₂ = g₃ = 0

If that happens, the ℘-function shows no periodic nature at all. Here's what a plot of its magnitude looks like in this case:

 

From the post a few days ago, we can see that in this case we have to have

℘(z) = z^-2

which explains the shape of this graph. We also have to have

℘′(z) = -2 z^-3

When we think of (x, y) as coming from (℘(z), ℘′(z)), we see that we have

y² = 4 x³

when this happens.

More interesting elliptic curve stuff

It turns out that we can easily tell some things about an elliptic curve of the form

y² = 4 x³ - g₂ x - g₃

Suppose that we get this elliptic curve from the Weierstrass ℘-function with periods ω₁ and ω₂. Then it turns out that we we can also write this elliptic curve as

y² = 4 (x - x₁)(x - x₂)(x - x₃)

where

x₁ = ℘(ω₁ / 2)

x₂ = ℘(ω₂ / 2)

and

x₃ = ℘((ω₁ + ω₂) / 2)

For an example of this, consider the elliptic curve

y² = 4 (x - 1)(x - 2)(x + 3)

= 4 x³ - 28 x + 24

which we get from the Weierstrass ℘-function with periods approximately

ω₁ = -1.48441 i

and

ω₂ = 2.01891

In this case, we find that 

℘(ω₁ / 2) = -3

℘(ω₂ / 2) = 2

and

℘((ω₁ + ω₂) / 2) = 1

Adding points on an elliptic curve

An interesting identity that can be proven for the Weierstrass ℘-function is that

det

℘(z1) ℘′(z1) 1 ℘(z2) ℘′(z2) 1 ℘(z1+z2) -℘′(z1+z2) 1

=

0

If we think about this for a while, we see that this is explains why addition of points on elliptic curves works the way it does. Here's why.

A fact that's usually covered in high-school algebra classes is that

det	x1 y1 1 x2 y2 1 x3 y3 1	=	0

if and only if the three points (x₁,y₁), (x₂,y₂) and (x₃,y₃) are colinear.

Now from the point of view of the correspondence that we saw in the previous post that identified the complex number z with the point (℘(z),℘′(z)) on an elliptic curve, let's write

P₁ = (℘(z₁), ℘′(z₁))

P₂ = (℘(z₂), ℘′(z₂))

and

P₃ = (℘(z₁+z₂), ℘′(z₁+z₂))

So the property of the ℘-function that's shown above tells us that although the points P₁, P₂ and P₃ aren't colinear, if we reflect P₃ across the x-axis to get -P₃, then we get three points that are.

So to find P₃ from P₁ and P₂, we need to first find the third point where the line that connects P₁ and P₂ intersects the elliptic curve. This point will be -P₃. Once we find that point, we reflect it across the x-axis to get P₃.

If we do this, we add the point P₁ that we get from z₁ to the point P₂ that we get from z₂ and get the point P₁ + P₂ = P₃ that we get from z₁ + z₂. In other words, adding points on an elliptic curve is really just adding complex numbers, but hidden by the mapping that takes z to the point (℘(z),℘′(z)) on the elliptic curve.

An example

For an example of how this works, let's look at the elliptic curve

y² = 4 x³ - 4x + 4

which we get from the Weierstrass ℘-function with periods approximately

ω₁ = -2.19658 i

and

ω₂ = 2.35354 + 1.09829 i

We have these two points on the curve

P₁ = (-1,2) = (℘(z₁),℘′(z₁)) for z₁ = 0.291202 + 1.09829 i

P₂ = (0,3) = (℘(z₂),℘′(z₂)) for z₂ = 0.73997 + 1.09829 i

for which we find that

P₃ = P₁ + P₂ = (1,-2) = (℘(z₃),℘′(z₃)) for z₃ = 1.03117

We also find that we have that

z₃ ≡ z₁ + z₂ (mod ω₁, ω₂)

just like we would expect to see.

Parameterizing elliptic curves

Here's an example of parameterizing an elliptic curve of the form

y² = 4 x³ - g₂ x - g₃

using the Weierstrass ℘-function.

Consider the elliptic curve

y² = 4 (x - 1)(x - 2)(x + 3)

= 4 x³ - 28 x + 24

This is a handy elliptic curve to use because we can easily see where its graph crosses the x-axis, etc. Identifying this with

℘′(z)² = 4 ℘(z)³ - g₂ ℘(z) - g₃

we have that

g₂ = 28

and

g₃ = -24

To plot the graph of this elliptic curve when it's parameterized as (℘(z), ℘′(z)) we first need to find the periods ω₁ and ω₂, which we can find from g₂ and g₃. Those turn out to be approximately

ω₁ = 1.48441 i

and

ω₂ = 2.01891

Here's what the magnitude of the corresponding ℘-function looks like over a few of its periods (graphed using Mathematica, as usual).

If we then plot the graph of (℘(z), ℘′(z)) as z goes along the real line from 0.7 to 1.4,  we get the following graph, which is the graph of y² = 4 x³ - 28 x + 24:

 

Another example

Doing the same thing for

g₂ = 4

and

g₃ = -4

and plotting the graph of (℘(z), ℘′(z)) as z goes along the real line from 0.7 to 4.0 we get this, which is the graph of y² = 4 x³ - 4 x + 4:

That's definitely another elliptic curve.

Why elliptic curves make sense

The way in which we can add points on an elliptic curve is often presented in a way that doesn't explain at all why adding points in that way makes sense. Adding points can roughly be summarized like this:

1. Draw a line through the two points that you want to add together
2. Find the third place where this line intersects the elliptic curve
3. Reflect that point across the x-axis and call the resulting point the sum of the first two points

Doing this actually makes perfect sense, but seeing why requires looking at a particular elliptic function called the Weierstrass ℘-function.

An elliptic function is a function of a complex variable that's doubly periodic: it has two periods instead of one. This means that we have both

f(z ) = f(z + ω₁)

and

f(z) = f(z + ω₂)

for complex numbers ω₁ and ω₂. 

It turns out that the function defined by

℘(z ) = z^-2 + Σ [ (z - ω)^-2 - ω^-2]

where the sum is over all ω = n₁ω₁ + n₂ω₂ not equal to zero, is an elliptic function with periods ω₁ and ω₂, and this particular elliptic function is called the Weierstrass ℘-function.

If we write

G_k = Σ ω^-2k

where the sum is over all ω = n₁ω₁ + n₂ω₂ not equal to zero, we find that we can write

℘(z) = z^-2 + 3 G₂ z² + 5 G₃ z⁴ + ...

and

℘′(z) = -2 z^-3 + 6 G₂ z + 20 G₃ z³ + ...

and that we can use these to find that we have that

℘′(z)² = ℘(z)³ - 60 G₂ ℘(z) - 140 G₃

For historical reasons it's traditional to write

g₂ = 60 G₂

and

g₃ = 140 G₃

so that we have that

℘′(z)² = ℘(z)³ - g₂ ℘(z) - g₃

If we write

 y = ℘′(z)

and

x = ℘(z)

we then have

y² = 4 x³ - g₂ x - g₃

which is just a quick change of variable away from the form that we usually see for an elliptic curve:

y² = x³ + a x + b

So it looks like we can parametrize an elliptic curve using the ℘-function just like we can parametrize a circle

x² + y² = 1

as

cos²t + sin²t = 1

using the usual trigonometric functions.

And just like understanding the properties of the trig functions tells us how to understand what's happening on a circle, understanding the ℘-function tells us how to understand what's happening on an elliptic curve. Like the addition of points.

More on that tomorrow.

Video of relay attack on a smart card

I just came across an interesting video clip yesterday. This clip shows a relay attack on a chip-and-PIN smart card that lets attackers perform fraudulent transactions. It's definitely proof that nothing is as secure as you think it is. Not even hardware-based cryptography.

A relay attack lets an adversary impersonate someone else during an authentication protocol. To do a relay attack, an adversary doesn't need to understand the underlying authentication protocol. If the authentication protocol is based on cryptography, they don't need to worry about the cryptography at all.

Relay attacks aren't a new idea. They've been known at least since 1976 when John Conway mentioned the idea in his book On Numbers and Games.  Here's a rough idea of how a relay attack works.

Suppose that I'm sitting in my car in the parking lot and you want to open the door to my office using the proximity card in my wallet. To do this, you get the door to issue the challenge that it issues to proximity cards when they're used to open it. You collect this wireless signal from a place close to the door and pass the signal to a friend manning another transmitter close to my car. The second transmitter passes the challenge to my proximity card and then passes the response from my card back to you where you use the response to authenticate to the door.

It's not much more complictated than that to do a similar attack against some smart cards that use a cryptographic challenge-response protocol. That's what's shown in this video.

In a relay attack on a chip-and-PIN smart card, you can't just intercept wireless signals like you could do with a relay attack on a proximity card. In this case you need to control a PIN entry device as well as a smart card that's modified to carry out the attack. 

A PIN entry device probably isn't too hard to get. You can get almost anything on eBay these days, after all. On the other hand, the modified smart card isn't something that's likely to go unnoticed. Most merchants will probably figure out that something's not right if you try to make a purchase with a smart card that has wires coming out of it that attach to a nearby laptop. But even if this attack isn't something that we'll probably see cybercriminals using on a wide scale, it definitely shows that designing secure systems is hard.

Was he really talking about PKI?

It's a vestige of the old superstitious Dark Ages when nobody knew anything and the whole world was sinking deeper and deeper into filth and disease and poverty and ignorance. It is one of those delusions that isn't called insane only because there are so many people involved.

Robert Pirsig, Lila

Key Management Summit - deadline for submissions approaching

The deadline for submissions for the 2010 Key Management Summit is rapidly approaching - you have until December 31 to submit proposals for talks, panel discussions, etc. That's not that far off.

Like the weasel-wording that you often see in financial statements says, past performance is no guarantee of what the future will bring, but if the 2010 Key Management Summit is anything at all like the previous one, then the 2010 meeting will be fairly good. The last one was actually one of the best meetings of its type that I've been to in the past several years.

Like the meeting's web site says:

Topics include, but are not limited to:

• Standards efforts relating to key management
• Government policies around key management
• Customer case-studies
• Panel discussions
• Key management technologies (avoid specific vendor references when possible)

If you have anything interesting to say in any of those areas, there's not much time left for a chance to tell other fans of key management what you know.

Google AdWords for the Key Management Summit

Because I'm on the program committee for the 2010 Key Management Summit, I knew that there's a Google AdWords campaign happening now to increase awareness of the event. Despite this, I was surprised to see the following ad when I last read my Gmail:

Key Management Summit - 2010.KeyManagementSummit.org - IEEE Conference on Encryption Lake Tahoe, NV. May 3-7 2010

While I'm probably the right kind of person to target with this ad, I have to wonder exactly how Google chose to show it to me. I don't get work-related email at my Gmail address, and the email that's in my Gmail Inbox right now is stuff like announcements of end-of-year sales that various small presses are having (up to 75 percent off in some cases), information about my kids' Boy Scout camp for next Summer, and confirmations that various Christmas gifts have shipped. There's nothing there that's even remotely related to encryption or key management.

Maybe the logic behind AdWords is even more clever than you might first think. Or there might be terms like "encryption" or "key management" hidden somewhere in those emails about Christmas gifts.

Linear recursions and geometric series

As I mentioned in a previous post, one way to look at a linear recursion is as a matrix. When you do this, it's natural to think about the eigenvalues and eigenvectors of that matrix, and the eigenvectors turn out to be the initial conditions for the recursion that get it to greate a geometric series. We can use this fact to create an nth order recursion that creates n different geometric series of our choice, with the particular series being created determined by the initial conditions of the recursion. So if we pick any two numbers, it's possible to find a single second-order linear recursion that we can make create a geometric series with our chosen numbers as the ration of consecutive terms. Which ratio we get is determined by the initial conditions for the recursion.

Suppose that we write the recursion

x_n = a_k-1 x_n-1 + … + a₁ x_n-k+1 + a₀ x_n-k

as

xn-k+1 ... ... xn

=

0 1 ... 0 1 a0 a1 ... ak-1

xn-k ... ... xn-1

If λ is a solution to

x^k – a_k-1 x ^k-1 - … - a₁ x – a₀ = 0

then

1 λ ... λk-1

is an eigenvector that corresponds to the eigenvalue λ, and this eigenvector is also the initial state that turns the recursion into a geometric series: if we have

x₀ = 1, x₁ = λ, x₂ = λ², …, x_k-1 = λ^k-1

then we’ll always have x_n = λⁿ.

This means that for an nth order recursion, we can pick any n values λ_i (which are exactly these eigenvalues), and find initial conditions for the recursion such that x_n = λ_iⁿ. The eigenvectors are the initial conditions that do this, and they get the recursion to create a geometric series with the ratio between successive terms being the eigenvalue which corresponds to the eigenvector. It's also easy to write down the recursion that does this for us. In particular, if the eigenvalues are the roots of

x^k – a_k-1 x ^k-1 - … - a₁ x – a₀ = 0

then the recursion

x_n = a_k-1 x_n-1 + … + a₁ x_n-k+1 + a₀ x_n-k

does this for us.

An example

Suppose that we want to find a second-order recursion that will create either the series

x_n = (-2)ⁿ

or

x_n = 3ⁿ

This corresponds to having

λ₁ = -2

and

λ₂ = 3

for the zeroes of

(x - λ₁) (x - λ₂) = (x + 2) (x - 3)

= x² - x - 6

so that the recursion

x_n+2 = x_n+1 + 6 x_n

will do this for us.

The initial conditions

x₀ = 1

and

x₁ = -2

give

x_n = (-2)ⁿ

and the initial conditions

x₀ = 1

and

x₁ = 3

give

x_n = 3ⁿ

Blogging at Despair.com

It looks like the fine people at Despair.com have some interesting gifts that are particularly suitable for bloggers.

You can get the poster "Blogging" that has a picture of what appears to be part of Utah's canyonlands along with this text

Never Before Have So Many People with So Little To Say Said So Much To So Few

If that's not worth $15.95 plus shipping and handling, you can always get the t-shirt instead. For only $18.95 plus shipping and handling you can get a t-shirt that says

MORE PEOPLE HAVE READ THIS SHIRT

THAN YOUR BLOG

0000002

The Fibonacci sequence, the golden ratio and Egyptian fractions

It turns out that there's a way to use the Fibonacci sequence to write the golden ratio in terms of Egyptian fractions. Here's how.

If we write the Fibonacci sequence as

f(n + 2) = f(n + 1) + f(n)

then we can write

f(n) = (aⁿ – bⁿ) / (a – b)

where

a = (1 + √5) / 2

and

b = (1 – √5) / 2

Using this form of f(n) it's easy to show that

f(n)² – f_n+1 f_n-1 = (-1)^n-1

which we can rewrite as

f_n+1 / f_n = f_n / f_n-1 + (-1)^n-1 / (f_n f_n-1)

But we also have that

f_n / f_n-1 = f_n-1 / f_n-2 + (-1)^n-2 / (f_n-1 f_n-2)

so that

f_n+1 / f_n = f_n-1 / f_n-2 + (-1)^n-2 / (f_n-1 f_n-2) + (-1)^n-1 / (f_n f_n-1)

If we keep making similar substitutions, we find that we get that

f_n+1 / f_n = f₂ / f₁ + 1 / f₁ f₂ - 1 / f₂ f₃ + … + (-1)^n-1 / f_n-1 f_n-2

The golden ratio a is the limit of f_n+1 / f_n as n gets large, so we have that

a = f₂ / f₁ + 1 / f₁ f₂ - 1 / f₂ f₃ + 1 / f₃ f₄ + …

= 1 + 1 - ¹⁄₂ + ¹⁄₆ - ¹⁄₁₅ + ...

Each of the terms in this sum happen to be fractions of the form ¹⁄_n for some integer n, which are exactly the so-called Egyptian fractions. Apparently, the classical Egyptians used only fractions of that form, plus the single additional fraction ²⁄₃, to represent all rational numbers.

If you try to actually do a few computations with Egyptian fractions, you'll probably come to the same conclusion that I did: that representing rational numbers this way is probably one of the greatest technical blunders of all time.

In any event, the above representation for the golden ratio that we got from the Fibonacci sequence is actually a way to represent it as a sum of Egyptian fractions. Yet another aspect of the Fibonacci sequence that I didn't expect.

Certificate-based authentication

Authentication is one of the big uses that's often hypothesized for PKI, and if you had to pick a use outside of SSL where PKI might actually succeed one day, authentication is probably a good one to pick. Using certificates for authentication avoids the troublesome discussion about whether or not you really have non-repudiation that you often get when certificates are used for digital signatures. You also avoid the headaches that accompany using certificates are used for encryption, like key recovery and key lookup.

On the other hand, authentication is also the case where I've seen certificates misused most often. This is probably, at least in part, due to the careless way that people often talk about using certificates. I've even done that here, haven't I?

People often talk about using a certificate to authenticate a user. This has led to more than one case where a certificate is attached to a message as an authentication credential. The recipient then checks the name in the certificate. If it says Alice, then the message is assumed to be from Alice.

This is absolutely useless as a means of authentication. Despite this, I've seen this done more than once. Other security people that I've talked to often have similar stories about seeing it.

A digital certificate carries a user's public key, which is, well, public. Because of this, it's reasonable to assume that Eve can get Alice's certificate and attach it to a message just as easily as Alice can, which means that using a certificate in this way isn't providing any useful authentication at all. Or it's just as useful as using other public information as a means of authentication.

A better way to use an authentication certificate is as part of a protocol that proves that a user has the private key that corresponds to the public key in the certificate. In addition to defining the format of certificates, the X.509 standard actually describes how to do this. Doing this is much trickier that just attaching a certificate and checking the name in it. On the other hand, it's also much more secure. So if someone says that they're doing "certificate-based authentication," it's probably worth asking for more details about exactly how they're doing this. It may not be as secure as it first sounds.

A trend in education?

There seems to be a trend in education where material that's cutting-edge research first gets taught in graduate-level classes and then, several years later, in undergraduate classes. Some even makes it into high-school classes. When my father went to college, for example, quantum mechanics hadn't made it into undergraduate classes yet, buy the time I was in high-school it had worked its way into the chemistry class that I had. I may have come across an even more extreme example of this last week.

I noticed that the book Special Relativity, part of the MIT Introductory Physics Series, is listed on Amazon.com as being written at a level suitable for "young adults." That's the same audience that The Hobbit is apparently suitable for. Or Brian Jacques' Redwall series.

If special relativity is now suitable for young adults, I'd hate to guess where they're teaching quantum mechanics these days. Or cryptography.

Is it profitless to use stronger keys?

Security should result in zero profit, but from an economic point of view, not an accounting point of view. Economists define profit as the difference between revenue and opportunity cost, where opportunity cost is the value of the next-best choice. As economist and comedian Yoram Bauman likes to point out, if someone gives you a candy bar that’s worth a dollar, your profit from that transaction is a dollar. But if they offer you the choice between two identical candy bars, your profit is zero, the value of the one that you pick minus the value of the one that you don’t pick. This means that it’s easily possible to show a profit from the accounting point of view yet have a zero or negative profit from the economic point of view.

So it should be clear that if we’re allocating resources to various information security projects, we should end up in a similarly profitless situation. If we don’t end up there then we could have allocated our resources better, so we should go back and reallocate things.

I was recently thinking about this in the context of the push to move to stronger cryptographic key that’s happening now. Today, a 1,024-bit RSA key is considered adequate for most uses, but soon, using 2,048-bit RSA keys will be considered a best practice.

Is it really worth doing this? Is doing this profitable in the sense that economists use?

The work needed to crack those 1,024-bit keys that we’ll soon be phasing out is extremely high, so an attacker always has a better alternative than trying to defeat the cryptography. These other forms of attacks don’t go away if you move to a 2,048-bit key. They’re still there, and they’re still the preferred approach for hackers to use. This means that when we upgrade to the 2,048-bit keys, the systems that use them really aren’t any more secure than they were when they were using the 1,024-bit keys because hackers will never actually try to beat the cryptography. All that we’ve really done is to add cost and complexity to our system, but we’ve added no additional security when we’ve done this.

(This was actually noted by Adi Shamir in the lecture that he gave when he won the Turing Award in 2002. One of his Three Laws of Security is that cryptography is typically bypassed, not beaten. Come to think of it, that's probably a better starting point for thinking about this, but people tell me that blog posts should reflect your train of thought instead of being more carefully written, so I won't go back and redo this from the better point of view.)

There will always be someone out there who will says scary things like “Using anything weaker than the strongest possible cryptography borders on criminal negligence!” but they’re usually not the ones who need to balance the cost of security and the benefits that it provides.

Upgrading to longer keys may seem fairly simple. It might be no more effort than changing a setting on a server. That’s all there is to it with Voltage’s products. But there are always other costs to consider. Those bigger keys take more computing power to handle, for example. You can expect the computing time of the operations that public-key cryptography uses to scale roughly like the cube of the key length, so if you double the key length, you’ll probably use about eight times the computing power to carry out the operations with the longer keys. There are also often issues with compatibility with the older keys that appear after a while. All of these issues cost money to address. On the other hand, using these longer keys doesn't really increase the security of your system.

If you’ve already taken care of all of the other threats that your organization faces then maybe it’s worth worrying about upgrading to longer keys soon. If you haven’t, doing it now seems like a profitless venture.

How to protect test data

Like I mentioned in a previous post, many things are more complicated than you first think. Testing IT systems that handle sensitive data is a good example of this.

You probably don't want to use real data in testing because of the compliance issues that it can cause. On the other hand, you also want your test data to be as much like the real data as possible to make the results of any testing reflect the behavior of the system under real conditions as much as possible. This is actually tricky to do.

It looks like our marketing guys have put together a webinar that talks about how to solve this very problem, so if this is of interest to you, you might want to consider checking it out. You can sign up for it here if it sounds interesting.

Her's a quick summary of this webinar:

Securing Confidential Data in Non-Production Environments
End-to-End Data Protection for Test, Development and Outsourced Systems

Date: December 9, 2009

Time: 10 am PST / 1 pm EST

Duration: 60 minutes

This webinar doesn't have as clever a name as the last one that we had (The Renaissance of Enterprise Key Management and the Barbarian Hordes), but I'm sure that it will contain lots of useful information.

The limits of provable security

I've never quite understood the objections that people have to cryptographic schemes that are provably secure. If you have a proof of security then one of two things must be true: either the scheme is secure or there's a flaw in the proof. There's no other possible case.

All of the technologies that Voltage's products use have such proofs. The Boneh-Franklin IBE, the Boneh-Boyen IBE and our format-preserving encryption technology all have such proofs that have been published in peer-reviewed research journals. Because of this, I often don't understand the questions that I sometimes get about the security of our technologies.

Here's a situation that I've seen more than once. Someone asks about the security of our FPE technology, for example. We'll point them to the paper by cryptographers John Black and Phil Rogaway that has a proof for the security of the scheme. The next question is essentially, "But why should I believe that it's secure?" At that point, I'm never quite sure what to say next. If you have a proof in front of you, then either the proof is correct or there's an error in the proof. If this proof is of the security of a cryptographic scheme, then either the scheme is secure or there's an error in the proof. As mentioned above, there's no other possible alternative.

My recent experiences have led me to believe that there's a fundamental problem with this approach, and that's because many people really aren't comfortable with the idea of a proof. I've seen many cases recently where people essentially accept P and NOT P at the same time and don't seem bothered by doing this.

Every time I see this, I start thinking about the logical implications of it. After all, if you accept both P and NOT P then you can prove that absolutely anything is true. "If 2 = 3 then all cats are dogs" is absolutely true, for example. But because many people either don't understand this or don't believe this, I've come to the conclusion that proofs of security really aren't that useful. They may help specialists make sure that their work is correct, but to non-specialists they really don't say anything useful.

Blog to book software

A few people have asked me about me creating a hardcopy book from the contents of this blog. Trying to find things to do other than look for errors in a math-heavy standards document, I recently tried out a couple of the available services that let you do this to see how hard it is and what's involved in doing it. I was stunned by how bad the available options were.

In one case, the first few posts were loaded into the book-making software with no problems, but the rest after that ended up badly garbled. That made that particular offering totally useless.

The next one I tried couldn't handle subscripts and superscripts, among other things, so it ended up being useless also.

I doubt that I'm the only person who does things like indenting text or using superscripts. Why can't the current versions of blog-to-book software handle the use of these things?

Federated key management as the basis for secure cloud computing

Cloud computing creates security problems that most organizations have not yet had to face on a large scale: protecting data when the location of the data is generally unknown. Encryption is a useful tool for solving this problem, but using it in the cloud is hard because of the key management problems that this causes. Fully federated key management can provide the basis for protecting sensitive data in the cloud, and it's probably the basis for how we’ll eventually protect such data. Let's look at exactly what this means and how it will probably work.

Key management

A cryptographic key is much like the combination to a safe: if you have the right combination, it’s easy to open a safe, but it’s hard to open one without the right combination. Similarly, if you have the right key, decrypting encrypted data is easy, but decrypting it is impractical without this key.

If you’re careless with the combination to your safe, someone else can easily use it to open your safe, and the protection provided by the safe is compromised. Similarly, the cryptographic keys that you use to encrypt data need to be handled carefully. If you’re careless with them then the protection provided by encryption can be essentially eliminated.

Key management covers all the details of how to handle keys carefully enough to ensure this does not happen. It ensures that you don’t do the cryptographic equivalent of writing the combination to your safe on a Post-it™ note and sticking it to the wall next to your desk.

Encryption only involves complicated mathematics that's incomprehensible to most people. Key management involves technology, people and processes, so it's even more difficult. Encryption provides an extremely high level of protection. Even with the world's most powerful supercomputers, hackers would need billions of years to beat modern encryption. Key management is nowhere near as robust. It's usually the weak link that limits how much protection data really gets, so it’s important to get it right if you’re serious about protecting sensitive data.

Federation

Federation describes how different computer systems can work together. In the context of key management, federation includes how different applications can get keys from the same key server. This is an important aspect of key management that needs to be addressed before encryption can be used to protect sensitive data in the cloud, and the lack of the ability to do federation dramatically limits the usefulness of many encryption and key management products today.

Encrypting a backup tape in a data center and decrypting it in an off-site disaster recovery site is a very simple example of federation. In this case, two different tape drives need to work with the same key server to get the key that's needed to encrypt or decrypt the backed-up data. But even extremely simple cases of federated key management can create problems that are hard to solve in practice.

The 2009 Encryption and Key Management Industry Benchmark Report from industry analyst firm Trust Catalyst estimates that only 41 percent of businesses encrypt backup tapes, and that issues relating to key management are the most common reason for not doing so. If the simple cases are that hard, it’s not hard to understand why there’s no solution for the harder cases yet, but that’s what we need to protect data in the cloud.

Cloud computing needs fully federated key management

In cloud computing, we have sensitive data that could be anywhere, and we need the ability for any application that needs access to this data to be able to decrypt it. To do this, we need a way for any application to be able to get the keys that it needs to decrypt data that it gets from the cloud and to use these keys in a careful way that keeps the data protected. More concisely, that's fully federated key management.

Federated key management for cloud computing

If today's systems can't implement fully federated key management, what are the missing pieces? If we look more closely at how cryptographic keys are handled today, we can probably get a good idea of what's needed in the more general case.

A cryptographic key always has additional information associated with it that uniquely identifies it. When a tape drive gets a key to use to encrypt stored data, for example, it also gets a unique key identifier which it stores with the encrypted data. To decrypt the encrypted data, the tape drive requests the key that corresponds to the key identifier that it finds with the encrypted data.

It's possible to extend the idea of a key identifier to include information about the key server where the right key can be obtained. Instead of having a key identifier like this

we might have one like this

 

where the additional information indicates the URL of the key server where the key can be obtained. If all applications understand how to handle such information when it's included in a key identifier, then they can easily use this information as the basis for federated key management.

How it's used today

This approach has already been used with great success in existing key management technologies. Systems that use Identity-Based Encryption (IBE), for example, already use more general key identifiers. In these systems, the identity of a user plus other policy information functions as the key identifier. In the case of using IBE to encrypt an email message, such an identifier might look like this

which indicates the email address of the recipient of the encrypted message, the time after which the private key can be downloaded from the key server, and the URL where the recipient can get the private key that he needs to decrypt the message. Any recipient that can interpret this type of key identifier can then contact the key server and request the IBE key needed to decrypt this message.

This approach hasn't quite made it to other encryption technologies yet, although it probably will soon. The most recent draft of the IEEE P1619.3 Standard for Key Management Infrastructure for Cryptographic Protection of Stored Data uses this approach to define unique identifiers for keys from which it's easy to find the URL of the key server where the key can be obtained. Once that standard is implemented, key management for encrypting backup tapes will certainly get much easier.

Once this idea is extended to other technologies, we’ll have the fully federated key management that we need to protect sensitive data in the cloud. This sounds simple enough, but actually writing a standard that will be the basis for doing this in an interoperable way isn’t easy. Using technologies like IBE may be as close as we can come to fully federated key management until the necessary standards are completed.

The last word on FPE?

There's an interesting paper by Mihir Bellare, Thomas Ristenpart, Phillip Rogaway and Till Stegers that's available on the IACR ePrint archive. This paper has the unassuming title "Format-Preserving Encryption," but it seems to have a fairly complete and definitive discussion of how to encrypt in an efficient and secure way that maps a plaintext into a ciphertext of identical format.

This is not a paper for casual readers because it talks about FPE at a level that's probably accessible only to cryptographers. But if you're interested in the details of the technical challenges that you need to address to make efficient and secure FPE schemes, it's probably the best paper to read.

Interestingly, Rogaway's work on this paper was supported by a grant from the NSF that's part of the American Recovery and Reinvestment Act of 2009. In other words, it's part of the US government's massive economic stimulus program. Apparently the government sees FPE as being a technology that's important to the future of the US economy.