This paper introduces an identification framework for random microstructures of material surfaces. These microstructures represent a kind of unique fingerprints that can be used to track and trace an item as well as for anti-counterfeiting. We first consider the architecture for mobile phone-based item identification and then introduce a practical identification algorithm enabling fast searching in large databases. The proposed algorithm is based on reference list decoding. The link to digital communications and robust perceptual hashing is shown. We consider a practical construction of reference list decoding, which comprizes computational complexity, security, memory storage and performance requirements. The efficiency of the proposed algorithm is demonstrated on experimental data obtained from natural paper surfaces.