A number of comments from well-known researchers on information security and key escrow systems, i.e. D. Denning, C. Mitchell, Bruce Schneier, Dieter Gollmann and Tatsuaki Okamoto, have come to me since my article on "A serious problem for key escrow systems?" published in IEEE Cipher Electronic Issue #20. In the short paper here, a summary of these comments with my points is given, and I propose some possible solutions.
All of the comments think that the work in my article subverts key escrow systems. Prof. C. Mitchell said "whilst such a situation is not desirable, it is very difficult to avoid." In fact, unless their SK1 to SKn-1 are intercepted, the legal interceptors can do nothing to decrypt the message encrypted by SKn. Moreover, it is very hard for legal interceptors to keep always watching the communications of every possible criminals or active attackers.
What I pursue is solutions to the problem. "Some schemes have been designed which try and avoid this problem; however many have turned out to be flawed, and my belief is that, in the end, there is little one can do" writes Prof. Mitchell. My point is that one is unlikely to find a mathematical approach or protocol to completely avoid the attack. It seems that we can not see a simple and easy solution to avoid the attack.
However, the attack does not make key escrow useless. The key recovery function of key escrow systems is not degraded by the attack, and any lost key may still be recovered by key escrow schemes.
If a key escrow system is to prevent the casual use of public secure networks in a way which defeats legitimate interception, the attack does not really relate to this "casual use" scenario. However, if a key escrow system is applied to business/personal telephones or regular users on the Internet and Intranet, it will be subverted by the attack.
One of possible solutions is to increase the difficulty of changing and replacing key management systems in key escrow systems, and provide more protection mechanisms to key management systems.
A second possible solution is that key escrow agences and key distribution centers randomly change users' keys, and intercept and check messages between users, so that the attack can be found effectively in time and further protection can be done immediately.
A third possible solution is that there is a visible mark on the message encrypted using a legitimate key. The attack can be found when an illegitimate key has been used to encrypt a message.
To avoid the attack in user's level, Dr. D. Gollmann said "Users must not be allowed to do their own encryption, you have to rely on a trusted service provider to encrypt data and escrow keys. Taken to its full length, you have to police all traffic ( and all data held somewhere in memory) and check whether they are encrypted (or simply compressed, written in a language you don't understand, etc)".
The author would like to thank D. Denning, C. Mitchell, B. Schneier, D. Gollmann T. Okamoto and other researchers for their comments.