mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2008-06-07, 16:16   #1
IronBits
I ♥ BOINC!
 
IronBits's Avatar
 
Oct 2002
Glendale, AZ. (USA)

3×7×53 Posts
Default Stop Gpcode!

http://forum.kaspersky.com/index.php?showtopic=71652
Anyone up for a challenge and a possible new DC project ?

So we're calling on you: crytographers, governmental and scientific institutions, antivirus companies, independent researchers…join with us to stop Gpcode. This is a unique project – uniting brain-power and resources out of ethical, rather than theoretical or malicious considerations.
Here are the public keys used by the authors of Gpcode.
The first is used for encryption in Windows XP and higher.
Key type: RSA KeyExchange
bitlength: 1024
RSA exponent: 00010001
RSA modulus:
c0c21d693223d68fb573c5318982595799d2d295ed37da38be41ac8486ef900a
ee78b4729668fc920ee15fe0b587d1b61894d1ee15f5793c18e2d2c8cc64b053
9e01d088e41e0eafd85055b6f55d232749ef48cfe6fe905011c197e4ac6498c0
e60567819eab1471cfa4f2f4a27e3275b62d4d1bf0c79c66546782b81e93f85d

The second is used for encryption in versions of Windows prior to XP.
Key type: RSA KeyExchange
bitlength: 1024
RSA exponent: 00010001
RSA modulus:
d6046ad6f2773df8dc98b4033a3205f21c44703da73d91631c6523fe73560724
7cc9a5e0f936ed75c75ac7ce5c6ef32fff996e94c01ed301289479d8d7d708b2
c030fb79d225a7e0be2a64e5e46e8336e03e0f6ced482939fc571514b8d7280a
b5f4045106b7a4b7fa6bd586c8d26dafb14b3de71ca521432d6538526f308afb

The RSA exponent for both keys is 0x10001 (65537).
The information above is sufficient to start factoring the key. A specially created utility could be of great help in factoring.
IronBits is offline   Reply With Quote
Old 2008-06-07, 16:25   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

178016 Posts
Default

Why do we need to crack these two RSA keys? Can you please explain more about what you think Gpcode is and what is so dangerous about it. I found this link (and many other similar websites) that says Gpcode uses simple encryption that is easily reversible.

If it is just a virus that encrypts some of one's files then it is a simple matter to reformat and restore from one's backup. Standard procedure.
retina is online now   Reply With Quote
Old 2008-06-07, 16:43   #3
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3·2,083 Posts
Default

Hmmm.....both of those are 309 digit numbers, assuming my hexadecimal-to-decimal conversion worked right. The fastest known method for factoring numbers of this type would be GNFS--though, unfortunately, even a 180-digit GNFS factorization is considered huge with today's resources. (Initial prep-work for such an effort is currently being coordinated in the Factoring forum.)

There's a slim chance that it could be done, with lots of resources and time, though the outlook may even be worse than that. (One of the gurus in the Factoring forum should be able to tell you whether it's even at all possible.) You might have better luck by hiring some hackers to find, and then break into, the virus writer's computer, and get the private key that way.

If even one of these numbers was successfully factored, AFAIK it would set a new world record for the largest factorization completed to date!
mdettweiler is offline   Reply With Quote
Old 2008-06-07, 16:44   #4
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

141518 Posts
Default

Quote:
Originally Posted by retina View Post
Why do we need to crack these two RSA keys? Can you please explain more about what you think Gpcode is and what is so dangerous about it. I found this link (and many other similar websites) that says Gpcode uses simple encryption that is easily reversible.

If it is just a virus that encrypts some of one's files then it is a simple matter to reformat and restore from one's backup. Standard procedure.
According to the website IronBits linked to, this was a "dangerous new variant" of Gpcode. Presumably, the easily-reversible encryption would have been from an earlier version.
mdettweiler is offline   Reply With Quote
Old 2008-06-07, 16:53   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

27·47 Posts
Default

There is no point in bothering to crack it. Once some malware takes over your data you can't trust it from then on, encrypted or not, it has been compromised. Even if, by some magic, the factors are found, by then the hacker will likely have tweaked his code to 2048bit, or put in a new key, or switched to ECC, or any number of other things to make the effort futile.
retina is online now   Reply With Quote
Old 2008-06-07, 21:49   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3×112×29 Posts
Default

Quote:
Originally Posted by retina View Post
There is no point in bothering to crack it. Once some malware takes over your data you can't trust it from then on, encrypted or not, it has been compromised. Even if, by some magic, the factors are found, by then the hacker will likely have tweaked his code to 2048bit, or put in a new key, or switched to ECC, or any number of other things to make the effort futile.
Almost certainly true!

Anyway, factoring kilobit hard integers, whether by GNFS or any other known algorithm, is significantly beyond the current state of the art. It should just about be possible in around ten years time with massive effort --- assuming that the last 40 years of progress in integer factorization is a reasonable guide to the next ten. Do not bet too much money on that assumption!


Paul
xilman is offline   Reply With Quote
Old 2008-06-11, 17:48   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by xilman View Post
Almost certainly true!

Anyway, factoring kilobit hard integers, whether by GNFS or any other known algorithm, is significantly beyond the current state of the art. It should just about be possible in around ten years time with massive effort --- assuming that the last 40 years of progress in integer factorization is a reasonable guide to the next ten. Do not bet too much money on that assumption!


Paul
The progress has come from two sources: new algorithms and faster/bigger
computers. We have not had a new algorithm in 20 years. Determining how
much more can be squeezed from NFS via faster/bigger computers is
problematic. Note that new algorithms alone have not helped. GNFS
could not have even been run on computers from (say) 1987. They did not
have enough memory.

And trying to predict the occurrence of a new algorithm is pure guesswork.

Hey Paul! How about a bet? Not too small, Not too big. Say $20 U.S.?
I bet that a 1024-bit GNFS factorization will NOT be achieved within 10 years.
R.D. Silverman is offline   Reply With Quote
Old 2008-06-11, 19:36   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3×112×29 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
The progress has come from two sources: new algorithms and faster/bigger
computers. We have not had a new algorithm in 20 years. Determining how
much more can be squeezed from NFS via faster/bigger computers is
problematic. Note that new algorithms alone have not helped. GNFS
could not have even been run on computers from (say) 1987. They did not
have enough memory.

And trying to predict the occurrence of a new algorithm is pure guesswork.

Hey Paul! How about a bet? Not too small, Not too big. Say $20 U.S.?
I bet that a 1024-bit GNFS factorization will NOT be achieved within 10 years.
You're on.

However, to hedge against currency fluctuations, I suggest that the amount be USD20 or GBP10, whichever is the greater at the time the bet becomes payable --- either 2018-06-12 00:00:01 UTC or when a factorization is announced, whichever is the earlier.

Note that at the current exchange rate, GBP10 is worth a few cents more than USD20.


Paul
xilman is offline   Reply With Quote
Old 2008-06-11, 19:58   #9
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

Or perhaps a more stable "currency" ...

Like some good "single-malt" :)
Wacky is offline   Reply With Quote
Old 2008-06-12, 07:37   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3·112·29 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Hey Paul! How about a bet? Not too small, Not too big. Say $20 U.S.?
I bet that a 1024-bit GNFS factorization will NOT be achieved within 10 years.
How about a side bet?

Same conditions except that there's no requirement that the factorization be performed by GNFS but, rather, is a demonstration of an algorithm and its implementation which is capable of factoring a hard 1024-bit (or greater) integer.

The quantum computer people, last time I heard (8 years ago) were also predicting "15-20 years" for kilobit factorizations by Shor's algorithm. We've no idea (at least, I've no idea) whether a new algorithm will turn up in the near future. If it does, or if the QC people hit their target, it may well be possible to perform a kilobit GNFS within ten years but not cost-effective to do so. Compare the situation with 512-bit factorizations. It's undoubtedly possible to do one with QS now but there's no real incentive to prove that claim.


Paul
xilman is offline   Reply With Quote
Old 2008-06-12, 13:17   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by xilman View Post
How about a side bet?

Same conditions except that there's no requirement that the factorization be performed by GNFS but, rather, is a demonstration of an algorithm and its implementation which is capable of factoring a hard 1024-bit (or greater) integer.

The quantum computer people, last time I heard (8 years ago) were also predicting "15-20 years" for kilobit factorizations by Shor's algorithm. We've no idea (at least, I've no idea) whether a new algorithm will turn up in the near future. If it does, or if the QC people hit their target, it may well be possible to perform a kilobit GNFS within ten years but not cost-effective to do so. Compare the situation with 512-bit factorizations. It's undoubtedly possible to do one with QS now but there's no real incentive to prove that claim.


Paul
You are on.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
It won't stop giving me ECM, help! 137ben PrimeNet 5 2012-03-29 12:43
Sieving: When to stop? SaneMur Riesel Prime Search 4 2011-07-18 17:04
When will it stop? ThomRuley Msieve 20 2010-05-19 02:12
Should we stop at k=249? jocelynl 15k Search 2 2004-07-10 13:31
RMA - stop LLR bug paulunderwood 3*2^n-1 Search 8 2004-05-19 07:10

All times are UTC. The time now is 06:19.

Thu Jan 28 06:19:17 UTC 2021 up 56 days, 2:30, 0 users, load averages: 2.48, 2.77, 2.64

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.