## Monday, September 17, 2012

### A crypto grab-bag

A bunch of otherwise unrelated stuff, with the common thread(s) that: they're interesting stories, and they have to do with cryptography of various sorts.

• Professor Ed Felten talks about the need for government-enforced security algorithms to be accountable: Accountable Algorithms
When we talk about making an algorithmic public process open, we mean two separate things. First, we want transparency: the public knows what the algorithm is. Second, we want the execution of the algorithm to be accountable: the public can check to make sure that the algorithm was executed correctly in a particular case. Transparency is addressed by traditional open government principles; but accountability is different.
Felten follows up that first essay with an example: Accountable Algorithms: An Example
you can verify that the TSA followed the algorithm correctly in deciding whether to search you. You can add the now-public R to the already-public Q, to get the day’s (previously) secret key K. You can then evaluate the selection function S(K,N) with your name N–replicating the computation that the TSA did in deciding whether to search you. If the result you get matches the result the TSA announced earlier, then you know that the TSA did their job correctly.
• In a somewhat similar vein, Ben Laurie talks about transparency and auditability of Certificate Revocation: Revocation Transparency and Sovereign Keys.
This document does not attempt to answer all questions about revocation, such as who can revoke and under what circumstances. It provides a mechanism for transparency: i.e. the ability to know, efficiently, that the list of revoked certificates you see is the same as the list everyone else sees, and that every revocation (or unrevocation) is available for scrutiny by any interested party.
• Professor Dick Lipton tells a nice story about his reaction upon reading about Mochizuki's work on the ABC conjecture: The ABC Conjecture And Cryptography
Everything changes when we ask questions that talk about the interplay between addition and multiplication. The first-order theory is undecidable and incomplete. There are countless simple-to-state questions that mix the two structures—addition and multiplication—that are beyond our current abilities. A simple example of this is the Twin Prime Conjecture: Are there an infinite number of primes p so that p + 2 is also prime? Note how it mixes primality (which depends on multiplication) with addition.

This is also the reason that the ABC Conjecture is so deep. It mixes in a critical way the additive structure a + b = c with the multiplicative structure, the radical of abc. This mixture is at the core of why the question is so deep.

When I win the lottery, I'll go buy a copy of Serge Lang's Math Talks for Undergraduates; it looks like a fine book.
• The guys over at Spider Labs have been digging into CryptOMG, and have published the first article in an intended series: CryptOMG Walkthrough - Challenge 1
Decoding just gives us garbage but taking a closer look at it, the length of the data is divisible by 8, so its worth treating this as some kind of ciphertext. The next step is to alter the data and see if we can get the application to spit out some useful errors.
• At the Throwing Fire weblog, Patrick Mylund Nielsen points out that the interesting new Art Of The Problem website is featuring a video series on cryptography, and that the videos are quite good: Gambling with Secrets: an Introduction to Cryptography
• Adam Shostack reflects on 15 years of BlackHat: Smashing the Future for Fun and Profit
I’m excited to have be a part of a discussion with others who spoke at the first Blackhat: Bruce Schneier, Marcus Ranum, Jeff Moss, and Jennifer Granick. We’ve been asked to think about what the future holds, and to take lessons from the last 15 years.
• And lastly, two nice pieces on the 20th anniversary of the movie Sneakers. First, actor Stephen Toblowsky reminisces about playing Werner Brandes: Memories of the Sneakers Shoot: I can’t remember ever having so much fun on a movie.
The script, written by Phil Alden Robinson, Larry Lasker, and Walter Parkes, is a wonder of the modern screenwriting world. It survives by wit and not tricks. It’s a caper movie that transcends the genre. It’s a technology movie that still isn’t outdated even though it was released 20 years ago and features cradle modems.
And Professor Len Adleman reminisces about his role as the mathematics consultant for the movie: Sneakers
He told me that there would be a scene wherein a researcher would lecture on his mathematical work regarding a breakthrough in factoring - and hence in cryptography. Larry asked if I would prepare the slides and words for that scene. I liked Larry and his desire for verisimilitude, so I agreed. Larry offered money, but I countered with Robert Redford - I would do the scene if my wife Lori could meet Redford.