Register Guidelines E-Books Search Today's Posts Mark Forums Read

 MobileRead Forums DRM and AZW files
 User Name Remember Me? Password

 Notices Tip Got Facebook? Join our MobileRead Facebook Fan Page!

 Thread Tools Search this Thread
 08-23-2012, 12:35 AM #31 ixtab (offline)     Posts: 2,904 Karma: 6727035 Join Date: Dec 2011 Device: K3, K4, K5, KPW, KPW2 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.
08-23-2012, 12:46 AM   #32
geekmaster
Carpe diem, c'est la vie.

Posts: 6,428
Karma: 10764602
Join Date: Nov 2011
Location: Multiverse 6627A
Device: K1 to PW3
Quote:
 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?

08-23-2012, 12:54 AM   #33
ixtab
(offline)

Posts: 2,904
Karma: 6727035
Join Date: Dec 2011
Device: K3, K4, K5, KPW, KPW2
Quote:
 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

Last edited by ixtab; 08-23-2012 at 01:01 AM.

 08-23-2012, 01:05 AM #34 geekmaster Carpe diem, c'est la vie.     Posts: 6,428 Karma: 10764602 Join Date: Nov 2011 Location: Multiverse 6627A Device: K1 to PW3 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. Last edited by geekmaster; 08-23-2012 at 01:40 AM.
08-23-2012, 01:45 AM   #35
geekmaster
Carpe diem, c'est la vie.

Posts: 6,428
Karma: 10764602
Join Date: Nov 2011
Location: Multiverse 6627A
Device: K1 to PW3
Quote:
 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
Quote:
 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.

Last edited by geekmaster; 08-23-2012 at 02:03 AM.

08-23-2012, 03:30 AM   #36
ixtab
(offline)

Posts: 2,904
Karma: 6727035
Join Date: Dec 2011
Device: K3, K4, K5, KPW, KPW2
Quote:
 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

 08-23-2012, 03:35 AM #37 pdurrant The Grand Mouse 高貴的老鼠     Posts: 45,620 Karma: 151221090 Join Date: Jul 2007 Location: Norfolk, England Device: Kindle Voyage 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.
 08-23-2012, 03:44 AM #38 ixtab (offline)     Posts: 2,904 Karma: 6727035 Join Date: Dec 2011 Device: K3, K4, K5, KPW, KPW2 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") Last edited by ixtab; 08-23-2012 at 04:32 AM.
08-23-2012, 05:18 AM   #39
zeb
Connoisseur

Posts: 73
Karma: 2634
Join Date: Sep 2010
Device: none
Quote:
 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.

08-23-2012, 08:53 AM   #40
geekmaster
Carpe diem, c'est la vie.

Posts: 6,428
Karma: 10764602
Join Date: Nov 2011
Location: Multiverse 6627A
Device: K1 to PW3
Quote:
 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.

Last edited by geekmaster; 08-23-2012 at 08:58 AM.

08-23-2012, 09:00 AM   #41
pdurrant
The Grand Mouse 高貴的老鼠

Posts: 45,620
Karma: 151221090
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Voyage
Quote:
 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.

08-23-2012, 09:00 AM   #42
JSWolf
Resident Curmudgeon

Posts: 44,525
Karma: 30422684
Join Date: Nov 2006
Location: Roslindale, Massachusetts
Device: Kobo Aura H2O, Sony PRS-650, Sony PRS-T1, nook STR, iPad 4, iPhone 5
Quote:
 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.

08-23-2012, 09:06 AM   #43
pdurrant
The Grand Mouse 高貴的老鼠

Posts: 45,620
Karma: 151221090
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Voyage
Quote:
 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.

08-23-2012, 09:07 AM   #44
ixtab
(offline)

Posts: 2,904
Karma: 6727035
Join Date: Dec 2011
Device: K3, K4, K5, KPW, KPW2
Quote:
 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.

08-23-2012, 09:08 AM   #45
pdurrant
The Grand Mouse 高貴的老鼠

Posts: 45,620
Karma: 151221090
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Voyage
Quote:
 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.

 Tags azw, drm, kindle

 Thread Tools Search this Thread Search this Thread: Advanced Search

 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home E-Book General     News     General Discussions     Deals, Freebies, and Resources (No Self-Promotion)     Self-Promotions by Authors and Publishers     Reading Recommendations         Book Clubs     Writers' Corner E-Book Readers     Which one should I buy?     Amazon Kindle         Kindle Fire         Kindle Developer's Corner     Android Devices         enTourage eDGe             enTourage Archive         Spring Design Alex         Android Developer's Corner     Apple Devices     Barnes & Noble NOOK         Nook Color & Nook Tablet         Nook Developer's Corner     Kobo Reader         Kobo Tablets         Kobo Developer's Corner     Onyx Boox     PocketBook         PocketBook Developer's Corner     Sony Reader         Sony Reader Dev Corner     Windows Devices     More E-Book Readers         Astak EZReader         BeBook         Bookeen             Gen3 Developer's Corner         Ectaco jetBook         Fictionwise eBookwise         HanLin eBook         Interead COOL-ER         iRex             iRex Developer's Corner         iRiver Story         Netronix         Plastic Logic Que         Legacy E-Book Devices     Alternative Devices E-Book Software     Calibre         Recipes         Devices         Editor         Related Tools         Conversion         Library Management         Plugins         Development     Calibre Companion     KOReader     Sigil         Plugins     Marvin     EPUBReader     Writer2ePub     Reading and Management E-Book Formats     Workshop     ePub     Kindle Formats     PDF     Other formats         IMP         LRF E-Book Uploads - Patricia Clark Memorial Library     Upload Help     BBeB/LRF Books         E-Book Index     Kindle Books         E-Book Index     ePub Books         E-Book Index     IMP Books         E-Book Index     Other Books         E-Book Index     Offline         BBeB/LRF Books (offline)         Kindle Books (offline)         ePub Books (offline)         IMP Books (offline)         Other Books (offline) Everything Audiobooks     Audiobook Discussions     Audiobook Hardware & Software Non-English Discussions     Deutsches Forum         Erste Hilfe         E-Books             Buchclub         Software         Sony Reader         Amazon Kindle         Apple         Android         PocketBook         Cybook         Andere Lesegeräte         Lounge     Forum Français         Assistance         E-Books         Software         Sony Reader         Autres liseuses         Amazon Kindle         Kobo Reader         Cybook         PocketBook         Notre espace de lecture         Lounge français     Foro Español         Presentación         E-Books: Libros electrónicos         Software         Lectores Sony         Amazon Kindle         bq         Apple         Android         Otros dispositivos de lectura         Cafetería Miscellaneous     Introduce Yourself     Flea Market     Lounge     Feedback     Announcements

 Similar Threads Thread Thread Starter Forum Replies Last Post Caleb666 Conversion 15 09-26-2015 12:44 AM lullaby88 Amazon Kindle 8 12-10-2011 05:23 PM Dellboy67 Kobo Reader 1 12-08-2011 07:45 PM geordiejohn Calibre 5 12-09-2010 12:41 PM lizzybeth05 Amazon Kindle 11 02-17-2010 01:47 PM

All times are GMT -4. The time now is 07:36 PM.

 -- Fixed ---- Liquid Contact Us - FAQ - Guidelines - Privacy - Archive - Top

MobileRead.com is a privately owned, operated and funded community.