« April 2010 | Main | June 2010 »

May 2010

Friday, 28 May 2010

Strictly ballroom

After some standards meetings I'm reminded of the movie Strictly Ballroom. In particular, the following bit of dialog from it:

(SCOTT HASTINGS is discussing his daring new dance steps with the corrupt Australian Dance Federation President BARRY FIFE.)

BARRY: Where do you think we'd be if everyone went around making up their own steps?

SCOTT: Out of a job.

Thursday, 27 May 2010

PCI tokenization guidance could benefit payment processors

Interesting news article by industry reporter Rob Westervelt who has been following business and technology trends in the payments sector:

PCI tokenization guidance could benefit payment processors
By Robert Westervelt, News Editor
27 May 2010 | SearchSecurity.com

It's not the crypto that's too hard

At the recent Key Management Summit, one theme that was mentioned frequently was how difficult it is for people to implement encryption in a secure way in their businesses. I heard lots of horror stories about how various IT organizations would try to add encryption to some sort of business application and do this in a way that had all sorts of security problems. Although many of the IT organizations had a reasonable understanding of encryption, they didn't really understand how keys need to be managed securely for the encryption to provide a useful level of protection.

Maybe we've reached a point where lots of people working in IT understand basic crypto concepts, but we apparently haven't reached a point where the same people understand basic key management concepts. It probably took about 10 years for a basic understanding of encryption to work its way into the IT world. I wonder how long it will take for the same level of understanding of key management to do the same.

Wednesday, 26 May 2010

Adding points on hyperelliptic curves

Suppose that we have two points P and Q in the Jacobian of a hyperelliptic curve of genus 2 where

P = (P1) + (P2) - 2(O)

and

Q = (Q1) + (Q2) - 2(O)

where the curve is defined by

y2 = f(x)

where f is a polynomial of degree 5.

Now suppose that we want to find P + Q = R where

R = (R1) + (R2) - 2(O)

Here's how we can use the structure of the hyperelliptic curve to do this.

In this picture

Image001

the red points represent P, the green points represent Q and the black points represent R. Let's write -R1 and -R2 for the blue points that we get by reflecting the black points across the x-axis even though that notation is a bit misleading, and let's look at three functions on the hyperelliptic curve: the curve u through P1, P2, Q1, Q2, -R1 and -R2, the vertical line v1 through R1 and -R1 and the vertical line v2 through R2 and -R2.

Note that if we write the cubic through P1, P2, Q1, Q2 as

y = g(x)

then we have

y2 = g2(x)

The hyperelliptic curve is defined by

y2 = f(x)

so we have that

g2(x) = f(x)

or that

g2(x) - f(x) = 0

which is a polynomial of degree 6 with zeroes at P1, P2, Q1, Q2, -R1 and -R2 and a pole of order 6 at O.

We can then write

div(u) = (P1) + (P2) + (Q1) + (Q2) + (-R1) + (-R2) - 6(O)

div(v1) = (R1) + (-R1) - 2(O)

and

div(v2) = (R2) + (-R2) - 2(O)

Combining these gives us that

div(u) - div(v1) - div(v2) = (P1) + (P2) + (Q1) + (Q2) - (R1) - (R2) - 2(O)

= (P1) + (P2) - 2(O) + (Q1) + (Q2) - 2(O) - (R1) - (R2) + 2(O)

P + Q - R

or that

P + Q = R + div(u/v1v2)

which is very similar to what we get for an elliptic curve.

In practice, there's an easier way to do this, and that's with Cantor's algorithm. With Cantor's algorithm, we work with polynomials whose zeroes we get from the coordinates of points on a hyperelliptic curve instead of with the points themselves. Cantor's algorithm is more efficient, but it's hard to see the geometric meaning of what's going on with it. If we just work with divisors, adding points on hyperelliptic curves is probably easier to understand.

Tuesday, 25 May 2010

Lots and lots of keys

757PX-~1

The Key Management Summit has always been part of the IEEE Symposium on Mass Storage Systems and Technologies. This is mostly for historical reasons: the biggest use for key management products today is managing the keys use to encrypt storage: tape drives, disk drives, etc. The same vendors interested in mass storage systems were also interested in key management, so the two meetings seemed to fit together well.

From what I heard at this year's Key Management Summit, the connection between mass storage and key management may get even stronger in the future. The concensus of the participants in the KMS was that within 10 years it will not be uncommon for key management products to be managing at least one trillion keys. That's a lot of keys, and it will take at least several terabytes of storage just to hold them all.

Maybe it's time for people to take a closer look at key derivation functions. If you use a KDF instead of generating all of your keys randomly, you just need to store and securely backup the master secrets that are used in the KDF. That can reduce the amount of storage that you need from several terabytes down to a few dozen bytes. KDFs are useful today. Maybe they'll be even more useful in the future.

Monday, 24 May 2010

Even more spectacular than the Morris worm

At the recent Key Management Summit I was talking with some of the people who had really come for the IEEE Symposium on Massive Storage Systems and Technology about some of the more spectacular security incidents that have affected the Internet. These included things like the Morris worm, the SQL Slammer, and other high-profile incidents. One of the people that I talked to works for CERN, and he told me about a type of incident that they apparently deal with on a routine basis that's a bit more spectacular than any of these security incidents.

In big particle accelerators you apparently get an event called a "magnet quench" now and then. These start when one of the superconducting magnets that controls the accelerator's particle beam develops a glitch. Maybe one of the magnet's superconducting coils gets hit by stray high-energy particles, for example. This can heat the coil to the point where it loses its superconductivity.

These coils can have tens of thousands of Amps running through them. This is OK when they're superconducting, but causes problems when they're not. When the coils lose their superconductivity, resistive heating from the huge amount of current flowing through them makes them even hotter. All of this heat then boils the liquid helium that's cooling the coils, which then vents through the equipment's pressure relief valves in a spectacular way.

Those superconducting coils probably aren't cheap, but I'd guess that the economic damage caused by any of the high-profile security incidents is greater than the cost of repairing the damage from a magnet quench in a big particle accelerator. I'll bet that the magnet quench is more impressive to watch, though.

Friday, 21 May 2010

Codebreakers - the comic

It looks like there's now a comic being pubished that stars cryptanalysts. It's Codebreakers from BOOM! Studios, the same people that are famous for, well, I've actually never heard of them before, but they're probably known for something.

Here's the summary of what happens in the first issue of this comic:

Busting foreign spies on domestic soil. Cracking the code on drug and human trafficking. Shutting down the mob. They are the elite Cryptanalysis Unit of the Federal Bureau of Investigation, examining manually encrypted documents and records of illegal enterprises, providing expert testimony, forensic assistance, and identification of terrorism, foreign intelligence, and criminal activities in support of federal, state, local, and international law enforcement investigations and prosecutions... Ciphers. Codes. Encryption. Passwords. Meet the best of the best at puzzling out the truth and protecting all of us from those that would steal information in ways that can shatter the global community and kill. But what happens to the Cryptanalysis unit when one of their own goes missing? Is it a puzzle the puzzle-solvers can't solve? And will this cipher reveal things about... themselves? In the mode of previous BOOM! series like POTTER'S FIELD, UNTHINKABLE, blockbusters like NATIONAL TREASURE and DAVINCI CODE, and espionage comics from our esteemed competition QUEEN AND COUNTRY and WHITEOUT!

I don't know how good this comic is, but I'd guess that my favorite depiction of cryptographers will still be The Amateur, the 1981 movie in which a mild-mannered CIA cryptographer blackmails the CIA into training him to hunt down and kill the terrorists that killed his girlfriend. Don't mess with cryptographers.

Thursday, 20 May 2010

A possible use for spam

I've received lots of spam emails recently that tell me that I've been selected for inclusion in some sort of Who's Who book. As far as I can tell, all of these are scams designed to get you to give them your credit card number so that they can charge you for expensive books that you didn't order. On the other hand, maybe there's actually a good use for these scams.

I have to wonder if being included in one of these books would help your chances for college admission these days. Imagine being able to add the following to your college application:

  • Received first pre-approved credit card offer at age 2
  • Included in Cambridge's Who's Who at age 4

Could that be the additional padding that will separate you from the other applicants at the more selective universities?

Wednesday, 19 May 2010

Hyperelliptic curves

Image001

Hyperelliptic curves are interesting for many reasons. The reason that we’re particularly interested in them at Voltage is that you can implement pairings using them and it might turn out that pairings on hyperelliptic curves can be more efficient than pairings on elliptic curves.

An elliptic curve is the set of points defined by an equation like

y2 = x3 + ax + b

This gives you a structure that’s much like a torus – a shape that has a single hole in it, like a doughnut.

A hyperelliptic curve is defined by an equation like

y2 = f(x)

where f is a monic polynomial of degree 2g + 1.

(There's really no reason to restrict the degree of f to being odd, and a polynomial of degree 2g + 2 will also work just as well. This makes some things trickier, so most people just stick to the odd degree case. One complication is that you actually get two different points at infinity instead of just one. More about that in a future post.)

When g = 1 this reduces to an elliptic curve, but the term “hyperelliptic curve” is usually reserved for the case where g is 2 or greater.

The number g defines the genus of the curve, a number which tells you how many holes the structure corresponding to an elliptic curve’s torus has. If the genus is 2, then the curve has a structure much like a doughnut with 2 holes, etc. The graph above is the graph of a hyperelliptic curve of genus 2.

Working with hyperelliptic curves causes some problems that aren’t there for elliptic curves. It’s possible to easily define a way to add points on an elliptic curve using the usual connect-the-dots algorithm, but this can’t be done for hyperelliptic curves. It’s possible, however, to add sets of g points on a hyperelliptic curve instead of single points. On a curve of genus 2, for example, we might add P = {P1,P2} to Q = {Q1,Q2} to get R = {R1,R2}. (Note that I've used brackets here instead of parentheses to make the notation more set-like. The order in which you list the elements isn't important for a set, and the order of the points isn't important here, either.)

The way that we add these sets of points is by thinking them as divisors, so that we're really adding divisors instead of adding points on a curve. The set of divisors on a curve, along with the rule that defines how to add them is called the Jacobian of the curve.

For a curve of genus g, we can reduce any divisor to one no bigger than one of the form

i=1:g(Pi) – g(O)

For a curve of genus g = 2, for example, we can reduce any divisor to one like

P = (P1) + (P2) – 2(O)

So that when we calculate something like

P + Q = R

for a hyperelliptic curve we actually calculating

(P1) + (P2) – 2(O) + (Q1) + (Q2) – 2(O) = (R1) + (R2) – 2(O)

How we find R1 and R2 from P1, P2, Q1 and Q2 is very similar to how we add points on an elliptic curve. In the case of an elliptic curve, we fit a line through two points, find the third point where the line intersects the curve, and reflect this point across the x-axis.

In the case of a hyperelliptic curve of genus 2, we fit a cubic polynomial to the points P1, P2, Q1 and Q2. We then find the two additional points where this polynomial intersects the curve and then reflect each of those points across the x-axis to get R1 and R2. Here’s a picture that shows what it looks like when we add the points P (the two red dots) and Q (the two green dots) to get R (the two black dots).

Image002

Because doing operations on hyperelliptic curves are defined in terms of divisors, it shouldn't be much of a surprise that pairings, that are also calculated using divisors, work just as well on hyperelliptic curves as they do on elliptic curves. That means hyperelliptic curves might end up be useful in pairing-based cryptography. If there's a good use for them, they'll probably appear in Voltage's products in the future. Right now, however, elliptic curves seem to be good enough.

Tuesday, 18 May 2010

Pathetic spammers

I received another one of those annoying spam emails from one of those operations that will include you in their exclusive Who's Who book because of your significant contributions to your field (i.e., having a valid email address). This particular spam, however, was apparently from "Satellite TV Quote." So it looks to me like some spammer couldn't quite keep his scams straight and included text from one scam in a message designed for another scam.

Come on, spammers, at least make a reasonable effort to make your messages look legitimate.

Monday, 17 May 2010

The value of privacy

Getting privacy right is tricky. People say that they want lots of privacy, but their behavior often tells us that they really don't value their privacy that much. If you promise to email someone a weekly cartoon, for example, they'll often give you lots of personal information that they claim they want to keep private.

The club cards that grocery stores are another example of this. The stores essentially pay you to let them track your purchases; they just pay you in discounts instead of cash. I was fairly surprised recently when I learned exactly how much stores pay you to let them track your purchases.

Voltage has social event every Friday afternoon. Someone buys a reasonable amount of food and drink for this event and they get reimbursed by Voltage. I bought the supplies for one of these events a week or so ago and was somewhat surprised to see that the total went from about $110 to about $85 with the discounts that my wife's club card gave me. That's almost 20 percent of the purchase.

I don't know how representative that single data point is, but if a grocery store is willing to give you that much of a discount if you let them track what you're buying, people must be fairly unwilling to let stores do this.

Friday, 14 May 2010

A new approach to outsourcing

According to the BBC, government officials in India have developed a new approach to outsourcing. This involves using prisoners in jails to run outsourced IT operations. The first projects planned to be run are actually the back-office systems for banks. I'm not entirely sure that's a good idea.

Thursday, 13 May 2010

A new approach to fighting spam?

Spam and the uncertainty that spam filters cause has dramatically reduced the effectiveness one of the most popular uses of the Internet. Maybe it’s time for a different approach to filtering email.

Phones and email are both about equally useful: given the choice between giving up their phone of giving up email, people are about evenly divided. When comparing e-mail to other Internet technologies, however, it's no contest. Given the choice between giving up email and giving up browser-based web access, people cheerfully give forgo the web in favor of email. The web may be nice to have, but email is a necessity, and most businesses really can’t function without it.

Unfortunately, almost all of today’s email traffic is spam so it’s necessary to separate the spam from the legitimate messages before they get to users’ inboxes. If you don’t do that, users are quickly overwhelmed by the sheer volume of spam that they receive.

Spammers are clever, however, and quickly find a way to get around the latest updates to spam filtering software. That’s possible because filtering applications use the latest models of what spam looks like to help them decide whether or not to let a message pass. Once spammers learn what filters look for, they quickly invent a way to get their spam past the filters.

Maybe an entirely new approach to filtering email is needed, and the fact that most email is actually spam may be the insight that we need for this. In particular, instead of trying to identify spam, why not try to identify legitimate email messages instead?

Note that this is entirely different from white-listing. With white-listing, an approved list of names, domains or IP addresses is used to allow incoming email. Instead, this approach looks at the content of an email and tries to decide if a particular message is legitimate. White listing doesn’t look for valid email messages. An entirely different model may be needed to do that.

Information security vendors have spent lots of time and effort over the past several years developing ways to identify spam. The benefits of this research have been temporary at best because spammers quickly learn to avoid the most recent versions of anti-spam filters. But while the arms race between spammers and anti-spam vendors has led to all sorts of unusual messages that are designed to pass filters undetected, the format of legitimate emails hasn’t changed much at all, and because of this, identifying legitimate emails may be a better strategy than identifying spam.

Looking for legitimate emails seems to be very simple to implement because it can be done with a minimal change to existing networks. All that’s needed is different logic on anti-spam filtering products. Everything else can stay the same. That seems much simpler than some of the alternatives that have been proposed. Simple is definitely good. It might even be effective.

I haven't heard of this approach being used. Maybe there's some obvious reason why it won't work.

Wednesday, 12 May 2010

Zn vs. Z/nZ

If you read papers about cryptography, you'll see the mathematical structure where integers are added modulo n written two different ways. Computer scientists tend to write this as Zn while mathematicians tend to write this as ℤ/nℤ. I've explained this so many times in the past year or so that I've decided to put an explanation here that I can just point people to in the future.

The notation Zn is fairly easy to understand. It's just the set {0,1,…,n-1} along with addition modulo n. The notation ℤ/nℤ is a bit trickier.

If we write the integers as ℤ where

ℤ = {…,-1,0,1,…}

then we can write

nℤ = {…,-n,0,n,…}

Elements of ℤ/nℤ are nℤ along with

1 + nℤ = {…,-n+1,1,n+1,…}

2 + nℤ = {…,-n+2,2,n+2,…}

along with an operation on ℤ/nℤ that acts just like addition, where we have that

(a + nℤ) + (b + nℤ) = (a + b) + n

It should be fairly clear that we can identify elements of Zn with elements of ℤ/nℤ in the obvious way, with a∈Zn corresponding to a + nZ∈ℤ/nℤ. Because they mean essentially the same thing, why would anyone want to use the more cumbersome ℤ/nℤ notation?

It turns out that there are lots of mathematical objects that have structure that lets you define operations on them that aren't division but that behave much like division does. In the case of group theory, for example, the third isomorphism theorem says that when some technical conditions are satisfied for groups G, H and K then we can write

(G/K) / (H/K) ≅ G/H

where the "≅" symbol indicates that the two structures are isomorphic, or essentially the same, just like Zn and ℤ/nℤ are. So while the mathematical notation may be both cumbersome and confusing, it actually can be a good way to show that there's additional structure present that the simpler notation doesn't suggest.

Tuesday, 11 May 2010

Zipf's law for data breaches

As we've seen in previous posts, there's lots of structure in the available data on data breaches. In particular, the size of data breaches seems to follow a lognormal distribution as well as Benford's law. It looks like we can add a third law that this data follows, and that's Zipf's law.

Suppose that we rank our data from largest to smallest. Zipf's law tells us that if we plot the log of the data versus the log of the rank we get a straight line. Zipf's law was first formulated based on the observation by linguist George Zipf that the frequency of words is inversely proportional to the rank of the word in a word frequency table. It also seems to hold for other data sets, like the size of US cities.

Let's look at the  the data breaches from 2007 through 2009 that are listed in the OSF's data breach database. Here's what we get when when we plot the log of the rank of a breach versus the log of the size of the breach. The blue dots represent actual data breaches. The red dots are what we get from fitting a straight line to the log-log data.

Image001 
Although the fit is much better for the breaches that aren't either too big or too small, the line actually fits the overall data fairly well, having a correlation coefficient R2 = 0.873.

Monday, 10 May 2010

Another model for usability

After reading the recent post about the usability lessons that software vendors could learn from the MMORPG Progress Quest, an alert reader suggested another good candidate for a very usable product, and that's the Holly Hop Drive, as seen in the episode "Parallel Universe" of the TV Show Red Dwarf.

Here's how the Holly Hop Drive is described in Red Dwarf:

LISTER: (Holding up the Holly Hop Drive) Is this it?

HOLLY: What do you think?

LISTER: It’s just a box with “STOP” and “START” on it!

HOLLY: It’s fairly straightforward. If you want to start it you press “START,” and you can work out the rest of the controls for yourself.

I can't say for sure whether or not the usability of Voltage's SecureMail was modeled on the Holly Hop Drive, but I don't recall it ever being mentioned. They do seem somewhat similar, though. In one case you just need to press "START" to get it working; in the other case you just need to click on "Send Secure."

Friday, 07 May 2010

Applying Shamir's Third Law

Shamir's Third Law tells us that cryptography is always bypassed instead of beaten. Here's an example of why this is true.

Suppose that you're a hacker who wants to sell credit card numbers on the black market, but all of the credit card numbers that you can get are encrypted with DES. Not Triple-DES, but the old, obsolete DES that only gives you 56 bits of strength. The same encryption algorithm that everyone dismisses as being way too weak to use.

The most cost-effective way to crack DES is probably with a COPACOPBANA machine. One of these costs about $25,000 and can find a DES key in an average of about 6.4 days. These aren't quite as fast as the DES Cracker that the EFF built back in 1998, but they're much cheaper. The TCO of computer systems is always higher than the cost of just the hardware and software, but let's ignore that for purposes of this exercise.

A COPACOBANA machine will recover about 57 DES keys per year. Over three years, this will get us about 171 DES keys at a cost of $25,000, or about $146 per key. So if you're a hacker who wants to resell the credit card numbers that you decrypt you'll need to get at least $146 for them, and that's just to break even.

According to researchers who monitor black markets, credit card numbers are worth nowhere near $146 each. Estimates that I've seen recently say that they're worth anywhere from $3 to $20 each. That's much less that what it will cost a hacker to recover them by cracking DES, so he won't try to do it. He'll find a way to bypass the encryption instead, just like Shamir's Third Law tells us.

Thursday, 06 May 2010

A very old computer

I came across an interesting old (1964) computer recently - an analog device (slide rule) designed to help reliability engineers calculate the cumulative binomial distribution. Here's what the package for this computer and its manual looks like:

Slide - manual 

Here are its instructions:

Slide - instr 
And here's what one side of the actual computer looks like:

Slide - side 1
They just don't make them like that any more, do they?   
 
 

Wednesday, 05 May 2010

Why Do People Hate Math?

How does this topic fit into a blog on security? Because crypto is an important part of security and math is an important part of crypto.

Many people say, "I'm no good at math." And then there is the subset of those who go a bit further than simply saying, "I'm no good at math." They say it with pride. I think they see math as not particularly human.To them, people who are good at math are more machine than person. Maybe they have heard that the left brain is logical and the right brain is creative, so those who are good at math are not creative and being creative is a mark of a superior human.

It is true, of course, that there are people who believe that those who are good at math are superior humans. For example, Robert Heinlein wrote, "Anyone who cannot cope with mathematics is not fully human. At best he is a tolerable subhuman who has learned to wear shoes, bathe, and not make messes in the house."

So I'm not going to say that those who think creative people are better humans (more evolved, on a higher plane than the rest of us plebians) are doing anything worse than what some in the numerate community do. But I still don't think it's a good idea: that it is better to be bad at math than to be good at it, that those who do well at math are really the lower form.

Some people who are bad at math blame the schools. "It's the way they teach math. It's too boring." Or "They make it too confusing." Or "Some people just can't explain math, and that's who I had in school."

That's possible, there are bad teachers in the world. But I also think too many people view learning as a passive activity. They sit back while the teacher does all the work. It's the teacher's job to pour knowledge and skill into the student's brain. Something I read once illustrates this. A college student had gotten a bad grade in a class and had written a letter to the dean arguing that it was undeserved. One of his arguments was that he had earned good grades in all his classes for over two years, so he was smart and teachable, meaning that a bad grade from this teacher was proof the teacher was at fault.

I think part of the problem people have with math is that it moves from memorization to thinking. When you first learn math you memorize most of it, from formulas to times tables to division rules. But later on, you are required to actually think. It starts with word problems then moves on to geometry proofs and then algebra and trigonmetry. Before, students just had to do pattern recognition: this pattern means to apply that formula. But pattern recognition does not work when the solution requires thinking. I once tutored a high school student in math. When I explained the difference between pattern recognition and thinking, she went from C's and D's to B's.

When people say, "I'm no good at math," here's what I think is happening. "I'm no good at math, it's not my fault, I was just born that way. That means I don't have to work hard. If I stress myself over this, I still won't understand it and I'll be stressed. If I just give up, I won't understand it but I won't be stressed. Either way I don't understand it, but in one scenario there's no stress."

And there you go. They don't have to try, they don't have to do any work. Life is so much easier if you never do anything difficult.

There have been times when I've tutored or helped people who claimed, "I'm no good at math." I thought I could be successful by teaching some very simple things so that they could build confidence, so that they would see that they indeed could do math. However, I quickly learned that these people refused to learn. They steadfastly and absolutely refused to understand even simple concepts. My theory was that they knew (maybe only subconsciously) that if they admitted they understood something about math, that if they allowed themselves to understand even simple math concepts, their argument "I'm no good at math," would go away and they would have to try. They would then have no excuse for failing and would then be forced to do a little hard work or else fail for no good reason. It's much easier to refuse to learn.

This is not to say that all people have natural math ability. I firmly believe that for some people, math is going to be much harder. There are indeed people whose brains are wired in a way that makes seeing math connections more difficult. It's not just math, some people have difficulty learning foreign languages, or music, or map reading, or computer programming. Or conversely, some people have brains that immediately come up with a witty remark in any situation, others will be able to know the best technique to sell a product to person A and that they'll need a different pitch to sell to person B. Some people have brains that understand math easily. Brains are wired differently.

But that's no excuse for not trying. That's no excuse for not working a little harder. And besides, I suspect that very few of the people who claim, "I'm no good at math," really have brains that just cannot make the connections to understand the basic and even intermediate elements of math. It's probably the case that many people who claim their brains are just not wired for math are either lazy or believe that non-math people are superior.

By the way, as I understand it, this attitude tends to appear mostly in the US. From what I've read, in other parts of the world, being good at math is neither a mark of superiority or inferiority. Maybe it's part of US culture that allows or even rewards people who say, "I hate math." Maybe in other cultures, children are expected to learn math just like they're expected to read. Maybe in other cultures children do not go to school with an existing fear of math.

Finding primes

In cryptography, we often need to find large prime numbers. One way to do this is to pick random numbers that are the right size until you find one that's a prime. This might take a while when we're working with numbers that are as big as the ones that we typically use in cryptography. How long will this take?

One way to answer that question is by using the prime number theorem. Let the function π(x) be the number of primes less than or equal to x. The prime number theorem says that limx→∞π(x) / (x / log x) = 1, or that x / log x is a good approximation to π(x) for large values of x.

Here's how well π(x) (black) and x / log x (red) agree:

Image001

An even better approximation to π(x) is x / (log x + 1). Here's how well π(x) (black) and x / (log x + 1) (green) agree:

Image002

But since for numbers of the sizes that we often use in cryptography log x and log x + 1 are fairly close, so we can use the easier approximation without worrying too much.

One consequence of the prime number theorem is that the probability of a number n being prime is roughly 1 / log n. Here's what log n looks like for numbers that are the sizes of those that we often use in cryptography:

n

log n

2512

354.891

21,024

709.783

21,536

1064.67

So suppose that we want to generate two random 512-bit primes, like we might need to create a 1,024-bit RSA modulus. The chances of a randomly-chosen 512-bit integer being prime is about 1 in 355, so that we'd expect to find a prime in about 355/2, or about 177 attempts.

This obviously isn't the best strategy: half of randomly-chosen integers will be even, so we don't want to waste time considering them. If we look at only odd integers, this will reduce the expected number of trials by 1/2, or down to about 89 attempts. We could even continue this strategy for other small primes. One-third of randomly-chosen integers are multiples of 3, for example, so we might not want to consider multiples of 3, etc. But for the simple strategy of just trying random odd 512-bit integers, we should expect to find a 512-bit prime in about 89 tries.

Tuesday, 04 May 2010

Is cloud security a distraction?

An alert reader recently pointed me to an on-line comment that said the following about using computers in the classroom:

My school district blocks content but students are very good at finding and sharing proxy sites. They are also not as tech savvy as administrators and school board members seem to think they are. They are no more interested in using the laptops to learn than they are in using books. The laptops simply give them a more exciting way to be off task.

The alert reader then suggested that a similar comment about cloud computing security might be appropriate. Something like "CIOs are no more interested in cloud security than they are in other aspects of security. Cloud security just gives them a more exciting way to waste time."

I don't know how well it's actually understood by CIOs, but one of the biggest security challenges of cloud computing, is also the easiest to solve, and that's the problem of not exposing sensitive data in cloud computing environments. If you just encrypt your sensitive data that goes into the cloud then most of your problems disappear. That's not wasting time. It's solving a real security problem.

The main reason that all of your problems don't totally disappear is that key management is still a problem. There's actually a good discussion of this in the report Using Encryption to Protect Sensitive Data in Cloud Computing Environments that's available from the Burton Group. That's why Voltage is now developing key management technologies that work well in cloud computing. We have some fairly good solutions or this right now and we'll have some even better ones soon.

You'll probably see those discussed at future Voltage webinars.

Monday, 03 May 2010

Proof that elliptic curves rock

http://www.sucks-rocks.com/rate/elliptic+curves

It looks like I'm not alone in thinking that elliptic curves are interesting. The collective wisdom of the Internet seems to feel the same way. Here's proof: a perfect 10 out of 10 on the sucks/rocks meter. Who ever would have thought?

Voltage Data Breach Index

  • Grab the Voltage Data Breach Index

February 2012

Sun Mon Tue Wed Thu Fri Sat
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29