22 votes

Why is the permutation in AES (and other ciphers) not random or key-dependent?

You have clarified the question as asking about whether replacing ShiftRows with a random byte permutation would strengthen AES against differential attacks. It would not. ShiftRows and MixColumns ...
J.D.'s user avatar
  • 4,415
18 votes
Accepted

Understanding the wide trail design strategy

Given the importance of the wide-trail strategy in modern symmetric-key cryptography, this question really deserves an answer (and a much better score). Since nobody else has tried, I'll give a brief ...
Aleph's user avatar
  • 1,856
10 votes

Why is the permutation in AES (and other ciphers) not random or key-dependent?

I assume that you mean the S-box. The answer is NO! Randomly chosen S-boxes are not good choices for differential and linear cryptanalysis. When Biham and Shamir presented differential attacks on DES, ...
Yehuda Lindell's user avatar
9 votes
Accepted

Selection of rotation constants in ARX design

Leaving besides that the designers (NSA) of Simon and Speck did not provide an initial design rational for their ciphers/parameter choices, they added some notes later after pressure from the ...
TheBananaMan's user avatar
7 votes
Accepted

In differential cryptanalysis for DES, why is F(0...0) assumed to be always 0...0?

The question arises from a misunderstanding: The attack described in the paper does not work with actual inputs and outputs, but with differences between them. Hence Differential Cryptanalysis. ...
Emiswelt's user avatar
  • 181
7 votes

What is a differential trail?

Imagine you have a function like this: $$f(x) = p_3(p_2(p_1(x))).$$ Now imagine that you find a pair $\Delta_0, \Delta_1$ such that $p_1(x \oplus \Delta_0) = p_1(x) \oplus \Delta_1$ with probability $...
Samuel Neves's user avatar
  • 12.4k
7 votes
Accepted

Security of the AES with a Secret S-box

Are the S-boxes they are considering just random permutations of bytes that fit into an 8×8 table? How might they have chosen all the entries to get the S-box? Yes, they chose a random s-box. Are ...
Richie Frame's user avatar
  • 13.1k
6 votes
Accepted

How can one construct the weakest S-box ever?

Any affine function will do. Let your Sbox be $$S(x)=Mx\oplus c$$ where $M$ is an $n\times n$ binary matrix and $c$ is an $n-$bit constant vector. The output difference for this Sbox is, for any ...
kodlu's user avatar
  • 21.9k
6 votes
Accepted

Does CPA-secure means security against differential cryptanalysis?

Differential cryptanalysis is a tool which is used to analyze symmetric primitives such as block ciphers and cryptographic hash functions. So it is applicable to CPA secure symmetric encryption ...
dade's user avatar
  • 1,323
5 votes
Accepted

Is the difference distribution table of AES S-box uniform?

The difference distribution table for the AES s-box contains mostly probability 2/256 differentials. However, there is a single probability 4/256 for each input/output difference. I uploaded a dump of ...
Ella Rose's user avatar
  • 19.6k
5 votes
Accepted

Differential Cryptanalysis for Hash functions

In the case of block ciphers, differential cryptanalysis aim to measure the changes between inputs and outputs with a probability. The goal is to predict what the result will be before the last round ...
Biv's user avatar
  • 9,979
5 votes

Best complexity of guessing difference of AES-256 outputs

Without further information, your question is overwhelmingly likely to be insoluble. Given $m_1$, $m_2$ and $c_1$ we expect there to be roughly $2^{128}$ 256-bit keys $k$ such that $\mathrm{AES}_k(m_1)...
Daniel S's user avatar
  • 22.8k
4 votes

Best differential characteristic for this PRF

The function $f$ is biased towards the complement of the input $c_{i,j}$, assuming the other two inputs are approximately randomly distributed. As all the values $c_{i,j}$ are public, this means ...
poncho's user avatar
  • 146k
4 votes

differential cryptanalysis cipher for the final round

Remark: The round function of your toy cipher is the following. ...
Biv's user avatar
  • 9,979
4 votes
Accepted

What is the difference between strong/weak alignment?

Truncated differential cryptanalysis was introduced by Lars R. Knudsen at FSE 1994. The Keccak team provides an summary of this technique as follows: In truncated differential cryptanalysis one ...
Biv's user avatar
  • 9,979
4 votes
Accepted

What is the meaning of Maximum Expected Differential/Linear Probability (MEDP/MELP)?

The paper you link to gives precise definitions for the MEDP and MELP. I will attempt to explain the definitions more expansively & clearly. First, the differential probability (DP) function ...
J.D.'s user avatar
  • 4,415
4 votes
Accepted

How is the SHA-1 collision detector so fast?

One trick used by the collision detector you mention is to check for "unavoidable conditions", described in the paper here: http://oai.cwi.nl/oai/asset/23932/23932A.pdf Essentially, the unavoidable ...
William Luc Ritchie's user avatar
4 votes
Accepted

What is the point of differential cryptanalysis when the amount of necessary plaintext is unrealistic?

Differential cryptanalysis is a very powerful technique that permitted highly practical attacks on many ciphers that were not designed to resist it (e.g. FEAL-4). DES, as it turns out, was designed ...
J.D.'s user avatar
  • 4,415
4 votes

What is an advantage of MDS matrices in block ciphers?

They said that, one goal of MDS matrices is to protect the block ciphers against linear and differential attacks. That would probably depend on the cipher, but in generally, pretty accurate. is ...
poncho's user avatar
  • 146k
4 votes
Accepted

Why is variable rotation uncommon in cryptographic primitives?

One issue is that data-dependent rotations (such as you describe) is patented by RSA data security (or, at least, was, the patent may have expired). RC5 and RC6 was created by the holder of this ...
poncho's user avatar
  • 146k
4 votes

Security of the AES with a Secret S-box

A random 8 bit permutation has $log_2(256!)=1684$ bits of information in it. Add thar to the regular AES key and you get the required number. You would not need/want to change the s box. You ...
Meir Maor's user avatar
  • 11.8k
4 votes
Accepted

Differential and Linear trail propagation in Noekeon

This is due to the duality between linear and differential trails. Let $L$ be an invertible linear map on $\mathbb{F}_2^n$, think of it as a matrix for convenience. In general, a nonzero differential $...
Aleph's user avatar
  • 1,856
4 votes
Accepted

Why the differential cryptanalysis complexity is linear with inverse of the probability while linear cryptanalysis is quadratic with the bias inverse?

What I don’t get is why the complexity became quadratic in linear case? Well, in linear cryptanalysis, for each input, we get a bit with a bias of $0.5 \pm \epsilon$, and we need to determine if that ...
poncho's user avatar
  • 146k
3 votes

Why is the permutation in AES (and other ciphers) not random or key-dependent?

I made a toy cipher that functioned in this manner. It had a bytewise transposition step that was performed by an invertible randomized permutation, similar to the Fisher-Yates shuffle, but easily ...
Ella Rose's user avatar
  • 19.6k
3 votes
Accepted

Can I use a differential that can be traced through the whole cipher with 100% probability?

Usually differential cryptanalysis relies on something called the "wrong key randomization hypothesis", which is the assumption that decryption of the last round with the wrong key results in a random ...
J.D.'s user avatar
  • 4,415
3 votes

What is the point of differential cryptanalysis when the amount of necessary plaintext is unrealistic?

Anyone who begins to develop an attack on primitive XYZ is probably not aware beforehand of what the computational complexity of their attack will turn out to be. Then, the attack is developed and ...
Ella Rose's user avatar
  • 19.6k
3 votes
Accepted

Finding differentials and space complexity

If such a large Sbox with no structure were to be analysed you'd treat the analysis as a one-off precomputation. Considering only classical differential cryptanalysis as an example, after the ...
kodlu's user avatar
  • 21.9k
3 votes
Accepted

Compression function cryptanalysis

Are there any standard/general techniques for determining an unknown compression function, given the input-output pairs? This appears to fall under the realm of reverse-engineering rather than ...
Ella Rose's user avatar
  • 19.6k
3 votes

What does it mean : "Canonical representative of Sbox is 0123468A5BCF79DE"? and How can we calculate this representative for Sbox?

Let's start with the basics: a bijective 4×4 bit S-box is a permutation of the set $\{0,1\}^4$ of 4-bit bitstrings. These bitstrings can be viewed as the binary representations of the integers ...
Ilmari Karonen's user avatar
3 votes

Recover all keys on differential cryptanalysis

Generally, if you want to recover k4, you will need to use a 4-round differential trail rather than the same 5-round trail you used for k5. This is because when you generated the pairs for the latter ...
JST's user avatar
  • 31

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