Cryptographic Reverse Firewalls

Since Edward Snowden informed us our internet traffic is under constant surveillance and that the US government has likely backdoored a standardised algorithm, threat models in provable security have evolved to consider an adversary within the user's machine. One of the first works addressing this was the substitution attack model of Bellare, Paterson and Rogaway that considered an adversary trying to corrupt an implementation to reveal a secret undetected by the user. A potential attack vector identified here was to use the randomness involved in operations to leak information while still appearing to be an honest implementation.

Today's study group continued in this area, taking a look at Mironov and Stephens-Davidowitz's paper on cryptographic reverse firewalls. While a traditional firewall sits between your machine and the network deciding what traffic gets through to you, protecting you from an outside threat, a cryptographic reverse firewall sanitises your incoming and outgoing traffic to prevent you from your own machine's misbehaviour. A reverse firewall does not need to know Alice's secret keys and so can be run by anyone, and in addition can be "stacked" so Alice can hedge her bets with multiple reverse firewalls in place at a time.

The desired properties of a reverse firewall are as follows.

1. Maintains functionality - If a protocol is implemented correctly then when the firewall is in place it should continue to provide the same functionality.
2. Preserves security - If a protocol provides a security guarantee then it should continue to do so when the firewall is in place.
3. Resists exfiltration - The firewall should prevent a tampered implementation leaking information to the outside world. This is modelled strongly by asking that an adversary cannot tell the difference between a tampered and an honest implementation behind the firewall.

The original paper goes on to consider reverse firewalls for multi-party computation, but we looked at the simpler case of signature schemes as studied by Ateniese, Magri and Venturi. For signature schemes maintaining functionality is straightforward to define - honestly generated signatures modified by the firewall should still verify.

Preserving security is slightly more complicated since the natural model of asking the adversary to forge a signature with access to a normal signing oracle and to an oracle that executes tampered signing algorithms of his choice then processes the output through the firewall admits a generic attack. To launch this attack the adversary submits a tampered signing algorithm that iterates over the bits of the secret key, returning an honest signature when the bit is 1 and a string of zeroes when the bit is 0, eventually recovering the secret key. To avoid this attack the firewall is allowed to output a special symbol that renders the oracle useless from that point on. This can be seen as the tampered implementation being detected and shut down.

Resisting exfiltration for signature schemes is impossible if arbitrary tampering is allowed, since for example the tampered algorithm can output a string of zeroes which the firewall has no way of turning into something indistinguishable from a valid signature.

As mentioned before a potential conduit for leaking information is the randomness used in an algorithm. The functionality maintaining and security preserving firewall given for signature schemes meeting a re-randomisability condition prevents such attacks by re-randomising valid signatures and returning the special symbol when given a signature that fails to verify.