Paolo Ardoino - ideas, programming, web and more…

[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 is a very simple wordpress plugin that uses Google Chart API to create and display a chart of your interests on the basis of blog’s categories and posts.

Version : 0.1

Download : http://ardoino.com/pub/wordpress/wp-interests.zip

Installation

1. Unzip into your `/wp-content/plugins/` directory..
2. Activate the plugin through the ‘Plugins’ menu in WordPress
3. Edit your current theme adding the few lines below (for example in siderbar.php)

    <?php
        $wp_interests = new wp_interests();
        $wp_interests->wpi();
    ?>

3.1. Defining size of the chart

        <?php
            // Chart width: 300px , height: 200px
            $wp_interests = new wp_interests();
            $wp_interests->wpi(array("size" => "300x200"));
        ?>

3.2. Defining excluded categories from chart

        <?php
            // Excluding 'Humor' and 'General' categories from chart
            $wp_interests = new wp_interests();
            $wp_interests->wpi(array("size" => "300x200", "exclude_cats" => array("Humor", "General")));
        ?>

3.3. Renaming long categories names in chart

        <?php
            // Renaming 'Ajax/Javascript' in 'Ajax/JS' and 'Crypto/Security' in 'Crypt/Sec'
            $wp_interests = new wp_interests();
            $wp_interests->wpi(array(
                "size" => "300x200",
                "exclude_cats" => array("Humor", "General"),
                "rename_cats" => array("Ajax/Javascript" => "Ajax/JS", "Crypto/Security" => "Crypt/Sec")
            ));
        ?>

3.4. For more options visit http://ardoino.com
4. That’s it!

Changelog :

• 0.1 -> initial release

My Sony Vaio TZ190N laptop powered by Gentoo Linux

Only one word… Wow!!

Features:

• Case : Black carbon fiber
• CPU: Intel­® Core™2 Duo Processor U7600 1.2Ghz
• RAM: 2GB DDR2
• HDD : 32GB Solid State Disk
• Graphic : Intel® Graphics Media Accelerator 950, 224MB
• Screen : WXGA LCD ( XBRITE-HiColor™ Technology )  11.1″ Razor-Thin Panel LED backlight for brilliant colors and clarit. Up to 1366×768
• Biometric Fingerprint Sensor Trusted Platform Module (TPM) TCG Ver.1.2 compliant
•  DVD±RW
• Built-in MOTION EYE® camera and microphone
• Networking :
  • Intel® PRO/Wireless 4965AGN Network Connection (802.11a/b/g/n)
  • 10Base-T/100Base-TX/1000Base-T
  • Integrated Bluetooth® Technology
  • Integrated V.92/V.90 modem (RJ-11)
• Battery : 7 hours ( 11 with the 9 cells large capacity)
• Weigh : 2.6 lbs ( 1.19 Kg )
• Dimension : 0.9″(W) 0.8″ - 1.17″(H) 7.8″(D)

I love it!

[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 »