phc-discussions - Re: [PHC] Catfish and public key hash

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Wed, 2 Apr 2014 19:32:23 -0400
From: Bo Zhu <bo.zhu@...terloo.ca>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Catfish and public key hash

[speed-ups...] isn't
=>
isn't [speed-ups... ]

Sorry for my big typo...

--Bo




On Wed, Apr 2, 2014 at 3:22 PM, Bo Zhu <bo.zhu@...terloo.ca> wrote:

> Hi Steve,
>
> Thanks for pointing that out.
> It's a well-known optimization method.
>
> But [speed-ups only if a large memory is present] isn't one of the
> features that PHC wants in order to thwart the attacks based on ASICs and
> GPUs, right? :)
> And in this case, knowing p and q, the look-up tables can be much smaller.
>
> Best,
> Bo
>
>
> On Wed, Apr 2, 2014 at 2:48 PM, Steve Thomas <steve@...tu.com> wrote:
>
>>   An attacker with more memory can calculate the public key hash faster
>> than
>> the defender even if the attacker doesn't have p and q.
>>
>> # initial work (done only once)
>> for j = 0 to 2 ** 16
>>     short_cut[0][j] = pow_mod(generator, j, N)
>> for i = 1 to BIT_SIZE_N / 16
>>     for j = 0 to 2 ** 16
>>         short_cut[i][j] = pow_mod(mem[i-1][j], 2 ** 16, N)
>>
>> # calculating the public key hash
>> num = short_cut[i][exponent & 0xffff]
>> exponent = exponent >> 16
>> for i = 1 to BIT_SIZE_N / 16
>>     num = mul_mod(num, short_cut[i][exponent & 0xffff], N)
>>     exponent = exponent >> 16
>> return num
>>
>> if BIT_SIZE_N is 1024 then with 1024 / 8 * 2 ** 16 * (1024 / 16) bytes of
>> memory (512 MiB) the attacker only needs to do 63 multiplies mod N. Using
>> less than 3.5 GiB you can get it down to 53 multiplies mod N.
>>
>
>

Content of type "text/html" skipped