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:

nanosleep(), usleep() and sleep() Precision Tests

Working on some Amazon EC2 benchmarks I run through few problems of having my processes to run with a high time precision where a more than 1ms shift between operations is not acceptable.

My program accumulates work time and sleep time, ideally, it would work for time t, sleeps for T - t microseconds and loop again. The problem is that in the sleep routine, a shift of few microseconds can be accumulated to become a shift of milliseconds after few loops.

After investigating the problem a little, I did some tests on how precise are the sleep functions in C, here is the code I used to test nanosleep(), usleep() and sleep().



Running these tests on my machine with Fedora 15 gives me these results :


As you can see, there is always an overhead of 100µs to 180µs, a call to printf inside the function will take about 70 µs more to execute. The call to the function itself (the nsleep function) takes at worst 1µs. With this accumulation of  microseconds, a program would get to a state where it is late by some milliseconds after a dozen of iterations and calls to these sleep functions.

On the other side gettimeofday() behaves pretty well considering precision, the benchmark below (found here) gives the following results:

$ ./gettimeofday_benchmark

50000000 cycles in 2315879542 ns = 46.317591 ns/cycle

Which is satisfying for its precision.

A solution (that is not applicable in all cases) is to have a global program independent clock regarding to which the sleep period is adapted. For example instead of waiting T - t microseconds, one will use every second tick on the system as a landmark, and thus any microseconds lost in the last loop iteration are discarded in the next one since the wait time is not dependent on the time the loop has started.