-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 November 28th 2009 for gnupg-users@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.crac...@gmail.com>: > On Sun, Nov 29, 2009 at 12:29 AM, Mario Castelán Castro > <mariocastelancas...@gmail.com> wrote: >> -----BEGIN PGP SIGNED MESSAGE----- >> Hash: SHA256 >> >> November 28th 2009 for gnupg-users@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.crac...@gmail.com> wrote: >> On Sat, Nov 28, 2009 at 7:08 PM, Mario Castelán Castro >> <mariocastelancas...@gmail.com> wrote: >>> -----BEGIN PGP SIGNED MESSAGE----- >>> Hash: SHA256 >>> >>> November 28th for gnupg-users@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. > _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
