4
$\begingroup$

From my limited research into this topic, it seems that AES can be brute-forced. One-time pad, on the other hand, cannot. Why then is it better to use AES than it is to use one-time pad? The only answer I have come to is performance, but this doesn't seem quite right.

$\endgroup$
4
  • 3
    $\begingroup$ How much keying material must be securely exchanged to transmit a 1 Megabyte message with AES? With one-time-pad? $\endgroup$
    – poncho
    Sep 26, 2022 at 10:29
  • $\begingroup$ So it is just performance and logistics then? $\endgroup$ Sep 26, 2022 at 10:30
  • 1
    $\begingroup$ @DarcySutton A one-time-pad can actually be brute forced if you have enough data. For instance, if you know anything about the plaintext, you likely can extract the key. $\endgroup$
    – b degnan
    Sep 26, 2022 at 13:05
  • 2
    $\begingroup$ @bdegnan That's not a problem, and neither is it brute force. Extraction of key bits will get you nowhere as they are only used to protect the part of the plaintext that you already know. This is in contrast with a cipher such as AES, where known plaintext can help by validating a guessed key which is also used for other parts of the message. Of course, a block cipher should protect against guessing the key in the first place, but if you can validate the key then the cipher is not information-technically secure. $\endgroup$
    – Maarten Bodewes
    Sep 26, 2022 at 23:39

3 Answers 3

6
$\begingroup$

For One Time Pad (OTP), you need to distribute the key. Consider that you want to send 1GB of encrypted data. In this case, beforehand you need to generate 1GB uniform random key and distribute it to the other party in a secure way. Do you see the problem now? Now, start using it, even before you start to use it, pretty sure you will leave it aside!

The other main problem with the OTP is the depletion of the one-time key. What will you do? Wait or Reuse? Both have problems. The first one leaves you out of touch/order/sync and the other will have catastrophic results; loss of the perfect secrecy with the two-time pad attack as done in history (Venona project) or now automatized.

See also these nice Q/As from our site;

  1. Taking advantage of one-time pad key reuse?
  2. How does one attack a two-time pad (i.e. one-time pad with key reuse)?
  3. Little problem with Vernam Cipher

Now instead of some mentioned problems of OTP, consider this;

  • Both parties have public and private keys 1;
  • Exchange keys with ECDH ( or choose one of the candidate post-quantum schemes) to have forward secrecy ( ECDH, ECDH has only secure against classical adversaries, Shor's algorithm beat Dlog, too ).
  • Use KDF on the exchanged key
  • Encrypt with AES-GCM-SIV ( or XChaCha20-Poly1305) so that one has
    • Confidentiality,
    • Integrity, and
    • Authentication

Here, GCM uses CTR mode that uses computational security instead of perfect secrecy. Yes, There are still pitfalls to using AES-GCM incorrectly

OTP on the other hand has only confidentiality. Yes, one can use OPT-HMAC to provide Integrity and Authentication, however, you left the perfect secret domain. To stay on the on the path you need Information Theoretic MACs ( for example the ones from strong universal functions (SUF) - see chapter 6).

AES can be brute-forced.

Even AES-128 withstand all attacks for more than 20 years. Direct brute forcing will take around $2^{35}$ years even if you combine all the Bitcoin miner's powers on brute-forcing AES. It is safe against the classical attacker, however, to be safe against quantum adversaries use AES-256 so that one can withstand even against the optimal Grover's algorithm.


1Well, not that easy of course! To be sure that you are correctly communicating with the other part one either uses TOFU ( Trust On the First Use) like Signal or degraded WhatsApp or well-established certificates. This is the top of the rabbit hole!

$\endgroup$
2
  • $\begingroup$ To be fair, if we are even considering using OTPs, then one can certainly use Information Theoretic MACs. $\endgroup$ Sep 27, 2022 at 8:28
  • 1
    $\begingroup$ @MarcIlunga you are too fair, I need to modify that part. $\endgroup$
    – kelalaka
    Sep 27, 2022 at 16:32
2
$\begingroup$

As the others have said, the fundamental disadvantage of a one-time pad, is that you have to securely exchange a key of equal length to the plaintext. This might not be practical for very large plaintexts.

In contrast, a cipher like AES uses a fixed length key, e.g. 128 bits (16 bytes) long, to encrypt messages of almost any length. This is clearly more convenient and practical as far as securely exchanging keys is concerned.

And AES can not in any way, shape or form be “brute forced”, if by “brute forced” you mean trying each of the possible (say) $2^{128}$ keys in turn. It’s not even possible to increment a counter from 0 to $2^{128}$, let alone do a trial decryption for each of those values, using any current or foreseen techniques.

Of course, a particular system might take a password or passphrase, and turn that into an AES key, using a key derivation function (KDF). Such systems are vulnerable to dictionary attacks, where you try many common words and phrases to see if any work. For example, if your password was “password”, this would undoubtedly fall instantly to a dictionary attack. But that’s quite different to a brute-force attack in my opinion.

In summary, one time pads are really not practical in many cases because of the need to securely exchange a key of equal length to the message. Ciphers such as AES are much more practical, as long as you choose your keys uniformly at random from the available keyspace, or (when using a KDF) choose unpredictable passwords or passphrases to reduce the risk of dictionary attacks.

$\endgroup$
2
  • $\begingroup$ Passwords and - to a lesser extend - passphrases generally do not have 128 bits of entropy. You'd have to use a generated password to come close to 128 bits, and a good password hash / PBKDF will only take you so far. $\endgroup$
    – Maarten Bodewes
    Sep 26, 2022 at 23:16
  • $\begingroup$ When I say "brute forced", I mean if you had an infinite amount of time and computing power, is it even possible to compute. This terminology is probably incorrect, hence the confusion. Obviously, a one-time pad cipher cannot be "brute forced" under this terminology, as brute-forcing a one-time pad cipher would yield every possible text of the given length with no distinguishing factors. $\endgroup$ Sep 27, 2022 at 10:44
0
$\begingroup$

It’s not.

Firstly, ”better” is a qualitative assessment like a feeling. It’s not a scientific metric as in is meat “better” than vegetable?

The answer is that AES is more “convenient” than the OTP in the majority of use cases. So three examples championing the OTP over AES:-

  1. OTPs are informationally secure for all time. This or the other side of the quantum computer revolution. AES isn’t. It may already have been broken. And we certainly can’t predict the future 20 years out. Both the US and China are slurping up vast amounts of internet traffic for decryption “later”. Consider the F-35 stealth fighter. Civilian academics can’t design one of those, therefore some might say they can’t exist. But they do as nation states can design and build them. And nation states might be able to break AES. It’s an extension of the “rolling your own” paradigm. Just because you can’t break it, doesn’t mean no other country can't. Post hoc ergo propter hoc.
  2. Key exchange is thought to be problematic. Consider wanting to message a chap in another place. If you’ve never met, how can you trust him? AES-GCM can’t help you. And if you’ve met him, you can exchange key material. NATO, the US, China, Japan, Switzerland, the EU, the banks and half of the world’s best technical universities are investing billions into quantum key distribution networks that securely exchange key material. It is possible though that all of those thousands of bankers, scientists and engineers are wrong.
  3. Authentication is thought to be problematic. What if a HMAC were appended to the OTP? That would create the situation whereby you’d have unbreakable theoretic security, and integrity and authenticity equal to that of AES-GCM. Or much better if a one time MAC were used. A win-win.

3 ½. Just how much messaging do you want? 1 GB of key is sufficient for 3 ½ million Tweet sized messages. You should not be using OTPs to transmit 8K UHD movies.

AES isn’t better than a OTP. It’s just more practical in more cases. Unless it’s already broken of course. Cryptographic monoculturism is extremely perilous, and the only field of human endeavour where all our eggs are de facto shoehorned into one basket. Ask any Irish potato or Dust Bowl farmer about monoculture.

$\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.