Is there a method of encryption where your key is made up of $n \cdot s$ bits, but also such that an attacker would know when they've successfully cracked each $s$-bit part?

For example, the full key could be $\texttt{1011 0101 1010}$, for $(n=3, s=4)$and you would be able to know if you successfully guessed that the first four digits are $\texttt{1011}$?

Note the entire key could be discovered in $n \cdot 2^s$ time if you individually cracked each of the $n$ parts.

Think of it by analogy like cracking a combination lock by sound, where you would know when you successfully discovered the first number, then the second number, and finally the third number?

  • 1
    $\begingroup$ whats the motivation for proposing a weak scheme like this? $\endgroup$ – kodlu Jul 30 '18 at 5:27
  • $\begingroup$ I'm just wondering $\endgroup$ – Some Guy Jul 30 '18 at 20:08

Encrypt a short known plaintext ($s$ bits) using truncated keys (to $s$, $2s$, $3s$, etc. bits) and publish them alongside the ciphertext. Then an attacker can break them in order of increasing keylength, until they recover the full key.

There is a quite similar vulnerability when performing a chosen-ciphertext (online) attack against short polynomial MACs. For example consider GCM with a short 32-bit authentication tag (hence you should never use short tags). The attacker submits messages to an oracle and learns if they're accepted or not. After a successful forgery (chance $2^{-32}$) the attacker learns 32-bits of the MAC key. After several successful forgeries they can recover the full MAC key. The decryption key can then be recovered using standard oracle attacks against unauthenticated CTR mode.

|improve this answer|||||

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.