1
$\begingroup$

Let say we have $N$ ciphertexts and each of them looks like this:

2iob3gRLvabM0QnMtgtMG5y4kCm=2xmLkasBUasLkQkjyQtQ3NFhU5UNkQ95U1nmk5UltxwZt1DltaojkQuHkxyXQI7=GYzYYf7t25ymQd7wtHJ52xWM3NJR3QTLUxmI3IZMU54NkitMGHz=2xmLvQnVtQUBk5Wa

assume it's encrypted URL string and we know output (actual URL) of each $N$ ciphertexts. In addition we know that the key is $m$ digits. So my question is how to assess complexity of breaking the $N+1$ ciphertext?

$\endgroup$
  • 5
    $\begingroup$ That's the definition of a known-plaintext attack. Unless the crypto is flawed, you are out of luck. $\endgroup$ – yyyyyyy Jul 29 '16 at 12:09
  • $\begingroup$ It will be very helpful if one could share a ref where i can read about impossibility of breaking ciphertext in respect of condition described above. $\endgroup$ – andreo Jul 29 '16 at 12:18
  • $\begingroup$ en.wikipedia.org/wiki/Known-plaintext_attack $\endgroup$ – mikeazo Jul 29 '16 at 12:22
  • $\begingroup$ Each ciphertext is quite similar (some substrings of ciphertext repeated in other ciphertexts ) and we know all them generated from URL. Is it weakness? I'm not going to break my goal is to figure out how complex this problem or find any proof of impossibility. $\endgroup$ – andreo Jul 29 '16 at 12:34
  • 1
    $\begingroup$ Repeating ciphertext blocks are a symptom of crypto being not applied correctly. Some of possible reasons include: usage of incorrect mode (such as ECB) or improper use of IV or nonce. Some modes require non-repeating IV/nonce and repeating IV/nonce will defeat security. $\endgroup$ – user4982 Jul 29 '16 at 15:24
0
$\begingroup$

The accepted answer from Maarten Bodewes (https://crypto.stackexchange.com/a/38045) is applicable to the common case, assuming that proper secure encryption has been applied.

I.e. it is true that knowing some plaintexts is not useful in breaking encryption except to validated the probable key(s) found.

Repeating ciphertext substrings

However, additional information from comments states that some ciphertext substrings repeat. Taking this into account, I provide additional detail regarding improper ways to do encryption. Repeat of ciphertext substrings means that some parts of inputs map to same output. This likely means non-proper mode of operation has been applied or mode of operation has been misused, as secure encryption instead produce ciphertexts which appear entirely unrelated.

To analyze the changed segments, it is first needed to decode them.

0000000: da2a 1bde 044b bda6 ccd1 09cc b60b 4c1b  .*...K........L.
0000010: 9cb8 9029 80db 198b 91ab 0151 ab0b 9109  ...).......Q....
0000020: 23c9 0b50 dcd1 6153 950d 910f 7953 59    #..P..aS....ySY

0000000: da2a 1bde 044b bda6 ccd1 010c b604 ccd1  .*...K..........
0000010: a93c d8d9 80db 198b 91ab 0151 ab0b 3b11  .<.........Q..;.
0000020: 15cb 5de6 9239 f551 0ba3 cb11 59ca 00    ..]..9.Q....Y..

If the length of changed segments is exactly 8 or 16 bytes at some 8 or 16 byte multiple location, changes are that the encryption is using ECB mode and cipher with 64-bit or 128-bit block, such as DES or AES. It could be something similar to Adobe ECB password database.

However, the segments in decoded ciphertext that have been changed are few bits here and there, instead of full 8 or 16 bytes. This could be result of e.g. misusing counter mode of operation, where plaintext is XORed with blocks from AES.

Conclusions:

  1. Repeating parts in output mean that the parts have been improperly encrypted or those parts have not been encrypted at all.
  2. The further investigation of this issue would be specific to this system where the problem has been detected. It is likely very laborious to investigate the security of the system and to fix it.
$\endgroup$
  • $\begingroup$ Ciphertexts came from <object> HTML tag in file (url path) parameter. This is secure protection provided by some flash player. $\endgroup$ – andreo Jul 29 '16 at 20:37
1
$\begingroup$

The known plaintext is only a useful tool for establishing that you actually found the right key if we assume a secure cipher (and mode of operation, etc.). It won't help you creating a faster than brute-force attack, as ciphers are assumed to be secure against known plaintext attacks.

So the complexity of breaking the cipher is simply still $m - 1$ (half the key space) on average, i.e. no change from normal brute forcing.

$\endgroup$
  • $\begingroup$ m is already the key size in bits. So it's not m / 2 as I first wrote but m - 1. $\endgroup$ – Maarten Bodewes Jul 29 '16 at 15:28
  • $\begingroup$ what you think about repeating in each ciphertext? Is it matter? $\endgroup$ – andreo Jul 29 '16 at 17:40
  • $\begingroup$ If ciphertext repeats it indicates that something is wrong with the mode of encryption. That could actually show some information such as repeating blocks in ECB mode up to the possibility of IV reuse in CTR mode which can completely open up the plaintext (but not the key). $\endgroup$ – Maarten Bodewes Jul 30 '16 at 11:41

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.