Identity-Based Encryption - how secure is it?

Question

I was always taught never to invent my own crypto algorithm, and never to trust someone who has a proprietary algorithm.

I'm looking at Voltage SecureMail, which uses IBE (identity-based encryption) and I'm way over my head trying to work out whether this is very clever, or if it's snake oil.

The IBE algorithms it uses are specified in RFCs (RFC 5091 - Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems, RFC 5408 - Identity-Based Encryption Architecture and Supporting Data Structures, RFC5409), but I know I'm not qualified to assess the quality of a cryptosystem.

I'd be interested in a commentary (or, more realistically a link to a commentary) by a cryptologist on IBE, how secure the cryptosystem is, how well designed the Voltage implementation is, how tied I am as a consumer to Voltage as a corporation, or whether I can go to a competitor or to open-source software that implements the same cryptosystem, etc.

Frankly, I'm probably underqualified to read such, but I'm the one with the job, so I get to learn about crypto.

Answer 1

(Warning: mathematics ahead. But there is a summary at the end.)

IBE, as implemented by Voltage, uses a pairing. Known efficient pairings work over specially crafted elliptic curves (the two main pairings are Weil pairing and Tate pairing, and there exist some variants of the latter which offer performance boosts in some situations). These pairings were discovered by mathematicians in the 1950s; application of pairings to cryptography was first hinted at by Miller in the 1980s.

Initially, pairings were thought of ways to attack elliptic curve systems -- by reducing discrete logarithm on elliptic curve to discrete logarithm into a more "easy" field. The critical parameter is the "embedding degree", which I will note k. For a normal n-bit elliptic curve, discrete logarithm is hard up to 2^n/2 operations, hence a 256-bit curve is enough for the standard "128-bit security". For a given curve, a pairing can be defined, which can be used to transform a discrete logarithm problem on the curve into a discrete logarithm problem in a multiplicative subgroup of a field of kn bits. The k parameter depends on the curve which is used. E.g., if you have a 256-bit curve with a very low k=2 embedding degree, then discrete logarithm on that curve is no harder than discrete logarithm in a multiplicative subgroup of a 512-bit field, which is much easier (a 530-bit discrete logarithm was performed in 2007).

Fortunately, a "normal" curve will have a very high embedding degree; a typical 256-bit elliptic curve will sport an embedded degree around 2²⁵⁵, i.e. much greater than 2 or 3. Selection of an elliptic curve according to the relevant standard (ANSI X9.62-2005) involves verifying that k is no lower than 100, which is invariably true with an overwhelming probability for a randomly selected curve anyway. This is called the "MOV condition".

An efficient pairing requires that kn is not too big, because the paring result is a kn-bit value and we want to do some relatively heavy computations with such values (modular exponentiations...). Hence, a pairing for IBE (not for attacks) needs a "weakened" curve with a very low embedding degree. The scheme described in the Boneh-Franklin article (2003) uses a 512-bit elliptic curve with the special property of being "supersingular", which implies (here) an embedding degree k=2 (thus the resulting security is that of discrete logarithm in a 1024-bit field, roughly similar to 1024-bit RSA).

Summary: the mathematical details above are meant to show where IBE stands:

• The first practical implementation is described in an article from 2003.
• That implementation works on elliptic curves with a special structure which was initially thought of as a weakness.
• Use of elliptic curves for cryptography dates from the 1980s. Elliptic curves are deemed secure because nobody could find any internal structure which could be exploited to speed up discrete logarithm on elliptic curve -- except pairings, which are fortunately inapplicable to "normal" curves. But for IBE, we need a "weak" curve.

So IBE security, in practice, stands on a careful dosage of weakness injected in an elliptic curve, and the details were defined less than ten years ago. This is not an awful lot of time. In comparison, research on integer factorization can boast a whooping 2500 years of history (at least) so when we claim that factorization must be a hard problem, we have some facts to back that assertion up. Accumulated research time is the main, and mostly the only, metric by which cryptographic risk can be estimated.

Hence, IBE is a bit young to my taste for unchecked general deployment. Yet, you can do much worse than following Dan Boneh's steps and chances are that if (when) you will get hacked, it will not be due to any mathematical issue in pairings. Also, pairings are fun (for a mathematician, that is).

A good reading on pairings is Ben Lynn's PhD thesis (his advisor was Boneh, by the way).

Answer 2

I've never looked at Voltage SecureMail from a cryptographic point of view (and realistically couldn't comment with any authority if I had), but seeing Voltage SecureMail in action, there are a couple of implementation details that concern me enough to be wary.

Firstly, when a user receives an encrypted message they are asked to enroll if they've never received an encrypted message before, based on that enrollment (an email asking you to click a link to confirm you've received it) gives you access to the message. There is no further identity verification required, so a sender making a typo gives the recipient access to the mail despite them not being the intended recipient (as far as I'm aware there is also no warning if you try to send a mail to a user you've never communicated securely with before).

Secondly, if you're already an enrolled user and forget your password you can reset it by clicking the ubiquitous forgotten password link (if you don't have the Voltage SecureMail client installed, it defaults to using a web based reader), and having a mail sent to you with a link to allow you to reset your password, but as this password reset message is sent via the same channel (email) as the encrypted message, surely there is a very good chance anyone intercepting the original cipher text can intercept the reset message, reset a users password, and then access the plaintext of the original message.

Answer 3

The cryptography underlying ID-based cryptography is as sound as any other major cryptosystem. It is based on a relatively recent breakthrough in the mathematics underlying elliptic curve cryptography, with many of the cornerstone protocols being contributed to by Dan Boneh, who co-founded Voltage. The properties you get from ID-crypto are significantly different enough that it can uniquely offer the ability to do certain tasks (but often requires a different architecture, trust assumptions, etc. -- see pepe's note on key escrow). So it is not snake-oil. Protocols like BF and BB1 were published in the top two crypto conferences.

How well the crypto gets filtered into products (and how secure the implementations are) I do not know. So I can't comment on Voltage APIs, libraries, products, etc. directly.

I doubt there are many competitors -- open source or not. Elliptic curve cryptography itself had a slow adoption rate (considering it was developed in the 80s) outside of Certicom. I expect pairing based cryptography (only developed in the 00s) to face a similar rate outside of Voltage.

Answer 4

I'm not familiar with the product or the specific protocol, but note that many ID-based encryption schemes suffer from "key escrow", meaning the key distribution center knows your secrets. Multiple proposals were made to mitigate or shift this problem, but I am not sure if a universal solution was found. They might very well be based on other assumptions that are only practical in closed environments or special hardware or other obscure things.

In general, IBE is not used a lot. I am surprised to see you citing RFCs. So yes, you definietly have some vendor lock-in there. What is used are well-known systems like S/MIME or PGP/GPG. Unless you are considering very special environments, IBE has no strong advantages over these traditional solutions. For secure email in your company, you can (and should, since many CAs are not exactly trustworthy and distribute certs simply upon email confirmation) setup your own PKI using either method.

You wanted background information about the system: I would recommend to look at the RFC. The underlying crypto system is usually cited there. But as pointed out before, the IBE is not the key here. IBE gives you vendor lock-in and a few mostly irrelevant features that are easily implemented with a trusted party(which you need anyway for IBE..). For an enterprise solution, you should really look at how the software supports your work flows and requirements. You can build the very same thing with PGP/SMIME. But the question is if there is a good product for your company to buy, or if Voltage SecureMail gives you all the features you want.

Answer 5

Voltage Security's algorithms are not snake oil. They have been subject to peer-review in the academic community on cryptography.

However, Voltage Security's approach does have some significant security risks. One risk has to do with trust in the central server. Voltage uses identity-based encryption (IBE), where the central server knows everyone's private keys. Therefore, if the central server is malicious or its security gets compromised, you have a catastrophic breach of security. Given that even Google has suffered from serious security breaches of its internal systems, is it reasonable to assume that Voltage Security's central servers are impenetrable? Probably not.

As others have noted, in general, the way that attackers successfully break these systems is usually not through a clever attack on the crypto-mathematics; instead, successful attacks typically bypass the crypto-math. In practice, usability issues are extremely important. Other email encryption systems (such as PGP) have suffered from poor security usability, which creates major weaknesses: if users don't know how to use the system securely, or if in their ordinary everyday practice users use the system in a way that is insecure, then you're in big trouble. It doesn't matter how secure the mathematics are if the system can't be used securely by users. I have not personally evaluated the usability of Voltage Security's product, but this has been a major pain point for other email encryption systems.

That said, despite the risks, imperfect email encryption is better than none.

Answer 6

Straying slightly from the crypto question as I think it has been well covered above Voltage has been subjected to FIPS140-2 certification which (although not to be trusted blindly) is a good mark for the product.

Reference was made above about sending mail to the wrong person and them still receiving it. Regardless of the mail encryption product (or a complete lack of encryption) the system will not know if the recipient is the right or wrong one - only the human being driving it will know that. The advantage is that if someone tells you they have sent confidential data to the wrong person and Voltage has encrypted it you can block their access to the message content.

IBE products as a whole (Voltage & ProofPoint Encryption) rely on users signing up and as such the process lacks the pre-agreement phase which does make people nervous however it the suitability does depend on your environment. If you have a need to encrypt mail to a large and varied audience mixed between b2b and b2c recipients and want a single solution IBE is a good choice.

I would agree with all above the mathematics is unlikely to be where the breach occurs. Users with weak passwords, users whose personal mail accounts are compromised etc are far more realistic weak points in the process. I would turn your attention to considering the overall IBE usage process for your users and external recipients and the information you need to protect to asses the suitability.