Over the last few years, I have been involved in issues related to the use of computerization in voting. This has come about because of my concerns about computer security, privacy and reliability, and from my role as chair of the ACM U.S. Public Policy Committee (USACM). USACM has taken a strong position as regards use of computers as voting stations and voting over the internet.

Two recent items address the issue of voting over the Internet.

The first is a study released by NIST about the threats posed by internet voting. This is a well-written document describing problems that would be encountered with any online voting system. Their conclusion is that, for public elections, distribution of blank ballots (on paper) is the only reasonable improvement that we can make with current technology.

The second is a note from my colleague, Yvo Desmedt, one of the senior leaders in information security He has asked that I circulate this to a wider audience:

  IACR (the International Association for Cryptologic Research) has changed its bylaws to allow e-voting over the internet to elect its board members and other purposes. IACR will likely move towards internet e-voting. The IACR Board of Directors subcommittee on internet e-voting has published a list of requirements for such a system at: http://www.iacr.org/elections/eVoting/requirements.html This is evidently a first step and the question remains whether the system the International Association for Cryptologic Research will choose will be easy to hack or not. So, security experts should follow this development.

The problems that need to be addressed by any voting technology are mostly obvious: impersonation of the voter, impersonation of the voting system, disclosure of the ballot, multiple voting, loss of votes, denial of access, and a number of other issues. The problems are complicated by the requirements of a fair voting system, one of which is that of vote deniability—that the voter is able to deny (or claim) that her/his vote was cast a particular way. This is important to prevent vote buying, or more importantly, retribution against voters who do not cast ballots in a particular way. It isn’t difficult to find stories where voters have been beaten or killed because of how they voted (or were presumed to have intended to vote). Thus, the tried-and-true concept of providing a receipt (ala ATM machines) is not a workable solution.

My intent in making this post isn’t to discuss all the issues behind e-voting—that is well beyond the scope of a single posting, and is covered well many other places. My main goal is to give some wider circulation to Yvo’s statement. However, in light of the recent problem with certificate issuance, it is also worth noting that schemes requiring encryption to secure voting may have hidden vulnerabilities that could lead to compromise and/or failures in the future.   

In the end, it comes down to a tradeoff of risk/reward (as do all security choices): can we accurately quantify the risks with a particular approach, and are we willing to assume them? Do we have appropriate mechanisms to eliminate, mitigate or shift the risks? Are we willing to accept the risks associated with adopting a particular form of e-voting in return for the potential benefit of better access for remote voters? Or are accurate (fair) results all the time more important than complete results?

Note that one objection often raised to USACM as we argue these points is “There is no evidence there has ever been a failure or tampering with a vote.” In addition to being incorrect (there are numerous cases of computer-based voting failures), this misses two key issues:

 
• How do you tell if there is tampering if there are no safeguards that definitively disclose such tampering? That you have not detected something does not mean it has not occurred.
 
• The past does not predict the future in such a case. That no failure (accidental or otherwise) has occurred does not mean it will not occur in the future. Worse, a string of occurrences without a failure may help cloud a future discovered discrepancy!

In the case of IACR, it is obvious why this group of cryptography professionals would wish to adopt techniques that show confidence in cryptography. However, the example they set could be very damaging for other groups—and populations—if their confidence is misplaced. Given the long history of spectacular failures in cryptography—often going unannounced while being exploited—it is somewhat surprising that the IACR is not more explicit in their statement about the risks of technological failures.

Yesterday, I posted a long entry on the recent news about how some researchers obtained a “rogue” certificate from one of the Internet Certificate Authorities. There are some points I missed in the original post that should be noted.

 
• The authors of the exploit have a very readable, interesting description of what they did and why it worked. I should have included a link to it in the original posting, but forgot to edit it in. The interested reader should definitely see that article online, include the animations.
 
• There are other ways this attack can be defeated, certainly, but they are stop-gap measures. I didn’t explain them because I don’t view them as other than quick patches. However, if you are forced to continue to use MD5 and you issue certificates, then it is important to randomize the certificate serial number that is issued, and to insert a random delay interval in the validity time field. Both will introduce enough random bits so as to make this particular attack against the CA infeasible given current technology.
 
• I suggested that vendors use another hash algorithm, and have SHA-1 as an example. SHA-2 would be better, as SHA-1 has been shown to have a theoretical weakness similar to MD5, although it has proven more resistant to attack to date. Use of SHA-1 could possible result in a similar problem within a few years (or, as suggested in the final part of my post, within a few weeks if a breakthrough occurs). However, use of SHA-1 would be preferable to MD5!
 
• MD5 is not “broken” in a complete way. There are several properties of a message digest that are valuable, including collision resistance: that it is infeasible to end up with two inputs giving the same hash value. To the best of my knowledge, MD5 has only been shown to be susceptible to “weak collisions”—instances where the attacker can pick one or both inputs so as to produce identical hash values. The stronger form of preimage resistance, where there is an arbitrary hash output H and an attacker cannot form an input that also produces H, still holds for MD5. Thus, applications that depend on this property (including many signing applications and integrity tools) are apparently still okay.
 
• One of our recent PhD grads, William Speirs, worked on defining hash functions for his PhD dissertation. His dissertation, Dynamic Cryptographic Hash Functions, is available online for those interested in seeing it.

I want to reiterate that there are more fundamental issues of trust involved than what hash function is used. The whole nature of certificates is based around how much we trust the certificate authorities that issue the certificates, and the correctness of the software that verifies those certificates then shows us the results. If an authority is careless or rogue, then the certificates may be technically valid but not match our expectations for validity. If our local software (such as a WWW browser) incorrectly validates a certificate, or presents the results incorrectly, we may trust a certificate we shouldn’t. Even such mundane issues as having one’s system at the correct time/date can be important: the authors of this particular hack demonstrated that by backdating their rogue certificate.

My continuing message to the community is to not lose sight of those things we assume. Sometimes, changes in the world around us render those assumptions invalid, and everything built on them becomes open to question. If we forget those assumptions—and our chains of trust built on them—we will continue to be surprised by the outcomes.

That is perhaps fitting to state (again) on the last day of the year. Let me observe that as human beings we sometimes take things for granted in our lives. Spend a few moments today (and frequently, thereafter) to pause and think about the things in your life that you may be taking for granted: family, friends, love, health, and the wonder of the world around you. Then as is your wont, celebrate what you have.

Best wishes for a happy, prosperous, safe—and secure—2009.

[12/31/08 Addition]: Steve Bellovin has noted that transition to the SHA-2 hash algorithm in certificates (and other uses) would not be simple or quick. He has written a paper describing the difficulties and that paper is online.

[tags]obituary,cryptography,Bob Baldwin,kuang, CBW,crypt-breaker’s workbench[/tags]

I learned this week that the information security world lost another of our lights in 2007: Bob Baldwin. This may have been more generally known, but a few people I contacted were also surprised and saddened by the news.

His contributions to the field were wide-ranging. In addition to his published research results he also built tools that a generation of students and researchers found to be of great value. These included the Kuang tool for vulnerability analysis, which we included in the first edition of COPS, and the Crypt-Breaker’s Workbench (CBW), which is still in use.

What follows is (slightly edited) obituary sent to me by Bob’s wife, Anne. There was also an obituary in the fall 2007 issue of Cryptologia.

Robert W Baldwin

May 19, 1957- August 21, 2007

Robert W. Baldwin of Palo Alto passed away at home with his wife at his side on August 21, 2007. Bob was born in Newton, Massachusetts and graduated from Memorial High School in Madison, Wisconsin and Yorktown High School in Arlington, Virginia. He attended the Massachusetts Institute of Technology, where he received BS and MS degrees in Computer Science and Electrical Engineering in 1982 and a Ph.D. in Computer Science in 1987. A leading researcher and practitioner in computer security, Bob was employed by Oracle, Tandem Computers, and RSA Security before forming his own firm, PlusFive Consulting. His most recent contribution was the development of security engineering for digital theaters. Bob was fascinated with cryptology and made frequent contributions to Cryptologia as an author, reviewer, and mentor.

Bob was a loving and devoted husband and father who touched the hearts and minds of many. He is well remembered by his positive attitude and everlasting smile. Bob is survived by his wife, Anne Wilson, two step-children, Sean and Jennifer Wilson of Palo Alto and his two children, Leila and Elise Baldwin of Bellevue, Washington. He is also survived by his parents, Bob and Janice Baldwin of Madison, Wisconsin; his siblings: Jean Grossman of Princeton, N.J., Richard Baldwin of Lausanne, Switzerland, and Nancy Kitsos of Wellesley, MA.; and six nieces and nephews.

In lieu of flowers, gifts in memory of Robert W. Baldwin may be made to a charity of the donor’s choice, to the Recht Brain Tumor Research Laboratory at Stanford Comprehensive Cancer Center, Office of Medical Development, 2700 Sand Hill Road, Menlo Park, CA 94025, Attn: Janice Flowers-Sonne, or to the loving caretakers at the Hospice of the Valley, 1510 E. Flower Street. Phoenix, AZ 85014-5656.

[tags]cryptography, information security, side-channel attacks, timing attacks,security architecture[/tags]
There is a history of researchers finding differential attacks against cryptography algorithms.  Timing and power attacks are two of the most commonly used, and they go back a very long time.  One of the older, “classic” examples in computing was the old Tenex password-on-a-page boundary attack. Many accounts of this can be found various places online such as here and here (page 25).  These are varieties of an attack known as side-channel attacks—they don’t attack the underlying algorithm but rather take advantage of some side-effect of the implementation to get the key.  A search of the WWW finds lots of pages describing these.

So, it isn’t necessarily a surprise to see a news report of a new such timing attack.  However, the article doesn’t really give much detail, nor does it necessarily make complete sense.  Putting branch prediction into chips is something that has been done for more than twenty years (at least), and results in a significant speed increase when done correctly.  It requires some care in cache design and corresponding compiler construction, but the overall benefit is significant.  The majority of code run on these chips has nothing to do with cryptography, so it isn’t a case of “Security has been sacrificed for the benefit of performance,” as Seifert is quoted as saying.  Rather, the problem is more that the underlying manipulation of cache and branch prediction is invisible to the software and programmer. Thus, there is no way to shut off those features or create adequate masking alternatives.  Of course, too many people who are writing security-critical software don’t understand the mapping of code to the underlying hardware so they might not shut off the prediction features even if they had a means to do so.

We’ll undoubtedly hear more details of the attack next year, when the researchers disclose what they have found.  However, this story should serve to simply reinforce two basic concepts of security: (1) strong encryption does not guarantee strong security; and (2) security architects need to understand—and have some control of—the implementation, from high level code to low level hardware.  Security is not collecting a bunch of point solutions together in a box…it is an engineering task that requires a system-oriented approach.
[posted with ecto]