4
$\begingroup$

While nowhere near being broken, AES has known attacks like reading from the substitution table, memory-based attacks, etc.

If we keep getting better at breaking ciphers and we eventually get close to taking AES down, what would (in your opinion) be the requirements for a cipher of an era where even Rijndael isn't safe enough?

I'm talking about:

  • key sizes
  • data sizes
  • design (stream/Feistel/PSN, or something else?)
  • what techniques should not be used (like because of exposing data in memory)
$\endgroup$
4
  • 1
    $\begingroup$ What do you mean with "memory based attacks" and "exposing data in memory" exactly? As it seems that this replacement algorithm needs to protect against those. $\endgroup$
    – Maarten Bodewes
    Sep 25 at 23:55
  • $\begingroup$ When AES retires for whatever reason, it will probably be time to use a block cipher designed to run on reversible hardware or software. This means that encryption should be done completely reversibly without any need for uncomputation except for rewinding the key schedule. $\endgroup$ Sep 26 at 0:42
  • $\begingroup$ @Joseph why? As far as I understand, reversible computing is completely theoretical and that is unlikely to change. And what does reversible hardware of software, assuming it will exist at some point, gain from a decryption algorithm that doesn't require any changes except for rewinding the key schedule? $\endgroup$ Sep 26 at 4:39
  • $\begingroup$ @thedefault. Researchers have been working on making reversible computing hardware since the 1990's, so it is hard to call that 'completely theoretical'. Reversible computation usually has a memory/time overhead, so it is best for an encryption algorithm to get rid of this overhead. $\endgroup$ Sep 26 at 4:54
-1
$\begingroup$

Nearly reversible computation will eventually replace conventional computation since reversible computation will be more energy efficient than conventional computation. Furthermore, symmetric encryption and decryption are very well suited for reversible computing, so we should expect for symmetric encryption and decryption to eventually be computed on reversible hardware or software. We should expect for future block ciphers to be eventually evaluated based on their performance on reversible hardware and reversible software. In fact, the advent of reversible computation will likely cause people to retire AES in favor of a more reversible block cipher before people would want to retire AES based on security concerns.

Reversible computing ubiquitously uses a technique called uncomputation which amounts to running the computation in reverse in order to clean up all the garbage information produced by the computation. A block cipher that is designed for reversibility should run on reversible hardware or software without any need for any uncomputation except for possibly the key schedule. In other words, in a block cipher that is designed for reversibility, not only must the encryption and decryption functions be invertible, but all of the components that compose the encryption and decryption functions should also be invertible. The process of uncomputation takes computational resources that are not being spent creating confusion and diffusion but are instead being spent reducing the amount of confusion and diffusion. Feistel ciphers tend to require some uncomputation while substitution-permutation networks do not require uncomputation (the most important component of a Feistel cipher is not invertible), so substitution-permutation networks will be more suitable for reversible computation.

It is probably a good idea for researchers to investigate reversible block ciphers right now to best prepare for encryption using reversible computers.

$\endgroup$
5
  • $\begingroup$ "running the computation in reverse in order to clean up all the garbage information produced by the computation" exactly what garbage information is produced by a block cipher? $\endgroup$ Sep 26 at 5:36
  • $\begingroup$ In a Feistel cipher, computing the mapping $(x,y)\mapsto(x\oplus f(y),y)$ reversibly usually produces information that must be uncomputed and possibly garbage information. A reversible computer would therefore compute $(x,y)\mapsto(x,f(y),G(y))\mapsto(x\oplus f(y),f(y),G(y))\mapsto(x\oplus f(y),y)$; here $G(y)$ is the garbage information produced when computing $f(y)$ (in particular, the mapping $y\mapsto(f(y),G(y))$ is injective). $\endgroup$ Sep 26 at 8:41
  • $\begingroup$ could you please elaborate about such computers (where are they)? there are many ciphers targeting low energy but I for the first time hear about the relevance of "reversible" computations for the energy consumption $\endgroup$
    – Fractalice
    Sep 26 at 19:29
  • $\begingroup$ With irreversible computing, it takes $kT\ln(2)$ to delete 1 bit of information; here $k=1.38\cdot 10^{-23} J/K$ is Boltzmann's constant, and $T$ is the temperature. In practice, one should expect to delete $100 kT$ to $1000kT$ energy per bit deleted. With reversible computation, one saves this energy by deleting very little information. $\endgroup$ Sep 26 at 19:59
  • $\begingroup$ Reversible computation was not relevant in the past since the energy required per logic gate operation was very far away from $kT$ and because there were better ways than reversibility to improve performance. But reversible computation will be relevant for the future of computing. $\endgroup$ Sep 26 at 20:02
-3
$\begingroup$
  • Can you categorically prove that AES isn't broken today, or won't be in October 2021? See NOBUS.

  • The one time pad with key size = message size. Facilitated via quantum key distribution. That's one of the the main areas of cryptographic research today in budgetary terms.

$\endgroup$
3
  • $\begingroup$ Documentation referenced AES with an expected retirement age of 2030, sometime in the next few years there may very well be a replacement competition $\endgroup$ Sep 26 at 0:49
  • $\begingroup$ There isn't a lot of space for hiding a backdoor in AES (unless it's some general attack that someone knows, but nobody else noticed for >20 years, which doesn't sound very likely, given that all other current attacks are very far from breaking it), and it's unlikely that future ciphers will somehow have even less space for backdoors. $\endgroup$ Sep 26 at 4:52
  • $\begingroup$ @thedefault. Sorry, you've misunderstood. I'm not suggesting any back doors. I'm suggesting a direct inversion of AES via mathematics, e.g. re-linearisation. And your missing the point with user confidence; just prove to me that AES isn't broken by either the NSA or Guoanbu. These are the largest employers of cryptographers in the world. Remember differential cryptanalysis. Why do you think that government agencies still use on time pads? And please please read about NOBUS and dwell on it's implications. $\endgroup$
    – Paul Uszak
    Sep 26 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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