DRM and AZW files

[ixtab]

Ok, I may have been a little too pessimistic when speaking of millions of years.

Here's a little thought experiment. From all that I know, the Kindle devices use a 10-character alphanumeric code derived from the serial number of the Kindle. Assuming that only A-Z and 0-9 are valid characters (which is a wrong assumption, because some special characters may also appear), that leaves us with 36^10 = 3,656,158,440,062,976 possible keys.

Now for the sake of simplicity, assume that we can try 1,000,000 keys per second. To try every single key, that means we'd need 3656158440 seconds.

That is 1015600 hours, or 42317 days, or 116 years. If you have 116 computers, you can thus effectively search the entire key space within a year.

The good news is that on average, you'd expect to be done at about half the time. In the best case, you're done immediately, because the first key you try matches, and in the worst case, the very last key you try matches.

[geekmaster]

Originally Posted by ixtab

Ok, I may have been a little too pessimistic when speaking of millions of years.

Here's a little thought experiment. From all that I know, the Kindle devices use a 10-character alphanumeric code derived from the serial number of the Kindle. Assuming that only A-Z and 0-9 are valid characters (which is a wrong assumption, because some special characters may also appear), that leaves us with 36^10 = 3,656,158,440,062,976 possible keys.

Now for the sake of simplicity, assume that we can try 1,000,000 keys per second. To try every single key, that means we'd need 3656158440 seconds.

That is 1015600 hours, or 42317 days, or 116 years. If you have 116 computers, you can thus effectively search the entire key space within a year.

The good news is that on average, you'd expect to be done at about half the time. In the best case, you're done immediately, because the first key you try matches, and in the worst case, the very last key you try matches.

But good encryption such as AES is designed so that you CANNOT generate keys quickly. To search the 10-character (constrained) key space would require generating encryption keys (such as 128-bit AES which is a much larger keyspace) using a slow crypto hash function at a rate far less than 1,000,000 key pairs per second.

The real question is, does kindle ebook DRM use a good (slow) secure hash function for its key generation?

[ixtab]

Originally Posted by geekmaster

But good encryption such as AES is designed so that you CANNOT generate keys quickly. To search the 10-character (constrained) key space would require generating encryption keys (such as 128-bit AES which is a much larger keyspace) using a slow crypto hash function at a rate far less than 1,000,000 key pairs per second.

The real question is, does kindle ebook DRM use a good (slow) secure hash function for its key generation?

Hmm.. u sure? My 3 years old laptop can generate about 1.5M SHA-256 hashes per second...

Edit: I may have missed the point. I don't know how many decryption "attempts" are feasible per second, that could well be much less.

Edit2: some further reading: http://security.stackexchange.com/qu...mized-cray-xe6

[geekmaster]

We typically used PBKDF2 key generation when I worked on this stuff. It converts a text key (passphrase, or serial number in this case) into a larger 128-bit key. It is designed to run slowly to prevent exhaustive brute-forcing.

If you plan to search the raw keyspace without doing slow key generation, you have to search a much larger keyspace (128-bits) which would take a LONG time.

Slow key generation is WHY encryption (done well) is still secure. Even for rainbow tables, it took a LOT of CPU time to generate those tables. You can crack the raw keyspace quickly by using rainbow tables to lookup the key precursors for a quick and small raw keyspace subset search.

I am no encryption expert -- but that is how I understand it. It has been awhile, so I may not remember it all correctly...

P.S. You are talking about SLOWLY GENERATING 10 alphunumeric character keys, or quickly searching a HUGE 128-bit raw keyspace. Either way takes a lot of time...

EDIT: Again, I do not know how the kindle DRM does it. I suspect that generating keys for all possible kindle serial numbers would be very slow. Using a fast hash for key generation would be vulnerable to brute-forcing the much smaller serial-number space instead of the full 12-bit encryption keyspace, so it would be foolish to use a fast hash for DRM key generation. After you have the right key, decryption is fast. But FINDING the right key is slow, which is why you need to know the serial number of the kindle that owns the DRMed media, or otherwise extract its key from it.

[geekmaster]

Originally Posted by ixtab

...
Edit2: some further reading: http://security.stackexchange.com/qu...mized-cray-xe6

They are talking there about searching a 10-character keyspace that uses a simple hash function. In the real world, PBKDF2 is often used for key generation to prevent such a brute-force attack. Like I said, I do not know if the kindle keys were generated with a secure (slow) hash, or use a weaker fast hash function. It would be silly for them to make it quick and easy to brute-force their DRM without knowing the serial number of the DRM-authorized device. Good DRM would use something slow for key generation like the ever-popular PBDKF2 function (RFC 2898).

http://en.wikipedia.org/wiki/PBKDF2

The added computational work makes password cracking much more difficult, and is known as key stretching.

EDIT: PBKDF2 uses SHA-1 inside, but it does 2,000 rounds (or more) of hashing, so you would need to divide your 1.5M/sec key generation rate by 2,000 (or 10,000 in recent implementations).

EDIT2: PBKDF2 (or other) key stretching algorithms are also used to severely slow down dictionary-based attacks.

[ixtab]

Originally Posted by geekmaster

EDIT: Again, I do not know how the kindle DRM does it. I suspect that generating keys for all possible kindle serial numbers would be very slow. Using a fast hash for key generation would be vulnerable to brute-forcing the much smaller serial-number space instead of the full 12-bit encryption keyspace, so it would be foolish to use a fast hash for DRM key generation. After you have the right key, decryption is fast. But FINDING the right key is slow, which is why you need to know the serial number of the kindle that owns the DRMed media, or otherwise extract its key from it.

So, I just tried it. This is the result of a quick & dirty test, using the actual implementation that is running on the Kindle. In fact, the search space is even less, it actually only consists of seven alphanumeric characters. Testing 1,000,000 different keys takes about 35 seconds - and that is completely unoptimized code, which can certainly be made faster by at least an order of magnitude.

So if I was using that unoptimized program to brute-force the key for a book, it would take pretty much exactly one month to go through the entire keyspace. Parallelize this to 100 quad-core machines using AWS, and you have it cracked in at most 2 hours.

Spoiler:

DEBUG>pdbName : ;modificationDate :1311982001;type :1112493899;creator :1297039945
DEBUG>wVersion : 17480; dwStoryLen :120547861; wNumRecs :29755; wRecSize :4096; wSpare2 :2
DEBUG>magic : 1297039945; hsize :232; type :1112493899; content_type :2; encoding :1252:1252; random_id :2081344976; version :6
DEBUG>Index :29757 29833 29836 -1 -1 -1 -1 29838 -1 -1 29757
DEBUG>titleOffset :1324; title_len :28; title :; minVersion:6; embedBase:29864
DEBUG>Huffman : hufdic : 29840; hufdiclen :24; absTable :30083; tableLen:2
DEBUG>New big title :Oxford Dictionary of English
DEBUG>FFV4: idx_slaves :-1; voucherOffset :1036; voucher_tblen :1; voucher_len :288; flow_count :77
ERROR>Wrong trailingByteTypes
DEBUG>header FFV6, idx=-1
DEBUG> This book was FFV :6

1000000 iterations took 34734 ms

[pdurrant]

The calculation on brute forcing Kindle keys is flawed in two ways.

(i) The key is actually only eight characters. The two other characters are a checksum.
(ii) Kindle ebook keys are not limited to A-Z and 0-9.

One error cancels out the other - it's still impractical to brute-force a Kindle ebook's DRM key.

[ixtab]

You're right... but actually, it's a bit different. I had assumed so far that only the PID (which is in turn derived from the serial number) constitutes the key, in which case it would indeed have been even worse than what I wrote above (the PID is really only 7 characters + "*" + 2-character checksum), and those 7 characters don't even span the entire possible range (O and 0 are excluded).

However, providing the correct PID, but a wrong serial number, also fails to decrypt the file. Thus, the key space is more likely to be something like 36^13 again, which leads back to the first calculation, multiplied by another factor of ~ 50000 (yes, the serials are 16 characters, but there are only few valid "prefixes")

[zeb]

Originally Posted by crescere

I am an American where we have a Constitution and free speech. I guess I should be more aware that the rest of the world does not have the same view of freedom as I.

Right, that same America that has a legislation that makes DRM breaking outlawed (DMCA)? That tried to push the ACTA, SOPA and other inane legislations using coercion to the rest of the world? At least in my country, breaking DRM for personal use is not illegal, and I can watch DVD and Blurays on my Linux system. But thanks to the land of the free, this may not last very long.

[geekmaster]

Originally Posted by ixtab

... Testing 1,000,000 different keys takes about 35 seconds - and that is completely unoptimized code, which can certainly be made faster by at least an order of magnitude. ...

That indicates that they did not use enough hashing rounds in their key generation. PBKDF2 key generation started with 1,000 rounds in the old days, but changed to 2,000 rounds when computers got faster, and is now 10,000 rounds in some of the latest implementations. Is amazon REALLY only using a single round of hashing to generate and test keys? That is badly broken by even very old encryption standards.

They must be relying on the DMCA to protect them, rather than using "REAL" security practices. It is still a lot faster to crack the DRM using information obtained from an authorized reading device.

EDIT: You did not say how many hash rounds you used in your test. Even if it is more than a single round, testing 1,000,000 keys in 35 seconds may require more rounds for good protection.

[pdurrant]

Originally Posted by geekmaster

They must be relying on the DMCA to protect them, rather than using "REAL" security practices. It is still a lot faster to crack the DRM using information obtained from an authorized reading device.

The length of the key, or the complexity from key to decryption, really makes little practical difference.

To be able to read the book, the user must have both the key and the decryption algorithm. It's just a question of how hard it is to do the reverse engineering.

[JSWolf]

Originally Posted by pdurrant

You should be aware that America has the Digital Millennium Copyright Act, which makes it illegal to "manufacture, import, offer to the public, provide, or otherwise traffic in any technology, product, service, device, component, or part thereof".

It is because of the DMCA that DRM removal instructions are not permitted on MobileRead.

But, you'll say, the DMCA also says "Nothing in this section shall enlarge or diminish any rights of free speech or the press for activities using consumer electronics, telecommunications, or computing products.". Whoop-de-woo. Unfortunately (but wisely) the owner of MobileRead isn't willing to take the risk of being prosecuted or perhaps arrested and jailed on visits to the US. (See Dmitry Sklyarov.)

What we really need is a judge to tell the USA that Fair Use trumps the DMCA and that the DMCA can go take a flying leap.

[pdurrant]

Originally Posted by ixtab

You're right... but actually, it's a bit different. I had assumed so far that only the PID (which is in turn derived from the serial number) constitutes the key, in which case it would indeed have been even worse than what I wrote above (the PID is really only 7 characters + "*" + 2-character checksum), and those 7 characters don't even span the entire possible range (O and 0 are excluded).

However, providing the correct PID, but a wrong serial number, also fails to decrypt the file. Thus, the key space is more likely to be something like 36^13 again, which leads back to the first calculation, multiplied by another factor of ~ 50000 (yes, the serials are 16 characters, but there are only few valid "prefixes")

Ah - I see where your confusion has come from.

The various sites that claim to generate a PID from a Kindle serial number are only useful for Kindle 1 and early firmware Kindle 2.

Kindles, since the later Kindle 2 firmwares, have not had a per-device PID. Instead the Kindle's serial number is combined with information from the book's metadata to produce a per-book 8 digit PID.

A similar mechanism is used for Kindle for PC and Kindle for Mac, and I think for Kindle for Android, using some IDs from the PC or Mac instead of a Kindle serial number.

Only Kindle for iOS still (until very recently) used a fixed PID for all kindle ebooks on the device, which was derived from the iOS device's UUID.

However, since Apple have banned the use of the UUID by iOS apps, new installations of Kindle for iOS use some new method of key generation.

But all the methods eventually lead to a 8-digit (64-bit) key to the base encryption.

[ixtab]

Originally Posted by geekmaster

EDIT: You did not say how many hash rounds you used in your test. Even if it is more than a single round, testing 1,000,000 keys in 35 seconds may require more rounds for good protection.

I didn't set any number of hash rounds at all. I simply used the existing classes from Amazon, providing a new Kindle serial number each time, and tried to open an encrypted AZW file with that. It lets me try about a million times in half a minute. But given that the key space is actually determined by the entropy of the serial number (*not* just the PID, as I initially thought), that's still a couple of hundred years to wait when brute-forcing. So yeah, I guess it's still not practical for the average home user who doesn't have a supercomputer at hand.

[pdurrant]

Originally Posted by JSWolf

What we really need is a judge to tell the USA that Fair Use trumps the DMCA and that the DMCA can go take a flying leap.

It would need to not only rules that fair use trumps the DMCA, but that Free speech, in terms of DeDRM software, also trumps the DMCA.

I don't see that either is likely to happen.