Key Factoring

[odolo]

Really impressed with your work!

Was wondering if you can tell me what special purpose algorithm was used to factor the 512 bit key, and how you identified which special purpose algorithm to use.

[ankostis]

I will try to briefly address some misconceptions:

• This tool does NOT factor any key, but takes advantage of factorization done by external tools (factordb.com, msieve and/or YAFU).
• Additionally, the key used by the malware developer is the 256bit EC curve, not 512bit.
• And actually it is not even this 256bit-key that is being attacked; it is the homegrown "mul" 128bit key that was in use till v3.x- variants of teslacrypt.

[ankostis]

Finally, in my opinion, 512bit factorization keys are currently impossible to break with civilian-grade hardware; 512bit EC crypto is beyond reach even for military-grade installations.

[odolo]

Thanks for your response. I always appreciate a well thought out message.
The 512 bit key comes from this stackoverflow post:
http://stackoverflow.com/questions/34258360/all-documents-converted-to-vvv-extension-teslacrypt
The author (Googulator) states:
The number being factored is NOT an RSA key, that's the point. It's a 512-bit number with lots of factors, one of which is the session key.

If possible can you please refer me to more details about this "mul" key and how it came to be?

I'm trying to get an idea of the of how the key was discovered, the kind of key it is and how it was factored specifically (algorithm wise),

[ankostis]

You are right.
I have forgotten a lot of stuff and the bit-width informations I gave above are totally wrong - please disregard it. I should have mentioned bytes(!) not bits.

So the "mul" key that gets factorized is 130bytes! (not bits) which is a bit more than 1024bits.
Inside this it is stored the 64byte EC-key (512bits).

[Googulator]

The "mul" key is 128 hex digits, which equals 64 bytes, or 512 bits. It's a multiplication of an uninteresting 256-bit (32-byte, 64 hex digit) ECDH shared secret, and a 256-bit AES key, which is what you need for decryption.

[odolo]

I've been wanting to better understand this particular piece of malware but I'm having trouble finding the binary. More specifically I want to get a better idea of the PRNG which may have been used for generating the ECC keys.

Any helps/tips on where I can find this particular malware would be appreciated.