Friday, 21 February 2020

Quantum crypto: Caveat emptor...

There is a great deal of buzz around the idea that with quantum cryptographic network links, we can shift to eavesdropping-proof communication that would be secure against every known form of attack.  The catch?  There is a serious risk of being tricked into believing that a totally insecure network link is a quantum cryptographic one.  In fact, it may be much easier and cheaper to build and market a fake quantum link than to create a real one!  Worse, the user probably wouldn't even be able to tell the difference.  You could eavesdrop on a naive user or her easily if you built one of these fakes and managed to sell it.  What's not to love, if you are hoping to steal secrets?

So, first things first.  How does quantum cryptography actually work, and why is it secure?  A good place to start is to think about a random pad: this is a source of random bits that is created in a paired read-once form.  You and your friend each have one copy of the identical pad.  For each message, you tear off one "sheet" of random bits, and use the random bits as the basis of a coding scheme.

For example, the current sheet could be used as a key for a fast stream cryptographic protocol.  You would use it for a little while (perhaps even for just one message), then switch to the next sheet, which serves as the next key.  Even if an attacker somehow was able to figure out what key was used for one message, that information wouldn't help for the next message.

This is basically how quantum cryptography works, too.  We have some source of  entangled photons, and a device that can measure polarization, or "spin".  Say that up is 1 and down is 0.  In principle, you'll see a completely random sequences of 0/1 bits, just like one sheet of a random pad.

Because the photons are entangled, even though the property itself is random, if we measure this same property for both of the entangled photons, we obtain the same bit sequence.

Thus if we generate entangle photons, sending one member of the pair to one endpoint and the other photon to the other endpoint, we've created a quantum one-time pad.  Notice that no information is actually being communicated.  In some sense, the photons do not carry information-per se, and can't be forced to do so.  The actual bits will be random, but because the photons are entangled, we are able to leverage the correlation to read exactly two copies out, one copy at each endpoint.  Then we can use this to obscure our messages (a classical method is used to authenticate the parties at each end, such as with RSA-based public and private keys).

Quantum cryptography of this form is suddenly being discussed very widely in the media, and there are more and more companies willing to sell you these cables, together with the hardware to generate entangled photons and to read out the binary bit strings using measurements on the entangled photon pairs. So why shouldn't everyone leap up this very moment and rush down to Home Depot to buy one?

To see the issue, think back to the VW emissions scandal from 2015.  It turned out that from 2011 to 2015, the company was selling high-emission engines that had a way to sense when they were being tested.  In those periods, they would switch to a less economical (but very clean) mode of operations  This would fool the department of motor vehicles, after which the car could revert to its evil, dirty ways.

Suppose the same mindset was adopted by a quantum cable vendor.  For the non-tested case, instead of entangling photons the company could generate a pseudo-random sequence of perfectly correlated unentangled ones.  For example, it could just generate lots of photons and filter out the ones with an unwanted polarization.  The two endpoint receivers measure polarization and see the same bits.  This leads them to think they share a secret one-time pad... but in fact the vendor of the cable not only knows the bit sequence but selected it!

To understand why this would be viable, it helps to realize that today's optical communication hardware already encodes data using properties like the polarization or spin of photons.  So the hardware actually exists, and it even runs at high data rates!  Yet  the quantum cable vendor will know exactly what a user will measure at the endpoints.

How does this compare to the quantum version?  In a true quantum crytographic network link, the vendor hardware generates entanged data in a superposition state.  Now, this is actually tricky to achieve (superpositions are hard to maintain).  As a result, the vendor can predict that both endpoints will see correlated data, but because some photons will decorrelate in transmission, there will also be some quantum noise.  (A careful fake could mimic this too, simply by computing the statistical properties of the hardware and then deliberately transmitting different data in each direction now and then).

So as a consumer, how would you test a device to unmash this sort of nefarious behavior?

The only way that a skeptic can test a quantum communication device is by running what is called a Bell's Inequality experiment.  With Bell's, the skeptic runs the vendor's cable, but then makes a random measurement choice at the endpoints.  For example, rather than always measuring polarization at some preagreed angle, it could be measured at a randomly selected multiple of 10 degrees.   The idea is to pick an entangled superposition property and then to measure it in a way that simply cannot be predicted ahead of time.

Our fraudulent vendor can't know, when generating the original photons, what you will decide to measure, and hence can't spoof an entanglement behavior.  In effect, because you are making random measurements, you'll measure random values.  But if the cable is legitimate and the photons are genuinely entangled, now and then the two experiments will happen to measure the same property in the identical way -- for example, you will measure polarization at the identical angle at both endpoints.  Now entanglement kicks in: both will see the same result.  How often would this occur?  Well, if you and I make random selections in a range of values (say, the value that a dice throw will yield), sometimes we'll bet on the same thing.  The odds can be predicted very easily.

When we bet on the same thing, we almost always read the same value (as mentioned earlier, quantum noise prevents it from being a perfect match).  This elevated correlation implies that you've purchased a genuine quantum cryptography device.

But now think back to VW again.  The company didn't run with low emissions all the time -- they had a way to sense that the engine was being tested, and selected between emission modes based on the likelihood that someone might be watching.  Our fraudulent vendor could try the same trick.  When the cable is connected to the normal communication infrastructure (which the vendor supplies, and hence can probably detect quite easily), the cable uses fake entanglement and the fraudulent vendor can decode every message with ease.  When the cable is disconnected from the normal endpoint hardware, again easy to detect, the vendor sends entangled photons, and a Bell's test would pass!

Clearly, a quantum communications device will only be trustworthy if the user can verify the entire device.  But how plausible is this?  A device of this kind is extremely complex.

My worry is that na├»ve operators of systems that really need very good security, like hospitals, could easily be fooled.  The appeal of a quantum secure link could lure them to spend quite a lot of money, and yet most such devices may be black boxes, much like any other hardware we purchase.  Even if a device somehow could be deconstructed, who would have the ability to validate the design and implementation?  A skilled skeptical buyer might have no possible way to actually validate the design!

So, will quantum security of this form ever be a reality?  They already are, in lab experiments where the full system is implemented from the ground up.  But one cannot just purchase components and cobble such a solution together: the CIO of a hospital complex who wants a secure network would need to purchase an off-the-shelf solution.  I can easily see how one might spend money and end up with a system that would look as if it was doing something.  But I simply don't see a practical option for convincing a skeptical auditor that the solution actually works!

Saturday, 15 February 2020

The delicate art of the pivot

Success in computing often centers on having the flexibility to know when to pivot an idea, and yet simultaneously, the steadiness to not wander off on hopeless yet seductive tangents.  Pivoting is a surprisingly subtle skill.

A bit of context.  We say that a project has done a pivot if it sets out in one direction but later shifts to focus on some other way of using some of the same ideas.  A pivot that tosses out the technology isn't really what I mean... I'm more interested in the kind of mid-course correction that doesn't require a ground-up rethinking, yet might have a profound impact on the marketing of a product or technology.

Pivots are a universal puzzle for entrepreneurs and researchers alike.  I'm pretty good at finding the right research questions, but not nearly as capable of listening to the market.  I remember an episode at Reliable Network Solutions (RNS). This was a company founded by Werner Vogels, Robbert van Renesse and me, to do management solutions for what we would call cloud computing data centers today.  Back then the cloud term wasn't yet common, so those were really very early days.

We launched RNS to seize an initial opportunity that was irresistible: call it the ultimate business opportunity in this nascent cloud space.  In our minds, we would solve the problem for one of the earliest major players and instantly be established as the go-to company for a solution.  Now, as it happened, our initial customer had special requirements, so the solution we created for them was something of a one-off (they ultimately used it, and I think they still do), but our agreement left us the freedom to create a more general product that we could sell to everyone else.  So, the RNS business plan centered on this follow-on product.  Our vision was that we would create a new and more scalable, general-purpose, robust, self-repairing, fast, trustworthy management infrastructure solution.  We were sure it would find a quick market uptake: after all, customer zero had been almost overwhelmingly hungry for such a solution, albeit in a slightly more specialized setting unique to their datacenter setups.

RNS ended up deciding to base this general product on Astrolabe, a scalable gossip-based management information database that we came up with as a research prototype, inspired by that first product for customer zero.  We had the prototype running fairly quickly, and even got a really nice  ACM TOCS paper out of the work.   Astrolabe had every one of our desired properties, and it was even self-organizing -- a radical departure from the usual ways of monitoring and managing datacenter systems.

Astrolabe was a lovely, elegant idea.  Nonetheless, when we made this decision to bet the bank on it (as opposed to doing something much narrower, along the lines of what we did for that first customer), we let our fondness for the concept get way out ahead of what the market really wanted.

I remember one particular road trip to San Francisco.  We met with the technology leaders of a large company based there, and they set up a kind of brainstorming session with us.  The intent was to find great fits for Astrolabe in their largest datacenter applications.  But guess what?  They turned out to really need a lot less than Astrolabe... and they were nervous that Astrolabe was quite exotic and sophisticated... it was just too big a step for them.

In fact, they wanted something like what Derecho offers today: an ultra-fast tool for replicating files and other data.  They would have wanted Derecho to be useable as a stand-alone command-line solution (we lack this for Derecho: someone should build one!).  But they might have gone for it as a C++ library.  In effect, 15 years later, I finally have what those folks were basically looking for at the time.

At any rate, we had a potential next big customer and a fantastic opportunity for which our team was almost ideally suited -- my whole career has focused on data replication.  Even so, RNS just couldn't take this work on.  We had early customers for our Astrolabe concept, plus customer zero continued to give us some work, and our external investors had insisted on a set of Astrolabe milestones.  We were simply spread too thin, and so even though our friends in San Francisco spoke the truth, it was just impossible for us to take their advice.

But guess what?  Reliable Network Solutions never did manage to monetize Astrolabe in a big way, although we did make a number of sales, and the technology ultimately found a happy home.  We just sort of bumped along for a few years, making barely enough money to pay all our bills, and never hitting that home run that can transform a small company into a big one.  And then, in 2001, the 9-11 terrorist attack triggered a deep tech downturn.  By late 2002 our sales pipeline had frozen up (many companies pause acquisitions during tech downturns), and we had no choice but to close the doors.  35 people lost their jobs that day.

The deep lesson I learned was that a tech company always needs to be awake to the possibility that it has the strategy wrong, that its customers may be able to see the obvious even though company leaders are blind because of their enthusiasm for the technology they've been betting on, and that a pivot might actually save the day.  The path forwards sometimes leads to a dead end.

This is a hard lesson to teach.  I've sometimes helped the Runway "post-doc" incubator program, which is part of the Jacobs Institute at NYC Tech, the technology campus Cornell runs in New York jointly with Technion.  My roles have been pretty technical/engineering ones: I've helped entrepreneurs figure out how to leverage cloud computing to reduce costs.

But teaching entrepreneurs to be introspective about their vision and to pivot wisely?  This has been an elusive skill, for me.  The best person I've ever seen at this is our Runway director, Fernando Gomez-Baquero.  Fernando favors an approach that actually starts by accepting the ideas of the entrepreneurial team at face value.  But then he asks them to validate their concept.   He isn't unreasonable about this, and actually helps them come up with a plan.  Just the same, he never just accepts assumptions as given.  Everything needs to be tested.

This is often hard: one can stand in the hallway at a big tech show-and-tell conference and interview passing CTOs (who are often quite happy to hold forth on their visions for the future), but even if a CTO shows interest, one has to remember my experience with RNS: product one, even a successfully delivered product that gets deployed, might not be a scalable story that can be resold widely and take a company down the path to wild profits.

Fernando is also very good at the non-technology side of companies: understanding what it takes to make a product look sexy and feel right to its actual end-users.  A lot of engineering teams neglect the whole look and feel aspect because they become so driven by the technical ideas and research advances they started with that they just lose track of the bigger picture.  Yet you can take a fantastic technology and turn it into a horrible, unusable product.  Fernando's students never make that kind of mistake: for him, technology may be the "secret sauce", but you have to make the dish itself irresistible, and convince yourself that you've gotten that part right.

This end, what Fernando does is to ask the entrepreneurs to list 20 or so assumptions about their product and their market.  The first few are always easy.  Take RNS: we would have said we were betting that datacenters would become really immense (they did), that managing a million machines at a time is very hard (it is), that the management framework needs to be resilient, self-repairing, stable under stress (and indeed, all of these are true).  Fernando, by the way, wouldn't necessarily agree that these are three assumptions and would never split that last item into subitems.  Instead, he might actually call this just one or two assumptions, and if you have additional technology details to add, he would probably be inclined to just lump them in.  This gets back to my point above:   For a startup company, technology is only a tiny part of the story.  All these "superior properties" of the RNS solution?  Fernando would just accept that.  Ok, "you have technical advantages."  But he would insist on seeing the next 20 items on the list.

When you are constrained to carry out a seemingly strange task, it can feel natural to list human factors: that CTOs have a significant cost exposure on datacenter management, that they know this to be true, and that they would spend money to reduce that exposure.  That they might have an appetite for a novel approach because they view existing ones as poorly scalable.  You might start to toss in cost estimate items, or pricing guesses.  If 20 turns out to be too easy a target, Fernando would read your list, then ask for a few more.

Fernando once told me an anecdote that I remember roughly this way: Suppose that a set of entrepreneurs wanted to bring Korean ice cream to the K-12 school cafeterias in America.  They might outline this vision, extoll the virtues of ice cream in tiny little dots (Korean ice cream is made by dripping the ice cream mix into liquid nitrogen "drop by drop"), and explain that for the launch, they would be going with chocolate.   They would have charts showing the explosive sales growth of Korean ice cream in K-12 schools in Seoul.   Profits will be immense! Done deal, right?

Well, you can test some of these hypotheses.  It isn't so hard to visit K-12 cafeterias, and the head chef probably would be very happy to be interviewed in many of them.  But guess what you might learn?  Perhaps, FDA rules preclude schools from serving ice-cream in a format that could possibly be inhaled.  Perhaps chocolate is just not a popular flavor these days strawberry is the new chocolate, or mint, or Oreo crunch.  Korea happens to be a fairly warm country: the demand for ice cream is quite high during the school year there.  Maybe less-so here.  Anyhow, ice cream isn't considered healthy here, and not every cafeteria serves sweets.

Korean dot-style ice cream?  Awesome idea!  But this kind of 20-questions approach can rule out ill-fated marketing plans long before the company tries to launch its product.  Our ice-cream venture could easily have been headed straight for a costly (but yet, delicious) face-plant. Perhaps the company would have failed.  Launch the exact same concept on the nation's 1000 or so small downtown pedestrian malls, and it could have a chance.  But here we have a small pivot: how would that shift in plan change the expense models?  Would we rent space, or kisoks, or sell from machines?  Would there be new supply challenges, simply to get the ice cream to the points of sale?   Schools are easy to at least find: you can download a list.  How would you find those 1000 small malls, and who would be selling the product at each location?

Had we done a this 20-questions challenge with Astrolabe, we might have encountered the friendly folks in California far sooner, gotten the good advice we received early enough to act on it, and realized that Astrolabe was just too exotic for our target market to accept as a product.  Technically superior?  Absolutely, in some dimensions -- the ones academic researchers evaluate.  But not every product needs technical superiority to win in the market, and conversely, not every technical attribute is decisive in the eyes of CTO buyers.

Fernando is a wizard at guiding companies to pivot before they make that costly error and find themselves so committed to the dead end that there is simply no path except to execute the plan, wise or foolish.

Today, I look at some of my friends who lead companies, and I'm seeing examples everywhere of how smartly timed pivots can be game-changing.  I was blind to that sort of insight back in 2000 when I was actually running RNS.

The art of the pivot isn't necessarily natural for everyone.  By now, I understand the concept and how it can be applied, but even so, I find that I'm prone to fall in love with technology in ways that can cloud my ability to assess a market opportunity in an unbiased way.  It really isn't easy.

So here's my advice: Anyone reading this blog is a technology-centric datacenter person.  Perhaps you teach and do research, as I do (most of the time, anyway).  Perhaps you work for a big company... perhaps you are even toying with trying to launch one.  But I would argue that every one of us has something to learn from this question of technology pivots.  Our students, or our colleagues, or our direct reports: they may be holding fast to some sort of incorrect belief, betting more and more heavily on it, and yet that belief may be either outright wrong, or perhaps just in need of a tweak.

You yourself may be more locked-in on some aspect of your concept than you realize.  That rigidity could be your undoing!

Fernando's 20-questions challenge is awesome because it doesn't approach the issue confrontationally.  After all, the entrepreneurs themselves make the list of assumptions -- it isn't as if Fernando imposes them.  They turn each assumption into a question, too, Jeopardy style.  Then he just urges them to validate the resulting questions, easiest first.  Some pull this off... others come back eager to pivot after a few days, and open to brainstorming based on what they learned.

What an amazing idea.  I wish that back then, we could have launched RNS in the Runway program!  Today, I might be running all the world's cloud computing systems.