3
$\begingroup$

In AES competition,Rijndael cipher obtained first rank and become Standard and Serpent, Twofish, RC6 and MARS obtained another ranks and I know that Serpent took second rank because it was slower than Rijndael.

My questions are:

  • Is Rijndael the fastest block cipher in the world?
  • What is the reason of 10 negative votes for Rijndael in AES2 conference?
  • What is the fastest block cipher in the world? (for software implementation on Intel processor)

In my question, suppose that I implement all known block ciphers with equality of condition (key size, block size, software implementation on PC) then which secure block cipher is fastest?

$\endgroup$
8
  • 7
    $\begingroup$ I think that the question lacks of context... Are you asking about a software implementation? an hardware one? AES has a no negligible advantage: being a stardard, CPUs contain specialized instructions to compute faster the algorithm. $\endgroup$
    – ddddavidee
    Apr 21, 2016 at 15:19
  • $\begingroup$ Define the fastest, secure cipher and I define one with a single round less. $\endgroup$
    – Maarten Bodewes
    Apr 21, 2016 at 20:21
  • 3
    $\begingroup$ and how does one define "secure"? matching the 100+ year potential security of AES candidates? 112-bit classical security as currently required by NIST? 128-bit post quantum? $\endgroup$ Apr 21, 2016 at 20:47
  • $\begingroup$ Depends on the CPU, using AES-NI instructions AES is very fast (especially AES-128). $\endgroup$ Apr 22, 2016 at 7:33
  • 2
    $\begingroup$ Which Intel Processors? Do they have AES-NI (e.g. Sandy Bridge or newer)? Do they have AVX (e.g. Sandy Bridge or newer)? Are they even 64-bit? Do they have AVX2 (Haswell or newer IIRC)? Do they have SHA-Extensions (TBA)? Do they have AVX512 (TBA)? $\endgroup$
    – SEJPM
    Apr 22, 2016 at 13:57

3 Answers 3

13
$\begingroup$

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 have a hard time getting anything faster than AES, because of specialized opcodes -- although you could define a block cipher that is identical to AES except that it has 9 rounds instead of 10. That alternate block cipher would be faster and still secure, but with less "security margin", an intuitive but very poorly defined notion.

During the AES competition, Rijndael was outperformed on some platforms, e.g. on the PC of that day, RC6 was faster. But Rijndael offered the most consistent performance on platforms of that era: there was no software platform (including 8-bit CPU) were it was abysmally slow, and it was perceived to be reasonably hardware-friendly (contrary to, say, RC6).

$\endgroup$
2
  • $\begingroup$ Thanks! except RC6,is any secure block cipher faster than Rijndael(with above conditions)? $\endgroup$
    – user29529
    Apr 23, 2016 at 13:57
  • $\begingroup$ Is the identity function really considered a cipher though? $\endgroup$
    – forest
    Apr 1, 2018 at 2:20
8
$\begingroup$

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 is the reason of 10 negative votes for Rijndael in AES2 conference?

I can't give a definitive answer on that one because I haven't been there actually to capture the general mindset of the people.
However, I can see why people voted against Rijndael. It was considered much weaker than Serpent (Rijndael: 1.6 coefficient of rounds divided by broken rounds whereas Serpent was at 3), it only got evaluation as "adequate security" whereas three others got "high security" and so people likely feared that Rijndael would get broken at some point. The main bonus for Rijndael was its higher software speed compared to Serpent (which would have excelled only with decdicated hardware) and it's simpler design (which was considered to be a potential weakness) compared to Twofish and Serpent.

What is the fastest block cipher in the world? (for software implementation on Intel processor)

This is really difficult to answer.
Threefish generally has really good performance on x64 and is likely the fastest software-only block cipher on x64 CPUs without AES-NI.
If you don't have a hard requirement for a block cipher, ChaCha20 would be the way to go with a solid 2cpb on a Sandy Bridge as per the benchmark.
Note however, that AES will outperform any other cipher on such a modern CPU in a realistic scenario, because AES-NI is built-in hardware acceleration (via special ASM instructions) and can get AES performance up to less than 1cpb on very new CPUs.

$\endgroup$
2
  • 1
    $\begingroup$ ChaCha isn't really a fair comparison, since it's only an unkeyed permutation, not a block cipher. Adding a key schedule costs some performance. I think @orlp got down to 2-3 cpb using SSE2 to implement a Blake2s derivative in OCB mode (10 rounds, corresponding to 20 ChaCha rounds). $\endgroup$ Apr 23, 2016 at 14:47
  • 1
    $\begingroup$ On a Core2, Kasper and Schwabe implemented AES at 7.59 cpb, which is substantially better than 11 cpb. This implementation runs 8 instances in parallel, which is fine for CTR, not so much for CBC encryption (CBC decryption can be done in parallel, though); as an added bonus, it is constant-time. $\endgroup$ Apr 23, 2016 at 20:46
3
$\begingroup$

The speed of a cipher actually depends on lots of factors, including:

  1. The specific hardware platform you're considering (CPU architecture, instruction set, number of cores etc).
  2. Implementation details.
  3. Compiler flags used.
  4. Some ciphers have a large initial overhead due e.g. to a slow key setup; as a result they are slow when encoding very small messages.

Is this relevant to you? Or you're only interested in the asymptotic speed for large messages?

There is a large 2008 analysis of block cipher speeds in crypto libraries by one Timo Bingmann

Jump to the table in section 5.1.1 for a summary. You'll see that there is quite a lot of variation across libraries in relative speed. Blowfish overall could be considered the fastest cipher, but uses a 64 bit block and this disqualifies it from the comparison. Among 128-bit ciphers AES has the fastest implementation (40.1 MB/s in the Tomcrypt library) followed by Twofish (35.5 MB/s also in Tomcrypt). Serpent is usually slow (~15MB/s) but has a very fast implementation in the Botan library (30.2 MB/s) using bit-slicing.

For a more recent comparison you can also check this master's thesis `Block Ciphers: Fast Implementations on x86-64' by Jussi Kivilinna This guy produced assembly implementations of a few block ciphers. On an Intel sandy-bridge i5-2450M CPU these are the speeds on his fastest implementations in cycles/byte (lower is faster):

AES 1.35 (uses AES-NI);
AES 5.83 (no AES-NI);
Camellia 5.32 (uses AES-NI);
Blowfish 9.53;
Twofish 9.93;
Serpent 10.30;
Camellia 14.10 (no AES-NI);

Note that there are other factors besides raw speed when considering implementations of ciphers (resistance to side-channel attacks and probably a million of other things).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.