Attacks on BD+

[loo3aem3ON]

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:

it's ability to execute a unique content code program for every movie
the ability to fingerprint the surrounding execution environment (player/emulator) to run a series of instructions specific to the detected environment
a set of keys unique to every licensed player
various code obfuscation techniques like the instruction filter

Every licensed player is given a set of certificates which contain various informations about the player including the ECDSA public key. Bases on the information in the certificate the content code may refuse to create the conversion table. Furthermore it requires some work to obtain the private key corresponding to the (ECDSA) public key. The content code tests the knowledge of the private key by letting the player sign a random message with the private key and then verifying the validity of the resulting signature with the public key.
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)
e = 3
N =
8B169F529C28B5D45DB5D1607B831BED31381D38AEF561A43E744326DD00765E
E7A47F353D4A8C507752B08A6671259AAF140E86EEB1D05D344EF801A5AFB150
3A82BE089DCF25618852199D26CC79AE99466A231999AAC6C26E7DDA662304A7
72D1B304C9CD0C724434D640E29BE64FBBE1E7993A30939D6FB925AE0C350896
14F89FBAE9B931FC01D4D10732EB62CA8878E1894BD82F3007806D75CE172B57

You might want to read about the latest results in integer factorization: Note on Integer Factoring Methods IV (http://arxiv.org/pdf/0802.4242)

[loo3aem3ON]

What did you do to calculate d'?
By definition e*d = 1 (mod phi(N)). So there exists a k in Z such that
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)
the result is:
d'=
5CB9BF8C681B23E2E923E0EAFD02129E20D0137B1F4E411829A2D76F3E004EE9
EFC2FF78D3870835A4E1CB06EEF61911CA0D5F049F2135937834A5566E7520E0
2701D405BE8A18EBB036BBBE19DDA674662EF16CBBBBC72F2C49A93C4417586F
A1E1220331335DA182CDE42B41BD443527EBEFBB7C206268F526191EB2CE05B9
63506A7C9BD0CBFD568DE0AF77479731B050965B87E574CAAFAAF3A3DEBA1CE5

[loo3aem3ON]

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. :rolleyes:

[loo3aem3ON]

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 :(

[plonk420]

how many boinc-units (athlon 64 3000 (IIRC)) or hours would it take to break?

[Dark Shikari]

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:

Sieving has been done on 80 2.2 GHz Opteron CPUs and took 3 months.
The matrix step was performed on a cluster of 80 2.2 GHz Opterons
connected via a Gigabit network and took about 1.5 months.

From what I know, these kind of problems tend to become enormous memory hogs very quickly and do not necessarily lend themselves to being easily distributed like SETI@Home or GIMPS.

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.

[loo3aem3ON]

how many boinc-units (athlon 64 3000 (IIRC)) or hours would it take to break?
I don't know because the algorithm was proposed a few months ago (by Prof. Carella) and has so far never been implemented. It has lots of parameter which have to be carefully chosen. A single run takes about 2s (maple) and currently doesn't produce anything useful :o. This approach has been used to factor N when some bits of the factors or the private exponent are known. Because we don't have this extra knowledge the newly proposed algorithm requires multiple runs for all combinations 0 <= c,d <= log(N)^A.

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+.

[Dark Shikari]

You know, I suspect it would be far, far, far, far easier to social-engineer the RSA factorization than to calculate it with computers ;)

[plonk420]

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...

[Ábudos]

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:



From what I know, these kind of problems tend to become enormous memory hogs very quickly and do not necessarily lend themselves to being easily distributed like SETI@Home or GIMPS.

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.

Modern CPUs (even Nehalem) aren't very good when it comes to large amounts of FLOPS. Projects like CUDA and Intel's Teraflop Research could be really promising. Intel has a working 80 core prototype that has half as many transistors as a current core 2 processor and capable of 1000 GFLOPs compared to the Core 2 which is about 25 GFLOPS. With a decent cluster of Multi TFLOP computers, it would be easy to reach multiple PFLOPS, and things like breaking lengthy RSA keys may be feasible in relatively short amounts of time.

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.

[Dark Shikari]

Modern CPUs (even Nehalem) aren't very good when it comes to large amounts of FLOPS.Good thing we're dealing with integers here and not FLOPS, eh? ;)

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?"

[cuthbert]

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/abstracts/RSAattack-survey.html

[loo3aem3ON]

Just thought I'd forward this following post from the discussion at Slashdot for you:
Not again :(
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.

[loric]

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.

[NeonMan]

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 key(?)[i] which can be calculated given enough amount of scrambled segments wit the same [i]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

[stars]

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...

[loo3aem3ON]

I don't know the 1st thing about crypto, but I have found this:
Thanks. I will probably try an "easier" example first if i don't make any progress soon.

Does anybody have a good 'manual' about the conversion tables?
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.

I've heard about a BDSVM-less attack (mere speculation? maybe). I supose the attack is soething like finding a probable adecuate key(?)[i] which can be calculated given enough amount of scrambled segments wit the same [i]key
BD+ doesn't descramble anything. The original data which was overwritten in the m2ts files by random data is stored in arbitrary form (obfuscated) in the content code (in the BDSVM directory). Only by executing the content code all the pieces are put together in form of a conversion table. And you definitely need the conversion table to repair the damages. Once you have the plain (encrypted) conversion table we can discuss how to proceed from there.

isnt it possible to hack a firmware of a Blue-Ray player ????
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.

[loo3aem3ON]

I've made a sample implementation in maple which should work properly if the parameters are correctly chosen. You can download it here (http://uploaded.to/?id=apdznq). 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.

[evdberg]

What do you need to compile or run your maple script? Because Maple looks like a commercial app.

[loo3aem3ON]

What do you need to compile or run your maple script? Because Maple looks like a commercial app.
Yes maple is commercial and i am currently porting the script to gp/pari which is open source and free. Maple runs on java so it's slow and i expect gp/pari to be much faster.
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. :rolleyes:

[loo3aem3ON]

That's another implementation in GP/Pari: http://uploaded.to/?id=pr2w41
And another in SAGE with Shoup's NTL (very fast): http://uploaded.to/?id=j7o6cz

All three implementations produce polynomials which satisfy the Howgrave-Graham bound and thus have the same root over the integers. Sadly all of them are multiples of f so the resultant vanishes. I'm trying to figure out the problem.
Lattice reduction is NP-hard so (probably) more difficult than integer factorization. The lattice construction could be wrong or maybe there is a much smaller basis but the reduction algorithm (approximation) doesn't find it. :confused:

[loo3aem3ON]

I had skipped an important step in my implementation and a few other things were wrong too. After fixing those issues and playing around with the parameters a bit i found a working combination so i can give you an example.

Let p = 289254655033, q = 576650390627 and N = p*q = 166798809815457581575691. We want to factor N. We setup some parameter which determine the polynomial f. By construction the polynomial f has a root (x_0, y_0) which will give us the factorization of N. It holds that p = m*x_0 + c and q = n*y_0 + d where we have to determine c,d by brute force search and x_0,y_0 by finding an appropriate second polynomial g with the same root. In this example is m = 5779 and n = 4877 (determined by my parameter choice). We want both m and n to be as small as possible because their size determines how many combinations for c and d we have to test. By brute force search (running the entire algorithm again and again) we find c = 3490 and d = 2000.

We obtain the polynomial f( x, y ) = 272663114441221050502036905165359*x*y + 111815917343129403527593563734000*x + 164664175359034688744092195713290*y - 1613666891439484824286517533623583653166443925443

Now we construct a lattice and use lattice reduction techniques to find a short coefficient vector for our new polynomial g. This polynomial must have the same root and may not be a multiple of f (gcd(f,g) = 1 because f is irreducible).

We find: g( x,y ) = -550027317057214807707838758454131*x^2*y^2 - 21035627259174470964704774394001486176978740190*x^2*y + 279798978942801467799047317444099858865221454226*x*y^2 - 8626461865562536561414577174664878412692940000*x^2 + 815210635045419056587043555126594181612580850722711584*x*y + 168973600365180529829184985202345054933202887160*y^2 - 138762500323450558676026989874427343055634473948375906415055203127687897949926*x + 60213348692682732919411494951824394082422924853210355495670640666282857023814*y - 174110984048404287435752616687571392254879687559395285145418320554729063981835001233

Now we compute the resultant of f and g:
4476571884282525266836510330141869220498240713975097720401448926613563671146029895483060633149767902954109339351810218406344618956582075732396*y^3 - 12944301498631912946627224525490850239753133562803345399593047007314825269294562029498487898880328775532821414009302732104707106625214703423125443824*y^2 - 61053757336251582441768270515159399095157293517551804381202990288793114577733640928959281804253883501665688671801616653381775535847520521818182191534537076572*y - 25037423551750369812975300235336096113581272995509465458164313917743589489401221657131723392563075939670940390415678987548009123529431653353682394713202072000

The roots of this polynomial are y_0 = 118238751 and y_0 = 1. We can disregard y_0 = 1 (don't know where this comes from) and use the special construction of f to obtain q = 4877*118238751+2000 = 576650390627. So we are done.

The implementation: in sage (http://uploaded.to/?id=b057vs)

Note: I still don't use brute force search here and instead calculate c = p mod m and d = q mod n so don't be confused. Also the calculation takes place over the integers obviously.

[loric]

@loo3aem3ON

Sorry if my question sounds dumb, but as I have already said, I know nothing about crypto. Does your latest message mean you succeeded in proving the approach you previously described may work on BD+ too?

[loo3aem3ON]

Does your latest message mean you succeeded in proving the approach you previously described may work on BD+ too?
BD+ uses RSA signed certificates. RSA is at most as difficult as factoring. My previous postings gives an example of how the proposed new factoring algorithm works. It's complexity (cost) is still unknown (the author claims polynomial complexity but that could be wrong) therefor i can't say if it will enable us to factor this 1280 bit integer. A single run with this 1280-bit integer takes almost an hour. About m*n/2 runs will be necessary on average.

[Dark Shikari]

BD+ uses RSA signed certificates. RSA is at most as difficult as factoring. My previous postings gives an example of how the proposed new factoring algorithm works. It's complexity (cost) is still unknown (the author claims polynomial complexity but that could be wrong) therefor i can't say if it will enable us to factor this 1280 bit integer. A single run with this 1280-bit integer takes almost an hour. About m*n/2 runs will be necessary on average.But what are m and n?

(The good thing about this is that it makes the process very very easy to split among multiple computers)

[loo3aem3ON]

But what are m and n?
m,n<T with T = log( N )^A for some constant A. For this example A was about 2.
That's the theory. In my experiments i found that the minimum A was slowly increasing with the size of N which is bad.

You can download sage and experiment yourself. :logfile:

[LoRd_MuldeR]

A single run with this 1280-bit integer takes almost an hour. About m*n/2 runs will be necessary on average.

Time for decrypting@home ??? :D

[Dark Shikari]

m,n<T with T = log( N )^A for some constant A. For this example A was about 2.
That's the theory. In my experiments i found that the minimum A was slowly increasing with the size of N which is bad.

You can download sage and experiment yourself. :logfile:So can you explain how to use this algorithm?

I run it and get:

p1 = 289254655033 , p2 = 576650390627
A = 2.20000000000000 , B = 1.20000000000000 , m = 5779 , n = 4877 , Z = 117 , z0 = 58
Polynom construction ...
Generating lattice (Dim 20) ...
v = (-1613666891439484891813347699313429355070090645443, 1164255692511893891412131840000, 164664175359034688744092195713290, 111815917343129403527593563734000, 272663114441221050502036905165359)
f_ = 5488471542216098163125157288218903626095520511257496423741593312718934894201005200995*x*y + 7654196330803549667654983765341924838280181567291571978633870861234418752878580476492*x + 11882837261449311819338121444518110374297594157272539284441671547953062752440741788682*y + 6969594697988569483575820766823632301849666510274599326557396744492742541570629290404*z + 1
Checking parameter choice ...
Checking Howgrave-Graham bound: True
Reducing lattice ...
f(x_0,y_0,z_0) = 0
f = 272663114441221050502036905165359*x*y + 111815917343129403527593563734000*x + 164664175359034688744092195713290*y - 1613666891439484824286517533623583653166443925443
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 1
looks good: g( x,y ) = -550027317057214807707838758454131*x^2*y^2 - 21035627259174470964704774394001486176978740190*x^2*y + 279798978942801467799047317444099858865221454226*x*y^2 - 8626461865562536561414577174664878412692940000*x^2 + 815210635045419056587043555126594181612580850722711584*x*y + 168973600365180529829184985202345054933202887160*y^2 - 138762500323450558676026989874427343055634473948375906415055203127687897949926*x + 60213348692682732919411494951824394082422924853210355495670640666282857023814*y - 174110984048404287435752616687571392254879687559395285145418320554729063981835001233
Res_x = 4476571884282525266836510330141869220498240713975097720401448926613563671146029895483060633149767902954109339351810218406344618956582075732396*y^3 - 12944301498631912946627224525490850239753133562803345399593047007314825269294562029498487898880328775532821414009302732104707106625214703423125443824*y^2 - 61053757336251582441768270515159399095157293517551804381202990288793114577733640928959281804253883501665688671801616653381775535847520521818182191534537076572*y - 25037423551750369812975300235336096113581272995509465458164313917743589489401221657131723392563075939670940390415678987548009123529431653353682394713202072000
Res_x(y_0): 0
[(118238751, 1)]

Which line gives me the information I need? I.e. how do I know when it's found the correct result? And how do I run it automatically for all values of m/n up until it gets the result?

Also, I ran a test on the large N just to see how long one iteration took, and I got:

Traceback (most recent call last):
File "algorithm.py", line 215, in <module>
buildLattice( m_, t_, X, Y, Z, C, n_ )
File "algorithm.py", line 124, in buildLattice
f_ = ZZ( mod( v[_sage_const_4 ]*X*Y/v[_sage_const_0 ], n_ ) )*x*y + ZZ( mod( v[_sage_const_3 ]*X/v[_sage_const_0 ], n_ ) )*x + ZZ( mod( v[_sage_const_2 ]*Y/v[_sage_const_0 ], n_ ) )*y + ZZ( mod( v[_sage_const_1 ]*Z/v[_sage_const_0 ], n_ ) )*z + _sage_const_1
File "integer_mod.pyx", line 102, in sage.rings.integer_mod.Mod (sage/rings/integer_mod.c:2375)
File "integer_mod.pyx", line 136, in sage.rings.integer_mod.IntegerMod (sage/rings/integer_mod.c:2715)
File "integer_mod.pyx", line 1027, in sage.rings.integer_mod.IntegerMod_gmp.__init__ (sage/rings/integer_mod.c:8869)
File "rational.pyx", line 1496, in sage.rings.rational.Rational.__mod__ (sage/rings/rational.c:11152)
File "integer.pyx", line 3754, in sage.rings.integer.Integer.inverse_mod (sage/rings/integer.c:21900)
ZeroDivisionError: Inverse does not exist.

[loric]

A single run with this 1280-bit integer takes almost an hour. About m*n/2 runs will be necessary on average.

Could this explain why Slysoft announced they will be releasing the new BD+ patch in about 2 months? Maybe because they are cracking a new RSA certificate?

If it is so.... well, BD+ has won, all they need to do is change certificate every 2 or 3 months and nobody will ever be able to play a BD+ title using AnyDVD-HD or an hypothetical open source BD player, if not months after it is released.

[loo3aem3ON]

In my experiments i found that the minimum A was slowly increasing with the size of N which is bad.
Well it's seems it's actually more complicated. Not every pair (m,n) below the boundary is valid. You could for example try m=5779 and n=4877+1 (see posting #22 (https://forum.doom9.org/showpost.php?p=1227083&postcount=22)). It won't work for some reason. The density of these valid pairs decreases with the value of m and n therefor finding a small pair is difficult. For example i set m=1000 and started searching for a matching n and the first possible value i've found was n=3023.
It seems we need a preprocessing for finding a valid pair (m,n) with a small product m*n. :rolleyes:

Time for decrypting@home ???
And i thought i am the one being too optimistic about this. No this needs a lot more work.

Which line gives me the information I need? I.e. how do I know when it's found the correct result? And how do I run it automatically for all values of m/n up until it gets the result?
look for 0 0 gcd = 1
looks good: g( x,y ) =
It tells you that it has found a valid polynomial g. The solution (y_0) is in the last line (ignore the '1' it means the root occurred once e.g. x^2 has the root x_0 = 0 twice): [(118238751, 1)]
So y_0 = 118238751 and you can see in one of the first lines n = 4877. Sadly c and d are not displayed in this version but you can calculate d by typing "p2 % n" in the sage shell. You can verify that p2 = n*y_0 + d.

Also, I ran a test on the large N just to see how long one iteration took, and I got:
In this case you have to modify the parameters (e.g. A, X, Y, Z) slightly depending on where the exception occurs. I am currently focusing on finding "cheap" valid parameter combinations. The time a single iteration takes depends heavily on m_ and t_ (define the dimension of the lattice).

[Dark Shikari]

Could this explain why Slysoft announced they will be releasing the new BD+ patch in about 2 months? Maybe because they are cracking a new RSA certificate?If Slysoft had RSA cracked, there would be far more important ramifications than the end of BD+.

Depending on how deep the crack was, it could be the end of public key cryptography as we know it.

[loo3aem3ON]

If we can factor N it doesn't necessarily mean RSA is broken. It doesn't mean BD+ is broken because it would still require the aes device keys and a way to perfectly emulate a licensed player but it would have lost some of it's strength though. And it certainly doesn't mean the end of public key cryptography.
The knowledge of the private key of the BD+ license administration is not necessary to repair every (future) BD+ damaged movie. I try to evaluate the strength of this RSA keysize (1280) using the latest mathematical advances out of my personal interest. :)

[Dark Shikari]

If we can factor N it doesn't necessarily mean RSA is broken.Huh? Isn't it proven that breaking RSA is equivalent to the problem of integer factorization?

[loo3aem3ON]

Huh? Isn't it proven that breaking RSA is equivalent to the problem of integer factorization?
It is known that the RSA problem is at most as strong as factoring the modulus. Recent research suggests that the RSA problem (finding m given m^e mod N and the public key) might be easier than factoring if e is small.
Anyway individuals can factor a 512-bit rsa-modulus within a few hours nowadays and you wouldn't call this a break because larger "key sizes" are still secure. So if 1280-bit should become insecure people could switch to 2048 or 4096-bits which could depending on the complexity of the new algorithm still be secure. Furthermore there are lots of highly efficient attacks known on large N (4096-bit and longer) which exploit certain known properties of p and q.

[loric]

If Slysoft had RSA cracked, there would be far more important ramifications than the end of BD+.

Depending on how deep the crack was, it could be the end of public key cryptography as we know it.

You got me wrong. There's a difference between cracking the algorithm, which, I believe, is still solid, and cracking a certificate whose complexity, if I got loo3aem3ON's past messages right, is not high due to limitations (speed) of the virtual machine on which BD+ code is executed.

loo3aem3ON, if I remember correctly, wrote the key is partially exposed (the most significant bits are known) and a low exponent (3) is used.

[rumplestiltskin]

So ssl is an issue.

Does the latest news about the 200 PS3 being networked together and cracking ssl certificates provide any help to this subject?

Additionally I realize 200 PS3 might not be feasible, however, what about something like SETI - a network of online computers worldwide - running the formulations.

Another theory perhaps, what about freezing the RAM? Do the keys for the RSA go through the RAM at all?

I admit I am less than a total noob on the issue of algorithms and RSA, but I just wanted to suggest a few things.

[LoRd_MuldeR]

Another theory perhaps, what about freezing the RAM? Do the keys for the RSA go through the RAM at all?

Yes, memory dumping is a method to steal keys from a certified software player that has been used successfully in the past.

But the current generation of Blu-Ray software players protect their keys much better. They use obfuscations to make it hard to find/extract the desired keys.

Try to find a 128-Bit key in a 4 GB memory dump, if you don't know where to start. Especially when the key is only present in RAM for a few milliseconds...

[Ajax_Undone]

Try to find a 128-Bit key in a 4 GB memory dump, if you don't know where to start. Especially when the key is only present in RAM for a few milliseconds...

Depends if you have a pan and some liquid Nitro...:p
____________________________________________

OK let me get this strait.

Are looking for d = Private key.

Or are we looking for a class that retrieves d in an unencrypted form.

Or is the main objective of this to solve for the certificates to build a class that enables us to use them against the disc in question.

I know this isn't going to be any walk in the park.

The idea of Brute force is not going to be of use. leased not for another 20 years when a standard PC can simultaneously compute 100,000 P-flops. and still have the computing space to do your taxes and encode a full HD movie.:p

I think that slysofts secret is that they have found a way to copy the device certificate and use it to interface with the Disc is self. (But I have not any idea theory only) The way they get away with it is that it remains a secret as to what they actually did. But this is my own conclusion of course.

The problem with using this type of method is that any device whos firmware has been tamped with will be revoked.

Of Course total noob here so:)

PS. here is the wiki on the encryption.
http://en.wikipedia.org/wiki/RSA

[loo3aem3ON]

Does the latest news about the 200 PS3 being networked together and cracking ssl certificates provide any help to this subject?
I don't think so.

Another theory perhaps, what about freezing the RAM? Do the keys for the RSA go through the RAM at all?
The RSA-1280 private exponent is used to sign the player certificates. It is kept secret by a central license administration. The private key (private exponent) never occurs in the memory of any player.