This post continues the series that I have started here.
Some months ago Dark Reverser published a python script that allows to strip the DRM encryption from a secure Mobipocket ebook. For legal reasons the source code has been removed from the webpage but it’s too late. The knowledge about the encryption algorithm is out and I think it’s time to have a look at its strength (or rather weakness)
MobiPocket uses the 128bit version of the Pukall (PC1) algorithm. The 128 bit key is calculated by using the device PID and a secret key (which is not secret anymore…). But that’s not all. As you know, the current format allows up to 4 different PIDs with which a book can be decrypted. Technically this problem is solved in a nice way. The final key, which is used to encrypt the book, is encrypted with the temp key generated with the PID. The result is stored in the DRM section of the book together with a simple checksum and a verification number. To find the working key, decrypt the data with the key that has been generated using the PID.
TempKey = (PID) encrypt with PC1 using (Secret Key) FinalKey = (FinalKeyEncrypted) decrypt with PC1 using (TempKey)
According to the Pukall author, the 128 bit key length should guarantee that the key cannot be hacked in a reasonable timeframe. This is true, however, the implementation in MobiPocket makes finding the PID much easier:
- The PID consists of 8 alphanumeric characters (A-Z, 0-9)
- Only upper-case letters are used.
- The 8th character is a $ for PIDs generated on the PC and * for the Amazon Kindle.
To brute-force all combinations, a program whould have to do only 1’838’317’255’040 tests (41 bit instead of 128 bit!). This still sounds much but one has to remember that the PC1 algorithm has been optimized for speed. On fast hardware I was able to do roughly 250’000 tests per second, which means that a single CPU would be busy for more than 85 days. Today it’s no problem to spread the load though, so if you have 16 cores available the tests would be finished in roughly 5 days, with 32 cores it would be a good 2.5 days.
But wait, it’s possible to speed up the test. The data, which holds the encrypted data, starts with the verification field (4 bytes). Instead of decrypting the whole 32 bytes, it’s enough to start with the first 4 bytes and check if the verification entry matches. By using this trick I was able to get 590’000 tests per second. It’s only 35 days of work for a single CPU now or, with access to 35 cores, roughly 1 day.
It looks like PIDs generated for the PC have a $ as last character. If this is true, the number of tests is 1/35th of the total combinations (36 bit)!
An encryption scheme that can be brute-forced in such a short time cannot be considered as strong. Theoretically the used algorithm is strong enough but the implementation fails to make use of it. By the way, if all 10 characters of the PID would have been used, the time required to test all combinations would increase by a factor of 1156 (46 bit) and make a brute-force attack impractical.