3
$\begingroup$

I am reading through the salsa family paper and on the second page DJB says this -- One can reasonably conjecture, for example, that every function that encrypts data in 0.5 Core-2 cycles/byte is breakable.

Why is this so obvious/easily conjectured? Also, does 0.5 Core-2 cycles/byte mean that the algorithm take 2 cycles to encrypt a byte using 0.5 core? Is there a table or some paper that talks about the timings of algorithms in Core-Cycles/byte? I am guessing this is implementation dependent as well, though the algorithm design also sets lower bound on this.

In the next sentence he says -- One can also conjecture that almost every function that encrypts data in 5 Core-2 cycles/byte is breakable.

Again, its not obvious to me. Can someone explain these two sentences to me?

Here is a link to the paper

$\endgroup$
  • 3
    $\begingroup$ By encrypts data using 0.5 Core-2 cycles/bytes, I believe he means that the program uses 0.5 cycles to encrypt a byte on an Intel Core-2 machine. Put an other way it encrypts 2 bytes pr. cycle or, e.g., 16bytes in 8 cycles. I am not sure why he says that such an encryption algorithm should be breakable. My guess would be that such an algorithm would have to be so simple that it cannot be secure. But I have nothing to back that up. $\endgroup$ – Guut Boy Sep 19 '16 at 7:19
  • $\begingroup$ @GuutBoy I believe that is exactly what he means, and I would agree with that statement. $\endgroup$ – Richie Frame Sep 19 '16 at 8:52
3
$\begingroup$

One can reasonably conjecture, for example, that every function that encrypts data in 0.5 Core-2 cycles/byte is breakable.

This is wrong. OTP is below 0.5 cycles/byte, and as we know it's very secure. Now, the author probably meant proper encryption, like functions that actually take key that doesn't have to be longer or equal to message length.

Also, does 0.5 Core-2 cycles/byte mean that the algorithm take 2 cycles to encrypt a byte using 0.5 core?

There isn't such thing as 0.5core. Core 2 Duo is architecture of Intel processors, and this means that on such processor, you can encrypt 2 bytes of ciphertext per processor cycle (but keep in mind that operations on ciphertext are usually done on 16-byte blocks, so this means that you do 8 operations on ciphertext).

Is there a table or some paper that talks about the timings of algorithms in Core-Cycles/byte? I am guessing this is implementation dependent as well, though the algorithm design also sets lower bound on this.

It is implementation dependent, but authors usually give performance they were able to get using optimized implementation, and usually only include time it takes to execute some core function, without padding, key setup etc. Cycles/byte are usually calculated by measuring time it takes to execute algorithm, because for many years now, there isn't set time in which CPU operation finishes.

Again, its not obvious to me. Can someone explain these two sentences to me?

Well, to achieve avalanche effect, you have to mix data. And author assumed that you cannot do this in 5cycles/byte. But actually Chacha20, variant of Salsa optimized for modern CPU's instructions, seems to be able to get to about 3-4cycles/byte. See here

$\endgroup$
  • 2
    $\begingroup$ Funfact: AES can come pretty close to these 0.5 cycles / byte (0.9 actually), but that's not on a Core2, but on the most modern CPUs. $\endgroup$ – SEJPM Sep 19 '16 at 13:24
  • 1
    $\begingroup$ 1) In your last paragraph you write "5 cycles/byte" when the claim was about "0.5" cycles. 2) The claim was about the Core-2 architecture specifically. Modern CPUs are much faster in some regards, for example they support specialized AES instructions and better SIMD instructions which bring secure crypto close to 0.5 cpb, but you can't use those to disprove the claim. $\endgroup$ – CodesInChaos Oct 19 '16 at 16:29
  • $\begingroup$ You are actually right with 5 cycles/byte was 0.5 which now seems more sensible (I didn't read paper and question contains a mistake). Still, one would use pxor to get below 0.5 on core2 (but probably author meant 'proper' encryption - I didn't read paper!). So you can go below 5 cycles/byte on core2 (thats why i mentioned Chacha20, not AES-NI), but probably not 0.5 (unless OTP). $\endgroup$ – axapaxa Oct 20 '16 at 9:16

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.