Welcome to Doom9's Forum, THE in-place to be for everyone interested in DVD conversion.

Before you start posting please read the forum rules. By posting to this forum you agree to abide by the rules.

 

Go Back   Doom9's Forum > General > Decrypting

Reply
 
Thread Tools Search this Thread Display Modes
Old 1st March 2007, 03:54   #41  |  Link
mb2696
Registered User
 
Join Date: Jan 2007
Posts: 39
Quote:
Originally Posted by ffguy View Post
I am not a crypto expert by any means, just an interested programmer.
Given enough of the keys, one could theoretically figure out the master key used to generate them all by guess-and-check, correct? It wouldn't be fast, but it could be theoretically done.
I ask because I have several computers with nothing to do. By splitting the potential solution space into many many parts, people like me with too much time on their hands could start chipping away at the problem. Divide the solution space and start handing out slots, if not to find the key than to verify where it is not.

if every person on the planet could uniquely test millions of keys per second it would still take forever
mb2696 is offline   Reply With Quote
Old 1st March 2007, 09:34   #42  |  Link
BlazingMind
Registered User
 
Join Date: Feb 2007
Posts: 19
Quote:
Originally Posted by ffguy View Post
I am not a crypto expert by any means, just an interested programmer.
Given enough of the keys, one could theoretically figure out the master key used to generate them all by guess-and-check, correct? It wouldn't be fast, but it could be theoretically done.
I ask because I have several computers with nothing to do. By splitting the potential solution space into many many parts, people like me with too much time on their hands could start chipping away at the problem. Divide the solution space and start handing out slots, if not to find the key than to verify where it is not.
I'm afraid the algorithms are too slow to do a brute force attack if we don't have a shortcut.

If you remember distributed.nets DES attack, it took ages to get anywhere, and that was with a fast algorithm and a tiny key (in comparison).

I'm not skilled enough with the underlying crypto to write this in assembler, but if anyone would be interested in joining forces, we might be to write highly optimized assembler code to attack these algos. This will help a little, but I fear it will still be an "impossible" task due to the nature of the algos.

Even if we managed to get 1 000 000 checks/second on an average computer (about the same speed as highly optimized MD5 brute force attacks run at today), we would still need 10 000 000 000 computers for 1 079 028 307 080 601 years to check all keys in the keyspace.

In other words... With Moores Law, we can't expect to do an effective brute force on such a key during the next 32 years, and it would still take 10 000 000 000 computers and 3-4 months.

ps. don't shoot me if it turns out that I've miscalculated this slightly, I'm not used to working with large numbers like these ;-)
BlazingMind is offline   Reply With Quote
Old 1st March 2007, 09:37   #43  |  Link
HyperHacker
Resident DRM Hater
 
HyperHacker's Avatar
 
Join Date: Oct 2006
Location: International waters
Posts: 242
Yeah, that's the problem with brute-forcing keys, it takes forever. A 128-bit key can be one of 2^128 = 3.4028236692093846346337460743177e+38 keys; even if you could arrange a bunch of computers to test one billion keys per second, it'd take about 10782897524556318080696.079785274 years to try them all.

Of course you could get lucky and it ends up being the first key tried... or you could get unlucky and it ends up being the last. Statistically, odds are this solar system won't still exist by the time we find the key at that rate.


BlazingMind, what is the goal with this memory search idea? You're trying to find places where the same 16 bytes occurrs twice in memory? Why is this?
__________________
Because Moogles pwn.
HyperHacker is offline   Reply With Quote
Old 1st March 2007, 10:17   #44  |  Link
BlazingMind
Registered User
 
Join Date: Feb 2007
Posts: 19
Quote:
Originally Posted by HyperHacker View Post
BlazingMind, what is the goal with this memory search idea? You're trying to find places where the same 16 bytes occurrs twice in memory? Why is this?
From what I understand, it is possible to obtain the various keys for those skilled enough to find them. This tool would help make it easier to find these keys so that more people would be able to find them, and that again adds pressure to the revocation system.

If such a tool does not help, my post about it is irrelevant ofcourse ;-)
BlazingMind is offline   Reply With Quote
Old 1st March 2007, 11:20   #45  |  Link
blutach
Country Member
 
blutach's Avatar
 
Join Date: Sep 2004
Location: is everything!
Posts: 6,499
Quote:
Originally Posted by HyperHacker View Post
Yeah, that's the problem with brute-forcing keys, it takes forever. A 128-bit key can be one of 2^128 = 3.4028236692093846346337460743177e+38 keys; even if you could arrange a bunch of computers to test one billion keys per second, it'd take about 10782897524556318080696.079785274 years to try them all.

Of course you could get lucky and it ends up being the first key tried... or you could get unlucky and it ends up being the last. Statistically, odds are this solar system won't still exist by the time we find the key at that rate.
Really putting it into perspective there HyperHacker!!

Regards
__________________
Les

Only use genuine Verbatim or Taiyo Yuden media.
blutach is offline   Reply With Quote
Old 1st March 2007, 16:03   #46  |  Link
awhitehead
Registered User
 
Join Date: Jan 2007
Location: Tel-Aviv, Israel
Posts: 185
Quote:
Originally Posted by HyperHacker View Post
A 128-bit key can be one of 2^128 = 3.4028236692093846346337460743177e+38 keys; even if you could arrange a bunch of computers to test one billion keys per second, it'd take about 10782897524556318080696.079785274 years to try them all.
Theoretically, given a 128 qbit (or larger) quantum computer, Peter Schor's algorithm will be able to factor it. They supposedly got working quantum computers with up to 16 qbits now (that can factor 2^16 keyspace) , so in another 10, 20 years, once AACS is no-longer relevant, this might be feasible. But not until then.

Coincidentially, modelling a quantum computer with more then ~60 qubits using conventional computers requires more bytes of RAM, then there are electrons in universe. A slight problem.
awhitehead is offline   Reply With Quote
Old 1st March 2007, 16:06   #47  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by arnezami View Post
Confirmed. This is a (sub) Device Key.
....
Technically there could be more Device and sub Device Keys (that are parents of the found device key) in memory. But I've yet to find one. Given the right memdump it should be possible to retrace it back to the "given" Device Key (the one given to WinDVD 8).
It looks like there should be 22 device keys given out to each device for use on this tree (the tree rooted at level 22 - one of the 512 largest trees in use and defined in the current MKB). There is one original device key for each level of a tree, except the root.

The PK key from arnezami matches up with an S-D set of devices rooted at level 22 and having a difference set ("revoked" pseudo device) in the lower left corner. Everyone below the upper root can calculate that PK key either from an assigned DK or a calculated sub DK.

If the device this key came from is adjacent to the lower left "revoked" device on this tree, then this would be the original device key assigned to that device. If not, then this must be a sub DK and there must be at least one other original DK at a higher level. The farther away this device is from the lower left, the more levels the device had to work through to get to the sub DK used to calculate arnezami's PK.

Are the device numbers for PowerDVD and WindDVD known? If they are different, then at least one of them must have another original DK at a higher level.

Last edited by FoxDisc; 1st March 2007 at 20:06.
FoxDisc is offline   Reply With Quote
Old 1st March 2007, 16:40   #48  |  Link
P0l1m0rph1c
h4x0r5 0n teh yu0r pC?
 
Join Date: Nov 2003
Posts: 156
Quote:
Originally Posted by awhitehead View Post
Theoretically, given a 128 qbit (or larger) quantum computer, Peter Schor's algorithm will be able to factor it. They supposedly got working quantum computers with up to 16 qbits now (that can factor 2^16 keyspace) , so in another 10, 20 years, once AACS is no-longer relevant, this might be feasible. But not until then.

Coincidentially, modelling a quantum computer with more then ~60 qubits using conventional computers requires more bytes of RAM, then there are electrons in universe. A slight problem.
This is not RSA, so Shor's algorithm does not apply.

In a quantum computer the speedup is quadratic in the general case, so to break a 128 bit key we would still need sqrt(2^128) effort, i.e. about 2^64 iterations to succeed.

Still a bit too large.
P0l1m0rph1c is offline   Reply With Quote
Old 1st March 2007, 17:04   #49  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by P0l1m0rph1c View Post
In a quantum computer the speedup is quadratic in the general case, so to break a 128 bit key we would still need sqrt(2^128) effort, i.e. about 2^64 iterations to succeed.
This discussion of breaking keys is interesting, but it's not clear what key you want to break (at least not to me). It is possible that the AACSLA set up a system with a single 128 bit key used as seed for a pseudorandom generator of master keys. That seed could then be used to derive all other keys in the entire AACS system. However, it's also possible that they set up a system with billions of randomly generated 128 bit master keys. No one knows for sure which system they set up. I suspect it was the latter, so breaking one key would not get you very far.
FoxDisc is offline   Reply With Quote
Old 1st March 2007, 18:23   #50  |  Link
KornX
primus inter pares
 
KornX's Avatar
 
Join Date: Feb 2004
Posts: 70
As i wrote some other time,
if you are talking about bruteforce cracking a 128bit cypher,
please keep the Landauer Limit in Mind...

http://en.wikipedia.org/wiki/Landauer%27s_Principle

Regards

KornX
__________________
Field Application Engineer
Advanced Micro Devices
KornX is offline   Reply With Quote
Old 1st March 2007, 20:28   #51  |  Link
BlazingMind
Registered User
 
Join Date: Feb 2007
Posts: 19
Quote:
Originally Posted by P0l1m0rph1c View Post
This is not RSA, so Shor's algorithm does not apply.

In a quantum computer the speedup is quadratic in the general case, so to break a 128 bit key we would still need sqrt(2^128) effort, i.e. about 2^64 iterations to succeed.

Still a bit too large.
Actually that would be an average of 2^127 (sorry for going slightly off topic :P)
BlazingMind is offline   Reply With Quote
Old 1st March 2007, 22:22   #52  |  Link
FoxDisc
Registered User
 
Join Date: Jan 2007
Posts: 274
Quote:
Originally Posted by xyz987 View Post
However if we want to break the revocation system, what we need is Device Keys, so many and so hight in the trees as possible.
Device keys won't do much to break "the revocation system." Even if there is only one valid player out there and you have all the device keys for all the other players, the revocation system will still work to allow that one player and keep all the rest revoked.

I can see two ways to really break the entire system:

1) Break the cryptography (very unlikely)

2) Have the AACS LA leak all their master keys (also unlikely, even if there is only one, and I suspect there are many more than one)

I can see two more ways to effectively break the system:

3) If the AACS LA issues the same device keys to many many standalone devices, and those keys can be extracted, they may be very reluctant to revoke all those devices. We don't know yet if they can revoke individual devices - it depends on what keys were assigned. (This only works if they are both stupid and greedy. Stupid to give too many devices the same keys and greedy because they don't want to revoke all the players for customers who might buy discs. Hmmmmmmmmmm - maybe this would work.)

4) Obtain title keys/device keys/processing keys faster than the AACSLA can harden players and change MKBs. (This seems likely to work (to me) but only time will tell.)

Last edited by FoxDisc; 1st March 2007 at 22:24.
FoxDisc is offline   Reply With Quote
Old 1st March 2007, 23:29   #53  |  Link
cwl7454
Dragon Slayer
 
cwl7454's Avatar
 
Join Date: Jan 2007
Location: Paradise - MD Eastern Shore
Posts: 126
One must ask themselves, how did slysoft accomplish the break? Highly unlikely that they are using someone else's certificate without their permission or reverse engineered, as this would bring it's own set of problems; or would be still selling the program without AACS knowledge. They are making no bones about the program being availible on the open market.
__________________
Dragons are alive and well!

Foxconn P45A-S/Intel Core2 Quad Q6600 Kentsfield 2.4GHZ/Artic Cooling Freezer 7 Pro/16GB OCZ2VU80016GQ DDR2 800MHZ/Radeon HD 3850 512MB GDDR3 PCIe Crossfire x2
cwl7454 is offline   Reply With Quote
Old 2nd March 2007, 01:32   #54  |  Link
xyz987
Registered User
 
Join Date: Dec 2006
Posts: 142
Quote:
Originally Posted by FoxDisc View Post
Device keys won't do much to break "the revocation system." Even if there is only one valid player out there and you have all the device keys for all the other players, the revocation system will still work to allow that one player and keep all the rest revoked.
You are right when you say that just Device Keys are not enought to break it. However the capability to get full sets of Device Keys will break it. It is this capability what matters, not the Device Key itself, and the way to get this capability is getting previously some DKs.

As I previously posted, if attacker A gets a full set of DKs, he can simply publish the DK that directly computes the PK. They can not revoke the player because they don't know its identity. If they revoke the DK, attacker simply publish the new DK that is used to "encrypt" (to compute the new PK). So they must try traitor tracing, but this is probably not effective (i.e. "traitor" can not be traced).

However to get this capability (getting full sets of DKs) attacker A needs some people have experimented how to get DKs. Attacker A can use this previously found keys to know what to search, or to check if his method is really getting DKs, and previous practice is even more important than keys. That's why I said we need to get so many keys and so hight in the trees as possible.

They can not revoke any player if they don't know its identity. Traitor tracing is at the very center of the problem, if they can not do it effectively, AACS will become quickly broken.

Edit: just an example:

Let's say WinDVD 8 is player 9 at master tree (22 level), so it has keys 8,5,3 in its DK set. If you get its DK set, you know which is WinDVD 8 position at master tree (you know it is player 9). A lot of useful information can be extracted of DK sets. This includes knowing if some standalones share the same keys, if soft players are contiguous at master tree, where a model of standalone stores DKs and how they are protected, and a lot of awaiting discoveries. WinDVD 8 will be revoked, the first compromised standalone will be revoked. So what?. Discoveries will remain.

Last edited by xyz987; 2nd March 2007 at 02:48.
xyz987 is offline   Reply With Quote
Old 2nd March 2007, 02:14   #55  |  Link
lightshadow
Registered User
 
Join Date: Feb 2007
Posts: 123
About the pattern (key) matching in memdumps we were talking about. It seams that "pattern matching" is a huge field in computer science, so there might be many programs already we can use? Where would be a good place to search for such?

Can anyone conmit if they fit out needs?

Pattern Matching
Designing Your Own Pattern Matching Routines
Perhaps the most promissing pattern match?
lightshadow is offline   Reply With Quote
Old 2nd March 2007, 07:41   #56  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Hi,

Just for clarity: we don't need a Device Key at this moment.

We need the Host Private Key.

I hope you guys and girls realize that.

Regards,

arnezami
arnezami is offline   Reply With Quote
Old 2nd March 2007, 10:33   #57  |  Link
BlazingMind
Registered User
 
Join Date: Feb 2007
Posts: 19
Quote:
Originally Posted by lightshadow View Post
About the pattern (key) matching in memdumps we were talking about. It seams that "pattern matching" is a huge field in computer science, so there might be many programs already we can use? Where would be a good place to search for such?

Can anyone conmit if they fit out needs?

Pattern Matching
Designing Your Own Pattern Matching Routines
Perhaps the most promissing pattern match?

Just to elaborate...
There is no pattern in the key. Also, don't expect all the 300MB of data to be matched to a pattern (leaving only the keys as non-patterned).

Arnezami:
Most of us are aware that it is the Host Private Key that is the holy grail.

The way I see it, we have only 3 ways to get it.

1. Continously taking memdumps from the app and go through all the data captured this way and search for the HPK.

2. Disassemble the code and follow its execution until you find the key.

3. Trace the device keys back to the AES-G algorithm and then trace its data back to the unmarked gray box in your drawing (sorry, havent checked what altorithm is used here... AES-D?) that mixes VID with HPK and log its input data until we find the HPK. This method can also be used to follow the VID to the HPK.

Option 1 is an extremely heavy task as you get huge amounts of data to analyze. On the positive side, a tool can be written to make the key searching automated so that non-programmers/hackers can contribute as well. The amount of data alone will however make this very computer intencive

Option 2... To be able to do this, you need to be a very experienced cracker with a huge amount of spare time. I speculate however that if PKs are known, this is the way they were found. This is by far the fastest way to get the HPK, but also the most demanding way.

Option 3 is what I would consider the best way for people with some programming skills to attack the HPK. Non-programmers can collect data, and with the right software/hardware in place, a semi competent cracker can analyze the data and find the key.

So...
Since I don't have hardware or software to help out, I can only guide you on the way.

Please help me clarify the following though...

From my understanding, you are still working with memory dumps taken during the "authentication/handshake" sequence of the process. This results in a file that is approx. 300MB?

You know when the VID is loaded into memory (right?).

Since the VID is used together with the HPK, it might also be worth wile to follow the VIDs to see if you can get to the HPK this way.

Last edited by BlazingMind; 2nd March 2007 at 10:37. Reason: Typo
BlazingMind is offline   Reply With Quote
Old 2nd March 2007, 11:22   #58  |  Link
arnezami
Registered User
 
Join Date: Sep 2006
Posts: 390
Ok. Let me clarify some stuff. It looks like I haven't been very clear about the Host Private Key.

First off the Volume ID is retrieved (not calculated). The Private Host Key is only used as a "passport" to let the drive give you the information it normally wouldn't give away (like the Volume ID).

Device/Processing/Media Keys have nothing to do with this process. Its a completely separate part of AACS. And I admin the gray box is a bit obscure and confusing. Sorry about that.



What's in the gray box? Basicly this:



and this:



The above is the communication between Software Player (=Host) and drive.

What is very clear is that first the AACS-auth communication is done (the picture with the Hpriv in it) and after that the Volume ID is retrieved (the last picture). However when the volume ID is retrieved the Hpriv is long gone (its not in memory anymore).

What I have done is halt the player the very moment the Hsig (or Hv) gets into memory. Since the Hsig is the result and the Hv is part of the input of the ECDSA signing function (for which the player needs the Host Private Key!) this was my best bet at finding the Private Key. But its already gone. It looks like i'm a few ms too late... (btw I always see both the Hv and the Hsig in mem which is a problem, indicating I might be looking at a copy of the Hv and Hsig)

This is the problem I am facing: how to stop the player at just the right time. I've tried to stop it just before and just after the signing function but no luck yet. It keeps slipping through my fingers .

I've also thought about this: in order for the player to sign it first has to SHA1-hash the "message" it wants to sign: this "message" is: Dn || Hv (the || simply means they are concatenated or "glued" together: Dn = 20 bytes, Hv = 40 bytes, resulting "message" = 60 bytes, and of course the SHA1-hash of this "message" is 20 bytes). Technically the hashing is part of the ECDSA signing process/function so its ideal as a marker. But this hash is not in any of my memory dumps (and btw its always different so its not very easy to check). But if I could find it in memory its quite likely the Private Key will also be in memory. But in order for this to work I need to be able to guess where this SHA1-hash is going to be written in memory so I can scan that area on-the-fly. This is what I'm currently working on.

Hope that helps to clarify it a bit.

Regards,

arnezami

PS. Of course me being able to find the private key also hinges on the fact that my private-key-identifyer is working correctly...
PPS. I'm also believe i'm having a practical problem: my GetMemoryAddressFromPattern function (link) doesn't seem capable of looking at the entire memory: it doesn't appear to be able to find patterns that are in the further portions of memory (those areas I can see using a WinHex dump). I'm not sure what "further" exactly is here. If somebody can give suggestions to solve this please do. The function uses lpMaximumApplicationAddress which seems to be correct.

Last edited by arnezami; 2nd March 2007 at 12:27.
arnezami is offline   Reply With Quote
Old 2nd March 2007, 12:20   #59  |  Link
BlazingMind
Registered User
 
Join Date: Feb 2007
Posts: 19
Arnezami:
Thanks for clearing things up... It seems i missed the fact that the optical drive also has a part in this play (Maybe you could add this to your drawing as well? :P)

I have another question or two though... (sorry for not reading all the details on how AACS works).

1. From my understanding, Hpriv is never relly needed for anything else but calculating Hsig. Why on earth would the Hsig be calculated in software, and not on the actual optical drive? Calculating it in the player would expose it to attacks like this, but from what I can see, the other components of Hsig is far less sensitive than Hpriv, and could be sent to the drive for Hsig calculation.

2. You have a complete sniff of the comunication with the drive during this sequence, correct? If these design specs are 100% correct, you should have a sniff of the Hpriv, so if you can't find it, it is probably because your analysis software has flaws.

All in all i do get a feeling that there is something missing from this picture though. The Hsig calculation seems like a red herring to me as I can't see any reason why the Hpriv should need to be accessible outside of the optical drive. Could it be that there are "secret specifications" that says "disregard figure x.x on page x. This is just written to throw off the hackers..." Or... "Hpriv should be encrypted before Hsig is calculated"...


Again, I don't have a good understanding of this system, so it may just be that I'm missing something...
BlazingMind is offline   Reply With Quote
Old 2nd March 2007, 12:23   #60  |  Link
BlazingMind
Registered User
 
Join Date: Feb 2007
Posts: 19
Quote:
Originally Posted by arnezami View Post
PPS. I'm also having a practical problem: my GetMemoryAddressFromPattern function doesn't seem capable of looking at the entire memory: it can't find patterns that are in the further portions of memory (those areas I can see using a WinHex dump). I'm not sure what "further" exactly is here. If somebody can give suggestions to solve this please do.
It might be that it gets confused by signing? (addresses above 2GB may be interpreted as being negative or positive). Just a guess.

What language is it written in?
BlazingMind is offline   Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +1. The time now is 09:27.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.