Generalized key substitution attacks on message recovery signatures

Abstract

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.