Charm Design Principles

It has been over a year since my last post. I blame the academic life! I will try to keep my blog more up-to-date, and perhaps, use it as a way to document how to use Charm and some of the features we are planning for this year and beyond. But first, some background on the purpose of Charm.

Charm is the beginning of what I hope to be a paradigm shift in how the academics and system engineers of the world approach the development of modern cryptography. This is because Charm doesn’t require sophisticated programming skills to realize the implementation of complex yet useful crypto algorithms.  It decouples gory implementation bits from the algorithmic details of crypto. Charm allows experts and non-experts to think about these constructs in terms of how they were written in the research papers. Basically, it represents a one-stop-shop approach to understand a scheme, implement it, and run it without needing to install extra software. 

More importantly, Charm benefits the research and systems community by providing a test bed and rapid prototyping environment for advanced crypto (e.g., more than just integer factoring and number theory). We do the hard work once (or a few times) so others can worry about the idea they want to implement. Moreover, the Charm code literally can run anywhere (and yes, even on Android). The hope is that Charm becomes the MATLAB for today’s cryptography. It enables the evaluation of new crypto in the hopes of facilitating the technology transfer of crypto from research to industry. Realizing this goal is central to being able to utilize the recent advances in theoretical crypto (e.g., computing and searching on encrypted data) in the real world.

One of the salient features of Charm is its ability to provide a developer-friendly environment to implement cryptography at a high-level. In general, when developing a crypto library, there are many issues outside the crypto scheme(s) that one must take into consideration. Which programming language? What kind of API or interface is required by users? What type of data structure for storing public/private keys and ciphertexts? Serialization methodology for transmission of those structures? 

These are the kind of issues that make the engineering time consuming and tedious, not to mention error-prone (e.g., due to poor interface design). In addition, this is separate from the headaches that come with implementing the crypto scheme itself. This is usually a non-trivial exercise that requires understanding of the underlying mathematics and theory involved in implementing it correctly. 

Assuming the proof of security for the scheme is free of errors, mistakes can easily be made as one transitions from the theoretical description to an implementation. But, in the end, these mistakes can turn into devastating flaws that make the resulting library useless. The ultimate goal of Charm is to lower the barriers for developing crypto by providing reusable building blocks and focusing the (time constrained) energies of researchers and developers on the algorithmic details of a scheme in a high-level programming language. Then, the other necessary bits like serialization of keys and ciphertexts are provided without any additional work. 

Implementing a crypto algorithm in Charm only requires three things: 1. a basic understanding of Python which is really easy to learn by the way, 2. the ability to understand the mathematical notation used in the research paper to describe the scheme, and 3. a willingness to try a new approach to develop crypto. Our goal is to make Charm a platform that anyone can use to further their own research agendas -- free of charge.

If you want more details, we have a somewhat dated tech report about the framework available here and a published research paper appeared in the second issue of the Journal of Cryptographic Engineering (DOI: 10.1007/s13389-013-0057-3, Vol: 3, Issue: 2, page 111-128).

IBE and Charm : Part 1

In my last post, I mentioned that Identity-based encryption (IBE) fixed the main drawback with respect to key distribution for public key cryptography (e.g., no need for public keys, just an easy to remember ASCII string). One of the biggest issues with IBE is that there is inherent key escrow. That is, the private key generator (PKG) which generates secret keys for users must be highly trusted because the PKG has the capability to generate any key and can thereby decrypt all messages. For centralized models (e.g., found in organizations), this is not necessarily a big deal in that there is likely a trusted infrastructure the PKG can plug into. Another issue is revocation. If public identities are represented by email addresses, then that poses problems when an individual in an organization is fired and coincidentally another employee is hired and given the same email address. Does the new guy automatically inherit the secret keys of the previous employee and thus access their old emails? To fix this, email addresses might be appended with a unique numbering system for each employee to avoid collisions, but that hardly seems like a novel solution. Although this approach would work, there are various ways of managing identities that do not involve cryptography per se, so it isn’t the focus of this post. If interested, refer to the wikipedia article for more details on IBE.

So, I’d like to discuss my experience implementing an IBE scheme in Charm. Charm is a Python framework for rapid development of advanced and complex cryptographic algorithms. It is a project I have been working on for the last few years and I’ve used it as an opportunity to understand how cryptographic schemes are designed and their proof of security with respect to chosen-plaintext and chosen-ciphertext attacks. If you’re familiar with Python, you will probably agree that it’s an easy to learn language and write readable code. Since it’s an interpreted language, you get the benefit of not having to worry about compilation errors. For developing crypto code, this is a great advantage and one that allows developers (like me) a neat way of learning modern cryptography without being bogged down with implementation details. Charm allows developers to focus on the high-level cryptographic algorithm and provides the necessary infrastructure for developers to implement a variety of cryptographic algorithms and protocols easily.

The IBE scheme I implemented in Charm can be found in “Revocation Systems with Very Small Private Keys” by Lewko et al (ePrint article) on page 8 in section 4 (published in IEEE S&P in 2010) has very useful revocation features. Fortunately, you do not have to understand the details of the scheme to use the implementation. Note that this scheme implementation isn't present in the previous release of Charm, but will be made available in the next release slated for early next month. So, I’m going to focus on the high-level API in this post and how you could easily incorporate the scheme in Python into your application.

As a recap, IBE consists of four algorithms: setup, keygen, encrypt and decrypt. The first step is to declare a group object in which the scheme will be instantiated. Historically, IBE has been implemented in pairing-based settings (subject for another post) due to efficiency reaosns. Non-pairing (or integer) based versions have been known to be quite inefficient for practical applications. Instantiating groups for implementing schemes is easy in Charm, so I'll leave that out of this post. So, once the group has been instantiated, we can create the new IBE instance as follows: 

IBE = IBE_LSW(groupObject)

Next, run the setup algorithm with the number of users in the system.

(mpk, msk) = IBE.setup(n)

mpk and msk represent python dictionaries for the global public and master secret parameters. Now, to generate user keys based on a specified identity, the private key generator executes the following on the user's behalf:

sk = IBE.keygen(mpk, msk, "user2@email.com") 

To encrypt a message with a revocation list of identities and the global public parameters:

ct = IBE.encrypt(mpk, M, ["user1@email.com", "user3@email.com",...])

In this case, the message, M, is a group element which means that this scheme by default cannot encrypt ASCII strings. For other settings such as standard elliptic curve and integers, we have the ability to encode strings as group elements. In practice, either the string is encoded as a group element OR we take the hash of a random group element and use that hash as a symmetric key to protect the actual ASCII message. In Charm, we have not implemented conversion routines for pairing groups given the complexity of the algorithm. 


To decrypt the ciphertext, a user has to specify the revocation list (denoted as S), the ciphertext, ct, and the user's secret key, sk:

m = IBE.decrypt(S, ct, sk)

If the user's identity is in the revocation list, S, then the decrypt routine will fail, otherwise, the user will be able to recover the message. Since the recovered message is a group element, we could either decode back to a string OR take a hash and decrypt the second ciphertext as a result of using symmetric encryption. Fortunately, there are tools in Charm that do this automatically, thus making it very easy to use this scheme in a real application. In the next post, we will look under the hood for a better understanding of how close the implementation is to the original scheme description in the paper. Comments and questions are welcome on any of the above. Thanks for reading.

Advances in Public Key Cryptography

Public key encryption (also known as asymmetric key encryption) has been around for decades (since mid 1970s to be exact) and it has revolutionized secure communication without need for pre-shared keys. Much of the web (if not all) relies on public key encryption. For example, TLS uses public key encryption to establish a session key between a client and a server for securing internet traffic.


Let's take the traditional example of Alice and Bob who want to communicate securely and they haven't spoken to each other before. Alice generates a public and private key pair. She gives Bob the public key (and the world for that matter) and anyone that wants to securely transmit data to her uses the public key to encrypt messages. The encryption is said to be hard to invert (in a reasonable amount of time for modern computers) without the private key, which only Alice possesses. Thus, Bob can reliably send confidential messages by encrypting to Alice using her public key and guarantee that only she can read the message. Note that public key encryption in itself relies on an infrastructure (or PKI) to authenticate public keys so that someone malicious (let's call her Eve :-) cannot impersonate Alice to Bob. The earliest use cases of public key encryption was to securing email communication and the most widely used algorithms even to this day are RSA and El Gamal. For large enough public/private keys (at least 1024 bits), these algorithms have been deemed secure for general use and you can find their implementation in pretty much every cryptographic library.


Now, is there a problem with traditional public key encryption? Yes. There's an easier attack that does not involve guessing keys, but rather of an active adversary that can inject herself between Alice and Bob's conversation. Eve could impersonate Alice to Bob and Bob to Alice such that she establishes secure communication with both parties without them suspecting. Therefore, authentication of the public keys needs to happen in order for Alice and Bob to verify that they are really talking to each other. To rectify this problem, an idea was to try to remove the "public" from public key encryption and reduce managing this key to an easy to remember string for the intended recipient (think email address). It is known an as identity-based encryption or IBE.


In IBE, instead of creating public and private keys, the private key is derived from a string that represents a user's identity. The public key essentially is the string (and also used in conjunction with some other public information to extract the public key). So, Bob's identity is all Alice has to remember in order to encrypt messages to him (e.g., "bob@gmail.com"). There is one caveat. Although there isn't a single public key, there is a set of public parameters that are typically a part of the IBE system. The difference is that everyone has access to this information, even the adversary but they do not have the ability to impersonate a particular individual by forging a public key that belongs to that individual's identity. There is a trusted key authority that is responsible for generating private keys for Alice and Bob. It is responsible for authenticating their true identity which makes this type of encryption work in practice. This is nice and is probably still considered a new encryption technique that is still an active area of research to make efficient enough for everyday use. There are tons of applications for IBE including use with biometrics, secure email and many more.


Next post, on improvements in IBE...

Introduction

Let me tell you a little about myself. I'm currently a graduate student in the CS dept at Johns Hopkins University focusing on information security research. In particular, I've been working with some great professors and students there and have had the opportunity to work on several cool projects. Most of this blog will be about my research exploits and the variety of things I find interesting within security. Things like cryptography and its application to medical security in the cloud and on mobile systems, for example.

I may also focus a bit on my understanding of the current state of virtualization and operating systems concepts.  In addition, focus on mobile OSes such as Android, iPhone and my personal experiences developing on these platforms. I hope you'll come back sometime soon and leave a comment on whatever you see here. Thanks for reading!

Welcome

Hi! Welcome to my blog. More to come in due time.