EASYCTF - Not OTP
21 Feb 2018It seems we’ve intercepted 2 strings that were both encrypted with what looks like OTP! Is it possible to decrypt them?
For this challenge we’ve been given a text file containing the following :
c1 = 38445d4e5311544249005351535f005d5d0c575b5e4f481155504e495740145f4c505c5c0e196044454817564d4e12515a5f4f12465c4a45431245430050154b4d4d415c560c4f54144440415f595845494c125953575513454e11525e484550424941595b5a4b
c2 = 3343464b415550424b415551454b00405b4553135e5f00455f540c535750464954154a5852505a4b00455f5458004b5f430c575b58550c4e5444545e0056405d5f53101055404155145d5f0053565f59524c54574f46416c5854416e525e11506f485206554e51
The two strings have the same length, so we can think that they have been encrypted with the same key. Let K be the encryption key, C1 and C2 the two ciphers, and M1 and M2 the corresponding plain texts with:
C1 = M1 ⊕ K, C2 = M2 ⊕ K
Then, we have :
R = C1 ⊕ C2 = M1 ⊕ M2
If we consider that the plain texts are made with comprehensive english language, if we xor R with a word contained in M1 at the offset x in the string, it will reveal a part of the message M2.
So we need to xor R with a known or potential substring at the offset 0 of R. If the result looks like an english word, it means that the substring may be in M1 or M2 at the offset 0. Else, we need to do the same again at offset +1.
This method is called crib dragging.
For this challenge, we can presume that the substring ‘easyctf{‘ is contained in M1 or M2. When xoring this substring with R, we find the substring “intext u” (let’s call it S) at the offset 76. In order to find out from which cipher (C1 or C2) this substring comes from, we can xor S with C1 and C2, at the offset 76. This will reveal a part of the key. With C2, it gives us :
:8+<*8t"
This looks pretty much like random text…
With C1, it gives us :
67, 182,
This one looks more like a pattern, with numbers, spaces and commas. It should be a part of the key.
At this point we know 8 characters from M1, M2 and K at the offset 76:
M1 :
intext uM2 :easyctf{K :67, 182,
Then we have two possibilities :
- xor R with an english word that is likely to appear in a sentence in order to find another part of M1 or M2
- guess parts of M1 or M2, then xor it with the corresponding cipher to check if the result looks like the key pattern
If we guess a part of one of the plain texts then it is quite easy to find out a part of the other plain text at the same offset. In this challenge, the flag was at the en of the 2nd message M2 ( from offset 76 to the end ). As the process to recover the flag is quite long, we didn’t take the time to recover the full plain texts, but only enough words from the end to be able to rebuild the flag. We ended up with something like :
M1 : …can also refer to a sample of plaintext used in the breaking
M2 : ……you will never guess! flag is
easyctf{otp_ttp_cr1b_dr4gz}
(the end of M1 might not be exact)
