Stop Gpcode!
 

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

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:
[COLOR=teal]c0c21d693223d68fb573c5318982595799d2d295ed37da38be41ac8486ef900a
ee78b4729668fc920ee15fe0b587d1b61894d1ee15f5793c18e2d2c8cc64b053
9e01d088e41e0eafd85055b6f55d232749ef48cfe6fe905011c197e4ac6498c0
e60567819eab1471cfa4f2f4a27e3275b62d4d1bf0c79c66546782b81e93f85d[/COLOR]
The second is used for encryption in versions of Windows prior to XP.
Key type: RSA KeyExchange
bitlength: 1024
RSA exponent: 00010001
RSA modulus:
[COLOR=teal]d6046ad6f2773df8dc98b4033a3205f21c44703da73d91631c6523fe73560724
7cc9a5e0f936ed75c75ac7ce5c6ef32fff996e94c01ed301289479d8d7d708b2
c030fb79d225a7e0be2a64e5e46e8336e03e0f6ced482939fc571514b8d7280a
b5f4045106b7a4b7fa6bd586c8d26dafb14b3de71ca521432d6538526f308afb[/COLOR]
The RSA exponent for both keys is [B]0x10001 (65537)[/B].
The information above is sufficient to start factoring the key. A specially created utility could be of great help in factoring.

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 [url=http://www.f-secure.com/v-descs/gpcode.shtml]this[/url] 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.

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! :shock:

[quote=retina;135403]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 [URL="http://www.f-secure.com/v-descs/gpcode.shtml"]this[/URL] 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.[/quote]
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.

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.

[QUOTE=retina;135408]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.[/QUOTE]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

[QUOTE=xilman;135438]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[/QUOTE]

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.

[QUOTE=R.D. Silverman;135694]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.[/QUOTE]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

Or perhaps a more stable "currency" ...

Like some good "single-malt" :)

[QUOTE=R.D. Silverman;135694]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.[/QUOTE]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, [b]I've[/b] 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

[QUOTE=xilman;135737]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, [b]I've[/b] 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[/QUOTE]

You are on.