How to break fraud-detectable key recovery

Fraud detection for software key recovery schemes means that, without knowing the session key, a third party can verify whether the correct session key could be recovered. This concept and a construction by so-called binding data was introduced by Verheul et al. at Eurocrypt '97 to provide for dishonest users that make simple modifications to messages, e.g., delete the key recovery information, and manipulate the recipient's software such that it decrypts messages even if the key recovery information is incorrect.We show how to break their general construction within their model, in particular without using any other encryption system or any pre-established shared secrets.We conclude that the concept of binding data does not improve the security of software key recovery but illustrates once more its fundamental problem: it does not improve an authorized third party's ability to eavesdrop on serious criminals.