I attended this year’s MRMCD in Darmstadt, Germany. I attended a few times in the past and I think this year’s edition was not as successful as the last ones. The venue changed this year, what probably contributed to some more chaos than usual and hence things not running as smoothly as they did. I assume it will be better next year, when people know how to operate the venue. Although all tickets were sold during the presale phase, it felt smaller than in the last years. In fairness, though, the venue was also bigger this year. The schedule had some interesting talks, but I didn’t really get around to attend many, because I was busy preparing my own shows (yeah, should’ve done that before…).
I had two talks at this conference. The first was on playing the children’s game “battleship” securely (video). That means with cryptography. Lennart and I explained how concepts such as commitment schemes, zero knowledge proofs of knowledge, oblivious transfer, secure multiparty computation and Yao’s protocol can be used to play that game without a trusted third party. The problem, in short, is to a) make sure that the other party’s ships are placed correctly and b) to make sure the other party answers correctly. Of course, if you get hold of the placements of the ships these problems are trivial. But your opponent doesn’t like you to know about the placements. Then a trusted third party would solve that problem trivially. But let’s assume we don’t have such a party. Also, we want to decentralise things, so let’s come up with a solution that involves two players only.
The second problem can be solved with a commitment. A commitment is a statement about a something you’ve chosen but that doesn’t reveal the choice itself nor allows for changing ones mind later. Think of a letter in a closed envelope that you hand over. The receiver doesn’t know what’s written in the letter and the sender cannot change the content anymore. Once the receiver is curious, they can open the envelope. This analogy isn’t the best and I’m sure there’s better real-world concepts to compare to commitment schemes. Anyway, for battleship, you can make the other party commit to the placement of the ships. Then, when the battle starts, you have the other party open the commitment for the field that you’re shooting. You can easily check whether the commitment verifies correctly in order to determine whether you hit a ship or water.
The other problem is the correct placement of the ships, e.g. no ships shall be adjacent, exactly ten ships, exactly one five-field ship, etc. You could easily wait until the end of the game and then check whether everything was placed correctly. But that wouldn’t be (cryptographic) fun. Let’s assume one round of shooting is expensive and you want to make sure to only engage if the other party indeed follows the rules. Now it’s getting a bit crazy, because we need to perform a calculation without learning anything else than “the ships are correctly placed”. That’s a classic zero knowledge problem. And I think it’s best explained with the magic door in a cave.
Even worse, we need to somehow make sure that we cannot change our placement afterwards. There is a brain melting concept of secure multi-party computation which allows you to do exactly that. You can execute a function without knowing what you’re doing. Crazy. I won’t be able to explain how it works in a single blog post and I also don’t intend to, because others are much better in doing that than I could ever be. The gist of the protocol is, that you model your functionality as a Boolean circuit and assign random values to represent “0” or “1” for each wire. You then build the truth table for each gate and replace the values of the table (zeros and ones) with an encryption under both the random value for the first input wire and the random value for the second input wire. The idea now is that the evaluator can only decrypt one value in the truth table given the input keys. There are many more details to care about but eventually you have a series of encrypted, or garbled, gates and you need the relevant keys in order to evaluate it. You can’t tell from the keys you get whether it represents a “0” or a “1”. Hence you can evaluate without knowing the other party’s input.
My other talk was about a probable successor of Return Oriented Programming: Data Oriented Programming (video). In Return Oriented Programming (ROP) and its variants like JOP the aim is to diverge the original control flow in order to make the program execute the attacker’s functionality. This, however, can probably be thwarted by Control Flow Integrity. In its simplest form, it checks on every branch whether it is legit. Think of a database with a list of addresses which are allowed to a list of other addresses. Of course, real-world implementations are more clever. Anyway, let’s assume that we’ll have a hard time exploiting our target with ROP, because we cannot change the CFG of the program. If our attack doesn’t change the CFG, though, we should be safe for anything that detects its modification. That’s the central idea of DOP.
Although I’m not super excited about this year’s edition, I’m looking forward to seeing the next year’s event. I hope it’s going to be a bit more organised; including myself 😉
