Magic of SELB / VSEL

2009-05-28T18:42:00.000-07:00

Last year after reading the presentation by Nick Breeze on using the PS3 as a password cracker, I decided to invest in one and investigate myself if it was suitable for password recovery.

Although I'd planned to write up a little article on the potential of the Cell B.E inside the PS3, never really got the time to develop anything and the following is simply the macros for MD5 which were used.


// selb replaces ((z) ^ ((x) & ((y) ^ (z)))) 
#define FF(a,b,c,d,x,t,s)                                           \ 
        data[x] = spu_insert(((unsigned int*)buf1)[x],data[x],0);    
        data[x] = spu_insert(((unsigned int*)buf2)[x],data[x],1);    
        data[x] = spu_insert(((unsigned int*)buf3)[x],data[x],2);    
        data[x] = spu_insert(((unsigned int*)buf4)[x],data[x],3);    
        a = spu_add(a, spu_splats((unsigned int)t));                 
        a = spu_add(a, data[x]);                                     
        a = spu_add(a, spu_sel(d,c,b));                              
        a = spu_rl (a, s);                                           
        a = spu_add(a, b);


// selb replaces ((y) ^ ((z) & ((x) ^ (y)))) 
#define GG(a,b,c,d,x,t,s)                               \ 
        a = spu_add(a, spu_splats((unsigned int)t));     
        a = spu_add(a, data[x]);                         
        a = spu_add(a, spu_sel(c,b,d));                  
        a = spu_rl (a, s);                               
        a = spu_add(a, b);


// same 2 xors here for ((x) ^ (y) ^ (z)) 
#define HH(a,b,c,d,x,t,s)                               \ 
        a = spu_add(a, spu_splats((unsigned int)t));     
        a = spu_add(a, data[x]);                         
        a = spu_add(a, spu_xor(b,spu_xor(c,d)));         
        a = spu_rl (a, s);                               
        a = spu_add(a, b);


// orc + xor used to replace ((y) ^ ((x) | ~(z))) 
#define II(a,b,c,d,x,t,s)                               \ 
        a = spu_add(a, spu_splats((unsigned int)t));     
        a = spu_add(a, data[x]);                         
        a = spu_add(a, spu_xor(c,spu_orc(b,d)));         
        a = spu_rl (a, s);                               
        a = spu_add(a, b);

As you can see, SELB is very useful instruction.
Looking at MD4 and SHA-1 which use similar instructions, Its possible to optimize G too.


In the G function of MD4 and SHA-1 we have the following expression: 

        (((x) & (y)) | ((x) & (z)) | ((y) & (z))) 

This was optimized to: 

        (x & y) | (z & (x | y)) 

and using the SPU or PPE vector instructions, we can 
do it with 2 VSEL or SELB opcodes.
                 
        t = spu_sel(y,x,spu_sel(y,x,z));

Maybe someone will find it useful, who knows.

G924789

Magic of SELB / VSEL