article with birth-day attack for md5

Moderator: BarsMonster

Post Reply [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
ash
Posts: 23
Joined: Wed Apr 15, 2009 10:23 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

article with birth-day attack for md5

Post by ash » Sat Dec 05, 2009 2:06 pm

i've gotten one question for the guys: take a look on cal implementation of rotate function in pdf article i'd attached below.
Very interesting implementation but very unlikely it works propertly (at least with my code)

Code: Select all

; F(x,y,z)
ixor r5, r0, r1
and r5, r5, r3
ixor r5, r5, r1
; m_k + AC_t
iadd r6, cb0[0].zzzz, cb1[0].zzzz
; sum everything
iadd r5, r2, r5
iadd r5, r5, r6
; rotate <<< RC_T
ushr r6, r5, l1.xxxx
umad r5, r5, l1.yyyy, r6
; final add
iadd r2, r3, r5
Attachments
BHUSA09-Bevand-MD5-PAPER.rar
(102.53 KiB) Downloaded 332 times

IvanG
Posts: 89
Joined: Wed May 06, 2009 12:42 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: article with birth-day attack for md5

Post by IvanG » Sat Dec 05, 2009 2:41 pm

It works OK. I was testing such constructions earlier but unfortunately there no hardware "integer MAD" instruction neither on ATI or nVidia GPUs, so it'll be translated to usual 2 shifts + OR (or, more correctly, to shift + mul + add which bad for nVidia as 32-bit muls costs more than 32-bit shifts there).

ash
Posts: 23
Joined: Wed Apr 15, 2009 10:23 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: article with birth-day attack for md5

Post by ash » Sat Dec 05, 2009 3:54 pm

i'm very appreciated for your help, the problem is what i can't even surely find out about its work because of hardware problems, but as i had undestood its something like next stuff

ushr r6, r5, l1.xxxx \_____firstly right shift on (32-n), and after multyply on (32-n) and addition of the value shifted before
umad r5, r5, l1.yyyy, r6/


BUT miltyply some value by n is left shift by the value log2(n)- not for odd

IvanG
Posts: 89
Joined: Wed May 06, 2009 12:42 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: article with birth-day attack for md5

Post by IvanG » Sat Dec 05, 2009 4:31 pm

Usual rotate: (x<<n) | (x>>(32-n)).

(x<<n) = (x*1)<<n = x * (1<<n), so

(x >> (32 - n)) + (x * (1<<n)), "plus" here equivalent to "logic or" as non-zero bits aren't overlaps.

ash
Posts: 23
Joined: Wed Apr 15, 2009 10:23 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: article with birth-day attack for md5

Post by ash » Sat Dec 05, 2009 4:54 pm

sorry for troubling you i hadn't payed attension on difference among l1.xxxx and l1.yyyy.
Shit my brain was switched off for today :oops:

IvanG
Posts: 89
Joined: Wed May 06, 2009 12:42 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: article with birth-day attack for md5

Post by IvanG » Sat Dec 05, 2009 5:06 pm

(x<<7) | (x>>25) == (x>>25) + (x * (1<<7)) == (x>>25) + (x * 128),

so l1.x = 25 and l1.y = 128;

Edit: You're fast with editing ;).

ash
Posts: 23
Joined: Wed Apr 15, 2009 10:23 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: article with birth-day attack for md5

Post by ash » Sat Dec 05, 2009 5:20 pm

(x<<7) | (x>>25) == (x>>25) + (x * (1<<7)) == (x>>25) + (x * 128),

so l1.x = 25 and l1.y = 128;

Edit: You're fast with editing ;).
advice never try to code something after yesterday's evening weekend felicitation :crazy:
at least for today i've gotten switched off only eyes, thanks GOD not brain :crazy:

P.S. just for interest , do you know some documents with timings for every instruction for nvidia's cuda

IvanG
Posts: 89
Joined: Wed May 06, 2009 12:42 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: article with birth-day attack for md5

Post by IvanG » Sat Dec 05, 2009 5:45 pm

ash wrote:P.S. just for interest , do you know some documents with timings for every instruction for nvidia's cuda
Official CUDA documentation contains this info. Actually not much to document -- almost everything executes in one cycle (i.e. 4 cycles per SM per warp) with some exceptions like 32-bit integer mul (afair, it's 4x times slower). DPFP also significantly slower.

ash
Posts: 23
Joined: Wed Apr 15, 2009 10:23 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: article with birth-day attack for md5

Post by ash » Sat Dec 05, 2009 6:41 pm

ash wrote:P.S. just for interest , do you know some documents with timings for every instruction for nvidia's cuda


Official CUDA documentation contains this info. Actually not much to document -- almost everything executes in one cycle (i.e. 4 cycles per SM per warp) with some exceptions like 32-bit integer mul (afair, it's 4x times slower). DPFP also significantly slower.

yes, i've already seen that stuff.
ok. do you know any penalities on sequential using the same register.
any shaders disassemblers???
coz nvidia's "black box" model must die!
By in any case they, unlike ati"s brook, product "nice" code:(from my selfwritten disassembler-1er round of F() function from BarsWF cuda shader )-constant precomputing works well :crazy:

Code: Select all

mov.b16.b8 $r1.lo, c0[$ofs1+0x0000]
and.b32 $r13, $r0, c1[0x0004]
cvt.s32.s8 $r0, $r1.lo
add.u32 $r0, $r0, $r13
add.b32 $r1, $r0, 0xd76aa477
shl.u32 $r13, $r1, 0x00000007
shr.u32 $r1, $r1, 0x00000019
or.b32 $r16, $r13, $r1
add.b32 $r15, $r16, 0xefcdab89
and.b32 $r1, $r15, c1[0x0008]
op.d0.b32 $r13, $r15, c1[0x000c]// (Unknown subsubop 04)
or.b32 $r1, $r1, $r13
add.u32 $r1, $r1, $r7
add.b32 $r1, $r1, 0xf8fa0bcc
shl.u32 $r13, $r1, 0x0000000c
shr.u32 $r1, $r1, 0x00000014
or.b32 $r1, $r13, $r1
add.u32 $r13, $r16, $r1
add.b32 $r1, $r13, 0xefcdab89
Rotate from brook-barsWF

Code: Select all

ishl r540.x___,r537.x000,r539.x000
mov r5723.x___,r344.x000
mov r541.x___,r5723.x000
iadd r542.x___,l12.x000,l17_neg(xyzw).x000
iadd r543.x___,l12.x000,r542_neg(xyzw).x000
mov r5724.x___,r543.x000
mov r544.x___,r5724.x000
ushr r545.x___,r541.x000,r544.x000
ior r546.x___,r540.x000,r545.x000

Post Reply
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Who is online

Users browsing this forum: No registered users and 1 guest