Score:4

What would be the requirements for a new-age cipher standard?

in flag

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)
Maarten Bodewes avatar
in flag
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.
Joseph Van Name avatar
ne flag
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.
the default. avatar
id flag
@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?
Joseph Van Name avatar
ne flag
@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.
Score:-1
ne flag

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.

Richie Frame avatar
cn flag
"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?
Joseph Van Name avatar
ne flag
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).
Fractalice avatar
in flag
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
Joseph Van Name avatar
ne flag
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.
Joseph Van Name avatar
ne flag
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.
Score:-4
cn flag
  • 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.

Richie Frame avatar
cn flag
Documentation referenced AES with an expected retirement age of 2030, sometime in the next few years there may very well be a replacement competition
the default. avatar
id flag
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.
Paul Uszak avatar
cn flag
@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.
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.