In this paper we propose to consider the problem of robust perceptual hashing of multimedia data as composite hypothesis testing. Such a problem formulation is justified by prior ambiguity about source statistics and channel parameters that is usually the case in multiple practical scenarios. An asymptotically universal test approaching the performance of the classical maximum likelihood test performed under the exact knowledge of the mentioned statistics is proposed under the specific constraints on the assumed source and geometric channel models. Finally, we consider the problem of a practical hash construction under the constraints on complexity, robustness to geometrical transformations, universality and security. The proposed solution is based on a binary hypothesis testing for randomly or semantically selected blocks or regions in sequences or images.