GnuPG private key resilience against off-line brute-force attacks (was: Re: Backup of private key)

[Ciprian Dorin, Craciun]

On Sun, Nov 29, 2009 at 12:29 AM, Mario Castelán Castro
<mariocastelancastro at gmail.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> November 28th 2009 for gnupg-users at gnupg.org thread "GnuPG private key
> resilience against off-line brute-force attacks"
>
> Loop unrolling only gives more performance in very small loops, for
> not so small ones there can be in fact a performance penality since as
> the unrolled code is great it leaves less cache for data.
>
> The complexity of a S2K algoritm is constant for variable input and
> constant iterations, in other words, it is O(1) but this O(1) assumes
> constant number of iterations, if we consider that factor the
> complexity would be O(iterations).
>
> So that O(1) than you say is correct but meaningless in this context.
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (GNU/Linux)
>
> iEYEAREIAAYFAksRpCIACgkQZ4DA0TLic4iEUACgjxnvVcF0JXiBI3MuMv8HHwdY
> +P4AniUvv+j5Ysg99Qc+xDZ9e1LnCzxS
> =h116
> -----END PGP SIGNATURE-----


    Again, as I've replied to Mario (off-the-list, below the excerpt
for the rest of the list), by pipe-lining I assumed something like a
hardware SIMD architecture.

    But I do agree that for a software-based implementation the
iteration count does imply O(iteration_count) time complexity (which
is constant). But not for a hardware implementation, where I can trade
O(1) (and by `1` I don't mean constant, I actually mean `one
heart-beat or a small number of hardware cycles`) in time with a O(n)
in hardware complexity.

    In short:
>    Now imagine that we construct `iteration_count` many hardware
> based `hash` blocks.
>
> password -> (hash) -> ... iteration_count ... -> (hash) -> output

    Could someone prove me wrong? (I'm not a hardware expert, but I
believe it's technical possible.)

    Ciprian.


On Sat, Nov 28, 2009 at 7:20 PM, Ciprian Dorin, Craciun
<ciprian.craciun at gmail.com> wrote:
> On Sat, Nov 28, 2009 at 7:08 PM, Mario Castelán Castro
> <mariocastelancastro at gmail.com> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA256
>>
>> November 28th for gnupg-users at gnupg.org thread "GnuPG private key
>> resilience against off-line brute-force attacks"
>>
>>>P.S.: I'm also aware of the fact that iterations do not help at all,
>>>if a big-budget agency (NSA and the like), is going to build a
>>>hardware based brute-force key breaking, as they can build a pipeline
>>>of iteration functions that would try one key in O(1) time. :) (Or
>>>I'm wrong here?)
>>
>> Pipelining do not make iterated functions go to O(1)!. They are faster
>> but still of the same complexity. So: more iterations, more time that
>> it took to calculate, be the CPU where ejecuted pipelined or not.
>> -----BEGIN PGP SIGNATURE-----
>> Version: GnuPG v1.4.9 (GNU/Linux)
>>
>> iEYEAREIAAYFAksRWPcACgkQZ4DA0TLic4hC/QCfe9k3PybJ7X4W0oApBuob1OWh
>> yjAAn2tYiBK3yUZkAQh8dcWwwlrgxUU5
>> =Om9a
>> -----END PGP SIGNATURE-----
>
>
>    By pipeline-ing, I don't mean what we have in CPU's.
>
>    I assume that the general working principle of the iterations work
> like this:
> ~~~~
>    password = ...
>    iteration_count = ...
>    hashed_password = password
>    for i in range (0, iterattion_count):
>        hashed_password = hash (hashed_password)
> ~~~~
>
>    Now this code can be unroll-ed (if the iteration count is known at
> build-time):
> ~~~~
>    password = ...
>    hashed_password = password
>    hashed_password = hash (hashed_password)
>    ... in total iteration_count times
>    hashed_password = hash (hashed_password)
> ~~~~
>
>    Now imagine that we construct `iteration_count` many hardware
> based `hash` blocks.
>
> password -> (hash) -> ... iteration_count ... -> (hash) -> output
>
>    And at each time-tick (heartbeat) we fed 'password + 1' and push
> the output from one hash box to another (at the same time). Thus at
> each step we obtain as output one hashed password per heart-beat.
>
>    This is why I'm saying it is only O(1), but O(n) in
> hardware-blocks. Thus we trade hardware complexity with time
> complexity.
>
>    This architecture is called SIMD (Single Instruction Multiple
> Data) http://en.wikipedia.org/wiki/SIMD
>
>    So, does it seem possible now? :) (I've not actually have seen any
> mention of such method, but my opinion is that it's possible.)
>
>    Ciprian.