0
$\begingroup$

I need to clarify if my understanding is correct.

if I am using 4.2 GHz CPU -one core only- that means:

4.2 billions hertz = 4.2 billion operations per second. (about 2^32)

So:

32 bit key : 2^32 \ 2^32 = 1 second

64 bit Key : 2^64 \ 2^32 = 2^32 = 4294967296 seconds = 136 Years

My Questions:

1) Is my way of calculation is correct?

2) In Assembly language : is one line = 1 operation?

$\endgroup$
4
$\begingroup$

Your calculation gives the correct order of magnitude but is not correct. Different assembly operations take a different number of clock ticks/cycles. Also note memory access can be expensive, and it makes a big difference which cache layer if any you hit. To make matters worse there is a difference between an instructions throughput and latency because several instructions can happen simultaneously. If you really want to do micro optimizations yourself you can look up instruction cost here: http://www.agner.org/optimize/instruction_tables.pdf

For cryptographic operations we usually already have highly optimized code and we can just look up the cost in cycles of various cryptographic primitives. For instance SHA-3 is very efficient and can be implemented with a throughput of ~8 cycles/byte on modern processor.

Just in general you expect single cryptographic function invocations to take on the order of a few hundred cycles in efficient implementations.

In order to make brute-forcing low entropy passwords difficult we usually use tuneable Key Derivation Functions which can be made arbitrarily slow.

$\endgroup$
  • $\begingroup$ Although serious bruteforce attacks don't use one core, or CPUs at all; they use highly parallel hardware such as GPU, FPGA, or ASIC. Even as far back as EFF's DES cracker in 1998, which did 2^56 in a few days (and I'm not sure why they didn't use complementarity to halve it). $\endgroup$ – dave_thompson_085 Apr 3 '18 at 1:20
  • $\begingroup$ The question specifically stated single core cpu. $\endgroup$ – Meir Maor Apr 3 '18 at 4:22
1
$\begingroup$

Specific to your 2nd question

No, 1 line does not equal 1 operation
Different instructions can take multiple operations to complete
Also different instructions work on different sized registers

A single instruction may require 3 processor cycles to complete, but process only 32 bits of data. A single instruction may require a single processor cycle to complete, but process 128 bits of data.

A complete algorithm is generally benchmarked as cycles per input byte or as cycles per invocation, depending on the type of algorithm. The result is dependent on processor architecture and implementation but independent of clock speed. Algorithms that accept variable input lengths such as hash functions are benchmarked with a variety of input lengths, as their performance will vary with input length.

$\endgroup$
  • 1
    $\begingroup$ Also a single memory operation (load / store from RAM) may take up to 100s of cycles if you're unlucky with caching / pre-fetching... $\endgroup$ – SEJPM Apr 3 '18 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.