Cryptography — 1 comment
11
Feb 12

New Ed25519 “ref10″ implementation available: 20x faster

“Dcoder” on the #tahoe-lafs IRC channel was kind enough to point me at the latest SUPERCOP benchmark-suite release: http://hyperelliptic.org/ebats/supercop-20120210.tar.bz2 , which includes a new portable-C reference version of the Ed25519 signature code named “ref10″. I added this into python-ed25519 in the “ref10″ branch (at https://github.com/warner/python-ed25519/tree/ref10) and did some quick speed comparisons.

I’m delighted to see that the new code is roughly 20x faster than the previous version, without using processor-specific non-portable assembly language. The old “ref” code, on my 2008 laptop (2.53GHz Core2Duo), makes signatures in 2ms and verifies them in 7ms. The “ref10″ code signs in 120us and verifies in 307us. That’s over 8300 signatures per second! The ref10 version also includes the batch-verification function, which (thanks to some tricks in the design of Ed25519) makes it faster to verify many signatures at once. Interestingly, this requires random numbers on the *verification* side (since it’s doing statistical verification: if the attacker knew which random numbers you were going to use, they could craft a set of message that would appear valid when checked by the batch verifier, but were invalid when checked individually).

Naturally, this release came exactly one day after I finally published python-ed25519 1.0 :-) . But 1.1 will have the speedups.

 

Jetpack / Python — 2 comments
31
Jan 12

Version String Management in Python: Introducing python-versioneer

What’s a good way to manage version numbers in a Python project? I don’t mean:

  • where should it be stored, so that other code can find it. PEP 8 tells us to use __version__, and distutils tells us to call setup() with a version= argument. The embedded string is particularly useful to report or record a version in bug reports.
  • what format it should take: PEP 386 describes a format (N.N[.N]+[{a|b|c|rc}N[.N]+][.postN][.devN]) that enables comparison, so packaging tools can evaluate things like “dependency > 1.2.0″. (I happen to find this format really limiting, and this tool doesn’t necessarily produce PEP386-compliant strings, but that’s not what this post is about)

What I do mean is:

  • how does the right version string get into the code?
  • what does a release manager need to do when it’s time to make a new release?

The traditional approach, ages old, is to have a static string embedded in the code. Each time you’re about to make a new release, you make a commit which updates this string. It’s nice and simple, but has some problems: Continue reading →

Cryptography — 7 comments
19
Jan 12

Improving the pynacl build process

I’ve been hacking on my copy of pynacl this week. pynacl is a set of Python bindings to the NaCl cryptography library (by djb and friends). The bindings, first written by Sean Lynch and then picked up by “k3d3″, are great. They even support py2.6 through py3.2.

But actually building them is a hassle, because the NaCl build process is so idiosyncratic. It consists of a 500-line undocumented shell script named “do”, and running it gets you 25 minutes of 100% CPU that executes in stony silence (all progress messages are redirected to a logfile). If you can wait that long, and think to explore the directory afterwards, you’ll be rewarded with a build/HOSTNAME/ directory that contains a libnacl.a and a set of header files that are pretty easy to use. What’s actually going on behind the scenes is that the script is exhaustively compiling and testing a large matrix of compiler flags (-O vs -O3 vs -O3 -funroll-loops), ABI variants, and alternative implementations. The goal is apparently to:

  • select the fastest possible implementation and compiler options, using any assembly-language tricks specific to the processor (SSE3, etc)
  • make sure the unit tests pass
  • construct a performance report to send back to the authors

Unfortunately, this doesn’t play well with other build systems that might want to embed a copy, such as Python’s distutils, because:

  • some compiler flags (-fPIC) are needed to build the .so files that python can load at runtime: distutils knows what these are, “do” doesn’t
  • when building e.g. debian packages, the results will be used on other machines, so processor-specific optimizations aren’t ok (you might build your packages on a machine with some feature that’s not present on the machines that use those packages, so stick with least-common-denominator).
  • running “do” requires a Bourne Shell interpreter, standard on unix systems but not so obvious on windows. distutils knows how to compile things on windows, but you have to tell it the source files, and it will run the compiler itself.
  • having a separate “./do” compile step means that “setup.py build” is not enough, which means that easy_install won’t work, making it hard to use pynacl as a dependency in virtualenv or pip environments.

In addition, waiting 25 minutes for an otherwise small and elegant library to build is just a drag.

Continue reading →

Cryptography — Leave a comment
29
Nov 11

Ed25519 Keys

How do Ed5519 keys work?

There are several different implementations of the Ed25519 signature system, and they each use slightly different key formats. While writing python-ed25519, I wanted to validate it against the upstream known-answer-tests, so I had to figure out how to convert those keys into a format that my code could use.

Continue reading →

Cryptography — 1 comment
21
Nov 11

Introducing python-ed25519

Ed25519 is an implementation of Schnorr Signatures in a particular elliptic curve (Curve25519) that enables very high speed operations. It also has a few nice features to make the algorithm safer and easier to use.

I’ve published some MIT-licensed Python bindings to djb++’s portable C implementation of this signature scheme. They’re available here:

Some highlights:

  • signing keys and verifing keys are both just 32 bytes
  • signatures are 64 bytes
  • key generation and signing each take about 2ms on my 2010 MacBookPro
  • signature verification takes about 6ms
  • 128-bit security level, comparable to AES-128, SHA256, and 3072-bit RSA
  • No entropy needed during signing (signatures are deterministic)

There are amd64-specific assembly versions that run even faster, in just a few hundred microseconds, and for bulk operations you can do batch verification faster than one-at-a-time verification. So you can perform thousands of operations per second with this algorithm (and hundreds with this particular implementation).

It’s very exciting to finally have short+fast signatures (and also, through Curve25519, key-agreement and encryption): it opens up a lot of new possibilities. When public-key encryption was first invented, keys took so long to generate that folks assumed that each human would have just one: all sorts of mental baggage was built up around this restriction (ideas like never sharing signing keys, keys representing people, and the need to distribute keys separately from fingerprints). When you can easily generate a new key for each message or object or operation, we can let go of some of those psychological fetters and build something new.

(Note that “Curve25519” uses the same basic curve equation, but only provides Diffie-Hellman key agreement [and, by extension, public-key encryption]. It can’t be used to create signatures that can be verified by third parties: for that you need Ed25519. A portable Curve25519 implementation can be found in curve25519-donna, and includes a Python binding that I wrote too)

Take a look and let me know what you think!

Cryptography / Tahoe-LAFS — 6 comments
28
Oct 11

Cryptographic Invitation Protocols

For a while now, I’ve been noodling around with a cryptographically-secure "invitation protocol" of sorts. I want something that can start with Alice sending an Invitation Message to Bob, and end with fully secure bidirectional communication.

The use cases I have so far are:

  • secure file-transfer tools, as a browser plugin or standalone application. The program would have an address-book, each entry would have an "Inbox" for that person, you would send them a file by drag-and-dropping it onto the Inbox. This invitation protocol would be used to populate the address book.
  • secure communication tools, like Petmail or an encrypted email/IM client, in which you want to add address-book entries so you can later exchange messages with the right correspondent.
  • Tahoe grid membership tools: you would use an Invitation to securely add another person’s client/server node to your grid, maintaining enough information to perform Accounting and server-selection properly.

but there are lots of others. Most applications with any sort of social component need a way to add "buddies" or correspondents. There are plenty of centralized systems (like IM networks, where the namespace is controlled by a single company), and a handful of insecure decentralized systems (like email addresses). I want this protocol for secure decentralized systems, in which the primary identifier for each participant is a public key of some sort.

Read on if you’re interested in cryptographic protocols..

Continue reading →

Jetpack — Leave a comment
06
Sep 11

London Jetpack Workshop coming up: September 29th

If you’re in the London area, check out the free workshop we’re hosting on writing addons with Jetpack. It’s happening on a Thursday night (September 29th) at City University. See Jeff’s blog post for details and signup. We’re also setting one up for the San Francisco area in October.. stay tuned.

I’ll be leading a session on using modules. See you there!

 

Jetpack / Tahoe-LAFS — Leave a comment
25
Aug 11

Introductions

Hi! My name is Brian Warner. Welcome to my blog!

I’ve been working at Mozilla for about a year and a half. Before Mozilla I was at a startup (now gone) named AllMyData.com, which ran an online backup service aimed at home users and small businesses. For the backend, we developed an open-source encrypted distributed filesystem named Tahoe-LAFS (still thriving), with the relatively-unique feature of “provider-independent security”: the servers hold ciphertext, and only your client (and anyone you choose to share them with) holds the decryption key. By relying upon the servers for availability but not security, you can use servers that you wouldn’t trust otherwise. The system is designed with “POLA” in mind, the Principle Of Least Authority, which improves safety by giving each component as little power as possible; just enough to do its one job.

Mozilla’s Sync system, which helps keep your bookmarks and other browser data synchronized between multiple browsers, uses the same principle. The data is encrypted before it leaves your computer, and our servers don’t get to see the key. The similarity in philosophy between Sync and Tahoe was a big part of the reason I joined Mozilla: I had found a bunch of like-minded people with whom I could promote these ideas, with a wider audience (400 million users and counting!) than anything our tiny startup could reach. Shortly after joining, I helped build the credential-exchange protocol that Sync uses to add a new computer to your account (the “copy this code” J-PAKE-based dialog panel).

But most of what I’ve been doing for the last 18 months is Jetpack, now better known as the Add-On SDK. It’s a new way to tackle the admittedly painful process of writing add-ons for Firefox (and eventually other XUL-based programs, like Thunderbird).

Add-ons in Firefox have always been a bit.. organic. There’s an awful lot of internal interfaces, and add-ons authors have had to dig through a lot of that to find a useful point to attach or override some code. It’s messy, and fragile: it’s difficult for the Firefox developers to keep those internals stable while making large-scale improvements to the browser, so add-on authors are fighting an uphill battle to maintain compatibility with newer releases. With our new faster release cadence (every couple months!), the problem becomes even more challenging.

Jetpack was intended to make the simple things simple. It has a library of interface modules for doing common add-on tasks, like creating a UI, and modifying web pages. We, the SDK authors, will keep updating these modules to match the Firefox internals, so add-on authors won’t have to. One of the promises of Jetpack is that the high-level add-on code doesn’t need to change much at all to keep up with newer browsers.

The SDK has two parts: this library of modules, and a program that assembles your code with the right set of modules and produces the XPI file, ready for installation or upload to AMO. If you think about it in terms of gcc and other compilers, this program is a linker: it figures out which modules are required and combines them into an executable bundle.

The linker is written in Python, and since that’s been my dominant language for the last ten years, most of my Jetpack work has been on the linker side. I’ve also been heavily involved in developing the security model, to make Jetpack-based addons safer in the face of bugs and compromises. I’ll be explaining a lot more about the security model in this blog over the coming months.

And no description of Jetpack is complete without also mentioning Flightdeck, better known as the Add-On Builder. This is an online IDE for writing add-ons. On the backend, it runs a copy of the SDK to generate the XPIs. It allows folks to get into the add-on writing business without downloading or installing an SDK: just start writing the code! A big goal of Jetpack is to make add-on writing accessible to a wider developer community, leveraging Javascript skills that web-devs already have, and an online tool like Builder removes a lot of the unnecessary hurdles for that audience.

Welcome!
-Brian