Superconductor

Some perspective on industry certifications

I recently had an interesting discussion about the value of information security certifications, like CISSP, CISA, etc. The person I was talking to believed that commercial pressures would eventually make any such certification valueless. In this conversation I learned about the existence of on-line churches that will ordain you as a minister if you fill out a form on their web site. In many cases there's not even a fee for doing this.

Intrigued by this, I found the web site of one of these organizations and submitted a request to be ordained. I got an email almost immediately addressing me as "Reverend Martin" and welcoming me to the ranks of ordained ministers:

Congratulations! You are now a legally ordained minister for life, though you may relinquish your credentials at any time. AS OF Wednesday the 17th of February 2010 YOU HAVE BECOME A MEMBER OF THE PRESTIGIOUS CLERGY. You have earned a title worthy of admiration and respect.

The web site of the organization that ordained me claims that I'm now allowed to do things like baptisms, funerals and marriages. For only $30 this organization will even sell you a certificate that's apparently good enough to convince government officials of some states that you're a legitimate minister. They even sell a product called "Ministry-in-a-Box," but at $139.99, it's way more than I can afford.  

I'm sure that there are some people who get ordained on-line who take their responsibilities as a minister very seriously, but there are probably just as many who don't. But because there's no way to easily tell which one a particular minister is, those certificates that you can get for $30 don't really tell you anything useful. All they tell you is that the person listed on it filled in a form on a web page and then spent $30 on a certificate.

I hope that industry certifications like the CISSP and the CISA don't end up being as devalued as credentials for ministers seem to be now. But because there are now lots of competing certification programs for information security professionals, I wouldn't be surprised if the standards for certifications do indeed loosen up over time.

(I haven't actually done any baptisms, funerals or marriages yet, but I have to admit that I'm less likely to swear now, even when editing standards documents or working on the paperwork for our FIPS 140-2 validation. I'll definitely have to relinquish my credentials, though, when we start our next Common Criteria evaluation.)

A maturity model for enterprise key management

Although it hasn't been posted on the web site yet, the schedule for the 2010 Key Management Summit is now all set. One of the talks sounds particularly interesting: "A Maturity Model for Enterprise Key Management," which will be presented by Keith Sollers and Chris Kostick of Ernst & Young.

E&Y seems to be one of leaders in many aspects of information security, at least among the big consulting firms. I haven't heard of any others who have enough experience with enterprise key management to give them the background for a talk like this one, for example, and I'm looking forward to hearing what they have to say about it.

An example of bad reduction mod p

Elliptic curves are a natural construction over the complex numbers, but curves over the complex numbers aren’t very useful in computing. For that, we need elliptic curves that are defined over a finite field. It turns out that an elliptic curve over the integers can be reduced to one over a finite field in most cases. In particular, if we have an elliptic curve defined by

y² = x³ + ax + b

which has discriminant

D = -4a³ - 27 b²

then we want to look at what happens if reduce everything modulo a prime p. As long as p isn’t a factor of D, everything works fine. If p is a factor of D, however, then we get a singular curve when we reduce mod p. For example, the curve

y² = (x - 3)(x - 8)(x + 11)

= x³ – 97x + 264

has no repeated roots over the complex numbers, which is reflected in its non-zero discriminant

D = 1768900

= 2² 5² 7² 19²

But because 19 is a factor of D, this curve becomes singular when we reduce everything modulo 19. In particular, we find that this curve becomes

y² = x³ – 97x + 264

≡ x³ + 17x + 17 (mod 19)

 ≡ (x + 11)² (x + 16) (mod 19)

The cubic part of the curve has multiple roots so it's singular over GF(19). Modulo 19 this curve also has discriminant

D = -4(17)² – 27(17)³

= -27455

≡ 0 (mod 19)

which also tells us that this curve is singular over GF(19).

Looking up BINs

Even though a typical credit card number has 16 digits, not all of these represent a user's account number. The first digit is the major industry identifier (MII). An MII of 3 indicates travel and entertaiment, like an American Express card or Diner's Club card. An MII of 4 or 5 indicates banking and financial, like a Visa card or a Master Card. An MII of 7 indicates petroleum. If you have a gas station credit card, its first digit will probably be 7.

The first six digits form the issuer identification number (IIN). This is more commonly referred to as the bank identification number (BIN), although I understand that the term BIN is actually supposed to be obsolete. The digits after the IIN are the account number, except for the very last digit, which is actually a checksum for the other digits.

There's even a web site that has a free tool that you can use to find out what the IIN on your credit card means. In the free version of this tool you're limited to two lookups per day, but that's probably enought to do an interesting check or two.

Even though I knew that the first six digits of a credit card number are just the IIN, I found it a bit unsettling when I used this tool to look up what bank corresponds to the IIN on one of my credit cards.

Why X9.31 key generation is so odd

There was recently an interesting discussion on the sci.crypt Google group. A member of the group asked why the X9.31 standard has such an odd process for how RSA keys need to be generated. One response claimed that there was an easy work-around for the cumbersome process, and that involved using XML:

What you need here is a boat load of XML. XML will solve this problem.

We can have:

<cipher type="Asymmetric" name="RivestShamirAdleman">
 <keygeneration method="outdated,outmoded" result="pointless" />
</cipher>

Then you have someone write a parser in twelve different, slightly
incompatible, libraries and call that a standard.

Then, and only then, have you created a standard that will be defunct
before it's even officially recongised. 
 

A more insightful, if not as entertaining, post described how the content of X9.31 was driven by political maneuvering within the X9 group.

According to a person who claims to have been involved in writing the X9.31 standard, a company who was trying to make their elliptic curve technology look good relative to RSA insisted on the unusual key generation process. The non-crypto people in the group apparently agreed with their arguments and the result was the key generation process that's now in the X9.31 standard. Reading the full discussion of this doesn't take long, and may give an interesting insight or two into exactly how standards are actually developed.

Convergence of power series

Some thoughts on the convergence of power series - with pictures.

Consider the three functions

f₁(x) = 1 / (1 - x²)

f₂(x) = 1 / (1 + x²)

f₃(x) = √(1 + x²)

If we expand each of these in a power series around x = 0 we find that

f₁(x) = Σ x²ⁿ

f₂(x) = Σ (-1)ⁿx²ⁿ

f₃(x) = Σ x²ⁿ Binomial(1/2,n)

and that each converges for -1 < x < 1.

In the case of f₁, it's easy to see why that's the case. Here's the graph of f₁, and it behaves badly at -1 and 1.

In the case of f₂, it's not immediately obvious why reaching -1 and 1 causes problems. Here's the graph of f₂, and it certainly doesn't behave badly at all at these points.

On the other hand, the graph of what we get by summing the first few terms in the power series for f₂ looks like this, which does behave badly at -1 and 1.

This is easy to explain. If we look at |f₂| as a function of a complex variable, we see that f₂ has poles at i and –i, and the location of those poles limits the radius of convergence of the power series.

In the case of f₃, it's slightly more complicated. Here's what f₃ looks like. It also doesn't behave badly at -1 or 1.

Here's what |f₃| looks like as a function of a complex variable, and there aren't any poles there to cause problems. What's going on here?

What's causing problems in this case are the branch cuts that you need to define for f₃. Here's a graph of the imaginary part of f₃. Note that it's the locations of the branch cuts that limit the radius of convergence of the power series.

I don't recall being taught about branch cuts limiting the radius of convergence of a power series when I was in school. Like many other things, I'm not sure why this was overlooked.

Outis - S/MIME for Gmail

There's apparently an add-on for Firefox that lets you do S/MIME-based email through Gmail. When I first saw this, my first reaction was something like Why on Earth is anyone doing this!?!?

According to the IETF's outcomes tracking database, S/MIME hasn't been a success. They somewhat charitably say that it has experienced "poor adoption."

For some reason, the heroic efforts of the S/MIME Working Group in creating the dozens of documents that they've finished so far remind me of the part of the Odyssey where Odysseus and his companions escape from the hungry Cyclops Polyphemus by blinding him and running away while his cries that "nobody (ουτις, or outis) was hurting him" were ignored by the other Cyclopes.

Maybe "Outis" is a good code name for the Firefox S/MIME add-on for Gmail. I expect that's who will be using it.

Points of order three on elliptic curves

In an earlier post, we saw how it’s easy to tell which points on an elliptic curve y² = x³ + ax + b have order 2. What about order 3? That’s not much harder. If we have 3P = O then 2P =  –P, and we can use what we know about points of order 2 to find out what happens for points of order 3.

Let’s write

P₁= (x₁,y₁)

and

P₂ = 2P₁ = (x₂,y₂)

so that

 –P₁ = (x₁, –y₁)

From the earlier post on point doubling we have that

x₂ = (x₁⁴  – 2ax₁²  – 8bx₁ + a²) / [4 (x₁³ + ax₁ + b)]

If 2P₁ =  –P₁ then we have that

x₂ = x₁

or

(x₁⁴ – 2ax₁² – 8bx₁ + a²) / [4 (x₁³ + ax₁ + b)] = x₁

or

(x₁⁴ – 2ax₁² – 8bx₁ + a²) / [4 (x₁³ + ax₁ + b)] - x₁ = 0

so that

x₁⁴ – 2ax₁² – 8bx₁ + a² – 4x₁⁴ – 4ax₁² – 4bx₁ = 0

or that

3x₁⁴ + 6ax₁² + 12bx₁ – a² = 0

Example

For the elliptic curve y² = x³ + 1 we have that the x-coordinates of the points of order 3 need to have the property that

3x⁴ + 6ax² + 12bx – a² = 0

with a = 0 and b = 1 this means that we have

3 x⁴ + 12x  = 3x (x³ + 4) = 0

the only rational solution of which is x = 0. Thich corresponds to the points (0,1) and (0,-1) on the elliptic curve. Here’s what this looks like:

Another point of view

From the formula for doubling a point we get that

x₂ = m² – 2x₁

where

m = y′ = (3x₁² + a) / (2y₁)

And because x₂ = x₁ we can write

x₁ = m² – 2x₁

or that

m² = 3x₁

Now if we have that

y² = x³ + ax + b

then we have that

2 y y′ = 3x² + a

and that

2 y y′′  + 2 (y′)² = 6x

so that

y′′ = (6x – 2 (y′)²) / (2y)

This means that we have y′′ = 0 when

6x – 2 (y′)² = 0

or

(y′)² = 3x

or

m² = 3x

As we saw above, this happens at a point of order 3, so at a point of order 3 we have that y′′ = 0.

Using Pari for elliptic curves

I recently tried Pari, a piece of software that’s designed for doing number-theoretical calculations – like those you need to do in cryptography. After using it for a few hours, I have to say that I’m very impressed by it. It has lots of built-in functions for doing calculations involving elliptic curves, and because lots of the technology that we use at Voltage involves elliptic curves, I found that very useful.

On the other hand, Pari seems to assume that you already know a lot about things before you start using it. Here’s an example of defining the elliptic curve y² = x³ + 1 and finding all of the points of finite order on the curve:

 

The ellinit() function initializes a data structure for an elliptic curve, but what it tells you when it does this probably isn’t useful to most people. Here's how the Pari User's Guide explains the output of ellinit():

a1-a6,b2-b8,c4-c6: coefficients of the elliptic curve

area: volume of the complex lattice defining E

disc: discriminant of the curve

j: j-invariant of the curve

omega: [ω₁,ω₂], periods forming the basis of the complex lattice defining E (ω₁ is the real period and ω₂ belongs to Poincare's half-plane).

eta: quasi-periods [η₁,η₂] such that η₁ω₂ - η₂ω₁ = 2πi.

roots: roots of the associated Weierstrass equation

tate: [u²,u,v] in the notation of Tate

w: Mestre's w (this is technical)

The elltors() function finds all of the points of finite order. Its output is slightly more user-friendly, but it’s probably not obvious to most people what it’s telling you.

So overall, I’d have to say that I’m very impressed with Pari, and I’ll probably be using it a lot in the future. On the other hand, I can’t really recommend it for most people. If you feel comfortable reading Silverman’s The Arithmetic of Elliptic Curves, you’ll probably find it very useful. You'll also understand how to interpret the output of ellinit(). Otherwise, you might find its output a bit cryptic and tricky to interpret.

Security of NFC

The NFC Forum has what seems to be an extremely optimistic claim about the security of near-field communications. Here's what they claim:

Because the transmission range is so short, NFC-enabled transactions are inherently secure.

NFC is a wireless technology that's designed to work over fairly short distances - 10 centimeters or less. The NFC Forum seems to think that this short range makes NFC technology inherently secure. I'm fairly sure that this isn't true.

Because lots of the uses that are anticipated for NFC are things like mobile payments, making sure that NFC is reasonably secure is important, and relying on NFC being inherently secure because of its short range probably isn't a good way to do this. Even over a distance of only 10 centimeters, you still need to encrypt any sensitive data that you're transmitting.

Can wireless be more secure than wired?

We had an interesting discussion about wireless security in the recent X9 meeting. This was in the context of the new X.112 Part 2 standard, Wireless Management and Security — Part 2: ATM and POS. The interesting part was that the claim was made that wireless connectivity to ATM and POS devices can actually increase security. This may have been the first time that I ever heard someone make this claim about wireless technology.

The claim that wireless is more secure that wired connections to ATM and POS devices is based on the fact that it’s harder to cut the connection to a wireless device than to a device with a wired connection. Many ATM and POS devices trigger alarms when they’re tampered with, and it’s easier for a hacker to cut a wired connection than to cut a wireless connection. Cut the connection for the alarm and you can attack an ATM at your leisure.

Some payment devices also only transmit transaction data to a back-end system in large batch transactions that take place once every day or two. If this is the case, then an attacker has a fairly big window of opportunity in which to attack one of these systems. The claim is that wireless connections will eliminate the need for such batch processing, which will then limit the exposure of the wireless systems to hackers.

From what I heard from banks at the X9 meeting, it sounds like wireless banking and wireless payments are becoming fairly widespread. I found it interesting that banks perceive wireless to have advantages as well as disadvantages in these cases.

Visualizing complex multiplication

Here's an attempt to create a way to visualize elliptic curves with complex multiplication. With any luck, it will also give some insight into why the term "complex multiplication" is used.

An endomorphism of an elliptic curve is a homomorphism that maps points on the curve to other points on the curve. The multiplication-by-n maps

φ_n: P→ nP

all do this. For most elliptic curves, those are all the endomorphisms that exist, but some elliptic curves have other endomorphisms. Curves like those are said to have complex multiplication, and if we look at a few examples, it's not hard to see why it's called this.

Example 1

For the elliptic curve

y² = x³ + x

the mapping given by

φ(x,y) = (-x,iy)

is an endomorphism that’s not a multiplication-by-n map. It also has the property that

φ²(P) = φ∘φ(P) = (x,-y) = -P

Because φ² acts roughly like multiplication by -1, we can think of φ as acting roughly like multiplication by the complex number  i.

If we think of this elliptic curve as being parametrized by the Weierstrass ℘-function with periods ω₁ and ω₂, we find that

ω₁ = 1.85407 – 1.85407 i

and

ω₂ = 1.85407 + 1.85407 i

Note that ω₂ = iω₂.

Here’s what the lattice L of points nω₁ + mω₂ looks like:

 

Here's what multiplication by i does to a typical point in this lattice:

 

Note that this lattice has the property that iL = L, so the same multiplication by i that maps points on the elliptic curve to other points on the curve also maps points in the lattice to other points in the lattice.

Example 2

For the elliptic curve

y² = x³ + 1

we have that the mapping given by

φ(x,y) = (ξx,y)

where

ξ = e^2πi/3, a complex cube root of 1 that's also a root of x² + x + 1 = 0

is an endomorphism that’s not a multiplication-by-n map. It also has the property that

φ³(x,y) = φ∘φ∘φ(x,y) = (x,y)

Because φ³ acts roughly like multiplication by 1, we can think of φ as acting roughly like multiplication by the complex number ξ.

If we think of this elliptic curve as being parametrized by the Weierstrass ℘-function with periods ω₁ and ω₂, we find that

ω₁ = 2.10327 -1.21433 i

and

ω₂ = 2.42865 i

Note that we have that ω₂ = ξω₁.

Here’s what the lattice L of points nω₁ + mω₂ looks like:

 

Here's what multiplication by ξ does to a typical point in this lattice:

Note that this lattice has the property that ξL = L, so the same multiplication by ξ that maps points on the elliptic curve to other points on the curve also maps points in the lattice to other points in the lattice.

Example 3

Consider the elliptic curve

y² = x³ - 4320 x + 96768

If we think of this elliptic curve as being parametrized by the Weierstrass ℘-function with periods ω₁ and ω₂, we find that

ω₁ = -0.296858 i

and

ω₂ = 0.419821

Note that ω₂ = √2iω_1.

Here’s what the lattice L of points nω₁ + mω₂ looks like:

 

In this lattice, if we multiply a point z by (√2i)² we get the point -2z. This looks something like this: 

This will also be reflected in the points on the elliptic curve, so this curve has complex multiplication by √2i. In this case, however, it's not at all obvious what the endomorphism is that's not a multiplication-by-n map.

What is end-to-end encryption?

End-to-end encryption is often mentioned as one of the best ways to greatly reduce identity theft, but what exactly is end-to-end encryption? It turns out that there are actually conflicting definitions of it, so there’s no quick and easy answer to this question.

The US government’s Federal Standard 1037C, Telecommunications: Glossary of Telecommunication Terms, defines end-to-end encryption as “the encryption of information at its origin and decryption at its intended destination without any intermediate decryption.”

Another US government document, Special Publication 800-12 – An Introduction to Computer Security – NIST Handbook, takes a different approach. SP 800-12 distinguishes between link encryption and end-to-end encryption, where link encryption encrypts routing information and end-to-end encryption doesn’t.

Which of these definitions is more useful depends on your point of view. If you’re a credit card processor, for example, if the transactions that you process are encrypted on each link between the merchant where credit card data is captured and your systems, that doesn’t necessarily provide a useful level of protection to the credit card information. It might be possible for a hacker to capture it between where it’s in the clear between links.What’s probably more useful to you is for the credit card information to be encrypted as soon as it’s collected and only decrypted when it’s needed for some sort of processing. If that’s done in a hardware security module, that gives you fairly strong protection against any hackers that might be targeting you. You really don’t care about whether or not the routing information that’s used to process your transactions is encrypted or not.

I’m not sure what the motivation was for the SP 800-12 definition. It must have made sense when it was written. Maybe it’s just out of date. SP 800-12 was published back in October 1995. It probably went through the extensive review that government documents typically go through, so it was probably actually written at least a year or two before that. Maybe it’s safe to ignore it today and stick with the FS 1037C version.

Weak cipher suites with EV certificates

We had an interesting discussion of EV certificates in the X9 meeting last week. Apparently, EV certificates guarantee that some non-trivial means of authentication was used to authenticate the entity requesting an EV certificate, but there are minimal requirements other than that authentication. In particular, some people at the X9F4 meeting were a bit concerned by the fact that you can apparently use an EV certificate with an extremely weak cipher suite, which means that it's possible to have a connection to a server that uses an EV certificate yet creates a connection that's extremely easy for a hacker to beat.

The administrator of the server that uses an EV certificate can always configure his server to not allow weak cipher suites, and most of them probably do, but the people at the X9F4 meeting thought that the use of strong cipher suites really ought to be required with EV certificates.

The right stuff

I recently read an article in The Washington Post about how the US government is having a hard time finding qualified information security people. One of their proposed solutions is to take existing government employees and retrain them to make them information security specialists. This is almost certainly a bad idea.

When I worked for the government, we had a similar staffing problem at the end of the Cold War. At that time, we had lots of Russian linguists but not enough people in technical fields. To solve this problem, the government decided to to retrain the Russian linguists into engineers and other technical jobs. It didn't work very well.

Imagine you're a government employee who has been translating Russian for maybe 10 or 20 years, and you're suddenly told that you need to retrain to become an engineer. You probably became a Russian translator because of your particular skills and aptitudes, and those skills and aptitudes are very different from those needed to succeed as an engineer. You may have the right stuff for a particular job, but that right stuff doesn't necessarily translate into the right stuff for another job.

I taught some of the classes that were supposed to do this retraining, and it didn't seem to me that this effort was going to work very well. This really shouldn't have surprised anyone.

Your typical cryptographer, for example, has probably spent several years studying the math that you need to understand the foundations of cryptography. In the government, our rule of thumb was that it took about three years on the job before a person with that background could make significant contributions on the job. This is definitely not the sort of training that you can fit into a class or two, and it's definitely not the sort of thing that you can easily pass on to mid-career Russian linguists who are stressed about losing their job if they can't learn material for which they have absolutely no aptitude.

Let's hope that the government remembers how well the previous attempt worked, and doesn't try it again today. Our attempt at cross-training people didn't work very well at the end of the Cold War, and I'd expect a similar attempt to fail today.

Making change

My wife went out for pizza last week and came back with an incredible story. She ordered two pizzas on-line and went to the store to pick them up. When she arrived at the pizza store their computer was down. When she paid with cash, she was surprised to see the cashier pull out a calculator that she used to calculate the change due from my wife's purchase. The cashier explained that they had to use a calculator to figure out how much change to give a customer and that they would get fired if they were caught making change without the use of the calculator.

I'd guess that the pizza store didn't just make the use of calculators mandatory for no reason. They almost certainly did this because their employees couldn't do it accurately without a calculator.

It's somewhat popular these days to criticize the exit exam that California high school students have to pass to graduate. Opponents like to say that it forces teachers to teach just the material that's covered on the test, and that this reduces the overall quality of education. Supporters of the exam maintain that it's just testing basic skills and that its requirements are quite reasonable. If pizza stores have to require their employees to use calculators to make change accurately, I'd guess that the exit exam isn't testing enough.

The fact that people can pass the exit exam and still can't make change accurately may account for the following joke:

Question: What is 2+2?

Answer: A question on the California high-school exit exam

Another example of rational points on an elliptic curve

Here's another example of finding rational points of finite order on an elliptic curve.

Suppose that we have the elliptic curve y² = x³ - 2x + 1. In this case we have that D = 5, so that the possibilities for the y-coordinate of a rational point of finite order are limited to 0, ±1 by the Nagell-Lutz theorem. A quick check of these possibilities shows that we have the following points:

P₁ = (1,0)

P₂ = (0,1)

P₃ = (0,-1)

Here's what this looks like:

These points form this subgroup of the points on the curve:

Rational points on y² = x³ - 2x + 1

+	O	P1	P2	P3
O	O	P1	P2	P3
P1	P1	O	P3	P2
P2	P2	P3	P1	O
P3	P3	P2	O	P1

We can also think of the elliptic curve y² = x³ - 2x + 1 as being parameterized by the Weierstrass ℘-function with periods ω₁ and ω₂ where we have approximately

ω₁ = -2.01891 i

and

ω₂ = 2.96882

All of the points on y² = x³ - 2x + 1 that have the property 4P = O come from the complex numbers shown here: 

 
Of these 16 points, these are the ones that we get the subgroup of rational points of finite order from (z₁ corresponds to P₁, etc., and z₀ corresponds to O):

Sign up now for the 2010 Key Management Summit

It looks like the agenda for the 2010 Key Management Summit is all set. This year's event will include an interesting range of presentations: talks by industry analysts, vendors, users of key management technology, and even a talk or two about cutting-edge research. We're also considering having some time set aside for impromptu presentations.

Suppose that you're sitting through one of the talks and what the speaker says gives you an idea that the rest of us would be interested to hear. The intent is to have some time allocated to hear these ideas - probably something that can be summarized in a slide or two.

I'm not sure how well that will actually work in practice, but it sounds like an interesting idea. I hope that we'll get a chance to try it in May.

It's easy to become famous

Intrigued by the possibility of becoming famous that I mentioned in the last post, I looked more closely at the email that invited me to get listed in some sort of prestigious publication and found a link that had my name in the URL. Once I saw this, I wondered how easy it would be for someone else to become famous. To test this, I removed my name from the URL and put in the name of one of my wife's stuffed animals.

Apparently Putsi Fischotter is also famous enough to get his name listed.

 

Maybe if I send these guys a picture of a stuffed otter dramatically staring off into the distance they'll add that image to their web site.