2
$\begingroup$

I'm looking for a general comparison of encryption algorithms in regard to Confusion and Diffusion (as defined by Claude Shannon), and if possible, specifically for their SAC and BIC quality.

For example, xor-streaming ciphers have no (0, zero, zilch) diffusion - you switch 1 bit in the ciphertext, you know which single bit in the plaintext after decryption will be flipped.

Most ciphers, especially block ciphers do have diffusion and confusion. But how much? That's the values I'm looking for. And I wonder why no such table exists yet. So, after some searching, I'm asking here.


I'm thinking of something like

Algorithm SAC average SAC min SAC sq.d. BIC average BIC min BIC sq.d.
AES 0.484 0.504 0.018 112 112 0

but for all the Usual Suspects like Twofish, RC5, IDEA, and so on.

If testing isn't that difficult, I wonder why I couldn't find such a table here, on research sites, or via web search.

I've found only individual calculations¹, related summaries, and related questions so far, but an overview would be useful - not just for me, I think.


¹ e.g. in Hussain, Dr & Jamal, Sajjad Shaukat & Shah, Tariq & Hussain, Iqtadar. (2020). A Power Associative Loop Structure For The Construction Of Non-Linear Components Of Block Cipher. IEEE Access. PP. 1-1. 10.1109/ACCESS.2020.3005087. https://ieeexplore.ieee.org/document/9125911 and for Hash functions only: Smriti Gupta, Sandeep Kumar Yadav. Performance Analysis of Cryptographic Hash Functions. ISSN: 2319-7064 https://www.ijsr.net/archive/v4i8/SUB157467.pdf

$\endgroup$
8
  • 2
    $\begingroup$ AFAIK, Strict Avalanche Criterion is computable only for small substitution tables, not block ciphers. It's unclear what could be tested for RC5 and IDEA that have no S-table, and even for Twofish that has no fixed S-table. Shortly after AES (and arguably, too late) S-tables got somewhat deprecated for software-friendly ciphers, because they open to cache-based timing/leakage attacks. Apocryphal note: this is about a former version of the question. $\endgroup$
    – fgrieu
    Mar 15, 2023 at 15:20
  • 2
    $\begingroup$ For every block cipher worth consideration, no statistical testing of the whole block cipher as a black box reveals any deviation from the statistical normal, because by definition that's a break of the block cipher. Tests on a few rounds of a block cipher can be performed with meaningful results, but comparisons at equal number of rounds are not meaningful (especially between permutation-substitution ciphers like AES, and Feistel ciphers like Twofish or RC5). $\endgroup$
    – fgrieu
    Mar 15, 2023 at 15:37
  • 1
    $\begingroup$ On “The quality of diffusion any encryption generates should be measurable, no?” : No, the quality of diffusion that encryption generates is not measurable past a certain threshold, and unbroken ciphers are way above this threshold. $\endgroup$
    – fgrieu
    Mar 15, 2023 at 16:56
  • 1
    $\begingroup$ @fgrieu has made some valuable points. also, the only publically accessible (non paywall) paper you link to is worthless in terms of the testing it supposedly does. It doesn't even specify how many samples were used and what the exact testing method was. $\endgroup$
    – kodlu
    Mar 15, 2023 at 18:39
  • 1
    $\begingroup$ @kodlu I know; and the other sources weren't satisfying, either. And these are the best I could find. So I am asking here. (I tried to do the Do Your Research bit before posting my question.) $\endgroup$
    – foo
    Mar 15, 2023 at 18:43

1 Answer 1

4
$\begingroup$

xor-streaming ciphers have no (0, zero, zilch) diffusion - you switch 1 bit in the ciphertext, you know which single bit in the plaintext after decryption will be flipped.

Indeed, there is no plaintext to ciphertext diffusion in a stream cipher. But that's by design, and not a weakness when the Initialization Vector changes at each use as it's hypothesized to do. So this consideration of plaintext to ciphertext diffusion is not meaningful to compare stream ciphers. The corresponding metric that matters for these is IV to keystream diffusion.

I'm looking for a general comparison of encryption algorithms in regard to Confusion and Diffusion (as defined by Claude Shannon), and if possible, specifically for their SAC and BIC quality.

For modern unbroken ciphers, it's impossible to make such comparison based on experiments with the cipher tested as a black box, because the moment we could prove a cipher A lesser than a cipher B on some meaningful criteria, cipher A would be broken, by definition of broken and meaningful. Something like diffusion from plaintext to ciphertext (for block cipher) or IV to keystream (for stream cipher) would be meaningful, but we can't practically measure that experimentally for a practical cipher: it's immensely too compute-intensive.

In fact, we can't make any measure that experimentally distinguish ciphertext or keystream of one cipher from that of another cipher (under hypothesis on format that is met in practice), unless one of the two is broken or we know it's key. Therefore, efforts in the direction of the question must allow examination of the inside of the cipher.

One of the metric for comparison among ciphers consisting of essentially identical rounds (as most modern ones are) could be: define the better cipher has the one with the highest security margin for a certain experimental test, defined e.g. as $r/r'$ where $r$ is the number of rounds in the cipher, and $r'$ is the smallest number of rounds such that the experimental test can not distinguish the cipher from a perfect one. Some problems with this approach:

  1. We know some ciphers that are unbroken for $r_1$ rounds but break abruptly for some $r_2>r_1$ rounds, including at least one where this has happened by accident (I wish I could remember which). We could actually live with that issue, because we have some insight on why it can happen, and hope we know how to design a cipher to avoid it.
  2. Knowing a simple test, it's reasonably easy to make a cipher with a high security margin (even if we add some speed constraint or upper limit on $r$), but we know that does not give any assurance of security, because sometime a different test will uncover a devastating weakness the original did not.
  3. If we allow complex rounds, we know how to make a cipher that's unbreakable by any fixed test for $r'=1$ round, yet is trivially breakable for any number $r\ge1$ of rounds with a new test devised with knowledge of (a constant in) the algorithm. There demonstrably is no workaround to that one!
  4. An actual cryptanalyst tailors attacks to the cipher, and that's known to often make the attack immensely more effective than a generic one, but that varies immensely.

All that combined, security margin for a certain experimental test is a poor metric to rank ciphers. This approach only works, somewhat, to compare ciphers with simple and comparable rounds. It's used to some degree to tune parameters of a class of ciphers; like, determining number of bits in rotations in ARX ciphers.

Currently, the only known way to improve that strategy for the variety of ciphers around is to modify the criteria to security margin for the best experimental test devised by experts in cryptanalysis after examining the cipher in detail. This is somewhat part of how AES (and the SHA-3 hashes) are chosen. But that process takes years of efforts by multiple experts in cryptanalysis. AI could conceivably help there, but I don't know that it's ready for that yet.


Summary: there are attempts at ranking of ciphers. But those that pretend to rank unbroken ciphers by black box testing are flawed. Even when opening the cipher, I know no automated sound alternative.

$\endgroup$

Your Answer

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

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