[Cryptography] how reliably do audits spot backdoors? (was: Re: RSA is dead.)

[Bill Frantz]

See <http://zesty.ca/pubs/yee-phd.pdf> Building Reliable Voting 
Machine Software

    Ka-Ping Yee

A dissertation submitted to the Graduate Division
of the University of California, Berkeley
in partial fulfillment of the requirements for the degree of
Doctor of Philosophy in Computer Science

p136ff for an experiment where reviewers attempted to find three 
bugs that had been inserted in some voting machine code.

The results were (p148):

"David Wagner and I decided to insert three bugs into Pvote to
see if the reviewers would find them. We inserted what we
thought would be an “easy” bug, a “medium” bug, and a “hard
bug” to find, and chose each bug individually in such a way that
an insider could conceivably exploit the bug to influence the
results of an election. These bugs are detailed in Appendix
E.

We decided to insert all of these bugs in a 100-line region of
a single file, lines 11 to 109 of Navigator.py, and told the
reviewers to look in this region. We did this both because the
navigator was the most interesting in terms of the program
logic and because we knew the reviewers would have limited
time. The new version of the code that we gave the reviewers
contained all three bugs, but we did not tell the reviewers how
many bugs there were.

Yoshi Kohno, Mark Miller, and Dan Sandler participated as
reviewers on the third day of the review. Dan was very familiar
with Python and found the “easy” and “medium” bugs quickly,
within about 70 minutes. Yoshi Kohno and Mark Miller found
the “easy” bug after about four hours of reviewing. None of the
reviewers found the “hard” bug

Ian Goldberg and Yoshi Kohno participated as reviewers on
the fourth day of the review. Ian Goldberg also found the “easy”
bug within about two hours; none of the other bugs were found
on the fourth day.

The reviewers spent a total of about 20 reviewer-hours
focused on the task of finding the bugs in this 100-line section
of Navigator.py.

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz        | Since the IBM Selectric, keyboards have gotten
408-356-8506       | steadily worse. Now we have touchscreen keyboards.
www.pwpconsult.com | Can we make something even worse?