The astonishing spread of Android OS, not only in smartphones and tablets but also in IoT devices, makes this operating system a very tempting target for malware threats. Indeed, the latter are expanding at a similar rate. In this respect, malware fingerprints, whether based on cryptographic or fuzzy-hashing, are the first defense line against such attacks. Fuzzy-hashing fingerprints are suitable for capturing malware static features. Moreover, they are more resilient to small changes in the actual static content of malware files. On the other hand, dynamic analysis is another technique for malware detection that uses emulation environments to extract behavioral features of Android malware. However, to the best of our knowledge, there is no such fingerprinting technique that leverages dynamic analysis and would act as the first defense against Android malware attacks. In this paper, we address the following question: could we generate effective fingerprints for Android malware through dynamic analysis? To this end, we propose DySign, a novel technique for fingerprinting Android malware's dynamic behaviors. This is achieved through the generation of a digest from the dynamic analysis of a malware sample on existing known malware. It is important to mention that: (i) DySign fingerprints are approximated of the observed behaviors during dynamic analysis so as to achieve resiliency to small changes in the behaviors of future malware variants; (ii) Fingerprint computation is agnostic to the analyzed malware sample or family. DySign leverages state-of-the-art Natural Language Processing (NLP) techniques to generate the aforementioned fingerprints, which are then leveraged to build an enhanced Android malware detection system with family attribution.