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 20th December 2008, 18:50   #21  |  Link
loo3aem3ON
Registered User
 
Join Date: Sep 2008
Posts: 189
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.
loo3aem3ON is offline   Reply With Quote
Old 23rd December 2008, 15:47   #22  |  Link
loo3aem3ON
Registered User
 
Join Date: Sep 2008
Posts: 189
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

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.

Last edited by loo3aem3ON; 23rd December 2008 at 16:49. Reason: smaller example (with m_ = t_ = 1)
loo3aem3ON is offline   Reply With Quote
Old 23rd December 2008, 16:19   #23  |  Link
loric
Registered User
 
Join Date: Sep 2008
Posts: 17
@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?
loric is offline   Reply With Quote
Old 23rd December 2008, 16:45   #24  |  Link
loo3aem3ON
Registered User
 
Join Date: Sep 2008
Posts: 189
Quote:
Originally Posted by loric View Post
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.

Last edited by loo3aem3ON; 23rd December 2008 at 16:48.
loo3aem3ON is offline   Reply With Quote
Old 23rd December 2008, 16:58   #25  |  Link
Dark Shikari
x264 developer
 
Dark Shikari's Avatar
 
Join Date: Sep 2005
Posts: 8,690
Quote:
Originally Posted by loo3aem3ON View Post
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)

Last edited by Dark Shikari; 23rd December 2008 at 17:01.
Dark Shikari is offline   Reply With Quote
Old 23rd December 2008, 17:39   #26  |  Link
loo3aem3ON
Registered User
 
Join Date: Sep 2008
Posts: 189
Quote:
Originally Posted by Dark Shikari View Post
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.
loo3aem3ON is offline   Reply With Quote
Old 23rd December 2008, 20:58   #27  |  Link
LoRd_MuldeR
Software Developer
 
LoRd_MuldeR's Avatar
 
Join Date: Jun 2005
Location: Last House on Slunk Street
Posts: 12,777
Quote:
Originally Posted by loo3aem3ON View Post
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 ???
__________________
There was of course no way of knowing whether you were being watched at any given moment.
How often, or on what system, the Thought Police plugged in on any individual wire was guesswork.



Last edited by LoRd_MuldeR; 23rd December 2008 at 21:29.
LoRd_MuldeR is offline   Reply With Quote
Old 24th December 2008, 00:13   #28  |  Link
Dark Shikari
x264 developer
 
Dark Shikari's Avatar
 
Join Date: Sep 2005
Posts: 8,690
Quote:
Originally Posted by loo3aem3ON View Post
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.
So can you explain how to use this algorithm?

I run it and get:

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

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

Last edited by Dark Shikari; 24th December 2008 at 00:23.
Dark Shikari is offline   Reply With Quote
Old 24th December 2008, 00:32   #29  |  Link
loric
Registered User
 
Join Date: Sep 2008
Posts: 17
Quote:
Originally Posted by loo3aem3ON View Post
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.
loric is offline   Reply With Quote
Old 24th December 2008, 00:38   #30  |  Link
loo3aem3ON
Registered User
 
Join Date: Sep 2008
Posts: 189
Quote:
Originally Posted by loo3aem3ON View Post
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). 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.

Quote:
Originally Posted by LoRd_MuldeR View Post
Time for decrypting@home ???
And i thought i am the one being too optimistic about this. No this needs a lot more work.

Quote:
Originally Posted by Dark Shikari View Post
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
Code:
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):
Code:
[(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.

Quote:
Originally Posted by Dark Shikari View Post
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).

Last edited by loo3aem3ON; 24th December 2008 at 01:07.
loo3aem3ON is offline   Reply With Quote
Old 24th December 2008, 00:56   #31  |  Link
Dark Shikari
x264 developer
 
Dark Shikari's Avatar
 
Join Date: Sep 2005
Posts: 8,690
Quote:
Originally Posted by loric View Post
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.
Dark Shikari is offline   Reply With Quote
Old 24th December 2008, 01:27   #32  |  Link
loo3aem3ON
Registered User
 
Join Date: Sep 2008
Posts: 189
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.
loo3aem3ON is offline   Reply With Quote
Old 24th December 2008, 01:52   #33  |  Link
Dark Shikari
x264 developer
 
Dark Shikari's Avatar
 
Join Date: Sep 2005
Posts: 8,690
Quote:
Originally Posted by loo3aem3ON View Post
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?
Dark Shikari is offline   Reply With Quote
Old 24th December 2008, 02:08   #34  |  Link
loo3aem3ON
Registered User
 
Join Date: Sep 2008
Posts: 189
Quote:
Originally Posted by Dark Shikari View Post
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.

Last edited by loo3aem3ON; 24th December 2008 at 02:33. Reason: typos
loo3aem3ON is offline   Reply With Quote
Old 24th December 2008, 10:46   #35  |  Link
loric
Registered User
 
Join Date: Sep 2008
Posts: 17
Quote:
Originally Posted by Dark Shikari View Post
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.
loric is offline   Reply With Quote
Old 19th January 2009, 04:30   #36  |  Link
rumplestiltskin
Registered User
 
Join Date: Aug 2008
Posts: 1
off beat approaches....

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.
rumplestiltskin is offline   Reply With Quote
Old 19th January 2009, 04:54   #37  |  Link
LoRd_MuldeR
Software Developer
 
LoRd_MuldeR's Avatar
 
Join Date: Jun 2005
Location: Last House on Slunk Street
Posts: 12,777
Quote:
Originally Posted by rumplestiltskin View Post
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...
__________________
There was of course no way of knowing whether you were being watched at any given moment.
How often, or on what system, the Thought Police plugged in on any individual wire was guesswork.



Last edited by LoRd_MuldeR; 19th January 2009 at 05:31.
LoRd_MuldeR is offline   Reply With Quote
Old 19th January 2009, 08:15   #38  |  Link
Ajax_Undone
I dont care so should you
 
Ajax_Undone's Avatar
 
Join Date: Apr 2006
Location: In hell next to the boiling pit of Lava...
Posts: 989
Quote:
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...
____________________________________________

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.

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
__________________
My Installer's ||
Ajax_Undone is offline   Reply With Quote
Old 19th January 2009, 18:43   #39  |  Link
loo3aem3ON
Registered User
 
Join Date: Sep 2008
Posts: 189
Quote:
Originally Posted by rumplestiltskin View Post
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.

Quote:
Originally Posted by rumplestiltskin View Post
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.
loo3aem3ON 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 18:05.


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