FBI Backdoor: Templar NVIDIA GPU Factoring Suite

[crushallserpents]

http://cryptome.org has posted this:

FBI Backdoor: Templar NVIDIA GPU Factoring Suite

March 29, 2012

http://cryptome.org/2012/03/Templar.zip

Other sites and twitter tweets have picked up the story and linked to the zip archive.

But, what is inside?

No one seems to know or wants to blog/tweet/talk about it on discussion forums, searching the web only reveals links to cryptome's url for the zip archive.

I'm not downloading the zip, but I'd like to know what is inside. Is this a separate program offered by NVidia, a hardware or firmware exploit?

What?

Please begin posting to blogs and discussion forums indexed by Google and other search engines, what this mystery zip archive contains!

Is anybody reading this?

[stickwhistler]

I got the zip file, and virus checked it = OK.
It appears to be a method of attacking RSA encryption.
Unless you're into such things, I wouldn't bother with it.

From the Redcross txt file in the zip.

Templar: Massively Parallel Hybrid Pollard Rho Factoring Implementation



This file, the contents of cudarho*.zip, and the contents of this folder
are the 2012 copyrighted intellectual property of Gregory Perry (Gregory.Perry@GoVirtual.tv), All Rights Reserved.




Templar is an NVIDIA CUDA implementation of the Pollard Rho factoring
method, and includes birthday attack optimizations collectively
referred to as a "reduction sieve" attack.





References on the original attack:

********************/25cdch6



The fundamental crux of this attack method against the RSA encryption
algorithm is that the keyspace to be searched can be limited to a smaller
subset of potential candidates for p and q by analyzing n with modular arithmetic, namely n mod 9 and the corresponding matrices that are
listed within the above-referenced post to sci.crypt several years ago.



This factoring implementation is designed around the NVIDIA CUDA
framework for desktop supercomputing, and contains arbitrary precision
math libraries implemented on the NVIDIA GPU architecture.

The NVIDIA GPU hardware architecture is especially well suited for this
particular factoring method, as each factoring process can be self-
contained within a single GPU thread/core as opposed to other factoring
techniques that are CPU bound with large memory tables and require
significant preprocessing, such as the Number Field Sieve (NFS).



This particular attack method should prove effective against public key
encryption methods such as RSA and Diffie Helman, as well as ECDLP key
materials used within elliptical curve encryption methods. In addition,
it would also appear that this method of reducing input candidates can
also be used against the S-boxes of conventional block ciphers such as
DES/3DES and the AES, by analyzing each S-box mod 9 and then reducing
the possibilities for predecessor round S-boxes in this same fashion.



For example, the c0/9 S-box in AES/Rijndael is dd which mod 9 = 5;
therefore, the only possible candidate input S-boxes for the preceding
rounds would then be the S-boxes which dd could be created from:

S-box 18 + S-box c5 = dd
18 mod 9 = 6 / c5 mod 9 = 8
6 + 8 = 14, 1+4 = 5



TODO:



- Fermi double precision-optimized multi precision math libraries.


- GPU localized gcd function for the Montgomery math operation which is
currently being processed by the host CPU. This is a limiting factor
of this pre-release version of the code as ~25% of the host PCI-E bus
is needed. Optimally the entire gcd function will happen on the GPU itself instead of the host CPU which will then open the doors for
highly dense supercomputing configurations such as the Dell PowerEdge
C410x GPU expansion chassis. With the C410x and the Tesla C2070 GPU,
a single 3U rack could provide 7,168 GPU cores with 8,240 gigaflops of
performance at a less than $100,000 USD price point; the "b0rken"
variant included within the Archive directory has a GPU-contained GCD
function that could be used for this (it's broken currently).


- Native multiple GPU support so that cloud GPU computing frameworks
such as the Amazon EC2 GPU cloud could be utilized for
highly scalable cryptanalytic services with a pay as you go billing
model. Amazon's recent GPU announcement provides dual Tesla GPU VM
instances for $2.10 per compute hour, with the ability to spin up
hundreds or thousands of instances, each with 896 hardware GPU cores.


- Integrate newly announced hardware-assisted PRNG functions from the
3.2 amd 4/x CUDA framework, in addition to separately seeded PRNGs for each of
the Rho factoring threads (currently the same seed is used which makes
the current implementation suboptimal).


- Integrate space/time tradeoff capabilities on the host CPU, which
would include SAN-based rainbow tables to further reduce
the field of candidates for the pre-computation attack phase.

There are additional optimizations that can be used for this attack that
will greatly reduce the attack keyspace and time required for factoring.