Superconductor

Another standard for tokenization

2010-03-15T08:00:00-07:00

It looks like a tokenization vendor has taken it upon themselves to organize a group of vendors to create a standard for tokenization and its secure implementation. Having a standard that describes tokenization and how to do it securely is definitely a good idea, but I'm not sure that a vendor-led group that's not part of any recognized standards organization is the best way to do this.

A group organized by a single vendor probably won't have decision making processes that are as transparent as those that established standards organizations have. This probably isn't good. Although all standards organizations have their problems, you at least have a known process by which these organizations create and review their standards. These processes may not be perfect, but they're at least well known, and they almost always try to keep any single vendor from unduly influencing the content of any particular standard. With vendor-led groups, however, there's often little attempt at transparency, and there may even be little incentive for the group to act on feedback that they get on their standard as it's being developed. This often results in standards that aren't as useful as they could be.

I also have to wonder why a vendor-led group is necessary in this particular case. The Accredited Standards Committee X9, the organization that creates the American National Standards for the financial services industry, is currently working on a standard (X9.119) that will define requirements for the secure implementation of tokenization. This X9 standard will only reflect the requirements of the financial services industry, but because that's the main user of tokenization, that really shouldn't be a problem. I'm fairly confident that an organization that specializes in standards for the financial services industry will have a better chance of creating a standard that reflects the needs of the financial services industry than an organization comprising tokenization vendors will.

I'm also a bit puzzled by the fact that many tokenization vendors don't seem to participate in X9 at all. Voltage has been an X9 member for quite a while, and both the X9 community as well as Voltage have benefitted from this. The other members of X9 have essentially received lots of free cryptography and security consulting from Voltage, and Voltage has received lots of useful information about exactly what the needs of its customers are in return.

I'm not sure why tokenization vendors don't actively participate in X9, and the fact that they don't makes me wonder how much they really understand the requirements of their customers and how well they'll be able to create a useful standard for the secure implementation of tokenization.

I'm fairly sure that Voltage will end up participating in this vendor-led effort to define a standard for secure implementations of tokenization, but from what I know now, I'm not sure that the standard that this group creates will be very useful. In this particular case, I hope that I'm wrong. That doesn't happen very often, does it?

Do we really need another tokenization standard in addition to X9.119?

The virial theorem in the workplace

2010-03-12T08:00:00-08:00

There's a theorem from mathematical physics that may have an application in the workplace. This is the virial theorem, and its workplace analogy may explain why every job has its annoying parts.

One version of the virial theorem roughly says that for a finite collection of point particles interacting gravitationally, the time average of the kinetic energy is half the time average of the potential energy, or

<K> = - <U> / 2

The virial theorem is useful to astronomers because you can use it get a good idea of masses of distant objects, which you can't really observe, from their kinetic energy, which you can observe. The reason that we think that dark matter exists is basically from observations like those plus the virial theorem.

Driving in to work today, I had the thought that an appropriate analogy for the virial theorem the workplace might be that the bad parts of a job are always proportional to the good parts of a job. In my experience, this seems to have always been true.You probably have some relationship like this, for example:

<Bad> = - <Good> / 2

When I was an officer in the US Army, there were lots of good aspects of the job. There's nothing in the world as rewarding as working with soldiers, for example, and getting paid to work with explosives and fire guns is also lots of fun. To make up for this, however, there's also the fact that the military is really part of the government, so you're really part of a large, mind-numbingly bureaucratic organization.

Or when I used to do what's probably best called applied physics research, it was great fun working with things like lasers and electron microscopes. To make up for this, however, there's the never-ending battle that you have to fight to get funding for those expensive gadgets.

Or when I did mergers and acquisitions consulting, it was great fun getting a look inside lots of different companies in lots of different industries and seeing how they worked. The pay wasn't bad, either. To make up for this, however, there were the 20-hour days and the backstabbing from other consultants (particularly the lawyers) involved in the M&A projects that you had to keep a constant eye out for.

So although I'm not sure that you can write down a set of assumptions that lets you rigorously prove an analogy for virial theorem for the workplace, it certainly seems to be true. If there's a job out there for which it doesn't hold, I'd definitely like to hear about it.

Right hand, say hello to the left hand

2010-03-11T08:00:00-08:00

At the recent X9 meeting, I noticed an interesting pattern in the discussions about the appropriate level of security around various on-line banking transactions. In every case that I can remember, we had a discussion that went something like this:

Bank A representative: So we think that this new technology has the potential to really revolutionize banking. Bank A loves it.

Bank B representative: Our concern with that particular technology is that we'll never be able to make it secure enough. Plus, our customers really don't want it.

Bank A representative: We don't see security as a problem at all. We've actually been using this technology for over two years now and customers love it.

Because these opinions were often so far apart, I had to wonder exactly how much thought went into creating some of the banks' positions. Had they really thought through the security implications of using a new technology? Did they really have an idea of what their customers really want?

With opinions as different as the ones that I saw, I suspect that not everyone had been as careful in forming their opinions as they should have been, although it was hard to see which position could have benefitted from some additional research.

The converse of the Nagell-Lutz theorem

2010-03-10T08:00:00-08:00

The Nagell-Lutz tells us that rational points of finite order have integer coordinates, but it doesn't tell us that points with integer coordinates have finite order. As a reminder, here's the statement of the Nagell-Lutz theorem.

Let y² = x³ + ax + b be an elliptic curve with integer coefficients and let D = 4 a³ + 27 b². Then if P = (x_P,y_P) is a rational point of finite order then P has integer coordinates and either y_P = 0 or y_P²|D.

Here are some examples of points with integer coordinates that don't have finite order.

The point P = (1,2) is on the elliptic curve

y² = x³ + 3

but (1,2) isn't a point of finite order. We have that

2P = (-23/16,-11/64)

for example. Since 2P doesn't have integer coordinates, it's not a point of finite order, so P isn't either.

For another example, consider the elliptic curve

y² = x³ + 17

There are 16 points with integer coordinates on this curve. These are the following

(-2,±3)

(-1,±4)

(2,±5)

(4,±9)

(8,±23)

(43,±282)

(52,±375)

(5234,±378661)

Although we can find a few cases where adding these points gives another point with integer coordinates, like

(-2,3) + (-1,4) = (4,9)

most cases don't. We have that

(-1,4) + (-1,4) = (137/64, -2651/512)

for example.

Even worse, we have that

(5234,378661) + (5234,378661) = (187618163896928/143384152921, -1/4)

None of these points actually have finite order although they have integer coordinates. So points of finite order have to have integer coordinates, but not all points with integer coordinates have finite order.

More on the Cryptographers Panel misunderstanding

2010-03-09T09:00:00-08:00

After pondering the odd reactions that I saw from some people who saw the Cryptographers Panel at the RSA Conference ("Oh no! Crypto is broken! We can't use it to protect sensitive data!"), I started to wonder why people don't have a similar reaction to tokenization. Except for the article that I recently wrote for the ISSA Journal, there's been absolutely no careful discussion of tokenization at all. Almost nobody can tell you exactly what it is and why you'd expect it to be secure. There are absolutely no standards for tokenization, and tokenization systems receive absolutely no peer review. Despite this, people are cheerfully willing to blindly assume that something is secure just because it's called "tokenization."

Why is this?

Now Voltage sells both encryption AND tokenization products. Which one we recommend to customers depends on exactly how they need to handle sensitive data after it's either encrypted or tokenized. And because we offer both options, we can afford to be fairly impartial in the battle that's apparently being fought by marketing people who don't really understand either encryption or tokenization.

Are people just afraid of encryption because it's hard? I'll admit that encryption is a difficult subject that's hard to master. Is the blind acceptance of the security of tokenization that we see a reaction to the previous generations of encryption technology that actually were too hard and expensive for most uses? There must be some good reason that people are willing to make a huge leap of faith just because a technology is called "tokenization."

Of course to really make people who blindly accept tokenization uncomfortable, ask them about that database of encrypted information that's used in the detokenization algorithm. If you can't trust the security of encryption, why would you trust the security of that database?

The bottom line is that the security of encryption is based on a solid foundation of rigorous research. There's no similar foundation for the security of tokenization. Maybe it's time to correct this oversight.

The PBA attack on RSA

2010-03-09T08:00:00-08:00

I understand that we’re now living in a world in which everyone feels like they deserve their 15 minutes of fame, but I found the way that unwitting journalists managed to get it for security researchers Andrea Pellegrini, Valeria Bertacco and Todd Austin of the University of Michigan get their 15 minutes to be a bit frustrating.

Pelligrini, Bertacco and Austin actually did some fairly clever work: they found a way to cause bit errors in a microprocessor by carefully altering its input voltage, and then used these errors to help recover an RSA private signing key. For each bit error they were able to recover about 8 bits of private key, and were able to recover an entire 1,024-bit RSA key in about 100 hours.

If you’re interested in side-channel analysis and implementations of cryptography, their paper is well worth reading. On the other hand, their attack really isn’t the sort of thing to worry about too much. Devices that are designed to be secure, like HSMs and smart cards, filter the power so that you can't do attacks like the PBA attack, and with devices that aren't designed to be secure, there's always an easier way to recover a key from them than doing something like the PBA attack. This means that we won't be seeing hackers using the PBA attack any time soon, but you'd never think this from seeing the way it was reported by the media.

One headline read “'Severe' OpenSSL vuln busts public key crypto." That really doesn't seem to be a good summary of the PBA attack. The rest of the article didn't really to do much better.

Another headline said “RSA 1024-bit private key encryption cracked,” which was also a bit misleading. RSA-1024 wasn’t actually cracked. Instead, a particular implementation of it was beaten, and beaten in a way that really doesn’t pose a threat to most people. There’s absolutely nothing fundamentally wrong with RSA, although you really can’t tell that from this particular story.

The big problem seems to be that for each person who read and understood the PBA paper, there are probably thousands out there now wasting lots of time and energy worrying about whether or not the RSA-1024 that they use for SSL is secure enough. It almost certainly is, but you really can’t tell that from the media coverage of the PBA attack.

Maybe some reporters ought to attend the next cryptography boot camp that our marketing guys hold. They did this at the RSA Conference last week, and from what I heard, the people who attended found it to be a very good use of a couple of hours. Maybe I’ll suggest that they invite some reporters to it the next time they organize it. Encryption is a tricky subject, and it's hard to understand all of the details of how it works. But if we had a few journalists who understood the basics of cryptography, we might not have had to spend so much time explaining exactly why this "severe vulnerability" isn't really worth worrying about.

Fortunately, Voltage's products use DSA for signatures instead of RSA. That will save us lots of time trying to explain to customers that while the PBA attack is actually some very clever research, it can't really be done to our products. Just saying that we don't use RSA for signatures is much easier.

Misunderstanding what was said at the Cryptographers Panel

2010-03-08T08:00:00-08:00

As usual, the Cryptographers Panel at the RSA Conference was interesting. Unfortunately, some of the remarks made by the panelists seem to have been taken out of context by people who apparently didn’t understand the context to begin with. This has apparently led to some people claiming that cryptography is totally broken and shouldn’t be used to protect sensitive information.

As Dave Barry would say, I’m not making this up.

The remarks that Adi Shamir made about attacks on AES seem to be at the root of this misunderstanding. Let’s look at exactly what Shamir said and see how close it comes to saying that cryptography is totally broken. You can find a recording of the talk here if you missed the RSA Conference last week. Some of the question and answer period has been edited out, and I’m not exactly sure why that happened.

In his opening remarks Shamir notes that progress has been made in the cryptanalysis of AES. Last year, Alex Biryukov and Dmitry Khovratovich found a related-key attack against the full AES-256 algorithm that has both time and memory complexity of 2^99.5.

This attack is much better than an exhaustive search, but it’s also not even close to being feasible. (If that’s not obvious, do a quick Google search to find out roughly how much information exists in the world today and compare it with the 2^99.5memory required by this attack.) If that’s the best that an attacker can do, then you’re still very safe. The fact that the way that standards require you to use AES also eliminates the possibility of actually carrying out a related key attack should make you feel even safer. If you use AES like the standards specify, then this attack can’t be used against you.

Shamir also mentioned an attack on AES-128 that was also found by Biryukov and Khovratovich that runs in 2⁴⁵ time. That’s so fast that it’s practical to do on a typical PC. On the other hand, Shamir also mentions that this attack also assumes that you use AES-128 in a way that is forbidden by the AES standard. In this case, the attack works if you use AES-128, but try to fake AES-256 using the shorter 128-bit key. Again, this isn’t allowed by the AES standard, so it shouldn’t really come as a surprise that it doesn’t work well. Once again, it you use AES like the standards specify, then this attack can’t be used against you.

So I’m not sure exactly how someone heard Shamir’s remarks and interpreted them as saying that encryption is fatally flawed and isn’t suitable for use in protecting sensitive information. It seems to me that a better interpretation is that you really need to follow the standards that specify how encryption is used. If you do that then it provides protection that’s incredibly secure. On the other hand, if you decide to not follow these standards and instead decide to invent new ways to use encryption that haven’t had any sort of independent review, then there’s a possibility that you can do things that dramatically reduce the security that the encryption provides.

There are definitely innovative ways to use encryption safely. These will always come with a peer-reviewed proof that the new technique is secure. If you use one of these, encryption will still provide an essentially unbreakable level of security. But if you use techniques that don’t have such a proof of security then you’re taking a significant risk. Maybe that’s too subtle an interpretation for the opening remarks at the Cryptographers Panel, but it’s certainly more accurate than saying that cryptography is totally broken and shouldn’t be used to protect sensitive information.

Cloud computing at the RSA show

2010-03-05T08:00:00-08:00

While too many of the pitches on the expo floor at this year's RSA Conference were about how various products or services could make you PCI DSS compliant, way too many of the talks this year were about cloud computing. Few of these talks really seemed to have anything new and interesting to say. Some seemed to be just thinly-veiled pitches for a cloud computing offering from vendors who had essentially bought speaking slots at the show with their sponsorship dollars.

Now, while cloud computing can be a very useful technology in some cases, it's also one that can create some interesting security challenges. But while talk after talk went on and on about the security challenges of cloud computing, one fairly obvious approach was rarely mentioned: encrypt your data before you put it into an external cloud computing environment.

The RSA Conference started out as a conference about cryptography. Despite this bit of history and the fact that cryptography can go a long way towards solving some of the tricky problems that cloud computing can cause, it was rarely mentioned at this year's conference. This struck me as being a bit ironic.

Wednesday at the RSA Conference

2010-03-04T08:00:00-08:00

If the number or size of the parties put on by vendors at this year's RSA Conference is any indication, the information security industry has fully recovered from any affects of the recent recession. Luckily, I recently saw an episode of Mythbusters that made surviving these parties much easier than it was in previous years.

The Mythbusters episode that I saw compared the hangover caused by drinking from beer to the hangover caused by drinking liquor. Somewhat surprisingly, they found that beer causes a much worse hangovers.

Armed with this research, I developed a strategy to deal with the numerous parties at this year's RSA Conference: stick to martinis and drink no beer. Drinking martinis also helps in another way. Martinis taste terrible so you're much less likely to drink too many of them. After a single sip from a martini, you're usually more than happy to wait a long time before taking another sip. Beer, on the other hand, doesn't have this built-in rate-limiting feature, so you're more likely to drink too much of it.

This strategy worked perfectly. By sticking to martinis I was easily able to keep my blood alcohol content well within the limits allowed for driving, and the next morning I felt no obvious effects from the parties at the RSA Conference the previous night.

Tuesday at the RSA Conference - Bah-weep-graaaaagnah wheep ni ni bong

2010-03-03T08:00:00-08:00

(Dozens of menacing SHARKTICONS appear in front of KUP and HOT ROD.)

KUP: Don't act hostile. I'll use the universal greeting.

HOT ROD: Universal greeting?

KUP: Watch. I'll have them eating out of my hand.

(KUP holds out his hands to show that he's unarmed and then addresses the SHARKTICONS.)

KUP: Bah-weep-graaaaagnah wheep ni ni bong.

HOT ROD: (puzzled) Bah-weep-graaaaagnah wheep ni ni bong?

SHARKTICONS: Bah-weep-graaaaagnah wheep ni ni bong.

KUP: See, the universal greeting works every time.

Transformers: The Movie, 1986

Many of the vendors at this year's RSA Conference seem to have adopted the idea of a universal greeting. Maybe they got this idea from Transformers: The Movie. Maybe they didn't, but if they didn't, it sure was hard to tell today.

The universal greeting that many of the vendors at this year's conference seem to have decided upon is "You'll never be PCI compliant without my product." Apparently they tired of the previous universal greetings "You'll never be HIPAA compliant without my product" and "You'll never be SOX compliant without my product."

In a few cases, the vendors could actually give a reasonable explanation of exactly what parts of the PCI DSS their products were designed to help customers address, but in even more cases they clearly hadn't really given this much thought. Instead, they seemed to be relying on the fear, uncertainty and doubt that the PCI DSS seems to have caused to get potential customers interested in their products.

I doubt that this is going to be a successful strategy. It certainly didn't work for the previous universal greetings, and I doubt that it will work this time, either.

On the other hand, I was happy to see that Voltage's partners who were exhibiting at the show didn't seem to have this problem at all. I turned my badge backwards to that they couldn't see that I was from Voltage and asked some of them a few questions about how their technology worked and exactly how it could help someone reach PCI compliance, and they all seemed to understand exactly what was required by the PCI DSS and how their technologies helped their customers comply with the PCI DSS.

Maybe this was because our business development team is fairly selective about who they partner with. Maybe there's some other reason. I don't know for sure, but I do know that after hearing this year's universal greeting over and over again, it was a pleasant change of pace to actually talk to people who seemed to actually understand their customers' problems and how to solve them.

Monday at the RSA Conference - Miranda?

2010-03-02T08:00:00-08:00

The exhibit hall of the RSA Conference was open for a couple of hours last night, so I got a chance to walk around and see what vendors were talking about this year. I have to say that I was not impressed in lots of cases - some vendors seemed to actually be moving backwards instead of forwards. It almost reminded me of the horror novella Miranda by John R. Little that won the 2008 Bram Stoker Award for Best Long Fiction. (No - this book has nothing to do with the planet Miranda from the movie Serenity.)

The protagonist of Miranda is a man who moves backwards through time instead of forwards. The book opens with him returning to life in a hospital at age 65 and ends, well, I'd hate to ruin a truly excellent book, so I'll just let you use your imagination.

The entire book reinforces this backward-through-time theme. It starts with chapter 15 and counts down to chapter 1, for example, and the pages are also numbered in the reverse order. For me, this produced a particularly chilling effect because you could tell exactly how many pages were left of the protagonist's life. You can easily look at the last page of a book to see how many pages are left before the story is going to end, but that doesn't seem to provide the same effect that the reverse page numbering in Miranda does.

In any event, the parallel between a man moving backwards through time and the vendors who seemed to be moving backwards instead of forwards definitely struck me when I made my first circuit through the expo hall of the RSA Conference this year. I doubt that the vendors that I saw yesterday will suffer the same horrific end that the protagonist of Miranda did, but I doubt that things are going to work out well for them in the long run.

The RSA Conference begins

2010-03-01T08:00:00-08:00

Today's the first day of the RSA Conference. If you can manage to cut through the marketing hype that surrounds this event, you can actually learn all sorts of useful things at it. This year, there are two parts of the conference that look particularly interesting.

The first is the Cryptographer's Panel, which will be on Tuesday at 10:30 am. Brian Snow will be on this panel, along with Whitfield Diffie, Martin Hellman, Ron Rivest and Adi Shamir. Hearing any of these people talk is always an excellent opportunity to learn all sorts of interesting things, but hearing Brian is probably the best opportunity of all. Before he retired, Brian was the Technical Director of the Information Assurance Directorate of the National Security Agency, sort of like the NSA's chief scientist on the defensive side, so he knows what really happened in lots of cases where others can only speculate.

Want to know about what really happened in the early history of public-key cryptography? Listen to Brian talk about it. Want to know about what really happened in the US government's pre-dot-com-era efforts to discourage the use of cryptography through export controls? Listen to Brian talk about it.

Another part of the conference that will probably be very interesting is Phil Rogaway's presentation "Format-Preserving Encryption: How to Encipher CCNs, SSN, and the Like," which will be on Friday at 10:20 am. It was a paper by Phil and John Black that was part of the Cryptographer's Track at the 2002 RSA Conference that gave the first proofs of security for format-preserving encryption, so he's been working on it from the beginning. Today, the technology is now commercially available and is being used by lots of businesses to help them comply with the PCI DSS without causing too many problems with their complex, legacy environments.

Format-preserving encryption is what's described in the FFX mode of AES that NIST is now working on, and here's even a part of the draft of the X9.119 standard: Retail Financial Services — Requirements for Protection of Sensitive Payment Data — Part 1: Using Encryption / Tokenization Methods that's dedicated to describing how to use the technology to protect payments information.

Phil's presentation isn't part of the Cryptographer's Track this year, so it will probably be at a level that's accessible to people who don't like to worry about all of the details about exactly how format-preserving encryption works and the details of the proofs of why it's secure. Instead, it will probably focus more on system-level issues like why it's useful and how to use it. If that's of interest to you, then you'll probably to make sure that you get a chance to hear Phil talk about format-preserving encryption.

Some perspective on industry certifications

2010-02-26T08:00:00-08:00

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

2010-02-25T08:00:00-08:00

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

2010-02-24T08:00:00-08:00

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

2010-02-23T08:00:00-08:00

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

2010-02-22T08:00:00-08:00

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

2010-02-19T08:00:00-08:00

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) = Σ (-1)ⁿ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

2010-02-18T08:00:00-08:00

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

2010-02-17T08:00:00-08:00

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₁

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

(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

(y′)² = 3x

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

2010-02-16T08:00:00-08:00

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.