2
$\begingroup$

I'm curious what would happen in the following scenario:

Suppose an attacker gets a hold of a cipher-text of sufficiently large length. And suppose he has the means to verify a successful decryption. But the attacker has no clue what cipher is used and assumes it's unbreakable with anything but brute-force whatever it is. He also assumes it's a block cipher. (Thus, whatever operations the cipher performs are repeated over each block.)

  1. Suppose he knows the block is of length 128bit. How long (what is the complexity) will it take him to brute-force all possible operations that can be performed?

  2. What if it's XTS and the attacker doesn't know anything about any standards?

I guess this is just to contrast the security in obscurity argument, but I'm also interested in the complexity numbers.

Also, what would happen if you modify AES in some way, like adding some extra rounds or an extra operation, something simple. And make it such that the change is NOT hard-coded into the algorithm but is instead loaded as a module/script as PART of the key to access the encrypted data? How much complexity would that add to someone trying to get your plain-text if he doesn't even know precisely what algorithm is used.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Your premises are implausible in practice. What if an alien bought a pig at the market, and the pig the alien picked just happened to be able to fly? Hey, it could happen.... $\endgroup$
    – D.W.
    Commented Oct 25, 2013 at 6:11
  • $\begingroup$ D.W. your comment is not very helpful. Lets assume for now that "alien" can be replaced with "attacker that does not know the algorithm/details of encryption used". That might be common for an attacker if the protocol is new/unknown/uncommon. I think these are some interesting questions regardless and deserve an answer. $\endgroup$
    – NDF1
    Commented Oct 25, 2013 at 6:19
  • 1
    $\begingroup$ In this situation, the workload shifts from reverse engineering the algorithm from only ciphertext to acquisition of algorithm details, which would have a substantially lower workload. There are too many permutations to deal with, as the situation has occurred in our history many times, and it only falls with details of the implementation. $\endgroup$
    – Richie Frame
    Commented Oct 25, 2013 at 8:04
  • $\begingroup$ Your question reads like a Choose Your Own Adventure book. They're valid questions - but I suggest you break them up into smaller, more answerable questions. I also suggest you read on up Kerckhoffs's principle. $\endgroup$
    – hunter
    Commented Oct 25, 2013 at 12:13
  • $\begingroup$ 128 bit block, doesn't this mean there are 2^128 possible combinations and therefore 2^128 possible operations? $\endgroup$
    – Mark Litovsky
    Commented Oct 25, 2013 at 13:39

2 Answers 2

Reset to default
4
$\begingroup$

An unknown block-cipher with an $n$-bit block length can just be viewed as an arbitrary permutation of size $2^n$. Assuming you have the means to verify a correct decryption, you can just try each of every $2^n!$ possible permutations.

Naturally, if your ciphertext consists of fewer than $2^n$ distinct block values then you can omit permutations which result in previously-tried plaintexts.

An extreme example of this would be a ciphertext consisting of one block of $n$ bits which would need only a maximum of $2^n-1$ decryptions to be tested. This is of course significantly less than $2^n!$

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Yeah, $2^n!$ is huge for any nontrivial $n$. I suppose you might justify it by saying they're aliens or whatever. The first natural $k$ such that $k! > 2^{128}$ is $k=35$, and $35 \ll 2^{35} \ll 2^{128}$, for an idea of the scale of numbers you're dealing with. $\endgroup$
    – Reid
    Commented Oct 25, 2013 at 17:35
  • $\begingroup$ And for $n = 128$, the factorial itself has more than $10^{40}$ digits. (See WolframAlpha). $\endgroup$
    – forest
    Commented May 8, 2019 at 5:21
2
$\begingroup$

Regarding the last part of the question, this approach is called "key-dependent transformations", or "key-dependent S-boxes" if we speak about smaller blocks that are key-dependent.

While this approach complicates the attacker's life in general, it might actually weaken the construction as the resulting operation may be weak or strong depending on the key. It is hard to generate a family of transformations, indexed by the key, that are equally good. This approach has been tried in 1980-90s, but eventually a simple xor of the key into the cipher's state proved the best.

Improve this answer
$\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.