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 15:22:24 -0400
From: Bo Zhu <bo.zhu@...terloo.ca>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Catfish and public key hash

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