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

[Mario Castelán Castro]

-----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"

Ciprian: Wath you say is possible but useless.

One could build a machine who computes anything in only 1 clock cycle
or than not even need clock cycles: there are circuits than change it
output as it input is changed without need of a pulse (Usually from a
clock, it is: constant frecuency pulse generator) but the change is
not inmmediate. As the compexity (Circuit complexity, not
computational complexity) increases the delay betwen input change (Or
clock signal) and output change becomes greater and greater thus they
operating frecuence is low.

So, yes, it can be built a machine than compues the S2K in one clock
cycle, but it clock cycle shold be of very very low frecuency thus
having the same performance as a machine than computes a S2K in say,
20,000 cycles but with much faster cicles.

This is the contrary version of the megahert myth: "More cycles, more
speed" than assumes than a 2.4 GHz CPU have the same eficiency per
cycle than a 3.2 one. You instead think than more eficience per cycle
gives more performance, your mistrake is than the cycles will be
larger and frecuency much lower.

Performance = Frecuency * Performance of each cycle. Sometimes one can
make cycles 2 times more efficient but frecuency only 20% lower as
intel do with P4 to Core 2 but this tradeoff can't be repeated infite
times. There are some point where slighty more efficient cycles
provokes a much more loss in frecuency and therefore the overall
performance will be low.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEAREIAAYFAksRwJ4ACgkQZ4DA0TLic4il2QCeKXlMID7S0K8/ay3JuWCqvxrP
Kq8An1GDC/bGlgbwjGr8ebrdRAPgJ+H4
=o+UI
-----END PGP SIGNATURE-----


2009/11/28 Ciprian Dorin, Craciun <ciprian.craciun at gmail.com>:
> 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.
>