Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Given two sets of plaintexts and their corresponding ciphertexts, how does one determine the key $K$?

The ciphertexts are:

$$C_1= (P_1 \oplus K_0) + K_1$$

and

$$C_2= (P_2 \oplus K_0) + K_1$$

$K = K_0 || K_1$ (string of bits).

where $+$ means addition mod $2^n$.

How do we find the unknowns (eg, $K_1$)?

share|improve this question
    
What do you mean by $+$ (as opposed to xor) in the above equations? Do you mean addition modulo $2^n$? –  poncho Nov 12 '13 at 20:09
    
@poncho : _italic_yes –  eagle93 Nov 12 '13 at 20:22
1  
Do you know (or do you have additional information about) the plaintexts? Normally it is required to have more than two ciphertexts to retrieve the key if you don't know the plaintext. To show you that you cannot always retrieve the key from above, if $P_1$ == $P_2$ then $C_1$ == $C_2$ ... –  owlstead Nov 12 '13 at 22:04

2 Answers 2

There is a straightforward brute force method. For example, take the lowest $8$ bits of everything and check for valid values of $K_1$ and $K_2$, mod $2^8$. You will need about $2^{16}$ checks to get the lower $8$ bits of $K_1$ and $K_2$. Proceed then to values mod $2^{16}$, as you know the lower $8$ bits of $K_1$ and $K_2$, only bits $8\dots15$ of these must be checked, the effort is $2^{16}$ again. Proceed until you get $K_1$ and $K_2$ in full.

Better, do the same but instead of $8$ bit increments do $1$ bit increments. So, brute force for values mod 2, mod $4$ ... mod $2^n$. You will need to check $4$ different values each step (one bit from $K_1$ and another from $K_2$), and do this $n$ times. Therefore, the cost of finding $K_1$ and $K_2$ is $4n$, meaning this isn't just polynomial in respect of the number of bits: it's linear.

However, must be noted that if $P_1 \equiv P_2 \pmod{2^i}$, then the first $i$ bits of $K_1$ and $K_2$ are indeterminable, so more plaintext/ciphertext pairs will be needed until finding some pair where $P_1 \not\equiv P_2 \pmod{2}$, to retrieve then the whole keys.

Update: Probably there are (for a given $n$) $2$ pairs $(K_1,K_2)$ compatible with an adequate $(P_1,P_2)$ pair, so this method should check incrementally $2$ pairs of keys.

share|improve this answer
1  
Actually, you may take any 8-bit substring, guess the corresponding carries from the lower bits, and obtain subkey candidates. –  Dmitry Khovratovich Nov 14 '13 at 10:12

With this cipher, it's pretty easy to retrieve at least 1 key that is consistent with 2 pairs of plaintext,ciphertext . (Other ciphers are better or worse at making it nearly impossible to recover even 1 key consistent with the given plaintext,ciphertext).

With this cipher, it is not possible to fully retrieve the key from only 2 known pairs of plaintext,ciphertext. (Other ciphers are better or worse at keeping the key secret after plaintext,ciphertext pairs are leaked).

For example: ( n=2 for simplicity )

c1 = ( 00 xor 01 ) + 10 (mod 2^2) == 11
c2 = ( 10 xor 01 ) + 10 (mod 2^2) == 01
c3 = ( 11 xor 01 ) + 10 (mod 2^2) == 00

So (plaintext, ciphertext) pairs 00-->11 and 10-->01 are consistent with K0==01, K1==10.

However,

c1 = ( 00 xor 00 ) + 11 (mod 2^2) == 11
c2 = ( 10 xor 00 ) + 11 (mod 2^2) == 01
c3 = ( 11 xor 00 ) + 11 (mod 2^2) == 10

So (plaintext, ciphertext) pairs 00-->11 and 10-->01 are also consistent with K0==00, K1==11.

As you can see, the third pair 11-->00 or 11-->10 can distinguish between these two possibilities, so they are not equivalent keys.

(On the other hand, the key K0=00, K1==11 is equivalent to the key K0=10, K1=01 -- given any plaintext, either key gives identically the same ciphertext as the other set of keys).

A quick way to find a key consistent with a given set of plaintext,ciphertext pairs (but not necessarily the key) is:

  • start with a candidate key K0 == 0 and K1 == all-ones, then use the following procedure to iteratively improve them.
  • Start with B0 as the most-significant bit position, and start with B1 as the next-most-significant bit position. (Every time through the loop, move B0 and B1 by 1 bit to the next-most-significant position).

Loop:

  • Generate 8 candidate keys from the current candidate key:

    1. Keep K0 and K1 the same.
    2. Flip K1 at bit position B0.
    3. Flip K0 at bit position B0.
    4. Flip both K0 and K1 at bit position B0.
    5. through 8. the same as the above 1 through 4, except also flip K1 at bit position B1 to block the carry chain.
  • Use each of the 8 candidate keys to encipher all the plaintexts.

  • If any candidate has no differences between its ciphertexts and the actual ciphertexts, that candidate may be the actual key used. Done!
  • Otherwise, for each candidate, find the most-significant bit position that differs between the actual ciphertext corresponding to that plaintext and this trial cipher.
  • If that bit position is the same as B0 or a more-significant bit position, this candidate is worse -- throw it away.
  • There should be at least 1 candidate that is better -- use those candidates the next time through the loop.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.