Paolo Ardoino - ideas, programming, web and more…

This is a summarizing post of large integers factorization methods I have exposed in my articles.

•  Classical method
  • Source code
  • Results
• Pollard P-1
  • Source code
  • Results
• Elliptic curve method
  • Source code , Factor base
  • Results

Note: remember that this is only an idea and I’m not responsible of its use.

Yesterday I was talking with my friend Davide about the announce of Yahoo’s and Google’s CAPTCHAs cracked and another funny and foolish idea, something similar to Javascript online massive social password cracking, came into my mind.

Articles report that breaking algorithms have a success rate from 10% to 35%,with an average of 1 crack for 5 attempts… too slow!

There should be a method to improve the success rate and here I would like to discuss a nice scenario that I hope nobody would implement ;-)

Base idea:

  There are three base components to get this idea working:

• spam-bots : bots used to spam blogs, forums and websites.
  • they submit CAPTCHA decoding requests to a server (named capster)
• capster is divided in :
  • a server that handles CAPTCHA decoding requests’ queue (named cpqueue)
  • a website of social interest ( :-) explained later )
• unaware users : clients of the website
  • they decodes CAPTCHAs displayed in website’s pages

The success of this approach depends on the topic of the website… We need something that could never become boring… Yes, I know you’re thinking about it! Yeah! Sex!!

So let be pornography the topic of the website.

As explained in the diagram, spam-bots send CAPTCHA decoding requests to cpqueue (part of capster) which forwards them to the website and here unaware users resolve them.

Every 5-6 photos or 2 videos the unaware user have to enter the code of a CAPTCHA displayed on a page to continue browsing. An horde of sizzling surfers will be happy to decode CAPTCHAs to quickly proceed to the next step of strip tease :-D

Probably the wish to see something more will obfuscate the consciousness of what they’re doing!

With a bit of luck we can obtain a success rate of 100% ;-) 

I heard that there’s some Virus which implement a similar approach using popup strip teases, but malware has always to fight to survive on a computer so there’s the constant risk that the cracking farm will decline day by day and then.. arent’ we in the Web(2/3/4).0 era or not ?

Thanks to:
Davide Scola that gave me some hints
Motocarota that gives a better look to my thoughts

[This article appeared on OndaQuadra0A Elettronic Magazine]

Fondamenti di Matematica - Algoritmi Fondamentali

Metodo delle curve ellittiche per la fattorizzazione

di numeri interi.

by Paolo Ardoino AKA binduck < paolo.ardoino@gmail.com >

< http://ardoino.com >
Prima di passare al prossimo algoritmo per la riduzione in fattori

primi di un numero, conviene spiegare alcuni concetti matematici

e alcuni algoritmi che stanno alla base delle operazioni tra numeri

interi composti da molte cifre.

N.B. Questi sono solo riassunti basilari e molto semplici, che potete

consultare per avere un idea delle nozioni che sono richieste negli

articoli matematico-informatici. Per una completa visione di questi

leggete testi di matematica e algoritmi.

Mi raccomando ricordate che la matematica e’ molto importante se

volete tuffarvi nel campo della crittografia.

Le implementazioni degli algoritmi presentati in questo articolo

possono essere facilmente trovate in ogni libreria matematica per

qualsiasi linguaggio di programmazione.
0] Notazione usata
1] Concetti fondamentali
1.1] Matematica

1.1.1] Strutture algebriche

1.1.2] Gruppo

1.1.3] Anello

1.1.4] Campo

1.1.5] Aritmetica modulare

1.1.6] Piccolo teorema di Fermat
1.2] Informatica

1.2.1] Calcolabilita’ e complessita’ di un algoritmo

1.2.2] Rappresentazione numerica di un messaggio

1.2.3] Rappresentazione di un messaggio in Zn
2] Algoritmi fondamentali

2.1] Test di primalita’ e teorema di Fermat

2.1.1] Probabilistic primality test

2.2] Numeri random

2.2.1] Linear congruential method

2.3] Massimo comun divisore GCD
3] Elliptic Curve Method

 Read more »

    

In these days I was using John the Ripper ( the most famous password cracking software tool ) to test robustness of a set of passwords … of mine ;-)

While my new wonderful Sony Vaio TZ was overheating and fans seemed to get my laptop flying I had this unhealthy thought: what about a javascript online massive social password cracking ? ( first definition was only javascript password cracking but I needed to add some cooler keyword to gain more audience :-D )

Yes, I know there’s a very useful tool called djohn , but I haven’t a cluster ( only two laptops ) nor a botnet. So… how could I setup a network of computers to distribute cracking task ?

Social networks seem to be very popular today and people have a lot of computer idle to waste !! :-) However this article will not focus on the philosophical or social facet but only on the technical feasibility study of a Javascript DES cypher implementation and its performance running on modern browsers ( Mozilla Firefox, Opera and Konqueror )

A simple first implementation came in my mind:

• DES and Triple DES encrypted password cracking
• Brute force/incremental method : all possible character combinations as passwords
• Password’s space divided in work packets by a web server that coordinates the effort among the clients ( browsers )

Other cracking methods, such as wordlist, are very much faster than brute force, but more complex, than password’s space subdivision, to coordinate via AJAX.
I had a quick look to JTR source to understand its cracking procedure, so I decided to port its Triple DES cipher implementation to javascript. Writing this article I found this one that seems to be a bit faster than mine.

Had you ever benchmarked John The Ripper on your machine? Here are results of the 3DES on my Sony Vaio TZ ( Intel Core 2 - ULV U7600 1.20ghz ) :

~# john –test

Benchmarking: Traditional DES [128/128 BS SSE2]… DONE
Many salts: 1019K c/s real, 1019K c/s virtual
Only one salt: 815539 c/s real, 839032 c/s virtual

Wow! 1019K cracks per second!!

How many days do we need, at most, to crack a weak 8 bytes ASCII password with a brute force attack? ( Note: read about password strength )

• assuming to know that it is 8 byte ASCII password
• 64^8 : are the permutations with repetitions
• 64^8 / ( 1019 * 10^3 ) = 276226669 secs = 3197 days needed to cover all the key space

Having a wide set of computers, a lan with some good machine, the cracking time will fly down quickly.

Ok, these are the results of a C compiled Triple DES. An xyssl library based solution gave me a proof of the validity of JTR results.

Clearly we all know that interpreted languages are slower than compiled ones… so I was expecting that an interpreted implementation of the algorithm could be 30, 50, 100 times slower …

No! it’s from 2000 to 4000 times slower !!!

Here are my browsers’ tests ( on Gentoo with an Intel Core 2 - ULV U7600 1.20ghz ) :

• Mozilla Firefox 2.0.12 : ~250 cracks per second
• Mozilla Firefox 3.0 beta3 : ~250 cracks per second ( … I was expecting better results than 2.0 version … )
• Konqueror 4.0 : ~500 cracks per second ( I love it !! )
• Opera 9.25 : ~370 cracks per second
• Safar 3 : results should be similar to Konqueror, because both use Webkit
• Internet Explorer : data unavailable

Test Javascript 3DES performances on your browser and please comment this post to report them (including your hardware, CPU at least)

Then I tested mcrypt PHP implementation ( with the code below ) and results weren’t better : ~1000 cracks per second.

$ts_start = gettimeofday();while(1) {
  $ts_end = gettimeofday();
  if(($ts_end["sec"] - $ts_start["sec"] == 1) && $ts_end["usec"] > $ts_start["usec"]) break;
  @mcrypt_encrypt(MCRYPT_3DES, "cialfklweflkwnelfkw", "Prova", MCRYPT_MODE_ECB);
  $cnt++;
}
echo "Cracks per second: ".$cnt++;

Another test to compare web browser is a simple addition. The C compiled version performs up to 100000000 additions per second and here are results of the Javascript implementation on browsers :

• Firefox 2.0.12 : ~33000 additions per second
• Firefox 3.0 beta3 : ~96000 additions per second ( fortunately, here it’s faster than 2.0.x )
• Konqueror 4.0 : ~130000 additions per second
• Opera 9.25 : 153000 ( good! )

Conclusion…

Performances of Javascript engines are still not good enough and I think this could be a very hard limit to Web2.0 that should be overtaken as soon as possible.

Time ago I wrote some articles to explain, with simple examples, the use of OpenSSL API s for file encryption:

• DES, Blowfish, IDEA, MD5
• OpenSSL RSA

Now, in this article, I’ll show how to add secure thread safe connections to your software using OpenSSL .

As reported by official FAQs, Multi-threaded applications must provide two callback functions to OpenSSL by calling CRYPTO_set_locking_callback() and CRYPTO_set_id_callback() . The library below, sslc ( Secure Sockets Layer Connections ) , sets up this two callbacks and offers two functions to the application to handle secure connections : open_sslc and close_sslc .

Read more »

[This article appeared on OndaQuadra0B Elettronic Magazine - Mar 2004 ]

OpenSSL/DES,OpenSSL/Blowfish,OpenSSL/IDEA,OpenSSL/MD5: implemtentation

UNISFED written and coded by Paolo Ardoino <paolo.ardoino@gmail.com>

0. Intro

1. Descrizione algoritmi

2. Funzioni & headers DES

3. Funzioni & headers Blowfish

4. Funzioni & headers IDEA

5. Funzioni & headers MD5
In questo articolo vedremo come implementare quattro tra gli algoritmi

piu’ famosi e piu’ usati nel campo della crittografia:

DES,Blowfish,IDEA,MD5

 Read more »