To protect a sensitive dataset, standard industry practice employs data masking—also known as data obfuscation—techniques. These techniques preserve the look and feel of the data but render it useless to unauthorized parties—at least in theory. The question is: If we know only the format of the masked data, how much information can be leaked? To answer that question, we explore so-called re-identification attacks; that is, attacks in which (1) customer records are recovered from masked datasets, (2) customers are uniquely identified, and (3) customers’ sensitive data is exposed. Our approach utilizes anonymized statistical data from an industrial dataset, which includes attributes such as address, city, etc. For each attribute (e.g., city), we are given the set of unique formats (e.g., aaaaaa, axaa) as well as the frequencies of those formats (e.g., aaaaaa appears 22 times and axaa appears 13 times). In this work, we design and implement two algorithms which construct new custom datasets by assigning different formats (e.g., aaaaaa, axaa) to each attribute (e.g., city) for each customer. This process creates a range of datasets that could have produced the anonymized data, ensuring that the formats and frequencies match exactly. The generated datasets serve as our “victim” datasets, and they include the worst-case scenario for our “adversary” (i.e., the most challenging dataset to de-anonymize). Finally, we conduct re-identification attacks against the generated datasets. Our analysis shows that as we add more attributes (to narrow down the possibilities), a greater proportion of customers can be uniquely identified, even in the worst case. Furthermore, if we assume certain attributes are inherently independent (e.g., full name and city), our algorithms can closely estimate the real distributions of the frequencies, with the lower and upper bounds holding with high probability.