Superconductor

Is RSA key generation really worse than DH key generation?

There's an interesting paper available on the IACR's eprint server: "Ron was wrong, Whit is right," by Adi Shamir and others. Here's the abstract of this paper:

We performed a sanity check of public keys collected on the web. Our main goal was to test the validity of the assumption that different random choices are made each time keys are generated. We found that the vast majority of public keys work as intended. A more disconcerting finding is that two out of every one thousand RSA moduli that we collected offer no security. Our conclusion is that the validity of the assumption is questionable and that generating keys in the real world for "multiple-secrets" cryptosystems such as RSA is significantly riskier than for "single-secret" ones such as ElGamal or (EC)DSA which are based on Diffie-Hellman.

A closer look at the data in the paper, however, suggests a simple explanation for what was observed: at some point (perhaps even continuing through the present day), some implementation of RSA had a bug in it, and that this bug managed to affect the 0.2% of the keys that the paper describes as being weak.

We'll probably find out one day which buggy implementation ended up creating these weak keys,  and we'll also almost certainly find out that this implementation of RSA hadn't been validated by a third party.

That's what certifications like FIPS 140-2 give you. They test to make sure that the implementation of their cryptographic algorithms work like they're supposed to, and that was definitely not the case with the weak keys that this paper describes. So maybe that's the best lesson to be learned from this: don't trust that an implementation of ANY security feature is done correctly, and to rely on third-party validations that security features are indeed correct.

But if it turns out that the buggy implementation was indeed validated, well, that's when things could start to get interesting.

More thoughts on the theory and practice of crypto workshop

After watching more of the presentations from the recent Is Cryptographic Theory Practically Relevant? workshop, I've come to two conclusions. First, there's definitely a serious disconnection between academic and commercial cryptographers. Next, it certainly looks like the commercial guys have a fairly good understanding of what the academic guys do, but the academic guys don't seem to have as much as understanding of what the commercial guys do.

I'm basing this on some of the comments that the academic guys made at this workshop about the differences between the two environments. I'd say that this misperception may be due to the fact that the people who thought of themselves as being "commercial" instead of "academic" tended to work for very large companies, where the interests of the R&D groups probably aren't that different from the interests of more academic organizations. If this workshop had included people from smaller companies (which it actually didn't seem to do), I'd guess that the discussion would have been a bit different. 

Another example of people not understanding encryption

The big hack at on-line game company Steam last year might not have actually exposed sensitive information becuse the data that the hackers ended up might actually have been encrypted. But according to a report at the 1Up web site,

Just because these hackers didn't break Valve's encryption yet doesn't make it impossible or prevent the criminals from selling the files to those who can.

Eh?

Let's assume that some sort of industry standard like 3DES or AES was used to encrypt this data. Cracking either of those requires so much computational power that it will be impossible anywhere on Earth in the forseeable future.

The most likely scenario for one of these algorithm being exploited is probably an encounter with aliens who happen to have extremely advanced quantum computers. And even then, cracking any symmetric algorithm is still hard enough to make it not worth the time and effort that it would take hackers to do it. Even if they're extremely advanced aliens.

So even though it's probably technically true that it's not actually impossible for someone to break today's encryption algorithms, it's extremely unlikely. You're much more to hear news about aliens landing than you are to hear about the encryption being broken. And it seems roughly as likely as finding accurate reporting on how hard it actually is to crack today's encryption.

An unexpected threat model

I learned something interesting while I was watching the video "Lessons Learned from Four Years of Implementation Attacks against Real-World Targets", one of the talks at the recent crypto theory and practice workshop.

It seems that fraud is a significant contributor to auto theft. I Googled around a bit and found claims that a typical driver in the US pays an additional $300 in premiums annually because of this. It's apparently much worse in Europe, where it's easy to drive a car to a nearby country that's not interested in cooperating with the law enforcement or insurance people of the country of the car's origin. 

So it seems that high-tech keying systems for cars deal with an odd threat model - one in which the legitimate owner of the car may actually be a bigger threat than a car thief. That's something that makes it harder to design good security protocols than it would be otherwise.

Is Cryptographic Theory Relevant?

Videos of most of the talks from the recent Is Cryptographic Theory Relevant? workshop that was held at Cambridge University from January 31 through February 2 are now available here.

 I haven't had a chance to watch all of the talks yet, but I've been fairly impressed with the ones that I have watched. The bottom line seems to be that theoretical and practical cryptographers still have lots of work to do. But with events like this workshop, people seem to be realizing what needs to be done. And if even a few of them start doing it, this workshop will definitely have been worth the time and effort that it took to organize it.

XTS in Cryptologia

It looks like the article on the XTS mode of AES finally made its way into Cryptologia. If you don't subscribe to Cryptologia, you can get a copy of the article here, although you'll have to pay either $58 for the entire issue that it's in or $43 for the single article. Either price seems a bit high to me.

A dot-com era story about digital signatures

Here's a dot-com era story that I was telling one of our engineers this morning. They suggested that I put it here, so here it is.

Back in the dot-com era, I worked for the information security group at a large accounting firm. It was called a "Big 5" accounting firm back then, before the troubles at Arthur Andersen reduced it to the Big 4. At this accounting firm we used Lotus Notes for email and other forms of collaboration, and Notes happened to give you the ability to sign or encrypt emails. This capability wasn't actually that useful because it really only worked inside the company, but that's a limitation that pretty much any email encryption product that uses digital certificates to manage public keys has.

In any event, the partner who ran the security group was very concerned that by digitally signing emails we were creating legally-binding contracts. Everyone in his group tried to explain to him how this wasn't true, but he either didn't understand what we were saying or decided not to follow our advice.

The result was a policy forbidding us to use digital signatures.

And because it can be hard to get policies changed at large organizations, I wouldn't be at all surprised if this particular organization is still forbidden from using digital signatures.

Maybe that's not quite true.

The people in this particular organization seemed to quickly figure out that their management didn't quite understand information security and there was soon a mass exodus of very talented people. I seem to recall that the group went from roughly 30 people to less than 10 people over a period of a month or two as people quickly quit and moved on to other jobs. The partner in charge of the group was quickly reassigned to a position that focused on just accounting, so it's entirely possible that his policy on digital signature use disappeared with him. But you never quite know with these sorts of policies.

Quantum cryptography gets hyped again

I just came across a story on the Science Daily web site that seems to be little more than a slightly-disguised marketing message for quantum cryptography (also known as quantum key distribution). Here's what the story claims when it describes a successful year-and-a-half pilot of QDK technology:

Scientists and engineers have proven the worth of quantum cryptography in telecommunication networks by demonstrating its long-term effectiveness in a real-time network.

This story goes on to say this:

For QKD to become more widespread in the commercial world, its reliability needed to be thoroughly tested as these networks run constantly all year round.

I don't think that that's quite right.

Instead, for QKD to become more widespread in the commercial world there needs be a compelling need for it. That's what it takes to get people to pay for technology. And because existing cryptography works just fine, I don't think that we'll be seeing the widespread use of QKD any time soon. Perhaps ever.

But if you want to read more about the actual pilot, you can find the paper that describes it here.

Academic cryptographers versus commercial cryptographers

Last night I was asked why I distinguish between academic cryptographers and commercial cryptographers. Here’s roughly what I said.

Academic cryptographers invent things. Some examples of these things are the Diffie-Hellman key exchange, RSA encryption and Boneh-Franklin identity-based encryption. Academic cryptographers also invent ways to ensure that cryptographic schemes and protocols are secure. Practice-oriented Provable Security is an example of this.

Most of the creations of academic cryptographers aren’t really very interesting to most people, but that’s not a reflection on the academic cryptographers. Most academic work isn’t very interesting unless you’re a specialist in a very narrow field, and cryptography is just like other academic fields in this respect.

Academic cryptographers need to keep producing new ideas to keep their jobs.

Commercial cryptographers worry about practical implementations of the things that academic cryptographers invent. They turn what’s in the paper “Identity-based Encryption from the Weil Pairing” into Voltage SecureMail, for example. They understand the legal and regulatory environment of business and how cryptography fits into it. And they understand the real-world constraints that make some otherwise-interesting academic creations not very practical.

Commercial cryptographers need to keep producing things that are of value to someone else to keep their jobs.

One example of the difference between academic cryptographers and commercial cryptographers is in how they understand one particular aspect of identity-based encryption. Many academic cryptographers think that the fact that systems that implement IBE inherently have the ability to do key recovery is a bad thing because it makes it possible for a rogue administrator (some would even say the NSA) to decrypt their encrypted data. Commercial cryptographers think that the ability to do key recovery is a good thing because it’s absolutely necessary due to the legal and regulatory environment of business.

From the point of view of the academic cryptographers, they’re right. They don’t want anyone to be able to get access to any data that they might encrypt. Particularly the NSA. And from the point of view of commercial cryptographers, they’re also right. The market for encryption technology that doesn’t include the ability to do key recovery is extremely small. In the real world, CIOs get hit by buses and their replacement needs access to the data that their predecessor encrypted. Even more commonly, administrators need to recover keys for people who lost their keys or forgot the password that controls access to their keys.

But not everyone understands the difference between the two approaches to cryptography. Some people in the business world try to approach cryptography from the point of view of academic cryptographers, and when they do this, it almost always causes problems. I actually come across this fairly often.

I don’t have any firsthand experience with this, but I’ve heard stories of how people in the academic world who try to approach cryptography from the point of view of commercial cryptographers also encounter problems. The places where they work typically put more value on inventing new things, so practical implementations are often considered not as good as less practical, yet new, inventions. So it’s easy to imagine an academic cryptographer who spends his time creating a successful business having problems with his academic department because that’s not the sort of behavior that they want to see.

So the bottom line is that there are really two different approaches to cryptography. The specialized background needed for academic cryptography is too expensive for most of the commercial world to support and the practical approach of commercial cryptographers isn’t really suitable for academic environments. But we really need people working on both aspects of the field if we’re going to see useful progress in the future.

#voltagelive Voltage Customer Summit Video

Cryptography and Security at arXiv.org

The best place to find preprints of papers on cryptography is probably the IACR's eprint preprint server. But it looks like there's also another place to find this type of preprint, and that's the on the arXiv.org preprint server that's maintained by Cornell. It turns out that they have a section for Cryptography and Security, although there aren't many papers there yet. Maybe it will get more useful in the future.

What does 15,360 bits look like?

According to NIST's guidelines, it takes a 15,360-bit RSA or Diffie-Hellman key to provide the same level of cryptographic strength as a 256-bit AES key.

What does a 15,360-bit key look like?

A 15,360-bit number has about 4,624 decimal digits. Here's what a number with 4,624 decimal digits looks like. It's big. Doing public-key operations with numbers that big is slow.

Don't use them unless you absolutely have to.

94598000209149914523662835549475089923370892004800021803369459826940368587029734135
53140333404205082341000224410481949851574795432979265755760040881222220641300023125
50737421110002040128607469796644894392870725815000246360649329165053448440219525634
36517708207207317900002561196904462645747774519243372965394595934258260527000261547
44526695270799535936783848823961011833211594660002794557285736789754387546224443191
19042592929274597300028424811621397344072116868487670307112059257014667000029235237
83177320889837689359141626252296630552282562000300449352494752463382445862510256196
27933565337124720003100549976546405188159961196389654692823912328729529000323596315
30726898093543335135462779745002490103393330003359808083914542726842836094970013021
24892785652010600034460588523601390922867728144077939108364770617429410003532179005
97873792524105567070078674317157853941183800036692346140620117452041595660000187439
24239711896338000371956541430017587537940419215856667436806849628520700038451551493
81947607246436679454359047900332082669541000399486431994361681085134888815530154035
45605014511760004098086248264524028404449990889639094734073544131880000413318516232
41941509498943548581886954199437548730430004280951004069638270774201512338725016252
98946246117100043797524914071961282966986102591748522053900387595790004418633325379
81450657131010246740545561427779389193600045740294390277557322709779017119525275802
18081451748000465417845611809933714305335129695612719255360409032400047116644988352
07984827593817153909973334408846123356000484832477928312496471002295368703230757546
15020099940004969074941388763791976355840440110518216150184876938000500918820097328
25395270422086304833898737464278580440005190045854975198150654949388199791870761506
84766465900052731895020747677262696229064464271246701841361827600005375768764902097
18774990429122729537505871938234317800054540164405666281310030068227398207145329507
70617813000550835869910785424278513661588730461897553312230842000056283060326481333
10591405100789332604604759411901840000575384086233815941362851215902902846668795777
62207910005891757537416161362269502639021255781765148348347055000598941592694003975
83911260717646489497230694541374080006077513038208686429901684148277451908139807289
35550700061195023717469979202885521029773742877525165344674150006221818593139327881
75705686731560708285046318533845200063514746649968107236219404991345428360919108007
45449000649955968331625352417069777128307481978142438607283400065337134800793584728
69519266472158303298229317493972000668527486893113032297028834341377351590400711484
36430006784133896404403552166738527009161222605616232718423000685673216234173959613
11012391622854965756081604188800006965138568068764885261343136586145875210698564447
27700070380010217681719117117160292937742196404965584496980007137402963970130477586
56271100864732462605400303743800072971254034887083314172181539250752376204715501295
78000732182641134471433407264638859024913906441038565455200074731354274295719090358
57947429608789881566469119202000750763877929030611807296207441562382199538047136699
40007660528834410795419814591752069505533521396121206455000778359635655069589298305
12809719774335378392301504980007810850627469959910507134990631953075718390641019362
00079398209895243622631476442180814438000935131024731670008059580064787556978800888
35544862376806156041110840800081385080734123793487639082297022177190420795954499530
00823069270668946881612756196800918206763400054626920000083654439565918288274374963
22404108337656769629990836000842726750264131927229407477446061798548911973413035800
08591307069911907224210366995372828825357932897666252000866843494688844731362262126
98408128438259009815931460008748908158775474524591357000475483824526925413055160000
88069134519742672786011188309528630119890114974403440008910455160191421033712913423
78218832580851436677088300090128839734365027611840428501392179741507790712267690009
12177830976388073696131649420966328102023088164744900092195235951565122596598628368
25869572137981643591529000936724552670355831656379246866867646334222266559080200094
60584473770750037992451342652926760836374132644344000955385341377360669485058838738
59493647333196240436420009624637387367438489342526230799212369186010374283873000978
30801245138992228150775951777973772758551972378670009816444243343615199073274937093
98513032552548465475900099607901815757178657621116178576458195297965130048600010003
99110461937161689466083246538460958232886181916100101385559555432886597800835560860
29735477627129923853001021754673704920524621555121292815907607936279545890900103326
43528619581906831009119893676355937798086300514001046957268

Data-centric security for a data-centric world - #voltagelive 2011 in NYC

New innovation and emerging technology brings with it opportunities for streamlining costs, eliminating hurdles for end users and reducing risks to the business. However, implementing game changing solutions can be unique to your environment, policies and processes.

That's why I invite you to join Voltage Security at its first customer summit in New York City on November 9, 2011. The summit will focus on data-centric security and will feature top Voltage customers such as Amex, Wells Fargo, State Street and others, who will discuss how they implemented encryption projects for mail, data and payments. Also presenting will be Eric Ouellet, research vice president with Gartner Group, who is currently developing new analyses of how companies use encryption. The summit features customers talking to customers—at last count this includesAmerican Express, BJ's Wholesale Club, Citigroup, Deutsche Bank, Fidelity Investments, JPMorgan Chase, UBS, State Street Bank andWells Fargo. The goal of the summit is to enable Voltage customers to network with each other and pick up valuable best practices. If you're interested in attending, please visit www.voltage.com/live.

The theme is 'Data-centric Security for a Data-centric World,' it's an area of huge attention. Data is the lifeblood of industry, commerce and leisure, every business and every transaction. That's why protecting it is such a serious and difficult responsibility. 

Here's a quick scan of the Hot Topics we have on tap at Voltage Security Live 2011:

Cloud Data Security Data-centric Encryption Ecommerce Security

Email Encryption Mobile Data Security Payment Security

There's no question that every company continues to face a long serious of challenges related to these topics. The conference is designed to tackle specific issues and help formulate achievable solutions. The areas to be covered include:

• How to fund and integrate a data-centric strategy into your overall security program
• Best practices for data-centric encryption based on real-world implementation at a Fortune 50 Bank
• How to roll out encryption projects successfully across the organization and end-user community
• Successful phases for fast and non-disruptive implementation—what you need to do before during and after an implementation
• Elements of key management architecture and design
• The role of cloud and mobile data-centric security

Voltage Security Live 2011 will bring together the brightest minds in our field, all with considerable experience. There will be representatives from teams responsible for implementation, as well as enterprise and security architects looking for, and developing, best practices for data-centric encryption. 

The sessions will cover customer project case studies addressing issues such as how to maximize end-user adoption for your B2C implementations and implementing data-centric encryption projects, while the Customer Track focuses on panel discussions and presentations on topics such as protecting outsourced data, eDiscovery and Archiving and securing application emails. There's also an Architecture Track, featuring panel discussions and presentations on topics such as key management architecture, security policy, enterprise applications and the web services API and scalable design considerations. And there's the Security Panel, with a discussion and general Q&A featuring leaders from the security community—Gartner Security Analyst, Encryption Architects, QSAs. 

There's going to be a broad cross-section of security specialists attending, but some executives will find it particularly enlightening: CXOs and security leaders responsible for security strategy and programs; VPs/Directors responsible for security implementation; and architects responsible for security and application and enterprise architecture. If you have one of these roles, we think this conference is exactly right for you. 

We know there are constant demands on your time - we hope to see you there.

Register at www.voltage.com/live

The OB-PRNG?

In a previous post, I described how to use the ever-changing structure of large organizations to create a good source of random numbers. One obvious abbreviation for this approach is "OB-PRNG," for "organization-based pseudo-random number generation."

If you're a fan of Brian Keene's zombie stories, you might find the reference to Ob particularly appropriate in the context of working for large organizations. If you're not a fan, Ob is the powerful supernatural being that's behind the world being destroyed by zombies in The Rising.

Elliptic curves over GF(p^n)

When we implement pairing-based cryptography, we end up working in some extension GF(p^k) of GF(p). I get lots of questions about exactly what the difference is between these two cases, so here's a simple example of exactly what this looks like.

Suppose that we have the elliptic curve E: y² = x³ +1, which has embedding degree 2 over GF(p) when p ≡ 2 (mod 3). What does E(GF(11²)) look like compared to E(GF(11))?

Here are the points of E(GF(11)). Each of these points satisfies the equation y² = x³ +1. There are 11 finite ones plus O, for a total of 12 points.

(0,1)
(0,10)
(2,3)
(2,8)
(5,4)
(5,7)
(7,5)
(7,6)
(9,2)
(9,9)
(10,0)
O

It gets a bit complicated because a point in E(GF(11²)) looks like (x,y) = ((x₁,x₂),(y₁,y₂)), so that we have two coordinates, each of which has two different components. We usually combine the two components of each coordinate into a single complex number, so we think of ((x₁,x₂),(y₁,y₂)) as being (x₁+ix₂,y₁+ iy₂).

Here are the points of E(GF(11²)). Each of these points also satisfies the equation y² = x³ +1. The points of E(GF(11)) are still there, but we've also added quite a few more. There are 121 finite ones plus O, for a total of 122 points.

(0,1)

(0,10)

(1,3 i)

(1,8 i)

(1+3 i,1+6 i)

(1+3 i,10+5 i)

(1+4 i,1+8 i)

(1+4 i,10+3 i)

(1+7 i,1+3 i)

(1+7 i,10+8 i)

(1+8 i,1+5 i)

(1+8 i,10+6 i)

(2,3)

(2,8)

(2+10 i,5+5 i)

(2+10 i,6+6 i)

(2+4 i,5+3 i)

(2+4 i,6+8 i)

(2+7 i,5+8 i)

(2+7 i,6+3 i)

(2+i,5+6 i)

(2+i,6+5 i)

(3 i,4+9 i)

(3 i,7+2 i)

(3,4 i)

(3,7 i)

(3+10 i,2+2 i)

(3+10 i,9+9 i)

(3+2 i,3+i)

(3+2 i,8+10 i)

(3+3 i,4+7 i)

(3+3 i,7+4 i)

(3+8 i,4+4 i)

(3+8 i,7+7 i)

(3+9 i,3+10 i)

(3+9 i,8+i)

(3+i,2+9 i)

(3+i,9+2 i)

(4 i,2+6 i)

(4 i,9+5 i)

(4,10 i)

(4,i)

(4+10 i,4+3 i)

(4+10 i,7+8 i)

(4+3 i,1+i)

(4+3 i,10+10 i)

(4+4 i,1+2 i)

(4+4 i,10+9 i)

(4+7 i,1+9 i)

(4+7 i,10+2 i)

(4+8 i,1+10 i)

(4+8 i,10+i)

(4+i,4+8 i)

(4+i,7+3 i)

(5,4)

(5,7)

(5+10 i,2+i)

(5+10 i,9+10 i)

(5+3 i,3+6 i)

(5+3 i,8+5 i)

(5+4 i,3+8 i)

(5+4 i,8+3 i)

(5+7 i,3+3 i)

(5+7 i,8+8 i)

(5+8 i,3+5 i)

(5+8 i,8+6 i)

(5+i,2+10 i)

(5+i,9+i)

(6,5 i)

(6,6 i)

(6+2 i,3+4 i)

(6+2 i,8+7 i)

(6+3 i,1+7 i)

(6+3 i,10+4 i)

(6+4 i,4+6 i)

(6+4 i,7+5 i)

(6+5 i,4+10 i)

(6+5 i,7+i)

(6+6 i,4+i)

(6+6 i,7+10 i)

(6+7 i,4+5 i)

(6+7 i,7+6 i)

(6+8 i,1+4 i)

(6+8 i,10+7 i)

(6+9 i,3+7 i)

(6+9 i,8+4 i)

(7 i,2+5 i)

(7 i,9+6 i)

(7,5)

(7,6)

(7+2 i,5+4 i)

(7+2 i,6+7 i)

(7+5 i,3+2 i)

(7+5 i,8+9 i)

(7+6 i,3+9 i)

(7+6 i,8+2 i)

(7+9 i,5+7 i)

(7+9 i,6+4 i)

(8 i,4+2 i)

(8 i,7+9 i)

(8,2 i)

(8,9 i)

(8+3 i,5+10 i)

(8+3 i,6+i)

(8+8 i,5+i)

(8+8 i,6+10 i)

(9,2)

(9,9)

(10,0)

(10+10 i,5+9 i)

(10+10 i,6+2 i)

(10+2 i,2+3 i)

(10+2 i,9+8 i)

(10+4 i,2+4 i)

(10+4 i,9+7 i)

(10+7 i,2+7 i)

(10+7 i,9+4 i)

(10+9 i,2+8 i)

(10+9 i,9+3 i)

(10+i,5+2 i)

(10+i,6+9 i)

O

 

Webcast - What's New in Crypto for z/OS?

Our marketing people are having another of their fine webcasts. This one tells you about what sort of new encryption technology is available for protecting data on z/OS mainframes. It's sponsored by IBM and will take place at 10 a.m. (Pacific) on November 15, 2011 and will last for 60 miniutes. If this sounds interesting, you can sign up for this event here.

Here's an overview of what this webcast will cover:

Mainframes remain the core of business-critical operations in most of the world's largest and most successful enterprises, including those in banking, insurance, healthcare, and retail. But as IT management will attest, there can be issues with complexity when it comes to securing critical information on the mainframes running on z/OS.

Implementing an encryption solution can be disruptive to business operations and require hundreds of lines of code to acquire and store keys and perform cryptographic operations. Adding to the complexity are the deep expertise and highly specialized knowledge needed to keep all the moving parts working. Not only that, roughly 80% of z/OS customers use CICS, yet many vendors offer no developer abstraction to make it easy to encrypt from CICS transactions.

In this webcast we'll discuss proven strategies for easily implementing data security in the z/OS environment.

We'll also cover:

• Extending the proven security and defenses of the mainframe to protect information assets against new world threat to data 
• Pros and cons of various types of encryption and key management
• Achieving system interoperability with a data security platform approach
• Simplified key management that virtually eliminates key management issues
• A native z/OS encryption implementation that's easy to use with CICS or any z/OS environment

Telling the future with Cleverbot

It looks like we won't be using anything except elliptic curves or hyperelliptic curves for a while. At least that's what the almost-certainly-authoritative Cleverbot thinks will happen.

  

Voltage Customer Summit #VoltageLive - Only 23 Spaces left

 *** Only 23 spaces left ***

Voltage Security invites you to "Voltage Security Live 2011" at Bridgewaters in New York City on November 9, 2011. This customer summit will focus on data-centric security and will feature several leading Voltage customers, such as American Express, Wells Fargo, State Street and others, who will discuss how they have implemented encryption projects for email encryption, data-centric encryption and end-to-end payment encryption. Also presenting will be Eric Ouellet, research vice president with Gartner Group, who is currently working on a new analysis of how companies use encryption. The goal of the summit is to enable Voltage customers to network with each other and pick up valuable best practices.

Stop Press: Thanks to our sponsors - Coalfire, OpenPath, Teradata and Thales, we are able to offer registration for eligible particpants at no cost.  Register now at www.voltage.com/live

Join Voltage customers including: ADP, American Express, Bank of America, AT&T, Citigroup, Deloitte, Deutsche Bank, Elavon, Fidelity Investments, Heartland, JPMorgan Chase, McGraw-Hill, UBS and Wells Fargo. 
.
Highlights of the agenda include:

• CxOs Panel – Business dynamics for data-centric encryption security – How to get your security project funded
• Key Note – Eric Ouellet, Vice President Research, Gartner Group                      
• How to maximize customer adoption – Kim Mroczkowski, Wells Fargo
• 4. How to structure a data-centric encryption project – Emily Mossberg, Deloitte
• 5. “Birds of a Feather” Networking lunch
• 6. Tracks: Customer and Best Practices – American Express, State Street, Thales, PwC, Coalfire 
• 7. Security Leadership Panel – Gartner Group, State Street, American Express, Wells Fargo

Stop Press: Thanks to our sponsors - Coalfire, OpenPath, Teradata and Thales, we are able to offer registration for eligible particpants at no cost.  Register now atwww.voltage.com/live 

 

The distribution of letters in Neverwhere

Suppose that you're a cryptanalyst. To do your job of cracking encryption, it's very useful to know what the underlying plaintext looks like. In English, for example, the letter "e" occurs more often than any other letter, and you can often make good use of that fact if you're trying to crack some encryption schemes. There are estimates for how frequently the letters of the alphabet appear in English words, but do those estimates hold in just a few cases, or are they fairly good in most cases?

I recently came across my elctronic copy of Neil Gaiman's Neverwhere, which, if my shell script worked correctly, has the following distribution of letters in it:

That's not too far from what you'd expect from English words, which is something like this:

And here's what the two distributions look side by side. There doesn't look like there's that much difference between them. The extra occurrences of the letters "d" and "h" in Neverwhere are probably from the frequent uses of the name of the protagonist (Richard).

I'll have to try a few more examples some day to see how much the source of the words affects the distribution. I seem to recall that the "usual" distribution for English letters is based on text from some newspaper (perhaps the New York Times?), and it's actually a bit surprising that we see roughly the same distribution in a work of fiction like Neverwhere. (OK, newspapers can also be works of fiction, but most people don't think of them as being that way.)

Encrypted QR codes for Android

I just came across an interesting application that's available for Android devices. This particular app let's you create and read encrypted QR (quick response) codes.

QR codes are those images that you see that look something like this:

These were created by Toyota back in 1994 to help track vehicles while they were begin manufactured, but now they're widely used in cell phones and other portable devices. Just take a picture of the QR code and many portable devices can easily translate that picture into a URL, phone number, or whatever was encoded in it. If you're really interested in how these work, you can find out in ISO/IEC 18004:2006 ("Information technology -- Automatic identification and data capture techniques -- QR Code 2005 bar code symbology specification").

The good thing about QR codes is that they're a standard, so anyone with a standards-compliant device can read one. But that also means that there's no privacy for information in QR codes because anyone with a standard-compliant device can read one. One workaround for this is to encrypt the data in a QR code, and that's just what QR Droid lets you do. It uses password-based encryption, so a typical use might be to encrypt those potentially-compromising pictures that you post on Facebook and to only share the password with your friends, thereby keeping any nosy HR people from blackballing you from future jobs because of what you did on your vacation to Cozumel.

Password-based encryption isn't very secure, of course, but it might be secure enough to protect the privacy of what you post on Facebook. If that's what you need, then QR Droid might be just what you're looking for.

A Simpler Approach to Encrypting z/OS Data

To some, mainframes are seen as dinosaurs, technology that is obsolete or should be. However, this veteran platform has shown its resilience in enterprise computing for a reason. The benefits it offers to the corporate infrastructure - extreme scalability, high throughout, high availability - are matchless.

However, as IT executives responsible for running mainframes or other platforms with z/OS can attest - there are issues regarding complexity. For example, traditional encryption solutions can require hundreds of lines of code to acquire and store keys and perform cryptographic operations. And that isn't even the biggest problem; it's the knowledge required of all the moving parts of an application to ensure effective operation. And of course, with all that code and other complexities, there's more room for error. 

That's why developing an encryption solution based on Format-Preserving Encryption to address the mainframe environment was an interesting challenge - and it's been met. 

In response to customer requests, Voltage has now developed command line tools and a simple API that dramatically reduces the number of lines of code needed - from hundreds to just three. Now, companies of all sizes benefit from using Format-Preserving Encryption on the mainframe, including the ability to "encrypt here, decrypt there." This helps avoid the ASCII/EBCDIC issues that plague most cross-platform encryption solutions.

But that's not all. Engineers at IBM Hursley - the software development lab in Winchester, U.K., home to many of these technologies - point out that 80% of z/OS customers use CICS, the transaction server that's critical for mainframe operation. Unfortunately, many vendors still don't support CICS. Even IBM, which provides advanced encryption interfaces built into z/OS, has no developer abstraction to make it easy to encrypt within CICS environments. Traditional solutions for encrypting data rely on POSIX facilities, which are incompatible with CICS. 

Now, in a major step forward for cryptographic operations encompassing CICS and other z/OS environments, Voltage is introducing z/Protect, part of the Voltage SecureData product family. z/Protect provides even higher application data-level abstraction, requiring just one line of code to accomplish what used to take hundreds. More to the point, no one likes to mess with mainframe applications, and the z/Protect approach means even fewer modifications. 

To learn more about this innovative approach, which perfectly complements IBM's advanced cryptography on z/OS, here's a presentation introducing Voltage SecureData z/Protect.

PKI: Lemon Markets and Lemonade

Just in case you missed Peter Gutmann's talk "PKI: Lemon Markets and Lemonade" at the 2011 RSA Conference, the slides from his talk are now available (PDF) on his web site.

This talk had some interesting things to say about some of the problems that PKI faced in its early years and how the that vendors dealt with these problems led to disaster. It's easy to reconstruct the talk from just the slides, and there's lots of interesting material in them.

What Google correlation tells us about encryption

Google correlation lets you find correlations in what's being searched for. I tried it a few times and got an interesting result or two. The first thing I did was to see what searches are correlated with "encryption." I wasn't surprised at all to see that searches for "database" are strongly correlated with searches for "encryption."

 

But when I checked to see what searches are correlated with searches for "cryptography" I got something that I didn't quite expect, and that's that there's a strong correlation between searches for "cryptography" and searches for "modulation." That's something that I really can't come up with a good explanation for.

 

Even harder to explain are the high correlations between searches for my name and for "Greek God" (r=0.8761) or "bear care" (r=0.8461). Finding the best explanation for those might be the basis for a contest in which the winner gets a free year of our cloud-based email encryption service. I'll have to mention the idea to the people who run our cloud service the next time I talk to them.

Ate pairing or ate pairing?

The ate pairing can be very useful for implementing pairing-based cryptography because it can be much faster that either the Tate or Weil pairing. It's what all of our shipping products are moving to for that very reason.

Note that the first letter of "ate" isn't capitalized while the first letters of "Tate" and "Weil" are. That's because the Tate pairing is named after John Tate and the Weil pairing is named after André Weil. The ate pairing isn't named after anyone, however, so the word "ate" isn't capitalized.

And that's a good thing. It turns out that if you capitalize it, you end up with the Greek goddess Ate. Here's how the Encyclopedia Mythica describes her:

The Greek personification of infatuation, the rash foolishness of blind impulse, usually caused by guilt and leading to retribution. The goddess of discord and mischief, she tempted man to do evil, and then lead him to ruin. She once even managed to entrap Zeus, but he hurled her down from the Olympus. Now she wanders the earth, as a kind of avenging spirit, but still working her mischief among mankind. Her sisters, the Litai, follow her and repair the damage she has wrought to mortals.

So never capitalize "ate." That may give you a pairing that you really don't want to use.

Visualizing FIPS 140-2

Because it was so much fun to create a visualization of the Common Criteria last week, I decided to try the same thing with FIPS 140-2, the US government's Security Requirements for Cryptographic Modules. Here's what I got. It's clearly a very focused document, isn't it?

 

JPMorgan Chase awards Voltage Security for Data-centric Encryption Innovation

At the J.P. Morgan Technology Innovation Symposium, yesterday afternoon, JPMorgan Chase inducted Voltage Security into its Innovation Hall of Fame in front of hundreds of Silicon Valley executives. 

Only two vendors were selected in this year's awards which recognize top emerging technology vendors for business impact, measured in terms of driving value for the firm, disruptiveness of technology and the overall quality of the partnership. Voltage was selected by top IT executives at JPMorgan Chase for its innovative data-centric encryption approach for protecting structured and unstructured data across datacenters, the cloud and mobile devices.

 

"In an environment of ever-increasing threats, secure communications are critical to our business and our clients." 

- Guy Chiarello, Global CIO of JPMorgan Chase.
 

"Voltage's stateless key management technology is enabling JPMorgan Chase to roll out secure communications on a global scale with an excellent time-to-market." 

-Anish Bhimani, Chief Information Risk Officer of JPMorgan Chase. 

   

http://www.voltage.com/pressreleases/PR111005-Voltage-JPMC-Innovation-Award.htm 

 

AES-XTS in Cryptologia

 

It looks like a paper that I wrote with Matt Ball (Google), Cyril Guyot (Hitachi), Jim Hughes (Huawei) and Landon Noll (Cisco) will be appearing in a forthcoming issue of Cryptologia. The current title of this paper is "The AES-XTS Disk Encryption Algorithm and the Security of Ciphertext Stealing," although that's certainly subject to change.

AES-XTS is a product of the IEEE Security in Storage Working Group and is one of the few modes of AES that has been approved (PDF) for government use by NIST. The Cryptologia paper will describe both the motivation for creating AES-XTS and its proof of security, and if you have more than a casual interest in AEX-XTS, it might be worth tracking down once it's out.

AES-XTS is a mode of AES that's meant to be used to encrypt hard drives. It's particularly useful for this because it encrypts sectors of a disk in a way that creates a ciphertext that's the same size as the original plaintext disk sector. In other words, it's a format-preserving mode of AES, much like the AES-FFX mode that NIST is now considering.  

Rot13 twice

When you're working with potential customers of information security products you often come across people who really don't understand the technology. And there's nothing at all wrong with that at all. Information security is a fairly arcane area, and encryption is probably the most arcane part of this arcane field. But you meet people now and then who don't know what they don't know, and it can be tricky to work with people like that. A former coworker recently told me a story about he dealt with one of these people.

At one particular customer, the story went, there was a person who always had to ask questions about something. Many of these were about things that he know absolutely nothing about. Many of them were also totally irrelevant to the solution that was being discussed. In the middle of a presentation, this person suddenly became interested in how a particular bit of data was encrypted.

"We just use Rot13 twice," said the annoyed sales engineer.

"Oh, OK," said the potential customer.

Apparently some of the other people understood what this meant because they snickered silently behind their coworker's back. But the answer was apparently good enough, because the deal was eventually closed, showing that even Rot13 applied twice can sometimes be good enough.

Units for the security of AES-256

 

In a previous post I suggested that solar mass units (about 2 x 10³⁰ kg) might be a good unit to measure the amount of computers needed to crack a 256-bit AES key. Is this really the case?

The EFF's DES Cracker could try about 92 x 10⁹ keys per second. Let's assume that that machine weighed about 20 kg and round up the number of keys per second to about 10¹¹. That means that that machine could try about 5 x 10¹² keys/(sec kg). Let's assume that we have a machine that's 1 million times faster for the same mass. That's probably not too realistic, but if we assume that then we get that our hypothetical machine can test about 5 x 10¹⁸ keys/(sec kg).

That means that to recover a 256-bit key in one year we need

2²⁵⁶ keys x (1 sec kg / 5 x 10¹⁸ keys) x (1 yr / 31 x 10⁶ sec) x (1 SMU / 2 x 10³⁰ kg)

= 4 x 10²⁰ SMU

of our hypothetical computers.

So it looks like I was actually wrong. Solar mass units really aren't big enough to measure the computers needed to crack a 256-bit AES key. Maybe a more appropriate unit would be a galactic mass unit. The Milky Way galaxy has a mass of about 2 x 10¹¹ SMUs, so it would take about 2 billion GMUs of computers to crack a 256-bit AES key in a year. Maybe even that unit isn't big enough.

More crypto misinformation

I just came across another example of a journalist writing about encryption in a way that isn't even close to being accurate. I try to sympathize with journalists because encryption can be very hard to understand, but this discussion was so far off that I had to mention it.

Here are some of the things that this particular article said:

Today, AES-256 should be considered the minimum security standard employed on any network. Though theoretically it is a vulnerable algorithm, the equipment required to attack AES-256 is still measured in acres.

You would be unlikely to sneak that much gear into somebody’s data centre, or park it outside, without being noticed. Nor is there any chance of being able to attack AES-256 remotely: the bandwidth requirements would be extraordinary.

Where are people getting the idea that AES-256 is the minimum acceptable level of security from? (Maybe the dubious report that I mentioned here?) Exactly ZERO of the standards that cover the business use of encryption recommend this. And if AES-256 isn't good enough, what are we supposed to move to? AES-257? Or should we just skip ahead to AES-666 to ensure that hackers will have a devil of a time recovering our sensitive information?

And the equipment needed to attack AES-256 isn't best measured in acres. A better unit is probably solar mass units (about 2 x 10³⁰ kg)! That's how much computing power is needed to crack a 256-bit key. The number 256 may not be very big but 2²⁵⁶ is so big that it's very hard to really understand how big it is. And that's the measure of how long an attack on AES-256 will take.

And why would you need massive amounts of bandwidth to carry out an attack against AES-256? The attacks that we're talking about that take somewhere between a zillion and a squillion years to carry out use lots of computing power, but they essentially use no bandwidth at all. Unless you're talking about the communications between a processor and storage, but that's not the case here, is it?

Why do articles like this one bother me?

Mainly because there's always someone who reads this sort of misinformation and sends a panicked email to one of our sales or marketing people.

"OMG! I just read that AES-256 is weak! What should I do?"

The sales or marketing people, in turn, hand these over to me, so I get stuck explaining why the fact that some astronomers no longer consider Pluto to be a planet really doesn't give hackers a way to decrypt sensitive information. Or whatever the most recent story is talking about.

JASON on cryptography

Not much of the field of information security can really be considered a science. The only part that can is cryptography. Here's how the JASON group report Science of Cyber-security (PDF) described this:

Cryptography, which examines communication in the presence of an adversary and in which the assumed power of that adversary must be clearly specified is viewed today as a rigorous field, and the approaches pursued in this area hold useful lessons for a future science of cyber-security.

Now if we could just make the rest of the field just as rigorous, lots of our problems would get much easier.

The helicopter story

Several years ago, back when I was in the army, I had an interesting experience on a training exercise that I'm often reminded of when I hear people talking about the tradeoffs between security and usability. On the particular occasion that I'm reminded of, we had helicopter gunship support. The purpose of the exercise was really for us to become familiar with helicopters: how they move, what their capabilities, and so on. I also learned a lesson that I can now apply to information security, but that certainly wasn't part of the original plan.

We were directing the helicopters towards their targets and making jokes at the expense of the pilots ("In my platoon I have PFCs driving the vehicles," etc.) when we had a problem with our secure communications. That gave us two choices: we could either not get the gunship support or we could flip a switch and talk in the clear.

This decision wasn't hard to make, and once you've felt your brain go through that thought process, it becomes fairly clear that useful secure communications have a property that's sometimes not considered: it needs to not get in the way of people getting their jobs done. If people are given a choice between being secure and not getting their job done and being non-secure and getting their job done, the security will always lose.

Celebrating Ten Years of Identity-Based Encryption (IBE)

Over the past 10 years, IBE has become the one of the fastest deployed encryption technologies as measured by the commercial adoption of Voltage SecureMail™ and the use of IBE as a general purpose key management solution used across the Voltage Security product line. Since its commercial launch 8 years ago, Voltage SecureMail has become one of the most widely adopted secure email products in the world with over one billion secure business emails sent annually and over 50 million worldwide users; those numbers are expected to double by 2014.

IBE was first introduced on Tuesday August 21 at the 2001 Crypto conference in a seminal paper by Dan Boneh, Stanford University, and Matt Franklin, University of California Davis. The paper, entitled “Identity-Based Encryption from the Weil Pairing,” set forth a simple but powerful approach for encrypting information with identity-based keys. This cryptography breakthrough became the founding technology for Voltage Security that was incorporated in 2002 by three Stanford students working with Professor Boneh: Matt Pauker, Rishi Kacker and Guido Appenzeller. In July 2003, the new company launched Voltage SecureMail, an email encryption product using IBE to secure messages without the difficulties and expenses of traditional certificates.

Key metrics in the 10 year history of IBE:

• 50 million Voltage SecureMail users worldwide.
• Approximately one billion IBE secured business emails will be sent in 2011.
• By 2014, it is estimated there will be 100 million Voltage SecureMail licensed users and over two billion secure emails will be sent that year.
• All the messages protected by IBE in 2011, if printed out, would circle the globe seven times.
• Nearly a third of the world’s 20 biggest public companies (per the Forbes Global 2000) have standardized on Voltage SecureMail.

 World’s Biggest Companies Standardize on Voltage SecureMail

Nearly 30% of the world’s 20 biggest public companies (as listed by Forbes Global 2000) have standardized on Voltage SecureMail powered by IBE including four of the world’s largest global financial institutions; one of the world’s largest retailers, one of the largest U.S. managed healthcare providers and several large regional healthcare providers.

 

 

 

Notable Voltage SecureMail customers from the last year include:

• One of the largest Wall Street banks with over 230,000 employees standardizes on Voltage SecureMail
• A major Wall Street bank and Fortune 100 financial services provider with global operations chooses Voltage SecureMail for its 100,000 employees around the world.
• A major credit card brand with over 60,000 employees standardizes on Voltage SecureMail
• An award-winning regional health care organization replaces a non-functioning email security solution from one of the largest technology companies in the world with a policy-based encryption solution from Voltage SecureMail

• A Fortune 50 global financial services company deploys Voltage SecureMail to over 320,000 internal and several million external users across 86 countries, replacing an aging PKI-based encryption technology.

In addition, over 1000 enterprise companies have standardized on Voltage SecureMail, and thousands of mid-size to smaller business use the cloud-based Voltage SecureMail Cloud™ solution to protect private and confidential information.

More information at www.voltage.com

Strong cryptography and the PCI DSS

The PCI DSS requires that credit card numbers are protected with "strong cryptography" or something equivalent. That's usually interpreted as meaning encryption that provides the equivalent of 112 bits of strength, like you get with three-key Triple-DES or an RSA key of 2,048 bits. But no way of protecting credit card numbers will get close to that much security. Here's why.

The strength of a way of protecting sensitive data is as strong as the easiest way for an attacker to recover the sensitive data. If the easiest way for him to do this involves cracking an encryption key that provides 112 bits of security, that's how much protection the sensitive data has. If there's an easier way, say one that takes only the effort equivalent to cracking an 80-bit key, then the data only has 80 bits of security. 

And that's exactly what we have with credit card numbers.

There are only 10¹⁵ possibilities for a typical 16-digit credit card number because the final digit is a checksum that's determined by the previous 15 digits. That means that an adversary can guess any credit card number in no more than 10¹⁵ attempts.

That's roughly the amount of guesses needed to crack a 50-bit cryptographic key (10¹⁵ is about 2^49.8), so that it's essentially impossible to get more that 50 bits of security for a 16-digit credit card number. It also means that worrying about "strong encryption" really isn't worth it. A 112-bit key won't provide any more security than a 50-bit key does because they're both equally hard to defeat.

There are lots of people in the payments industry who spend lots of time worrying about whether or not particular techniques qualify as "strong cryptography." It certainly looks like they ought to stop worrying about this particular issue and move on to more useful things.

AES cracked - or is it?

There's new research that's being described as saying that the AES encryption algorithm has been "cracked."

I'm probably not alone in dreading these sorts of stories. Many people who work for encryption vendors probably feel the same way about them because they always end up being a distraction for a week or so as we explain to people why their sensitive data is still safe, even if hackers have access to the latest and greatest attack.

The headlines often aren't quite true, but that that doesn't stop lots of people from worring about exactly what's what. And that's understandable, because most people really don't care about the details of encryption. And they shouldn't. As Calvin Coolidge might have said if he were around today, "The business of America is business, not worrying about the arcane details of encryption."

So what's the bottom line this time and how does it affect the security of any sensitive data that you're encrypting with AES?

Here's the way that Andrey Bogdanov, one the researchers who found this weakness in AES, described the implications of this new attack:

The practical consequence is that the effective key length if AES is about 2 bits shorter than expected - it is more like AES-126, AES-190 and AES-254 instead of AES-128, AES-192 and AES-256.

So we're looking at reducing the security provided by an AES key by about 2 bits, or about a factor of 4. But because even the weakest AES keys, the 128-bit keys, require hundreds of billions of years on implausibly-powerful supercomputers to crack, knocking off 2 bits is really no big deal. That might reduce the time needed to crack a key from 100 billion years to only 25 billion years, for example, which is still isn't the sort of attack that's practical for a hacker to do. And it's one that probably never will be.

So the work by Andrey Bogdanov, Dmitry Khovratovich and Christian Rechberger (BKR) that's being described as leading to AES being cracked really isn't really worth losing sleep over. Even if hackers only have to do one-quarter of the work that they would have otherwise needed to do to crack an AES key, this still leaves them with an impossible amount of work left. So much work that they'll never try to actually carry out this attack.

So the bottom line is that if the BKR attack is the best that a hacker can do, your data's still extremely safe.

An ENIGMA machine at the Computer History Museum and FPE

 

The Computer History Museum is close to Voltage's headquarters. We're in Cupertino and museum's in nearby Mountain View. On a recent visit to this museum I noticed that they had an ENIGMA cipher machine, the machine that the Germans used to encrypt lots of their military communications in World War II. The Allied cryptographers were eventually able to break the ENIGMA cipher, and this let them decrypt and read lots of German military communications.

Part of the reason that the Alllies were able to do this was due to the way that the ENIGMA cipher was designed so that it would never encrypt a symbol to itself. So a plaintext "A" would never get encrypted to a ciphertext "A," even though you'd expect this to happen about 1 time in 26 (if a 26-letter keyboard was used). The fact that it never did proved very useful in the cryptanalysis of the ENIGMA cipher.

Now skip ahead a few decades and you get to the present day.

Instead of using cipher machines like the ENIGMA, people are commonly using AES to encrypt sensitive information. One way that's getting very popular to do this is by using a format-preserving mode of AES, like the FFX mode that NIST is now considering.

But many people who want to use FPE to encrypt sensitive data also want a version that makes sure that patterns never get encrypted to themselves. So if they're encrypting the last four digits of a credit card number, they want to make sure that the plaintext four digits never get encrypted to the same four ciphertext digits.

From the more theoretical point of view, this seems to make such a format preserving approach non-secure. One definition for the security of a deterministic block cipher is that it's indistinguishable from a random permutation, and ensuring that certain patterns never get mapped to themselves seems to violate this.

On a more practical level, this seems to introduce the same flaw that let the Allies break the ENIGMA back in World War II, so it's probably not a good idea.

A better approach is just to accept the fact that the plaintext and the ciphertext are going to agree by chance a certain fraction of the time. Doing that doesn't intentionally introduce a weakness like forcing the plaintext and ciphertext to never agree does.

Comments on NIST's proposal to approve FFX

What's on the NIST web site seems to say everything that needs to be said:

On June 9, 2011, NIST announced a period of public comment on a proposal to approve two schemes of the FFX framework for format preserving encryption: FFX[radix] and VAES3. The public comments that NIST received in response to this request are collected here.

Oddly enough, the comments are all very positive. In situations like these you usually get negative comments by vendors who don't have an interest in the technology which give either weak or obscure technical reasons why a particular proposal is bad.

A dubious best practice for encryption

I was just reading a report from another security vendor when I came across this as a recommended best practice:

Use 2048 bit encryption for symmetric keys and at least 256 bit encryption for asymmetric keys

This is probably a good example of why the Oxford English Dictionary now includes the word "d'oh!"

It's also probably worth noting that even if you correct the confusion between symmetric and asymmetric algorithms, that using 256-bit symmetric keys is definitely NOT an industry best practice. Even the conservative people at NIST expect 128-bit keys to be good essentially forever - there's no date by which they'll ever become obsolete. And current best practices actually only call for keys that provide at least 112 bits of cryptographic strength, which is the level of security that you get from three-key Triple-DES, an elliptic curve key of 224 bits, or a key of 2,048 bits from most other public-key algorithms.

Another good source of random bits

In a recent post, Steve Burnett talked a bit about NIST's DRBG and using it to generate random numbers. Here's an alternate approach to generating random bits. It has the advantage that its security is based on understanding how large organizations operate. Even fewer people understand that than understand the math behind pairing-based cryptography, so the number of people who could potentially attack a system that implements this approach is fairly small. Even better, absolutely none of these people are hackers.

In any event, here's how the sytem works.

Pick a suitably-big organization. The US government is a good example of this, and if this approach ever becomes approved for government use, the standard that defines its use will probably specify that the US government MUST be used for this.

To generate a random bit at a particular time, look at the parity of the number of divisions in the large organization at that instant in time. To make this more precise, to generate a random bit b(t) at a particular time t, find the number of divisions d(t) in the organization at that the time t and reduce it modulo 2:

b(t) = d(t) (mod 2)

The beauty of this PRNG is that, as anyone who has worked for one can tell you, the structure of large organizations is very random. Or if it's not truly random, it's indistinguishable from random. In any case, it's definitely a good source of random numbers, and this approach is probably just one the many ways that we can take advantage of this property.

Are side-channel attacks no longer interesting?

 

I don't know how current this information it, but the database of side-channel attacks that's available at sidechannelattacks.com seems to show that there's not much work being done in this area now. It looks like research into side-channel attacks peaked back in 2006 and has steadily declined ever since.

Why are side-channel attacks no longer interesting to researchers?

FIPS-Certified PRNGs, Part 2

In a previous post, I introduced FIPS certification and PRNGs. I pointed out that there's a new algorithm (800-90, now called DRBG for Deterministic Random Bit Generator) to be certified. In this post I'm going to talk about that algorithm and how to get it FIPS certified.

One of the twists in the 800-90 standard, is that it requires the implementation to come up with seed material. That is, most old PRNGs worked the same way:

1. instantiate
2. return to the user
   1. the user enters seed
   2. the PRNG can now generate random numbers based on the seed

 800-90 works this way:

1. instantiate
2. collect seed material
3. return to the user.
   1. the user can now enter more seed material or
   2. just call on the DRBG to generate random bytes.

Here at Voltage, we use the term autoseed. That means the PRNG/DRBG seeds itself.

So NIST is requiring that products up for FIPS certification must supply a DRBG that autoseeds. But that brings up the question, how can one test an implementation? With 186-2, it was possible to come up with seed/expected output pairs. But with 800-90, there's autoseeding. We can't guarantee what any seed will be in advance. Furthermore, if we enter a seed, we won't get the expected output because the autoseed will be different every time we run the test.

The answer is to require the implementation to turn off autoseeding in order to run the test. Then, the test supplies some data that is a substitute for the autoseed material, and possibly some more material that is a aubstitute for user-supplied seed. The implementation then generates random bytes and it is compared to an expected value.

This makes sense on one level. In order to test an implementation (make sure they follow the standard), make sure it produces expected output from a specific seed.

However, this also means introduing a security hole.

In order to get FIPS certification, an implementation must turn off autoseeding. But if a user somehow accidentally uses the PRNG/DRBG in FIPS testing mode, and they don't add their own seed, they'll get bad random output. After all, they're using a PRNG/DRBG that seeds itself, so why enter any new seed?

You might declare, "Then don't release the FIPS testing mode version of the PRNG/DRBG." However, one FIPS requirement is that the code tested is the code released. Furthermore, in order to get FIPS certification, it is necessary to perform these "Known Answer Tests" (KATs) at startup. When the user first launches the product, it must run some KATs to show that it is running properly.

It all means that in order to get FIPS certification, we must release the product with FIPS testing mode in there.

We've written our code in such a way that the FIPS testing mode is not publicly available. There are also some hoops to go through to get to that code. So the probability is extremely low -- virtually zero -- that a user will accidentally instantiate in FIPS testing mode. With some research, a user could figure out how to explicitly (as opposed to accidentally) instantiate in that mode, but why would they? So I'm not too worried.

Nonetheless, I don't like this requirement from NIST. I think that NIST should either not require the KAT, or allow an implementation to take out the FIPS testing mode before releasing.

By the way, I can think of one reason someone might make the effor to instantiate in FIPS testing mode, and that is to intentially create a security hole. Someone writing an app that they want to break themselves would appreciate this implementation. Of course, someone wanting to do this would have many, many more ways of inserting back doors. So taking away this code would not thwart them. But no one wants to add anything to help the attackers.

FIPS-Certified PRNGs, Part 1

What I really want to talk about is an issue with getting FIPS certification with the new NIST 800-90 DRBG. However, before I get to that, I want to make sure anyone reading these posts know some background.

• What is FIPS certification? If you don't know, it's simply a US Federal government program run by NIST (National Institute of Standards and Technology) that checks to make sure crypto products meet a minimum standard of quality. Any US government agency that wants to purchase a crypto product must purchase a FIPS-certified one, or else prove to some authorizing agency why they the uncertified product they want to buy is necessary. (FIPS = Federal Information Processing Standards.)
  
  The original FIPS certification was all about hardware security modules. Later on, it was expanded to software. There are a number of tests a vendor has to pass in order to get certification. For example, a product has to get the correct answer when performing AES or DSA or SHA-256 or whatever algorithms are offered. However, not all crypto algorithms are FIPS-certifiable. That is, you might have an implementation of RC2 in your product, but you can't get that FIPS certified.
    
• What is a PRNG? The letters stand for Pseudo-Random Number Generator. Over the years, this has become a very common term and abbreviation. A PRNG is an algorithm that produces random bytes. Except the bytes are not truly random because it is possible to reproduce the output. The algorithm works by converting input "seed" material into output bytes that pass statistical tests of randomness. A PRNG will always produce the same output for a given seed. Change the seed and you get different output.
  
  In order to get FIPS certification, a product has to use an approved PRNG algorithm. There was an algorithm described in the FIPS PUB 186-2 that was certifiable. As part of FIPS certification for this algorithm, the testers would verify that the implementation produced the right answers, just as with an encryption algorithm. The testers would supply a seed, the implementation would generate random bytes. The tester would compare the bytes generated with the expected output. If it matched, the product passed.

The internals of a PRNG have two main components: what it does with seed material and how it produces the actual random bytes. If someone invents a PRNG, they specify the operations on the seed material and the operations to perform when actual random bytes are requested.

Most PRNGs use a message digest (cryptographic hash) or block cipher algorithm to convert seed into random bytes. Furthermore, there are specific steps in a specific order to take when performing the operations. You might think, "What's the big deal? Just digest the seed and there's your output." Except a PRNG might need to generate more than one block of data. That is, suppose you use SHA-512 to digest the seed, you get 64 bytes of output. But suppose you need 256 bytes or more? What then? "Just digest the previous output to get the next output?" No, because then anyone looking at some output will know what the next output will be ("I see that with me, the SSL server used an RC4 key of 0x38 C2..., so I know with the next connection, they will use 0x7A 05...").

For that reason, and many more, building a PRNG is not trivial. And once a PRNG exists, and the crypto community studies it and finds it to be good, anyone implementing it should make sure they've implemented it correctly. "Yeah, I've implemented a PRNG algorithm pretty much as defined, but if it's not exact, so what?" Did you introduce a security flaw? Maybe not, but without study, how do you know for sure? The best thing to do is to implement an algorithm exactly as specified so you know you have not introduced flaws. And how do you know you've implemented it correctly? The best test is to make sure you produce expected output given a particular seed.

Back to the 186-2 algorithm. Over the years, several people found some issues with the this PRNG (I'm proud to say I was one of those people: I showed an example of two seeds producing the same output, and that to solve that problem an app should digest all seed material). Hence, NIST decided to develop a new algorithm

NIST recenly came out with that new algorithm and published it in NIST Special Publication 800-90. In that doc, they call the algorithm a "Deterministic Random Bit Generator" or DRBG. In fact, NIST now uses that term for the entire class of algorithms that produce random bytes from a seed.

I'd just like to say that I don't like this new term DRBG. The industry has been using the term PRNG for many years, why come up with a new one? And besides, isn't "Deterministic Random" an oxymoron?

Nonetheless, there's a new algorithm to get FIPS certified. In fact, NIST has said that in the future, the old 186-2 algorithm will no longer be certifiable. In the future, a product up for certification will have to implement 800-90.

Part 2 will talk about this new algorithm and FIPS certification.

A song for Friday

It's the Friday before a holiday weekend, so it must be time to listen to the song "Crypto" by Bob Rivers again.

FIPS that!

After my comment on the inappropriate language in a recent paper by Koblitz and Menezes, an alert reader pointed out yet another reason why their use of the f-word was inappropriate in this context: if you really want a four-letter word that begins with the letter "f" that will provoke a strong reaction from people who work in the field of cryptography, "FIPS" is a much better choice.

Security theater for DNSSEC

The recent DNSSEC workshop in Singapore got some interesting coverage in the San Jose Mercury News:

The Singapore event included an elaborate technical ceremony to create and then securely store numerical keys that will be kept in three hardened data centers there, in San Jose, Zurich and Singapore. The keys and data centers are working parts of a technology known as Secure DNS, or DNSSEC. DNS refers to the Domain Name System, which is a directory that connects names to numerical Internet addresses. Preliminary work on the security system had been going on for more than a year, but this was the first time the system went into operation, even though it is not quite complete.

The three centers are fortresses made up of five layers of physical, electronic and cryptographic security, making it virtually impossible to tamper with the system. Four layers are active now. The fifth, a physical barrier, is being built inside the data center.

As the recent compromises of RAs at Comodo showed us, the weak link in PKI is almost never the CA itself, and a clever hacker will always go after one of the weaker links instead of trying to get the CA's private keys. And it certainly looks like the fortresses that are being built in San Jose, Zurich and Singapore are really designed to keep hackers away from those very keys.

So if a hacker wants to compromise DNSSEC, they almost certainly won't try to beat the security of one of the fortresses. They'll do something much easier like compromising an RA. That means that all of the expensive layers of security around the DNSSEC root keys are probably just for show. They may make people feel better about the security of DNSSEC, but they probably don't really add much actual security because they're designed to defeat attacks that never happen. And these attacks still wouldn't happen if the security measures around the keys weren't as tight.

Inappropriate language by Koblitz and Menezes

Neal Koblitz and Alfred Menezes have written yet another paper about the strengths and weaknesses of using proofs of security to establish trust of cryptographic algorithms and protocols. Their first paper on this topic actually had some very valid points. Their latest contribution has elements that definitely don't belong in a serious publication.

Their discussion of non-repudiation is a good example of this. I've blanked out most of the letters in two of the particularly offensive words. Koblitz and Menezes didn't.

In many settings non-repudiation rather than authentication has been the most important need.

For example, in America, where illiterates have traditionally been permitted to sign with an X, such signatures are required to be witnessed. The reason is to prevent Bubba⁴ from later claiming

Ain’t my f***in’ X. Must be somebody else’s f***in’ X.
Roll Tide!
We the people!⁵

The f-word in a paper about cryptography? Why would anyone think that's appropriate?

They then try to explain in the footnotes exactly how they were trying to offend people:

⁴We chose the name Bubba rather than Bob because in all protocol descriptions of which we’re aware Bob is assumed to be literate.

⁵The first slogan refers to the football team of the University of Alabama, which is nicknamed the Crimson Tide. Bubba is a proud alumnus of that institution, and played football for them when he was a "student." The second slogan is the motto of the Tea Party movement, which Bubba strongly supports. He doesn’t believe in evolution or global warming, and is very proud to be an American because only in America do people like Bubba wield great political influence.

It seems to me that comments like these have absolutely no place in a serious discussion of provable security. That's why we have things like blogs, Facebook, reality TV and movies by Quentin Tarantino. But I'm fairly sure that Koblitz and Menezes really knew that, didn't they?

Is Triple-DES not secure enough?

I've had a number of discussions about Triple-DES recently. Some people are saying that it's not secure enough to use to protect sensitive information. When I hear this, I always ask them to explain why they think this is the case, and their thoughts on this always seems to be a misperception or misunderstanding of some sort.

The fact that the DES algorithm was retired (PDF) a few years ago because it was considered too weak to use seems to have tainted the term "DES," and people who don't worry about the arcane details of encryption on a regular basis (and that's almost all of the world) seem to confuse DES being fairly weak with Triple-DES being fairly weak. But it's not. Even the ultra-conservative cryptographers at NIST say that Triple-DES is secure enough to use for almost 30 more years.

Three-key Triple-DES provides 112 bits of cryptographic strength. That's a lot more strength than DES provides. It's actually stronger by a factor of 2⁵⁶.  That's 72,057,594,037,927,936, or over 72 quadrillion.

It's possible to buy a special-purpose machine today that can try all 2⁵⁶ possible DES keys in a few hours. Let's assume that we have a machine that's even more powerful than that. Let's assume that we have one that's so powerful that it can crack DES in a single minute. If we have a machine that can crack keys that quickly, it will still take about 260,658 years to crack a Triple-DES key. That's not as impressive as the billions or trillions of years that it would take to crack an AES key, but it's still good enough to protect your sensitive information.

So don't let people tell you that Triple-DES isn't secure enough. It's definitely strong enough to protect all but the most sensitive information. If you're a national government trying to protect your most sensitive diplomatic and military secrets from other national governments you might worry about Triple-DES being secure enough, but for the rest of us, it's just fine.

A new record for pairing computation at the 256-bit level

Mike Scott, the researcher who's responsible for lots of the optimizations that make it possible to efficiently implement the pairings that pairing-based cryptography uses, has set another record. His new record is for a BB₁ decryption at the 256-bit security level on a 64-bit Intel i5 520M running at 2.4 GHz in about 44 ms. That's very impressive.

When pairing-based cryptography was relatively new, calculating a pairing was fairly expensive, which made PBC unattractive for many applications where the computing power of a desktop PC or server wasn't available. The work of Scott and others has essentially removed that obstacle to the widespread use of pairings, so they may be showing up in lots of other areas soon.

There's also more interesting material in Scott's paper ("On the Efficient Implementation of Pairing-Based Protocols") that describes this record. Here's how he describes what it tells us, just in case you're undecided about whether or not you should read it:

The advent of Pairing-based protocols has had a major impact on the applicability of cryptography to the solution of more complex real-world problems. However there has always been a question mark over the performance of such protocols. In response much work has been done to optimize pairing implementation, and now it is generally accepted that being pairing-based does not preclude a protocol from consideration as a practical proposition. However although a lot of effort has gone into the optimization of the stand-alone pairing, in many protocols the pairing calculation appears in a particular context within which further optimizations may be possible. It is the purpose of this paper to bridge the gap between theory and practise, and to show that even complex protocols may have a surprisingly efficient implementation. We also point out that in some cases the usually recommended pairing friendly curves may not in fact be optimal. We claim a new record with our implementation of a pairing at the AES-256 bit level.

Eavesdropping on quantum cryptography

Researchers in Singapore and Norway have just shown how it's possible to eavesdrop undetected on a communications link that's protected by one particular implementation of quantum cryptography. This isn't an attack on quantum cryptography in general. Instead, it's an attack on a particular implementation of a particular type of quantum cryptography.

This ought to be sounding very familiar to anyone with more than a casual interest in cryptography. Without the word "quantum," this really describes lots of attacks that have made the news in the past few years in which someone finds an attack that doesn't work in general, but works against one particular implementation of one particular type of cryptography.

Here's how the researchers describe their work:

The stated goal of quantum key distribution (QKD) is to grow a secret key securely between two parties with a minimum of additional assumptions. The number of assumptions has been continuously reduced, from requiring the validity of quantum mechanics in early QKD, to more general constraints on the laws of physics in device-independent QKD. Despite steady theoretical progress in dealing with known limitations of current technology, in practice the security of QKD relies not only on the quantum protocol but on the physical implementation. A variety of attacks have been conceived to exploit weaknesses of current systems. Here we demonstrate the first full field implementation of an eavesdropper attacking an established QKD connection. The eavesdropper obtains the complete 'secret' key, while none of the results measured by the legitimate parties indicate a breach in security. This confirms that non-idealities in physical implementations of QKD can be fully exploitable. 

As we often see with quantum cryptography, there's a certain amount of spin involved in how the work is described. Here's what one of the researchers said about the implications of this work:

"Quantum key distribution has matured into a true competitor to classical key distribution. This attack highlights where we need to pay attention to ensure the security of this technology," says Christian Kurtsiefer, a professor at the Centre for Quantum Technologies at the National University of Singapore.

The claim that quantum cryptography has matured into a true competitor to classical key distribution is a good example of this type of spin. That's really just wishful thinking on the part of researchers who want to get funding for their future work. Except for a few proof-of-concept systems, we probably won't be seeing quantum cryptography used much in the near future. It just doesn't solve any problems that people are willing to pay to have solved. At least not yet. 

What was this vendor really talking about?

I just came across an interesting discussion on LinkedIn. Here's what someone from a security vendor said:

While I’m unable to delve into our patented technology without an NDA, needless to say all data to and from our gateway solution uses a proprietary transport encryption solution that secures transactions at an effective security level of 320 bits, which is 200 times more secure than SSL3 using 128-bit encryption.

A proprietary encryption solution that a vendor won't tell you about unless you sign an NDA is almost certainly a sign that something's not right. There are essentially two approaches that are generally accepted for validating encryption technology. In one case you let people try to find problems with it, and if they don't find anything after several years then you have some level of assurance that there aren't any problems with it. Or if you have a peer-reviewed proof of security, that's another option. 

The wait-and-see approach isn't as good as having a proof. It's really a legacy approach that was used before the work of Phil Rogaway and Mihir Bellare on provable security transformed cryptography from an art into a science. But since lots of people don't quite understand the proofs of security for cryptographic schemes and protocols, we're likely to see the wait-and-see approach well into the future.

In any case, neither of these approaches is one that benefits from keeping your cryptography secret, so it's not clear why a serious security vendor would want to keep the details of their encryption protocol secret.

But what struck me as odd about this particular vendor's statement was the fact that 320-bit encryption was claimed to be 200 times more secure that 128-bit encryption.

Is there any way at all to interpret this vendor's statement in a way that makes sense?

If both the 320 bits of security and 128 bits of security are both key lengths of ideal symmetric ciphers, then 320 bits is way stronger that 128 bits. It's stronger by a factor of 2^(320-128) =  2¹⁹² = 6,277,101,735,386,680,763,835,789,423,207,666,416,102,355,444,464,034,512,896. That's so much bigger than 200 that it seems very unlikely that someone would try to approximate it as 200, so this explanation doesn't seem to make sense.

Could the 320 bits be from an elliptic-curve scheme? In that case, 320 bits could give you 160 bits of cryptographic strength. But such a key is stronger than a 128-bit AES key by a factor of roughly  2^(160-128) = 2³² = 4,294,967,296. That's still so much bigger than 200 that almost nobody would approximate it as 200.

Maybe a few politicians would. It's easy to imagine some of them saying things like, "Our projected budget deficit is approximately $200 this year"  when they're really spending billions more than they're getting in revenue. Cryptographers tend to be more precise.

Or those 320 bits could be the size of an RSA modulus or a similar value (DH modulus, etc.). But if the 320 bits comes from something like an RSA modulus, then they'd actually be giving you much less than 128 bits of strength. That means that you'd never actually claim that using the 320-bit key was stronger, so that explanation doesn't seem to make sense either.

A final possibility is that this vendor noticed that 320 - 128 = 192, so they thought that 320 bits of strength is 192 times better than 128 bits of strength. Round the 192 up to 200 and you're done.  That makes absolutely no sense at all, of course, and it's a mistake that nobody who's selling security products should ever make.

So I'm left wondering exactly what's going on with this vendor's cryptography. And why they won't tell you exactly how it works. And exactly how that 320-bit key is used.