1
$\begingroup$

In all modern ciphers, even if one bit of input changes, then half of the output will change because of diffusion. Considering this, how exactly will knowing standard salutations, etc. ("Hello Alice" or other known parts of the message) be used to launch an attack. You don't know the whole PlainText but only part of the PlainText. So how exactly will it help?

$\endgroup$
5
  • $\begingroup$ Hint: what if your decipher the start of the ciphertext with key guesses and compare the outcome against standard greetings? $\endgroup$
    – fgrieu
    Jan 6 at 7:02
  • $\begingroup$ @fgrieu - what do you mean 'decipher only the start of the cipher text'? Would "Hello Alice, how are you" & "Hello Alice" encrypt to the same start of the cipher text? $\endgroup$
    – user93353
    Jan 6 at 7:06
  • 1
    $\begingroup$ No. In fact even the same plaintext encrypted twice should give different ciphertexts with a secure cipher. What I suggest is take a ciphertext, try to decipher it with incremental keys, and see which keys lead to a plaintext that starts with a greeting such as "Hello Alice". That automatically filters most bad keys. $\endgroup$
    – fgrieu
    Jan 6 at 13:57
  • $\begingroup$ @fgrieu - but how will that be any more effective than a brute force attack without knowing any plain text at all? You could take the ciphertext and do a similar exhautsive search and see if you get any meaningfull words by decrypting the ciphertext with those keys. $\endgroup$
    – user93353
    Jan 6 at 15:48
  • 1
    $\begingroup$ It will be slightly more effective because (a) we only need to decipher little ciphertext, only the beginning; and (b) we have a simple, highly selective filter. Also, not all plaintext has recognizable words. $\endgroup$
    – fgrieu
    Jan 6 at 17:26
4
$\begingroup$

Known Plaintext Attack (KPA) is the security level that is below of Chosen Plaintext Attack (CPA) that we want at least CPA from all ciphers. Actually, we want more in the modern cryptography; Ind-CPA.

The classical cryptography era contains lots of examples that can be easily broken with KPA attack; shift, permutation, Vegenere, and Hill ciphers are some examples.

In the modern era, the KPA can be used for key searching as below.

  • Brute-force attack; search for all keys
  # c = E(k,m) for some key k we are looking for
  for i in keys:
    if c == E(i,m):
       return i

An interesting example in the history was the RSA's DES challenges, which contains given partial information The unknown message is: on the full plaintext and the contestants are required to find the key given the full ciphertext. They used brute-force attacks similar to the above. The attack is successful since the key size of DES 56-bit.

This above can be still considered a classical way to find the key and the technological advances help to find the key. A modern novel attack is coming from Matsui and Yamagish in 1992 on their novel paper

This is now called the Lineart Attack. On attacking the DES, it requires $2^{43}$ known plaintexts by Matsui in 1994.

If you want to learn about the Linear attack the tutorial by Heys is a good starting point.

Now back your specific question;

("Hello Alice" or other known parts of the message) be used to launch an attack. You don't know the whole PlainText but only part of the PlainText. So how exactly will it help?

First of all, with the Kerckhoff's principle, we assume that except the key we assume all known about the target system, like how the messages turned into bytes for encryption.

  • If the position is known as in the RSA DES challenges, then this knowledge can be easily turned into a known-plaintext if fits into one block. One needs at least 16 characters for AES and 8 for DES.

    The Hello Alice is forming more than one block for DES Hello Al and ice?????. If you brute-force the DES then the first block can be used to find the key candidates, yes there be more than one candidate. Then the decryption of the next blocks can be used to pinpoint the messages.

    # c = E(k,m) for some key k 
    # we are looking for the possibele key for full known message block m
    for i in keys:
       if c == E(i,m):
          m' = D(i,c')             # c' is the other message blocks  
          if m' is a valid string  # check the validity of m'
            return i 
    
    • A special case if we don't have a full block, then execute the brute force by decryption, and for each possible candidate, which contains the partial information, look for the meaningful strings by decrypting the rest ciphertexts. This can be automized with tools like Linux's string command and possibly check the PKCS#5 padding at the end will eliminate most of the candidates.
  • If the position is not known

    This is a little problem to be solved compared to brute force and really depends on the message size. If the message size is $t$ and the known message part is $l$ then one needs to look for $t-l$ positions. Therefore the cost of brute force was multiplied with $t-l$. For short messages, this is not a real problem, however when the message size is more than $2^{32}$ then the brute-force cost become $2^{80}$ for DES and $2^{160}$ for AES.

$\endgroup$
7
  • $\begingroup$ My question was about partial PT - only the RSA's DES challenges part in the your answer is relevant to that I think. And the Q&A doesn't mention how exactly they check partial text - all it says is "Check the beginning of the message; it must start with ..." - How do you check this - unless you have the full Plaintext & not just a part of it. $\endgroup$
    – user93353
    Jan 6 at 10:50
  • $\begingroup$ @user93353 It was explained on the link that I've given. Did you read it? The message fits at least one block to execute a brute for and you check the other blocks for valid strings and the PKCS#5 padding, too. $\endgroup$
    – kelalaka
    Jan 6 at 10:56
  • $\begingroup$ Are you referring to this like - crypto.stackexchange.com/questions/64863/… - I did read it - all it says about the partial text is this - Check the beginning of the message; it must start with "The unknown message is:" - what I want to know is how to check this? $\endgroup$
    – user93353
    Jan 6 at 11:49
  • $\begingroup$ Also - The message fits at least one block to execute a brute for - how the partial text is 23 bytes - so it's not exactly the block size $\endgroup$
    – user93353
    Jan 6 at 11:53
  • $\begingroup$ Block size is 8 byte for DES and 16 bytes for AES, $\endgroup$
    – kelalaka
    Jan 6 at 11:54
0
$\begingroup$

Known plaintext attacks were successfully launched into enigma during second world war if I am not wrong. Modern block ciphers are designed to be immune to known plaintext attacks, I guess. One thing you can do is change content in stream ciphers if you know the exact plain text content in exact location if no integrity check is done, but it won't allow you to do any thing else. And block ciphers are designed in a way that you cannot recover the key from a realistic number of raw (unpadded) plain text and cipher text pairs.

$\endgroup$

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.