[Cryptography] RSA is dead.

[David Wagner]

On Tue, Dec 24, 2013, at 02:05 PM, ianG wrote:
> So, assuming I sober up by the morn, and SO doesn't notice, where's 
> Ping's code?

I believe I've managed to faithfully reconstruct the version
of Ping's code that contains the deliberately inserted bug.
If you would like to try your hand at finding the bug, you can
look at it yourself:
  http://www.cs.berkeley.edu/~daw/tmp/pvote-backdoored.zip
I'm copying Ping, in case he wants to comment or add to
this.

Some grounds rules that I'd request, if you want to try
this on your own:
1. Please don't post spoilers to the list.  If you think you've
    found a bug, email Ping and I privately (off-list), and I'll be
    happy to confirm your find, but please don't post it to the
    list (just in case others want to take a look too).
2. To help yourself avoid inadvertently coming across
    spoilers, please don't look at anything else on the web.
    Resist the temptation to Google for Pvote, check out the
    Pvote web site, or check out the links in the code.  You
    should have everything you need in this email.  We've
    made no attempt to conceal the details of the bug, so
    if you look at other resources on the web, you may
    come across other stuff that spoils the exercise.
3. I hope you'll think of this as something for your own
    own personal entertainment and edification.  We can't
    provide a controlled environment and we can't fully
    mimic the circumstances of the review over the Internet.

-----

Here's some additional information that may help you.

We told reviewers that there exists at least one bug,
in Navigator.py, in a region that contains 100 lines of code.
I've marked the region using comments.  So, you are
free to focus on only that part of the code (I promise you
that we did not deliberately insert any bug anywhere else
outside that region).  Of course, I'm providing all the code,
because you may need to understand how it all interacts.
The original Pvote code was written to be as secure and
verifiable as we could make it; I'm giving you a modified
version that was modified to add a bug after the fact.
So, this is not some "obfuscated Python" contest
where the entire thing was designed to conceal a
malicious backdoor: it was designed to be secure, and
we added a backdoor only as an afterthought, as a way
to better understand the effectiveness of code review.

To help you conduct your code review, it might help to
start by understanding the Pvote design.  You can read
about the theory, design, and principles behind Pvote
in our published papers:

- An early version of Pvote, with many of the main ideas:
  paper: http://pvote.org/docs/evt2006/index.html
  Ping's slides: http://pvote.org/docs/evt2006/talk.pdf

- Many improvements to the initial idea, and the final Pvote:
  paper: http://pvote.org/docs/evt2007/index.html
  slides: http://pvote.org/docs/evt2007/talk.pdf

The Pvote code probably won't make sense without
understanding some aspects of its design and how it is
intended to be used, so this background material might
be helpful to you.

We also gave reviewers an assurance document, which
outlines the "assurance case" (a detailed argument describing
why we believe Pvote is secure and fit for purpose and free
of bugs).  Here's most of it:
  http://www.cs.berkeley.edu/~daw/tmp/pvad-excerpts.pdf
Why not all of it?  Because I'm lazy.  The full assurance
document contains the actual, unmodified Pvote code.  We wrote
the assurance document for the unmodified version of Pvote
(without the deliberately inserted bug), and the full assurance
document includes the code of the unmodified Pvote.  If you
were to look at that and compare it to the code I gave you
above, you could quickly identify the bug by just doing
a diff -- but that would completely defeat the purpose of the
exercise.  If I had copious free time, I'd modify the assurance
document to give you a modified document that matches
the modified code -- but I don't have time to do that.  So,
instead, I've just removed the part of the assurance
document that contained the region of the code where we
inserted our bug (namely, Navigator.py), and I'm giving you
the rest of the assurance document.

In the actual review, we provided reviewers with additional
resources that won't be available to you.  For instance, we
outlined for them the overall design principles of Pvote.  We
also were available to interactively answer questions, which
helped them quickly get up to speed on the code.  During
the part where we had them review the modified Pvote with
a bug inserted, we also answered their questions -- here's
what Ping wrote about how we handled that part:

 Since insider attacks are a major unaddressed threat in existing
 systems,
 we specifically wanted to experiment with this scenario. Therefore, we
 warned the reviewers to treat us as untrusted adversaries, and that we
 might not always tell the truth. However, since it was in everyone’s
 interest
 to use our limited time efficiently, we settled on a time-saving
 convention.
 We promised to truthfully answer any question about a factual matter
 that
 the reviewers could conceivably verify mechanically or by checking an
 independent source — for example, questions about the Python language,
 about static properties of the code, about its runtime behaviour, and
 so on.

Of course, since this is something you're doing on your
own, you won't get the benefit of interacting with us and having
us answer questions for you (to save you time).  I realize this
does make code review harder.  My apologies.

You can assume that someone else has done some
runtime testing of the code.  We deliberately chose a bug
that would survive "Logic & Accuracy Testing" (a common
technique in elections, where election officials conduct a
test in advance where they cast some ballots, typically
chosen so that at least one vote has been cast for
each candidate, and then check that the system accurately
recorded and tallied those votes).  Focus on code review.

-- David