27

Post-quantum security: As you note, quantum attacks are not known to break lattice-based cryptosystems. But some other proposals like McEliece, as well as most symmetric primitives are not known to be poly-time breakable on a quantum computer. Security from worst case assumptions: In security proofs for cryptosystems we typically assume that some problem ...


24

Bitslicing is a technique where computation is: Reduced to elementary operations (called gates) with a single bit output (typically NOR, XOR, and similar like OR AND NAND NXOR, often with further restriction to two inputs), rather than operations on words or integers spanning several bits. Executed in parallel, with as many simultaneous instances (on a ...


21

The basic idea of bitslicing, or SIMD within a register, involves two parts: expressing the cipher in terms of single-bit logical operations (AND, OR, XOR, NOT, etc.), as if you were implementing it in hardware, and carrying out those operations for multiple instances of the cipher in parallel, using bitwise operations on a CPU. That is, in a bitsliced ...


16

It depends. Specifically, it depends on the type of cipher, and on the way it's used. For stream ciphers like RC4, and for block ciphers like AES in CTR and OFB modes, decryption is effectively identical to encryption, and thus takes the exact same time. (Minor exception: encryption may require generating a unique nonce / IV, which might take a small ...


15

Contrary to the other answer, I'll be assuming the hash function is of the password-oriented kind; and my answer will be: input size has almost no influence on speed in good practice, even for much longer input than in the question. Password-oriented (or entropy-stretching, key-stretching) hash functions are, for example, suitable to transform a (password, ...


15

There are two important differences between AES-128 and AES-256: AES-128 has 10 rounds, AES-256 has 14 The key expansion process (that is, how they generate subkeys) is different If your AES-128 encryption hardware just takes a plaintext block and a 128 bit key, and produces a ciphertext block, well, no, there's not much you can do. In this case, the ...


13

ECDSA should in general create signatures faster than RSA for the same cryptographic strength if you just look at the mathematics. In the end the modular exponentiation is performed for smaller numbers. However, ECDSA depends on a random number generator, so ECDSA speeds may be slower if the random number generator blocks for any reason (and not using a good ...


13

The security level of an elliptic curve group is approximately $\log_2{0.886\sqrt{2^n}}$. You can use this to approximate the security level of a $n$-bit key, eg: $\log_2{0.886\sqrt{2^{571}}} = 285.32537860389294$ The real computation (at least for curves over a finite field defined by a prime $p$) is $ \log_2{\sqrt{\pi/4}\sqrt{ℓ}} $, where $ℓ$ is the ...


13

The fastest block cipher is identity, which leaves input blocks completely unchanged. This is infinitely fast on all platforms; however, it is not secure. So maybe you want the fastest block cipher that still offers some given non-trivial level of security? Then it depends a lot on what you want to implement the block cipher on. With recent PC, you would ...


11

Are you sure? Float operations are very hard to reproduce in diverse environments. Do you round towards positive, negative or zero? Do you handle denormals or just treat them as zero? What about dividing by zero? I'm sure we would love to have that problem with every cipher we implement. Looking for a CSPRNG that's very fast on GPUs, and would be hard ...


11

As cypherfox had correctly pointed out during our chat, two rounds is not enough to reliably diffuse a single changed bit throughout the entire output. My question appears to have been answered directly by Bernstein's page on diffusion for Salsa20 (note that ChaCha has better diffusion). Quoting https://cr.yp.to/snuffle/diffusion.html The following pictures ...


10

To perform a good check, please use a large number of iterations (i.e. a for loop) of calls to the cryptographic primitive with your specific data size. Then average these out. To avoid compiler optimizations, be sure to print out the result after the clock has been stopped. For instance, you could XOR all the outputs together and print that out. Otherwise ...


10

I second Richie Frame's observation that AES is an excellent choice. I'd use AES-128 in CTR mode, which has the advantage that decryption is the same as encryption (thus is as fast, contrary to some other modes). Update: SPECK, considered in this other answer, is good if compactness or speed per encryption for narrow block size are the choice criteria. ...


9

A "general computer" simply doesn't exist, test for yourself with this command: openssl speed rsa As an example here is the output on a Mac Pro 2007 withIntel Xeon 5130: Doing 512 bit private rsa's for 10s: 67450 512 bit private RSA's in 9.95s Doing 512 bit public rsa's for 10s: 961891 512 bit public RSA's in 9.94s Doing 1024 bit private rsa's for 10s: ...


9

"Cycles" are CPU instruction cycles. Cycles per byte roughly measures how many instructions, in a given instruction set, are needed to produce each byte of output. They're a reasonably-good relative measure of the performance of different algorithms. Generally, when you measure an algorithm's cycles per byte, you use carefully controlled conditions. You ...


9

Bitslicing is a technique that allows multiple instructions/Data points to be encoded into a single register. The idea is that you encode several bitwise operations within a single register. So, instead of 32 bitwise OR operations in sequence, you could reduce the total number of operations by cramming the data into SIMD registers and executing in ...


9

If you are using the full HKDF each time, you could possibly save time by only using the Extract portion once and Expand once per derived key. That could even halve the total time taken, if you had a worst case situation. Another speedup possibility within HKDF is to use another hash. Either a faster hash or one that matches the required key length better. ...


9

It depends how the “AES-128 encryption hardware units” you mention are actually defined. I've already encountered processors that allow to independently compute AES operations such as $\texttt{SubBytes}$ and $\texttt{MixColumns}$ – which are the same regardless the key size involved (128 or 256 bits). In that case: yes, it can speed up the calculation for ...


8

Is Rijndael the fastest block cipher in the world? No. On an Intel 64 Sandy Bridge without AES-NI, AES (a subset of Rijndael) is outperfomed by ChaCha20 (and also likely by Threefish 512 which has about 6-7cpb cost on an older Intel Core 2 Duo with 64-bit ASM (link: original Skein paper PDF)) as opposed to AES' 11 cpb. (7.59 cpb on an Intel Core 2) What ...


8

SPECK was actually designed with 8-bit CPUs in mind. I use Simon and Speck extensively, and there's example source code and comparisons out there, as well as a good paper. The references are good and will lead you the the original sources. AES is generally faster but takes more resources, which you may or may not have. I do not use AES on a MCU because ...


8

Poly1305 is not based on AES, it was used together with AES in Bernstein's first description http://cr.yp.to/mac/poly1305-20050329.pdf. For pseudocode of the Poly1305 algorithm see e.g. https://tools.ietf.org/html/rfc7539#section-2.5.1. GHASH is the 'hash function' in AES/GCM. So if Poly1305 is faster than GHASH on some hardware this is no contradiction. ...


7

In RSA encryption as practiced (that is, to encipher a message which is a short symmetric key), the message size after padding is fixed and equal to the modulus size. Thus the size of the message has no impact on performance. Calculating a modular inverse is performed only during key generation, that is seldom. Also, it has low cost compared to generating ...


7

Computations on elliptic curves are more efficient. Roughly speaking, when the base field has size $n$ (for DH/ElGamal/DSA, the size in bits of the modulus $p$; for elliptic curves, the size of the field for point coordinates) and a "security level" $t$ (e.g. $t = 80$ for "80-bit security" as can be expected when using a 160-bit subgroup and a 160-bit hash ...


7

Given the choice, it is preferable to use the block encryption operation of AES, since it often faster than block decryption (never slower AFAIK). For this reason, AES-CTR is defined to use the block encryption operation of AES exclusively; that's both for AES-CTR encryption and AES-CTR decryption, which are the same operation except for IV generation/input. ...


7

Yes, AES-128 is intended to be the standard block cipher for building a secure and efficient symmetric cryptosystem using some block cipher operating mode, like CTR for encryption or GCM for authenticated encryption; efficiency can be particularly good when there is hardware support for AES and GCM. There might be better choices in the case at hand, like ...


7

Dedicated stream ciphers typically are, or at least can be, somewhat faster than constructions based on block ciphers. (If they weren't, there would be no point in using them, since a block cipher can do everything a dedicated stream cipher can.) What you gain in speed (and possibly code size), however, you lose in versatility: A block cipher (in CTR / ...


7

The previous answer has the correct formula for estimating the security level of prime field elliptic curves. However, the table seems to just list the closest Koblitz curve sizes used, as Richie Frame points out. If you computed the actual security strength of the curves in question, you would not end up with exactly the values in the left column. For ...


7

All hashes I know of are block oriented. The time required to calculate the hash scales with the number of blocks to be hashed. There is a small constant overhead dealing with the IV and, possibly, a finalization function.


6

Predicting speed by looking at the assembly is hard, especially since processors do all sorts of tricks which have memory (e.g. branch prediction). So yes, this is all about measuring. There is an art to it; for instance, you would rather repeatedly encrypt the same relatively small buffer (4 or 8 kB) so as to avoid cache effects. One method is to do the ...


6

They measure it. Once upon a time, CPUs were simple enough that you really code compute the amount of time for a stretch of code by looking up the clocks per instruction in the manual, add them all together, and that'd be the total time. However, CPU manufacturers have added more and more optimizations and parallelism; this makes the CPUs run faster (for ...


Only top voted, non community-wiki answers of a minimum length are eligible