4 ms·

His insight that crypto is hard because you don't get feedback when you mess up is good. It made me wonder what other domains are like that -- domains where co

His insight that crypto is hard because you don't get feedback when you mess up is good. It made me wonder what other domains are like that -- domains where correctness seems within reach, yet there are subtle aspects that are hard to state. Some that come to mind: * Concurrency. It's easy to introduce race conditions, livelocks, or deadlocks without even knowing. They are often difficult to observe or reproduce, and it takes a lot of hard-won experience to become sufficiently critical of your own incompetence. On the other hand, the tools are improving here (helgrind, relacy, threadsanitizer). * Exception-safety. I don't mean in the weak sense of "won't leak resources" but in the stronger sense of leaving the system in a consistent state after an exception. Again, it's difficult to analyze or induce all the different code paths that might occur, and difficult or expensive (depending on your starting point) to roll back your mutations. Again, there are tools that help with this, like STM or cheap persistent data structures (so you can do a bunch of mutation that is only committed atomically at the end). Are there others? Can the progress in these domains shed light on how to make crypto safer?

LaGrange 13y ago
Outside of computing: health and diet. Sure, you get some feedback, but you also can screw up things in some ridiculously slow-acting way. Pharma companies (are supposed to) monitor drug use for decades after introduction for the same reason. Construction. Just build that chunk out of two steel beams instead of one, and witness it work perfectly until someone decides to throw a party on that balcony. Or witness your construction slowly turn itself from a perfectly normal tower to a major tourist attraction over the centuries. Parenting. Things like sudden stimuli in early life have been linked to ADD, the way you do attachment can have tremendous consequences, and sometimes singular events you barely have any control over can have unpredictable consequences later in your life. In fact, I'm tempted to say "life in general".
- jiggy2011 13y ago
  Economics is also an excellent example. Nobody knows how to do it properly, even establishing direct cause and effect is basically impossible so we just iterate through progressively less broken solutions.
  - BrainInAJar 13y ago
    > so we just iterate through progressively less broken solutions. And then get all ideological about it and iterate back to more broken solutions (Chicago school)
    - jiggy2011 13y ago
      I wouldn't necessarily call Chicago school broken in it's entirety. I guess the whole idea that there are differing "schools" is probably an indicator in itself though.
    - mindcrime 13y ago
      And then get all ideological about it and iterate back to more broken solutions (Chicago school) Or, even worse, Keynesianism.
  - LaGrange 13y ago
    "progressively less broken solutions" Now that's a controversial statement if I've ever seen one.
- darkarmani 13y ago
  > health and diet. Sure, you get some feedback, but you also can screw up things in some ridiculously slow-acting way. This makes me think of the primal diet and coconut oil (saturated fat). The current arguments are that good saturated fats don't cause heart disease but (roughly) sugar does.
pcwalton 13y ago
Memory safety in memory-unsafe languages. We've had Valgrind and ASan for a while, and people still find crippling bugs in C and C++ code all the time. XSS vulnerabilities. Maybe Content Security Policy will help some here when it becomes ubiquitously available. Integer overflow. This is a particularly insidious problem because your well-formed test cases often won't catch it.
- jimmaswell 13y ago
  Here's a gem from an attempt to fix an integer overflow vulnerability in the PHP compiler: if (size > INT_MAX) return NULL; http://use.perl.org/use.perl.org/_Aristotle/journal/33448.html http://use.perl.org/use.perl.org/_Aristotle/journal/33448.ht...
Strilanc 13y ago
- Relying on undefined or implementation-specified behavior. Problems only show up years down the road. (example issue: expecting signed overflow to wraparound in C) - Avoiding statistical biases when transforming random values. Statistical unit tests are hard. (example issue: shuffling via lots of uniformly random swaps) - Integer overflow ruining algorithms that would be correct, given unbounded integers. (example issue: average = (a+b)/2)
- Estragon 13y ago
  Regarding statistical biases, you can always pipe expected distributions through the test and compare to the expected transformed distribution using chi-squared.
scythe 13y ago
The biggest candidate: * Pure mathematics: Consider e.g. the difficulty in verifying the recent proofs of Fermat's Last Theorem (Wiles-Taylor-Frey theorem?), the Poincaré conjecture (Perelman-Hamilton-Thurston theorem?), and now the ABC conjecture (Mochizuki-Szpiro theorem?): there is essentially no indication of the correctness of a mathematical proof besides simply having a whole lot of smart people look at it and think very hard. This may be of particular interest because pure math has lately experienced a turn towards the use of proof-verifying systems, and so it may be of some interest if one of these can be designed for cryptography. In particular, consider the following method of verification: a cryptographically secure function h(M, k), known or at least believed to be hard, a message M, a secret key k, and a channel C(h) over which data is transmitted. We wish to prove the following combination of statements: a: given C and h, a method to obtain the message M also obtains the key k, and b: given M, C, and h, it is "impossible" to obtain the key k -- i.e. it would require breaking the hash function; this means that if the cryptography is broken, so must be the hash function. The latter portion of the proof is necessary because we must always consider the possibility of a rubber hose or a stupid user. EDIT: I should add here that side channel attacks depend on an incorrect understanding of the content of C. So perhaps we should include c: we send only what we wish to in C. In the interest of pedantry, I dreamed up an example "cryptosystem" which may fit the bill, though I have no honest idea of the difficulty of the h function [and I know almost nothing about cryptography!]: consider a large prime number p, the finite field F_p, and its algebraic closure Fbar_p. A message M is a [presumaly long] polynomial M(x) over Fbar_p, and a key consists of the pair k = [p, z], where z is some arbitrary element of Fbar_p. h(M, k) is obtained by expanding (x - z) * M(x) in Fbar_p, and we send over C the coefficients of the resulting polynomial. Verification is obtained by computing C(z) in Fbar_p and the message is extracted by polynomial division. Then (a) rests on the difficulty of factoring a polynomial and (b) rests on the secrecy of p: so we cannot, for example, simply compute C/M. Note that Fbar_p is countable, so the whole procedure uses only integer math.
- anonymouz 13y ago
  If I understood your proposed system correctly, the following seems to be a deal-breaking weakness: Given a number of polynomials representing encrypted messages, (x-z) is a common factor of all of them. The GCD of a set of polynomials can very efficiently be computed. Thus, an attacker observing different messages encrypted with the same key over time gets a better and better idea of what the key is (how quickly depends on the messages: two plaintext messages that happen to give coprime polynomials M_1(x) and M_2(x) would be enough to get the key).
agwa 13y ago
Along the lines of of your examples, I would add distributed systems. Still, cryptography is much, much worse than all these examples for a simple reason: with a sufficient amount of testing for functionality you can convince yourself that you've gotten things like concurrency correct, or at least correct enough that it won't be a problem most of the time. You can't do that with security - instead of testing for functionality you have to test for attack resilience, but whereas you know what functionality to test for, you can't test for attacks you don't know about. Furthermore, you can't be correct merely most of the time - you have to be correct all of the time, because if you slip up just once, your adversary will exploit you. I really don't think there's any parallel.
- AlexDanger 13y ago
  Rumsfeld sums up the problem rather succinctly: http://www.brainyquote.com/quotes/quotes/d/donaldrums148142.html http://www.brainyquote.com/quotes/quotes/d/donaldrums148142.... I think Netflix and its Chaos Monkey software is a very effective way of dealing with the 'unknown unknowns' of distributed systems. Although obviously this approach doesnt work with cryptography systems. They call it Chaos Monkey (opposed to Genius Monkey) for a reason.
ramblerman 13y ago
"Thinking Fast and Slow" tackles this issue. Doctors who asses xray fotos for cancer usually get feedback ~6 months later. What's worse is they become more confident in their abilities as they age, and subsequently diverge from the standard checklists inexperienced doctors follow. This leads to even worse results from doctors with 10-15 years of experience. The opposite case is surgeons who gain immediate feedback and generally become better with experience.

LaGrange 13y ago

Outside of computing: health and diet. Sure, you get some feedback, but you also can screw up things in some ridiculously slow-acting way. Pharma companies (are supposed to) monitor drug use for decades after introduction for the same reason. Construction. Just build that chunk out of two steel beams instead of one, and witness it work perfectly until someone decides to throw a party on that balcony. Or witness your construction slowly turn itself from a perfectly normal tower to a major tourist attraction over the centuries. Parenting. Things like sudden stimuli in early life have been linked to ADD, the way you do attachment can have tremendous consequences, and sometimes singular events you barely have any control over can have unpredictable consequences later in your life. In fact, I'm tempted to say "life in general".

jiggy2011 13y ago
Economics is also an excellent example. Nobody knows how to do it properly, even establishing direct cause and effect is basically impossible so we just iterate through progressively less broken solutions.
- BrainInAJar 13y ago
  > so we just iterate through progressively less broken solutions. And then get all ideological about it and iterate back to more broken solutions (Chicago school)
  - jiggy2011 13y ago
    I wouldn't necessarily call Chicago school broken in it's entirety. I guess the whole idea that there are differing "schools" is probably an indicator in itself though.
  - mindcrime 13y ago
    And then get all ideological about it and iterate back to more broken solutions (Chicago school) Or, even worse, Keynesianism.
- LaGrange 13y ago
  "progressively less broken solutions" Now that's a controversial statement if I've ever seen one.
darkarmani 13y ago
> health and diet. Sure, you get some feedback, but you also can screw up things in some ridiculously slow-acting way. This makes me think of the primal diet and coconut oil (saturated fat). The current arguments are that good saturated fats don't cause heart disease but (roughly) sugar does.

pcwalton 13y ago

Memory safety in memory-unsafe languages. We've had Valgrind and ASan for a while, and people still find crippling bugs in C and C++ code all the time. XSS vulnerabilities. Maybe Content Security Policy will help some here when it becomes ubiquitously available. Integer overflow. This is a particularly insidious problem because your well-formed test cases often won't catch it.

jimmaswell 13y ago
Here's a gem from an attempt to fix an integer overflow vulnerability in the PHP compiler: if (size > INT_MAX) return NULL; http://use.perl.org/use.perl.org/_Aristotle/journal/33448.html http://use.perl.org/use.perl.org/_Aristotle/journal/33448.ht...

Strilanc 13y ago

- Relying on undefined or implementation-specified behavior. Problems only show up years down the road. (example issue: expecting signed overflow to wraparound in C) - Avoiding statistical biases when transforming random values. Statistical unit tests are hard. (example issue: shuffling via lots of uniformly random swaps) - Integer overflow ruining algorithms that would be correct, given unbounded integers. (example issue: average = (a+b)/2)

Estragon 13y ago
Regarding statistical biases, you can always pipe expected distributions through the test and compare to the expected transformed distribution using chi-squared.

scythe 13y ago

The biggest candidate: * Pure mathematics: Consider e.g. the difficulty in verifying the recent proofs of Fermat's Last Theorem (Wiles-Taylor-Frey theorem?), the Poincaré conjecture (Perelman-Hamilton-Thurston theorem?), and now the ABC conjecture (Mochizuki-Szpiro theorem?): there is essentially no indication of the correctness of a mathematical proof besides simply having a whole lot of smart people look at it and think very hard. This may be of particular interest because pure math has lately experienced a turn towards the use of proof-verifying systems, and so it may be of some interest if one of these can be designed for cryptography. In particular, consider the following method of verification: a cryptographically secure function h(M, k), known or at least believed to be hard, a message M, a secret key k, and a channel C(h) over which data is transmitted. We wish to prove the following combination of statements: a: given C and h, a method to obtain the message M also obtains the key k, and b: given M, C, and h, it is "impossible" to obtain the key k -- i.e. it would require breaking the hash function; this means that if the cryptography is broken, so must be the hash function. The latter portion of the proof is necessary because we must always consider the possibility of a rubber hose or a stupid user. EDIT: I should add here that side channel attacks depend on an incorrect understanding of the content of C. So perhaps we should include c: we send only what we wish to in C. In the interest of pedantry, I dreamed up an example "cryptosystem" which may fit the bill, though I have no honest idea of the difficulty of the h function [and I know almost nothing about cryptography!]: consider a large prime number p, the finite field F_p, and its algebraic closure Fbar_p. A message M is a [presumaly long] polynomial M(x) over Fbar_p, and a key consists of the pair k = [p, z], where z is some arbitrary element of Fbar_p. h(M, k) is obtained by expanding (x - z) * M(x) in Fbar_p, and we send over C the coefficients of the resulting polynomial. Verification is obtained by computing C(z) in Fbar_p and the message is extracted by polynomial division. Then (a) rests on the difficulty of factoring a polynomial and (b) rests on the secrecy of p: so we cannot, for example, simply compute C/M. Note that Fbar_p is countable, so the whole procedure uses only integer math.

anonymouz 13y ago
If I understood your proposed system correctly, the following seems to be a deal-breaking weakness: Given a number of polynomials representing encrypted messages, (x-z) is a common factor of all of them. The GCD of a set of polynomials can very efficiently be computed. Thus, an attacker observing different messages encrypted with the same key over time gets a better and better idea of what the key is (how quickly depends on the messages: two plaintext messages that happen to give coprime polynomials M_1(x) and M_2(x) would be enough to get the key).

agwa 13y ago

Along the lines of of your examples, I would add distributed systems. Still, cryptography is much, much worse than all these examples for a simple reason: with a sufficient amount of testing for functionality you can convince yourself that you've gotten things like concurrency correct, or at least correct enough that it won't be a problem most of the time. You can't do that with security - instead of testing for functionality you have to test for attack resilience, but whereas you know what functionality to test for, you can't test for attacks you don't know about. Furthermore, you can't be correct merely most of the time - you have to be correct all of the time, because if you slip up just once, your adversary will exploit you. I really don't think there's any parallel.

AlexDanger 13y ago
Rumsfeld sums up the problem rather succinctly: http://www.brainyquote.com/quotes/quotes/d/donaldrums148142.html http://www.brainyquote.com/quotes/quotes/d/donaldrums148142.... I think Netflix and its Chaos Monkey software is a very effective way of dealing with the 'unknown unknowns' of distributed systems. Although obviously this approach doesnt work with cryptography systems. They call it Chaos Monkey (opposed to Genius Monkey) for a reason.

ramblerman 13y ago

"Thinking Fast and Slow" tackles this issue. Doctors who asses xray fotos for cancer usually get feedback ~6 months later. What's worse is they become more confident in their abilities as they age, and subsequently diverge from the standard checklists inexperienced doctors follow. This leads to even worse results from doctors with 10-15 years of experience. The opposite case is surgeons who gain immediate feedback and generally become better with experience.