Factoring Large Numbers With Distributed Quadratic Sieve

Integer factorization is a problem that has its roots in the very far history, it is a fascinating problem (to me especially) that has gained a lot of attention in the recent years for cracking the RSA cryptosystem for example.

While having no time to blog about the internals of one of the very efficient methods to factorize relatively large numbers, I present here a simple implementation I have developed of the Quadratic Sieve to factorize relatively big RSA numbers. For a reference about the mathematical premises, the 6th chapter entitled Subexponential Factoring Algorithms of the Prime Numbers, A Computational Perspective book is pretty great.

The program available here is composed of 4 different versions, 3 centralized (sequential) and 1 distributed using MPI. The distributed version needs to be run on at least 2 nodes. The centralized versions consist of different implementation experiments : 

• The first one keeps the exponent vector of each smooth number (impractical due to the huge memory needed to keep the vectors).
• The second one sieves at an interval centralized at sqrt(N); according to my testing, this has no visible improvements over the standard one. 
• The last version which is the same as the first one but which uses only a binary exponent vector (saving one bit for each prime in the base) for the smooth numbers.

One of the caveats of this implementation is the linear algebra step that performs the Gaussian elimination. The method I am using is the most naive one (though goes pretty fast using XOR operations on GMP integers) which keeps an identity matrix besides the effective matrix while performing the Gaussian elimination, and hence the program needs twice the memory needed for the matrix.

The distributed version spawns as many nodes as needed and makes them all perform the sieving step, after some very hundreds of thousands of steps, the slaves communicate their found smooth numbers to the master which decides if they must stop or should continue sieving for more numbers. Sending GMP integers mpz_t over MPI was very challenging due to the way MPI handles the string representation of these numbers (sometimes '\0' are included at the end and the length returned does not represent exactly the number of characters in the string).  You can take a look at the functions doing the MPI send/receive of mpz_t here.

You will need the mpfr library too (for logarithm calculations) in case you want to test the programs, for the distributed version, compile with mpicc and run with mpirun as usual.

Results:

Centralized version:

Distributed version (60 intel i7 nodes):

Factoring Integers: Part 1 - Pollard's rho Method

I'll be developing a program for factoring numbers (especially RSA numbers), the goal is to have a parallel quadratic sieve program running on GPUs (using CUDA or OpenCL) to factorize RSA numbers.

I have just started playing around GMP so I implemented a naive version (in C) of the Pollard's rho factoring method, it uses the optimisation technique proposed by Pollard and Brent, however it doesn't check for cases that may cause the algorithm to fail.

In order to compile this program, you need to have GMP installed.
You can invoke the program with ./pollard-rho NUMBER or ./pollard-rho p q where the number to factorize is p*q.

Compile : gcc pollard-rho.c -o pollard-rho -lgmp -lm

Rolling Back a Project to Windows Phone OS 7.0 After an Upgrade to 7.1 (Mango)

If you had a project that was developed before the Mango SDK was available, or a project that was created with the Windows Phone 7.0 as the target platform and wanted to upgrade to 7.1, then there is no way to roll back to 7.0 again, which means that your app will be available only for those who have Mango updated devices.

On creating a new Windows Phone project with the Mango 7.1 SDK tools installed, Visual Studio prompts you for the target platform:

If for any reason, you want to upgrade the app to take advantage of the 7.1 SDK (use background agents, live tiles' animations etc..), you go to Project -> Project properties and set the target to OS7.1:

Once the Windows Phone OS7.1 version is selected, Visual Studio shows the following warning stating that once upgraded, the application cannot roll back to Windows Phone OS 7.0 anymore :

Because the referenced projects are not upgraded with the app, there is actually a way to roll back anyways, even if Visual Studio warns it is not possible.

First in the WPAppManifest.xml you need to change the AppPlatformVersion back to "7.0". Then unload the project from Visual Studio and open your *.csproj with a text editor. Locate <TargetFrameworkProfile>WindowsPhone71</TargetFrameworkProfile> and change it to <TargetFrameworkProfile>WindowsPhone</TargetFrameworkProfile>.

Reload the project in Visual Studio, and voila, it's back to version 7.0.

Hope this helps.

Bloginto 2.1 Now Available

Bloginto 2.1 is available for download from the Google Chrome Web Store, the 2.1 version is a patch to the 2.0 version after the (abrupt) changes of Bloginy Algeria.

Bloginto is a Chrome extension that brings Bloginy Algeria and Morocco feeds to the browser. With Bloginto you can:

• Read the live feeds of Bloginy Algeria and Morocco
• Keep track of the new feeds and get notified whenever newer news are available
• Keep track of the read and unread feed entries
• Vote for the feed entries directly from the browser with 1 mouse click
• Tweet directly through the extension

Bloginto is an open source extension, you can grab the source code from here https://github.com/martani/BlogInto-Chrome, you can suggest amelioration and patches too.

Mass Spamming WP7 Users by Taking Advantage of the Chrome to WP7 App

Send to WP7 (previously Chrome to WP7) is an app on Windows Phone 7 that allows users to send text, web links, images etc. to their WP7 handsets directly from the browser. It resembles in it's purpose Google's Chrome to Phone utility, however, its security model is way poorer, and even insecure by default.

While Google Chrome to Phone uses OAuth to authenticate users along with their Google accounts, Send to WP7 generates a 6 chars hex number which is calculated from a random GUID generated when the app is started for the first time. This code is then used by the extension to send data back to daveamenta.com server, waiting to be served when the WP7 client fetches the updates.

Since there is absolutely no validation process on the server and the design of the app that makes it impossible to verify who is sending to who depending only on the randomly generated code, abusing this app is just like taking a walk on the shore.

Sending data to a WP7 device is done by a POST request to http://www.daveamenta.com/wp7api/com.davux.ChromeToWindowsPhone/ with the random code of the user as the only piece identifying him.

Request URL: http://www.daveamenta.com/wp7api/com.davux.ChromeToWindowsPhone/
Request Method:  POST
Query String Parameters
        title: some title
        url: http://martani.net
        sel:
        type: page
        passcode: ABCDEF

The server then returns "Client Not Found. Check Pair Code." if the code used is not associated to any device, or "OK - No notification" upon success. Using these information, we can run a large scale "empty message" spamming to retrieve the valid codes associated to actual devices, or send a wave of spams directly without having to check for validity.

Theoretically, there are over 16777216 different available codes for a 6 char hex number, a naive method would be to iterate through all these and fetch the correct ones:

This above program would do -a very lengthy- sequential probing to check for all the codes that return "OK" in the response and list them on the console.

As you can see, you can send any message and even links to your apps on the WP7 Marketplace (which once clicked would open the Marketplace directly) to all the users of "Send to WP7", and of course retain their codes for future spamming eventually.

On the other hand, it is not clear how the data users exchange with their devices is handled. Does it get archived in the server forever? Does a deletion from the WP7 client entail a deletion from the server etc. I believe users of this app should get answers of all these questions and of course must expect a minimum of security where only them could eventually send data to their phones.


//I cannot be held responsible for any abusive use of information I present here, this post is merely a showcase of bad security design.

Skype XSS Made Easy

I was so deprived of caffeine today so I couldn't do any work except erring in the dark sides of the internet till I got to the skype home page. Once there, the first thing I tried was of course some XSS injection, that's just a 'weby' thing, I can't help it.

I was amused to see that after 3 characters, the skype home page started to show beatiful html code where it should not, a very good sign for an XSS injection.

Here you go, on the home page, locate the "See how little it costs to call phones and mobiles with Skype" search box and type -"&gt; , you should get something like this :

Now type in your favorite XSS verse, I use &lt; script &gt; alert(document.cookie) &lt; /script &gt;, Voilà! the result: