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

Powered by blists - more mailing lists