I had a dream that I met an old man who knew about the design of some NSA Suite A cipher like BATON (I forget the name of the cipher, might have been SAVILLE) who threw flaming axes at me in the snow when I nagged him to tell me how the cipher worked. Eventually he gave up and told me. Turns out it wasn't an unbalanced Feistel network, but some crazy construction I never heard of that started with a Z.
2
Then we proceeded to trade source trees on his Win2k machine.
@Strernd Looking back I saw this question. Generally we don't apply the direct calculation even doing normal arithmetic. If that was the case we would be in serious problems even when just multiplying a number - doing 1000 x 1000 would take 1000 steps. Obviously it doesn't - we know shortcuts to the calculation.
@fgrieu For potential homework questions like that last one, should I even bother answering? I mean the answer to all their questions is easy, but it seems really likely that it's just homework and they want to be spoonfed.
I thought of a question, but it's not on topic for this SE -- Why isn't ChaCha12 closer to 1.66 times faster than ChaCha20? Why isn't ChaCha8 closer to 2.5 times faster?
On x64 style computers, single or multithreaded, it's instead about 1.5 and 2.0 respectively. Of course this strays into implementation-question off-topic-ness.
I wish there were an SE dedicated for optimizing code and to answer how low level software stuff works...
Could the overhead of loading the initial matrix values and adding them back in at the end be that significant? Naive assumptions would tell me it should be closer to linearly scaling with the number of rounds.
Load the IV (I mean all 512 bits, not just the nonce) into four 4x32 registers, treat those as read only. Then duplicate them and add in the counter value. Do ChaCha rounds 8, 12, or 20, times. Then add four times, once for each IV vector and each block vector.
I think there are more than enough registers to avoid storing what I called IV (nonce, key, and constants) on the stack. -_- I don't wanna look at the source of those implementations.
It doesn't look like this kind of stuff belongs on EE.SE
I probably found about 4 questions I found interesting in several tags. [CPU], [x86], [microarchitecture], etc. One was clearly a homework question, possibly copied from a handout. I saw "enter image description here" in the question.
In this one assembly implementation it seems that they're encrypting 256 bytes at a time. ChaCha's block size is 64 bytes. They're computing 4 consecutive blocks of the key stream in a single loop iteration. (There are 4x32 registers numbered z0-z15, not 4 4x32 registers representing a single 4x4x32 ChaCha block state.)
My first thought reading the asm was "Huh. There sure are a lot of mov* and pshuffle instructions for ChaCha." One of the changes between ChaCha's and Salsa was that ChaCha ARX parts operates directly on two registers so there is less need to copy values.
It ends up writing the first word of the first block, first word of the 2nd block, first of the 3rd, first of the 4th, second of the 1st, and so on.
So I think that explains the unexpected overhead that doesn't depend on the number of rounds.
I suspect the answer to your question "Why isn't ChaCha12 closer to 1.66 times faster than ChaCha20? Why isn't ChaCha8 closer to 2.5 times faster?" is related to the cost of setup and other operations that are not intrinsic to the cost of processing the round function
every step makes a notable difference towards the cost once you're optimized far enough
if it's a poorly designed algorithm that only manages like 100KB/s of throughput, minimizing MOVs as an optimization won't do much to help
but once you've squeezed almost everything else out, stuff like that starts to make a non-negligible difference
I had one design at one point that had maybe 14 instructions in the round function, so if all of a sudden there were 4 MOVs added to that then the 14 instruction loop becomes 18 instructions. almost 1/4 of the time would be loading data instead of operating on it.
No. Kerckhoffs no longer applies.
Auguste Kerckhoffs principle's were fashioned in 1883. That's yonks ago. Cryptography was not much more advanced that tattooing the message on people's heads. You can see exactly the level of complexity he was dealing with in the original document, La cryptog...
No. Kerckhoffs no longer applies.
Auguste Kerckhoffs principle's were fashioned in 1883. That's yonks ago. Cryptography was not much more advanced that tattooing the message on people's heads. You can see exactly the level of complexity he was dealing with in the original document, La cryptog...
