FORUMS

BOINC Project for bruteforcing Milestone's RSA Keys (This time for real!)

58 posts
Thanks Meter: 35
 
By pontomedon, Member on 22nd December 2010, 11:04 AM
Thread Closed Email Thread
23rd December 2010, 03:07 AM |#31  
Member
Flag Grenoble
Thanks Meter: 2
 
More
Wow I'm very surprised to see a BOINC project made by a XDA member !
I've been calculating on various BOINC projects for years (Even during [email protected] own client period)

It's quite nice to see the XDA community helping you, especially that it also promote the BOINC platform with all its projects (Biology, Math, Ecology, etc...)

But I'm quite concerned by your project and I've 3 questions:

I'm a HTC user (Been using the Magic and now the Desire HD), so excuse me for my dumb question, but:
- There is plenty of roms for the motorola, what will be the improvment to crack the RSA Key ? (Better Bootload ?)

RSA key will takes us year and year to crack (Or my not, or may be longer....we never know), so I understand that some people think it will be a waste of CPU Cycle, but:
- Isn't it possible to find a better way to crack the key instead of using Brute Force ?
- If Brute Force is the only solution, how long can it takes to crack it with 10 PC ? 100 PC ? 1000 PC? etc... Just to see if with an increase of the "crunching power" the delay can be shortened.

And it would be much more efficient to see a good GPU Application ! (In such a case, improving the CPU application will be unecessary)
Several BOINC projects got GPU application or are trying to build one. You should try to get support from them.

If you need help, let us know how we can help you.

PS: I've added my dualcore laptop on it. If I'm satisfy with your project, I might add 14 extra cores.

Good luck !
23rd December 2010, 04:43 AM |#32  
Junior Member
Thanks Meter: 0
 
More
will it also fight for XT700 series?
23rd December 2010, 05:33 AM |#33  
Senior Member
Thanks Meter: 2
 
More
Alright, I'm not up to the caliber of programming required to write a GPU application, but a quick googling around found me this:

http://researchdaily.blogspot.com/20...sing-cuda.html

Not sure if you guys can write up the big int stuff you need using that, but hey, I can say I tried to help

I also added 4 Core 2 Duo cores. I have a pair of P4 cores I will add when I get network run down to my arcade machine.
23rd December 2010, 07:56 AM |#34  
Junior Member
Thanks Meter: 0
 
More
Cool
I'm in waitting....6 hours...
23rd December 2010, 07:56 AM |#35  
Member
Flag Grenoble
Thanks Meter: 2
 
More
Quote:
Originally Posted by saren

will it also fight for XT700 series?

As said before, they don't have the ressource to run 2 servers for 2 projects (The current and the XT700).
Hence they will not "fight" for the XT700 now (But later why not)

Now, in my opinion,
- First of all, they don't need to run 2 servers (waste of ressources and money) for cracking 2 devices. But also, having 2 projects divide the number of processing power into 2 websites....and means 2 website to mantain...troublesome.
So hosting 2 projects on the same server is not a solution.

- Secondly, it is unlikely that they arrive to crack the 1024 RSA within a decent period of time (But at least they try and they might be lucky, we never know), so having 2 keys to crack on the same time phewww...

However, if they improve the algorithm for 32b and 64b or find a better way than brute force, and/or add a GPU application (as this kind of parallel calculs should be very efficient on GPU), then why not add another application ! on the same project for the XT700 (Easy to do as the code is almost the same)
Giving also the choice to the user on which application to "crunch"

But I guess, they need dev first ^^
23rd December 2010, 09:17 AM |#36  
Senior Member
Flag Livingston
Thanks Meter: 127
 
Donate to Me
More
Quote:
Originally Posted by pontomedon

as i said above, no cuda client so far, probably someone will help me implement one..

Aha, appologies. I skim read it as there being cuda support. Lulz.
23rd December 2010, 09:23 AM |#37  
Junior Member
Thanks Meter: 0
 
More
Welp, quad core coming your way
23rd December 2010, 10:07 AM |#38  
OP Member
Thanks Meter: 35
 
More
Quote:
Originally Posted by dudumomo

I'm a HTC user (Been using the Magic and now the Desire HD), so excuse me for my dumb question, but:
- There is plenty of roms for the motorola, what will be the improvment to crack the RSA Key ? (Better Bootload ?)

Currently it is not possible to change the kernel (which is stored in the "boot" partition) on the Milestone. we therefore do not have any "real" roms, all we can do is stay on the (buggy, slow, etc) Motorola kernel and try to improve it by loading modules. This is afaik what all the Roms for the Milestone do, load kernel modules and modify the system partition. if we could sign our own kernels, we would have the same possibilities as most HTC users have.

Quote:
Originally Posted by dudumomo

RSA key will takes us year and year to crack (Or my not, or may be longer....we never know), so I understand that some people think it will be a waste of CPU Cycle, but:
- Isn't it possible to find a better way to crack the key instead of using Brute Force ?

First, I'm not a mathematician, so don't nail me down on the following explanation, this is how i understood the process.
Well, as i explained on the project front page, there are extremely fast algorithms for factoring integers. The problem with those algorithms is, that they consist of two major steps. The first step is called sieving, you have to do that until you think you sieved enough. The second step is "doing something with the results from step 1". The second step is quite fast (half a year or so on a decent grid), but it will only yield a result if you sieved long enough. and this sieving is what takes enormous amounts of time, centuries in our case (and to know when you sieved enough is quite hard). So we know that GNFS (for example) will only yield a result after a few centuries, which is, of course, extremely fast compared to the worst case runtime of bruteforcing, but still bruteforcing has the (really really small) chance to yield a result in a short time, while GNFS will give you a result, but only after a very long time.
Second reason: I'm not able to implement something like GNFS. I tried to understand that algorithm, and the easiest thing i found was a paper called "An Introduction to the GNFS", which was a 85 page long Masters thesis. So it is a really really complicated thing
Quote:
Originally Posted by dudumomo

- If Brute Force is the only solution, how long can it takes to crack it with 10 PC ? 100 PC ? 1000 PC? etc... Just to see if with an increase of the "crunching power" the delay can be shortened.

it really doesn't make sense to calculate any numbers since the results would still be so incredibly small. to draw you a picture: we deal with decimal numbers of about 200-300 digits. each workunit tests an interval of 50 billion (11 digits). each more digit is a *10 increase of work. as a wild guess i would say that with millions of computers, we could reduce the worst case runtime to a few million years.

Quote:
Originally Posted by dudumomo

And it would be much more efficient to see a good GPU Application ! (In such a case, improving the CPU application will be unecessary)
Several BOINC projects got GPU application or are trying to build one. You should try to get support from them.

of course a GPU app would be incredibly much faster than the CPU app, but as said before it is quite hard to port the big integer stuff to cuda, and I'm a student, so i don't think i have enough time at the moment to accomplish this. Of course, having a gpu app would be extremely cool, i won't forget about it, whenever i have time i try to work on it.
Quote:
Originally Posted by dudumomo

If you need help, let us know how we can help you.

I think i'll make the source code of the worker available in a google code project or something like that in a few days/weeks (you know, christmas and such..). I would be glad if all of you could have a look at it then and help me improve it (or help porting it to cuda). I think especially the linux build is not as fast as it could be, because i'm really not good at building stuff under linux.
Quote:
Originally Posted by dudumomo

PS: I've added my dualcore laptop on it. If I'm satisfy with your project, I might add 14 extra cores.

Good luck !

thanks
The Following 2 Users Say Thank You to pontomedon For This Useful Post: [ View ] Gift pontomedon Ad-Free
23rd December 2010, 10:32 AM |#39  
Member
Flag Grenoble
Thanks Meter: 2
 
More
Thank you for your detailed answer ! I appreciate !
Very clear.
23rd December 2010, 10:35 AM |#40  
Senior Member
Flag Ho Chi Minh City
Thanks Meter: 12
 
More
I couldn't access the site. I had to access a cache copy of the page. Installed BOINC, but couldn't connect to the site, as it was unavailable.
23rd December 2010, 10:46 AM |#41  
OP Member
Thanks Meter: 35
 
More
it's perfectly accessible atm, there might be some provider problem at your (or even my) side. you can try accessing the page through something like TOR, you need minimal traffic for this project (a work unit file is <1KB, a result file is exactly 1 byte) the only bigger thing is the worker you have to download once, ~~1MB for windows, ~~2MB for linux.
The Following User Says Thank You to pontomedon For This Useful Post: [ View ] Gift pontomedon Ad-Free
Thread Closed Subscribe to Thread

Tags
boinc, crack, milestone, rsa, signature
Previous Thread Next Thread
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes