At my previous job my daily commute took me past 611 Folsom Street in San Francisco. This building is infamous for being the home of Room 641A, where a whistleblower, Mark Klein, revealed that the NSA had created a secret room and placed beam splitters on fiber optic cables carrying Internet backbone traffic.
I heard Jacob Appelbaum mention this building’s street addess in his 29c3 keynote, along with the NSA’s Utah Datacenter, where wiretapped traffic from this room was allegedly funneled and stored, a challenge that sounds daunting but according to NSA whistleblower William Binney, the datacenter has a “yottabyte” scale capacity intended to archive all the traffic they can collect for up to 100 years. From then on I got a little bit preoccupied with this building every time I walked past it on my daily commute.
It’s a building I took pictures of and tweeted about:, like this picture from February:
The idea of an adversary eavesdropping your traffic is central to cryptography. Cryptographers generally bestow the name “Eve” on this adversary, although the EFF has recently abandoned this pretense and has started producing diagrams which identify this adversary as the NSA. For the sort of beam-splitter based observe-but-do-not-interfere style traffic snooping the NSA is performing, the NSA is pretty much acting as the textbook example of “Eve”. However, given the vast capacity of the Utah Data Center, the NSA has the ability to be an incredibly patient Eve, and can leverage all sorts of things like future key compromises and even future algorithm compromises (on a 100 year timespan) to break older traffic dumps.
I’m the sort of person who spends far too much of my day aimlessly thinking about cryptography, and walking past 611 Folsom Street every day it couldn’t help but set my thoughts towards how to defeat the NSA with better cryptography.
The idea of trying to out-crypto a state level adversary with seemingly boundless funding, resources, and expert personnel on their hands might seem a little absurd, and it should be. For an expert look at the problem of whether we can defeat a state-level adversary with cryptographic applications, we can look to Matt Green’s blog post Here come the encryption apps!. Matt does a “Should I use this to fight my oppressive regime?” evaluation of several cryptographic applications and determines that only one of them, RedPhone by Moxie Marlinspike’s Whisper Systems, fits the bill.
Securing our Internet traffic from an “Eve” like the NSA is a daunting challenge. But it’s one I feel it’s worth working on…
Trust No One
“The Cloud” as a concept has somewhat… fluffy security properties (please pardon the pun). We can encrypt data in the cloud, but encryption in and of itself isn’t particularly helpful. It’s particularly problematic if we trust the same people to store our personal data encrypted and also trust them to hold the encryption keys to that data. If they’re doing both, they can decrypt our personal ciphertexts on a whim.
Matt Green defines a “mud puddle test” for cloud services: let’s say you slip in a mud puddle, which destroys both the brain cells which store a password to your data, and a backup of your password you kept on your phone when the water seeps in and fries its circuit board. Can you still access your data somehow? If so, congratulations, you have failed the mud puddle test.
What’s the problem? In order to get access to your data again, someone else must’ve held onto your key, and you are therefore trusting that someone with the security of your data. Many services today might encrypt your data server-side using a key they know (and perhaps only they know!). Your data may reach their service encrypted over SSL, but they’re terminating the SSL on their end and are able to see all of your plaintext as it passes through their servers. If a state level adversary like the NSA has wormed their way in and requested a backdoor, then your cloud provider is able to tell the NSA anything they want.
The solution to this problem is to encrypt everything client side using a key which is only known to the owner of the data. Before the data ever leaves a single computer, it needs to be encrypted with a key known only by the data’s owner. None of this “decrypt it server-side then re-encrypt it” business will do, nor will storing unencrypted keys with a third party. If you want to ensure your data remains confidential, it must be encrypted with a key known only to you.
Without the guarantee that you are the one and only one holder of the encryption key to a particular piece of data, you have absolutely no assurances that your data is being kept confidential, and that it is not being observed by the NSA, or for that matter… the entire rest of the world.
Secure Cloud Storage
What does “the Cloud” really mean? Who knows. But as far as I can tell, one of the things it does is store data: your personal data, others' personal data, businesses' data. Sensitive data of all sorts. How much of this is stored in plaintext, or with keys held directly by the cloud provider?
We are at the whims of whatever cloud services we use when it comes to how our data is stored, but when you understand the “mud puddle test”, it becomes quite clear that where your data is stored is irrelevant, because if you encrypt data before putting it in the cloud you hold all the keys and your data is protected by cryptography. Any country-specific government snooping should be irrelevant if you can trust cryptography to keep your data secure. There shouldn’t be any worries in trusting nodes in Geneva, San Francisco, Moscow, Beijing, or Tehran. We should be able to rely on cryptography to keep our data secure.
You’d think by now distributed secret storage and sharing would be a solved problem. Unfortunately no one system for generally solving this problem has ever gained traction. This is something I have personally been longing for since I was a high school student playing around with MojoNation, and I would later discover the concept existed much earlier in Project Xanadu, which dates back to the 1960s. Some of the 17 rules of Project Xanadu seem relevant to me today:
Every Xanadu server is uniquely and securely identified.
Every Xanadu server can be operated independently or in a network.
Every user is uniquely and securely identified.
Every user can search, retrieve, create and store documents.
Every document can consist of any number of parts each of which may be of any data type.
Every document can contain links of any type including virtual copies (“transclusions”) to any other document in the system accessible to its owner.
Links are visible and can be followed from all endpoints.
Permission to link to a document is explicitly granted by the act of publication.
Every document can contain a royalty mechanism at any desired degree of granularity to ensure payment on any portion accessed, including virtual copies (“transclusions”) of all or part of the document.
Every document is uniquely and securely identified.
Every document can have secure access controls.
Every document can be rapidly searched, stored and retrieved without user knowledge of where it is physically stored.
Every document is automatically moved to physical storage appropriate to its frequency of access from any given location.
Every document is automatically stored redundantly to maintain availability even in case of a disaster.
Every Xanadu service provider can charge their users at any rate they choose for the storage, retrieval and publishing of documents.
Every transaction is secure and auditable only by the parties to that transaction.
The Xanadu client-server communication protocol is an openly published standard. Third-party software development and integration is encouraged.
These are some rather lofty goals, hardly any of which are met by the hypertext system we now use today instead of Xanadu: the web. I believe Xanadu’s original goals are worth revisiting, and that creating a world-scale content addressable storage system which is secure, encrypted, and robust is worth pursuing.
Who is working on this problem?
Perhaps Xanadu’s scope was too vast, and while it’s goals were admirable, its complexity doomed it to vaporware. Indeed, Xanadu may be the biggest vaporware project in history. There are, however, many people working on limited subsets of the Xanadu problem, attempting to build secure distributed document storage systems. Here are some of the ones I find interesting:
Tahoe-LAFS: my favorite on the list, Tahoe applies a capability-based security model to the problem of cloud storage, permitting the ability to provide extremely granular access on a read-write, read, or verify level to individual files, directories, and subtrees in a distributed filesystem. I recently contributed some UI improvements to Tahoe and would strongly suggest you check it out. Unfortunately, Tahoe has failed to garner any sort of mainstream traction.
Freenet: a perpetual contender in this space, FreeNet has somewhat similar goals to Tahoe, but on a global scale. Unfortunately, FreeNet has failed to solve problems around accounting, and generally has problems around performance and reliability.
Perfect Dark: a closed-source Japanese system, Perfect Dark is attempting a “defense in depth” (otherwise known as “security by obscurity”) approach towards frustrating those who would try to undermine its crypto. It boasts a number of impressive features such as mixnets for improving anonymity, but without the ability to audit its source code it’s questionable as to how cryptographically secure it actually is.
The Cryptosphere: my own personal vaporware solution to this problem. It’s received a little bit of coverage on TechCrunch despite being largely vaporware, but in the wake of the recent NSA scandals finally dragging their activities into the spotlight of the public consciousness, I have newfound motivation to continue working on it.
Why create something new?
I’ll admit that, to a certain degree, the Cryptosphere feels like reinventing the wheel. There are several projects out there that more or less do most of the things I’d like for the Cryptosphere to do. So why bother?
I’d like to take a different approach with the Cryptosphere, one which to my knowledge hasn’t been tried yet, in hopes that I can perhaps produce something meaningful to your average person. I feel like the problem with existing P2P systems like I mentioned above is that their value proposition is difficult for your average person to understand. That was certainly the case for the last P2P system I tried to write.
I’d like to try to build the secure web from the top down. If you look at the existing codebase (which is, admittedly, rather small at this point) this isn’t really what I’ve been doing, as I’ve been spiking out the primitives for encrypted storage. Once these are in place though, I’d like to build a system whose frontend is a web browser, but whose backend runs locally on the same machine, performing encryption and P2P activities.
The end result, in my mind, is a system that allows people to write secure HTML/JS applications able to tap into a rich cryptographic backend running locally on the same machine, a backend which could hopefully provide many of the things people presently run their own servers for today. This is an idea born out of Strobe, a startup I used to work for: with the right set of canned backend services and a way to securely deploy and manage HTML/JS applications, you can author an application which lives entirely in the browser.
Digital signatures are a passion of mine (as is infosec in general). Signatures are an integral part of my cryptosystem Keyspace for which I wrote the red25519 gem. The red25519 gem’s sole purpose was to expose the state-of-the-art Ed25519 digital signature algorithm in Ruby. I have since moved on to implementing Ed25519 in the much more comprehensive RbNaCl gem. Point being, I have longed for a modern, secure digital signature system in Ruby and have been working hard to make that a reality.
Digital signatures are something I think about almost every single day, and that’s probably fairly unusual for a Rubyist. That said, if you do work with Ruby, you have hopefully been informed that RubyGems.org was compromised and that the integrity of all gems it hosted is now in question. Because of this, RubyGems.org is down. As someone who thinks about digital signatures every day, I have certainly thought quite a bit about how digital signatures could’ve helped this situation.
And then I talk to people… not just one person, but several people, who make statements like “signing gems wouldn’t have helped here”.
These people are wrong. They are so wrong. They are so so very wrong. They are so so very very wrong I can’t put it in words, so have a double facepalm:
These people are so wrong I’m not even going to bother talking about how wrong they are. Suffice it to say that I think about digital signatures every day, and people making this claim probably don’t (if you do, I’d love to hear from you), but I can also provide an analogy about what they’re saying:
The lock which secures the door of your home can be picked. It doesn’t matter how expensive a lock you buy, someone can pick it. You can buy a top-of-the-line Medeco lock. It doesn’t matter. Just go to Defcon, and watch some of the top lockpickers in the world open 10 Medeco locks in a row. Because locks are pickable, they are pointless, therefore we shouldn’t put any locks on our doors at all.
Does that sound insane to you? I accept the truth that locks are easily pickable, but I certainly want locks on anything and everything I own. Putting locks on things you want to secure is common sense, and part of a strategy known as defense in depth. If someone tells you not to put a lock on your door just because locks are pickable, they’re not really a trustworthy source of security advice. We should start signing gems with the hope that signing gems gains enough traction for the process to be useful to everyone, not give up in despair that signing gems is a fruitless endeavor. If you disagree, I wonder how willingly you’d part with the easily pickable deadbolt on your front door.
I can’t offer a perfect system with unpickable locks, but I think we can practically deploy a system which requires few if any changes to RubyGems, and I also have suggestions about things we can do to advance the state-of-the-art in RubyGems security. So rather than trying to micro-analyze the arguments of people who say digital signatures don’t work (which, IMO, are flimsy at best), let’s just jump into my plan and let me tell you how they could work.
Understanding the Problems
I became passionate about signing RubyGems about a year ago. I even had a plan. It was a plan I wasn’t sure was entirely a good idea at the time, but now I certainly think it’s a good idea. I talked with several people, including RubyGems maintainers like Eric Hodel about it, and I can’t say he was thrilled about my idea but he thought it was at least good enough not to tell me no. Now that the RubyGems.org hack has happened, I think it’s time to revisit the idea.
First, let’s talk about what we’d like to accomplish by signing gems. Let’s start with a hypothetical (but not really!) scenario: let’s say you want to add some gems to a Ruby app, and RubyGems.org has been compromised (you know, like what just happened). Let’s say RubyGems.org has been compromised, and someone has uploaded a malicious version of some obscure Rails dependency like “hike”. You probably aren’t thinking to look at the source code of the “hike” gem, are you? In fact you probably have no idea what the hike gem is (that’s okay, before today neither did I).
Let’s say someone has done all this, and RubyGems.org doesn’t even know this has happened yet. Yet you’re doing “bundle update rails”, possibly in response to the very security vulnerabilities which lead RubyGems.org to be hacked in the first place. After doing this, bundler has just downloaded the compromised version of the “hike” gem, and you are completely unaware.
You now deploy your app with the compromised “hike” gem (along with anyone else who has upgraded Rails during the window in which RubyGems.org has been compromised) and now your app contains a malicious payload.
Does a malicious payload scare you? It should. Do you even know what power gems have over your system? Even gem installation gives a malicious gem maker wide-ranging control over your system, because gemspecs take either the form of arbitrary Ruby code or YAML files which are known to have a code execution vulnerability.
Whose fault is it your app is now running a malicious payload? Is it RubyGems fault for getting hacked in the first place? Or is it your fault for putting code into production without auditing it first?
Here’s my conjecture: RubyGems is going to get hacked. I mean, it already did. We should just anticipate that’s going to happen and design the actual RubyGems software in such a way that it doesn’t matter if RubyGems gets hacked, we can detect modified code and prevent it from ever being loaded within our applications. This isn’t quite what RubyGems provides today with its signature system (I sure wish RubyGems would verify gems very, very first thing before it does anything else!) but it’s close, and it’s a goal we should work towards.
There’s a more general concept around the idea that a site like RubyGems, which stores a valuable resource like Ruby libraries, can get hacked but an attacker cannot confuse you into loading malicious code, because we have cryptosystems in place to detect and reject forgeries. That idea is the Principle of Least Authority. Simply speaking the principle of least authority says that to build secure systems, we must give each part as little power as possible. I think it is unwise to rely on RubyGems to deliver us untainted gems. That’s not to say those guys aren’t doing a great job, it’s just that it’s inevitable that they will get hacked (as has been demonstrated empirically).
A dream system, built around digital signatures, should ensure that there’s no way someone could forge gems (obligatory RubyForge joke here) for any particular project without compromising that project’s private key. Unfortunately RubyGems does not presently support project-level signatures. That’s something I’ll talk about later. But first, let’s talk about what RubyGems already has, and how that is already useful to the immediate situation.
RubyGems supports a signature system which relies on RSA encryption of a SHA1 hash, which is more or less RSAENC(privkey, SHA1(gem)). This isn’t a “proper” digital signature algorithm but is fairly similar to systems seen in Tahoe: The Least Authority Filesystem and SSH. RubyGems can maintain a certificate registry and check if all gems are signed, and prevent the system from starting in the event there are unsigned gems.
It’s close to what’s needed, and would provide quite a bit even in its current state. For example, let’s say RubyGems had digital signature support and also has trusted offsite backups of their database that they know aren’t compromised. They’re able to restore a backup of their database, and from that restore their own trust model of who owns what gems. Just in case they could ask everyone to reset their password and upload their public keys. Perhaps we could keep track of people whose public keys changed during the reset process and flag them for further scrutiny, just in case an attacker was trying to compromise the system via this whole system-reset process.
Once this has happened, RubyGems could then verify gems against the public keys of their owners. This would allow RubyGems to automatically verify many gems, and quarantine those which can’t be checked against the owners' certificates. This is relatively easy-to-automate and could’ve gotten RubyGems back online with a limited set of cryptographically verifiable gems in much less time than it’s taken to date.
This is all well and good, but what happens if an attacker manages to forge a certificate which RubyGems accepts as legitimate? RubyGems needs some kind of trust root to authenticate certificates against. If it had such a trust root, it could compare things like email address on RubyGems.org accounts (which it could double check via an email confirmation) against the one listed in the certificate to at least ensure a given certificate was valid for a given email address. It could also look at a timestamp and ensure that timestamp was significantly prior to a given attack. But to do any of that it would need a trust root which isn’t RubyGems itself.
The Identity Problem: Solving Zooko’s Triangle
Who can RubyGems trust if not RubyGems? Is there a way to build a distributed trust system where there is no central authority? Can we rely on a web-of-trust model instead?
The answer is: kind of in theory, probably not in practice. We could allow everyone who wants to publish a gem to sign it with their private key. Their private key could include their name and cryptographic proof that they at least claim that’s their name. Let’s call this person Alice.
Is it a name we know? Perhaps it is! Perhaps we met Alice at a conference. Perhaps we thought she was really cool and trustworthy. Awesome! A name we know. But is Alice really Alice? Or is “Alice” actually a malicious Sybil (false identity, a.k.a. sock puppet) pretending to be the real Alice?
We don’t know, but perhaps we can Google around for Alice and attempt to find her information on the intarwebs. Hey, here’s her blog, her Twitter, etc. all with her name and recent activity that seems plausible.
If we really want to be certain Alice’s public key is authentic, now we need to contact her. You’ve found her Twitter, so perhaps you can tweet at her “Hey Alice, is this your key fingerprint?” Alice may respond yes, but perhaps the attacker has stolen her phone and thus compromised Alice’s Twitter account. (Silly Alice, should’ve used full disk encryption on your phone ;)
To really do our due diligence, perhaps we can try to authenticate Alice through multiple channels. Her Twitter, her email, her Github, etc. But it sure would be annoying to Alice if everyone who ever wanted to use Alice’s gems had to pester Alice across so many channels just to make sure Alice’s signature belongs to the real Alice.
It sure would be nice if we could centralize this identity verification process, and have a cryptographically verifiable certificate which states (until revoked, see below) that Alice really is Alice and this really is her private key, and this really is her email address, and this really is her Github, and so on.
Is there any option but centralization in this case? Not really… we’ve run afoul of Zooko’s triangle:
Modeling identity is a hard problem. We can attempt to tie identities to easily memorable, low-entropy things like names or email addresses, but doing that securely is rather difficult as I hope I’ve just illustrated. We could also attempt to tie identities to hard-to-remember things like large numbers resulting from irreversible transformations of other large random numbers, such that computing their inverse mathematically is an intractable problem such as computing a discrete logarithm (or at least it’s a hard problem until quantum cryptography happens).
If we choose to identify people by random-looking numbers, we don’t need to have any type of trust root. Per the diagram of Zooko’s triangle above, random-looking numbers can be used as the basis of a “global” system where we have no central trust authority.
But there’s a problem: random-looking numbers give us no information about whether or not we trust a particular person who holds a particular public key. We know absolutely nothing from random-looking numbers. So we’re back to chasing down the person whose name appears in a certificate and asking them if we really have the right number.
To really have a practical system where we can centralize and automate the process of tying people’s random-looking numbers to the memorable parts of their identity like names and email addresses, we can’t have a global system. We need a centralized one. We need someone whom we can trust to delegate this authority to, who can be diligent about at least attempting to verify people’s identities and issue signed certificates which are not easily obtainable and cannot be actively attacked due to manual portions of a process and also human-level scrutiny of the inputs.
I propose someone steps up and runs some kind of certificate authority/trust authority for RubyGems. You may be thinking that RubyGems itself is best equipped to do this sort of thing, but I think there would be value in having some 3rd party specifically interested in security responsible for this endeavor. At the very least, as a different organization running what is hopefully a different codebase on a different infrastructure, there’s some defense in depth as far as not having all your eggs in one basket. Separating the trust authority from the gem monger makes for two targets instead of one.
I’m not saying this CA should be run like practically any other CA in existence. It should be run by volunteers and provided free-of-charge. It should be unobtrusive, relying on fragments of people’s online identities to piece together their personhood and gauge whether or not they should be issued a certificate. It should be noob-friendly, and not require that people are particularly well-known or have a large body of published software, but should still perform due diligence in ascertaining someone’s identity.
I don’t think any system which relies on unauthenticated third party certificates can provide any reasonable kind of security. I think, at the very least, a CA is needed to impede the progress of the malicious.
PKI sucks! Ruby security is unfixable!
Yes, PKI sucks. There’s all sorts of things that can go wrong with a CA. People can hack the CA and steal their private key! If this happens, you probably shouldn’t be running a CA. If a CA relies on a manual review process, people can also social engineer the CA to obtain certificates to be used maliciously.
This is particularly easy if the CA doesn’t require much in the way of identity verification (which is required if you’re trying to be noob-friendly). Perhaps they’ve already compromised the trust vectors a CA like this would use to review certificates.
These are smaller issues compared to the elephant in the room: If I were to run a CA, you’d have to trust me. Do you trust me? I talk a lot of shit on Twitter. If you judge me solely by that, you probably don’t trust me. But would you trust me to run a CA?
All that said, I’m trying to write security software in Ruby, and I feel like thanks to all the recent security turmoil, Ruby has probably gained a pretty bad reputation security-wise. Worse, it’s not just Ruby’s reputation that’s at stake, these are real problems and they need to be fixed before Ruby can provide a secure platform for trusted software.
I want to write security software in Ruby. I do not feel doing this is a good idea if Ruby’s security story is a joke. So I want to help fix the problem. I feel some type of reasonable trust root is needed to make this system work, and I can vouch for my own paranoia when it comes to detecting malicious behavior. I’d be happy to attempt to run a CA on behalf of the Ruby community, and potentially others, or I’d be happy to help design open source software that can be used for this purpose but administered by an independent body like RubyCentral.
In a Dream World: The Real Fix
I spend way too much time thinking about cryptographic security models. In doing so, I always want to use the latest, greatest tools for the job. In that regard, RubyGems' homebrew signature algorithm falls down. So do DSA and ECDSA, as they’re both vulnerable to entropy failure as was illustrated a few days ago when reused nonces were discovered signing BitCoin transactions. The real fix would involve a modern signature algorithm like Ed25519, which would necessitate a tool beyond RubyGems itself (which, by design, relies only on the Ruby standard library).
As I mentioned earlier: I think project-specific certificates are the way to go. I don’t think it would be particularly hard to create a CA-like system that issues certificates to individual projects or people who maintain gems, but a certificate that signs the name of the gem, and is in turn signed by a trusted root.
If I were really to try to run a CA for RubyGems, I would probably try to run it at the project level, and try to have a nontrivial burden of proof that you are the actual owner of a project, including things like OAuth to your Github account and confirming your identity over multiple channels as I described earlier. I’d probably not rely on the existing RubyGems infrastructure at all but ship something separate that could ensure gems are loaded securely, using state-of-the-art cryptographic tools like RbNaCl, libsodium, and Ed25519.
I feel like the gems themselves should be the focus of authority, and the current RubyGems certificate system places way too much trust in individual users and does not provide a gem-centric authority system.
The whole goal of this is what I described earlier: a least authority system where the entire RubyGems ecosystem could be contaminated and RubyGems.org could be serving nothing but malware and the client-side tool could detect the tampering and prevent the gems from even being loaded.
If you’re interested in this sort of system, hit me up on Twitter (I’m @bascule).
The Challenges Moving Forward
So I’m probably not going to make the dream RubyGems CA system described above. What can we do in the meantime? I think someone needs to step up and create some kind of a CA system for gems, even if that someone is RubyGems.org themselves.
You can bypass the entire identity verification process and automatically issue signed certificates upon request. Doing so is ripe for abuse by active attackers, and brings up another important aspect of designing a certificate system like this: revocation.
Let’s say the CA has issued someone a certificate, and later discovered they were duped and they have just issued a certificate to Satan instead of Alice. Oops! The CA now needs to communicate the fact that what they said about Alice before, yeah whoops, that’s totally wrong, turns out Alice is Satan. My bad!
Whatever model is applied to secure gems must support certificate revocation. If whatever modicum of a trust model a certificate authority that auto-issues certificates to logged in users (or at best, an un unobtrusive volunteer-run CA) can provide is violated, which it surely will be, there should be some way to inform people authenticating certificates that there’s malicious certs out there that shouldn’t be trusted.
Whatever CA we were to trust needs to maintain a blacklist of revoked certificates, preferably one which can be authenticated with the CA’s public key. This is an essential component of any trust model with a central authority, and one, as far as I can tell, has not exactly been codified into the existing RubyGems software and its signature system.
Now What?
This is a problem I’d love to help solve. I don’t know the best solution. Perhaps we place all our trust in RubyGems, or perhaps we set up some other trust authority that maintains certificates. I think we can all agree whatever solution comes about should be fully open source and easily audited by anyone. Kerckhoffs wouldn’t have it any other way.
As the post title implies, I don’t have any definitive answers, but I think we need something to the tune of a CA to solve this problem, and for everyone to digitally sign their gems using certificates which in turn are signed by some central trust authority So Say We All (until said authority turns out to be malicious, at which point we abandon them for Better Trust Authority, and on and on ad infinitum)
Building a trust model around how we ship software in the Ruby world is a hard problem, but it’s not an unsolvable one, and I think any good solutions will still work even in the wake of a total compromise of RubyGems.org.
In the words of That Mitchell and Webb Look: come on boffins, let’s get this sorted!
(Edit: If you are interested in this idea, please take a look at https://github.com/rubygems-trust. Also check out the #rubygems-trust IRC channel on Freenode)
Rubyists are people who generally value elegance over performance. “CPU time is cheaper than developer time!” is a mantra Rubyists have repeated for years. Performance has almost always taken a second seat to producing beautiful code, to the point that Rubyists chose what used to be (but is no longer) the slowest programming language on earth in order to get things done.
You can file me under the “somewhat agree” category, or otherwise I’d be using languages with a better performance track record like Java, Scala, or even Clojure. That said, I like Ruby, and for my purposes it has been fast enough. I also like to make light of those who would sacrifice elegance for speed, at least in Ruby, calling out those who would do silly stuff “FOR SPEED!” while compromising code clarity (otherwise known as roflscaling).
The past year though, there’s been an idea creeping through the Ruby community whose performance implications are so pathological I think it needs to die now. That idea is “DCI”, which stands for Data, Context, and Interaction. The DCI Architecture paper makes the following claims:
Imagine that we might use something like delegation or mix-ins or Aspects. (In fact each of these approaches has at least minor problems and we’ll use something else instead, but the solution is nonetheless reminiscent of all of these existing techniques.)
…
In many ways DCI reflects a mix-in style strategy, though mix-ins themselves lack the dynamics that we find in Context semantics.
DCI, as envisioned by its creators, is something distinct from mix-ins or delegation, however it seems in Ruby these are the two ways that people have chosen to implement it. This makes me believe that the way Rubyists are attempting to implement DCI does not live up to the original idea, but that’s a subject for a different blog post.
Far and away, the main pattern we see described as “DCI” in Ruby works by using a mix-in on an individual instance. This pattern is what I will be referring to from now on as “DCI”:
class ThisBlogContext
def initialize(rubyist)
rubyist.extend(Fool)
end
end
Let’s look at what’s happening here. First, we’re mixing the “Fool” module into the metaclass of the “rubyist” object. Since this is an instance-specific modification, unless “rubyist” already has an instance-specific metaclass, the Ruby VM needs to allocate a new one which will exist for the lifecycle of this object. Okay, so we’re allocating more memory than we otherwise would. That doesn’t seem too bad, does it?
Well, unfortunately there’s something far more sinister going on here inside the depths of any Ruby VM you happen to be using. The main thing we’re doing here is modifying the class hierarchy at runtime. Depending on when this is occurring, this can have very, very bad non-local effects. But before I get into that, let’s look at some benchmarks:
NOTE: you will need the benchmark-ips gem for this snippet
require 'rubygems'
require 'benchmark/ips'
class ExampleClass
def foo; 42; end
end
module ExampleMixin
def foo; 43; end
end
Benchmark.ips do |bm|
bm.report("without dci") { ExampleClass.new.foo }
bm.report("with dci") do
obj = ExampleClass.new
obj.extend(ExampleMixin)
obj.foo
end
end
And the results:
Using DCI is about an order of magnitude slower (or in the case of Rubinius, four orders of magnitude slower) than simply instantiating an object. Okay, so DCI is slow, right? Big deal, plenty of things are slow. But should we really care? The actual bottleneck here is going to be talking to the database or something, right? Actually, something far more sinister is going on here…
What if I were to tell you that the performance impact you’re seeing here wasn’t just localized to the little snippet we’re microbenchmarking, but is in fact having non-local effects that are causing similar performance degradations throughout your Ruby application? Scared now?
This is exactly what’s happening. All Ruby VMs use method caches to improve dispatch speed. They can, for example, cache which method to use based on the types flowing through a particular call site. These caches remain valid so long as we don’t see new types and the class hierarchy doesn’t change.
Unfortunately, what this approach to DCI is doing by using an instance-specific mixin is making modifications to the class hierarchy at runtime, and by doing so, it’s busting method caches throughout your application. By busting these caches everywhere, the performance effects you see aren’t localized just to where you’re using DCI. You’re taking a pathological performance hit every time you use obj.extend(Mixin).
This becomes especially problematic if you’re performing these sorts of runtime mixins every time you handle a request (or worse, multiple times per request). By doing so, you are preventing these caches from ever filling, and forcing the VM to dispatch methods in the most pathological way possible every time you use this feature.
Ruby gives you a lot of expressive power, but with great power comes great responsibility. My advice to you is to completely avoid using any of Ruby’s dynamic features which alter the class hierarchy after your application has loaded. They’re great to use when loading your application, but once your app has been loaded, you should really avoid doing anything that creates instance-specific metaclasses. This isn’t just limited to extend on objects but also includes things like doing def within a def, def obj.method, class << obj then making modifications, or define_method.
Let me provide a very different picture of how Rubyists used to view threads versus what the title of this post implies about now. I’m not talking about in 2005 in the early days of Rails. I’m talking about at Dr. Nic’s talk at RubyConf 2011, a little more than a year ago. Dr. Nic had a fairly simple message: when performance matters, build multithreaded programs on JRuby (also: stop using EventMachine). Now granted he was working the company that was subsidizing JRuby development at the time, but I didn’t, and I for one strongly agreed with him. Not many other people in the room did. The talk seemed to be met with a lot of incredulity.
“I thought this was going to be a talk on EventMachine!” said That Guy. Perhaps what That Guy missed was that Dr. Nic had hosted EventMachineConf as a subconference of RailsConf a few months before. And now Dr. Nic was saying don’t use EventMachine, use threads. And Dr. Nic is certainly not the only one who has come to this conclusion.
Flash forward to 2012 and I think the Ruby community has completely changed its tune. I may be a bit biased, but if I were to pick an overall “theme” (or perhaps “tone”) of RubyConf 2012, it’s that the single-core nature of the canonical Ruby interpreter, MRI (the “Matz Ruby Interpreter”), is limiting Ruby’s potential applications.
There was a lot of buzz about JRuby this year, and Brian Ford, one of the primary developers of Rubinius, announced the first 2.0 prerelease. Both of these Ruby implementations support parallel execution of multithreaded Ruby programs on multicore CPUs. I talked to a lot of people who are interested in my Celluloid concurrent object library as well.
At the same time RubyConf 2012 marked the first “Ruby 2.0” prerelease. Many of the talks covered upcoming Ruby 2.0 features, most notably refinements. Much like the release of Rails 2.0, this felt a bit underwhelming. What the crowd was clamoring for was what would be done with the Global Interpreter Lock (or GIL, or perhaps more appropriately the Global VM Lock or GVL in ruby-core parlance).
At the end of the conference, Evan Phoenix sat down with Matz and asked him various questions posed by the conference attendees. One of these questions was about the GIL and why such a substantial “two dot oh” style release didn’t try to do something more ambitious like removing the GIL and enabling multicore execution. Matz looked a bit flustered by it, and said “I’m not the threading guy”.
Well Matz, I’m a “threading guy” and I have some ideas ;)
Personally I’m a bit dubious about whether or not removing the GIL from MRI is a good idea. The main problems would be the initial performance overhead of moving to a fine-grained locking scheme, and also the bugs that would crop up as a large codebase originally intended for single-threaded execution is retrofitted into a multithreaded program. I think the large bug trail this would create would hamper future Ruby development, because instead of spending their time improving the language itself, ruby-core would spend its time hunting thread bugs.
All that said, there are some features I would personally like to see in Ruby which would substantially benefit multithreaded Ruby programs, GIL or no GIL. I would personally prioritize all of these features ahead of removing the GIL, as they would provide cleaner semantics we need to write correct multithreaded Ruby programs:
Recommendation #1: Deep freeze
Immutable state has a number of benefits for concurrent programs. What better way to prevent concurrent state mutation than to prevent any state mutation? (actually there are ways I think are better, but I’ll get to that later) Ruby provides #freeze to prevent modifications to an object, however I don’t think #freeze is enough.
Purely immutable languages allow the creation of immutable persistent data structures. The word “persistent” in this case doesn’t mean written to disk, but that you can create multiple versions of the same data structure with “persistent” copies of parts of the old one that get shared between versions. This approach only works if it’s immutable state all the way down. Ruby supports immutable persistent data structures via the Hamster gem, but it would be much easier to work with immutable data if this feature were in core Ruby.
What we need is more than just freezing of individual objects that #freeze provides. As some recent compiler research into immutability by Microsoft demonstrates, what really matters isn’t the mutability of individual objects but rather aggregates (i.e. object graphs). We need a guaranteed way to freeze aggregates as a whole, rather than freezing just a single object at a time. This means we’d walk all references from a parent object and freeze every single object we find. This would allow for the creation of efficient immutable persistent data structures in Ruby.
What would this look like? Something like Object#deep_freeze. While it’s possible to use Ruby introspection to attempt to traverse all the references a given object is holding recursively (see the ice_nine gem) this is something I really feel should be part of the language proper. I also get the idea that VM implementers know exactly where these references are in their implementations and could implement a lot faster version of #deep_freeze than using Ruby reflection to spelunk objects and find their references.
Recommendation #2: Deep dup
There’s another approach that works equally well when we have objects we’d like to mutate but that we’d also like to share across threads. Before we send objects across threads, we could make a copy, and give the copy to another thread.
Making copies every time we want to pass an object to another thread might sound expensive and wasteful, but there’s a language that’s been very successful at multicore performance which does just that: Erlang. In Erlang, every process has its own heap, so every time a message is passed from one process to another the Erlang VM makes a copy of the data being sent in the message and places the new copy in the receiving process’s heap space. (the exception is binary data, for which Erlang has a shared heap)
Ruby has two methods for making shallow copies of objects, Object#dup and #clone (which are more or less synonymous except #clone copies the frozen state of an object). However, the only built-in way to make a deep copy of entire object graphs is to use Marshal. This is nowhere near ideal for making in-VM copies, because for starters it produces an intermediate string that needs to be garbage collected, not to mention that Marshal uses a complex protocol which precludes the sorts of optimizations that could be done on a simple deep copy operation.
Instead of Marshaling, Ruby could support Object#deep_dup to make deep copies of entire object graphs. This would work much like #deep_freeze, traversing all references in an object graph but constructing an equivalent copy instead of freezing every object. Once a copy has been created, it can be safely sent to another thread. This could be leveraged by systems like Celluloid which control what happens at the boundary between threads. If Celluloid even provided an optional mode for always copying objects sent in messages, then using it would ensure your program was safe of concurrent mutation bugs.
Bonus points #1: Ownership Transfer
Copying object graphs every time we pass a reference to another thread is one solution to providing both mutability and thread safety, however making copies of object graphs is a lot slower than a zero copy system. Can we have our cake and eat it too: zero-copy mutable state objects that are free of any potential concurrent mutation bugs?
There’s a great solution to this: we can pin whole object graphs to a single thread at a time, raising exceptions in other threads that may hold a reference to any object in the graph but do not own it and attempt to perform any type of access. This idea is called ownership transfer.
The Kilim Isolation-Typed Actor system for Java is one implementation of this idea. Kilim supports the idea of “linear ownership transfer”: only one actor can ever see any particular object graph in the system, and object graphs can be transferred wholesale to other actors, but cannot be shared. For more information on the messaging model in Kilim, I definitely suggest you check out the portion of Kilim-creator Sriram Srinivasan’s talk on the isolation system Kilim uses for its messages.
Another language that supports this approach to ownership transfer is Go. References passed across channels between goroutines change ownership. For more information on how this works in Go, I recommend checking out Share Memory By Communicating from the Go documentation. (Edit: I have been informed that Go doesn’t have a real ownership transfer system and that the idea of ownership is more of a metaphor, which means the safety guarantees around concurrent mutation are as nonexistent as they are in Ruby/Celluloid)
Ruby could support a similar system with only a handful of methods. We could imagine Object#isolate. Like the other methods I’ve described in this post, this method would need to do a deep traversal of all references, isolating them as well so as to isolate the entire object graph.
Moreover, to be truly effective, isolation would have to apply to any object that an isolated object came in contact with. If we add an object to an isolated array, the object we added would also need to be isolated to be safe. This would also have to apply to any objects referenced from the object we’re adding to the isolated aggregate. Isolation would have to spread like a virus from object-to-object, or otherwise we’d have leaky bits of our isolated aggregate which could be concurrently accessed or mutated without errors.
If a reference to an isolated object were to ever leak out to another thread, and that thread tried to reference it in any way, the system would raise an OwnershipError informing you that an unpermitted cross-thread object access was performed. This would prevent any concurrent access or mutation errors by simply making any cross-thread access to objects without an explicit transfer of ownership an error.
To pass ownership to another thread, we could use a method like Thread#transfer_ownership(obj) which would raise OwnershipError unless we owned the object graph rooted in obj. Otherwise, we’ve just given control of the object graph to another thread, and any subsequent accesses by ourselves will result in OwnershipError. If we ever want to get it back again, we will have to hand the reference off to that other thread, and the other thread must explicitly transfer control of the object graph back to us.
A system like this would be a dream come true for Celluloid. One of the biggest drawbacks of Celluloid is its inability to isolate the objects being sent in messages, and while either #deep_freeze or #deep_dup would provide solutions to the isolation problem (with various and somewhat onerous tradeoffs), an ownership transfer system could provide effective isolation, zero copy messaging, and preserve mutability of data (which Ruby users will generally expect).
Bonus points #2: Unified Memory Model and Concurrent Data Structures
Java in particular is well known for its java.util.concurrent library of thread-safe data structures. Many of these are lock-free equivalents of data structures we’re already familiar with (e.g. ConcurrentHashMap). Others provide things like fast queues between threads (e.g. ArrayBlockingQueue)
It would be great if Ruby had a similar library of such data structures, but right now Ruby does not have a defined memory model (yet another thing Brian Ford called for), and without a memory model shared by all Ruby implementations it seems difficult to define how things like concurrent data structures will behave.
Celluloid solves some of the synchronization problems of multithreaded programs, but not all of them. It’s still possible to share objects sent in messages between Celluloid actors, and it’s possible for concurrent mutations in these objects go unnoticed.
I don’t think I can solve these problems effectively without VM-level support in the form of the aforementioned proposed features to core Ruby. You can imagine being able to do include Celluloid::Freeze or include Celluloid::Dup to control the behavior of how individual actors pass messages between each other. Or, even better, if Ruby had an ownership transfer system Celluloid could automatically transfer ownership of objects passed as operands to another actor or returned from a synchronous call. If that were the case, accesses to objects which have been sent to other threads would result in an exception instead of a (typically) silent concurrent mutation.
Celluloid is your best bet for building complex multithreaded Ruby programs, but it could be better… and we need Ruby’s help.
tl;dr: use authenticated encryption. use authenticated encryption. use authenticated encryption. use authenticated encryption. use authenticated encryption. use authenticated encryption. use authenticated encryption. use authenticated encryption. use authenticated encryption. use authenticated encryption.
Do you keep up on the latest proceedings of the IACR CRYPTO conference? No? Then chances are whenever you have tried to use a cryptographic library you made some sort of catastrophic mistake which would lead to a complete loss of confidentiality of the data you’re trying to keep secret.
The most important question is: are you using an authenticated encryption mode? If you don’t know what authenticated encryption is, then you’ve probably already made a mistake. Here’s a hint: authenticated encryption has nothing to do with authenticating users into a webapp. It has everything to do with ensuring the integrity of your data hasn’t been compromised, i.e. no one has tampered with the message.
Why is authenticated encryption so poorly known despite being so important? I don’t know. Perhaps it’s because the need for it wasn’t formally proven until the year 2000. And chances are you’ve never heard of authenticated encryption at all, because despite the best efforts of the cryptographic community it remains a relatively poorly-known concept.
Most of the cryptographic APIs you’ve ever encountered have probably made you run a gambit of choices for how you want to encrypt data. You might think AES-256 is the way to go, but by default your crypto API might select ECB mode, which is so bad and terribly insecure it isn’t even worth talking about. Perhaps you select CBC or CTR mode, but your crypto API doesn’t make you specify a random IV and will always encrypt everything with an IV of all zeroes, which if you ever reuse the same key will compromise the confidentiality of your data.
Let’s say you’ve gotten through all of that and are now using something like AES-CTR mode with a random IV per message. Great. Do you think you’re secure now? Probably not. A sophisticated attacker might attempt a man-in-the-middle attack, which gives him the ability to execute “chosen ciphertext” attacks (CCAs). To defend against these you must also ensure the integrity of your data, or otherwise confidentiality might be lost.
You may have learned you need to use a MAC to do this (and if you didn’t you’re most likely insecure!). You may have selected HMAC for this purpose. But you’re still left with three options here! Do you compute the MAC of the plaintext or the ciphertext. If you compute the MAC of the plaintext, do you encrypt it along with the plaintext, or do you append it to the end of the ciphertext? Or to spell it out more precisely, which of the following do you do?
Encrypt and MAC: encrypt the plaintext, compute the MAC of the plaintext, and append the MAC of the pltaintext to the ciphertext
Encrypt then MAC: encrypt the plaintext, compute the MAC of the ciphertext, and append the MAC of the ciphertext to the ciphertext
MAC then Encrypt: MAC the plaintext, append the MAC to the plaintext, then encrypt the plaintext and the MAC
If you have answered any of the above questions incorrectly (the correct answer to the above question is “encrypt then MAC”) you’ve quite likely created an insecure cryptographic scheme. Unless you really know what you’re doing and can answer all these questions correctly (and even then!), you probably shouldn’t be trying to build your own cipher/MAC constructions and should defer to cryptographic experts who specialize in that sort of thing. These cipher/MAC constructions are called authenticated encryption modes.
If you find yourself reaching for any form of encryption that isn’t an authenticated encryption mode, you’re probably doing it wrong. You shouldn’t ever be choosing between CBC or CFB or CTR (or god forbid ECB). Unless you’re a cryptographer, these should be considered dangerous low-level primitives not for the consumption of mere mortals.
That said, what should you be using?
NIST-approved AEAD block ciphers: AEAD stands for Authenticated Encryption with Associated Data, and represent ciphers that simultaneously provide confidentiality and integrity of data. Examples of these ciphers include EAX, GCM, and CCM modes. (Edit: some cryptographers have suggested I probably shouldn’t even recommend using this directly as there are still a number of attacks you will probably be susceptible unless you know what you’re doing, especially if you have a service accessible to an active attacker)
(Edit: adding this retroactively) Google Keyczar also provides a high-level cryptographic toolkit with authenticated encryption modes.
(Edit: also adding this retroactively) GPG is one of the easiest cryptographic tools to use that provides high-level functionality intended for cases where you would like authenticated encryption.
EAX is one of the recommended modes and is relatively easy to understand: it’s a combination of AES-CTR mode and CMAC (a.k.a. OMAC1) which is a MAC derived from a block cipher (in this case AES). While EAX mode is relatively simple to understand and you may be tempted to implement it yourself it if it’s unavailable in your language environment, you probably shouldn’t, as there are a number of potential pitfalls that await you and unless you know what you’re doing (and even then!) you’re likely to get it wrong.
If I’ve scared you enough by now, you my be googling around to discover if there’s an implementation of any of the above modes in your respective programming language environment, and sadly in many language environments you may turn up empty. In these cases, there’s not much you can do except petition your language maintainers who specialize in cryptography to expose APIs to authenticated encryption modes.
Authenticated encryption is something you should use as a complete package, implemented as a single unit by a well-reputed open source cryptographic library and not assembled piecemeal by people who do not specialize in cryptography.
Bottom line: unless you’re using authenticated encryption, you are opening yourself up to all sorts of attacks you can’t even anticipate, and shouldn’t consider the data you’re storing confidential.
Edit: several people have asked about more information on everything I’ve described here, most notably why various MACing schemes are secure or insecure. If you are really interested in this topic, I strongly recommend you take the Stanford Crypto class on Coursera which is what inspired me to write this blog post to begin with.
