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. |
3rd December 2008, 18:46 | #1 | Link |
Registered User
Join Date: Sep 2008
Posts: 189
|
Attacks on BD+
As we all know BD+ (just like AACS) has not been broken yet. But now that it is known how BD+ works we should take a look for possible weaknesses. A successful attack on BD+ would remove the need to compromise future licensed hardware/software players.
The strength of BD+ seems to be based on:
If we are able to forge the RSA signature of the certificates or attack it's verification by the content code in a generic way we would no longer depend on certificates and private keys from licensed players. This would compromise a good part of the security of BD+. The RSA public key (N,e) of the license administration is: (before you start counting: ld(N) ~ 1280) Code:
e = 3 N = 8B169F529C28B5D45DB5D1607B831BED31381D38AEF561A43E744326DD00765E E7A47F353D4A8C507752B08A6671259AAF140E86EEB1D05D344EF801A5AFB150 3A82BE089DCF25618852199D26CC79AE99466A231999AAC6C26E7DDA662304A7 72D1B304C9CD0C724434D640E29BE64FBBE1E7993A30939D6FB925AE0C350896 14F89FBAE9B931FC01D4D10732EB62CA8878E1894BD82F3007806D75CE172B57 Last edited by loo3aem3ON; 3rd December 2008 at 18:52. |
6th December 2008, 12:15 | #2 | Link |
Registered User
Join Date: Sep 2008
Posts: 189
|
By definition e*d = 1 (mod phi(N)). So there exists a k in Z such that
Code:
1=e*d-k*phi(N) = e*d-k((p-1)*(q-1)) = e*d - k*(N-p-q+1) therefor d = k*(N-p-q+1)/e = k*(N+1)/e - k*(p+q)/e d' := k*(N+1)/e with k = 2 (always for e = 3) Code:
d'= 5CB9BF8C681B23E2E923E0EAFD02129E20D0137B1F4E411829A2D76F3E004EE9 EFC2FF78D3870835A4E1CB06EEF61911CA0D5F049F2135937834A5566E7520E0 2701D405BE8A18EBB036BBBE19DDA674662EF16CBBBBC72F2C49A93C4417586F A1E1220331335DA182CDE42B41BD443527EBEFBB7C206268F526191EB2CE05B9 63506A7C9BD0CBFD568DE0AF77479731B050965B87E574CAAFAAF3A3DEBA1CE5 Last edited by loo3aem3ON; 6th December 2008 at 12:23. |
6th December 2008, 20:39 | #3 | Link |
Registered User
Join Date: Sep 2008
Posts: 189
|
To give you an idea of how this new factoring method works: Let N be a product of two large primes. The problem of factoring N can be reduced to the problem of determining the roots of a polynomial like f(x,y) = N - x*y over the integers. The idea is now to find a second polynomial g(x,y) which is algebraically independent and which has the same roots like f. Given f and g we have two equations {f=0, g=0} in two variables {x,y} which we can solve efficiently using groebner basis or resultants. The difficult part is to construct g from f in efficiently. All the other steps seem to take only polynomial time. A common way to construct the second polynomial is to choose a collection of polynomials which share a common root with f and use the coefficients to construct a lattice which will then be reduced. Among the reduced vectors of the lattice (after application of the LLL algorithm) we can find a vector which corresponds to g.
This method has been recently used in several partial key exposure attacks (an adversary gained knowledge of a few bits of p,q or d) to factor N in a matter of minutes. The author of the paper in my first posting (Prof. Nelson A. Carella) has tried to combine this approach with a brute force search over a few small parameters (residue classes) to factor N without additional knowledge (of. p,q,d, etc ). I'm not sure if he is correct but i'm trying to implement his ideas anyway (in maple). If he is right with his theorem 5 then factoring would be in P and RSA broken. Last edited by loo3aem3ON; 6th December 2008 at 20:45. |
10th December 2008, 14:56 | #4 | Link |
Registered User
Join Date: Sep 2008
Posts: 189
|
Carella suggested the use of an irreducible polynomial f with degree 1 of the form f(x,y,z)=c_4*x*y + c_3*x + c_2*y + c_1*z + c_0 with a small root (x_0,y_0,z_0). Because f is irreducible it is sufficient to find any polynomial g with the same root which is not a multiple of f to efficiently calculate the root (x_0,y_0,z_0) which in turn gives us the factorization of N=p*q. It's easy to construct such a polynomial g if we know the root but we want to find the root.
With my current implementation every polynomial g i find is a multiple of f so the resultants vanish |
14th December 2008, 02:19 | #6 | Link | |
x264 developer
Join Date: Sep 2005
Posts: 8,666
|
The only way you're going to break that key is using a number sieve. There are very few implementations of that, most of which are not very optimized or not suitable for production use (merely getting one working is easily a thesis project). But there's definitely code out there to be used.
To give you an order of magnitude, breaking this key will be 100,000 times harder than breaking a 640-bit RSA key. The latter, done with a number sieve, took the following: Quote:
But assuming you could do it with the same efficiency as they did, you would need approximately 3 million modern CPU cores cranking away for one full year. Assuming each one was twice as fast as an Opteron (Nehalem) and your code was twice as fast and each had 8 cores, that would drop the requirements to a "mere" 100,000 computers. If you could GPU-accelerate the problem and get a very large performance increase it might actually be tractable, but you'd still need a massive distributed computing project. |
|
14th December 2008, 02:33 | #7 | Link | |
Registered User
Join Date: Sep 2008
Posts: 189
|
Quote:
It would take many years with "classical" methods based on fermat factorization like the general number field sieve. So the latest advances in mathematics are our only hope. The factorization would give us one of the "master keys" of BD+. |
|
14th December 2008, 05:05 | #9 | Link |
amd & h.264 fanboy
Join Date: Jun 2002
Location: NTSC
Posts: 420
|
i should have googled that... (time to brute force RSA) 100k computers is easy, depending on the number crunching purpose. yeah, social engineering would be easier than convincing this many people to crunch for possibly a small collection of movies that could change on the very next batch of releases...
|
14th December 2008, 05:22 | #10 | Link | |
Suspended for forum rule violations
Join Date: Jan 2007
Posts: 35
|
Quote:
Right now a nvidia GTX280 puts out a bit over 1 TFLOP maximum performance, and you can fit up to 4 cards in to on computer. |
|
14th December 2008, 06:00 | #11 | Link | |
x264 developer
Join Date: Sep 2005
Posts: 8,666
|
Quote:
It's a rather bad idea to overrate the power of GPUs--if you do it too much, you might find yourself having to answer the question "why is x264 faster than Badaboom?"
__________________
Follow x264 development progress | akupenguin quotes | x264 git status ffmpeg and x264-related consulting/coding contracts | Doom10 Last edited by Dark Shikari; 14th December 2008 at 06:03. |
|
14th December 2008, 12:30 | #12 | Link |
Registered User
Join Date: Aug 2005
Posts: 1
|
Just thought I'd forward this following post from the discussion at Slashdot for you:
---- One potential flaw I just noticed in the way BD+ uses RSA is that they use the public exponent e = 3. This low value is known to open up multiple theoretical attacks as described in section 4 of this paper. Too lazy to register a Doom9 account to post that info on their forums... --- link: http://crypto.stanford.edu/~dabo/abs...ck-survey.html |
14th December 2008, 13:31 | #13 | Link | |
Registered User
Join Date: Sep 2008
Posts: 189
|
Quote:
We are not trying to break RSA instead we try to evaluate it's current strength. If you read my postings carefully you will see that we are looking at the latest mathematical progress in the field of integer factorization. A new algorithm has been proposed based on polynomial equations and lattice reduction which the author (Prof. Nelson A. Carella) claims runs in polynomial time and we are trying to implement it. If this algorithm should work in polynomial time then Carella and other researchers have broken RSA. I have started this thread looking at TRAP_DeviceDiscovery first (which uses RSA signed certificates) because it is very well understood. Other parts of BD+ are still under research. It's not that TRAP_DeviceDiscovery would be the weakest part of BD+! The small public exponent e=3 is no security issue if carefully implemented. I couldn't find any weakness resulting out of this. Last edited by loo3aem3ON; 14th December 2008 at 14:37. Reason: typo |
|
16th December 2008, 17:58 | #14 | Link |
Registered User
Join Date: Sep 2008
Posts: 17
|
I don't know the 1st thing about crypto, but I have found this:
http://www.win.tue.nl/~bdeweger/RSAattack2D-final.pdf I hope it may be of some use. |
16th December 2008, 18:51 | #15 | Link |
Registered User
Join Date: Nov 2007
Posts: 80
|
Does anybody have a good 'mannual' about the conversion tables?
I've heard about a BDSVM-less attack (mere speculation? maybe). I supose the attack is soething like finding a probable adecuate [i]key(?)[i] which can be calculated given enough amount of scrambled segments wit the same key given the conversion table contents are XORed unmodiffied trhough the whole executtion (I don't know if it happens this way [I suppose it doesn't]) and because of the LARGE files we could maybe repair the damaged segments without even running the bdsvm
__________________
< War is Peace; Freedom is Slavery; Ignorance is Strength!> ^__^ (oo)\_______ (__)\.......)\/\ . . ||----w | . . || . . || |
16th December 2008, 19:17 | #16 | Link |
Registered User
Join Date: Feb 2006
Posts: 12
|
Hi...
This has maybe nothing to do with BD+ but.... I have done some bruteforcing on different encryption systems. Viaccess and D2MAC. This is satellite encryption systems but they use both RSA and AES... What I know of uses TPS AES 128 bit encryption and NAGRA, Conax are using RSA. (I think they use 512 bit keys) When our team was at its peak the total CUP power was ecual to the 5 super computer in the world... We found a lot of MK keys Management Keys (the key that updates the decryption key) for the Viaccess V2.3 system, and the the key was 8 bit long. We even tried to bruteforce a decryption key for Viaccess V2,4 which is 16 bytes long. We never found it... Maybe was the bruteforce program wrong or something else... The speed was about 4000 000 keys/sec and one area took about 24h. (1GH Athlon) So bruteforcing is a very large operation even if the computers nowadays are more powerful.. So instead of bruteforcing some people tries to find "backdoors" in the smartcards or the recivers to get hold of the MK keys. And some have been sucessful......isnt it possible to hack a firmware of a Blue-Ray player ???? stars... Last edited by stars; 16th December 2008 at 19:23. |
16th December 2008, 19:24 | #17 | Link | |
Registered User
Join Date: Sep 2008
Posts: 189
|
Thanks. I will probably try an "easier" example first if i don't make any progress soon.
No. But you can generate one with the debugger or libblueray and take a look at it with KenD00's ConvTableView or with a hex editor. Quote:
Yes and this has been done multiple times. Both AACS and BD+ are able to deal with compromised players by revoking their ability to decrypt/repair future releases. So even if you can emulate a specific licensed blue-ray player both AACS and BD+ can regain full strength for future releases. But both systems have master keys which when made public break AACS and significantly weaken BD+. The factorization of N (see above) yields one of these master keys. Last edited by loo3aem3ON; 16th December 2008 at 19:48. |
|
17th December 2008, 20:25 | #18 | Link |
Registered User
Join Date: Sep 2008
Posts: 189
|
I've made a sample implementation in maple which should work properly if the parameters are correctly chosen. You can download it here. Execute it with "maple -i algorithm.maple -q".
I used the same notation (variable/parameter names) as Carella (see first posting of this thread). The lattice construction is described in subsection 4.1.2 of the paper referenced as [ER]. You only have to interchange x and z. After lattice reduction the resulting g must have the same root over the integers so you should see some output like "row: 03 Result: 0 (0)" where the "(0)" is important. At the same time it may not be a multiple of f so you should see "gcd_ := 1" a few lines below. In that case the resultant should not vanish and you should see "res := .... some polynom ... ". The number this sample program tries to factor is 166798809815457581575691 = 289254655033 * 576650390627. It uses the knowledge of the factors to avoid brute force search over all residue classes and to verify that g has the same root over the integers. Last edited by loo3aem3ON; 17th December 2008 at 20:33. |
18th December 2008, 12:54 | #20 | Link | |
Registered User
Join Date: Sep 2008
Posts: 189
|
Quote:
Anyway it currently doesn't work. The parameters are probably wrong and maybe buggy. But for those who have read Carella's contribution it might still be interesting. I have little doubt that this algorithm will work but it's use makes only sense if m_, t_ (parameters which determine the lattice dimension) and A (parameter which determines the number of residue classes) can be small to make it work. It needs some experiments to figure our how big they have to be. |
|
|
|