Join Log in
Score:1
J. Doe avatar Crypto

Can a block-cipher considered secure if a bit-change of the input leads to a 50% chance change for every single output bit? -> round number?

at flag
J. Doe

Block-cipher use self-inverse ($f(f(x)) = x $) operations which then will be applied to the plaintext and most likely contain some constants which can be based at a key. To get security such operations which interpret the input in different ways are aligned to each other. This process gets repeated multiple rounds with different keys. In optimal case a random input lies inside a closed cycle (if block-cipher applied over and over again) with a random cycle size (uniform, given random key).

By testing around I noticed this can happen with just some very simple operations of XOR, Bit-Rotation and addition. (called ARX)

E.g.: for one round with input $m$:

$$ m = XOR(m, R_i) \\ m = RotateBit(m,5) \\ m = m + K_i $$

$R_i, K_i$ are round keys for round $i$.

  • XOR alone is not secure because that operation is just at single bits without impact to each other.

  • Bit rotation is added to increase the impact of a single bit to every other bit. At its own also not secure because it has only impact at single bits each

  • Addition is added as as 2nd kind of input interpretation (as number instead of bits). Here the bits can impact each other.

With this I got some good (but not perfect) uniform distribution of the different cycle lengths (given random key and input).

The question is how many rounds need to be applied for security? It need to be at least the total bit-size so every bit can reach every other position due to bit rotation.

Here is some related thread for AES.

But as a more general metric (for custom block-cipher) can the security measured with the impact of a bit change in the input to every bit of the output?

In optimal case every possible bit change of every possible input should lead to 50% different bits at the output (with each bit being different to same amount).

The round number can be increased until it reaches a suitable level of security.

89
0 + 0
aes
user2357 avatar
us flag
user2357
To the best of my knowledge, sensitivity to the plaintext is necessary condition, not sufficient condition.
0
Reply
kelalaka avatar
in flag
kelalaka
Related [Is there block cipher that is secure for n round but not secure when the rounds increased](https://crypto.stackexchange.com/q/91929/18298)
0
Reply
Score:2
SAI Peregrinus avatar Crypto
si flag
SAI Peregrinus

But as a more general metric (for custom block-cipher) can the security measured with the impact of a bit change in the input to every bit of the output?

Trivially no. If the block cipher's round function is linear, then no number of rounds will make inverting it any more difficult.

You also didn't describe whether you're talking about Confusion, Diffusion, or both.

Confusion defines a relationship between the key and the ciphertext: each bit of the ciphertext is dependent on many bits of the key, so that if any bit of the key is changed approximately 50% of the bits of the ciphertext will change.

Diffusion defines a relationship between the plaintext and the ciphertext: each bit in the ciphertext is dependent on many bits of the plaintext, so that if any bit of the plaintext is changed approximately 50% of the bits of the ciphertext will change.

Both are necessary, but not sufficient, for security. When combined with a non-linear round function you might get a decent block cipher, but even then it's possible for information to leak resulting in insecurity.

Also, block ciphers on their own are only at best IND-CPA secure (the weakest form of security) if exactly one block is encrypted with any given key. More blocks being encrypted means that any two identical plaintext blocks will have identical ciphertext, which is a break in the indistinguishability. To be IND-CPA secure a mode of operation like CTR mode (turning it into a stream cipher) or CBC mode (chaining ciphertext blocks) is required. But even that isn't "secure", since an attacker can alter the ciphertext and cause a victim to decrypt to get incorrect plaintext, so an Authenticated Encryption mode is needed for proper IND-CCA3 security. That'd be something like GCM, SIV, GCM-SIV, or OCB mode. And even that has some caveats, since such modes require a "nonce" (Number used ONCE) that eliminates (GCM, OCB) or reduces (GCM-SIV, SIV) security if re-used.

0 + 0
user2357 avatar
us flag
user2357
I think the confusion is related to the relationship between the key/plaintext and the ciphertext to be covered, whilst the diffusion is related to the spread of the changes of the key/plaintext in the ciphertext, am I right?
0
Reply
J. Doe avatar
at flag
J. Doe
Thank you for the response. I'm not 100% convinced yet (but enough that this won't work in practice). I did some mistake to not exactly specify what is given and what is wanted (given: min 1 non-linear+ min 1 other operation which interpret the input different, at least that many rounds that every bit of the plaintext/key can have an impact at every bit of the cipher, wanted:IND-CPA security enough for this case). However you convinced me the statistics need to be done much more detailed than expected. For example a given bit could always be 1 if another bit of the plaintext/key is 1 as well.
0
Reply
J. Doe avatar
at flag
J. Doe
Bit-wise statistics won't be able to track this. For a given bit value at a certain position the chance of change in the ciphertext need to be tracked for each member of the power set of all other bit values (except full set) which is infeasible in real application. E.g. chance for change of the first bit from 1 to 0 given the 3rd & 6th bit is 1 and 7bit is 0. Assuming this kind of statistic has be done and about 50% for each member of the power set is achieved: do you still see the possibility for information being leaked (if yes, some example pls)?
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.