Generalized Key Substitution Attacks on Message Recovery Signatures

This paper treats effectiveness of the generalized key substitution attacks, and practical measures against them. The generalized key substitution attacks are proposed as a generalization of the key substitution attacks to examine the security of the signature schemes adopted in ISO/IEC (1st CD) 14888-3, which standardizes appendix-type signature schemes based on the discrete logarithm problem. This paper examines the message recovery signature schemes based on the discrete logarithm problem, adopted in ISO/IEC 9796-3:2006, and shows that all but one scheme are vulnerable to the generalized key substitution attacks.