THC-Shagg - A modular application to bruteforce check digit algorithms --------------------------------------------------------------------- (c) 2001, 2003 Plasmoid , The Hacker's Choice, o Introduction Our modern world is full of serial numbers that represent important parts of our daily life, credit card numbers, social id numbers, calling card numbers, shopping cards, ISBN numbers, ... These numbers have two things in common: - They contain information inside the number in opposite to serial numbers used in software industry that are often only a cryptographic fingerprint of the customers data and are designed for authentication only. - They contain a check digit, generated using a check digit algorithm. A check digit is not meant as a cryptographic fingerprint or designed to be hard to crack, instead it allows easy verification of the numbers and especially detects most simple typos. Analyzing the information that are stored in such a serial number is hard because a lot of background knowledge is necessary. Finding the corresponding check digit algorithm and the position of the check digit inside such a serial number is simple, since there is THC-Shagg. o How it works A check digit algorithm uses the digits of a serial number to construct a check digit, it is not necessary that the digits are numeric values, they can be extended to alpha-numeric values. THC-Shagg currently implements the following algorithms: Full name Internal name -------------------------------- ---------------- binary Modulus 7 DR Modulus 7 binary Modulus 9 DR Modulus 9 weighted Modulus 10 DR Modulus 10 Basic weighted Modulus 10 Luhn Modulus 10 Luhn weighted Modulus 10 IBM Modulus 10 CC weighted Modulus 11 DSR Modulus 11 Future releases will implement more algorithms. To get a list of all available algorithms use the -A. For simplicity this version mixes binary and weighted algorithms, DR and DSR algorithms, future version of THC-Shagg may include separate options for binary, weighted, DR and DSR algorithms. As this is the first release, only the most common algorithms have been implemented. For details on the concept of each algorithms consult the source code of THC-Shagg or browse the web, there are some good information covering these algorithms. Most of the algorithms above operate using so called weights. Weights are just a sequence of numbers that are multiplied with the individual digits of the serial number to be checked. THC-Shagg generates all weights up to a specified length and checks the serial numbers against all of these weight using all algorithms. Example: All weights up to length 3 1,2,3,4,5,6,7,8,9, 01,02,03,04,05,06,07,08,09,10,...99 001,002,003,004,005,006,007,...999 THC-Shagg ignores all weights that only consist of zeros because they result in fault-positives and are not used in check digit algorithms. In order to find the position of a check digit, THC-Shagg splits the serial numbers into partitions. A partition has a head and a tail, these parts are ignored during analysis of the serial numbers. THC-Shagg generates all partitions up to a specified minimum length where length is the length of the part to be analyzed. The programs checks the serial number against these partitions using weights and algorithms. Example: All partition limited to length 2 for a number of length 5 (0,5,0), (2,3,0), (3,2,0), (0,3,2), (0,2,3) ^ ^ ^ | | | +------ length head +---- length of number to check +-- length of tail As you can imagine there exists a lot of combination for a set of serial numbers that are checked against all weights, algorithms and partitions. THC-Shagg stores each combination in a data type that is called "state". A state includes an algorithm, specific weights and a partition. During analysis THC-Shagg collects all states that return positive results on a serial numbers. This collecting is done using a fast data structure that allows O(log n) insertion/searching. After checking all serial numbers, the set of collected states is cleared by removing all states that don't match all serial numbers (You can add failure tolerance to THC-Shagg by using the -f option.) Finally THC-Shagg outputs the states that match all serial numbers and stores them in a file. The user is now able to generate similar serial numbers using this saved file. If you don't have enough serial numbers THC-Shagg will not be able to determine one state but find a lot of states, in this case the information given are not exact enough, try adding more serial numbers, or decrease the partition length and/or weights length. The current version of THC-Shagg has been successfully launched against the following concrete check digit algorithms and was able to detect the weights and partitions. After analysis THC-Shagg was able to generate new numbers for all of these algorithms: - International Standard Book Number (ISBN) - VISA and MasterCard credit card numbers - Electronic Funds Transfer (EFT) routing numbers - Universal Product Code (UPC) - Serial Shipping Container Code (SSCC) - European Article Numbering (EAN) UCC-8, UCC-12, UCC-13, UCC-14 - International Mobile Equipment Identity (IMEI) numbers o Usage THC-Shagg is Java application therefore you need at least the Java Runtime Environment to run THC-Shagg. For more information on Java installation and configuration consult http://java.sun.com. Since THC-Shagg is placed in a JAR Archive it is executed the following way if the Java binary is in your path. $ java -jar shagg.jar THC-Shagg expects an input file that contains serial numbers, one per line. Any non-digit characters are ignored, so serial numbers containing "-" or "." are okay. Comments can be added to the serial numbers file by starting the comment with a "#" or ";" sign. In generation mode -g THC-Shagg expects an input file containing saved states. shagg [-ghqALRV] [-p ] [-w ] [-l ] [-i ] [-d ] [-c ] [-s ] [-n ] -p Minimum length of partitions. [7] This option sets the minimum length of partitions. The smaller this value is the more partitions are generated. Where the length of a partition is defined by the sequence between the head and the tail. -w Maximum length of weights. [3] THC-Shagg generates weights up to the specified length . Using values above 3 doesn't make much sense, because nobody has ever seen an check digit algorithm running with more than 3 weights, but who knows! If you want to go sure. -l Length of serial numbers. [auto] By default THC-Shagg automatically detects the length of the serial numbers. In case you have a large set of serial numbers and don't want to check them by hand, set this to the length the serial numbers should have. -i Number of serial numbers to ignore (tolerance). [0] By using this option you can add failure tolerance to THC-Shagg. In the final result serial numbers will be ignores. You can use this feature if you have the assumption that some serial numbers might be broken. -d Maximum number of states displayed. [20] By default 20 states are displayed, if more sates have been found THC-Shagg issues a warning stating that not enough information were provided to the program. -c Maximum number of states until clear forced. [100000] Collecting the states can be very memory expensive, if you are running above a large set of serial numbers, THC-Shagg calls an "emergency" clear if states have been collected. THC-Shagg will then remove all states that don't have enough hits and continue analyzing the serial numbers. -s Save matching states to filename. -h Print this help screen. -q Be quiet during analysis. -A Print implemented algorithms. This option prints all implemented algorithms, if you have retrieved a new version of THC-Shagg, use this feature to find out which new algorithms have been implemented. -R Print included README file to STDOUT. -V Print version, license and copyright information. -g Generation mode, create serial numbers from states in Create serial numbers from a file of states that was saved using the -s option in non-generation mode. -n Number of serial numbers to generate. [10] -P

Prefix

for numbers to generate. [none] This options allows to set the prefix of the generated number, if prefix could be the bank's id or any other sequence of numbers. -L List loaded states. This option prints all states that are included in a states file. The option has to be used with the -g option. [] = Default values. o Examples THC-Shagg comes with some example inside the JAR archive and the source JAR archive. In order to learn more about how the bruteforce checks of THC-Shagg work, probing with the examples is recommended. Extract the JAR archive using the jar tool included in the Java distribution, e.g. $ jar -xf shagg.jar Change to the examples directory and try some the examples by running: $ java -jar shagg.jar examples/isbn.lst $ java -jar shagg.jar examples/fake-visa.lst The examples contain some comments, that help explaining what kind of serial numbers they contain. If you succeed with the above, try saving a states file generated from the analysis of another example. $ java -jar shagg.jar -s /tmp/saved-states examples/mod10-7.lst You have now successfully saved the states that represent the numbers in mod-seven.lst. You can list the states by typing $ java -jar shagg.jar -g -L /tmp/saved-states Now we want to generate 5 serial numbers from this file with the prefix 0123. $ java -jar shagg.jar -g -P 0123 -n 5 /tmp/saves-states If you want to do some sanity checks, pipe the generate serial numbers in a file and rerun the analysis on them. o Your Support The future development of THC-Shagg relies on your support. If you code more check digit algorithms, have criticism, ideas, interesting numbers, whatever, feel free to contact Plasmoid Don't request anything related to credit cards, Plasmoid is not your source for illegal activities. o Credits & Greets THC-Shagg has been developed by Plasmoid . Any ideas, improvements and especially newly implemented check digit algorithms can be send to him. So if you want to contribute some own check digit algorithms get the source package of THC-Shagg and implement them in Java using the provided interface "CheckDigitAlgorithm". Greets in no special order to Wilkins, Hendy, Van Hauser, Twonky, Skyper, Escher, Acpizer, Tick, Gamma, Scut and the great Segfault.net possee. o Appendix The Hacker's Choice Website http://www.thc.org The THC-Shagg Website http://www.thc.org/thc-shagg Plasmoid's PGP Key http://www.thc.org/keys/plasmoid.pub Some Check Digit Links http://www.augustana.ab.ca/~mohrj/algorithms/checkdigit.html http://www.pointil.com/resources/mod.htm